PaperlayerView exact revision on arXiv

Source-linked AI summary

Recursive Neighbor Pruning: Decentralized Community Detection with Certified Behavior from Saturated Opinion Dynamics

Anthony Couthures, Irinel-Constantin Morarescu, Vineeth Satheeskumar Varma, Samson Lasaulce, Antoine Girard

arXiv:2610.34316v1eess.SYcs.SY

TL;DR

Community detection often requires a central entity with full network knowledge, motivating decentralized methods based on local interaction. This paper studies RNP, which uses saturated opinion dynamics and recursive local link pruning. On two synthetic benchmark families, RNP matches Louvain up to a mean external-link ratio of about 0.4, with breakdown following the predicted confinement threshold.

  • Problem

    Standard community detection methods require a central entity that knows every link, which may be infeasible in large networks or when nodes cannot or will not share connections.

    Source: §I · p. 1

  • Method

    RNP has agents broadcast amplified, clipped actions, update opinions from neighbors' actions, and recursively remove links between neighbors with opposite-sign actions.

    Source: §I · p. 1, B. Nonlinear social learning dynamics · p. 2

  • Results

    On ABCD and LFR benchmarks, RNP matches Louvain up to a mean external ratio of about 0.4, and its breakdown follows the confinement threshold.

    Source: §VII · p. 6

  • Takeaways & Limitations

    For ξ≤0.4, RNP achieves NMI ≥0.99 and relative error below 0.01, similar to Louvain, while outperforming label propagation and DSB at ξ=0.4.

    Source: A. Results · p. 5

    Indivisibility is certified only statistically after N_retry unsuccessful rounds, and this stopping procedure can dominate communication cost.

    Source: §VI · p. 6

Abstract

from arXiv · show

Detecting communities, i.e., groups of densely connected nodes, usually requires a central entity that knows the whole network. We study Recursive Neighbor Pruning (RNP), a fully decentralized alternative inspired by social learning. Each agent holds a private opinion but only shows its neighbors a coarse public action, namely its opinion amplified and clipped to a fixed range. Agents repeatedly move their opinion toward the actions of their neighbors and, once opinions settle, drop the links with neighbors whose action has the opposite sign. Repeating this procedure on the remaining network splits it into communities, without any agent knowing the network or the number of communities. We use tools from nonlinear control to characterize this behavior. We show that splitting requires the amplification to exceed a threshold set by how strongly the network is bottlenecked. We also show that a group in which every member has enough of its links inside the group can no longer be split once its members agree, and that a single run separates such groups exactly when started from suitable opinions. Finally, we bound the number of runs and messages. On two standard families of synthetic networks, RNP is as accurate as the best centralized method as long as each node has fewer than about forty percent of its links outside its community, and it fails close to the value predicted by our analysis. It is more accurate than two decentralized competitors below this level, but exchanges many more messages.

I. INTRODUCTION

The paper seeks community detection without a central entity that knows every network link, using local interactions whose behavior can be guaranteed. RNP uses saturated opinion dynamics to prune links and identify connected communities.

I. INTRODUCTION

  • Centralized spectral-clustering and modularity methods require one entity to know every link, which may be impossible in large networks or when nodes cannot or will not share connections.Communities matter because they shape network function and information spread.Source: §I · p. 1
  • RNP is motivated by social learning, where people infer group membership from whether neighbors' visible choices agree, while ordinary neighbor averaging erases community structure through consensus.Coarse communication can sustain disagreement: sufficiently strong amplification makes neutral agreement unstable and polarizes groups toward opposite extremes.Source: §I · p. 1
  • RNP repeatedly settles local opinion dynamics, removes links between neighbors showing opposite-sign actions, and treats the remaining connected components as communities.Agents need not share exact private opinions or community labels, or know the network or number of communities.Source: §I · p. 1
  • The paper's contributions include a bottleneck-dependent amplification threshold for splitting, an internal-link condition protecting agreed groups, and an exact one-run separation result for suitable initial opinions.It also bounds runs and messages and compares RNP with centralized and decentralized methods on synthetic benchmark networks.Source: §I · p. 1

A. Graph and decentralized constraints

  • The target setting requires locality, limited disclosure, and uniform rules: agents interact only with neighbors, exchange one scalar per step, and use no leader or central aggregation.The paper reports that simulations validate its theoretical results.Source: A. Graph and decentralized constraints · p. 2, §I · p. 2

