PaperlayerView exact revision on arXiv

Source-linked AI summary

Multiresolution community detection for megascale networks by information-based replica correlations

Peter Ronhovde, Zohar Nussinov

arXiv:0812.1072v4physics.soc-phcond-mat.stat-mechphysics.comp-phphysics.data-an

TL;DR

Community divisions may change with scale, making it difficult to identify the important resolutions of hierarchical and other multiscale graphs. The paper uses Potts-model replicas and information-based correlations across resolutions to quantify those structures. It reports high accuracy on large systems, while noting limitations for small or sharply transitioning systems.

  • Problem

    Community divisions can depend on examination scale, creating a need to identify and quantitatively evaluate important resolutions in multiresolution graphs.

  • Method

    The method solves a graph across resolutions and compares independent replicas using NMI, VI, and related information measures to select strongly correlated structures.

  • Results

    40 million nodes and one billion edges were analyzed in 3.7 hours, while the multiresolution algorithm handled 200,000 nodes and over 10 million edges in about 4.6 hours on one processor.

  • Takeaways & Limitations

    The approach quantifies best resolutions and relative structural strength, applies beyond strictly hierarchical structures, and can in principle work with other resolution-based community models.

  • Takeaways & Limitations

    For small systems, NMI and VI correlations can remain strong across structural transitions, requiring H and I to resolve the ambiguity.

Abstract

from arXiv · show

We use a Potts model community detection algorithm to accurately and quantitatively evaluate the hierarchical or multiresolution structure of a graph. Our multiresolution algorithm calculates correlations among multiple copies ("replicas") of the same graph over a range of resolutions. Significant multiresolution structures are identified by strongly correlated replicas. The average normalized mutual information, the variation of information, and other measures in principle give a quantitative estimate of the "best" resolutions and indicate the relative strength of the structures in the graph. Because the method is based on information comparisons, it can in principle be used with any community detection model that can examine multiple resolutions. Our approach may be extended to other optimization problems. As a local measure, our Potts model avoids the "resolution limit" that affects other popular models. With this model, our community detection algorithm has an accuracy that ranks among the best of currently available methods. Using it, we can examine graphs over 40 million nodes and more than one billion edges. We further report that the multiresolution variant of our algorithm can solve systems of at least 200000 nodes and 10 million edges on a single processor with exceptionally high accuracy. For typical cases, we find a super-linear scaling, O(L^{1.3}) for community detection and O(L^{1.3} log N) for the multiresolution algorithm where L is the number of edges and N is the number of nodes in the system.

I. INTRODUCTION

Community structure can change with examination scale, motivating multiresolution methods for hierarchical and other multiscale networks. This paper combines Potts-model detection with information-based replica comparisons to identify and quantify important resolutions.

  • Multiresolution analysis is needed to capture community divisions and relationships that vary across scales, including in hierarchically organized systems.
  • The method examines correlations among independent graph replicas across resolutions, using NMI and VI to identify best resolutions and estimate structural strength.
  • The approach applies beyond strictly hierarchical graphs and, in principle, to any community detection model targeting different resolutions.
  • The underlying Potts model and community detection algorithm achieve accuracy at least equal to the best currently available methods and resist noise effects.
  • 40 million nodes and one billion edges were analyzed in 3.7 hours, while multiresolution analysis handled 200,000 nodes and over 10 million edges in about 4.6 hours on one processor.

III. POTTS MODEL HAMILTONIAN

The absolute Potts model evaluates connected and unconnected edge weights directly, yielding an effectively local community measure. Its weighting parameter γ sets resolution through typical internal community edge density without dependence on global graph parameters.

  • The model directly sums connected and unconnected edge weights without a weighted null model, producing an effectively local measure free from the resolution limit.
  • The absolute Potts model uses fixed topology and edge-weight parameters, while γ weights unconnected edges and Potts spin values encode community membership.
  • Community edge density is defined from internal edges and nodes, linking γ to the minimum internal density required for a community.
  • Typical internal edge density corresponds to system resolution, so γ effectively sets resolution independently of the graph’s global parameters.

