Opinion Dynamics with Local Interactions

1 Introduction

In everyday life, people form their opinions by exchanging information about almost everything. Information exchange is mostly local, in the sense that socially connected people (e.g., family, friends, colleagues) interact more often and affect each other's opinion more strongly, and dynamic, i.e., discussions go on until opinions converge. Due to their ubiquity and importance, opinion dynamics have been studied extensively for decades (see e.g., [Jackson, 2008]). The interest has been intensified recently by the rapid growth of online social networks (e.g., Facebook, Twitter), which provide the basis for a better understanding (and possibly for applications, see e.g., [Lever, 2010]) of opinion formation.

Over the years, several models of opinion formation have been proposed. The standard assumption is that people (or agents, in general) update their opinions to a weighted average of the opinions in their neighborhood. The updates proceed in synchronous parallel rounds, until opinions reach a stable state. A distinctive feature of the models is whether the agent neighborhoods are determined by a fixed social network, decoupled from the opinion formation process, or they reflect the affinity of the agent opinions and are updated during the process. Among the most influential models are those of [DeGroot, 1974] and [Friedkin and Johnsen, 1990], in the former case, and the bounded confidence model of [Hegselmann and Krause, 2002], in the latter. In this work, we investigate how practical restrictions on the locality of agent interaction and on the amount of information exchanged in each round affect the convergence properties of these models.

Related Work. The convergence properties of the FriedkinJohnsen (FJ) and the Hegselmann-Krause (HK) models have received considerable attention. Both are known to converge to a stable state relatively fast. In the FJ model, the stable state is unique [Friedkin and Johnsen, 1990] and approximately minimizes a certain notion of opinion disagreement in the network [Bindel et al., 2011]. Moreover, the convergence time is determined by the spectral radius of the adjacency matrix [Ghaderi and Srikant, 2014] (see also [Ferraioli et al., 2012; Yildiz et al., 2013] for discrete variants of the FJ model).

The HK model leads to opinion clustering, where the agents form groups with consensus in each group (see e.g., [Blondel et al., 2009]). The single-dimensional HK model is known to converge in at least ⌦(n2 ) and at most O(n3 ) rounds, where n is the number of agents [Bhattacharyya et al., 2013; Wedin and Hegarty, 2015]. [Lorenz, 2005] proved that generalizations of the HK model converge to a stable state under symmetric (and possibly time-dependent) local agent interactions. E.g., this implies convergence of the DeffuantWeisbuch (DW) model [Deffuant et al., 2001; Weisbuch et al., 2002], where two random agents meet and exchange opinions in each round. Moreover, there has been significant experimental work on the convergence properties of variants of the HK model and on confidence levels that are sufficient or necessary for consensus (see e.g., [Fortunato, 2005; Lorenz and Urbig, 2007]). Nevertheless, the convergence properties of heterogeneous and/or asymmetric variants of the HK model are far from being well understood. E.g., only recently, [Chazelle and Wang, 2015] proved that the HK model with partially stubborn agents converges.

Recent work has also studied the convergence properties of opinion dynamics that combine features of the DeGroot/FJ and the HK models and allow for coevolution of the opinions and the network under mutual influence between the agents. E.g., motivated by applications of opinion dynamics to expert opinion aggregation, [Carvalho and Larson, 2013] proved convergence to consensus for a generalization of DeGroot's model, where the influence between two agents is inversely proportional to the distance of their opinions. Subsequently, [Tsang and Larson, 2014] analyzed experimentally the convergence properties of a similar model where the agents are skeptical towards opinions far away from theirs. On the theoretical side, [Bhawalkar et al., 2013] investigated the existence and the efficiency of stable states for discrete and continuous coevolutionary opinion formation processes.

