PaperlayerView exact revision on arXiv

Source-linked AI summary

Tolerating the Community Detection Resolution Limit with Edge Weighting

Jonathan W. Berry, Bruce Hendrickson, Randall A. LaViolette, Cynthia A. Phillips

arXiv:0903.1072v2physics.soc-phphysics.data-an

TL;DR

Modularity maximization can miss small communities because of a network-scale resolution limit. The paper extends this limit to weighted networks, derives edge weights that reduce inter-community weight, and adapts CNM to weighted modularity. Its weighted CNM variant resolves natural communities in test data and is reported as competitive with accurate community-detection methods.

  • Problem

    Modularity maximization may fail to resolve small communities in large networks, limiting its accuracy on real networks.

  • Method

    The paper derives a weighted resolution-limit argument, computes edge weights to reduce inter-community weight, and modifies CNM to maximize weighted modularity.

  • Results

    wCNM5 resolves all 1000 natural communities in the ring-of-cliques experiment, while wCNM1 resolves 263.

  • Takeaways & Limitations

    Careful edge weighting and weighted CNM can resolve communities of varying sizes and may support greater community resolution than unweighted modularity analysis suggests.

Abstract

from arXiv · show

Communities of vertices within a giant network such as the World-Wide Web are likely to be vastly smaller than the network itself. However, Fortunato and Barthélemy have proved that modularity maximization algorithms for community detection may fail to resolve communities with fewer than $\sqrt{L/2}$ edges, where $L$ is the number of edges in the entire network. This resolution limit leads modularity maximization algorithms to have notoriously poor accuracy on many real networks. Fortunato and Barthélemy's argument can be extended to networks with weighted edges as well, and we derive this corollary argument. We conclude that weighted modularity algorithms may fail to resolve communities with fewer than $\sqrt{W ε/2}$ total edge weight, where $W$ is the total edge weight in the network and $ε$ is the maximum weight of an inter-community edge. If $ε$ is small, then small communities can be resolved. Given a weighted or unweighted network, we describe how to derive new edge weights in order to achieve a low $ε$, we modify the ``CNM'' community detection algorithm to maximize weighted modularity, and show that the resulting algorithm has greatly improved accuracy. In experiments with an emerging community standard benchmark, we find that our simple CNM variant is competitive with the most accurate community detection methods yet proposed.

I. INTRODUCTION

Modularity maximization remains useful for detecting tightly connected communities, but resolution limits motivate alternatives and weighting-based approaches.

  • Modularity maximization detects groups of nodes that are more tightly connected than expected.
  • Traditional, tightly connected communities remain an important detection target despite broader definitions of community.
  • Many previous methods address resolution limits by searching over an input parameter that favors smaller or larger communities.
  • HQcut resolves communities at multiple scales without a tuning parameter by alternating spectral methods and local improvement.
  • HQcut uses a statistical splitting test, but its stopping criterion has been characterized as ad hoc.
  • HQcut accuracy often exceeds that of spectral and simulated-annealing competitors, while its solution is not constrained by global maximum modularity.

II. RESOLUTION LIMITS

The modularity resolution limit can prevent global modularity maximization from separating small natural communities, especially in networks much larger than the communities of interest.

  • A module is a vertex set with positive modularity, containing more internal edges than expected under degree-preserving randomization.
  • Minimal natural communities contain no smaller natural communities and are the target for resolution.
  • Fortunato and Barthélemy show that modularity maximization may merge two linked modules rather than resolve them separately.
  • Human communities are generally limited to roughly 150 members, placing them far below the scale of many large networks.
  • Communities with far fewer than L/2 edges may be unresolved when L is much larger than their internal edge count.
  • The paper revisits the resolution limit and argues that carefully computed edge weights can permit positive results without contradicting it.

III. RESOLUTION WITH EDGE WEIGHTS

The paper generalizes modularity’s module definition to weighted networks by replacing edge counts and degrees with corresponding weight sums.

  • Weighted modularity replaces internal edge count with the total weight of edges connecting vertices within a set.
  • The weighted degree of a vertex is the sum of the weights of all incident edges.
  • The sum of weighted degrees over a set is used in the weighted module definition.
  • The weight of edges leaving a set is represented as wout_s and expressed as α_s w_s.
  • The weighted degree sum can therefore be rewritten as d_s = (α_s+2)w_s.
  • The resulting inequality implies that sets representing communities must not contain too much total weight.

IV. THE MAXIMUM WEIGHTED MODULARITY