B. Nonlinear social learning dynamics

Agents maintain private opinions and broadcast bounded actions, then update toward the average actions of their neighbors. The assumed monotone action function amplifies opinions near zero and has three fixed points, supporting symmetry breaking.

B. Nonlinear social learning dynamics

  • Each agent broadcasts an action s(x_i) in [-1,1] and moves its opinion toward the average action of its neighbors.The update is an Euler discretization of the continuous-time dynamics, and the opinion state space [-1,1]^N is forward invariant.Source: B. Nonlinear social learning dynamics · p. 2
  • The action function is monotone with slope bounded between 0 and K, differentiable at zero with s′(0)=K>1, and has fixed points {-1,0,1}.The experiments use s_K(x)=sat(Kx), an amplified opinion clipped to [-1,1].Source: B. Nonlinear social learning dynamics · p. 2
  • Clipping means neighbors can reconstruct x_i exactly when |x_i|<1/K, but reveal only its sign when |x_i|≥1/K; this is not a formal privacy guarantee.The sign is always revealed, and repeated observations may reveal more.Source: B. Nonlinear social learning dynamics · p. 2

III. THE RECURSIVE NEIGHBOR PRUNING ALGORITHM

RNP repeats rounds of random initialization, opinion dynamics, and local removal of opposite-action links, stopping after consecutive rounds remove no links. Random starts can produce multiway cuts, and recursion refines the resulting components independently.

III. THE RECURSIVE NEIGHBOR PRUNING ALGORITHM

  • A round draws independent uniform initial opinions, runs the dynamics for T_max steps, and removes each edge whose endpoint actions have opposite signs.After a cut, another round starts on the pruned graph; after N_retry unsuccessful rounds, the final connected components are the communities.Source: §III · p. 2
  • The illustrated implementation uses a stochastic block model with four blocks of 40 nodes, within-block link probability 0.3, and between-block probability at most 0.05.Source: §III · p. 2
  • Random initialization samples the multistable attractor landscape and can cut a graph into more than two components in one round, unlike a Fiedler initialization that restricts rounds to bisections.A Fiedler initialization would also require global information.Source: §III · p. 2

IV. THEORETICAL GUARANTEES

The spectral results tie splitting to amplification above a graph-dependent threshold, with the Fiedler direction leading disagreement growth. Because the consensus mode grows faster, retries are needed, and large steps on nearly bipartite graphs are a discrete-time caveat.

A. Spectral threshold for the discrete-time dynamics

  • If KλN−1 < 1, equilibria are consensus states; if Kρ(G) < 1, disagreement contracts at every step.The equilibrium result restricts equilibria to α1 for α ∈ {−1, 0, 1}.Source: A. Spectral threshold for the… · p. 3
  • With s(x) = x (K = 1), linear averaging cannot reveal communities, and complete graphs cannot be split for any K.For nearly bipartite graphs, the discrete-time result has a gap at large h; for small h, the dynamics follows the continuous-time one.Source: A. Spectral threshold for the… · p. 3
  • When KλN−1 > 1, disagreement has an unstable direction led by the Fiedler vector, but the consensus mode grows faster, so RNP needs retries.The Fiedler sign pattern corresponds to the spectral cut.Source: A. Spectral threshold for the… · p. 3

B. Robustness and confinement of dense cores

The section distinguishes a disturbance-dependent robustness bound from a stronger confinement guarantee for polarized groups. Under the confinement condition, subsets already beyond the saturation threshold remain polarized; without sufficient internal connectivity, confinement is not assured.

B. Robustness and confinement of dense cores

  • The ISS gain is smaller for more internally connected agents, but that bound alone does not prevent a sign change.The bound tracks the group's distance from a polarized state and disturbance from external neighbors.Source: B. Robustness and confinement of dense… · p. 3
  • Under Proposition 3's group condition, the sets with all xi ≥ 1/K or all xi ≤ −1/K are forward invariant.The proposition states that its condition cannot be weakened without information about external neighbors.Source: B. Robustness and confinement of dense… · p. 3
  • If the confinement condition fails and all external neighbors broadcast −1, an agent can leave H+(W) when h = 1.This illustrates why the condition cannot be weakened without information about external neighbors.Source: B. Robustness and confinement of dense… · pp. 3–4
  • For saturated dynamics, groups whose members have more external than internal neighbors cannot be confined.The closed-form condition specializes a general force balance; its threshold is below one half.Source: B. Robustness and confinement of dense… · p. 4

