PaperlayerView exact revision on arXiv

Source-linked AI summary

Significant Scales in Community Structure

V. A. Traag, G. Krings, P. Van Dooren

arXiv:1306.3398v2physics.soc-phcs.DMcs.SI

TL;DR

Choosing a significant resolution in community detection remains difficult, especially for multi-resolution methods. The paper introduces an efficient CPM resolution scan and a method-independent significance measure based on subgraph probabilities; it reports accurate benchmark portrayals and meaningful information from European Parliament voting data.

  • Problem

    For multi-resolution community detection, it remains difficult to determine at what scale a partition is significant or which resolution parameter to choose.

    Source: §II · p. 2, §I · p. 2

  • Method

    The paper uses bisectioning to scan CPM resolutions and defines partition significance through subgraph probabilities, interpretable as encoding gain.

    Source: A. Scanning resolutions · p. 2, §III · p. 9

  • Results

    The significance measure accurately portrays partitions in benchmarks and conveys meaningful information in European Parliament voting data.

    Source: §III · p. 9

  • Takeaways & Limitations

    Significance provides a method-independent way to assess partitions and help choose resolution parameters.

    Source: §II · p. 2, §III · p. 9

    The relationship between fixed-partition probabilities and the paper’s search-based significance measure remains unclear in an intermediate grey area.

    Source: B. Significance · p. 3

Abstract

from arXiv · show

Many complex networks show signs of modular structure, uncovered by community detection. Although many methods succeed in revealing various partitions, it remains difficult to detect at what scale some partition is significant. This problem shows foremost in multi-resolution methods. We here introduce an efficient method for scanning for resolutions in one such method. Additionally, we introduce the notion of "significance" of a partition, based on subgraph probabilities. Significance is independent of the exact method used, so could also be applied in other methods, and can be interpreted as the gain in encoding a graph by making use of a partition. Using significance, we can determine "good" resolution parameters, which we demonstrate on benchmark networks. Moreover, optimizing significance itself also shows excellent performance. We demonstrate our method on voting data from the European Parliament. Our analysis suggests the European Parliament has become increasingly ideologically divided and that nationality plays no role.

I. INTRODUCTION

Community detection gives a bird’s-eye view of network structure, but choosing an appropriate resolution remains difficult. The paper frames this problem through the Constant Potts Model (CPM), whose resolution parameter can be interpreted as a desired community density.

I. INTRODUCTION

  • A partition cost rewards links within communities and penalizes missing links, with adjacency and community membership defining the terms.This formulation is a simplified version of the approach by Reichardt and Bornholdt.Source: §I · p. 1
  • The CPM is resolution-limit-free, but its resolution parameter γ has no a-priori choice and is interpreted as the desired community density.Communities have internal density at least γ and external density at most γ.Source: §I · pp. 1–2
  • The CPM uses local weights a_ij = 1 − γ and b_ij = γ, with its community form expressed using internal edges and community sizes.The paper treats random graphs as Erdős–Rényi graphs unless otherwise stated.Source: §I · p. 1
  • Modularity is prominent across fields, but it cannot detect relatively small communities in large networks because of its resolution limit.The passage describes applications in ecology, biology, political science, and sociology.Source: §I · p. 1

II. RESULTS

The paper scans CPM resolutions efficiently by exploiting how the optimal partition changes with γ. Stable ranges of γ also provide a way to interpret community density and the clarity of a partition.

A. Scanning resolutions

  • A stable range [γ1, γ2] implies community density at least γ2 and separation density at most γ1.The paper treats a wider stable plateau as indicating clearer community structure.Source: A. Scanning resolutions · p. 2
  • Higher γ generally produces smaller communities, with the endpoint optima being one community at γ = 0 and singleton communities at γ = 1.The endpoint partitions follow from the CPM objective described in the passage.Source: A. Scanning resolutions · p. 2
  • A partition optimal at both γ endpoints remains optimal throughout the interval between them.This follows because H(γ, σ) is linear in γ.Source: A. Scanning resolutions · p. 2
  • The resolution profile can be constructed efficiently by bisectioning γ to find where N(γ), the sum of squared community sizes, changes.N is monotonically decreasing with γ; when two partitions are optimal at both tested parameters, their N and E values must match.Source: A. Scanning resolutions · p. 2

B. Significance

The paper defines partition significance around the probability that a dense partition can be found in a random graph, rather than the probability that one fixed partition is dense. It develops this approach using subgraph probabilities and notes that its relationship to earlier measures is not fully resolved.

