kth.sePublications KTH
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Concentration in Gossip Opinion Dynamics over Random Graphs
KTH, School of Electrical Engineering and Computer Science (EECS), Intelligent systems, Decision and Control Systems (Automatic Control). KTH, School of Electrical Engineering and Computer Science (EECS), Centres, Digital futures.ORCID iD: 0000-0003-2641-2962
KTH, School of Electrical Engineering and Computer Science (EECS), Intelligent systems, Decision and Control Systems (Automatic Control). KTH, School of Electrical Engineering and Computer Science (EECS), Centres, Digital futures.ORCID iD: 0000-0001-9940-5929
2024 (English)In: SIAM Journal of Control and Optimization, ISSN 0363-0129, E-ISSN 1095-7138, Vol. 62, no 3, p. 1521-1545Article in journal (Refereed) Published
Abstract [en]

We study concentration inequalities in gossip opinion dynamics over random graphs. In the model, a network is generated from a random graph model with independent edges, and agents interact pairwise randomly over the network. During the process, regular agents average neighbors' opinions and then update, whereas stubborn agents do not change opinions. To approximate the original process, we introduce a gossip model over an expected graph, obtained by averaging all possible networks generated from the random graph model. Using concentration inequalities, we derive high-probability bounds for the distance between the expected final opinion vectors over the random graph and over the expected graph. Leveraging matrix perturbation results, we show how such concentration can help study the effect of network structure on the expected final opinions in two cases: (i) When the influence of stubborn agents is large, the expected final opinions polarize and are close to stubborn agents' opinions. (ii) When the influence of stubborn agents is small, the expected final opinions are close to each other. With the help of concentration inequalities for Markov chains, we obtain high-probability bounds for the distance between time-averaged opinions and the expected final opinions over the expected graph. In simulation, we validate the theoretical findings and study a gossip model over a stochastic block model that has community structure.

Place, publisher, year, edition, pages
Society for Industrial & Applied Mathematics (SIAM) , 2024. Vol. 62, no 3, p. 1521-1545
Keywords [en]
concentration, opinion dynamics, random graphs, social networks
National Category
Control Engineering Probability Theory and Statistics Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-367398DOI: 10.1137/23M1545823ISI: 001230833500002Scopus ID: 2-s2.0-85195291273OAI: oai:DiVA.org:kth-367398DiVA, id: diva2:1984797
Note

QC 20250923

Available from: 2025-07-17 Created: 2025-07-17 Last updated: 2025-09-23Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Xing, YuJohansson, Karl H.

Search in DiVA

By author/editor
Xing, YuJohansson, Karl H.
By organisation
Decision and Control Systems (Automatic Control)Digital futures
In the same journal
SIAM Journal of Control and Optimization
Control EngineeringProbability Theory and StatisticsComputer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 35 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf