A simple bipartite graph projection model for clustering in networks

Abstract

Graph datasets are frequently constructed by a projection of a bipartite graph, where two nodes are connected in the projection if they share a common neighbor in the bipartite graph; for example, a coauthorship graph is a projection of an author-publication bipartite graph. Analyzing the structure of the projected graph is common, but we do not have a good understanding of the consequences of the projection on such analyses. Here, we propose and analyze a random graph model to study what properties we can expect from the projection step. Our model is based on a Chung-Lu random graph for constructing the bipartite representation, which enables us to rigorously analyze the projected graph. We show that common network properties such as sparsity, heavy-tailed degree distributions, local clustering at nodes, the inverse relationship between node degree, and global transitivity can be explained and analyzed through this simple model. We also develop a fast sampling algorithm for our model, which we show is provably optimal for certain input distributions. Numerical simulations where model parameters come from real-world datasets show that much of the clustering behavior in some datasets can just be explained by the projection step.

References in corpus (18)

• Emergence of scaling in random networks
• The structure and function of complex networks
• The structure of scientific collaboration networks
• Hierarchical organization of modularity in metabolic networks
• Random graphs with arbitrary degree distributions and their applications
• Evolution of networks
• Stochastic blockmodels and community structure in networks
• The Dynamics of Viral Marketing
• Higher-order organization of complex networks
• How to project a bipartite network?
• Powerlaw: a Python package for analysis of heavy-tailed distributions
• Simplicial Closure and higher-order link prediction
• Module identification in bipartite and directed networks
• Community structure and scale-free collections of Erdös-Rényi graphs
• Efficiently inferring community structure in bipartite networks
• Community Structure in Congressional Cosponsorship Networks
• Structural transitions in scale-free networks
• Random clique covers for graphs with local density and global sparsity

Cited by in corpus (2)

• Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components
• Augmented Sparsifiers for Generalized Hypergraph Cuts with Applications to Decomposable Submodular Function Minimization