Community Search Algorithms Of Dense Subgraphs In Bipartite Graph

Bipartite graphs are widely used to capture the relationships between two types of entities.Community search is an important problem in bipartite graph analysis.We can obtain different information based on different subgraphs and communities.However,for some existed models and algorithms,they have limited applicability and low efficiency.Finding the maximum balanced biclique(MBB)is an important problem.A biclique is balanced if its two disjoint vertex sets are of equal size.However,in realworld scenarios,each vertex is associated with a weight to denote its properties.For weighted bipartite graphs,the previous studies for MBB are no longer applicable due to the ignorance of weight.Meanwhile,biclique percolation community(BPC)search is also a fundamental problem.Existing online approach has to enumerate all the maximal bicliques and compute the results based on these bicliques.Considering the large number of maximal bicliques in real graphs and the high frequency of BPC search requests issued in real applications,existing approach is cost prohibitive to obtain the result.This paper focus on these two major problems.Firstly,to fill the gap of MBB problem,we propose a reasonable definition of“balance” by restricting the weight difference between two sides of a biclique within k.Given a weighted bipartite graph G and a constraint k,we aim to find the maximum k-balanced biclique(Maxk BB)with the maximum weight.To address the problem,we first propose an approach based on biclique enumeration on single side of G following the Branch-and-Bound framework.To improve the performance,we further devise three optimization strategies to prune invalid search branches.Moreover,we utilize graph reduction strategy to reduce the redundant search space.Secondly,motivated by BPC problem,we devise a novel index-based(BPC-Index)approach.Based on the index,we can obtain the result in near-optimal time with wellbounded index space.We further devise an efficient index construction algorithm.Moreover,we also extend our indexing method to address the personalized BPC search problem,which is one of the most common variants of BPC search.Extensive experiments are conducted on real bipartite datasets to demonstrate the efficiency,effectiveness and scalability of our proposed algorithms and models.