Asynchronous opinion dynamics in social networks

Our opinions are not static. On the contrary, opinions are susceptible to dynamic changes, and this is heavily exploited by (social) media, influencers, politicians, and professionals for public relations campaigns and advertising. The way we form our opinions is not a solitary act that simply combines our personal experiences with information from the media. Instead, it is largely driven by interactions with our peers in our social network. We care about the opinions of our peers and relatives, and their opinions significantly influence our own opinion in an asynchronous dynamic process over time. Such opinion dynamics are pervasive in many real-world settings, ranging from small scale townhall meetings, community referendum campaigns, parliamentary committees, and boards of enterprises to large scale settings like political campaigns in democratic societies or peer interactions via online social networks.

The aim for understanding how opinions are formed and how they evolve in multi-agent systems is the driving force behind an interdisciplinary research effort in diverse areas such as sociology, economics, political science, mathematics, physics, and computer science. Initial work on these issues dates back to Downs [31] and early agent-based opinion formation models as proposed by Abelson and Bernstein [1].

In this paper we study an agent-based model for opinion formation on a social network where the opinion of an agent depends both on its own intrinsic opinion and on the opinions of its network neighbors. One of the earliest influential models in this direction was defined by DeGroot [30]. In this model the opinion of an agent is iteratively updated to the weighted average of the opinions of its neighbors. Later, Friedkin and Johnsen [38] extended this by incorporating private opinions. Every agent has a private opinion which does not change and an expressed opinion that changes over time. The expressed opinion of an agent is determined as a function of the expressed opinions of its neighbors and its private opinion.

The main focus of our paper is the very influential model by Hegselmann and Krause [43] that adds an important feature: the set of neighbors that influence a given agent is no longer fixed, and the agents’ opinions and their respective sets of influencing neighbors co-evolve over time. At any point in time the set of influencing neighbors of an agent are all the neighbors in a given static social network with an opinion close to their own opinion. Hence, agents only adapt their opinions to neighboring agents having an opinion that is not too far away from their own opinion. Note that this adaption, in turn, might lead to a new set of influencing neighbors. In sociology this wide-spread behavior is known as homophily [46], which, for example, governs the formation of social networks and explains residential segregation. Co-evolutionary opinion formation helps to analyze and explain current phenomena like filter bubbles in the Internet [49] and social media echo chambers [21] that inhibit opinion exchange and amplify extreme views. The co-evolution of opinions and the sets of influencing neighbors is the key feature of a Hegselmann–Krause system (HKS). It is also the main reason why the analysis of the dynamic behavior of a HKS is highly non-trivial and challenging.

Researchers have investigated the convergence to stable states and the corresponding convergence speed in many variants of the Hegselmann–Krause model. The existing work can be categorized along two dimensions: complete or arbitrary social network and synchronous or asynchronous updates of the opinions. Synchronous opinion updates means that all agents update their opinion at the same time. In systems with asynchronous updates a single agent is selected uniformly at random and only this agent updates its opinion. While the main body of recent work focuses on HKSs assuming the complete graph as social network and the synchronous update rule, empirical simulations have also been performed with asynchronous updates on arbitrary social networks. Interestingly, convergence guarantees and convergence times for the latter case are, to the best of our knowledge, absent from the literature so far. This case is arguably the most realistic setting as social networks are typically sparse, i.e., non-complete, and social interactions and thereby opinion exchange usually happens in an uncoordinated asynchronous fashion.

In this paper we study the following Hegselmann–Krause system (HKS). We have n agents and their opinions are modeled by points in d-dimensional Euclidean space \(\mathbb {R}^d\), for some \(d\ge 1\). The agents are connected by a social network which does not change over time. At any point of time the set of influencing neighbors of an agent is the subset of its neighbors (in the social network) with an opinion of distance at most \(\varepsilon > 0\) from its own opinion. We assume that in each step a random agent is activated and its opinion is updated to the average of its current opinion and the opinion of all current influencing neighbors. Note in such an asynchronous HKS stable states in the sense that no agent will change its opinion might never be reached. This can be seen by a simple example with two nodes and one edge. Hence, we adopt a natural stability criterion defined by Bhattacharyya and Shiragur [13]. A HKS is in a \(\delta \)-stable state if and only if each edge in the influence network has length at most \(\delta \). For this scenario we prove that the convergence of the opinion dynamics is guaranteed. We give an upper bound on the expected convergence time ofwhere \(|E|\) is the cardinality of the edge set of the given social network. We demonstrate the tightness of our derived upper bound by providing analytical lower bounds as well as empirical simulations for several topologies of the underlying social network topologies. Note that for complete graphs as social network our bound of \({\text {O}}(n^3(n^2 + (\varepsilon /\delta )^2))\) improves the best previously known upper bound of \({\text {O}}(n^9 (\varepsilon /\delta )^2)\) [33].

