Robustness of community structure in networks

Brian Karrer; Elizaveta Levina; M. E. J. Newman

Source-linked AI summary

Robustness of community structure in networks

Brian Karrer, Elizaveta Levina, M. E. J. Newman

arXiv:0709.2108v1Sep 13, 2007physics.data-ancond-mat.stat-mechphysics.soc-ph

TL;DR

The paper addresses how to determine whether detected network communities are statistically meaningful rather than chance configurations. It proposes perturbing networks and measuring changes in community assignments, finding that robustness distinguishes community structure more reliably than modularity z-scores across real and generated networks.

Problem
Determining whether detected communities are significant or could have arisen by chance remains largely unaddressed, despite its importance for interpreting community analyses.
Method
The paper perturbs networks while preserving their size and compares original and perturbed community assignments using variation of information.
Results
Robustness measures distinguish community structure in real and computer-generated networks, while modularity z-scores show little correlation with robustness.
Takeaways & Limitations
Community significance is better assessed by robustness to network perturbations than by high modularity alone.

Abstract

from arXiv · show

The discovery of community structure is a common challenge in the analysis of network data. Many methods have been proposed for finding community structure, but few have been proposed for determining whether the structure found is statistically significant or whether, conversely, it could have arisen purely as a result of chance. In this paper we show that the significance of community structure can be effectively quantified by measuring its robustness to small perturbations in network structure. We propose a suitable method for perturbing networks and a measure of the resulting change in community structure and use them to assess the significance of community structure in a variety of networks, both real and computer generated.

I. INTRODUCTION

Community detection is widely used to reveal functional or behavioral organization, but determining whether detected communities are statistically meaningful remains a crucial unresolved problem. The paper argues that robustness to small network perturbations is more relevant than modularity alone for judging whether a community assignment is trustworthy.

Community structure can correspond to functional modules in biochemical networks or social groups in social networks.
Many community-detection methods exist, including betweenness, clique, information-theoretic, belief-propagation, and maximum-likelihood approaches.
High modularity is not sufficient evidence because random graphs can contain high-modularity divisions, while some accepted community structures lack significantly elevated modularity.
The paper proposes assessing significance through robustness to small edge perturbations rather than relying on modularity differences or z-scores.

II. ROBUSTNESS OF COMMUNITY STRUCTURE

The paper motivates robustness testing by showing that competing modularity optima can shift under small network changes. Its perturbation-based approach can evaluate community assignments independently of the optimization method, while retaining the limits of a significance test.

In real networks, low-temperature sampling often yields similar community divisions, whereas random graphs yield varied divisions.
Multiple roughly equal modularity maxima indicate that the corresponding community assignments are not trustworthy.
The test can reject some assignments but cannot guarantee that a surviving assignment is significant, because chance can produce an isolated highest maximum.
Small edge changes can alter the relative heights of closely competing maxima, shifting the global optimum between different partitions.
The proposed method perturbs the network and observes changes in the optimal partition, converting significance into a more tractable robustness question.

III. QUANTIFICATION OF NETWORK ROBUSTNESS

The robustness calculation has two components: perturbing the network and quantifying how much its community structure changes.

The approach combines network perturbation with a measure of the resulting change in community structure.

A. Network perturbation

The perturbation scheme preserves network size while stochastically rewiring edges toward a configuration-model ensemble. The parameter α controls the interpolation from the original network to a fully randomized network.

Perturbed networks retain the original numbers of vertices and edges while changing only edge positions.
The random graph assigns an edge between vertices i and j with probability e_ij/m, giving an expected edge count e_ij.
The configuration model is chosen because it preserves the original degree sequence while randomizing edge positions.
Each original edge is rewired with probability α to a pair sampled from the ensemble; otherwise it remains unchanged.
α = 0 preserves the original network, α = 1 produces a random-ensemble graph, and intermediate values move only some edges.
The perturbation scheme preserves the number of edges and preserves original degrees in expectation.

B. Quantifying differences in community structure

The paper compares community assignments using pair-counting, cluster-matching, and information-theoretic measures, ultimately motivating variation of information as a more suitable distance measure.

