Measuring and Modeling Bipartite Graphs with Community Structure

Abstract

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.

Publication
Journal of Complex Networks
Date
Tags
Citation
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. https://doi.org/10.1093/comnet/cnx001

Keywords

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

BibTeX

@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},
}