The weighted resolution-limit analysis adapts the ring-of-cliques construction and shows that reducing inter-community edge weight can expand the number of resolvable modules.

  • The weighted analysis follows the unweighted strategy by studying highly modular clique-based networks and their connected ring-of-cliques relaxation.
  • In the ideal weighting, intra-clique edges receive weight 1 and connecting edges receive weight 0, making weighted modularity equivalent to that of independent cliques.
  • The relaxed construction assigns weight ε to connecting edges and 1.0 to intra-clique edges.
  • Each clique is a module when ε is sufficiently small, and the network’s weighted modularity can then be evaluated by summing clique contributions.
  • The weighted resolution scale depends on ε; if ε becomes small enough, there is no longer a limit on the number of modules expected in a maximum-weighted-modularity solution.
  • The unweighted case has a natural scale tied to L, limiting how many modules optimal unweighted modularity can find.

V. THE WEIGHTED RESOLUTION LIMIT

The weighted extension of the resolution-limit argument shows that modularity maximization may fail to resolve sufficiently small modules. The analysis identifies reducing inter-module edge weight as a route toward resolution, while leaving edge-weight construction and weighted algorithm adaptation as challenges.

  • V. THE WEIGHTED RESOLUTION LIMIT: √(L/2) edges is the unweighted threshold below which modularity maximization may fail to resolve a module.The argument compares keeping two linked true modules separate with merging them into one.
  • V. THE WEIGHTED RESOLUTION LIMIT: Modules with l ≪ L are likely to exist in large real-world networks such as the WWW, making the resolution limit practically consequential.The passage presents this as corroboration of the theoretical concern in large networks.
  • V. THE WEIGHTED RESOLUTION LIMIT: Weighted modularity extends the same analysis by comparing resolved and merged configurations of two modules with intra-module weights w1 and w2.Inter-module edges are assigned weight ϵ, and the difference between the two weighted-modularity expressions yields the weighted condition.
  • V. THE WEIGHTED RESOLUTION LIMIT: A small ϵ can permit small communities to be resolved, but the paper still must find weights that reduce ϵ and adapt modularity algorithms to use them.These are identified as the two remaining challenges after deriving the weighted argument.

VI. EDGE WEIGHTING

The paper derives edge weights from local neighborhood structure by rewarding short cycles around each edge. Iteration can lower inter-module weights, although longer-cycle extensions are computationally expensive and expected to provide diminishing benefits.

  • VI. EDGE WEIGHTING: Short cycles connecting an edge’s endpoints are rewarded because they suggest strong interconnections and local community structure.The method uses local computations rather than a globally searched tuning parameter.
  • VI. EDGE WEIGHTING: Neighborhood coherence marks incident edges on paths of at most three edges between an edge’s endpoints as “good” and uses their weight relative to endpoint-incident weight.Such edges add credence to the proposition that the target edge is intra-community.
  • VI. EDGE WEIGHTING: For the Figure 1 example, coherence is computed from the thickened-edge weights divided by the total weight incident on the target edge’s endpoints, giving C(e) = 4.85.This provides the paper’s concrete illustration of the neighborhood-coherence calculation.
  • VI. EDGE WEIGHTING: Extending the coherence definition to cycles of length 5 and greater would be computationally expensive and is expected to yield diminishing marginal benefit.The authors have considered the extension but do not adopt it here.
  • VI. EDGE WEIGHTING: Algorithm W(k) repeatedly replaces each edge weight with its coherence until changes fall within a tolerance, with k denoting the iteration count.The process begins from weight 1.0 unless input weights are supplied.
  • VI. EDGE WEIGHTING: The iteration siphons weight from inter-module edges with smaller coherence, while computing triangles and 4-cycles can require O(mn log n) time on scale-free graphs.The paper notes that more efficient data structures are used in practice and that very large graphs may require ignoring some incident edges.

VII. WEIGHTED CLAUSET-NEWMAN-MOORE

The paper modifies the Clauset-Newman-Moore algorithm to maximize weighted modularity directly. The weighted version changes initialization while retaining CNM’s update and greedy-merging framework.

  • VII. WEIGHTED CLAUSET-NEWMAN-MOORE: wCNM handles arbitrary edge weights directly instead of replacing weighted edges with multiple integral-weight edges.It is an adaptation of CNM’s agglomerative modularity-maximization algorithm.
  • VII. WEIGHTED CLAUSET-NEWMAN-MOORE: CNM begins with singleton communities, initializes merger gains, repeatedly selects the best merger, and returns the encountered partition with largest modularity.Efficient data structures update the modularity changes during agglomeration.
  • VII. WEIGHTED CLAUSET-NEWMAN-MOORE: Table I evaluates weighting on a ring of 1000 5-cliques by comparing predicted m∗ and discovered |S| community counts, alongside QM and ϵ.The table caption defines ϵ as the heaviest edge weight between two communities.
  • VII. WEIGHTED CLAUSET-NEWMAN-MOORE: The weighted modification changes only initialization: vertex degrees and initial merger quantities are computed from edge weights, while update steps remain identical.The weighted degree is defined as the sum of weights on edges incident to each vertex.
  • VII. WEIGHTED CLAUSET-NEWMAN-MOORE: With these weighted initializations, normal CNM merging greedily maximizes weighted modularity Qw.The paper states that this Qw definition is equivalent to the definition in reference.