IV. COMMUNITY DETECTION ALGORITHM

The community detection algorithm iteratively moves nodes toward lower-energy communities and repeats independent trials, selecting the lowest-energy configuration. Neighbor searches and node skipping improve sparse-graph performance.

  • Nodes are sequentially placed into communities that best lower energy, with cycles repeated until a full pass makes no moves.
  • The algorithm can test community merges to escape local-minimum traps and optionally permit zero-energy moves for difficult problems.
  • Independent optimization trials use permuted node orders, and the lowest-energy configuration is selected as the solution.
  • Neighbor-node searches and skipping strongly defined nodes improve performance, reaching O(N^(1+β)Z^(1+β)t log Z) for sparse graphs.

V. MULTIRESOLUTION ALGORITHM

The multiresolution algorithm addresses the difficulty of selecting meaningful resolutions by comparing independent solutions across a range of γ values. Strong replica agreement identifies candidate resolutions and estimates structural strength, while supplementary measures and explicit assumptions constrain interpretation.

  • Selecting best resolutions is difficult because correct model weights are generally unknown without prior information.
  • Independent replicas are compared with NMI or VI across resolutions, and the strongest correlations determine the selected resolutions.
  • High average NMI indicates dominant structures, whereas low VI indicates better replica agreement and supports estimates of relative structural strength.
  • The method does not distinguish unrelated multiresolution structures from strictly hierarchical ones, although additional hierarchical constraints can be imposed.
  • Replica correlations rely on treating meaningful information as present in local energy minima, including incomplete solutions, within the energy landscape.
  • The framework can incorporate replica interactions through a free-energy-like functional using information measures between replica pairs and a temperature-like scale T.

B. Algorithm

The algorithm sweeps Potts-model resolutions, solves multiple independently initialized replicas, and uses information correlations to identify strong structures. It estimates O(log N) resolutions and reports scaling for large graphs, while retaining generality rather than enforcing hierarchy.

  • Resolution sweep: The algorithm solves a graph across resolutions {p_i} mapped to model weights {γ_i}, with p_in representing each partition’s minimum internal edge density.The resolution sweep begins near p_0 ≃ 0.95 and decreases through prescribed steps until the system is no longer reducible.
  • Replica generation: Independent replicas are generated by reordering traversal of a symmetric one-node-per-community initialization, with t optimization trials per replica.Typical settings use 8 ≤ r ≤ 12 replicas and 2 ≤ t ≤ 20 trials per replica.
  • Information evaluation: At each resolution, the algorithm computes pairwise replica NMI, VI, mutual information, and Shannon entropy, then selects regions with high NMI or low VI correlations.If correlations are imperfect, the lowest-energy replica is chosen as the partition solution; a consensus partition is another option.
  • Complexity: O(log N) resolutions are estimated to specify an arbitrary system, while the dominant algorithmic scaling is O(N^(1+β)Z^(1+β)rt log N log Z).Here N is the node count, Z the average degree, r the replica count, t the trial count, and β is small.
  • Generality: The algorithm does not require detected structures to be hierarchical, and imposing hierarchical constraints on some replicas produced only modest improvement in identifying the best resolutions.The unconstrained method is retained for its generality and relative simplicity.

VI. EXAMPLES

