Source-linked AI summary
Community structure and scale-free collections of Erdös-Rényi graphs
C. Seshadhri, Tamara G. Kolda, Ali Pinar
TL;DR
Community structure is important in interaction-network analysis but is not well captured by many existing models. The paper defines communities formally, proves that they contain dense ER subgraphs, and proposes BTER; experiments show that BTER closely matches observed degree and clustering properties, with modeling assumptions and tuning choices remaining limitations.
Problem
Community structure in interaction networks is important but remains poorly understood and inadequately captured by many graph models.
Method
The paper defines communities as highly interconnected subgraphs without deeper substructure, proves they contain dense ER subgraphs, and builds the BTER model from ER blocks plus Chung–Lu interconnections.
Results
BTER matches arbitrary input degree distributions and closely matches observed clustering coefficients, whereas Chung–Lu does not combine heavy tails with high clustering.
Takeaways & Limitations
Dense ER subgraphs are necessary building blocks for models of community structure, motivating BTER as a model for testing interaction-graph algorithms and architectures.
Takeaways & Limitations
BTER assumes equal expected degrees within communities and currently tunes block connectivity with a prescribed formula fitted by trial and error.
Abstract
from arXiv · showhide
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.
INTRODUCTION
The paper formalizes communities as internally well-connected, substructure-free modules and proves that each contains a dense Erdős–Rényi subgraph. It then hypothesizes that heavy-tailed interaction networks comprise scale-free collections of such subgraphs.
- INTRODUCTION: Interaction networks often contain internally well-connected communities, reflected by low conductance, high modularity, and high clustering coefficients.Communities vary in size, and community analysis decomposes interactions into more meaningful components.
- A Theory of Communities: A module is a high-modularity subgraph whose internal structure is adequately modeled by the Chung–Lu model and contains no further substructure of interest.Communities additionally require high internal connectivity.
- A Theory of Communities: Theorem 1 states that a community with s edges contains Ω(√s) vertices of degree Ω(√s), accounting for a constant fraction of its edges in a dense ER graph.The proof uses triangle bounds from extremal combinatorics and probabilistic arguments.
- A Theory of Communities: Dense ER graphs are therefore treated as building blocks for communities, despite ER graphs being poor standalone models of interaction networks.The paper interprets the simplest community as a dense ER graph.
- A Theory of Communities: Combining heavy-tailed degree distributions with dense ER communities yields a scale-free distribution of community sizes, consistent with empirical observations.For n = 1,000,000 and γ = 2, the estimated maximum community size is approximately 100, close to Dunbar’s estimate of 148.
The BTER model
BTER models interaction networks through dense ER blocks followed by inter-block connections, while allowing the input degree distribution to be matched. Heavy-tailed inputs naturally produce scale-free ER subgraphs.
- The BTER model: BTER proposes a graph model built from ER communities that matches important properties of real-world graphs.Its communities are dense ER subgraphs.
- The BTER model: Phase 1 constructs ER blocks while respecting any specified degree distribution.When the degree distribution is heavy tailed, the resulting graph naturally contains scale-free ER subgraphs.
- The BTER model: Phase 2 connects blocks using a Chung–Lu model over nodes’ excess degrees after their internal ER-block edges are assigned.Excess degree is the target degree minus the degree supplied by the ER block.
Previous models
Existing graph models may reproduce heavy-tailed degrees or other network properties, but the paper argues that they generally do not explain the high clustering and community structure of interaction networks.
- Previous models: Preferential attachment, small-world, and copying models can produce heavy-tailed degree distributions, but several have low clustering coefficients.The paper also describes their behavior as difficult to match to real data.
- Previous models: Stochastic Kronecker Graph models can have desirable properties but generate lognormal tails and do not produce high clustering coefficients.This limits their fit to the properties emphasized in the paper.
- Previous models: Stochastic block models use a constant number of relatively large blocks, which the paper argues does not satisfactorily explain low-degree clustering coefficients.Low-degree vertices constitute a majority of the graph in this argument.
MATHEMATICAL DETAILS
The proof compares triangle and wedge counts under the community conditions and uses asymptotic bounds to show that many vertices must have degree on the order of the square root of the edge count. These vertices form a dense ER subgraph containing a constant fraction of community edges.
- MATHEMATICAL DETAILS: The proof assumes a community with internal degrees ˆd1, ˆd2, …, ˆdr and s edges, using O, Ω, and Θ notation asymptotically.The community condition requires expected triangles to be at least κ/3 times the expected number of wedges.
- MATHEMATICAL DETAILS: The argument bounds triangles using the Kruskal–Katona theorem, which gives T ≤ s^3/2 for a graph with T triangles and s edges.Expected triangles are computed from independent edge probabilities under the Chung–Lu degree distribution.
- MATHEMATICAL DETAILS: The bounds are simultaneously tight when the community has √s vertices, each with degree √s.In that case, the relevant degree-sum quantity is s^3/2.
- MATHEMATICAL DETAILS: Therefore, Θ(√s) vertices of degree Θ(√s) form a dense ER graph within the community.This subgraph contains a constant fraction of the community’s edges.
THE BTER MODEL IN DETAIL
BTER constructs an interconnected, scale-free collection of communities using dense local ER graphs and sparse global connections generated by a CL model on excess degrees.
- Two-level structure: BTER combines dense short-range connections within communities with sparse long-range connections between communities.The implementation also generates extra Phase 2 edges to account for removed repeats and self-loops.
- Preprocessing: BTER partitions nodes into scale-free communities before generating within-community and across-community links in separate phases.The preprocessing assigns nodes to communities based on desired degrees; Phase 1 models each community with an ER graph, while Phase 2 interconnects communities.
- Phase 1: Phase 1 models each community as an ER graph whose connectivity is a tunable parameter.The model adjusts connectivity so smaller communities can be more tightly connected than larger ones, matching observed clustering patterns.
- Phase 2: Phase 2 applies a CL model to each node’s excess degree to generate inter-community edges by randomly selecting endpoints proportional to excess degree.Duplicate links and self-links are discarded after edge generation.
RESULTS
BTER is compared with CL on astrophysics co-authorship and Epinions social networks. Both models match degree distributions, but BTER more closely matches clustering coefficients and adjacency-matrix eigenvalues.
- Degree distributions: Both BTER and CL match the degree distributions of the ca-AstroPh and soc-Epinions networks.The ca-AstroPh distribution has a mid-way kink, while soc-Epinions is fairly close to a power law; both are matched by the models.
- Clustering coefficients: BTER closely matches observed clustering coefficients, whereas CL does not capture the combination of high clustering and heavy-tailed degrees.Dense ER graphs provide high clustering coefficients for BTER’s nodes.
- Eigenvalues: For ca-AstroPh, BTER adjacency-matrix eigenvalues are much closer to the real network’s eigenvalues than CL’s.The stronger difference is associated with substantial community behavior, with C = 0.32.
- Eigenvalues: For soc-Epinions1, BTER remains closer than CL in both clustering coefficients and adjacency-matrix eigenvalues despite smaller overall clustering.The eigenvalue difference is less dramatic when community behavior is weaker, with C = 0.07.
DISCUSSION
The paper defines communities through internal connectivity and lack of deeper substructure, proves they contain dense ER subgraphs, and builds BTER around this structure. BTER automatically creates communities of varying sizes, generates heavy-tailed degrees, and produces properties remarkably similar to real-world datasets.
- Communities are internally well-modeled by CL, highly interconnected, and contain many triangles without further substructure.
- Any community must contain a dense Erdős–Rényi subgraph, motivating graph models with dense ER substructures.
- BTER automatically determines community sizes and composition from the degree distribution while generating a heavy-tailed degree sequence.
- BTER assumes equal expected degrees within each community, although its variance and Phase 2 produce considerable degree variation.
- BTER has properties remarkably similar to real-world datasets and is designed to scale to interaction-graph applications.
Theoretical details
The theoretical analysis combines extremal combinatorics and probability to show that a clustered Chung–Lu graph with a suitable degree sequence must contain many high-degree vertices. The proof uses triangle bounds, edge-count estimates, and degree-sequence arguments to establish a dense core of scale √s.
- Theorem 2 assumes a Chung–Lu graph with sufficient degree mass and at least a constant fraction of the maximum possible triangle count.
- Theorem 2 concludes that, for sufficiently large s, Ω(√s) vertices each have expected degree Ω(√s).
- The proof uses extremal combinatorics and probability theory, including Kruskal–Katona’s triangle bound t ≤m^3/2.
- For the Chung–Lu graph, the expected number of edges is bounded through independent edge indicators and a multiplicative Chernoff bound.
- The triangle analysis combines the Kruskal–Katona inequality with the edge-moment bound to obtain T ≤ E[E^3/2] ≤ 2s^3/2.
- Vertices in the identified index range are incident to at least Ω(m) edges, have degree Θ(√m), and number Θ(√m).
Implementation details
BTER separates degree-one handling from the main Chung–Lu generation process and adjusts expected degrees to account for manually added edges and duplicates. Its implementation exposes parameters for degree-one pairing and community connectivity.
- The final community may contain fewer than its target number of nodes, so its connectivity parameter is set to ρ_k = 0.
- BTER handles degree-one vertices in separate subphases before creating the Chung–Lu component.
- By default, 75% of degree-one vertices are handled manually, though the proportion is user-definable.
- Phase 2a can randomly pair selected degree-one vertices, but all reported experiments use q = 0.
- Phase 2b connects remaining degree-one vertices to endpoints selected proportional to e_i.
- Phase 2c updates expected degrees to account for Phase 2b edges and duplicate edges before generating the Chung–Lu model.
Additional experimental results
Additional citation and co-authorship experiments compare BTER and CL with real networks. Both models match degree distributions, while BTER more closely matches clustering coefficients and adjacency-matrix eigenvalues.
- The additional experiments use a high-energy-physics citation network and a condensed-matter co-authorship network.
- Both CL and BTER match the degree distributions of the original graphs.
- BTER closely matches clustering coefficients, whereas CL produces no significant number of triangles.
- BTER’s adjacency-matrix eigenvalues are closer to those of the original graphs than CL’s eigenvalues.