A Scalable Generative Graph Model with Community Structure

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.

References in corpus (10)

• Power-law distributions in empirical data
• Finding community structure in networks using the eigenvectors of matrices
• Hierarchical structure and the prediction of missing links in networks
• Kronecker Graphs: An Approach to Modeling Networks
• Community structure and scale-free collections of Erdös-Rényi graphs
• Triadic Measures on Graphs: The Power of Wedge Sampling
• Counting Triangles in Massive Graphs with MapReduce
• Component sizes in networks with arbitrary degree distributions
• Revisiting Degree Distribution Models for Social Graph Analysis
• A Scalable Null Model for Directed Graphs Matching All Degree Distributions: In, Out, and Reciprocal

Cited by in corpus (34)

• Clustering via Hypergraph Modularity
• Measuring and Modeling Bipartite Graphs with Community Structure
• Structural Patterns and Generative Models of Real-world Hypergraphs
• Machine Learning in Network Centrality Measures: Tutorial and Outlook
• Stochastic Gradients for Large-Scale Tensor Decomposition
• Artificial Benchmark for Community Detection (ABCD): Fast Random Graph Model with Community Structure
• A generative graph model for electrical infrastructure networks
• Dimensionality of social networks using motifs and eigenvalues
• Capturing Dynamics of Information Diffusion in SNS: A Survey of Methodology and Techniques
• Generating Simple Directed Social Network Graphs for Information Spreading
• Publishing Community-Preserving Attributed Social Graphs with a Differential Privacy Guarantee
• An Unsupervised Framework for Comparing Graph Embeddings
• Darwini: Generating realistic large-scale social graphs
• Node Immunization with Non-backtracking Eigenvalues
• Using Motif Transitions for Temporal Graph Generation
• Graph Generators: State of the Art and Open Challenges
• Modeling Graphs with Vertex Replacement Grammars
• GraphTune: A Learning-based Graph Generative Model with Tunable Structural Features
• Modular Networks for Validating Community Detection Algorithms
• Designing Networks: A Mixed-Integer Linear Optimization Approach
• Fast generation of complex networks with underlying hyperbolic geometry
• Trust based attachment
• The Infinity Mirror Test for Graph Models
• Computing Vertex Centrality Measures in Massive Real Networks with a Neural Learning Model
• The Infinity Mirror Test for Analyzing the Robustness of Graph Generators
• EGBTER: Capturing degree distribution, clustering coefficients, and community structure in a single random graph model
• Block-Approximated Exponential Random Graphs
• Towards a property graph generator for benchmarking
• Multi-Level Anomaly Detection on Time-Varying Graph Data
• Large Graph Models: A Review
• Evaluating the Potential of a Dual Randomized Kaczmarz Solver for Laplacian Linear Systems
• Generating realistic scaled complex networks
• A Sparse Tensor Generator with Efficient Feature Extraction
• A simple method for improving the accuracy of Chung-Lu random graph generation