Constructed hierarchies provide test cases for the multiresolution algorithm from 256 nodes to 200 000 nodes. Information-measure extrema recover the intended levels, including a noisy large hierarchy and communities whose external edges exceed internal edges.

  • 256-node hierarchy: The 256-node test graph contains a three-level heterogeneous hierarchy with densities p3 = 0.9, p2 = 0.3, and p1 = 0.1.Level-3 communities average 16 nodes, while level-2 merged groups range from 33 to 76 nodes.
  • 256-node hierarchy: NMI peaks at levels 2 and 3 with IN = 1, while VI minima at the same levels have V = 0, indicating perfect replica agreement.Plateaus in H, I, and the average cluster count q provide additional structural indications but are not sufficient alone in later examples.
  • 256-node hierarchy: At level 3, the algorithm identifies communities despite Zout ≃ 32.0 and Znoise_out ≃ 19.8 exceeding Zin ≃ 14.3.The external edges are not concentrated strongly enough into one external cluster, supporting robustness to this noise pattern.
  • Resolution interpretation: The VI extrema occur near γ1 = 0.111 and γ2 = 0.435, corresponding through γ/(γ + 1) to inter-community densities p1 = 0.1 and p2 = 0.3.The authors associate these points with increased energy-landscape complexity when competing states have nearly equal energy.

B. Erd˝os-R´enyi random graph

The Erdős-Rényi control graph distinguishes genuine multiresolution structure from plateaus and spikes caused by trivial or inconsistent partitions. Information correlations, rather than plateaus alone, provide the decisive check.

  • Control graph: The random graph has the same average density p = 0.182 as the 256-node hierarchy and produces a single NMI peak tied to a trivial partition.The partition sizes are approximately {1, 2, 253} across replica solutions.
  • Runtime comparison: The random-graph run takes about 6.9 seconds, compared with 6.1 seconds for the corresponding hierarchy, despite nearly identical density and node count.Run-time variation is influenced by effective noise as well as replica and trial counts.
  • Plateau interpretation: Plateaus in NMI, VI, H, I, or q do not indicate consistent multiresolution structure when replica correlations are poor.At the random-graph plateau, IN ≃ 0.70 and V ≃ 3.6; detailed solutions give IN = 0.644 and V = 4.04.
  • Plateau interpretation: The weak plateaus reflect similarly sized partitions with similarly high community edge densities rather than a consistent structure.Information checks on nearby solutions can remedy the risk of misidentifying plateaus as significant structure.
  • Control graph: The random graph’s NMI spike is marked as trivial by low mutual information I and low VI V and Shannon entropy H at the corresponding extrema.Thus, a prominent NMI feature does not by itself establish meaningful structure.

D. Dolphin social network

The dolphin network exhibits multiple strongly defined partitions across resolutions, including a known two-cluster split and finer subgroupings. Information measures also reveal ambiguity in some transitions and help distinguish robust structures from weaker or noisy plateaus.

  • Dolphin social network: 0.78 sec: Ten replicas with ten trials identified a known 21-and-41 dolphin split with perfect NMI and VI correlations.The partition has I_N = 1 and V = 0.
  • Dolphin social network: Partitions (ii)–(v) were identified as important candidates from strong NMI and VI correlations, including a perfectly correlated major reconfiguration in partition (iv).Partition (v) is a slight variation of (iv), with I_N ≃0.998 and V ≃0.0178.
  • Dolphin social network: The figures plot I_N, V, H, and I against Potts weight γ, with offset axes showing cluster count q; configuration (i) matches a known community split.The pictorial summaries show configurations (i), (iv), and (v).
  • Dolphin social network: The algorithm permits nodes to move between super-groups across resolutions, supporting multiresolution structures that are not restricted to nested assignments.In configuration (iv), the groups {7, 19, 30} and {23, 36, 39} split nodes between the two super-groups of configuration (i).
  • Dolphin social network: The number of clusters q detects structures (ii) and (v) but misses partition (iv), while weak plateaus in H, I, or q can indicate noisy or transient resolutions.The information measures provide complementary evidence for evaluating candidate resolutions.
  • Highland Polopa tribe relations: All Polopa configurations shown are strongly defined with I_N = 1 and V = 0, while the three-cluster partition agrees exactly with prior analysis.Five-cluster solutions subdivide the three-cluster system into two slightly different dense configurations of allied tribes.