Variation of information is selected to compare the optimal divisions of an original and perturbed network.It belongs to the information-theoretic class of partition-comparison measures reviewed by the paper.
Community assignments can be compared using pair-counting, cluster-matching, or information-theoretic measures.Pair-counting methods examine vertex pairs; cluster-matching methods seek the best match between clusters.
Pair-counting measures compare how many vertex pairs are grouped similarly or differently in both assignments.The Rand index is one example, using counts of pairs placed together or apart across assignments.
Adjusted pair-counting indices can be non-local: differences in one network region depend on how the rest is partitioned.Their null-model adjustment can make a local change appear dependent on unrelated parts of the assignment.
Cluster-matching measures can ignore subdivisions of communities that are never selected as matches.Under the van Dongen scheme, an example gives equal distance to assignments that other measures judge differently.
Mutual information alone can assign the same value to assignments with materially different community structures, so normalization is needed.The paper notes that label permutations should not count as differences, while subdivisions can still be obscured.

C. Variation of information

Variation of information measures the information needed to describe each community assignment given the other. It is a metric with local behavior and an interpretable range that can be normalized by log n.

Variation of information equals the sum of the information needed to describe C given C′ and C′ given C.It can also be expressed as H(X) + H(Y) − 2I(X; Y).
Variation of information is a true metric on community assignments and is local with respect to partition differences.It also gives the intuitively expected ordering for the paper’s example assignments.
The measure returns the expected ordering V(C, C′′) > V(C, C′) for the example assignments.
Its maximum value is log n, achieved when one assignment groups all nodes together and the other isolates every node.The paper normalizes by log n in its calculations when this dependence on network size is undesirable.

IV. METHODS

The method optimizes modularity on an original network, perturbs the network, re-optimizes its community structure, and measures the resulting variation of information, with configuration-model random graphs as a comparison.

The procedure first finds the modularity-maximizing community assignment C, or the best available approximation.The optimization quality depends on the algorithms available for the network.
Each perturbed network is re-optimized to obtain C′, and the variation of information between C′ and C is measured.Repeating this process quantifies how community structure changes under perturbation.
The same calculations are performed on configuration-model random graphs with the original network’s degree sequence.Multiple random-graph samples are used and their variation-of-information values are averaged.
The calculations use spectral optimization, 10 or 100 random graphs, and 40 α values from 0 to 1, depending on network size.Runtime depends on the modularity optimizer, number of random-graph samples, and number of α values.

V. RESULTS

The perturbation analysis compares how community assignments change as edges are rewired, using random-graph curves as a robustness baseline. Across real networks, it distinguishes robust, insignificant, and weak community structure more effectively than modularity z-scores alone.

Synthetic networks: The test networks’ variation of information starts at zero for α = 0, rises with perturbation, and is compared against a random-graph null model.The perturbation parameter α measures the amount of network perturbation, with α approaching 1 representing its maximum value.
Synthetic networks: For b = 10, the variation-of-information curve matches the null model, whereas smaller b values produce slower increases and greater robustness.Departure from the null-model curve indicates that the detected community structure is more robust against perturbation than random structure.
Robustness measure: The robustness measure uses horizontal variation-of-information levels corresponding to randomly reassigning 10% and 20% of vertices, while retaining the full curves for richer interpretation.Crossing these reference lines at larger α indicates greater robustness, but the authors avoid reducing the curves to a single crossing-point scalar.
Real-world networks: In the karate club network, the real community structure is more robust than its random-graph counterpart, crossing the 20%-reassignment level near α = 0.2.The figure compares real-network variation of information with the equivalent random graph.
Real-world networks: The Groningen friendship network has modularity 0.368 but no meaningful robustness difference from its random graph, so its four detected communities are not significant.The detected communities contain 5, 7, 9, and 11 vertices.
Real-world networks: The protein network is substantially robust, whereas the metabolic, electronic-circuit, and power-grid networks show weaker or partly fragile community structure.The protein network reaches the 20%-vertex-randomization level near α = 0.3; the metabolic network reaches it near α = 0.05, while the technological networks retain some but weak structure.
Comparison with modularity: Modularity z-scores correlate poorly with robustness: the protein network has the lowest of four large scores, while the weakly structured power grid has z = 100.8.The authors conclude that z-scores may indicate community strength but are unreliable without complementary robustness calculations.

VI. CONCLUSIONS

The paper argues that community significance is better assessed by robustness to network perturbations than by modularity alone. Its method distinguishes networks with strong community structure from those without across real and computer-generated examples.

Robustness to network perturbation provides a more discriminating significance measure than high modularity scores.The comparison addresses whether detected communities could plausibly arise from chance fluctuations in network structure.
The proposed method perturbs networks and measures changes in community assignments using variation of information.
The method successfully and clearly distinguishes examples with strong community structure from examples without it.The evaluation covers both real and computer-generated networks.