In this section we prove Theorem 1 in three steps. Recall that for a HKS in d dimensions the opinion are represented by points in the d-dimensional Euclidean space. First, in Lemma 4 we show that for each HKS in d dimensions there exists a mapping to a suitable 1-dimensional HKS, such that the length of all edges does not increase, and the influence network (consisting of the active edges) as well as the length of the longest edge \(\lambda \) is preserved. We use this projection in the second step (see Lemma 6) where we only consider HKS in one dimension: We prove that \(\sum _{v \in V}(|\mathcal {N}_{t}(v)|\cdot \Vert m_{t}(v)\Vert _2) \ge 2\lambda \), where \(\mathcal {N}_{t}(v)\) is the set of neighbors in the influence network and \(m_{t}(v)\) is the available movement of the node. In the third step, we prove that the potential drop due to activating an agent v can be lower bounded by \((|\mathcal {N}_{t}(v)|+1) \cdot \Vert m_{t}(v)\Vert _2^2\) (see Lemma 7). Finally, in Lemma 8 we combine these three insights to bound the potential drop.

Let \(S = (G=(V,E),\varepsilon , x_{})\) be a state of some d-dimensional HKS with influence network \(I_{} = (V,\mathcal {E}_{})\). For some arbitrary edge \(e=\{u,w\} \in \mathcal {E}_{}\), we will project the state S to a state \({\bar{S}}_e\) of some 1-dimensional HKS. We define the projected state \({\bar{S}}_e\) along edge \(e=\{u,w\}\) with the help of the projection vectorwhere the order of u and w is chosen arbitrarily. We defineas follows. We project the position of each agent \(v \in V\) toFurthermore, in the graph \({\bar{G}}=(V,{\bar{E}}_{})\) of the projected system, we restrict the set of edges \({\bar{E}}\) to the ones, which are edges of the influence network in the original state, i.e., \({\bar{E}} = \mathcal {E}_{}\). For an agent \(v \in V\), we denote by \(\bar{\mathcal {N}}_{}(v)\) its influencing neighborhood, and by \({\bar{m}}_{}(v)\) its available movement in \({\bar{S}}_e\).

We now prove a lower bound on the total available movement of agents.

In the next step, we will prove a lower bound on the drop in the potential when updating any agent \(v \in V\).

We now have the tools to prove a lower bound on the expected potential drop in a single step.

The proof of Theorem 1 is a direct consequence of Lemma 8.

Our results in Theorem 1 directly improve the results from Etesami and Başar [33] even though they use a slightly different convergence criterium. In their paper, convergence is reached if the diameter of each connected component is bounded by \(\delta \), and they call this state a \(\delta \)-equilibrium. They bound the expected number of update steps to reach a \(\delta \)-equilibrium in the complete social network by \({\text {O}}(n^9(\varepsilon / \delta )^2)\).

Our result transfers to their notion of convergence as follows. Assume \(\delta \le \varepsilon /2\) and that the length of the longest edge is at most \(\delta .\) If the social network is the complete graph, each connected component in the influence network must be a complete sub-graph, see Lemma 10. Hence, the diameter of this connected component is also bounded by \(\delta \). Hence, if \(\delta \le \varepsilon /2\), a \(\delta \)-stable state must be in \(\delta \)-equilibrium as well. On the other hand, if \(\delta > \varepsilon /2\), the expected number of steps to reach a \(\varepsilon /2\)-stable state and hence a \(\delta \)-equilibrium is bounded by \({\text {O}}(n^5)\) by Theorem 1.

The next theorem shows that our bound on the potential drop per step is tight. Consequently, if we would like to improve the theorem, we have to choose a different potential function and/or consider multiple activations at once.

Note that this only proves that the drop in the first step is sufficiently small. The expected drop for the next step could increase after activating a node. Therefore, this theorem does not prove a lower bound for the convergence time. Instead, it shows that the analysis of the step-by-step drop is tight.

In the next section, we see an example of how to change the analysis to circumvent this bound.

In this section, we will prove two improved upper bounds, each for a more restricted set of graph classes. The first result holds when the social network is a complete graph, while the second holds when, in each step of the HKS, the influence network is the same as the social network.