VIII. RESULTS

The full weighted pipeline applies Algorithm W(k) and then wCNM; the unweighted baseline is recovered when k = 0. Experiments use a ring-of-cliques example and a generalized Girvan-Newman benchmark.

  • VIII. RESULTS: wCNMk consists of applying Algorithm W(k) to set edge weights and then running wCNM on the resulting network.Running wCNM0 is equivalent to running the original CNM algorithm.
  • VIII. RESULTS: The experiments cover the ring-of-cliques example and the benchmark generalized from Girvan and Newman’s 128-node benchmark.These are the two datasets specified for evaluation.

A. The ring of cliques

The ring-of-cliques example exposes modularity’s resolution limit: standard CNM merges many natural cliques, whereas weighted CNM progressively recovers them through neighborhood-coherence weighting.

  • 1000 cliques of size five form the test network, with each clique connected in a ring by single edges.
  • 108 communities is the theoretical maximum found by unweighted CNM, far fewer than the network’s 1000 natural cliques.
  • ε = 0.047 yields an estimate of 286 resolved communities, while wCNM1 resolves 263.
  • Five neighborhood-coherence iterations recover all 1000 natural communities and achieve the highest observed weighted modularity.
  • Further iterations reduce ε without changing the community assignment.

B. The LFR Benchmark

The LFR benchmark generates realistic graphs with power-law community and degree distributions, enabling evaluation of community-detection accuracy and discovered community-size distributions. On these instances, weighted CNM improves agreement with ground truth and more closely tracks target community sizes than unweighted CNM, while fracturing affects weighted methods and HQcut.

  • Benchmark construction: 30 LFR instances with 5000 vertices and average degree 8 used community sizes from k^-1.5 over [10, 105] and degrees from k^-2 over [2, 50].Graphs were generated for several mixing parameters µ using code from Fortunato’s website.
  • Evaluation: The benchmark compares algorithm solutions with ground-truth intra-community edges using the Jaccard index.A is the ground-truth set of intra-community edges, while B is the corresponding set in an algorithm solution.
  • Accuracy results: wCNM achieves greater accuracy than CNM and HQcut on the LFR experiments, while the CNM variant is competitive with sophisticated community-detection methods.CNM fails to resolve most natural communities in these data, whereas wCNM performs better even on the more realistic benchmark.
  • Weighting iterations: Iterating neighborhood-coherence weighting yields diminishing marginal returns on these data, although further iterations still add value in later results.The benchmark analysis explicitly distinguishes reduced marginal gains from the continued value of iteration.
  • Community-size distributions: wCNM variants track the target community-size distribution closely at µ = 0.3, improve drastically over CNM, and appear to outperform HQcut; at µ = 0.5, neither weighted method nor HQcut tracks it closely.The reported comparison uses quantile-quantile plots, with y = x denoting a perfect match to the LFR distribution.
  • Statistical testing: The K–S tests assess whether discovered community sizes follow the discrete power law with τ = 1.5 at 95% confidence, using 100,000 simulated samples per sample size.Critical values were computed for sample sizes between 10 and 290 communities.
  • Interpretation: Fracturing occurs because target communities can contain statistically significant sub-communities, which modularity-based algorithms may discover as smaller communities.For wCNM5, a target community of size 10 can correspond to a discovered community smaller than 5; HQcut also finds communities smaller than 10.

IX. CONCLUSIONS

The paper concludes that carefully weighted edges and wCNM can resolve communities of varying sizes, while the original CNM dendrogram may contain smaller communities that its modularity cut merges.

  • Carefully computed edge weights leave open substantially greater community resolution for modularity maximization.The authors argue that weighting can tolerate the resolution limit without contradicting Fortunato and Barthélemy’s result.
  • wCNM resolves communities of varying sizes in test data after careful edge-weight computation.The conclusion reports empirical evidence that these techniques may resolve small local communities more effectively than analysis alone suggests.
  • Unweighted CNM can retain small communities in its dendrogram even when its modularity cut defines unnaturally large groups.Mining those smaller modules would disregard the cut supplied by CNM and abandon modularity maximization.
  • wCNM produces a deeper, more uneven dendrogram cut, analogous to mining CNM’s hierarchy for natural communities.
Loading 0903.1072v2…