WCCS: Efficient Wedge Conductance Community Search over Large Temporal Bipartite Graphs (Full Paper)

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 $(\alpha,\beta)$-core to a higher-order $(\alpha,\beta,\tau)$-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.