Recursive Neighbor Pruning: Decentralized Community Detection with Certified Behavior from Saturated Opinion Dynamics
Submitted to 2027 European Control Conference (ECC)
Abstract
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.
Citation
BibTeX citation:
@misc{couthures2026,
author = {Couthures, Anthony and Morărescu, Irinel-Constantin and
Satheeskumar Varma, Vineeth and Lasaulce, Samson and Girard,
Antoine},
title = {Recursive {Neighbor} {Pruning:} {Decentralized} {Community}
{Detection} with {Certified} {Behavior} from {Saturated} {Opinion}
{Dynamics}},
date = {2026},
url = {https://anthonycouthures.github.io/publications/2026_preprint_recursive-neighbor-pruning.html},
langid = {en},
abstract = {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.}
}
For attribution, please cite this work as:
Anthony Couthures, Irinel-Constantin Morărescu, Vineeth Satheeskumar
Varma, Samson Lasaulce, and Antoine Girard. 2026. “Recursive
Neighbor Pruning: Decentralized Community Detection with Certified
Behavior from Saturated Opinion Dynamics.”