A Scalable Generative Graph Model with Community Structure
From MaRDI portal
Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Network design and communication in computer systems (68M10) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Social networks; opinion dynamics (91D30)
Abstract: Network data is ubiquitous and growing, yet we lack realistic generative network models that can be calibrated to match real-world data. The recently proposed Block Two-Level Erdss-Renyi (BTER) model can be tuned to capture two fundamental properties: degree distribution and clustering coefficients. The latter is particularly important for reproducing graphs with community structure, such as social networks. In this paper, we compare BTER to other scalable models and show that it gives a better fit to real data. We provide a scalable implementation that requires only O(d_max) storage where d_max is the maximum number of neighbors for a single node. The generator is trivially parallelizable, and we show results for a Hadoop MapReduce implementation for a modeling a real-world web graph with over 4.6 billion edges. We propose that the BTER model can be used as a graph generator for benchmarking purposes and provide idealized degree distributions and clustering coefficient profiles that can be tuned for user specifications.
Recommendations
- Scalable and exact sampling method for probabilistic generative graph models
- A multi-level generative framework for community detection in attributed networks
- Graph-Based Representations in Pattern Recognition
- Graphical models based hierarchical probabilistic community discovery in large-scale social networks
- Overlapping community detection using a generative model for networks
- A deep stochastic model for detecting community in complex networks
- Scalable generation of scale-free graphs
- Scalable and Robust Community Detection with Randomized Sketching
Cited in
(23)- Generating graphs by creating associative and random links between existing nodes
- The Kronecker-clique model for higher-order clustering coefficients
- Limitations of Chung Lu random graph generation
- Scalable and exact sampling method for probabilistic generative graph models
- Motifs, coherent configurations and second order network generation
- The domination number of on-line social networks and random geometric graphs
- A mathematical analysis of the R-MAT random graph generator
- Characterization of Graphs Using Degree Cores
- I/O-efficient generation of massive graphs following the \textit{LFR} benchmark
- Updating dynamic random hyperbolic graphs in sublinear time
- Configuring random graph models with fixed degree sequences
- Nonbacktracking eigenvalues under node removal: X-centrality and targeted immunization
- Distribution-Free Models of Social Networks
- Stochastic gradients for large-scale tensor decomposition
- A Unifying Generative Model for Graph Learning Algorithms: Label Propagation, Graph Convolutions, and Combinations
- Coin-flipping, Ball-dropping, and Grass-hopping for generating random graphs from matrices of edge probabilities
- I/O-efficient generation of massive graphs following the LFR benchmark
- Algorithms and Models for the Web-Graph
- Towards a Systematic Evaluation of Generative Network Models
- A multi-level generative framework for community detection in attributed networks
- Generating large scale‐free networks with the Chung–Lu random graph model
- Self-similarity of communities of the ABCD model
- From Delaunay triangulation to topological data analysis: generation of more realistic synthetic power grid networks
This page was built for publication: A Scalable Generative Graph Model with Community Structure
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2940027)
