Asynchronous Opinion Dynamics in Social Networks

Abstract: Opinion spreading in society decides the fate of elections, the success of products, and the impact of political or social movements. A prominent model to study opinion formation processes is due to Hegselmann and Krause. It has the distinguishing feature that stable states do not necessarily show consensus, i.e., the population of agents might not agree on the same opinion.

We focus on the social variant of the Hegselmann-Krause model. There are $n$ agents, which are connected by a social network. Their opinions evolve in an iterative, asynchronous process in which agents are activated one after another at random. When activated, an agent adopts the average of the opinions of its neighbors having a similar opinion (where similarity of opinions is defined using a parameter $\varepsilon$). Thus, the set of influencing neighbors of an agent may change over time. To the best of our knowledge, social Hegselmann-Krause systems with asynchronous opinion updates have only been studied with the complete graph as social network.

We show that such opinion dynamics are guaranteed to converge for any social network. We provide an upper bound of $\mathcal{O}(n|E|^2 (\varepsilon/\delta)^2)$ on the expected number of opinion updates until convergence to a stable state, where $|E|$ is the number of edges of the social network, and $\delta$ is a parameter of the stability concept. For the complete social network, we show a bound of $\mathcal{O}(n^3(n^2 + (\varepsilon/\delta)^2))$ that represents a major improvement over the previously best upper bound of $\mathcal{O}(n^9 (\varepsilon/\delta)^2)$.

game theoryoptimization and control

Audience: researchers in the topic

( paper )

---

CAM seminar

Series comments: Online streaming via zoom on exceptional cases if requested. Please contact the organizers at the latest Monday 11:45.

---