Efficient search finds stronger communities in time-changing bipartite graphs
WCCS: Efficient Wedge Conductance Community Search over Large Temporal Bipartite Graphs (Full Paper)
Social and Information Networks
Summary
Bipartite graphs model relationships between two types of entities, like buyers and products, but many existing methods miss how these connections change over time. The authors introduce a new way to find groups, or communities, that are tightly connected and well separated, even if their interactions happen at irregular times. They develop a new measure called temporal wedge conductance and efficient methods to identify these communities quickly on large datasets. Their approach works better than previous ones by capturing more complex interaction patterns without requiring connections to happen in strict order.
What this means in practice
- •For e-commerce data teams: Identify cohesive groups of users and products interacting irregularly over time for better recommendation systems.
- •For social network engineers: Detect temporally cohesive communities in user-item or user-activity networks without requiring strict consecutive interactions.
Authors
Longlong Lin, Wei Chen, Pingpeng Yuan, Ruikun Luo, Qiangqiang Dai, Rong-Hua Li
Abstract
Bipartite graphs are ubiquitous for modeling complex interactions between two distinct entity types across numerous practical applications such as e-commerce, academic networks, and social systems. Despite significant progress in community search over bipartite graphs, most prior work is limited to static settings and ignores the rich temporal dynamics present in real-world networks. Moreover, existing methods typically adopt edge-centric measures and strict consecutivity constraints, failing to capture higher-order interactions and frequent yet non-consecutive activities. More importantly, they often neglect the crucial community-quality requirements of both internal cohesiveness and external sparsity, failing to identify critical nodes or including many irrelevant nodes. To address these dilemmas, we propose the novel problem of \emph{Wedge Conductance Community Search (WCCS)}, which aims to identify a query-dependent community that is not only structurally and temporally cohesive but also well-separated from the rest of the network over non-consecutive timestamps. We formalize WCCS by generalizing the classical $(α,β)$-core to a higher-order $(α,β,τ)$-wedge core, and by proposing a novel temporal wedge conductance metric that explicitly balances internal density and external sparsity. To solve WCCS efficiently, we first develop an online priority-driven filter-and-expand framework with several effective pruning techniques and a powerful geometric slope optimization for rapid temporal wedge conductance calculation. Subsequently, to further improve scalability, we propose an offline compressed index to accelerate search. Finally, comprehensive experiments on seven real-world datasets demonstrate the effectiveness, efficiency, and scalability of our solutions compared to eight competitors.