PaperlayerView exact revision on arXiv

Source-linked AI summary

Narrow scope for resolution-limit-free community detection

V. A. Traag, P. Van Dooren, Y. Nesterov

arXiv:1104.3083v2physics.soc-phcs.SI

TL;DR

The paper addresses the unclear definition and classification of resolution-limit-free community detection methods. It develops a rigorous framework and theorem, showing that methods using local weights are resolution-limit-free, while CPM provides a simple formulation that performs excellently in tests.

  • Problem

    Modularity and several related community-detection methods suffer from a resolution limit, while the meaning and scope of resolution-limit-free detection remain unclear.

  • Method

    The paper defines resolution-limit-free detection rigorously, analyzes Potts-model methods, and proves which methods qualify using the concept of local weights.

  • Results

    Methods using local weights are resolution-limit-free; RB, modularity, and AFG are not, while CPM performs well on hierarchical test networks.

  • Takeaways & Limitations

    CPM appears to be among the simplest possible non-trivial resolution-limit-free formulations, while meaningful resolution selection remains important.

Abstract

from arXiv · show

Detecting communities in large networks has drawn much attention over the years. While modularity remains one of the more popular methods of community detection, the so-called resolution limit remains a significant drawback. To overcome this issue, it was recently suggested that instead of comparing the network to a random null model, as is done in modularity, it should be compared to a constant factor. However, it is unclear what is meant exactly by "resolution-limit-free", that is, not suffering from the resolution limit. Furthermore, the question remains what other methods could be classified as resolution-limit-free. In this paper we suggest a rigorous definition and derive some basic properties of resolution-limit-free methods. More importantly, we are able to prove exactly which class of community detection methods are resolution-limit-free. Furthermore, we analyze which methods are not resolution-limit-free, suggesting there is only a limited scope for resolution-limit-free community detection methods. Finally, we provide such a natural formulation, and show it performs superbly.

I. INTRODUCTION

Community detection studies modular structure in networks, but modularity has a resolution limit that can hide smaller communities. The paper rigorously defines resolution-limit-free detection, identifies the qualifying methods, and introduces the CPM formulation.

  • I. INTRODUCTION: Modularity is widely used for community detection but suffers from an inherent resolution limit that affects detection effectiveness.The limit prevents detection of smaller communities in sufficiently large networks.
  • I. INTRODUCTION: Meaningful or relevant levels of description are not investigated in this paper.The paper separates this issue from its resolution-limit analysis.
  • I. INTRODUCTION: A rigorous definition is needed because demonstrating failure requires only a few cases, whereas establishing freedom from the resolution limit requires broader guarantees.The paper motivates a formal definition for analyzing which methods do and do not suffer from the problem.
  • I. INTRODUCTION: The paper analyzes resolution-limit behavior within the first principle Potts model framework and examines methods derived from it.The framework includes modularity and supports comparison among alternative formulations.
  • I. INTRODUCTION: The authors prove which methods are resolution-limit-free, analyze methods that are not, and report that CPM performs superbly.These results establish both a classification and a proposed formulation.

II. POTTS MODEL FOR COMMUNITY DETECTION

The Potts-model formulation rewards links within communities and penalizes missing internal links. Its weights determine which community structures are favored.

  • II. POTTS MODEL FOR COMMUNITY DETECTION: The notation represents a connected graph with nodes, edges, adjacency entries, link weights, and community assignments σ_i.For unweighted graphs, link weights can be taken as w_ij = 1.
  • II. POTTS MODEL FOR COMMUNITY DETECTION: The framework rewards links within communities and penalizes missing links within communities.This encodes the assumption that internal links are frequent and between-community links are rare.
  • II. POTTS MODEL FOR COMMUNITY DETECTION: A partition with minimal H is desirable, although the minimum need not be unique.The objective can therefore admit multiple equally optimal partitions.
  • II. POTTS MODEL FOR COMMUNITY DETECTION: The choices of weights a_ij and b_ij are important because they affect which types of communities are detected.Different weight choices produce different community-detection methods.

A. Previous methods