To prove the result for HKSs with a social network, we prove the following characteristics of these systems.

We say an HKS is socially stable if, independently of the update steps, the influence network is always equal to the social network. For these systems, we can prove a better upper bound on the expected number of steps needed to reach a \(\delta \)-stable state. Examples of such graphs are the path, where all the nodes are positioned with equal distance of at most \(\varepsilon \), as well as the graph from Theorem 9 if the social network for the latter is reduced to the set of edges in \(\mathcal {E}_{0}\).

In this section, we complement our upper bounds on the expected convergence time with a lower bound. To the best of our knowledge, no lower bound for asynchronous updates is known so far. We prove that there exists a family of instances of HKS \((S_{0,4n})_{n \in \mathbb {N}}\) for which at least \(\Omega (\Phi (S_{0,4n}) n |E|)\) updates are needed to converge. In this family, we have \(|E| = \Theta (n^2)\) and \(\Phi (S_0) = \Theta (n)\) for \(\varepsilon =1\) and \(\delta < 1/2\). Note that the lower bound holds for any given update sequence. In particular, we also prove that there cannot be a deterministic algorithm that reaches a \(\delta \)-stable state faster than the proven lower bound.

Note that this lower bound is tight with regard to the considered family of instances and the parameter n since Theorem 1 states that in expectation at most \({\text {O}}((\Phi (S_{0,4n}) n |E|)/\delta ^2) = {\text {O}}(n^4)\) updates are needed, to reach a \(\delta \)-stable state.

We prove this lower bound in three steps. First, we prove that edges cannot be deactivated in the defined family of instances. Then, we upper bound the total available movement of certain nodes in the family by a modified process that is simpler to analyze.

Dumbbell Graph We define the following family of instances of HKS \((S_{0,4n})_{n \in \mathbb {N}} = (G_{4n} =(V,E),\varepsilon ,x_0))_{n \in \mathbb {N}}\): Let \(G_{4n}= (V,E)\) be the Dumbbell graph defined as follows. The \(|V| = 4n\) nodes of the graph are partitioned into the sets \(C_{\ell },C_{r}, P,\{\ell ,r\} \subseteq V\), such that \(|C_{\ell }| = |C_{r}| =n \), \(|P| = 2n-2\).

The set of edges are given such that \(C_{\ell }\cup \{\ell \}\) and \(C_{r}\cup \{r\}\) are cliques, \(P = \{p_1,\dots ,p_{2n-2}\}\) is a path such that \(\{p_i,p_{i+1}\} \in E\) for each \(i \in \{1,\dots ,2n-2\}\), as well as \(\{\ell ,p_1\},\{r,p_{2n-2}\} \in E\). In state \(S_{0,4n}\) the opinions of the agents that correspond to the nodes V are given as follows:Note that \(\Phi (S_{0,4n}) \in \Omega (n\varepsilon ^2)\) and \(|E| = n^2\), therefore \(\Omega (\Phi (S_0)n |E|/\delta ^2) = \Omega (n^4)\).

A necessary condition to terminate is that each edge on the path P has a length of at most \(\delta \). Since the distance between \(\ell \) and r is \((2n-1)\varepsilon \) at state \(S_{0,4n}\) and can be at most \((2n-1)\delta \) in the final state, one of the nodes \(\ell \) and r has to move by at least \((\varepsilon -\delta )(2n-1)/2\).

