Research On Counting The Number Of （m,n） Bipartite Cliques On Large-scale Bipartite Graph

A bipartite graph can model the relationship between two different types of entities.Cliques in bipartite graphs are called bipartite cliques,which are the basic dense substructures in bipartite graphs and have important applications in many fields.The（m,n）bipartite clique refers to the bipartite clique with the number of nodes in the two layers being m and n,respectively.It is very important to calculate the number of（m,n）bipartite cliques in a given bipartite graph.Existing bipartite clique counting algorithms can only deal with（2,2）bipartite clique,but cannot handle the general（m,n）bipartite clique counting problem.This paper studies how to efficiently calculate the number of（m,n）bipartite cliques on a large-scale bipartite graph.The specific research contents are as follows:Firstly,an enumeration counting algorithm CNBC based on depth-first search is proposed.The algorithm selects the U layer of the bipartite graph as the search layer,and then enumerates all possible m node combinations in the U layer.If the number of common neighbors k of these nodes is greater than or equal to n,it means that a（m,k）bipartite clique has been searched,and the number of（m,n）bipartite cliques contained in it is C_kⁿ.By enumerating all（m,k）bipartite cliques in the bipartite graph,the number of（m,n）bipartite cliques in the bipartite graph can be calculated eventually.Secondly,for the problem of large search space of CNBC algorithm,an optimization algorithm CNBC MBC based on maximum bipartite clique is proposed.The algorithm first uses graph reduction strategy based on node degree to reduce the size of the bipartite graph.A subgraph is then peeled from the bipartite graph using a subgraph stripping technique based on the maximum bipartite clique.Finally,the solution based on the subgraph can greatly reduce the search space.Finally,based on multiple real bipartite graph datasets,the efficiency of the optimization algorithm CNBC＿MBC proposed in this paper is verified by taking the running time of the algorithm as the indicator.The scalability of the algorithm is tested by changing the values of the thresholds m and n.The experimental results show that the optimization algorithm proposed in this paper can efficiently calculate the number of（m,n）bipartite cliques in a bipartite graph and has good scalability.