Source-linked AI summary
Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks
Lucas G. S. Jeub, Prakash Balachandran, Mason A. Porter, Peter J. Mucha, Michael W. Mahoney
TL;DR
The paper asks how community quality varies with community size and how communities of different sizes fit together. It compares locally biased identification procedures and finds that most large realistic networks favor small communities or show similar quality across sizes, motivating attention to local structure and overlapping communities.
Problem
The paper asks how community quality changes with community size, how smaller groups fit into larger structures, and what these patterns mean for network processes.
Source: §I · p. 2Method
The authors use network community profiles and several locally biased procedures based on diffusion, spectral optimization, and geodesic spreading from seed nodes.
Source: §I · pp. 2–3Results
Most large realistic networks correspond to the small-better or similarly-good/bad scenarios, and local procedures produce similar global profiles but distinct local behavior.
Source: §I · pp. 2–3Takeaways & Limitations
The authors conclude that real-network community structure is more intricate than block-diagonal assumptions suggest, and that a local perspective accommodates pervasive overlap.
Source: §VI · p. 23An NCP based on conductance does not measure communities' internal structure, so a good-conductance community can comprise disconnected pieces.
Source: B. Robustness and Information Content… · p. 8
Abstract
from arXiv · showhide
It is common in the study of networks to investigate meso-scale features to try to gain an understanding of network structure and function. For example, numerous algorithms have been developed to try to identify "communities," which are typically construed as sets of nodes with denser connections internally than with the remainder of a network. In this paper, we adopt a complementary perspective that "communities" are associated with bottlenecks of locally-biased dynamical processes that begin at seed sets of nodes, and we employ several different community-identification procedures (using diffusion-based and geodesic-based dynamics) to investigate community quality as a function of community size. Using several empirical and synthetic networks, we identify several distinct scenarios for ``size-resolved community structure'' that can arise in real (and realistic) networks. Depending on which scenario holds, one may or may not be able to successfully identify ``good'' communities in a given network, the manner in which different small communities fit together to form meso-scale network structures can be very different, and processes such as viral propagation and information diffusion can exhibit very different dynamics.In addition, our results suggest that, for many large realistic networks, the output of locally-biased methods that focus on communities that are centered around a given seed node might have better conceptual grounding and greater practical utility than the output of global community-detection methods. They also illustrate subtler structural properties that are important to consider in the development of better benchmark networks to test methods for community detection. [Note: Because of space limitations in the arXiv's abstract field, this is an abridged version of the paper's abstract.]
I. INTRODUCTION
The paper studies how community quality changes with community size and how small communities fit into larger structures. Across several networks and identification procedures, it finds that most large realistic networks favor small communities or show similar quality across sizes.
I. INTRODUCTION
- The study asks how community quality varies with node count, how smaller communities fit into larger ones, and how size relates to network processes.The motivating downstream processes include viral propagation and information diffusion.Source: §I · p. 2
- Most large realistic networks fit the small-better or similarly-good/bad scenarios, rather than the large-better scenario.The three scenarios correspond respectively to upward-sloping, roughly flat, and downward-sloping network community profiles.Source: §I · p. 2
- The authors compare three procedures using network community profiles, which plot the best community-quality score at each size.AclCut uses diffusion dynamics, MovCut locally biased spectral optimization, and EgoNet geodesic spreading from a seed.Source: §I · p. 3
- These procedures treat community structure as dependent on network region and application as well as connectivity, and they use different underlying dynamics.The procedures include dynamics-based operational definitions and optimization-based approaches.Source: §I · p. 3
- Global profiles are similar across procedures in some respects, while local behavior differs; the authors suggest seed-centered methods may have stronger grounding and utility.The local differences reflect the distinct dynamical processes underlying the methods.Source: §I · p. 3
- Community-size patterns matter for detection and for processes such as viral propagation and information diffusion.The authors also report that some networks lack diffusion-bottleneck communities at any size, consistent with prior observations of communities having little or no effect on dynamics.Source: §I · p. 4
II. BACKGROUND AND PRELIMINARIES
The section establishes graph conventions and notation for describing network structure. It defines weighted and unweighted undirected graphs, their matrices, and basic path and neighborhood concepts.
A. Definitions and Notation
- The networks are represented as undirected graphs, with both weighted and unweighted cases considered.Source: A. Definitions and Notation · p. 4
- For a graph G, the notation specifies its nodes, edges, edge weights, adjacency matrix, degree matrix, and node strength.The degree matrix is diagonal, with each diagonal entry equal to the node's weighted degree.Source: A. Definitions and Notation · p. 4
- Paths are sequences of edges; their lengths define shortest-path geodesic distances and the k-neighborhoods of nodes or node sets.For unweighted networks, each edge has length 1; in weighted networks, edge length can be the reciprocal of edge weight.Source: A. Definitions and Notation · p. 4
B. What Can Networks “Look Like”?
Networks can have distinct coarse structures that shape how smaller communities relate to larger-scale organization. The paper contrasts low-dimensional networks with core-periphery, expander, and bipartite structures.
B. What Can Networks “Look Like”?
- When α11 ≈ α22 ≫ α12, a low-dimensional network has dense, roughly balanced communities that clustering methods can often identify and visualize.The Zachary Karate Club illustrates this pattern.Source: B. What Can Networks “Look Like”? · p. 5
- When α11 ≫ α12 ≫ α22, a core-periphery network has a well-connected core and a sparsely interconnected periphery.Source: B. What Can Networks “Look Like”? · p. 5
- When α11 ≈ α12 ≈ α22, an expander or complete graph has little discernible large-scale structure, so partitioning it need not reveal meaningful communities.Source: B. What Can Networks “Look Like”? · p. 5
- When α12 ≫ α11 ≈ α22, a network is bipartite or nearly bipartite, as can occur when two node types predominantly connect to each other.Source: B. What Can Networks “Look Like”? · p. 5
- Realistic networks often resemble core-periphery or expander structures rather than low-dimensional networks with a few balanced, nearly decomposable communities.The Zachary Karate Club is presented as a low-dimensional example, while the paper argues that such networks are atypical.Source: B. What Can Networks “Look Like”? · pp. 5–6
III. NETWORK COMMUNITY PROFILES (NCPS) AND THEIR INTERPRETATION
The network community profile (NCP) tracks the quality of the best community at each size. Its shape distinguishes size-resolved patterns of community quality across network structures.
A. The Basic NCP: Measuring Size-Resolved Community Quality
- An NCP plots the conductance of the best community of each size, with lower conductance indicating a better-separated community.The profile is the lower envelope of conductance values across communities of each size.Source: A. The Basic NCP: Measuring… · p. 6
- Empirical social and information networks often have good small conductance-based communities but no good large ones, whereas caveman networks can favor larger communities.The LiveJournal profile illustrates the upward-sloping pattern; the caveman example has a downward-sloping profile.Source: Figure 2 · p. 7, A. The Basic NCP: Measuring… · p. 7
- The figures show NCPs only up to half the network’s size because the profile for very large communities roughly mirrors that for small communities.This follows from conductance symmetry: the complement of a good small community is a good large community.Source: A. The Basic NCP: Measuring… · p. 7
- A downward-sloping NCP indicates that larger communities are better, as in low-dimensional networks such as the Zachary Karate Club.The best partitions in the low-dimensional example are roughly balanced, and the profile’s lowest point tends to occur at large community sizes.Source: A. The Basic NCP: Measuring… · pp. 7–8, Figure 3 · p. 7
- A core-periphery network often has an upward-sloping NCP: good small peripheral communities do not combine into equally good large communities.If its periphery is sufficiently well-connected, however, the profile can instead be flat.Source: A. The Basic NCP: Measuring… · p. 8
- Complete graphs and degree-homogeneous expanders have roughly flat NCPs, while bipartite structure alone does not determine a profile’s shape.The uniformly random bipartite example has a flat profile characteristic of an expander.Source: Figure 3 · p. 7, A. The Basic NCP: Measuring… · p. 8
B. Robustness and Information Content of NCPs
NCP shape is generally robust to common network perturbations, but profiles omit important information about community prevalence and internal structure. The paper supplements them with internal conductance and conductance-ratio profiles.
B. Robustness and Information Content of NCPs
- The qualitative upward, downward, or flat shape of an NCP is robust to removing nodes or edges and to changes in data generation or preprocessing.Specific communities attaining local minima are less robust, and pathological networks can have non-robust NCPs.Source: B. Robustness and Information Content… · p. 8
- An NCP does not reveal how many communities attain a quality level, so its extremal communities need not represent most communities in the network.Those extrema nevertheless identify the most severe bottlenecks for associated network dynamics.Source: B. Robustness and Information Content… · p. 8
- Because conductance ignores a community’s internal structure, a low-conductance set can even consist of several disconnected pieces.The paper uses internal conductance and conductance-ratio profiles to assess internal connectivity alongside separation from the rest of the network.Source: B. Robustness and Information Content… · pp. 8–9
C. Our Application and Extension of NCPs
The paper samples size-resolved community quality with diffusion-, spectral-, and geodesic-based methods, then compares network profiles to distinguish structural effects from algorithm choice. It applies this framework to real networks.
C. Our Application and Extension of NCPs
- Three methods sample communities of different sizes: diffusion-based AclCut, local-spectral MovCut, and seed-centered geodesic EgoNet.For each size, the best community’s conductance is plotted as a function of size.Source: C. Our Application and Extension of NCPs · p. 9
- NCPs and CRPs provide network signatures for comparing community structure and separating properties attributable to network structure from those attributable to detection algorithms.The comparison framework can also use other community-quality diagnostics and community-generation procedures.Source: C. Our Application and Extension of NCPs · p. 9
IV. EMPIRICAL RESULTS ON REAL NETWORKS
- The empirical evaluation examines small-, medium-, and large-scale community structure in example real networks.Source: §IV · p. 9
A. Example Network Data Sets
The section compares six networks across coauthorship, university Facebook, and congressional voting classes, selected for contrasting large- and small-scale community structure.
A. Example Network Data Sets
- The six networks comprise two different-sized examples each from coauthorship, university Facebook friendship snapshots, and congressional voting similarity networks.The voting networks are represented as multilayer temporal networks, with one layer per two-year Congress and interlayer ties linking legislators across consecutive Congresses.Source: A. Example Network Data Sets · p. 9
- Coauthorship edges connect authors who shared a paper, so each paper with k authors forms a k-clique.The networks represent arXiv papers in general relativity and quantum cosmology, and in astrophysics.Source: A. Example Network Data Sets · p. 9
- The authors chose these networks as representatives of classes with different large- versus small-scale community structures and prior study or validation.The coauthorship networks represent previously studied SNAP networks, the Facebook graphs represent Facebook100, and the congressional networks provide examples used to validate conventional community-detection methods.Source: A. Example Network Data Sets · pp. 9–10
- Nearly all Facebook100 networks have larger λ2 values than the collaboration and voting graphs, indicating fewer bottlenecks to mixing.λ2 does not indicate the size or cardinality of the set attaining the minimum.Source: A. Example Network Data Sets · p. 10
- Spy plots show adjacency-matrix nonzeros, with coauthorship and Facebook nodes ordered by Louvain-like community assignments and congressional nodes ordered by time.The community order was manually chosen to suggest large-scale structures; congressional diagonal blocks correspond to Congresses, with off-diagonal entries arising from interlayer ties.Source: A. Example Network Data Sets · p. 10, Figure 5 · p. 11
- The plots suggest banded congressional structure, many small coauthorship communities, and roughly ten relatively large, good Facebook communities, but quantitative measures do not unambiguously support most visual hypotheses.The paper notes that many visually appealing communities can be judged largely artifactual by quantitative community-quality measures.Source: A. Example Network Data Sets · p. 11
B. Network Community Profiles
Community quality varies with size in distinct ways across coauthorship, Facebook, and congressional networks. The same-type networks show qualitatively similar NCP shapes, and other methods yield similar global insights despite differing local behavior.
B. Network Community Profiles
- CA-GrQc and CA-AstroPh have good small communities but no good large communities; their large groups are loosely connected collections of good small communities.Their NCPs are mostly upward-sloping except below 100 nodes, and their CRPs are high for communities of hundreds or thousands of nodes.Source: Figure 6 · p. 12, B. Network Community Profiles · p. 12, Figure 7 · p. 13
- NCP shapes are qualitatively similar within each network type but distinct across types; MovCut and EgoNet yield similar global insights while sometimes differing in local behavior.The authors interpret the paired networks’ similar behavior as suggesting that coarse NCP shape characterizes broader network classes rather than only the examples studied.Source: B. Network Community Profiles · pp. 12–13
- Facebook communities at nearly every size have conductance greater than 10^-1, indicating poor community quality and no substantial bottlenecks to random-walk mixing.The exceptions are two FB-Harvard1 groups of 5 and 10 nodes; larger-size NCP dips correlate strongly with self-reported demographic information.Source: Figure 6 · p. 12, B. Network Community Profiles · p. 13, Figure 7 · p. 13
- US-Senate and US-House have predominantly downward-sloping NCPs, associated with low-dimensional temporal structure overlaid by within-Congress structure that is nearly partitioned along party lines.The temporal scaffold is one-dimensional, and the paper notes that smaller interlayer coupling values can be used to examine these structures.Source: Figure 6 · p. 12, B. Network Community Profiles · p. 13, Figure 7 · p. 13
C. Comparison of Results from AclCut, MovCut, and EgoNet
AclCut and MovCut usually rank nodes similarly, but their agreement varies by network, seed, and parameters. The resulting local communities can differ in geodesic distance and in how quickly they spread through a network.
Comparison results
- Mean Spearman correlations for AclCut versus MovCut were 0.92 in FB-Johns55, 0.85 in CA-GrQc, and 0.86 in US-Senate; minimums were 0.43, −0.13, and −0.44, respectively.The reported means and minimums are calculated over sampled seed nodes and parameter values.Source: C. Comparison of Results from AclCut,… · p. 14
Parameter dependence
- Largest deviations occurred at ϵ = 10−6 in CA-GrQc and, to a lesser extent, FB-Johns55, but at ϵ = 10−4 in US-Senate.For CA-GrQc and FB-Johns55, truncation effects were small at the smaller ϵ values, implicating the different seed-vector representations; for ϵ ≥10−4, the methods behaved similarly when the approximate PPR support was small.Source: C. Comparison of Results from AclCut,… · p. 14
US-Senate
- In US-Senate, AclCut and MovCut behave almost identically for small ϵ, but diverge more for large ϵ and small α as probability remains among interlayer neighbors.Those neighbors represent the same Senator across different Congresses; for US-Senate, EgoNet reaches those interlayer nodes before other Senators, whereas AclCut and MovCut initially select Senators from one Congress.Source: C. Comparison of Results from AclCut,… · pp. 14, 18
Local community differences
- AclCut communities tend to include nodes closer in geodesic distance to the seed than MovCut communities in CA-GrQc and FB-Johns55, consistent with higher AclCut–EgoNet than MovCut–EgoNet rank correlations across all three networks.The correlation pattern holds across the reported choices of ϵ and α.Source: C. Comparison of Results from AclCut,… · pp. 14–15
FB-Johns55
- In FB-Johns55, both example seeds reach a large fraction of nodes within two steps, illustrating how quickly local neighborhoods can expand in that network.The paper relates this to the short mean geodesic distance reported for the full Facebook graph.Source: C. Comparison of Results from AclCut,… · pp. 15–16
Seed-dependent behavior
- In CA-GrQc, seed neighborhoods vary sharply: one sampled seed has a much larger k-neighborhood than another, while the latter’s 6-ego-net is tree-like, with few triangles and no larger cliques.The larger neighborhood is associated with a more core-like position in the nested core-periphery structure.Source: C. Comparison of Results from AclCut,… · pp. 16–18
D. Meso-Scale Structure
The paper uses an association matrix to visualize how sampled local communities overlap and combine into meso-scale structure. The resulting patterns vary across networks and do not generally resemble idealized block-diagonal community structure.
Association matrices
- The association matrix records how often node pairs co-occur in sampled local communities, normalized by how often either node appears.The samples can vary across seed nodes and locality parameters.Source: D. Meso-Scale Structure · p. 18
Across-network patterns
- The resulting visualizations are messy and difficult to interpret in CA-GrQc and FB-Johns55, whereas US-Senate displays a natural large-scale temporal structure.The visualizations are produced from best-conductance communities sampled using AclCut, MovCut, and EgoNet.Source: D. Meso-Scale Structure · p. 18
CA-GrQc
- CA-GrQc has many small communities of about 10–100 nodes, but they do not combine into large communities; the network’s features are interpreted as nested core-periphery structure.The small communities correspond to dips in its NCP.Source: D. Meso-Scale Structure · pp. 18–20
FB-Johns55
- In FB-Johns55, two large communities are low-quality by conductance, while one smaller community remains separate as other local communities spread and merge.The paper reports that the remainder shows little conductance-based community structure, though overlapping remnants may be identifiable by other methods.Source: D. Meso-Scale Structure · pp. 20–21
US-Senate
- US-Senate’s large-scale structure is temporal, with AclCut and MovCut also finding partitions at individual-Congress scale that can split into multiple communities.Local-community spreading for individual seed nodes also follows the temporal structure.Source: D. Meso-Scale Structure · p. 21, Figure 14 · p. 21
Implications
- In CA-GrQc and FB-Johns55, superposed local communities do not closely match good-conductance or block-diagonal structures; the paper expects substantial overlap in many realistic networks.The authors argue that larger communities tend to have lower internal-versus-external connectivity quality than smaller ones in collaboration and Facebook networks.Source: D. Meso-Scale Structure · p. 21
V. EMPIRICAL RESULTS ON SYNTHETIC BENCHMARKS
The paper tests whether LFR synthetic benchmarks reproduce the size-resolved community-quality patterns observed in real networks. In the tested settings, their NCPs are approximately flat above a critical size rather than showing the gradual worsening found in many realistic networks.
LFR results
- Above a critical size, the tested LFR networks have approximately flat NCPs, with larger communities of comparable quality; increasing mixing parameter µ initially shifts the NCP upward.For µ ≈1, the NCP levels off to the flat shape associated with configuration-model random graphs.Source: §V · p. 22
Comparison with real networks
- The tested LFR NCPs do not resemble those of the real-world networks studied, and sampled parameter settings did not reproduce the gradual upward-sloping NCP found in many realistic networks.The aggregate trends remained similar across sampled network sizes and parameter choices.Source: §V · pp. 22–23
Benchmark recommendation
- Synthetic benchmark families should include settings that generate robust upward-sloping, flat, and downward-sloping NCPs to reflect the range of size-resolved structure observed in real networks.These three profiles correspond to distinct small-, medium-, and large-scale community-quality scenarios.Source: §V · p. 23
VI. CONCLUSIONS AND DISCUSSION
The paper finds that realistic network community structure varies with community size and is more intricate than block-diagonal assumptions suggest. Its locally biased, size-resolved approach offers a way to study overlapping local communities and their larger-scale organization.
Main findings
- The study identifies a wider range of community-quality patterns across realistic networks and finds that popular LFR benchmarks behave differently from many real networks.The authors emphasize developing benchmark graphs whose NCPs are qualitatively similar to real networks.Source: §VI · p. 23
Methodological scope
- The locally biased, size-resolved approach can be applied with other community-quality diagnostics and community-generation procedures to investigate meso-scale network structure more generally.The authors suggest it may complement global diagnostics, especially where traditional algorithmic and visualization methods have difficulties.Source: §VI · p. 23
Structural implications
- Real-network community structure can interact with core-periphery organization, while a local perspective naturally accommodates pervasive overlap and consensus structures need not be block-diagonal.The authors caution that studying community structure without other meso-scale structures can be misleading.Source: §VI · p. 23
Dynamical perspective
- The bottleneck role of a network structure depends on the dynamical process and its initial conditions, including the seed nodes.The paper connects this perspective to the example of weak ties and social contagion.Source: §VI · p. 23
Appendix A: Expander Graphs
The paper treats communities as bottlenecks in locally biased dynamics, and uses expander properties to frame how connectivity relates to community quality. It describes diffusion-based and locally biased spectral methods for finding communities around seed nodes.
Appendix A: Expander Graphs
- Expanders are highly connected graphs: they have large boundaries for node sets, resist disconnection, and support rapidly converging random walks.For d-regular graphs, a family is expanding when its edge expansion stays bounded below by a positive constant.Source: Appendix A · p. 24
- Expansion and conductance differ in how they measure set size and boundary; conductance is more natural for degree-heterogeneous graphs.For d-regular graphs, the distinction is inconsequential, and smaller expansion corresponds more closely to better communities.Source: Appendix A · p. 24
Appendix B: Community Quality, Dynamics on Graphs, and Bottlenecks to Dynamics
- Communities are treated operationally as outputs of local dynamics, including random walks and geodesic hops that are expected to become trapped in good communities.The paper relates these procedures to optimization problems for community identification.Source: Appendix B · p. 24
1. Dynamics Type 1: Local Diffusions (the “AclCut” method).
- AclCut approximates a seed-biased personalized PageRank vector through localized mass-pushing, with larger truncation values producing more locally biased solutions.The approximation typically avoids reaching most nodes and is faster on moderately large to very large graphs than the naïve linear-system solution.Source: §1 · p. 25
2. Dynamics Type 2: Local Spectral Partitioning (the “MovCut” method).
- MovCut uses a locally constrained spectral partitioning problem whose solution is an exact personalized PageRank vector and supports sweep cuts with Cheeger-like guarantees.With a single-node seed, it relaxes the problem of finding the best-conductance set containing that node under a volume bound.Source: §2 · p. 25
3. Dynamics Type 3: Local Geodesic Spreading (the “EgoNet” method).
EgoNet ranks nodes by geodesic distance from a seed and uses seed-centered neighborhoods as local communities. The paper samples local profiles through sweep cuts across seeds and method parameters, with different sampling choices for EgoNet and the diffusion-based methods.
3. Dynamics Type 3: Local Geodesic Spreading (the “EgoNet” method).
- EgoNet forms local communities from nodes within geodesic distance k of a seed; these k-ego-nets include the seed node and induced edges.Its EgoRank interpretation assigns higher rank to nodes infected earlier in an extreme susceptible-infected process starting at the seed.Source: §3 · pp. 25–26
4. Sampling Procedures and Parameter Choices
- Sweep cuts select the minimum-conductance partition among threshold sets of each method’s ranking vector, yielding local profiles that are combined into a global NCP.The procedures are run from multiple seeds and parameter settings to estimate structure across size scales.Source: §4 · p. 26
- AclCut has teleportation and truncation parameters, whereas MovCut has only teleportation; increasing AclCut’s α improves observed NCP accuracy at the cost of computation time.The reported computations use α ≈ 0.998 for AclCut.Source: §4 · p. 26
- Seed nodes for AclCut and MovCut are sampled uniformly without replacement until all nodes are sampled or every node appears in at least 10 best local communities.EgoNet has no size-scale parameter, so all nodes are used for the network sizes studied; its NCPs are plotted only through half the network size.Source: §4 · p. 26
Appendix C: Detailed Results for the MovCut Method
MovCut produces profiles broadly similar to AclCut’s, though it can yield disconnected sweep sets and differs at some sizes. EgoNet preserves qualitative NCP patterns across the studied networks, but its profiles are shifted upward, especially at larger community sizes.
Appendix C: Detailed Results for the MovCut Method
- MovCut can produce disconnected sweep sets with lower conductance than connected sets of the same size, often in coauthorship and Facebook networks but almost never in Congressional voting networks.Including these sets does not substantially change the NCP, although some differences remain.Source: Appendix C · pp. 26–27
- MovCut’s NCPs and CRPs are similar to AclCut’s overall, but the methods show some different local behavior while yielding similar insights about large-scale structure.The plotted thin curves include disconnected sweep sets.Source: Appendix C · pp. 27–28, Figure 16 · p. 27, Figure 17 · p. 27
- For CA-GrQc, the MovCut NCP is higher and less choppy than the NCP computed using AclCut, because AclCut’s truncation performs implicit sparsity-based regularization absent from MovCut.Source: Appendix C · p. 28
Appendix D: Detailed Results for the EgoNet Method
- EgoNet yields qualitatively similar NCPs to AclCut and MovCut across the studied networks, preserving small-scale structure and each network’s upward, flat, or downward trend.Its NCPs are shifted upward, especially at larger sizes, consistent with AclCut and MovCut more aggressively optimizing conductance.Source: Figure 18 · p. 28, Figure 19 · p. 28, Appendix D · p. 29