C. Exact separation in one round

Theorem 1 gives a deterministic condition for one round to cut exactly the links between groups assigned opposite signs. It also supplies a sufficient time horizon for those groups to reach the required polarized state.

C. Exact separation in one round

  • If every node’s external-degree ratio is at most ε < (K −1)/2K and each initial signed opinion exceeds m*, then a round with Tmax ≥ t* cuts exactly the links between oppositely signed groups.The guarantee applies simultaneously to all groups in the partition.Source: C. Exact separation in one round · p. 4
  • The threshold m* is below 1/K, and the initial signed opinions must exceed it for every node in every group.The sufficient time t* is defined using the minimum initial signed opinion m0.Source: C. Exact separation in one round · p. 4
  • After t*, every group member broadcasts its assigned sign, so a link is cut if and only if its endpoints belong to groups with opposite signs.The proof lower-bounds the minimum signed opinion using the internal and external neighbor contributions.Source: C. Exact separation in one round · p. 4
  • Theorem 1 certifies the cut for specified initial conditions, not typical behavior; the actual basin is reported to be much larger.The passage attributes this difference mainly to uniform initialization covering a small set for large N.Source: C. Exact separation in one round · p. 4

D. Consequences for RNP

The corollary bounds RNP’s rounds and messages, and gives conditions for preserving a sufficiently cohesive group and for a component to remain uncut. Together with the splitting result, these conditions suggest a range of amplification values that can split the network while preserving isolated communities.

D. Consequences for RNP

  • RNP stops after at most (|E| + 1)Nretry rounds and sends at most 2Tmax|E| scalar messages per round.At least 2TmaxNretry messages per edge are spent after the last cut.Source: D. Consequences for RNP · p. 4
  • If the state enters H+(W) or H−(W), no edge inside W is cut that round, and W’s condition (4) continues to hold in later graphs while W remains intact.The preservation guarantee applies after the state enters either specified set during a round.Source: D. Consequences for RNP · p. 4
  • If a component Gc satisfies Kρ(Gc) < 1, each round converges to the consensus set, and a limit of ±1 leaves every edge of Gc uncut.Components evolve independently.Source: D. Consequences for RNP · p. 4
  • The suggested range K*(G) < K < minc K*(Gc) can allow the graph to split while certifying isolated communities as indivisible.For discrete time, use ρ(Gc) in place of λN−1 for each community subgraph.Source: D. Consequences for RNP · p. 4

V. NUMERICAL PERFORMANCE

The numerical-performance section sets up ABCD and LFR synthetic benchmarks and specifies the methods and measures used for evaluation. The supplied passages describe the benchmark and figure contents, but do not report the numerical outcomes.

V. NUMERICAL PERFORMANCE

  • ABCD is the main benchmark; unlike LFR, its communities remain well connected as mixing increases, and ξ denotes expected external-degree ratio.The reported ξ is the mean of the nodes’ external-degree ratios.Source: §V · p. 4
  • Both benchmarks use N = 1000 with degree exponent 2.5, degrees in [10, 100], community-size exponent 1.5, and sizes in [20, 250].The default RNP settings are K = 4, h = 0.5, Tmax = 300, and Nretry = 50; LFR uses eight graphs per nominal mixing value.Source: §V · p. 4
  • The evaluation compares Louvain, label propagation, and distributed spectral bisection using NMI and scalar messages per edge.Fig. 2 shows ABCD results, while Fig. 3 plots LFR results against measured mean external-degree ratio.Source: §V · pp. 4–5, Figure 2 · p. 5, Figure 3 · p. 5

A. Results

On ABCD and LFR benchmarks, RNP matches Louvain at mean external-link ratios around 0.4 or below, then degrades near the predicted confinement threshold. It is less communication-efficient than decentralized competitors, and reducing retries trades message cost for accuracy.

