Journal Article

Measuring and modeling bipartite graphs with community structure

Sinan G. Aksoy, Tamara G. Kolda and Ali Pinar

in Journal of Complex Networks

Volume 5, issue 4, pages 581-603
Published in print August 2017 | ISSN: 2051-1310
Published online March 2017 | e-ISSN: 2051-1329 | DOI: https://dx.doi.org/10.1093/comnet/cnx001
Measuring and modeling bipartite graphs with community structure

More Like This

Show all results sharing these subjects:

  • Mathematics
  • Computer Science

GO

Show Summary Details

Preview

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.

Keywords: bipartite generative graph model; two-way graph model; two-mode network; metamorphosis coefficient; bipartite clustering coefficient; complex networks

Journal Article.  7036 words.  Illustrated.

Subjects: Mathematics ; Computer Science

Full text: subscription required

How to subscribe Recommend to my Librarian

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content. subscribe or purchase to access all content.