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.
bipartite generative graph model, two-way graph model, two-mode network, metamorphosis coefficient, bipartite clustering coefficient, complex networks
@article{AkKoPi17,
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 = {https://academic.oup.com/comnet/article/5/4/581/3091113/Measuring-and-modeling-bipartite-graphs-with},
eprint = {1607.08673},
}