Community structure and scale-free collections of Erdös-Rényi graphs

Abstract

Community structure plays a significant role in the analysis of social networks and similar graphs, yet this structure is little understood and not well captured by most models. We formally define a community to be a subgraph that is internally highly connected and has no deeper substructure. We use tools of combinatorics to show that any such community must contain a dense Erdös-Rényi (ER) subgraph. Based on mathematical arguments, we hypothesize that any graph with a heavy-tailed degree distribution and community structure must contain a scale free collection of dense ER subgraphs. These theoretical observations corroborate well with empirical evidence. From this, we propose the Block Two-Level Erdös-Rényi (BTER) model, and demonstrate that it accurately captures the observable properties of many real-world social networks.

References in corpus (12)

• Modularity and community structure in networks
• Power-law distributions in empirical data
• Benchmark graphs for testing community detection algorithms
• Hierarchical structure and the prediction of missing links in networks
• Stochastic blockmodels and community structure in networks
• Hyperbolic Geometry of Complex Networks
• Kronecker Graphs: An Approach to Modeling Networks
• Validation of Dunbar's number in Twitter conversations
• Sustaining the Internet with Hyperbolic Mapping
• Characterizing the community structure of complex networks
• Motif-based communities in complex networks
• Multifractal Network Generator

Cited by in corpus (76)

• Networks beyond pairwise interactions: structure and dynamics
• A Scalable Generative Graph Model with Community Structure
• Triadic Measures on Graphs: The Power of Wedge Sampling
• Higher-order clustering in networks
• Counting Triangles in Massive Graphs with MapReduce
• Clustering via Hypergraph Modularity
• Static Graph Challenge: Subgraph Isomorphism
• Wedge Sampling for Computing Clustering Coefficients and Triangle Counts on Large Graphs
• Measuring and Modeling Bipartite Graphs with Community Structure
• Unifying Sparsest Cut, Cluster Deletion, and Modularity Clustering Objectives with Correlation Clustering
• Local Differential Privacy and Its Applications: A Comprehensive Survey
• Machine Learning in Network Centrality Measures: Tutorial and Outlook
• Random Graph Modeling: A survey of the concepts
• Expectation-Maximizing Network Reconstruction and MostApplicable Network Types Based on Binary Time Series Data
• Using Triangles to Improve Community Detection in Directed Networks
• The impossibility of low rank representations for triangle-rich complex networks
• Artificial Benchmark for Community Detection (ABCD): Fast Random Graph Model with Community Structure
• Degree Relations of Triangles in Real-world Networks and Models
• On time-varying collaboration networks
• Exponential random graph models for networks with community structure
• Approximately Counting Triangles in Sublinear Time
• GraphChallenge.org: Raising the Bar on Graph Analytic Performance
• Capturing Dynamics of Information Diffusion in SNS: A Survey of Methodology and Techniques
• Generating Simple Directed Social Network Graphs for Information Spreading
• Constant-Depth and Subcubic-Size Threshold Circuits for Matrix Multiplication
• ESCAPE: Efficiently Counting All 5-Vertex Subgraphs
• Learning multifractal structure in large networks
• Robust Multimodal Graph Matching: Sparse Coding Meets Graph Matching
• A Generalized and Adaptive Method for Community Detection
• PageRank Pipeline Benchmark: Proposal for a Holistic System Benchmark for Big-Data Platforms
• Network Density of States
• An Unsupervised Framework for Comparing Graph Embeddings
• Darwini: Generating realistic large-scale social graphs
• Measuring Directed Triadic Closure with Closure Coefficients
• A simpler sublinear algorithm for approximating the triangle count
• Growing networks of overlapping communities with internal structure
• Fast Change Point Detection on Dynamic Social Networks
• GraphChallenge.org Sparse Deep Neural Network Performance
• Design, Generation, and Validation of Extreme Scale Power-Law Graphs
• Provably and Efficiently Approximating Near-cliques using the Turán Shadow: PEANUTS
• Stylized facts in social networks: Community-based static modeling
• Metaplex networks: influence of the exo-endo structure of complex systems on diffusion
• GraphChallenge.org Triangle Counting Performance
• Finite size analysis of the detectability limit of the stochastic block model
• Hierarchical Change Point Detection on Dynamic Networks
• Fast Generation of Large Scale Social Networks with Clustering
• Tuning the Clustering Coefficient of Generalized Circulant Networks
• Catching the head, tail, and everything in between: a streaming algorithm for the degree distribution
• Modular Networks for Validating Community Detection Algorithms
• Towards Interpretable Graph Modeling with Vertex Replacement Grammars
• Designing Networks: A Mixed-Integer Linear Optimization Approach
• A simple bipartite graph projection model for clustering in networks
• A Machine Learning Approach to Predicting Continuous Tie Strengths
• Graph Mixture Density Networks
• On Approximating the Number of $k$-cliques in Sublinear Time
• Signed Network Modeling Based on Structural Balance Theory
• Computing Vertex Centrality Measures in Massive Real Networks with a Neural Learning Model
• The Infinity Mirror Test for Graph Models
• Fast generation of complex networks with underlying hyperbolic geometry
• Co-Membership-based Generic Anomalous Communities Detection
• Characterizing and Utilizing the Interplay Between Core and Truss Decompositions
• Block-Approximated Exponential Random Graphs
• How to Count Triangles, without Seeing the Whole Graph
• Counting Triangles in Real-World Graph Streams: Dealing with Repeated Edges and Time Windows
• Understanding How Network Geometry Influences Diffusion Processes in Complex Networks: A Focus on Cryptocurrency Blockchains and Critical Infrastructure Networks
• EGBTER: Capturing degree distribution, clustering coefficients, and community structure in a single random graph model
• A stopping criterion for Markov chains when generating independent random graphs
• Using Bayesian Network Representations for Effective Sampling from Generative Network Models
• Modeling Graphs Using a Mixture of Kronecker Models
• Multi-Level Anomaly Detection on Time-Varying Graph Data
• SoK: Practical Aspects of Releasing Differentially Private Graphs
• Evolution of a modified binomial random graph by agglomeration
• How the Degeneracy Helps for Triangle Counting in Graph Streams
• Growing Better Graphs With Latent-Variable Probabilistic Graph Grammars
• Plan Interdiction Games
• Influence Maximization for Social Good: Use of Social Networks in Low Resource Communities