Portal de Periódicos da CAPES

Exploring cohesive subgraphs with vertex engagement and tie strength in bipartite graphs

2021; Elsevier BV; Volume: 572; Linguagem: Inglês

10.1016/j.ins.2021.04.027

1872-6291

Yizhang He, Kai Wang, Wenjie Zhang, Xuemin Lin, Ying Zhang,

Advanced Graph Theory Research

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 2Dindex 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.