Source-linked AI summary
Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
Jure Leskovec, Kevin J. Lang, Anirban Dasgupta, Michael W. Mahoney
TL;DR
The paper asks how meaningful communities are distributed across size scales in large social and information networks. It uses conductance-based approximation algorithms and a network community profile to study over 100 networks, finding strong small communities but progressively less community-like larger ones; a Forest Fire model reproduces this pattern.
Problem
The paper addresses how to characterize meaningful community structure across size scales when community definitions and large-network behavior remain unclear.
Method
The authors introduce the network community profile plot and use approximation algorithms for conductance-based graph partitioning to analyze large networks.
Results
The best communities often occur near 100 nodes, then become progressively more blended into the network; the Forest Fire model reproduces this structure.
Takeaways & Limitations
Large well-defined communities become questionable beyond a size threshold, while recursively added edges via forest-fire burning offer a generative explanation for the observed structure.
Takeaways & Limitations
The paper notes that communities beyond a threshold may require combining network structure with node attributes to detect them.
Abstract
from arXiv · showhide
A large body of work has been devoted to defining and identifying clusters or communities in social and information networks. We explore from a novel perspective several questions related to identifying meaningful communities in large social and information networks, and we come to several striking conclusions. We employ approximation algorithms for the graph partitioning problem to characterize as a function of size the statistical and structural properties of partitions of graphs that could plausibly be interpreted as communities. In particular, we define the network community profile plot, which characterizes the "best" possible community--according to the conductance measure--over a wide range of size scales. We study over 100 large real-world social and information networks. Our results suggest a significantly more refined picture of community structure in large networks than has been appreciated previously. In particular, we observe tight communities that are barely connected to the rest of the network at very small size scales; and communities of larger size scales gradually "blend into" the expander-like core of the network and thus become less "community-like." This behavior is not explained, even at a qualitative level, by any of the commonly-used network generation models. Moreover, it is exactly the opposite of what one would expect based on intuition from expander graphs, low-dimensional or manifold-like graphs, and from small social networks that have served as testbeds of community detection algorithms. We have found that a generative graph model, in which new edges are added via an iterative "forest fire" burning process, is able to produce graphs exhibiting a network community profile plot similar to what we observe in our network datasets.
1 Introduction
The paper shifts community detection from finding individual groups to characterizing how the best conductance-based communities change with size across large networks. Its network community profile reveals tight small communities, worsening larger communities, and structure unlike common graph models.
- Community detection traditionally seeks node sets with more or better internal connections than connections to the rest of the network.
- The authors use conductance, the ratio of cut edges to internal connectivity, as a community-quality measure that can be approximately optimized.
- The network community profile plot records the minimum conductance achievable by a k-node set across community-size scales.
- Up to roughly 100 nodes, the profile generally slopes downward, indicating that smaller communities can often combine into meaningful larger communities.
- At roughly 100 nodes, the profile often reaches its global minimum, with the best communities frequently connected to the remainder by only one edge.
- Above roughly 100 nodes, conductance worsens as communities blend into the network, while large networks still contain more structure than degree-matched random graphs.
- Common generation models fail to reproduce this profile, whereas the Forest Fire model reproduces deep small-scale cuts, weaker large-scale cuts, and gradual profile increases.
2 Background on communities and overview of our methods
The paper analyzes diverse real-world network datasets and uses graph partitioning methods to find and compare low-conductance cuts. It combines multiple approximation strategies to study network structure across these datasets.
- Network datasets: The study covers social, information/citation, collaboration, web, Internet, bipartite, biological, low-dimensional, IMDB, and Amazon networks.The dataset collection includes networks with different node and edge semantics, including people and interactions, web pages and hyperlinks, and users connected to items or queries.
- Graph partitioning: Graph partitioning models the network as a simple undirected graph and seeks groups with relatively few edges between them.The partitioning objective minimizes inter-group edges, possibly after normalization, while generally seeking groups of roughly equal size.
- Approximation algorithms: Spectral methods use a Laplacian eigenvector to find a cut with conductance no bigger than φ when a cut of conductance O(φ^2) exists.The spectral approach also provides lower bounds that can indicate when a solution is closer to optimal than its worst-case guarantee.
- Approximation algorithms: Flow-based methods achieve an O(log n) approximation to optimal conductance, complementing spectral methods on graph classes where each approach has different difficulties.Flow methods face their worst-case guarantee on expanders, whereas spectral methods can confuse long paths with deep cuts.
- Approximation algorithms: The analysis uses spectral and semidefinite-programming lower bounds alongside several approximation algorithms for low-conductance cuts.These methods provide complementary ways to probe candidate communities and assess how close computed cuts may be to optimal.
3 The Network Community Profile Plot (NCP plot)
The NCP plot reveals contrasting community structure across graph types: low-dimensional and small social networks generally show downward profiles, whereas large real-world networks typically show upward profiles, with larger communities increasingly blended into the network core.
- Low-dimensional and small social networks: Low-dimensional grids produce steadily downward NCP plots whose slope is −1/d, where d is the underlying dimensionality.Higher-dimensional grids therefore have less-steep downward slopes.
- Low-dimensional and small social networks: Power-grid, road, and manifold networks also exhibit downward-sloping NCP plots across substantially different sizes and application domains.The power grid has 4,941 nodes and 6,594 edges, while the California road network has 1,957,027 nodes and 2,760,388 edges.
- Low-dimensional and small social networks: Small benchmark social networks show downward NCP trends with local minima at cluster sizes corresponding to good communities.The karate club network has local minima at k = 5 and k = 17, with the larger cut having better conductance.
- Large social and information networks: The best large-network communities are typically around 10^2 nodes, barely connected by a single edge, while communities of 10^5 or 10^6 nodes have conductance near 10^-1.Communities around 10^2 nodes can have conductance below 10^-3, with conductance worsening gradually between these scales.
- Large social and information networks: Rewired networks have smaller, worse-conductance minima, whereas original networks retain deeper cuts and larger-scale structure.In the LiveJournal01 example, the original network has more structure than its degree-preserving rewiring, while the rewired profile rises rapidly after a dip near 10 nodes.
- Large social and information networks: The upward NCP trend indicates that separating larger clusters becomes increasingly expensive because they blend more with the rest of the network.The paper interprets this behavior under a density-based notion of community goodness using conductance.
- Large social and information networks: Large real-world networks instead have NCP plots that increase over nearly their entire size range, unlike the downward profiles of low-dimensional and small social networks.This pattern is reported consistently across networks spanning different sizes, densities, and domains.
4 More structural observations of our network datasets
Large networks commonly contain weakly attached peripheral structures that strongly influence their best conductance communities. Whisker-based analyses show that these structures explain many low-conductance cuts, while removing 1-whiskers leaves the overall NCP trends largely intact.
- Core and peripheral structure: Nearly every examined network contains many 10–100-node clusters attached to the main network by one or a few edges.A substantial fraction of nodes lies outside the largest biconnected core.
- Core and peripheral structure: The largest biconnected component averages about 60% of nodes and 80% of edges across the datasets.For Epinions, the core contains 36,111 nodes (47%) and 365,253 edges (90%).
- Whiskers: A 1-whisker is a maximal subgraph that can be detached from the rest of the network by removing a single edge.The identification procedure removes edges incident to the largest biconnected component and takes the resulting connected components.
- Whiskers: Whisker sizes are heavy-tailed, ranging from fewer than 10 nodes to well above 100 across network types.Co-authorship and citation networks tend to have whiskers around 10 nodes, while very large whiskers occur in a web graph.
- Whisker-based communities: The largest whisker is nearly always the lowest NCP point, making the best conductance community a single-edge cut that a simple heuristic can find.Below the critical size of about 100 nodes, the best community is a whisker.
- Whisker-based communities: Above about 100 nodes, unions of disconnected whiskers often achieve better conductance than internally connected communities found by the Local Spectral Algorithm.The Bag-of-Whiskers Heuristic often agrees with Metis+MQI, indicating that best cuts may be disconnected or only tenuously connected.
- Core after whisker removal: Removing 1-whiskers shifts the NCP plot slightly upward but preserves its general trends because the remaining core still contains weakly connected pieces.The resulting 2-whiskers connect by two edges and have conductance roughly twice as poor as comparable 1-whiskers.
5 Comparison to other algorithms
The authors compare multiple approximation algorithms and lower bounds to determine whether the observed NCP shape reflects network structure rather than algorithmic artifacts. Across methods, small-scale communities are compact, while larger-scale pieces become increasingly difficult to separate and less community-like.
- Algorithmic validation: Algorithm comparisons support the conclusion that the observed NCP shape reflects structural properties of the networks, not merely the behavior of the primary algorithms.The study compares Local Spectral and Metis+MQI with other algorithms and examines their differences to expose structural properties.
- Algorithmic validation: At large scales, Leighton-Rao curves rise sharply because expander-like cores are encountered, whereas low-dimensional mesh-like graphs behave differently.The authors characterize Leighton-Rao as poor on expander graphs but effective on large low-dimensional mesh-like graphs.
- Algorithmic comparison: Graclus and Dendrogram produce lower envelopes roughly similar to Local Spectral, and neither yields points below the Metis+MQI curve.Their lowest points also rise from small to large scales, so these algorithms would support the same broad structural observations.
- Lower bounds: The lower bound at Vol(G)/2 exceeds the spectral lower bound and many smaller-scale upper bounds, forcing the true conductance curve to rise toward large scales.Computed algorithmic curves provide upper bounds, while spectral and SDP results constrain the intractable true curve from below.
- Piece structure: Local Spectral finds more compact pieces with shorter internal paths, whereas Metis+MQI finds longer, stringier pieces of comparable size.The distinction reflects a trade-off in which Local Spectral favors piece compactness over cut quality.
- Piece structure: Only small pieces generally have external-to-internal conductance ratios well below 1.0, although individual larger exceptions can occur.A roughly thousand-node Email-Enron piece is cited as an example of a distinct larger piece.
- Overall comparison: Communities below approximately 100 nodes are compact and well separated, whereas larger pieces are harder to separate externally than internally.This comparison summarizes the relationship between piece size, internal structure, and external separability.
6 Models for network community structure
The paper tests existing and proposed models against the observed network community profile, showing that sparse random structure and Forest Fire dynamics explain distinct features of real networks.
- Commonly studied preferential-attachment, copying, hierarchical, mesh-like, and manifold-like models do not reproduce observed NCP plots even qualitatively.
- Θ(log n)-sized cuts with logarithmically deep conductance exist in the G(w) model for power-law exponent 2 < β < 3.
- Beyond c′ log n nodes, the G(w) model has no sets with conductance below ϵ, with probability 1 −o(1).
- The toy growing-tree construction explains an upward-sloping NCP by showing best cuts moving progressively from small subtrees toward the expanding central tree.
- The Forest Fire Model combines recursive burning, skewed out-degree generation, bridging, and locality to produce NCP plots resembling those of real networks.
- Forest Fire behavior depends strongly on burning probabilities: low forward-burning probability yields sparse, tree-like graphs with large communities that improve as they grow.
7 Discussion
The discussion compares explicitly labeled communities with network-derived profiles across several datasets and finds that larger communities generally become less well separated. It also connects this pattern to network cores, community semantics, and limits of conductance-based analysis.
- Comparison with “ground truth” and sociological communities: Ground-truth communities follow network-derived conductance trends up to roughly 10–100 nodes, after which larger groups generally become less community-like.This extends the observed pattern of small, well-separated communities blending into the network as they grow.
- Comparison with “ground truth” and sociological communities: The network-derived NCP generally reaches lower conductance values and rises more gradually than the profiles of explicitly defined communities.Ground-truth curves are generally positioned between the original-network and rewired-network profiles.
- Comparison with “ground truth” and sociological communities: In LiveJournal12 and CA-DBLP, larger ground-truth communities approach the separation expected from randomly rewired networks, whereas AmazonAllProd and AtM-IMDB retain the broader trend.The authors associate the social-network pattern with relatively weak and overlapping ground-truth definitions.
- Comparison with “ground truth” and sociological communities: Email-Inside has a decreasing community profile because communication is concentrated within departments, making both network and ground-truth communities well expressed.Its small size also agrees with results observed for small social networks.
- Connections and broader implications: Large networks decompose into many small communities and a dense, intermingled core containing about 60% of nodes and 80% of edges.The core itself retains a nontrivial core-whisker structure analogous to that of the full network.
- Connections and broader implications: The bond-to-identity transition helps explain why small cohesive groups can be well separated while larger identity-based groups are less clearly expressed by network connectivity.The discussion places this transition at approximately one hundred nodes.
- Connections and broader implications: The discussion raises whether larger network communities exist at all and suggests combining network structure with node attributes for such cases.This is presented as a possible direction rather than an established solution.
- Connections and broader implications: Conductance alone can favor bags of whiskers and internally disconnected sets, motivating questions about compactness, regularization, and smoothness.These concerns qualify conductance as a complete characterization of community quality.
8 Conclusion
The paper studies community structure in large real-world social and information networks using statistical profiles of community quality across size scales. It finds that well-defined communities are generally small, that larger sets blend into the network, and that forest-fire generation reproduces this pattern better than several common models.
- 8 Conclusion: Large real-world social and information networks exhibit community structure unlike expectations from small networks and commonly used network-generation models.The conclusion presents this as a statistical finding across the studied networks.
- 8 Conclusion: ≈100 nodes marks the observed scale up to which good network communities exist; above it, the best-set conductance rises as community size increases.The NCP plot operationalizes this relationship between community size and conductance.
- 8 Conclusion: Common preferential-attachment, copying, and hierarchical models do not qualitatively reproduce this community-structure property, whereas iterative forest-fire edge addition produces remarkably good results.The comparison concerns qualitative reproduction of the observed NCP behavior.