Measuring and Modeling Bipartite Graphs with Community Structure


Network science is a powerful tool for analyzing complex systems in fields ranging from sociology to engineering to biology. This article is focused on generative models of large-scale bipartite graphs, also known as two-way graphs or two-mode networks. We propose two generative models that can be easily tuned to reproduce the characteristics of real-world networks, not just qualitatively but quantitatively. The characteristics we consider are the degree distributions and the metamorphosis coefficient. The metamorphosis coefficient, a bipartite analogue of the clustering coefficient, is the proportion of length-three paths that participate in length-four cycles. Having a high metamorphosis coefficient is a necessary condition for close-knit community structure. We define edge, node and degreewise metamorphosis coefficients, enabling a more detailed understanding of the bipartite connectivity that is not explained by degree distribution alone. Our first model, bipartite Chung-Lu, is able to reproduce real-world degree distributions, and our second model, bipartite block two-level Erdős-Rényi, reproduces both the degree distributions as well as the degreewise metamorphosis coefficients. We demonstrate the effectiveness of these models on several real-world data sets.

Journal of Complex Networks
S. Aksoy, T. G. Kolda, A. Pinar. Measuring and Modeling Bipartite Graphs with Community Structure. Journal of Complex Networks, Vol. 5, No. 4, pp. 581-603, 2017.


bipartite generative graph model, two-way graph model, two-mode network, metamorphosis coefficient, bipartite clustering coefficient, complex networks


author = {Sinan Aksoy and Tamara G. Kolda and Ali Pinar}, 
title = {Measuring and Modeling Bipartite Graphs with Community Structure}, 
journal = {Journal of Complex Networks}, 
volume = {5}, 
number = {4}, 
pages = {581-603}, 
month = {March}, 
year = {2017},
doi = {10.1093/comnet/cnx001},	
url = {},
eprint = {1607.08673},