Earlier Potts-model formulations recover or relate to modularity, label propagation, and self-loop approaches through different weight and null-model choices. Null-model-based methods remain subject to the resolution limit.

  • A. Previous methods: The RB formulation uses a random null model through b_ij = γ_RB p_ij, where p_ij is the probability of a link between nodes.This choice provides the basis for several related formulations.
  • A. Previous methods: Using the configuration model p_ij = k_i k_j/2m with γ_RB = 1 recovers the original modularity definition.The configuration model uses node degrees and total edge count.
  • A. Previous methods: Independent of the null model choice, the RB method suffers from a resolution limit, and this therefore also holds for modularity.The paper explicitly extends this conclusion to modularity.
  • A. Previous methods: The AFG approach adds self-loops but still depends on a null model, so its merging behavior retains dependence on global parameters.Its resolution parameter changes scale but does not fundamentally remove the resolution limit.
  • A. Previous methods: Label propagation corresponds to the Potts formulation with a_ij = w_ij and b_ij = 0, but its global optimum places all nodes in one community.The paper characterizes that optimum as trivial, while local minima may remain interesting.
  • A. Previous methods: The RB model is equivalent to the RN model up to a multiplicative constant under an Erdős–Rényi null model with transformed resolution parameters.For γ_RN = 0, the RN model reduces to label propagation; AFG with r = 0 retrieves modularity.

B. Constant Potts model

The constant Potts model compares adjacency to a constant γ, combining internal-edge maximization with a preference for relatively small communities. γ acts as an interpretable density threshold.

  • B. Constant Potts model: The CPM sets b_ij = γ, producing a simple formulation similar to both the RB and RN models.The constant γ replaces the pair-specific null-model term.
  • B. Constant Potts model: The CPM compares A_ij to the constant term γ, and on unweighted graphs it is equivalent to the RN model after parameter transformation.It also recovers label propagation when γ = 0 and matches RB with an Erdős–Rényi null model under a corresponding setting.
  • B. Constant Potts model: The model maximizes internal edges while keeping communities relatively small.The balance between these objectives is controlled by γ.
  • B. Constant Potts model: γ acts as the threshold separating preferred within-community and between-community link densities.Within-community density should exceed γ, while between-community density should remain below γ.
  • B. Constant Potts model: For a community with e_c edges and n_c nodes, the CPM favors splitting it when the inter-community density condition described by γ is met.This gives γ a direct interpretation in terms of the density between the resulting communities.
  • B. Constant Potts model: The practical range is min_ij A_ij w_ij ≤ γ ≤ max_ij A_ij w_ij.At the lower endpoint the optimal solution is one community; at the upper endpoint each node forms its own community.

III. RESOLUTION LIMIT

The paper defines resolution-limit-free detection through invariance on induced subgraphs, then characterizes such objectives via local weights. It shows modularity and other non-local formulations fail this criterion, leaving a narrow scope centered on CPM and related methods.

  • Resolution-limit examples: Modularity can merge neighboring cliques when a global network variable crosses a threshold, hiding smaller communities according to network size.For the RB model with a configuration null model, merging occurs when γRB < q/(nc(nc −1) + 2), where q is the number of cliques.
  • Definition: A resolution-limit-free method must preserve the optimal partition when applied to every induced subgraph.The definition compares an H-optimal partition of the full graph with the corresponding subpartition on an induced subgraph.
  • Properties: For additive resolution-limit-free objectives, optimal subpartitions can be replaced by alternative optimal subpartitions without losing global optimality.Theorem 1 formalizes this recombination property for an induced subgraph generated by a subpartition.
  • Properties: Resolution-limit-free objectives are forced to have trivial optima on complete graphs: either one community or one community per node.This is the paper’s second general theorem for complete graphs Kn across all n.
  • Scope: Modularity, RB, AFG, triangle-based, shortest-path, and betweenness methods are not resolution-limit-free, while CPM is presented as the simplest sensible general formulation.The paper attributes this restriction to the dependence of non-local weights on global graph properties, while allowing exceptions for special graph classes.
  • Characterization: Local weights are sufficient for resolution-limit freedom, and CPM, RN, and label propagation satisfy this condition.Local weights do not change when restricting attention to subgraphs; Theorem 3 establishes sufficiency.

IV. PERFORMANCE

