Quantitative function and algorithm for community detection in bipartite networks

Community detection in complex networks is a topic of high interest in many scientific fields. A bipartite network is a special type of complex network whose nodes are decomposed into two disjoint sets such that no two nodes within the same set are adjacent. Many relationships in real-world systems can be represented by a bipartite network, such as predator-prey relationships, plant-pollinator interactions, and drug-target interactions. While community detection in unipartite networks has been extensively studied in the past decade, identification of modules or communities in bipartite networks is still in its early stage. Several quantitative functions have been developed for evaluating the quality of bipartite network divisions, however, these functions were designed based on null model comparisons and thus are subject to certain resolution limits. In this paper, we propose a new quantitative function called bipartite partition density for community detection in bipartite networks, and use some network examples to demonstrate that this quantitative function is superior to the widely used Barber's bipartite modularity and other functions. Based on the bipartite partition density, the bipartite network community detection problem is formulated into an integer nonlinear programming model in which a bipartite network can be partitioned into reasonable overlapping communities by maximizing the quantitative function. We further develop a heuristic adapted label propagation algorithm (BiLPA) to optimize the bipartite partition density in large-scale bipartite networks. BiLPA is efficient and does not require any prior knowledge about the number of communities in the networks. We conduct extensive experiments on simulated and real-world networks and demonstrate that BiLPA can successfully identify the community structures of bipartite networks.