Opinion Dynamics With Decaying Confidence: Application to Community Detection in Graphs

DOI10.1109/TAC.2010.2095315zbMATH Open1368.93349arXiv0911.5239MaRDI QIDQ5347805FDOQ5347805

Irinel-Constantin Morărescu, Antoine Girard

Publication date: 25 August 2017

Published in: IEEE Transactions on Automatic Control (Search for Journal in Brave)

Abstract: We study a class of discrete-time multi-agent systems modelling opinion dynamics with decaying confidence. We consider a network of agents where each agent has an opinion. At each time step, the agents exchange their opinion with their neighbors and update it by taking into account only the opinions that differ from their own less than some confidence bound. This confidence bound is decaying: an agent gives repetitively confidence only to its neighbors that approach sufficiently fast its opinion. Essentially, the agents try to reach an agreement with the constraint that it has to be approached no slower than a prescribed convergence rate. Under that constraint, global consensus may not be achieved and only local agreements may be reached. The agents reaching a local agreement form communities inside the network. In this paper, we analyze this opinion dynamics model: we show that communities correspond to asymptotically connected component of the network and give an algebraic characterization of communities in terms of eigenvalues of the matrix defining the collective dynamics. Finally, we apply our opinion dynamics model to address the problem of community detection in graphs. We propose a new formulation of the community detection problem based on eigenvalues of normalized Laplacian matrix of graphs and show that this problem can be solved using our opinion dynamics model. We consider three examples of networks, and compare the communities we detect with those obtained by existing algorithms based on modularity optimization. We show that our opinion dynamics model not only provides an appealing approach to community detection but that it is also effective.

Full work available at URL: https://arxiv.org/abs/0911.5239

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Programming involving graphs or networks (90C35) Social networks; opinion dynamics (91D30) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Agent technology and artificial intelligence (68T42) Discrete-time control/observation systems (93C55) Network design and communication in computer systems (68M10)

Cited In (20)

• Design and Analysis of Reset Strategy for Consensus in Networks with Cluster Pattern
• The critical behavior of Hegselmann-Krause opinion model with smart agents
• Criteria for asymptotic clustering of opinion dynamics towards bimodal consensus
• Analysis of opinion dynamics under binary exogenous and endogenous signals
• A generalized voter model with time-decaying memory on a multilayer network
• Impact of temporal network structures on the speed of consensus formation in opinion dynamics
• Control design with guaranteed cost for synchronization in networks of linear singularly perturbed systems
• A Density Description of a Bounded-Confidence Model of Opinion Dynamics on Hypergraphs
• A differential game model of opinion dynamics: accord and discord as Nash equilibria
• Community structure recovery and interaction probability estimation for gossip opinion dynamics
• Reset strategy for consensus in networks of clusters
• Topology Preservation for Multi-agent Networks: Design and Implementation
• Space-time budget allocation policy design for viral marketing
• A hybrid model for opinion formation
• Opinion dynamics with decentralized proportional-integral control strategy
• New cut-balance conditions in networks of clusters
• Bounded confidence opinion dynamics: a survey
• Erratum: A Bounded-Confidence Model of Opinion Dynamics on Hypergraphs
• Optimal campaign strategy for social media marketing with a contrarian population
• TIME DEPENDENCE OF THE SURVIVAL PROBABILITY OF AN OPINION IN A CLOSED COMMUNITY

This page was built for publication: Opinion Dynamics With Decaying Confidence: Application to Community Detection in Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5347805)