Source-linked AI summary
Analysis of the structure of complex networks at different resolution levels
Alex Arenas, Alberto Fernandez, Sergio Gomez
TL;DR
Modularity optimization can miss genuine submodules because of a resolution limit. The paper addresses this by rescaling node strengths with self-loops and optimizing modularity across resolution levels. The method recovers predefined synthetic structures, exact literature-supported splits in two real social networks, and substructure beyond those splits.
Problem
Modularity optimization has a resolution limit that can leave genuine network submodules undetected.
Method
The method adds self-loops of weight r to every node and optimizes modularity for different values of r to screen multiple topological scales.
Results
The method discovers predefined synthetic structures and recovers exact reported splits in two real social networks, including substructure beyond the splits.
Takeaways & Limitations
Stable resolution scales correspond to predefined structures in synthetic networks and previously known modular divisions in real networks.
Abstract
from arXiv · showhide
Modular structure is ubiquitous in real-world complex networks, and its detection is important because it gives insights in the structure-functionality Modular structure is ubiquitous in real-world complex networks, and its detection is important because it gives insights in the structure-functionality relationship. The standard approach is based on the optimization of a quality function, modularity, which is a relative quality measure for a partition of a network into modules. Recently some authors [1,2] have pointed out that the optimization of modularity has a fundamental drawback: the existence of a resolution limit beyond which no modular structure can be detected even though these modules might have own entity. The reason is that several topological descriptions of the network coexist at different scales, which is, in general, a fingerprint of complex systems. Here we propose a method that allows for multiple resolution screening of the modular structure. The method has been validated using synthetic networks, discovering the predefined structures at all scales. Its application to two real social networks allows to find the exact splits reported in the literature, as well as the substructure beyond the actual split.
A Arenas1,2,3‡, A Fern´andez1 and S G´omez1
The paper lists affiliations in Spain and the United States, along with its submission venue and correspondence designation.
- The authors are affiliated with Universitat Rovira i Virgili in Tarragona, Spain.
- Additional affiliations include the Institute for Biocomputation and Physics of Complex Systems at Universidad de Zaragoza, Spain.
- One author is affiliated with Lawrence Berkeley National Laboratory in Berkeley, USA.
1. Introduction
Community detection uses modularity to identify meaningful network structure, but modularity optimization has a resolution limit that can hide submodules. The paper proposes screening topology across resolution levels using the original modularity definition.
- Community structure reveals information about the roles of node groups across social, biological, technological, and other real networks.
- Modularity measures within-community connectivity relative to a randomized network preserving node strengths.
- Because exhaustive partition search grows at least exponentially with network size, modularity is optimized using heuristics.
- Modularity optimization has a resolution limit that can leave submodules undetectable, a limitation also observed for other quality functions.
- The paper interprets the resolution limit as a feature of quality functions and introduces a method for screening topology at any resolution level.
2. Complex networks topology represented at different scales
The method changes a network’s effective modularity scale without changing its original links, enabling modularity optimization across positive, zero, and negative resolution parameters. Different values expose smaller groups, the standard scale, or larger superstructures.
- 2.1. Resolution limit and topological scales: The modularity resolution limit depends on the network’s total strength, motivating modification of that quantity.
- 2.1. Resolution limit and topological scales: Increasing every node’s strength by r allows previously hidden modules to become separable because r grows faster than the relevant square-root bound.
- 2.1. Resolution limit and topological scales: The rescaled network W_r is constructed by adding self-loops of weight r to every node, shifting each node strength by the same amount.
- 2.1. Resolution limit and topological scales: Rescaling preserves original link weights and common network characteristics while changing the modularity characteristic scale.
- 2.2. Multiple resolution method: Optimizing modularity for different r values reveals larger groups at small r and smaller groups at large r, all embedded in the original topology.
- 2.2. Multiple resolution method: At r = 0 the method recovers the conventional modularity scale, positive r exposes substructures, and negative r exposes superstructures.
- 2.2. Multiple resolution method: The all-node-separated scale occurs at r_max, while the whole-network scale has a lower bound at the asymptote r_asymp = −2w/N.
- 2.2. Multiple resolution method: Modules at different resolution levels need not form a hierarchy, although each scale provides information about network topology.
3. Results
Across synthetic and real networks, screening modularity over multiple resolution levels recovered predefined hierarchical structures, overcame modularity’s resolution limit, and identified known social-network splits.
- In the RB 125 hierarchical scale-free network, persistent structures appeared at 5 and 25 communities, while the most stable partition contained 26 modules.The 26-module partition isolates the main hub relative to the 25-module partition.
- The method revealed both predefined hierarchical levels in the H 13-4 synthetic network: four groups of 64 nodes and 16 groups of 16 nodes.
- Increasing resolution separated the two small cliques in the FB network, recovering the expected partition into four isolated cliques.At r = 0, modularity cannot separate the two small cliques; the expected partition appears in region (II).
- For Zachary’s karate club, the most stable resolution produced the exact two-club split with no individual misassigned.The usual modularity optimum at r = 0 is four groups, whereas the stable multiresolution result matches the known split.
- For the dolphins network, the most stable resolution exactly matched the two observed partitions, unlike the five-community optimum obtained at r = 0.The network contains 62 dolphins, and the observed fission followed the temporary disappearance of SN100.
4. Discussion
Varying the resistance parameter reveals topological mesoscale partitions and aligns them with synchronization timescales, while comparisons show that alternative methods screen different structures or assume hierarchy.
- Multiple-resolution interpretation: Positive resistance reveals substructures below the original modularity scale, whereas negative resistance reveals superstructures.The resistance parameter acts as a scale control: larger positive values expose smaller groups, while negative values expose larger groups.
- Multiple-resolution interpretation: Intermediate topological scales appear as resistance intervals where the optimal partition remains unchanged.These persistent intervals define the network’s topological mesoscale.
- Contact with physics: Synchronization patterns agree with the communities found by the topological method across the hierarchical synthetic network’s scales.The comparison uses community counts over translated resistance and time, with the correspondence described as overwhelming.
- Contact with physics: The synchronization comparison is instructive but does not establish generality for dynamics different from phase-oscillator synchronization.Real networks may rely on substantially different dynamical processes.
- Comparison with other methods: Methods based on modified quality functions or local modularity minima have limitations: the former may miss substructure, while the latter assumes hierarchy.The authors contrast these assumptions with their broader scope over arbitrary topology.
- Comparison with other methods: The method succeeds on a toy network with unequal community sizes and densities, whereas varying the Reichardt–Bornholdt parameter fails to recover its natural partition.The natural partition consists of four stars and one clique.
- Comparison with other methods: The resistance parameter is not equivalent to the Reichardt–Bornholdt parameter except at r = 0 and γ = 1.The paper concludes that the two prescriptions screen different structures.
- Best scale of description: The paper identifies stable partitions as relevant using prior knowledge, but says relevance cannot straightforwardly be inferred from persistence alone.Other, less persistent partitions may still contain information.
5. Conclusions
The paper introduces a multiple-resolution modularity procedure that scans network structure from individual nodes to the whole network. Stable scales recover predefined synthetic structures and previously known real-network splits.
- 5. Conclusions: The method adds self-loops of weight r to every node, changing modularity’s characteristic scale without changing the original connectivity or link weights.Optimizing the rescaled network across r exposes modules at different topological scales.
- 5. Conclusions: The resulting partitions screen the full range of structural modules, from individual nodes through the whole network.The paper presents this range across synthetic and real complex networks.
- 5. Conclusions: Stable topological scales correspond to predefined synthetic structures and exactly match previously known real-network splits.These scales provide information about the networks’ main modular aspects.
Appendix A. Resistance limiting cases
The appendix proves the limiting resistance cases for weighted undirected and directed networks.
- Appendix A. Resistance limiting cases: The proofs cover the resistance limit where every node is isolated and the limit where all nodes form one group.These are the two physical limiting cases of the resistance parameter.
Appendix A.1. Resistance limiting cases for weighted undirected networks
For weighted undirected networks, resistance analysis identifies limiting modularity configurations: all nodes isolated at sufficiently large resistance and all nodes joined just above the asymptote.
- All nodes isolated: For r > rmax, all nodes are separated in the optimal community configuration.rmax is the minimum resistance satisfying the inequalities for every pair of nodes joined by an edge.
- All nodes in the same community: For multiple communities, the intercommunity edge-weight sum a is positive; for one community, a = 0.
- All nodes in the same community: The null-case expansion yields b > 0, with b ∼O(ǫ^2) only when all node strengths are equal and b ∼O(1) otherwise.
- All nodes in the same community: When the resistance is just above rasymp = −2w/N, the optimal configuration places all nodes in one module.The modularity asymptotically approaches −∞ for partitions with multiple communities and 0 for a single community.
Appendix A.2. Resistance limiting cases for weighted directed networks
For weighted directed networks, the same resistance-limit analysis gives isolated-node configurations at sufficiently large resistance, while the single-module limit depends on the sign of b.
- Setup: The directed-network derivation uses modularity generalized to directed networks and defines input and output strengths for the resistance-transformed network.
- All nodes isolated: For r > rmax, all nodes are separated in the optimal community configuration.rmax is the minimum resistance satisfying the inequalities for every pair of nodes joined by an arc.
- All nodes in the same community: Just above the asymptote, modularity approaches −sign(b)∞ for multiple communities and 0 for one community.
- All nodes in the same community: The single-module configuration is optimal near the asymptote only if b is positive for every community partition.Otherwise, modularity rises to +∞ for the maximum-modularity configuration, and the single-module structure may be absent at every resistance.
Appendix B. Optimization of the modularity using the Tabu heuristic
The modularity optimizer uses a Tabu-search heuristic that iteratively explores node moves between communities while forbidding recent moves to escape local optima.
- Algorithm: The method optimizes modularity using Tabu search, starting from an initial partition and iteratively exploring neighboring solutions.
- Neighborhood exploration: A neighborhood consists of partitions produced by moving one node to another community or creating a new community.The best neighboring solution becomes the current solution for the next iteration.
- Tabu mechanism: The tabu list stores recently accepted moves and temporarily forbids them, while allowing tabu moves that improve the best solution found.
- Stopping rule: A logarithmic function of network size determines the number of idle iterations used to stop the search.
- Algorithm properties: The algorithm combines divisive and agglomerative processes and can begin from any initial partition.This supports screening nearby resistance values whose optimal partitions are frequently similar.