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

DOI10.1016/J.INS.2021.04.027MaRDI QIDQ6092095zbMATH OpenOpenAlexFDO

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

Publication date 23 November 2023

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.04054

zbMATH Keywords

bipartite graphclassificationcohesive subgraphtie strengthvertex engagement

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Graph theory (including graph drawing) in computer science (68R10) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: We propose a novel cohesive subgraph model called $au$-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 $au$ butterflies ($2imes2$-bicliques). $$-core requires each vertex on the upper or lower level to have at least $alpha$ or $$ strong ties, given strength level $au$. To retrieve the vertices of $$-core optimally, we construct index $$ 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 $$, and $I_{alpha,au}$ that selectively store the vertices of $$-core for some $$, and $au$. 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.

Recommendations

• Generalized core maintenance of dynamic bipartite graphs
• Effective and efficient community search with size constraint on bipartite graphs
• Cohesive subgraph search over large heterogeneous information networks
• Core decomposition, maintenance and applications
• Hypercore decomposition for non-fragile hyperedges: concepts, algorithms, observations, and applications

Cites work

• Deep learning
• Preventing unraveling in social networks: the anchored \(k\)-core problem

This page was built for publication: Exploring cohesive subgraphs with vertex engagement and tie strength in bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6092095)