VII. ACCURACY

The multiresolution algorithm accurately recovers benchmark communities across varied system sizes and mixing conditions, while revealing specific limits for exceptionally small systems. Its accuracy reflects local resolution by community edge density rather than a global resolution-limit effect.

  • Benchmark tests: N = 1000 and 5000 benchmark systems were tested across degree and community-size exponents, with results summarized over varying mixing parameter µ.The experiments used α = 2 and 3, β = 1 and 2, and mean degree ⟨k⟩ = 15.
  • Multiresolution analysis: The algorithm identifies the best partition using the strongest average NMI correlation among replica pairs across resolutions.For one benchmark graph, the analysis used r = 8 replicas and t = 4 energy-optimization trials per replica.
  • Benchmark accuracy: Combined with the absolute Potts model, the multiresolution algorithm performs excellently against known benchmark partitions across 0.1 ≤ µ ≤ 0.7.Solutions were compared with known partitions using NMI and averaged over repeated benchmark graphs.
  • Benchmark accuracy: For N = 5000, external edges spread across more communities, increasing the contrast between interior and external edge densities and making the benchmark easier to identify.The converse behavior occurs for small systems.
  • Limitations: For N ≲300, the algorithm has difficulty identifying all communities; for N = 300, IN ≃1.0 only for µ ≤0.45.The limitation arises from simultaneously resolving communities with substantially different relative densities, not from a resolution-limit effect.
  • Limitations: Despite substantially different community edge densities, realistic community-size distributions produce benchmark structures that the Potts model can solve well.The numerator in the edge-density expression is constant on average across communities, while community sizes generate a substantial distribution of edge densities.

VIII. DISCUSSION

The information-based evaluations generally identify important multiresolution structures and quantitatively estimate the best resolutions, while complementary measures help resolve ambiguous cases. The discussion also highlights extensions to localized analysis, alternative scaling, and difficulty transitions.

  • Strong NMI and VI correlations consistently indicate important multiresolution structures across the reported figures.Plateaus in mutual information and Shannon entropy often confirm the partitions selected by these correlations.
  • Independent optimization at each resolution can produce nonhierarchical partitions in which node reassignments create overlaps between communities across levels.This behavior is reported for the dolphin social network and other individually oriented networks.
  • 6.1 s versus 6.9 sec illustrates that runtime depends on effective noise, even for graphs with nearly identical density and size.The comparison uses the hierarchy in Fig. 2 and a corresponding random graph in Fig. 3.
  • NMI and VI are complementary: VI more clearly identifies poor agreement, whereas NMI can reveal very low-density divisions.Plateau behavior in H, I, and q can be qualitative or misleading, while NMI and VI can identify short-lived but strongly defined structures.
  • Small systems or graphs with few intercommunity connections can keep NMI and VI correlations strong across structural transitions.In such cases, H and I may be needed to resolve the ambiguity.
  • Future directions include additive resolution scaling, localized partitions or confusion-matrix analysis, and a detailed study of the community-detection easy–hard crossover.The proposed local analysis could identify stable localized structures beyond global information correlations.

IX. CONCLUSION

The paper presents a Potts-model approach that compares independently solved resolutions through information measures to identify and evaluate multiresolution structure. It supports general partitions, avoids the cited resolution limit, achieves high accuracy, and scales to very large graphs.

  • The approach identifies and quantitatively evaluates the best multiresolution structures, or their absence, in graphs.
  • Independent solutions at every resolution allow the algorithm to identify completely general multiresolution structures.
  • Information comparisons make the multiresolution procedure applicable in principle to any community-detection model that examines different resolutions.
  • The local Potts model is reported as accurate as the best currently available methods and free from the literature’s resolution limit.
  • O(10^7) nodes and O(10^9) edges were tested with the community-detection algorithm, while the multiresolution algorithm showed extremely high accuracy on large systems.

