AI summaryⓘ
The authors address a problem in finding groups within networks, where methods must balance spotting small tight groups without breaking the network into many tiny pieces. They propose Scaled Null-Adjusted Persistence (Scaled-NAP), a flexible approach that mixes two existing ideas, modularity and persistence, to control how detailed the groups are. They also developed the Milano algorithm to efficiently find good groups using Scaled-NAP in large networks. Tests showed their method can detect meaningful community structures well, especially when group sizes vary, and runs faster than others on big networks. This work links two important ways to find communities, making it both effective and scalable.
community detectionmodularitypersistenceresolution limitLouvain algorithmmultilevel heuristicnetwork partitioningCaveman graphsLancichinetti-Fortunato-Radicchi benchmarkcommunity-size heterogeneity
Authors
Alessandro Avellone, Paolo Bartesaghi, Stefano Benati, Rosanna Grassi
Abstract
Community detection methods must balance two competing objectives: identifying small, cohesive groups while avoiding excessive fragmentation. Modularity, the most widely adopted optimization criterion, typically merges small communities in large networks due to its resolution limit. In contrast, a persistence-based criterion promotes more granular partitions. We introduce Scaled Null-Adjusted Persistence (Scaled-NAP), a parametric family of quality functions that incorporates both these criteria. The definition exploits the exact identity between a cluster's modularity contribution and its Null-Adjusted Persistence (NAP) multiplied by its relative volume. Raising this volume factor to a parameter $α\in[0,1]$ yields NAP at $α=0$ and modularity at $α=1$, while intermediate values control the scale of the detected partition. We derive conditions under which merging two communities improves the objective function and characterize the emergence of scale dependence, including resolution-limit behaviour on Caveman graphs. We develop the Milano algorithm, a multilevel Louvain-style heuristic for optimizing Scaled-NAP on large networks. Experiments on weighted and unweighted Lancichinetti-Fortunato-Radicchi benchmarks show that Scaled-NAP achieves the highest or tied-highest recovery wherever the ground truth structure is detectable, with its advantage increasing under community-size heterogeneity. Tests on three real networks with up to 1.1 million nodes confirm its capability to identify fine-grained ground-truth communities. The Milano algorithm also turned out to be the fastest method evaluated on large networks. These results show that Scaled-NAP provides an effective and scalable bridge between modularity-based and persistence-based community detection methodologies.