Discovering Significant Communities on Bipartite Graphs: An Index-Based Approach

Bipartite graphs are widely used to model relationships between two types of entities. Community search retrieves densely connected subgraphs containing a query vertex, which has been extensively studied on unipartite graphs. However, it remains largely unexplored on bipartite graphs. Moreover, all existing cohesive subgraph models on bipartite graphs only measure the structure cohesiveness while overlooking the edge weight. In this paper, we study the significant (alpha,beta)-community search problem on weighted bipartite graphs. Given a query vertex q, we aim to find the significant (alpha,beta)-community R of q which adopts (alpha,beta)-core to characterize the engagement level of vertices, and maximizes the minimum edge weight (significance) within R. To support fast retrieval of R, we first obtain the maximal connected subgraph of (alpha,beta)-core containing q(the (alpha,beta)-community), and the search space is limited to this subgraph with a much smaller size than the original graph. A novel index structure is presented to support retrieving the (alpha,beta)-community in optimal time. Efficient index maintenance techniques are also proposed to handle dynamic graphs. To further obtain R, we develop peeling and expansion algorithms. The experimental results on real graphs validate the effectiveness and efficiency of our proposed techniques.

Automated summary

This paper investigates the significant (alpha,beta)-community search problem on weighted bipartite graphs. The goal is to find the significant (alpha,beta)-community R of a query vertex q that characterizes the engagement level of vertices using (alpha,beta)-core, and maximizes the minimum edge weight (significance) within R. To support fast retrieval, a novel index structure and efficient index maintenance techniques are proposed. Peeling and expansion algorithms are developed to obtain R. Experimental results validate the effectiveness and efficiency of the proposed techniques.