The evaluation tests CPM against RB variants, modularity, and Infomap on standard and hierarchical benchmarks. CPM performs strongly, while results depend substantially on choosing an appropriate resolution parameter.

  • Standard benchmarks: CPM performs extremely well on the benchmark networks, with tests using 10^3 and 10^4 nodes and 100 graphs per mixing-parameter value.The networks use degree-distribution exponent 2, average degree 15, maximum degree 50, and community-size distribution exponent 1.
  • Standard benchmarks: The difference between CPM and the RB model with an ER null model is especially striking because setting γ = p is generally not a good strategy.The authors attribute this difference to resolution-parameter choice rather than CPM being resolution-limit-free.
  • Resolution choice: With γ∗ RB, RB and CPM have comparable results; RB declines less quickly and eventually outperforms CPM, unlike modularity at γRB = 1.The configuration-model RB method becomes more difficult to use on large networks at the ordinary resolution γRB = 1.
  • Resolution choice: CPM and appropriately tuned RB also outperform Infomap in the reported tests, showing that determining a correct or meaningful resolution remains important and challenging.The paper notes several proposed approaches based on algorithmic or network stability and significance.
  • Hierarchical benchmarks: On hierarchical networks, CPM and hierarchical Infomap extract two community levels effectively; Infomap is slightly better, while CPM remains highly competitive.For relatively low µ2, lower µ1 clarifies the larger level, whereas higher µ1 clarifies the smaller level.

V. CONCLUSION

The paper defines resolution-limit-free community detection rigorously and identifies the methods satisfying that definition. It concludes that local-weight methods, especially CPM, occupy most of the practical scope, while meaningful resolution selection remains unresolved.

  • Conclusion: The paper defines resolution-limit-free methods through invariance of optimal partitions on induced subgraphs and proves that exactly methods using local weights satisfy the criterion.This establishes a formal relationship between local methods and the resolution limit.
  • Conclusion: The paper does not address how to determine an actual meaningful resolution, which remains a challenging problem.This is explicitly identified as an unresolved issue.
  • Conclusion: There appears to be little room for resolution-limit-free methods without local weights.The conclusion characterizes the available scope for such methods as limited.
  • Conclusion: CPM is presented as the simplest possible formulation among the few available resolution-limit-free methods and is reported to perform excellently.The paper frames CPM as a natural formulation enabled by the preceding analysis.

Appendix A: Louvain like Algorithm

The appendix describes a Louvain-like multilevel algorithm for optimizing the CPM objective. It greedily moves nodes, aggregates communities into supernodes, and repeats until no further decrease is possible.

  • Aggregation: After a node-movement pass, the algorithm constructs a smaller graph whose nodes represent communities and whose node sizes aggregate constituent sizes.The reduced graph becomes the input for the next iteration.
  • Stopping rule: The multilevel process repeats until the objective function can no longer be decreased.The implementation is derived from the Louvain method.
  • Initialization: The algorithm initializes the adjacency matrix with link weights and assigns every node size n_i = 1.For unweighted networks, w_ij = 1.
  • Greedy optimization: It repeatedly removes each node from its community and evaluates the objective-function increase from placing it in every candidate community.Nodes are moved to the community yielding minimal ΔH, and iterations continue while the objective decreases.
  • Recursive improvement: A recursive improvement cuts the network into subgraphs until each subgraph density exceeds γ, then recombines them and greedily searches for improvements.This uses the expected subgraph invariance of resolution-limit-free methods.

Appendix B: Benchmark tests

The benchmark construction uses planted communities with power-law community sizes and node degrees, then controls mixing between and within communities. The resolution parameter is calculated analytically from inner and outer densities.

  • Benchmark construction: Benchmark networks use planted community structures with power-law community sizes and node degrees.Community sizes follow exponent τ2, while node degrees follow exponent τ1.
  • Benchmark construction: A mixing parameter µ assigns probability 1 − µ to connections within communities and probability µ to connections between communities.Lower and upper bounds are imposed on community sizes.
  • Resolution selection: The resolution parameter γ is calculated analytically beforehand rather than detected algorithmically.It functions as a threshold related to inner and outer community density.
  • Hierarchical benchmarks: For hierarchical networks, the same averaging approach is applied separately at the two community levels.Communities are ordinarily assumed to exist when p_in > p_out.
Loading 1104.3083v2…