Exploring cohesive subgraphs with vertex engagement and tie strength in bipartite graphs
- Publisher:
- Elsevier BV
- Publication Type:
- Journal Article
- Citation:
- Information Sciences, 2021, 572, pp. 277-296
- Issue Date:
- 2021-09-01
Closed Access
Filename | Description | Size | |||
---|---|---|---|---|---|
1-s2.0-S0020025521003480-main.pdf | Accepted version | 3.68 MB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
We propose a novel cohesive subgraph model called τ-strengthened (α,β)-core (denoted as (α,β)τ-core), which is the first to consider both tie strength and vertex engagement on bipartite graphs. An edge is a strong tie if contained in at least τ butterflies (2×2-bicliques). (α,β)τ-core requires each vertex on the upper or lower level to have at least α or β strong ties, given strength level τ. To retrieve the vertices of (α,β)τ-core optimally, we construct index Iα,β,τ to store all (α,β)τ-cores. Effective optimization techniques are proposed to improve index construction. To make our idea practical on large graphs, we propose 2D-indexes Iα,β,Iβ,τ, and Iα,τ that selectively store the vertices of (α,β)τ-core for some α,β, and τ. The 2D-indexes are more space-efficient and require less construction time, each of which can support (α,β)τ-core queries. As query efficiency depends on input parameters and the choice of 2D-index, we propose a learning-based hybrid computation paradigm by training a feed-forward neural network to predict the optimal choice of 2D-index that minimizes the query time. Extensive experiments show that (1) (α,β)τ-core is an effective model capturing unique and important cohesive subgraphs; (2) the proposed techniques significantly improve the efficiency of index construction and query processing.
Please use this identifier to cite or link to this item: