PaperlayerView exact revision on arXiv

Source-linked AI summary

Asymptotic resolution bounds of generalized modularity and multi-scale community detection

Xiaoyan Lu, Brendan Cross, Boleslaw K. Szymanski

arXiv:1902.04243v2cs.SIphysics.soc-ph

TL;DR

Generalized modularity’s performance lacks asymptotic bounds for more realistic degree-corrected stochastic block networks, despite its tendency to mishandle communities with differing properties. The paper derives resolution-parameter bounds and proposes a progressive agglomerative multiscale heuristic. Within the bounds, communities are likely to be recovered; beyond them, splitting or merging may occur.

  • Problem

    Generalized modularity’s performance lacks asymptotic bounds on degree-corrected stochastic block networks, despite its tendency to mishandle communities with differing properties.

    Source: §1 · pp. 2–3

  • Method

    The paper derives asymptotic upper and lower resolution-parameter bounds and proposes a progressive agglomerative heuristic for multiscale community detection.

    Source: §1 · p. 3, §4 · p. 26

  • Results

    Within the derived range, generalized modularity is likely to detect the correct communities; above it communities may split, and below it they may merge.

    Source: §1 · pp. 3–4

  • Takeaways & Limitations

    When the bounds leave no common resolution parameter, some communities split or merge, while the proposed multiscale heuristic targets practically significant communities across levels.

    Source: §1 · p. 4, §4 · p. 26

    The network-generation assumptions are approximations, and the planted-partition approximation is supported when within-community edge densities greatly exceed background density.

    Source: §4 · p. 25

Abstract

from arXiv · show

The maximization of generalized modularity performs well on networks in which the members of all communities are statistically indistinguishable from each other. However, there is no theory bounding the maximization performance in more realistic networks where edges are heterogeneously distributed within and between communities. Using the random graph properties, we establish asymptotic theoretical bounds on the resolution parameter for which the generalized modularity maximization performs well. From this new perspective on random graph model, we find the resolution limit of modularity maximization can be explained in a surprisingly simple and straightforward way. Given a network produced by the stochastic block models, the communities for which the resolution parameter is larger than their densities are likely to be spread among multiple clusters, while communities for which the resolution parameter is smaller than their background inter-community edge density will be merged into one large component. Therefore, no suitable resolution parameter exits when the intra-community edge density in a subgraph is lower than the inter-community edge density in some other subgraph. For such networks, we propose a progressive agglomerative heuristic algorithm to detect practically significant communities at multiple scales.

1. Introduction

The introduction frames generalized modularity as a resolution-parameter approach to community detection, but notes its tendency to split or merge well-formed communities with differing properties. It motivates deriving performance bounds for degree-corrected stochastic block networks and using them to guide multiscale detection.

1. Introduction

  • The resolution-limit problem reflects modularity’s tendency to detect communities with similar properties, sometimes splitting or combining well-formed communities.The generalized modularity scales discovered community sizes with a resolution parameter.Source: §1 · p. 2
  • The paper addresses the lack of asymptotic performance bounds for generalized modularity on degree-corrected stochastic block networks, despite its equivalence to planted-partition model maximum-likelihood estimation.The degree-corrected planted partition model is a special case of the degree-corrected stochastic block model.Source: §1 · p. 3
  • Within the derived resolution-parameter range, generalized modularity is likely to detect the correct communities in degree-corrected stochastic block graphs.The bounds connect modularity-based resolution limits with random graph models.Source: §1 · pp. 3–4
  • Above the upper bound, well-formed communities are likely to split; below the lower bound, communities may merge into one large component.When the lower bound exceeds the upper bound, no universal resolution parameter is suitable for all communities.Source: §1 · p. 4
  • A progressive agglomerative heuristic recursively splits clusters, raises the resolution parameter locally, and stops when Bayes model selection finds no practically significant communities.Unlike uniform-resolution approaches, it avoids repeatedly re-estimating the parameter for the entire network.Source: §1 · p. 5
  • The introduction presents asymptotic bounds, a theoretical explanation of the resolution limit, and an efficient multiscale heuristic as contributions to community detection.The stated contribution links modularity-based resolution limits with random graph models and prior work on multiscale discovery.Source: §1 · p. 5

2. Approach

The paper derives resolution bounds for generalized modularity under degree-corrected stochastic block models, then addresses cases where no single resolution works across heterogeneous subgraphs. It proposes recursively applying modularity with increasing effective resolution and using Bayes model selection to decide when to stop.

2.1. Asymptotic bounds on resolution parameter

  • The classical resolution-limit anomaly follows when the lower bound needed to avoid merging small communities exceeds the upper bound needed to avoid splitting a larger community.The paper notes such a conflict is likely in large networks with small- and large-degree communities.Source: §2.1 · p. 7
  • ω_rs ≤ γ ≤ min_t ω_tt bounds the resolution parameter: larger values can split loose communities, while smaller values can merge communities with dense inter-community connections.The bounds are intended to let a uniform γ avoid the resolution-limit trap when a suitable interval exists.Source: §2.1 · p. 8
  • The derived bounds also contain the maximum-likelihood resolution for the degree-corrected planted partition model, for any positive ω_out < ω_in.For this special case, the bounds reduce to ω_out ≤ γ ≤ ω_in.Source: §2.1 · pp. 8–9

2.2. Plateaus problem

  • The paper proposes recursive detection at multiple scales because heterogeneous subgraphs can make a uniform resolution parameter inadequate, a situation described as more common in large networks.The heuristic gradually increases resolution locally to detect practically significant communities.Source: §2.2 · p. 10, §2.3 · p. 13
  • When one subgraph’s inter-community density exceeds another’s intra-community density, no single γ avoids both merge and split errors.A worked example gives inter-clique density 1.93 and random-graph intra-community density 1.03: γ > 1.93 preserves the cliques but splits the random graph, while γ in [1.03, 1.93] preserves the random graph but merges the cliques.Source: §2.2 · pp. 9–10, §2.3 · p. 12

2.3. Multi-scale community detection

  • The recursion’s stopping rule addresses a real ambiguity: a random graph can be partitioned at high enough resolution without warranting a claim that it contains community structure.The algorithm evaluates whether a subgraph is better explained by the configuration model or a multiple-block alternative.Source: §2.3 · pp. 13–14
  • The Bayes selection approach is used because the likelihood-ratio test requires enumerating null networks to obtain a p-value, which is computationally inefficient for large networks.The paper states that the test statistic’s null distribution does not follow a chi-squared distribution in these generative models.Source: §2.3 · p. 15
  • At each recursion level, the algorithm maximizes generalized modularity with a small γ, tests each detected community, and recurses on communities deemed significant.Bayes model selection compares a configuration-model null with a multi-block degree-corrected planted-partition alternative; the recursion stops when the null is more likely.Source: §2.3 · pp. 14–15

3. Experimental Results

The experiments validate the resolution bounds on synthetic and empirical networks, then evaluate multi-scale detection on synthetic benchmarks and real networks. Results show performance within the derived bounds, modest gains over other modularity methods on LFR benchmarks, and more small communities detected in real networks.

3. Experimental Results

  • The experimental section compares multi-scale detection with Louvain and CPM on real and synthetic networks, using NMI and ARI where ground-truth communities are available.The experiments also report F-measure for real-network comparisons.Source: §3 · pp. 15–16, §3.3 · p. 24

3.1. Validation of resolution bounds

  • On the extended degree-corrected planted partition model, generalized modularity detects communities within ω0 ≤ γ ≤ ω1; above ω1, communities risk splitting.The reported example uses ten communities of ten nodes each and background density ω0 = 0.17; the bounds approximate edge counts by their expectations, so accuracy declines near either boundary.Source: §3.1 · pp. 17–18
  • For empirical networks, stable resolution intervals fall within the derived asymptotic bounds, even though those networks are not generated by the tested extended planted partition model.The validation compares ranges yielding NMI above 90% with bounds estimated from fitted background and lowest intra-community densities.Source: §3.1 · p. 19, Table 2 · p. 19

3.2. Synthetic Networks

  • On LFR networks, multi-scale detection performs modestly better than Louvain and CPM, with its strongest advantage being avoidance of the resolution-limit anomaly.The authors note that the tested LFR networks likely did not exhibit the anomaly.Source: §3.2 · p. 21, Table 3 · p. 22
  • For the 5,000-node LFR network, the multi-scale method outperforms Louvain across tested resolution parameters, consistent with adapting resolution to different graph regions.The authors suggest that no single parameter may avoid both unnecessary splits and merges; multi-scale detection achieves better ARI and NMI scores.Source: §3.2 · pp. 21–22, Table 4 · p. 23
  • On the 5,000-node LFR network, NMI stays above 0.8 for γ0 values from 0.4 to 0.9, while ARI is relatively stable below 0.7 and execution-time variation is small.The sensitivity experiment varies the multi-scale algorithm’s initial resolution parameter γ0.Source: §3.2 · p. 22, Figure 6 · p. 23

3.3. Real Networks

  • On DBLP, the multi-scale algorithm exceeds Louvain by 86% and CPA by 8% in performance; on DBLP and Amazon, detected-community sizes match the ground-truth distribution.The DBLP comparison uses only the top 5,000 ground-truth communities to reduce bias from metadata.Source: §3.3 · pp. 24–25

4. Conclusions

The random-graph assumptions are approximations of real community structures, but the degree-corrected planted partition model can remain useful when within-community edge densities greatly exceed background density and the resolution parameter is in the theoretical range. The conclusions also identify plateaus, motivate multiscale detection, and note limits of the simpler model.

4. Conclusions

  • When within-community edge densities greatly exceed background density, the degree-corrected planted partition model can approximate real community structures without the resolution limit for a resolution parameter in the theoretical range.Real networks need not be generated by a random graph model, so the assumptions are only approximations.Source: §4 · p. 25
  • Plateaus can leave no single resolution parameter satisfying all bounds, and edge weighting may address the heterogeneity involved in their formation.The paper also proposes extending the multiscale algorithm to weighted and directed networks.Source: §4 · p. 26
  • The proposed multiscale community detection algorithm minimally modifies modularity maximization, preserving its high speed and robustness.Source: §4 · p. 26
  • The degree-corrected planted partition model is simpler than the degree-corrected stochastic block model, which limits its performance on realistic large networks.Stochastic block model inference is more complicated, although model selection can prevent overfitting community models.Source: §4 · p. 26
  • The authors identify model complexity as a reason to seek a simple quality measure that accounts for complexity.Source: §4 · p. 26

Related papers

Loading 1902.04243v2…