Source-linked AI summary
Scaled Null-Adjusted Persistence: A Multiscale Bridge between Modularity and Persistence
Alessandro Avellone, Paolo Bartesaghi, Stefano Benati, Rosanna Grassi
TL;DR
Community detection must balance fine-grained cohesive groups against modularity's tendency to merge small communities through its resolution limit. The paper introduces Scaled-NAP, which interpolates between NAP and modularity with α, analyzes its scale behaviour, and optimizes it using Milano. On LFR benchmarks it achieved the highest AMI wherever the planted structure was recoverable, while real-network tests and runtime results supported its accuracy and scalability.
Problem
Community detection needs an objective that balances small cohesive communities with modularity's tendency to merge small groups in large networks.
Method
Scaled-NAP rescales null-adjusted persistence by a parameterized relative-volume factor, analyzes merging and resolution behaviour, and optimizes the objective with the multilevel Milano heuristic.
Results
Scaled-NAP attained the highest AMI in every recoverable LFR configuration and was best or tied for best on real networks while running fastest by a wide margin on a single thread.
Takeaways & Limitations
The α parameter provides a tunable bridge from fine-grained NAP communities to coarser modularity communities, supporting scale exploration on networks without known ground truth.
Takeaways & Limitations
Infomap is a strong parameter-free competitor, and Scaled-NAP's comparative advantage is most evident in some difficult cases where Infomap performance deteriorates.
Abstract
from arXiv · showhide
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.
1 Introduction
Community detection depends critically on choosing an objective function that matches the intended notion and scale of community structure. Scaled-NAP bridges modularity's coarse, static grouping with NAP's finer, dynamic interpretation while providing a tunable resolution parameter.
- Motivation: Community detection methods require an objective function that can determine which candidate partition is preferable for a given application.Optimization methods provide an objective comparison between partitions.
- Motivation: Modularity compares observed within-community edges with configuration-model expectations but can merge small communities in large networks because of its resolution limit.Alternative responses include corrected modularity and different statistics such as the Map equation or persistence.
- Motivation: NAP measures persistence beyond the configuration-model expectation, offering a dynamic alternative in which communities retain information flow more persistently.Its optimum is obtained by maximizing total NAP.
- Motivation: Modularity emphasizes strong internal bonds, whereas NAP emphasizes persistent information flow, so the appropriate measure depends on the qualitative interpretation of community.The paper motivates a bridge when neither interpretation or the desired resolution is straightforward.
- Contribution: Scaled-NAP introduces α ∈ [0, 1] to control resolution, recovering NAP at α = 0 and modularity at α = 1.The parameter acts through an inflated cluster-volume factor and interpolates between finer and coarser structures.
- Contribution: The paper combines theoretical analysis of resolution-limit behaviour with Milano, a scalable Louvain-style heuristic for near-optimal Scaled-NAP partitions.The stated computational goal includes graphs with billions of arcs.
2 Null-adjusted persistence
Null-Adjusted Persistence measures how strongly a cluster retains a random walker relative to a configuration-model null hypothesis. The resulting excess-persistence score supports community detection by maximizing the total score over admissible connected partitions.
- Definitions: A clustering is a partition of the graph's vertices into nonempty clusters whose induced subgraphs are connected.The graph is defined as weighted, connected, and undirected, and admissible clusterings form ℘(G).
- Persistence: Persistence is the fraction of cluster-node strength associated with internal edges, equivalently the probability that a random walker remains in the cluster after one step.This interpretation also applies to the weighted formulation.
- Null adjustment: The configuration-model null preserves the node-strength sequence while randomly locating arcs, providing the expected persistence against which observations are adjusted.The null model uses weighted adjacency entries based on node strengths.
- Null adjustment: NAP is the excess persistence of a cluster beyond what its node-strength distribution alone predicts under the null model.A positive value indicates stronger-than-expected separation from the rest of the graph.
- Cluster quantities: For a cluster, volume equals its total strength and, in an unweighted graph, equals 2m_i + m_e.Here m_i counts internal edges and m_e counts edges connecting the cluster outward.
- Optimization: Community detection with NAP is formulated as maximizing the total NAP score over all admissible partitions.The same configuration model also defines modularity, linking the two objective functions.
3 Scaled Null-Adjusted Persistence (Scaled-NAP)
Scaled-NAP rescales NAP by a power of relative cluster volume, creating a family that contains NAP and modularity as endpoint cases. Varying α changes the influence of cluster volume and therefore the granularity of the maximizing partition.
- Definition: Scaled-NAP is a parametric family of objective functions incorporating null-adjusted persistence and modularity as special cases.The family is designed to control the influence of relative cluster volume.
- Relationship to modularity: NAP and modularity differ by relative-volume weighting: modularity rescales NAP by cluster volume, while NAP divides modularity by that factor.NAP can therefore be viewed as a density-normalized modularity contribution.
- Endpoint cases: At α = 0, Scaled-NAP coincides with NAP, while at α = 1 it coincides with the modularity contribution.These are the two endpoint objective functions of the family.
- Optimization: The Scaled-NAP community-detection problem maximizes the total Scaled-NAP score over feasible partitions.The objective is extended from individual clusters to partitions.
- Resolution control: Increasing α promotes larger, coarser communities, whereas smaller α values remain closer to NAP and tend toward smaller communities.This flexibility is intended for applications where the appropriate analysis scale is not known in advance.
4 Analytical Properties of the Scaled-NAP family
The Scaled-NAP family yields an explicit condition for when merging two clusters improves the objective, interpolating between scale-invariant NAP at α=0 and scale-dependent modularity at α=1. For α>0, larger network weight lowers the merging threshold, and on Caveman graphs resolution-limit behaviour can arise below α=1.
- Merging condition: Proposition 1 gives a necessary and sufficient condition for merging two disjoint clusters to increase Scaled-NAP in weighted networks.The condition applies for every α∈[0,1] when the union induces a connected subgraph.
- Merging condition: In unweighted networks, Corollary 2 provides the corresponding necessary and sufficient inter-cluster edge threshold for an improving merge.The threshold is expressed using internal, external, and inter-cluster edge counts.
- Endpoint behaviour: At α=0, the merging threshold is independent of total network weight S, whereas at α=1 it depends explicitly on S through modularity.These endpoint cases recover NAP and modularity, respectively.
- Scale dependence: For α>0, the threshold decreases as total network weight S increases when the clusters’ local properties remain fixed.The dependence enters through a positive term inversely proportional to S.
- Parameter dependence: When the relevant positivity condition holds, the merging threshold Tα(C1,C2) is strictly decreasing in α over [0,1].Thus increasing α makes merging more permissive under the proposition’s assumptions.
- Numerical example: Figure 2 shows that increasing α lowers the threshold, while increasing network size lowers it further for fixed α>0, producing different merge decisions for identical local structures.This demonstrates scale dependence within Scaled-NAP.
- Caveman graphs: On connected Caveman graphs with cave size p≥3, the asymptotic resolution-limit threshold satisfies α⋆<1 and approaches 1 as p increases.Values α<α⋆ can remain close to modularity while preserving individual caves in this graph class.
5 The Milano Algorithm
The Milano algorithm extends a heuristic approach to the full Scaled-NAP family, optimizing a combinatorial connected-partition problem through repeated node moves and graph contractions. It checks connectivity after multilevel optimization and supports randomized multi-start runs.
- Motivation and scope: Milano extends heuristic community detection from NAP to the full Scaled-NAP family because the optimization problem has an NP-hard modularity special case.At α=1, maximizing Scaled-NAP is exactly modularity maximization.
- Local optimization: The algorithm initializes communities as singletons and repeatedly applies MoveNode to improve the partition.MoveNode reallocates nodes to the candidate community yielding the largest objective gain.
- Multilevel scheme: After local moves, Milano contracts each community into a super-node and aggregates inter-community edges by weight before repeating the search.The process continues over successive contractions until MoveNode finds no further improvement.
- Feasibility: The final partition is expanded back to the original vertices, and community connectivity is explicitly verified.The connectivity check addresses disconnected communities that can arise in Louvain-style local search.
- Randomization: Random node shuffling makes Milano suitable for multi-start optimization using independent seeds, returning the partition with the highest Scaled-NAP score.The randomized ordering is generated by the algorithm’s random number generator.
6 Community detection on simulated and real-world networks
Experiments evaluate Scaled-NAP across simulated weighted and unweighted networks and real-world networks, comparing recovery, resolution behavior, and computational performance. Scaled-NAP performs especially well when community sizes are heterogeneous and produces fine-grained partitions on real networks, while Milano is computationally fast.
- Experimental design: The experiments vary mixing, average degree, community-size heterogeneity, and weight informativeness to assess community recovery.Higher mixing makes recovery harder, while higher density generally makes recovery easier at fixed mixing.
- Resolution stability: Across fifteen unweighted configurations, optimal α∗ remains in the narrow interval [0.85, 0.95].At average degree 50, α∗ is 0.85 in every row; increasing mixing lowers peak AMI but barely changes its location.
- Weighted benchmarks: Weighted graphs show higher recovery when weights reinforce community structure, with optimal α∗ generally shifting to [0.95, 1.00] compared with the unweighted range 0.85–0.95.When weights are anti-informative, Infomap declines sharply, whereas Scaled-NAP, Leiden, and Walktrap can still recover consistent partitions.
- Unweighted benchmarks: When community-size heterogeneity increases, Scaled-NAP generally achieves the highest AMI wherever the planted partition is reliably recoverable.At µ = 0.65, its advantage over the best competitor grows from +0.005 in the intermediate scenario to +0.081 in the heterogeneous scenario.
- Resolution comparison: Varying modularity resolution parameters does not reach the planted K = 75 communities in the heterogeneous example, while Scaled-NAP is evaluated against this fine-grained target.Leiden and Louvain produce at most 68 and 67 communities, respectively.
7 Conclusions
The paper introduces Scaled-NAP as a tunable bridge between NAP and modularity, combining analytical characterization with scalable optimization and strong benchmark performance.
- Scaled-NAP controls cluster volume with α ∈[0, 1], yielding NAP at α = 0 and modularity at α = 1.The parameter moves from fine-grained communities toward larger, coarser communities.
- The authors derive analytical properties, including conditions for merging clusters, and apply the family to real networks.
- The Milano heuristic optimizes Scaled-NAP, with α⋆ stable in [0.85, 0.95] across all LFR benchmark configurations.
- Scaled-NAP attained the highest AMI in every LFR cell where the planted structure was recoverable.
- On real networks up to 1.1 × 10^6 nodes, Milano was best or tied for best on com-DBLP and com-YouTube, competitive on com-Amazon, and fastest by a wide margin.
- Future work includes more sophisticated optimization heuristics, extensions to directed or overlapping communities, and applications to domain-specific networks.
A An exact mixed-integer linear programming formulation
The appendix formulates fixed-α Scaled-NAP maximization as an exact MILP for small integer-weighted instances, providing a provably optimal reference for validating Milano.
- For fixed α, Scaled-NAP maximization can be expressed as a mixed-integer linear program for obtaining exact optima on small instances.The formulation is intended to validate the Milano heuristic against provably optimal partitions.
- The formulation assumes integer edge weights, allowing cluster volumes to range over the finite set {0, 1, . . . , Vmax}, with Vmax = 2S.Rational weights can be rescaled to integers.
- Binary assignment, edge-membership, and volume-selection variables represent communities, while tcv linearizes the product Wc zcv.
- The constraints enforce node partitions, internal edge weights, selected community volumes, and exact McCormick linearization of the nonlinear objective terms.
- Proposition 5 establishes that the MILP optimum equals maxΠ sNAPα(Π), with K = n always sufficient.
- The formulation uses O(nK), O(mK), and O(K Vmax) variables, making it pseudo-polynomial and practical only for small integer-weighted instances.
B Comparison between AMI, NMI and ARI
The appendix justifies AMI as the primary comparison measure because it corrects NMI’s chance bias and closely tracks ARI while avoiding redundant reporting.
- AMI corrects NMI’s positive bias in cases where no community structure is recognized.
- AMI is strongly correlated with ARI, so the authors report AMI alone to avoid redundant results.
- In an MCL example, NMI remained 0.710 for a highly inconsistent partition, whereas AMI and ARI scored it 0.081 and 0.013.
- Across the three LFR scenarios, ARI produced the same method rankings as AMI, although ARI intervals were wider.
- ARI magnifies errors involving merges or splits of large communities because it counts agreements over node pairs.