Motivation and Contribution. An important assumption in most of the previous work is that each agent exchanges opinions with all its neighbors in every round. In the HK model, in particular, determining each agent's neighborhood requires access to the opinions of all agents! This assumption is crucial for establishing existence of and convergence to a stable state in the FJ model [Ghaderi and Srikant, 2014] and fast convergence to opinion clustering in the HK model [Bhattacharyya et al., 2013]. However, this assumption is questionable in real life and in modern online social networks. Instead, it is far more reasonable to assume that agents act within a social network and update their opinions by consulting the opinions of a small (possibly random) subset of their neighbors. Motivated by this natural observation and by experimental work on opinion dynamics with communication regimes [Urbig and Lorenz, 2004], we introduce variants of the FJ and the HK model where information exchange in each round is limited (for both models) and local (for the HK model). We thoroughly investigate, both theoretically and experimentally, to which extent the convergence properties of the FJ and the HK models are affected by such practical considerations in the opinion exchange between the agents.

For the FJ model, we present a simple randomized protocol where each agent consults the opinion of one of her social neighbors in each round. We show that it converges in expectation to the stable state of the FJ model, albeit in exponential time. Our result indicates the importance of lively communication for the fast convergence of opinion dynamics.

Our main contribution concerns variants of the HK model with local agent interactions and limited (and possibly asymmetric) communication in each round. To decouple the two issues, we consider two variants of the HK model, one accompanied by a fixed social network and another with agent neighborhoods determined by random sampling in each round. In the former variant, the agents are embedded in an undirected network and exchange opinions only with their social neighbors in each round. Due to this restriction, the relative order of agent opinions is not preserved and standard convergence proofs for the HK model cannot be applied. Inspired by the notion of temporal network connectivity [Kempe et al., 2002] and using a recent result of [Chazelle, 2011], we prove convergence of this variant to a stable state, where opinion clustering occurs within social neighborhoods. Our approach provides a simpler and more versatile proof of the main results in [Hendrickx and Blondel, 2006; Lorenz, 2005]. We also extend this convergence result to multidimensional opinions. In the variant with random sampling, each agent consults the opinions of a small random subset of other agents, chosen independently in each round. Extending our temporal connectivity approach, we show that this variant converges to a stable state. Conceptually, HK with random sampling can be regarded as a significant generalization of the DWmodel. Technically, the DWmodel employs symmetric opinion exchange between random agent pairs. Hence, its convergence follows directly from the result above. On the other hand, HK with random sampling employs asymmetric opinion exchange (i.e., it may be that an agent i consults the opinion of an agent j, but j does not consult i's opinion). Thus, convergence proofs for symmetric variants of the HK model do not apply to HK with random sampling (e.g., condition (2) in [Lorenz, 2005, Theorem 2] is violated). Moreover, such asymmetric variants of the HK model either do not converge to a stable state, or if they converge, it is notoriously difficult to be proven (see e.g., [Bhawalkar et al., 2013]).

Our experimental findings indicate that if the size of random neighborhoods is roughly logn◁", where n is the number of agents and " is the agent confidence, the HK model with random sampling converges at comparable speed and to almost the same number of opinion clusters as the standard HK model. On the other hand, the HK model on random Gn↪p and power-law networks and on real-world social networks converges noticeably slower and to a larger number of clusters than the standard version. This behavior is amplified by small confidence values. The delay in convergence is justified by the existence of opinion clusters with relatively large diameter in the social network, while the cluster proliferation is justified by the existence of many small opinion clusters in relatively isolated parts of the network.

Due to the space limitations, some proofs and a significant part of our experimental justification are omitted.

2 Models of Opinion Dynamics

We consider a population of n agents, each maintaining an opinion xi(t) 2 [0↪ 1] in each time step t 2 N. We let ~x(t) 2 [0↪ 1]n denote the vector of agents' opinions at time t.

We use k~xk1 and k~xk1 to denote the 1-norm and the infinity-norm of a vector ~x, respectively. We say that a sequence ¶~x(t)♦t2N converges to a stable state ~x⇤ if for all γ > 0, there is a tγ, so that for all t ≥ tγ, k~x(t)-~x⇤ k1  γ. The Friedkin-Johnsen Model. We are given a weighted network G(V↪E) and the agents' initial opinions ~x(0). Each agent i corresponds to vertex i 2 V , has weight wii 2 (0↪ 1] for her initial opinion and weight wij 2 [0↪ 1) for the current opinion of each other agent j. We assume that wij = wji, for

all i↪ j, and that Pj2V wij = 1. At any round t ≥ 1, each agent i updates her opinion to

We let A denote the adjacency matrix of G with 0 on its main diagonal and let B be the diagonal matrix with Bii = wii, for all i. Then, (1) can be written in matrix form as:

Since wii > 0, A is a substochastic matrix and has spectral radius ⇢(A) < 1. Thus, (2) converges to a unique stable state ~x⇤ = (I -A)-1B~x(0), where I is the n⇥n identity matrix, in O( ln(n◁γ) 1-⇢(A) ) time steps [Ghaderi and Srikant, 2014].

The Hegselmann-Krause Model. We are given the agents' confidence " > 0 and their initial opinions ~x(0). At any round t ≥ 1, agent i computes her opinion-dependent neighborhood

and updates her opinion to the average of the opinions in Si(t↪ "), i.e., xi(t) = Pj2Si(t↪") xj(t - 1)◁♣Si(t↪ ")♣.

We consider two variants of the HK model with local agent interaction and limited information exchange. In the networkHK model, we are also given a undirected connected social network G(V↪E). The neighborhood of each agent i is now restricted to her social neighbors:

In the random-HK model, we let k be the size of the sample. At any round t ≥ 1, each agent i samples (from all agents, with replacement) a random subset Ki of k agents and lets

We require that ¶i↪ i♦ 2 E and i 2 Ki, for all i, so that i is always included in Si, in both variants. Then, agent i updates her opinion to the average of the opinions in Si(G↪ t↪ ") and Si(Ki↪ t↪ "), respectively.

To establish that the two variants converge, we use the following equation describing the agent opinions at round t ≥ 1:

Each Ar is an n ⇥ n matrix with 1◁♣Si♣ in position Ar(i↪ j), if j 2 Si, and 0, otherwise (Si is Si(G↪ t↪ ") for networkHK and Si(Ki↪ t↪ ") for random-HK). Ar corresponds to the adjacency matrix of an unweighted graph (undirected for network-HK and directed for random-HK), but with normalized entries so that Ar is stochastic.

In the convergence proofs, we use the coefficient of ergodicity ⌧(A) = 1 2 maxi↪j kAT (~ei -~ej)k1 of a stochastic square matrix A, where AT is A's transpose and ~ei is the vector with 1 in coordinate i and 0 elsewhere (see e.g., [Seneta, 1979]). We know that for any stochastic matrices A, B, (i) ⌧ (A)  1, (ii) ⌧(AB)  ⌧(A)⌧(B), and (iii) ⌧(A) = 0 iff rank(A) = 1. Moreover, if A has strictly positive elements only, ⌧(A) < 1.

We also let Pr[E] denote the probability of an event E and E[X] denote the expectation of a random variable X.

3 The FJModel with Limited Information

A natural question about the FJ model is whether we can simulate the opinion formation process by simple protocols where agents consult the opinions of a small subset of their neighbors in each round. To this end, we present such the Limited Information Protocol, or LIP-FJ, in brief, and discuss its convergence properties.

Let (G(V↪ E)↪ ~x(0)) be an instance of the FJ model and let λ(t) 2 (0↪ 1). In LIP-FJ, at any round t ≥ 1, each agent i selects one index j 2 V with probability wij and sets si(t) = xj(t - 1), if j 6= i, and si(t) = xi(0), if j = i. Then, agent i updates her opinion to xi(t) = λ(t)xi(t-1)+(1-λ(t))si(t).

We observe that (i) for any fixed instance and any fixed round t, the set ⌦t of possible values of the random variable ~x(t) is finite; and that (ii) for any possible value ~y of ~x(t-1),

For brevity, let pt-1(~y) ⌘ Pr[~x(t-1) = ~y] be the probability that the opinions at round t - 1 are as in ~y. Then, using (i) and (ii), we obtain that for any fixed t ≥ 1,

Using linearity of expectation, we conclude that any t ≥ 1,

Then, using induction on t and standard properties of the matrix infinity norm ⌫(A) ⌘ kAk1 2 (0↪ 1), we show that for an appropriate choice of λ(t), LIP-FJ converges in expectation to the stable state ~x⇤ = (I-A)-1B~x(0) of the FJ model.

Theorem 1. For any instance (G(V↪ E)↪ ~x(0)) and any round t ≥ 1, the opinions maintained by LIP-FJ satisfy

where ~x⇤ is the stable state of the FJ model.

If λ(t) = t t+1 , then kE[~x(t)] - ~x⇤ k1  e1-⌫(A) ◁t1-⌫(A) , by Theorem 1, and LIP-FJ converges in expectation in time exponential in 1◁(1 - ⌫(A)). The experiments indicate that for such values of λ(t), LIP-FJ indeed converges asymptotically to ~x at a very slow rate. For larger values of λ(t), e.g., for λ(t) = 1 - 1 t2 , Ptq=1 (1 - λ(q)) converges to a constant value. Therefore, the expected distance to ~x⇤ stops decreasing after a finite number of rounds. If we set λ(t) to some constant, aiming at improving the convergence time, the experiments indicate that LIP-FJ does not converge asymptotically to ~x⇤ , due to the high variance of the stochastic process.

4 Convergence of Network-HK

We proceed to show that the HK model on social networks converges to a stable state. We consider any fixed instance (G(V↪E)↪ "↪ ~x(0)) of the network-HK model. As in Section 2, we let At be the stochastic matrix encoding the agent neighborhoods in round t and let Gt be the corresponding undirected network. Then, ~x(t) = At~x(t-1) for each t ≥ 1.

Our approach is motivated by temporal graph connectivity. Specifically, we say that a set of agents S ✓ V is weakly connected if for any non-empty S0 ⇢ S and any t0 2 N, there is a round t ≥ t0 so that Gt includes at least one edge connecting an agent in S0 to some agent in S ∩ S0 (we highlight that the sequence ¶Gt♦t≥0 and weak connectivity depend on the opinion formation process). Intuitively, all agents in a weakly connected set influence each other with their opinions.

Lemma 1. Let (G(V↪ E)↪ "↪ ~x(0)) be an instance of networkHK, where the opinion dynamics keep V weakly connected. Then, all agents converge to a single opinion x⇤ .

Proof. To prove the lemma, it suffices to show that there is a round t0 so that the coefficient of ergodicity of the matrix C = At0 At0-1 · · ·A1 is ⌧(C)  "◁2. Given this, we have that ~x(t0) = C~x(0), by (3), and that for all agents i and j,

where Ci is the i-th row of matrix C. Since at t0 all opinions are within distance ", in any round t > t0, all agents take the average of all opinions in their social neighborhood (including their opinion). Hence, after round t0, we have essentially an instance of DeGroot's model on the undirected connected network G (enhanced with self-loops). Since G (with selfloops) defines an irreducible and aperiodic process, by [Jackson, 2008, Cor. 8.3.1], all agents converge to a single opinion.

So, we need to show that for any δ > 0, there is a t0 such that ⌧(At0 At0-1 · · ·A1)  δ. To this end, we first show that since V remains weakly connected, for any round t, there is a round `(t), such that the matrix C `(t) t = A`(t)A`(t)-1 · · ·At has all its elements positive, and thus, ⌧(C `(t) t ) < 1.

We recall that any matrix At has only positive diagonal elements. Moreover, an element C `(t) t (i↪ j) is positive iff there is a (time-respecting) walk (i↪ i1↪ ▷ ▷ ▷ ↪ im-1↪ j) from agent i to agent j such that (i) the first edge ¶i↪ i1♦ exists in some network Gt0 with t0 ≥ t, (ii) for each index q, 1  q  m- 1, if the edge ¶iq-1↪ iq♦ exists in some Gt0 , then the edge ¶iq↪ iq+1♦ exists in some network Gt00 with t00 > t0 , and (iii) the last edge ¶im-1↪ j♦ exists in some Gt0 with t0  `(t) (since any matrix At has positive diagonal elements, the walk can wait at each intermediate agent until the next edge appears). The existence of such a walk between any pair of agents in V follows from the definition of weak connectivity.

Then, [Chazelle, 2011, Theorem 2.5] implies that there is a fixed ⌘ > 0, so that for any round t and the corresponding round `(t), ⌧(A`(t) · · ·At)  1 - ⌘. Now, we can concatenate an appropriately large number of non-overlapping sequences At↪ ▷ ▷ ▷ ↪A`(t) and obtain a sequence A1↪ ▷ ▷ ▷ ↪At0 with ⌧(At0 · · · A1)  δ, for any δ > 0.

If V is not weakly connected, we can show that it admits a unique partition into weakly connected components. Applying Lemma 1, we get that the agents in each component converge to a single opinion. Thus, we obtain the following:

Theorem 2. Network-HK converges to a stable state.

Extension to d-Dimensional Opinions. We can generalize Theorem 2 to the case where each agent i maintains a ddimensional opinion ~xi(t) 2 [0↪ 1]d by the d-dimensional HK model (see e.g., [Bhattacharyya et al., 2013]) on a social network G. The proof is essentially identical, with the only difference that in (4), we need that ⌧(C)  "◁(2pd).

5 Convergence of Random-HK

Next, we show that the random-HK model, where each agent contacts only k random agents in each round, converges to a stable state. Let (k↪ "↪ ~x(0)) be any fixed instance. As before, we let At be the stochastic matrix that encodes the agent neighborhoods in round t and let Gt be the corresponding network. Now At is a random matrix and Gt is a random directed network. Again, ~x(t) = At~x(t - 1), for any t ≥ 1.

Since the process is now stochastic, we prove that each agent converges to a specific opinion with probability arbitrarily close to 1.

We first prove the equivalent of Lemma 1, but now with the notion of "-connectivity. For any two disjoint sets of agents S1↪ S2, we let dt (S1↪ S2) = mini2S1↪j2S2 ♣xi(t) - xj(t)♣ be their distance at round t. We say that a set of agents S is "-connected at round t, if for any non-empty S0 ⇢ S, dt (S0 ↪ S ∩ S0 )  ". A set of agents S breaks at round t if S is "-connected at round t - 1 and is not "-connected at round t. We note that once S0 and S∩S0 break, they behave as independent subinstances in the future. We also say that agents i and j are ("↪ t)-connected if there is a "path" (i↪ i1↪ ▷ ▷ ▷ ↪ ik-1↪ j) so that for each "step" q, ♣xq(t) - xq+1(t)♣  ". The diameter at some time step t, denoted diam(t), is the maximum distance ♣xi(t)-xj(t)♣ overall ("↪ t)-connected pairs of agents i↪ j. We observe that if at time step t, diam(t)  ", then no break occurs in the future. We also let Γl be the set of all opinion vectors ~y such that for all rounds t ≥ 0, Pr[at most l breaks occur in ¶0↪ t♦ ♣ ~x(0) = ~y] = 1. Namely, Γl consists of all vectors ~y such that if the initial opinions are ~y, then no matter the random choices, at most l breaks occur. E.g., all vectors with a single opinion belong to Γ0. We next show that in a set that remains "-connected during the (random) opinion formation process, all agents converge to a single opinion with probability that tends to 1.

Lemma 2. Let (k↪ "↪ ~x(0)) be an instance of the random-HK model with ~x(0) 2 Γ0. For any γ↪ δ > 0, there is a round t0 such that

Proof sketch. Without loss of generality, we assume that there exists a single "-connected component (otherwise, the lemma applies to each "-connected component separately). Since ~x(0) 2 Γ0 no break occurs and the agents are ("↪ t)- connected for all t and all random choices.

Let p = 1 - (1 - 1◁n)k be the probability that an agent j is not in the sample set of agent i in a round t. For any round `, we denote C` = A`+2n2 ◁p · · ·A` and D` = A`-1 · · ·A1. The important step is to show that there is some fixed ⌘ > 0 such that for any fixed value of D`, E[⌧ (C`)♣D`]  1 - ⌘◁2.

For any round t0 ≥ `, pos(t0 ) (resp. posi(t0 )) denotes the number of positive entries in (resp. the i-th row of) matrix At0 · · ·A`. We have 0  pos(t0 )  n2 and pos(t0 + 1) ≥ pos(t0 ). As long as pos(t0 ) < n2 , there is some agent i with posi(t0 ) < n. As in the proof of Lemma 1, posi(t0 ) is the number of agents reachable from i, between rounds ` and t0 , by time-respecting walks. Since V is "-connected and no break occurs, if posi(t0 ) < n, there is at least one new agent reachable from i in round t0 + 1, with probability at least p. Hence, for any round t0 with pos(t0 ) < n2 , pos(t0 + 1) > pos(t0 ) with probability at least p, and the expected number of rounds before it becomes pos(t0 ) = n2 for the first time is at most n2 ◁p. By Markov's inequality, Pr[pos(` + 2n2 ◁p) < n2 ♣D`]  1◁2. Moreover, since pos(` + 2n2 ◁p) = n2 implies that ⌧(C`) < 1,

As in the proof of Lemma 1, since C` is the product of 2n2 ◁p matrices, there exists a fixed fractional ⌘ > 0 such that if ⌧(C`) < 1, then ⌧(C`)  1 - ⌘. Thus, we obtain that for any fixed value of D`, E[⌧ (C`)♣D`]  1 - ⌘◁2.

Now, we can work as in the proof of Lemma 1. Taking an appropriatelly large number of rounds, we obtain a t0 and a matrix C = At0 · · · A1 such that ⌧(C)  γ◁2 with probability at least 1-δ. Then, the Lemma follows from the properties of the coefficient of ergodicity, similarly to (4).

We proceed to show that the random-HK model converges asymptotically, with probability that tends to 1. We recall that if there exists a round t⇤ with diam(t⇤ )  ", then ~x(t⇤ ) 2 Γ0 and Lemma 2 again implies convergence in each "-connected component separately. The following lemma establishes the existence of such a round t⇤ with probability that tends to 1.

Lemma 3. Let (k↪ "↪ ~x(0)) be any instance of the random-HK model. For any δ > 0 there is a round t⇤ such that

Proof sketch. Intuitively, if ~x(0) 2 Γl, there are constants p and t0 such that Pr[~x(t0) 2 Γl-1] ≥ p. Moreover, there is a constant m such that Pr[~x(mt0) 2 Γ0] ⇡ 1, i.e., with almost certainty, all possible breaks have occurred by round mt0. Then, the proof follows easily from Lemma 2.

In the following, we let t0 be the number of rounds in Lemma 2 for γ = ". Namely, t0 is such that if ~x(0) 2 Γ0 then Pr[diam(t0)  "] ≥ 1 - δ. For brevity, we let p = 1◁nknt0 and let P(~y↪m) = Pr[diam((m + 1)t0)  " ♣ ~x(0) = ~y]. Namely, P(~y↪m) is the probability that the diameter is at most " after (m+ 1)t0 rounds, given that the initial opinion vector is ~y.

At first, we consider the case where ~x(0) 2 Γ1 and prove inductively that

occurs in ¶0↪ t0♦ for all random choices. Thus, ~x(0) satisfies the hypothesis of Lemma 2 and P(~x(0)↪ 0) ≥ 1 - δ. As a result, P (~x(0)↪ m + 1) ≥ 1 - δ.

We can verify (5) is true for m = 1. We inductively assume that m satisfies (5) and consider the following cases for m+1. Pr[~x(t0) 2 Γ0] = 0 ▷ Therefore, since ~x(0) 2 Γ1, no break

Pr[~x(t0) 2 Γ0] > 0 ▷ There is an opinion vector ~y 2 Γ0 such that Pr[~x(t0) = ~y] ≥ p. Since ~x(0) 2 Γ1, if ~x(t0) 6= ~y, then ~x(t0) 2 Γ1. Hence, we obtain that:

Now we extend the proof to the case where ~x(0) 2 Γl, for any 2  l  n - 1. We recursively define the functions fl(m) = pfl-1(m - 1) + (1 - p)fl(m - 1), for all m↪ l ≥ 2, with f1(m) = (1 - δ)(1 - (1 - p)m). Using induction and the same arguments as above, we can show that if ~x(0) 2 Γl, then P(~x(0)↪m) ≥ (1 - δ)fl(m). We observe that limm!1f1(m) = 1. Then, by the definition of fl, we can show inductively that limm!1fn-1(m) = 1. Since at most n - 1 breaks can occur, we conclude that P (~x(0)↪ m) ≥ (1 - δ)fn-1(m).

6 Experimental Evaluation

We performed computer simulations so as to obtain a better understanding of the convergence properties and the number of clusters of network-HK and random-HK. We sketch the main conclusions of the experimental evaluation, which confirm and enhance our results in sections 4 and 5.

The Random-HK Model. We simulate the random-HK and the standard HK models for 625 agents and 21 values of " 2 [▷01↪ ▷45], repeating each run for 100 different initial opinion vectors to account for the randomness in local interaction. Opinions are selected uniformly at random from [0↪ 1] in all our simulations. We choose k = min(n◁10↪ log n◁") to ensure that with high probability every agent has some neighbors in each cluster.

Figure 1 shows the average convergence time for different values of ". The curve for random-HK is very similar to that for the standard HK model. Naturally, random-HK results in larger convergence times, as every agent has access to less information. The peak at ▷25 is where we move from two clusters to one cluster in the stable state.

The number of opinion clusters is an important property of the HK model. We calculate it by sorting the final opinion values and separating the groups which differ more than " from each other. Figure 2 shows the average number of clusters created by each model as " changes. At a first glance, the limited amount of information in random-HK does not hinder its ability to simulate the standard HK model effectively regarding the number of clusters. The small difference in the number of clusters is rather insignificant, especially if one considers the rather unstable behavior of the HK model. Specifically, even small perturbations during the opinion formation can cause noticeable differences in the final clustering of the agents. To demonstrate this, we first simulate the standard HK model, and then, we repeat the process on the same initial opinion vector, but with some small random perturbations for few randomly selected rounds. The perturbations consists of increasing " to 2" for the selected round. Our simulations show that for "  0▷25, these small perturbations may significantly change the resulting number of clusters.

The Network-HK Model. We start with the convergence time for different types of networks. We mostly focus on random Gn↪p networks (see e.g., [Bollobas, 2001]) and Barab´asiAlbert (preferential attachment) graphs [Barab´asi and Albert, 1999]. We select 64 different values of n 2 [256↪ 1024] and create 10 relatively sparse networks for each value. We run the network-HK and the standard HK models on each of these networks for 10 values of " 2 [▷001↪ ▷4].

The resulting convergence times are shown in Figure 3. For both network types, the variance drops as " increases. This happens because for large values of ", the agents can more easily find other agents at opinion-distance at most ", regardless of the network structure. As a result, the opinion formation process behaves more uniformly. The lower variance in Barab´asi-Albert networks (compared to Gn↪p networks) is mostly due to their smaller diameter. Our simulations show that the convergence time depends more on the value of ", less on the network type, and not so much on the number of agents n. A notable exception is chain networks where, for large values of ", the convergence time heavily depends on n.

As for the number of clusters, we repeat the simulations that we performed for the random-HK model. We now create random Gn↪p networks with p 2 [logn◁n↪ ▷1]. To count the clusters at the stable state, we delete every edge that connects agents at opinion-distance more than " and count the number of connected components. The results are depicted in Figure 4. The absolute difference in the number of clusters is now quite large. It is larger than 300, for " = ▷01, and slowly drops to 0, when both models reach consensus. We observe a similar behavior for sparse Barab´asi-Albert networks. To explain the cluster proliferation, we run both models for " = ▷15 and a random G1000↪▷05 network. Figure 5 shows that the large number of clusters for network-HK is due to the fact that many agents (and especially agents with extreme opinions) fail to find any neighbors at opinion-distance at most ", which leads to many singleton clusters.

Finally, we test the network-HK model on the Facebook "circles" network [Leskovec, 2012], with 4039 nodes and 88234 edges (see Figure 6a). Compared to the computergenerated networks before, this instance takes much longer to converge. To obtain a better understanding of the increased convergence time, we draw, at round t = 40, the agents who will eventually form a cluster with opinions in [▷2↪ ▷4]. In Figure 6b, we see that the future cluster consists of tightly bound communities which communicate with each other through a small number of edges. As a result, information exchange is slow, which crucially affects the convergence time.

Acknowledgments: Stratis Skoulakis is partially supported by a scholarship from the Onassis Foundation.

(a) Opinion formation.

(b) subgraph of the network.

Figure 6: Network-HK on the Facebook network.