# Measuring and Modeling Bipartite Graphs with Community Structure

arXiv: https://arxiv.org/abs/1607.08673 · HTML: https://mlsanity.com/paper/1607.08673/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jul 2016.

## Built on by (most cited first, 2 of 2)

- [Hypergraph Artificial Benchmark for Community Detection (h-ABCD)](https://mlsanity.com/paper/2210.15009/) (2022)
- [Alice and the Caterpillar: A more descriptive null model for assessing data mining results](https://mlsanity.com/paper/2506.09764/) (2025)

## Abstract (arXiv)

Network science is a powerful tool for analyzing complex systems in fields ranging from sociology to engineering to biology. This paper 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 (CL), is able to reproduce real-world degree distributions, and our second model, bipartite block two-level Erd"os-R'enyi (BTER), 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.