CS Paper Radar

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

eess.SY ·submitted 2026-10-25 14:27 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Robust Action Clusters and Cascades in Opinion Dynamics with Heterogeneous Action Thresholds

eess.SY ·2026-11-16 ·Hassan Munif, Anthony Couthures, Vineeth Satheeskumar Varma, Samson Lasaulce, Irinel-Constantin Morarescu
similarity 0.71
Abstract

We study the preservation and propagation of public actions in networks whose agents hold continuous private opinions. Agents update their opinions from their neighbors' observed actions and express them through action rules whose thresholds differ across agents. We characterize groups of agents that preserve a given common action regardless of the outsiders' actions. We call such a group, paired with that action, a robust action cluster. We show that a group is a robust action cluster for that action if and only if each member places enough of its influence weight on the group, where the required influence depends on the member's own action rule. We further give a sufficient condition under which an agent outside the cluster permanently adopts the cluster's action, and we iterate it to obtain a cascade of agents that are guaranteed to adopt that action. Finally, numerical examples show that replacing heterogeneous thresholds by their mean can change both the propagation of an action and the presence of robust action clusters.

0.22

Influence Enhancement in Opinion Dynamics Using Edge Modification: A Kron Reduction-Based Approach

eess.SY ·2026-09-12 ·Aashi Shrinate, Aravind Seshadri, Twinkle Tripathy, Laxmidhar Behera, Lingfei Wang +1 more
similarity 0.65
Abstract

With the emergence of online social networks as a primary platform for advertising and advocacy, enhancing a user's influence has become of significant interest. In this paper, we investigate this problem under the Friedkin Johnsen opinion dynamics model, wherein stubborn agents influence the opinions of other agents in the network. Unlike most of the existing works, we leverage topological properties of the network to increase the influence of a desired stubborn agent. Specifically, we introduce the notion of edge modification, which mimics the mechanism of recommendations in social networks. First, we present a topology-based condition that identifies edge modifications that always increase the influence of a desired stubborn agent. It is shown that the impact of the chosen edge modifications remains robust to changes in parameters such as stubbornness and the interaction weights. Thereafter, we formulate a discrete optimisation problem to identify a set of edge modifications that maximise the agent's influence centrality. We present a computationally efficient approximate solution to the optimisation problem. Finally, we demonstrate the effectiveness of our approach on the Friedkin-Johnsen opinion dynamics over the Erdos Renyi random graph.

0.31

Behavior of Nonlinear Opinion Dynamics over Large Networks

eess.SY ·2026-09-12 ·Yu Xing, Anastasia Bizyaeva, Karl H. Johansson
hot direction similarity 0.64
Abstract

Opinion dynamics have been studied for decades across disciplines, with much of the theoretical literature focusing on behaviors such as consensus, polarization, and clustering. Although classic models can exhibit more complex opinion patterns in simulations, quantifying such distributions is not fully understood. To address this question, in this paper, we study the behavior of nonlinear opinion dynamics over large-scale networks using graphons, which capture the underlying network structure. In the model, agents update their opinions according to a nonlinear rule that includes saturation effects in interactions. The network is represented by random graphs generated from a graphon, and a corresponding nonlinear dynamical model is introduced over the graphon. We show that the graphon dynamics approximate the finite-dimensional system, when the network size is large. Leveraging spectral approximation results for random graphs, we further show that the equilibria of the nonlinear model can also be approximated by those of the continuum limit. This result enables a quantitative characterization of the opinion distribution based on the underlying graphon structure. The theoretical results are illustrated by numerical simulation.

0.26

Scaling Laws for Majority-based Opinion Dynamics in the Presence of Stubborn Agents

cs.MA math.PR ·2026-08-11 ·Luke Meredith, Arpan Mukhopadhyay
similarity 0.63
Abstract

In a multi-agent system, there are often stubborn followers of specific opinions or beliefs. Motivated by this observation, in this paper, we aim to understand how stubborn agents affect the distribution of opinions in a network where both stubborn and non-stubborn agents interact with each other. To do so, we assume that all agents have an opinion in the set $\{0,1\}$ and each non-stubborn agent updates its opinion according to the $2k$\textit{-choices rule}, where the agent samples $2k$ neighbours (including both stubborn and non-stubborn neighbours) uniformly at random and adopts the majority opinion among the sampled group of neighbours and itself. We assume that a proportion of agents, $γ_i$, are stubborn followers of opinion $i\in \{0,1\}$. It is natural to expect that the steady-state distribution of the opinions in the network will be dominated by the opinion with the larger proportion of stubborn followers. We show that while this is true, the time to reach steady-state depends heavily on the values of the parameters $γ_0$ and $γ_1$. When the individual values of these parameters, as well as their difference, are small, it can take an exponentially long time (in the network size) to reach the steady-state. In sharp contrast, when at least one of the parameters $γ_0$ and $γ_1$ is large, the network reaches the steady-state in a time that is only logarithmic in the network size. Hence, there exists a sharp phase transition in the network dynamics based on the proportions of stubborn agents. We also characterise the behaviour of the system when the parameters $γ_0$ and $γ_1$ lie on the boundary of the phase transition. In this boundary region, we show using Stein's method that the dynamics are driven by a diffusion process which takes polynomial time to mix.

0.04

Gossip Agents: Reputation through Opinion Dynamics over Evolving Networks

cs.MA ·2026-10-15 ·Yutong Wu, Arlei Silva
similarity 0.62
Abstract · 10 pages, 8 figures