B. Significance

  • The figure contrasts evaluating the same fixed partition with searching the rewired graph for a partition having more internal edges.Panel (b) keeps the original partition; panel (c) uses a denser partition in the same graph.Source: Figure 1 · p. 3
  • Earlier approaches ask whether a fixed partition contains at least E internal edges, while this paper asks whether such a partition can be found in a random graph.The distinction reflects that community detection searches over partitions, including relabelings that can preserve a partition.Source: B. Significance · p. 3
  • The significance measure and earlier fixed-partition probabilities are related, but their behavior in the intermediate “grey area” needs further analysis.The passage says the measures are not completely independent and that a more in-depth analysis is required to understand the intermediate case.Source: B. Significance · p. 3
  • The asymptotic analysis considers fixed numbers of communities and subgraphs of size proportional to n with density q in random graphs.The authors note that exact results for finding a partition in a random graph are hard to obtain.Source: B. Significance · p. 3
  • For p ≠ q, the probability of a subgraph with density q decays as a Gaussian, at a rate set by the Kullback–Leibler divergence between p and q.Larger subgraphs with density different from p are less likely to be found.Source: B. Significance · p. 3

1. Encoding gain

Significance can be interpreted as the coding gain from using a community’s actual density rather than the graph-wide density. Summing that gain over communities yields partition significance.

1. Encoding gain

  • H(q, p) is cross-entropy, while H(q) is binary entropy; their difference measures the gain from encoding with q.The passage describes this difference as an entropy difference assuming q is the correct probability.Source: §1 · p. 4
  • Using each community’s actual density q instead of the graph-wide density p gives a coding gain of D(q ∥ p).The expected code length under p is H(q, p), while using q gives H(q); external edges are not counted.Source: §1 · p. 4

2. Using significance

The paper uses significance to select promising CPM resolutions or to optimize significance directly, while resolution profiles reveal stable, meaningful plateaus on benchmark networks.

2. Using significance

  • A greedy scan can restrict CPM’s candidate γ ranges to those with maximal significance, after skipping intervals where N(γ) is unchanged.The scan uses the fact that N decreases monotonically with γ and changes only at particular points.Source: §2 · p. 4
  • Optimizing significance itself is not resolution-limit-free: on a single-community induced subgraph, that partition has significance zero.The paper notes that this objective does not ensure the same partition remains optimal on all community-induced subgraphs.Source: §2 · p. 4

C. Resolution Profile

  • Significance is highest near the stable resolution plateaus on LFR benchmarks, where pairwise variation of information is low.The plateaus correspond to the planted partition in the benchmark networks.Source: C. Resolution Profile · p. 4
  • For hierarchical LFR graphs, two low-VI plateaus recover the hierarchy at μ2 = 0.1; they merge at μ2 = 0.5, with lower significance.The smaller communities are more significant when μ2 = 0.1.Source: C. Resolution Profile · p. 5

D. ER graphs

In Erdős–Rényi graphs, the resolution profile transitions near the graph density, while significance provides a low baseline that appears to scale with n log n.

D. ER graphs

  • The ER resolution profile transitions around γ ≈ p: below p it favors one large community, while above p it favors singleton communities.The asymptotic explanation is that relatively large subgraphs with density different from p become increasingly unlikely as n grows.Source: D. ER graphs · p. 5, Figure 3 · p. 6
  • The asymptotic account misses small communities with density above p because it ignores growth in the number of communities.This omission explains the somewhat slower increase in community count for γ > p.Source: D. ER graphs · p. 6
  • ER significance appears to scale as n log n and is relatively low compared with benchmark graphs, providing a baseline for observed significance.The paper presents comparison with this baseline as a first step toward hypothesis testing of community structure.Source: D. ER graphs · p. 6

E. Maximizing significance benchmarks

On LFR benchmarks, selecting CPM’s resolution by significance works well, and optimizing significance itself also performs well. Significance values also track whether planted communities are recoverable relative to random-graph baselines.

E. Maximizing significance benchmarks

  • Significance-based CPM resolution selection works quite well; optimizing significance also performs well, though it is slightly worse in some settings.The paper suggests local minima may trap significance optimization; its results appear to outperform Infomap, while OSLOM performs relatively well but below CPM scanning.Source: E. Maximizing significance benchmarks · p. 6, Figure 4 · p. 7
  • When the planted partition’s significance falls below that of an equivalent random graph, no tested method seems able to recover it correctly.When methods do recover the planted communities, their partition significance matches that of the planted partition; as mixing μ increases, significance decreases.Source: E. Maximizing significance benchmarks · pp. 6–7, Figure 4 · p. 7
  • Modularity shows the resolution limit, especially when detecting small communities in large networks.The benchmark results also show that the planted partition ceases to be optimal by significance when a method’s significance exceeds the planted partition’s.Source: Figure 4 · p. 7

F. European Parliament

Annual European Parliament roll-call networks show that significance associated with EP-group divisions increased over time, while national-party and member-state partitions were not significant. The 2008 analysis also reveals different community structures at different resolutions.

F. European Parliament

  • The analysis uses yearly networks from roll-call voting, linking MEPs who vote more in accord than average when both cast a yea or nay vote.The networks cover 1979–2009 and omit abstentions, non-voting, and absences from the pairwise vote comparison.Source: F. European Parliament · p. 7
  • National-party and member-state partitions were not significant, although MEPs from the same national party may vote similarly while also voting similarly to members of other parties.The division ran across member states, whose MEPs did not necessarily vote alike; national background may still matter for certain votes.Source: F. European Parliament · pp. 7–8
  • EP-group significance rose from S/⟨S⟩≈3.9 in 1981 to S/⟨S⟩≈16.8 in 2001, an increase of more than 400%.The EP-group partition showed 5 to 15 times the significance of a random graph; significance for national parties and member states remained almost constant.Source: Figure 5 · p. 8, F. European Parliament · p. 8
  • The EP-group significance trend rose particularly sharply between 1995 and 1996; the authors suggest EU enlargement as one possible explanation, while later accessions did not appear to increase divisiveness.The 2004 Eastern European and 2007 Eastern Balkan accessions did not seem to increase divisiveness.Source: F. European Parliament · pp. 8–9
  • The 2008 communities had high internal density and remained strongly connected to one another.The section examines γ = 0.5 and γ = 0.8, with γ = 0.8 corresponding to maximum CPM significance.Source: F. European Parliament · p. 9
  • For the 2008 parliament, γ = 0.5 groups the Greens/EFA with EUL/NGL, while at γ = 0.8 PES joins them and the partition resembles left–right politics.The maximum-significance partition differs from these CPM partitions and includes smaller communities, including a split of UEN with PES.Source: F. European Parliament · p. 9

III. DISCUSSION

The discussion presents an efficient resolution-profile scan and a method-independent significance measure, then reports benchmark and European Parliament applications. It also identifies unresolved statistical and null-model limitations.

III. DISCUSSION

  • The paper combines bisectioning to construct resolution profiles with a subgraph-probability measure of partition significance, interpretable as encoding gain.The authors report that significance portrays benchmark partitions accurately.Source: §III · p. 9
  • The authors report that significance conveys meaningful information in European Parliament voting data.They also describe significance as closely related to surprise and stochastic block models, relationships left for future exploration.Source: §III · p. 9
  • Significance can also assess partitions based on node characteristics such as school grades, gender, or dormitories, not only community-detection outputs..Source: §III · p. 9
  • The proposed ⟨S⟩∼n log n maximum for random graphs is conjectured, with a proof and standard-error estimate still lacking.Simulations suggest the standard error is relatively small.Source: §III · p. 9
  • The current significance measure uses an Erdös-Rényi random-graph baseline, though the authors note that accounting for degree distribution may be more realistic..Source: §III · p. 9

A. Subgraph probabilities

This section develops probabilities for induced subgraphs in Erdős–Rényi graphs and uses moment calculations to bound the occurrence of dense subgraphs.

A. Subgraph probabilities

  • The probability model is an Erdős–Rényi graph G(n,p), where each edge is included independently with probability p.The section uses induced-subgraph probabilities and notation for graphs with nc nodes and mc edges.Source: A. Subgraph probabilities · p. 9
  • The second moment method bounds the probability of at least one qualifying subgraph using expected occurrence counts and squared counts.The second moment calculation considers pairs of candidate subgraphs, including their overlap.Source: A. Subgraph probabilities · p. 10
  • The expected number of qualifying induced subgraphs is calculated through indicator variables for candidate subgraphs and their occurrence probabilities.The theorem concerns induced subgraphs with nc nodes and mc edges in a random graph.Source: A. Subgraph probabilities · pp. 9–10
  • For pairs of subgraphs, grouping by node overlap allows conditioning on the shared part, after which the two remaining parts are independent.The proof separates the overlap from each subgraph’s remainder.Source: A. Subgraph probabilities · p. 10
  • For subgraphs of size sn and fixed density q, log E(X) ∼ nH(s) − (sn)^2D(q ∥p), and the theorem bounds their occurrence probability asymptotically.The asymptotic analysis uses fixed 0 < s < 1 and bounds the probability of finding a dense subgraph.Source: A. Subgraph probabilities · p. 11

B. Optimizing significance

The optimization adapts Louvain-style node moves and graph aggregation, tracking the size represented by each node.

B. Optimizing significance

  • The optimization uses Louvain-style node moves and aggregates the graph while retaining the ability to move communities.Node size starts at 1 and becomes the sum of the sizes within an aggregated community.Source: B. Optimizing significance · p. 11
  • After aggregation, each node’s size is the sum of the sizes of the nodes in its community.Initially, each node has size 1.Source: B. Optimizing significance · p. 11
  • A node’s size and its edges to the source and destination communities enter the significance difference for moving it.The passage describes moving node i from community r to s using size ni and edge counts eir and eis.Source: B. Optimizing significance · p. 12
Loading 1306.3398v2…