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 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ös-Rényi (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.

References in corpus (2)

• Modularity and community detection in bipartite networks
• Emergence of a non-scaling degree distribution in bipartite networks: a numerical and analytical study

Cited by in corpus (13)

• Hypergraph Motifs: Concepts, Algorithms, and Discoveries
• The simpliciality of higher-order networks
• A generative graph model for electrical infrastructure networks
• FLEET: Butterfly Estimation from a Bipartite Graph Stream
• Efficient Temporal Butterfly Counting and Enumeration on Temporal Bipartite Graphs
• Motif-driven Dense Subgraph Discovery in Directed and Labeled Networks
• Reticula: A temporal network and hypergraph analysis software package
• Common Neighborhood Estimation over Bipartite Graphs under Local Differential Privacy
• Clustering coefficients for networks with higher order interactions
• Searching Personalized $k$-wing in Large and Dynamic Bipartite Graphs
• Clustering Coefficient Reflecting Pairwise Relationships within Hyperedges
• Higher-order null models as a lens for social systems
• Alice and the Caterpillar: A more descriptive null model for assessing data mining results