Accuracy

  • RNP achieves NMI ≥0.99 on ABCD for ξ ≤0.4, similar to Louvain, and NMI ≥0.97 on LFR up to mean external ratio ¯ξ ≈0.38.On LFR, NMI falls to 0.58 at ¯ξ = 0.46 and 0.03 beyond 0.53; ABCD performance also falls sharply beyond ξ ≈0.40.Source: A. Results · p. 5
  • For ξ ≤0.4, RNP achieves NMI ≥0.99 and finds correct communities (relative error below 0.01), outperforming label propagation and DSB, whose NMI values are 0.72 and 0.69 at ξ = 0.4, respectively.Beyond ξ ≈0.40, RNP’s NMI drops to about 0.47 at ξ = 0.45, 0.09 at ξ = 0.5, and 0 from ξ = 0.55, while Louvain stays above 0.96 up to ξ = 0.55. DSB degrades more slowly and is the most accurate decentralized method for ξ ≥0.45; when RNP fails, it returns a single community.Source: A. Results · p. 5

Communication cost

  • About 3 × 10^4 messages per edge makes RNP two orders of magnitude costlier than DSB and three orders costlier than label propagation.The final Nretry unsuccessful rounds alone account for 2TmaxNretry = 3 × 10^4 messages per edge.Source: A. Results · p. 5
  • RNP-light uses twentyfold fewer messages with the same accuracy for ξ ≤0.3, but its NMI drops to 0.46 at ξ = 0.4.With Nretry = 10 and Tmax = 300, RNP returns the same partitions for ξ ≤0.275 with three times fewer messages, but NMI drops quickly as ξ increases.Source: A. Results · p. 5

Breakdown follows the confinement threshold

  • For K = 2, 4, and 8, RNP maintains NMI ≥0.97 up to ξ = 0.2, 0.4, and 0.425, respectively, tracking the predicted confinement threshold.The indivisibility window is conservative in practice, with no over-segmentation observed and relative error at most 0.06.Source: A. Results · p. 5

VI. LIMITATIONS AND DISCUSSION

RNP's cuts are irreversible, stopping and gain selection impose practical constraints, and saturation is not a privacy guarantee. The authors also identify limits on the theorem's scope and point to two variants for future study.

Irreversible cuts

  • A single trajectory determines irreversible cuts; the theorem covers an exponentially small set of starting opinions, leaving frontier-node assignment dependent on initialization.The authors note that the actual basin is much larger than this theorem-bound set, partly because uniform initialization covers a small set for large N.Source: §VI · p. 6

Cost of stopping

  • Indivisibility is certified statistically only after Nretry unsuccessful rounds because the consensus mode dominates.The retry counter requires component-wide agreement on whether a cut occurred; a common clock with a fixed number of rounds is offered as a decentralized alternative.Source: §VI · p. 6

Gain selection

  • The graph-dependent thresholds cannot be computed by agents, and no local rule for adapting K is available yet.The results support choosing a large initial gain.Source: §VI · p. 6

Disclosure and scope

  • Saturation limits but does not prevent information leakage, and the paper claims no formal privacy guarantee; Proposition 1 assumes undirected graphs.The stronger condition in item (ii) also restricts the stated scope.Source: §VI · p. 6

Future variants

  • The extended version studies transient-time cuts with decaying confidence bounds and replacing hard cuts with edge-reliability scores across rounds.Source: §VI · p. 6

VII. CONCLUSION

The conclusion summarizes RNP's theoretical guarantees and benchmark behavior, while identifying communication cost and typical-basin guarantees as remaining weaknesses. Local gain adaptation is also left for future work.

VII. CONCLUSION

  • Recursive Neighbor Pruning (RNP) is a decentralized community-detection algorithm whose discrete-time agent dynamics exchange saturated actions and cut ties with opposite-action neighbors; analysis establishes a spectral splitting threshold and identifies the Fiedler symmetry-breaking direction.It also gives a closed-form confinement condition.Source: §VII · p. 6
  • On ABCD and LFR, RNP matches Louvain up to a mean external ratio of about 0.4, with breakdown following the confinement threshold and safe failure beyond it.Source: §VII · p. 6
  • Communication cost is RNP's main weakness, and the typical basin of separating rounds lacks guarantees; future work will address this and local gain adaptation.Source: §VII · p. 6

Related papers

Loading 2610.34316v1…