Paper detail

Exploring Cohesive Subgraphs with Vertex Engagement and Tie Strength in Bipartite Graphs

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\times2$-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.