Modified Update Process In the following, we will lower-bound the number of required update steps to move \(\ell \) by this distance by defining a modified update process that moves \(\ell \) faster. However, the required number of steps in the modified process can be analyzed more easily. The opinions in the modified process are denoted by \(x'_t(v)\) for each \(v \in V\) and \(t \in \mathbb {N}\). Let \(S_t = \sum _{v \in C_{\ell } \cup \ell } x_{t}{(v)}/(n+1)\) and \(S'_t = \sum _{v \in C_{\ell } \cup \ell } {x'_{t}(v)}/(n+1)\) denote the mass center of the nodes \(C_{\ell } \cup {\ell }\) in the original and modified process respectively. Note that when activating an agent from \(C_{\ell }\) in each of the two processes, it will move to the corresponding center of mass.

Consider any update-sequence \((u_t)_{t \in \mathbb {N}_{{\ge } 0}}\) specifying for any \(t \in \mathbb {N}_{\ge 0}\) the node \(u_t\) that will be updated to generate the positions \(x_{t+1}\) from \(x_t\). Assume for simplicity of notation, that the nodes in \(C_{\ell }\) are numbered from one to n, i.e., \(C_{\ell } = \{v_1,\dots ,v_n\}\). Given \((u_t)_{t \in \mathbb {N}_{{\ge } 0}}\), the modified process is defined as follows:We prove Theorem 3 in two steps. First, we prove that, indeed, the modified process moves the node \(\ell \) faster than the original process. Afterward, we prove that the modified process needs at least \(\Omega (n^4)\) steps to move the clique by the distance \((\varepsilon - \delta )(2n-1)/2\).

To corroborate our theoretical findings, we performed agent-based simulations of asynchronous Hegselmann–Krause opinion dynamics in one dimension on two types of initial HKS states called Path and Dumbbell. They are defined as follows:We fixed \(\varepsilon = 100\) and \(\delta = 1\) in our simulations. For each initial HKS state on social networks with varying numbers of agents n, we simulated 100 independent runs of random activations needed to reach a \(\delta \)-stable state. The code for our simulator software and all necessary tools to reproduce our figures are available from our public GitHub repository.¹

We present our simulation results in Fig. 2.

There, the obtained number of activations divided by \(n^3\) is plotted via box plots that summarize the results for each configuration. Since for Path instances, the number of activations appears to be constant, we observe that we need \(\Theta (n^3)\) activations for Path instances. On the other hand, the number of activations seems to grow linearly in n for Dumbbell instances. This matches our proofs (upper and lower bound) that in \(\Theta (n^4)\) activations Dumbbell instances reach a \(\delta \)-stable for constant \(\varepsilon \) and \(\delta \).

Note that by construction, in the first step, the potential function of both instance types is bounded by \(\Phi (S_0) = \Theta (n \varepsilon ^2)\). Applying Theorem 1 yields an upper bound of \(\Phi (S_0)/(2\delta ^2/(n|E|)) = {\text {O}}(n \varepsilon ^2 / (2\delta ^2/(n|E|)))\), which yields an upper bound of \({\text {O}}(n^3 (\varepsilon /\delta )^2)\) for Path instances and \({\text {O}}(n^4 (\varepsilon /\delta )^2)\) for Dumbbell instances. Thus, the empirically observed lower bounds on the expected number of steps until convergence match our theoretical analysis for these two graph classes with respect to the dependence on the number of agents.

We highlight that our simulations not only confirm our theoretical results but also allow us to empirically pinpoint the constants hidden in the asymptotic analysis. For the simulations carried out on the path our simulation results indicate a constant of roughly 1.5, giving a total running time of roughly \(1.5 \cdot n^3\). For the dumbbell we get a running time of less than \(0.1 \cdot n^4\). We remark that in our theoretical analysis we did not attempt to optimize the constants. In fact, our result for the dumbbell graph (see the proof of Theorem 1) gives a bound of at most \(\log (100^2)/4 \cdot n^4 \approx 3.32 \cdot n^4\). Interestingly, the total running times are sharply concentrated around their mean. In fact, the plot in Fig. 2 actually shows box plots, but starting with a number of agents as small as only 40 the upper and lower whiskers become almost identical with no outliers detected.

In this paper, we present the first analysis of the convergence time of asynchronous Hegselmann–Krause opinion dynamics on arbitrary social networks. As our main result, we derive an upper bound of \({\text {O}}(n |E|\Phi (S_0)/\delta ^2 ) \le {\text {O}}(n |E|^2 \left( \varepsilon /\delta \right) ^2)\) expected random activations until a \(\delta \)-stable state is reached. This bound significantly improves over the state-of-the-art upper bound for the special case with a given complete social network. Moreover, our simulation results on one-dimensional instances with a path graph or a dumbbell graph as the social network indicate that our theoretical upper bound is tight for these instances. For the dumbbell graph, this is not only underlined by our simulations but also proven by presenting a matching lower bound with respect to the number of agents. This theoretical lower bound on the expected convergence time is the first proven non-trivial lower bound for asynchronous opinion updates. A challenging open problem is to improve this lower bound by finding a graph class with \(\Phi (S_0) \in \Omega (n^2\varepsilon ^2)\) with expected convergence time in \(\Omega (n^5)\).

It might be possible to prove better bounds for specific social network topologies. Regarding this, it would be interesting to consider social networks that have similar features to real-world social networks. Moreover, another direction for future work is to consider social networks with directed and possibly weighted edges. This would more closely mimic the structure of real-world neighborhood influences, allowing us to study asymmetric influence settings found in online social networks like Twitter. Another promising extension would be to incorporate the influence of external factors like publicity campaigns.