APPENDIX A: ACCURACY OF THE COMMUNITY DETECTION ALGORITHM

The algorithm accurately recovers planted communities across noise levels, while additional optimization trials matter most in an intermediate-difficulty regime. It also scales to systems with 40 million nodes and over one billion edges.

  • Benchmark setup: 128-node benchmark tests community recovery using four planted clusters and evaluates accuracy against externally connected edges Zout.The analysis constrains q to four and uses γ = 1; accuracy is measured as the percentage of correctly placed nodes.
  • Accuracy results: 95% or better accuracy is maintained up to Zout = 7.5, matching or exceeding the accuracy of the best available algorithms.These results use an older, slower algorithm version without neighbor-node search.
  • Trial dependence: t = 10 optimization trials mark diminishing returns for many tests, with the greatest benefit occurring at intermediate difficulty, 8 ≤Zout ≤9.High-noise systems can trap replicas in different local energy minima, making additional trials useful in the transition region.
  • Noise transition: Additional trials provide negligible benefit for Zout ≲7 but become important near 8 ≤Zout ≤9 before diminishing returns in the hard region Zout ≳9.5.The susceptibility peak becomes more pronounced as the number of trials increases.
  • Large-scale validation: 40 million nodes and over one billion edges are solved in 3.7 hours on a single processor, with 13 nodes misclassified.The solved and known partitions have IN ≃1.00 and V = 1.85 × 10^-6, with Vmax = log2 N ≃25.3.

APPENDIX D: GENERALIZATION OF THE INFORMATION-BASED REPLICA METHOD

The replica-information framework can be generalized from graph partitions to optimization systems with general Hamiltonians. It replaces graph-based entropy calculations with thermodynamic quantities while retaining information-based correlations among replicas.

  • Generalization: The method recasts information measures for non-graph optimization problems with general Hamiltonians or cost functions H.The replica comparison is expressed through an alternative mutual-information formulation.
  • Thermodynamic formulation: For general Hamiltonians, Shannon entropies of individual and combined replicas are replaced by thermodynamic entropies.The construction uses traces over coordinates in collections of decoupled copies.
  • Permutation issue: Identical graph nodes can violate permutation invariance of standard mutual information when adjacency is unchanged by swapping them.In graph terms, identical nodes satisfy [Pij, A] = 0.
  • Graph interpretation: The graph formulation treats the N nodes as ensemble points and communities as q possible states whose occupation probabilities reproduce pk = nk/N.This provides a physical analogy for the information measures used in graph partitions.
  • Scope boundary: The thermodynamic extension may require many copies of the same system, whereas graph problems use node number N as effective ensemble points.This copy requirement is identified as a potential limitation for non-graph applications.

APPENDIX E: MULTIRESOLUTION BENCHMARK COMMENTS

The benchmark can contain strongly correlated transient resolutions in addition to the intended solution. These artifacts can complicate automated selection, especially when a transient configuration slightly outperforms the stable intended configuration on NMI and VI.

  • Benchmark structure: The benchmark is designed with one intended solution, but random graph-generation effects can create additional transient, strongly defined resolutions.The multiresolution algorithm is intended to identify all strongly defined resolutions, including such artifacts.
  • Low-mixing regime: For µ ≲0.4, multiple resolutions near the intended solution can show perfect correlations, IN = 1 and V = 0, despite varying across graph realizations.These transitional partitions are artifacts of the randomly generated system.
  • Selection difficulty: For 0.45 ≲µ ≲0.65, a transient configuration can slightly exceed the intended configuration in NMI, causing automated selection to favor the wrong resolution.The difference is δIN ≃6.3 × 10^-5, while the intended configuration has stable plateaus and strong NMI and VI correlations.
  • Accuracy effects: The observed accuracy perturbations remain high at IN ≃0.96, and an iteration cap filters most low-density spikes.Moving NMI or VI averages are proposed as a possible further improvement to automated analysis.
Loading 0812.1072v4…