Sustained cooperation among self-interested learning agents is essential in many shared environments. Reputation systems are among the best-studied mechanisms for promoting such cooperation. Existing multi-agent reinforcement learning approaches, however, typically assume that reputation is either globally available to all agents or derived solely from an agent's own observations, leaving largely unexplored how reputational information propagates between agents. We study gossip, the exchange of information about third parties, as a mechanism for reputation diffusion over dynamic communication networks. Agents form private opinions from limited observations and exchange them with their neighbors following DeGroot opinion dynamics, while the communication network changes as agents interact and move. A tunable broadcast radius controls the reach of information, spanning private reputation, local gossip, and globally shared reputation. We study this framework in two \(n\)-player social dilemmas with distinct network dynamics: a Prisoner's Dilemma with randomly resampled interaction groups and Harvest, where communication neighborhoods emerge from agents' movements. Our results show that the reach of reputational information shapes cooperation in both environments. Moreover, in Harvest, reputation diffusion increases environmental rewards and leads to more peaceful and sustainable behavior.

0.28

Robust Opinion Maximization

cs.SI ·2026-10-30 ·Nikos Theologis, Evaggelia Pitoura, Evimaria Terzi, Panayiotis Tsaparas
similarity 0.61
Abstract

Opinion-formation models are fundamental for analyzing social behavior and understanding social dynamics. The Friedkin-Johnsen (FJ) model is the most commonly used model in this line of research. In FJ, the expressed opinion of an individual evolves over time as the combination of the opinions of their peers and a fixed inner opinion, weighted by their stubbornness. A problem that has received considerable attention is the problem of Opinion Maximization, where the goal is to adjust the parameters of the FJ model, such as stubbornness, or inner opinions, to maximize the average expressed opinion, i.e., the public opinion. Most existing work assumes full knowledge of the parameters of the model, which is unrealistic. In this paper, we introduce the problem of Robust Opinion Maximization, where we assume uncertainty for the inner opinions of the nodes, and we maximize the public opinion under worst-case assumptions on this uncertainty. Using tools from Robust Optimization, we formulate our problem as a max-min problem, and we develop an optimal two-step solution that is both highly intuitive and efficient. Experiments on several real-world networks demonstrate that our approach can achieve robust solutions for million-node graphs in minutes, and reveal that our robust strategies can significantly mitigate the impact of noise compared to standard baselines.

0.13

Strategic Opinion Manipulation in Multiplex Networks

cs.GT cs.SI ·2026-09-18 ·Raman Ebrahimi, Massimo Franceschetti
similarity 0.61
Abstract

Models of opinion dynamics on networks, provide a framework to study how a network of agents aggregates dispersed opinions into a consensus. However, existing models assume that agents truthfully report their opinions, and do not account for environments in which a platform aggregates agents' reports across multiple networks, and agents can strategically report different opinions on each. In this paper, we propose a model of strategic opinion manipulation on multiplex networks, in which a platform merges L network layers with attention weights, and each agent, holding a private opinion, chooses (potentially different) reports on each layer, at a layer-specific misreporting cost, so as to pull the merged consensus toward their own opinion. We show that this game has a unique Nash equilibrium in closed form, that the resulting consensus is the truthful consensus under a centrality tilted toward a manipulability index of each agent, and that the resulting distortion is the (centrality-weighted) covariance of agents' manipulability and opinions. We further show that agents' reports on every layer are more extreme than their opinions, so that the polarization observed by the platform overestimates the true polarization. Notably, we highlight that merging layers is a double-edged sword: as manipulability depends on the square of an agent's influence on each layer, spreading attention across layers dilutes manipulation, while heterogeneous misreporting costs across layers and shifts in agents' centralities can amplify it. Finally, we characterize the platform's optimal choice of attention weights, in closed form when the layers share a stationary distribution, and through an exact gradient and a marginal test otherwise. Together, our findings shed light on when aggregating opinions across networks is (not) robust to strategic manipulation, and point out potential interventions to alleviate it.

0.44

DeGroot Dynamics on Multiplex Networks with Directed and Acyclic Interlayer Connectivities

cs.SI econ.THeess.SYmath.DS+1 ·2026-10-19 ·Mia Zender, Kye Shi, Abigail Hickok, Weiqi Chu, Mason A. Porter
theory similarity 0.61
Abstract · 44 pages, 9 figures

In models of opinion dynamics, researchers typically examine how an individual's opinion on one topic is influenced by the opinions of their neighbors in a network. However, people's opinions on a topic are also influenced by their opinions and their neighbors' opinions on related topics. In an election, for example, the opinions of a voter on a variety of issues inform their opinions of electoral candidates. To consider the influence between people's opinions on multiple distinct topics, we study a multiplex extension of the traditional DeGroot consensus model. In our multiplex DeGroot model, different network layers represent distinct topics and directed interlayer edges (which are not allowed to form cycles) encode relationships between distinct topics. In our model, an individual's opinion on one topic is influenced both by the opinions of their neighbors on that topic and by their own opinions on related topics. We prove under mild conditions that our multiplex DeGroot model converges to a limit state. We also prove that strong connectedness in ``source layers'' (which represent fundamental beliefs) eventually yields a consensus opinion in each layer. In particular, we show that consensus on source layers can lead to consensus on other layers even when those layers otherwise would be polarized. By numerically simulating our multiplex DeGroot model on a two-layer network, we examine the effects on opinion dynamics of (1) different network structures and (2) different types of initial opinion data.

0.30