# When social networks polarize: On the number of clusters in the Hegselmann-Krause model

Wout de Vos, Michel Grabisch, Agnieszka Rusinowska

<figure><img src="image_1.png" /></figure>

## To cite this version:

Wout de Vos, Michel Grabisch, Agnieszka Rusinowska. When social networks polarize: On the number of clusters in the Hegselmann-Krause model. 2025. halshs-05274032

HAL Id: halshs-05274032

https://shs.hal.science/halshs-05274032v1

Submitted on 23 Sep 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>
CES

Centre d'Économie de la Sorbonne
UMR 8174

When social networks polarize: On the number of clusters
in the Hegselmann-Krause model

Wout DE VOS, Michel GRABISCH, Agnieszka RUSINOWSKA

2025.18
When social networks polarize:
On the number of clusters in the Hegselmann-Krause model

WOUT DE VOS *†
MICHEL GRABISCH ‡§
AGNIESZKA RUSINOWSKA ‡§¶

July 3, 2025

Abstract

In the present paper, we study opinion dynamics in a social network, where individuals only listen to those with opinion not farther away than a given threshold from their own opinion (known as bounded confidence models, proposed by Hegselmann and Krause). It is well known that in bounded confidence models consensus does not always exist, and that agents split in clusters (polarization), with convergence to consensus in each cluster. We are precisely interested in the effect of bounded confidence on polarization in the network. Our main focus concerns the formation of clusters and their number, as well as its non-monotonicity with respect to the value of the threshold. First, a framework with a finite number of agents is considered. We study analytically disintegration of various types of opinion chains (clusters), and investigate by simulation the likelihood of chains of a certain length and their disintegration. Next, we analyze in a formal way the formation of clusters in a model with a continuum of agents. Finally, we examine the (non-)monotonicity of the number of clusters with respect to the threshold for a given initial vector of opinions and in expectation.

**Keywords:** opinion dynamics - polarization - clusters - bounded confidence - non-monotonicity - network formation - continuous opinion

**JEL Classification:** D85 - D72

# 1 Introduction

Today's world is characterized by polarization. When groups of people communicate, new links form and old bonds sever. Often this is related to the distance between individuals' opinions. People with similar opinions will listen to each other, but then ignore them when they drift too far apart. This process of forming and breaking links in social networks occurs at many levels, e.g., on the world's stage of international diplomacy, in national politics in parliaments and public debate, within and between companies, as well as in informal ways in families and friend groups.

Formally, polarization is usually defined as the event when a group of agents transitions from a state where there is communication among its members to a state where the group has disintegrated into two or more groups that no longer communicate with each other. In this paper, we are interested in polarization as a consequence of individuals' opinions having become too dissimilar. In the existing

<footnote>*CentER and Department of Econometrics and Operations Research, Tilburg University, P.O. Box 90153, 5000 LE Tilburg, The Netherlands.</footnote>

<footnote>†Corresponding author: w.m.devos@tilburguniversity.edu.</footnote>

<footnote>‡Centre d'Economie de la Sorbonne, University Paris 1 Panthéon Sorbonne, Paris, France</footnote>

<footnote>§Paris School of Economics</footnote>

<footnote>¶CNRS – National Centre for Scientific Research</footnote>
literature, it is still not sufficiently well understood when such a polarization event occurs and when it
does not.

A well-established model of opinion dynamics that is very well suited for studying polarization is the Hegselmann-Krause model (Krause (2000); Hegselmann and Krause (2002)), abbreviated here as the *H-K dynamics*; see also Dittmer (2001) and closely related settings in Deffuant et al. (2000); Weisbuch et al. (2000). In the *bounded confidence models*, individuals hold their continuous opinion, which takes value in a closed real interval like e.g. [0, 1], and listen to or trust only those with opinion being not too far from their own opinion. There is a certain exogenously given range of confidence and every individual updates his opinion by taking the average of the opinions of his trusted individuals, i.e., those with opinions lying within his confidence interval. The framework is a simple model of homophily in the dynamics of opinion (Abelson (1964)) and can be seen as a French-DeGroot model (DeGroot (1974); French (1956)) with time varying interaction matrix; for various results concerning time varying models; see e.g., Seneta (2006); Blondel et al. (2005); Lorenz (2005); Bullo (2019).

Various properties of the Hegselmann-Krause model have been studied for last twenty years. Questions and issues of interest in this setting concern, in particular, the convergence analysis, a non-monotonic dependence between the range of confidence, the number of clusters and the convergence time; see e.g., Dittmer (2001); Lorenz (2006); Blondel et al. (2007); Bhattacharyya et al. (2013); Etesami and Basar (2015); Wang et al. (2017). Also, there exist different extensions of the H-K model, in particular, versions with multidimensional opinions (e.g., Nedić and Touri (2012); Etesami et al. (2013)), continuous-time bounded confidence models (e.g., Blondel et al. (2010); Yang et al. (2014)), a model with truth seekers (Hegselmann and Krause (2006, 2015)), among others. Parravano et al. (2016) study a framework coupling the dynamics of two models: structural balance and bounded confidence. More precisely, the authors investigate a model where agents form opinions under bounded confidence (Hegselmann and Krause (2002)), but only consider the opinions of their friends. Grabisch et al. (2023) propose a model of the joint evolution of opinions and social relationships with social influence decaying over time and the dynamics based on bounded confidence. They retrieve the model of Hegselmann and Krause (2002) as a particular case of their framework. For a most recent extensive survey on bounded confidence opinion dynamics models, we can refer to Bernardo et al. (2024).

Among numerous works that analyze polarization in networks by using a variety of approaches dif-
ferent from Hegselmann and Krause (2002), several of them propose frameworks that share quite some
similarities with the bounded confidence model. To give a couple of examples, Pan (2010) considers
social learning where agents update both their opinion by taking the weighted average of others’ current
opinions and the influence weights that they assign on the agents. Using the concept of distance, the
author assumes that an agent places more weights on those who share similar opinions, but differently
from Hegselmann and Krause (2002) and Weisbuch et al. (2002), the weights remain positive even for
agents with very distant opinions. Mavridis and Tsakas (2021) investigate two dynamic processes of
opinion formation with bounded confidence, based on a dynamic framework of multidimensional opinion
formation of Deffuant et al. (2000). They model communication through bonding associations (bonding
similar individuals together) and bridging associations (bridging the gap among different individuals),
respectively. Genicot (2022) considers an agent’s tolerance, i.e., the largest deviation from his identity
that the agent can accept in a friend, and studies the limits of compromise. In equilibrium, an agent’s
ability to compromise is bounded by the difference between his tolerance level and the lowest tolerance
level in society. Azzimonti and Fernandes (2023) study the impact of the structure of social media net-
works and the presence of fake news on misinformation and polarization in a society. The authors extend
their baseline opinion formation model with agents placing equal weight on friends in every period, to
a process with a threshold rule (bounded confidence model) of Krause (2000); Hegselmann and Krause
(2002); Deffuant et al. (2000). Bolletta and Paolo (2025) develop a model of network formation and
opinion dynamics with an endogenous rule of bounded confidence, where strategic individuals can sever
links with others having similar opinions to join those with more cohesive opinions. The authors compare
their model with Hegselmann and Krause (2002) and show differences between the two frameworks.

We return to the original Hegselmann-Krause model (Krause (2000); Hegselmann and Krause (2002)) and some of its features. Concerning the relation between the number of clusters and the range of
confidence $\sigma$, intuitively, one could expect less clusters with larger values of $\sigma$. Mysteriously, this is not always the case. This form of non-monotonicity has been identified in the literature; see e.g., survey papers of Proskurnikov and Tempo (2018); Grabisch and Rusinowska (2020). Explaining non-monotonicity necessarily requires deeper understanding of disintegration of $\sigma$-chains.

In this paper, we provide new insights on the disintegration of $\sigma$-chains in the H-K dynamics. We do so in two independent parts. First, we provide a bottom-up approach for a finite number of players, i.e., for the case with atomic agents. We start with a comprehensive analysis of $\sigma$-chains of small sizes, i.e., containing at most 5 agents, and provide necessary and sufficient condition for disintegration with 5 agents. Then we extend the analysis to a generic $\sigma$-chain of $n$ agents and provide necessary and sufficient link-breaking conditions.

In the first part, spacings vectors play a crucial role, as they turn out to be an efficient and insightful language for analyzing the H-K dynamics. This is not a novel concept, as it has been well-studied in the field of order statistics, where the stochastic properties of spacings between random variables are analyzed. Here, spacings are taken as deterministic values.

In the second part, we analyze the disintegration of $\sigma$-chains for the case of continuum of agents, i.e., in the non-atomic setting. More precisely, we assume that the population is given by a continuum of infinitely many agents uniformly distributed on $[0, 1]$. The analysis depends on the value of $\sigma$. We show that if $\sigma \ge 1/2$, then at step 2 the process already converges to a single cluster positioned at $1/2$. Moreover, if $\sigma \le 0.3253$, the process converges at step 3 to a single cluster at $1/2$. Lower values of $\sigma$ lead to polarization, however further analysis becomes difficult.

In the last part of the paper, we revisit non-monotonicity of the number of clusters with respect to the value of the threshold. Using the insights above, we argue that non-monotonicity can only occur in networks of at least 5 agents. Also, using simulation, we show that monotonicity does hold in expectation.

This work does not comprehensively “solve” the phenomena of disintegration of $\sigma$-chains, and therefore also not of non-monotonicity. However, it does put some substantial steps in better understanding of the H-K model and the cluster formation within this opinion dynamics setting.

The paper is structured as follows. Section 2 presents the H-K dynamics, recalls several existing results and defines spacings vectors. In Section 3, we analyze the disintegration of $\sigma$-chains for a finite number of agents. The disintegration of a population with a continuum of agents is studied in Section 4. In Section 5, we analyze (non-)monotonicity of the number of clusters, which naturally relies on our insights on disintegration presented in the previous sections. Section 6 proposes concluding remarks. All proofs of our results and some examples are shown in Appendix A. Additional computations are placed in Appendix B.

# 2 The Hegselmann-Krause model

## 2.1 The model with a finite number of agents

First, let us recall the Hegselmann-Krause model of opinion dynamics (Krause (2000); Hegselmann and Krause (2002)). We consider a group of $n$ agents, given by $N = \{1, 2, ..., n\}$, whose opinions are traced throughout a discrete time horizon $t \in \{0, 1, 2, 3, ...\}$. At any time step $t$, each agent $i \in N$ holds an opinion $x_i(t) \in [0, 1]$, and all opinions combined at time $t$ constitute the opinion vector $x(t) = (x_1(t), ..., x_n(t))$. The initial opinion vector $x(0)$ is assumed to be exogenously given. Opinion updating occurs through a fixed range of confidence $\sigma > 0$. At time $t$, every agent trusts only those fellow agents whose opinion is no further than $\sigma$ from his own. Specifically, the group of trusted individuals by agent $i$ at time $t$ is given by

$$I_i(t) = \{j \in N : x_j(t) \in [x_i - \sigma, x_i + \sigma]\}.$$
Note that, in particular, $i \in I_i(t)$, i.e., every agent trusts himself. Then, the next opinion of agent $i \in N$ at time $t+1$ is given by the average opinion of his group of trusted individuals at time $t$, i.e.,

$$x_i(t+1) = \frac{1}{|I_i(t)|} \sum_{j \in I_i(t)} x_j(t).$$

Now we recall several known results about the H-K dynamics. First, the updating procedure preserves order.

**Lemma 2.1.** [Lemma 8 from Proskurnikov and Tempo (2018)] Consider a group of $n$ agents and let $x(0) \in [0, 1]^n$ be an initial opinion vector. Assume that the initial opinions are labelled such that $x_1(0) \le x_2(0) \le \dots \le x_n(0)$. Then, for all $t \ge 1$, it also holds that $x_1(t) \le x_2(t) \le \dots \le x_n(t)$.

Inspired by the latter result, without loss of generality we assume throughout this paper that the initial opinions are such that $x_1(0) \le x_2(0) \le \dots \le x_n(0)$.

Next, we recall the definition of the (maximal) $\sigma$-chain (Dittmer (2001)).

**Definition 2.1.** Let $n \in \mathbb{N}$ and $\sigma \ge 0$.

(i) An opinion vector $x \in [0, 1]^n$ is a $\sigma$-chain of length $n$ if $x_{i+1} - x_i \le \sigma$ for all $i \in \{1, \dots, n-1\}$.

(ii) A $\sigma$-chain is maximal if it is not contained by any longer $\sigma$-chain.

**Lemma 2.2.** [Lemma 9 from Proskurnikov and Tempo (2018)] Two maximal $\sigma$-chains can never merge.

It is also known that the diameter $x_m(k) - x_i(k)$ of a maximal $\sigma$-chain $(x_i(k), \dots, x_m(k))$ is nonincreasing. Moreover, the following results hold true.

**Lemma 2.3.** [Lemma 11 from Proskurnikov and Tempo (2018)] During two consecutive steps $k$ and $k+1$, any maximal $\sigma$-chain either collapses into a singleton, splits into several maximal $\sigma$-chains or reduces in diameter by at least $\sigma/n^2$.

The H-K model always converges to a fixed point in a finite number of steps, as first proven in Dittmer (2001) and recalled below:

**Lemma 2.4.** [Theorem 7 from Proskurnikov and Tempo (2018)] For any $x(0)$, the H-K model converges to a vector $\bar{x}$ in a finite number of steps, with the property that for any two agents $i$ and $j$, either $\bar{x}_i = \bar{x}_j$ (consensus) or $|\bar{x}_i - \bar{x}_j| > \sigma$ (distrust).

## 2.2 Spacings vectors

The language of spacing vectors turns out to be useful for clear and efficient speaking about the H-K dynamics. This concept is not novel; see e.g., Pinelis (2019) who uses both the terms “spacings” and “gaps”.

To every (sorted) opinion vector $x(t) \in [0, 1]^n$ we associate a (unique) spacings vector of length $(n-1)$, given by

$$w(t) = (x_2(t) - x_1(t), x_3(t) - x_2(t), \dots, x_n(t) - x_{n-1}(t)).$$

In a setting of $n$ agents, the set of all spacing vectors is given by

$$W_{n-1} = \left\{ w \in [0, 1]^{n-1} \mid \sum_{i=1}^{n-1} w_i \le 1 \right\}.$$

To illustrate the model, the following example provides an instance of the H-K dynamics in graph representation, with all steps until convergence. For every period $t$, the graph corresponding to opinion vector $x(t)$ is given, where each node $i$ corresponds to an agent $i$ and is labelled with opinion $x_i(t)$. An edge $\{i, j\}$ exists in period $t$ between agents $i$ and $j$ if and only if $|x_i(t) - x_j(t)| \le \sigma$, and its edge weight is the corresponding spacing $|x_i(t) - x_j(t)|$.
**Example 2.1.** Consider $n = 5$ agents and the initial opinion vector $x(0) = (0.19, 0.25, 0.40, 0.57, 0.77)$. Below we illustrate by graph representation the corresponding H-K dynamics for $\sigma = 0.20$.

<figure><img src="image_3.png" /><figcaption>Figure 1: H-K dynamics for $x(0) = (0.19, 0.25, 0.40, 0.57, 0.77)$ and $\sigma = 0.20$.</figcaption></figure>

<figure><img src="image_4.png" /></figure>
# 3 Disintegration of $\sigma$-chains with a finite number of agents

## 3.1 Chains with at most 5 agents

We begin our analysis of disintegration of $\sigma$-chains by recalling the cases of less than 5 agents, see Krause (2000) and also Proskurnikov and Tempo (2018); Grabisch and Rusinowska (2020).

**Lemma 3.1.** Any $\sigma$-chain of length:

(i) 2 collapses into a singleton in at most 1 step,

(ii) 3 collapses into a singleton in at most 2 steps,

(ii) 4 collapses into a singleton in at most 5 steps.

Concerning the case of chains with 5 agents, there exist $\sigma$-chains of length 5 that disintegrate, as shown in the following example.

**Example 3.1.** Consider the initial opinion vector $x(0) = (0.1, 0.1, 0.3, 0.5, 0.7)$ and $\sigma = 0.2$. The corresponding initial spacings vector is $w(0) = (0, 0.2, 0.2, 0.2)$. The first two states of the H-K dynamics are as follows, where $x(0)$ constitutes a $\sigma$-chain of length 5, and where $x(1)$ constitutes two separate $\sigma$-chains.

<figure><img src="image_5.png" /></figure>

For $\sigma$-chains from length 5 onward, it depends on the precise structure within a given $\sigma$-chain whether it disintegrates. To study which inner structures lead to the disintegration of links $\{i, i+1\}$ between an agent $i$ and its right neighbour $i+1$, we will generalize the argument that is made in the following example. As we are studying an H-K updating step from a generic period $t$ to the next period $t+1$, we omit time arguments. That is, for period $t$ we denote opinions by $x_i := x_i(t)$ and spacings by $w_i := w_i(t)$. Moreover, a next spacing in period $t+1$ in terms of the spacings in period $t$ will be denoted by $\tau_i(w) := w_i(t+1)$, and we denote the opinion change of an agent $i$ in the $t$th updating step by $\Delta x_i := x_i(t+1) - x_i(t)$.

**Example 3.2.** Consider a $\sigma$-chain of length 5 of the type from Example 3.1, i.e., which has the following structure:

<figure><img src="image_6.png" /></figure>
We characterize this σ-chain in terms of the following requirements on the spacings:

$$
\left\{
\begin{array}{l}
w_1, w_2, w_3, w_4 \le \sigma \\
w_1 + w_2 \le \sigma \\
w_2 + w_3 > \sigma \\
w_3 + w_4 > \sigma.
\end{array}
\right.
$$

Here, the first inequality ensures that it is a σ-chain. The second inequality ensures that the link {1,3}
exists, and the last two inequalities ensure that no other links exist.

Now we focus on the link {3,4} with the corresponding spacing $w_3$. It remains intact in the H-K
updating if and only if the next spacing satisfies $\tau_3(w) \le \sigma$. To compute $\tau_3(w)$, we first compute the
changes in opinion $\Delta x_3$ and $\Delta x_4$ of agents 3 and 4. Observing that agent 3 has agents 1, 2, 3 and 4 in
his confidence range, we express the opinion shift $\Delta x_3$ in terms of the current spacings as follows:

$$
\begin{align*}
\Delta x_3 &= \frac{x_1 + x_2 + x_3 + x_4}{4} - x_3 \\
&= -\frac{1}{4} \left[ \underbrace{(x_3 - x_2)}_{w_2} + \underbrace{(x_2 - x_1)}_{w_1} \right] - \frac{1}{4} \underbrace{(x_3 - x_2)}_{w_2} + \frac{1}{4} \underbrace{(x_4 - x_3)}_{w_3} \\
&= -\frac{1}{4}w_1 - \frac{1}{2}w_2 + \frac{1}{4}w_3
\end{align*}
$$

Similarly, one can obtain

$$
\Delta x_4 = -\frac{1}{3}w_3 + \frac{1}{3}w_4.
$$

Then, the next spacing of link {3,4} is given by

$$
\tau_3(w) = w_3 + \Delta x_4 - \Delta x_3 = \frac{1}{4}w_1 + \frac{1}{2}w_2 + \frac{5}{12}w_3 + \frac{1}{3}w_4.
$$

We conclude that link {3, 4} remains intact in the H-K updating if and only if $\frac{1}{4}w_1 + \frac{1}{2}w_2 + \frac{5}{12}w_3 + \frac{1}{3}w_4 \le \sigma$.
$\triangle$

To generalize the argument from Example 3.2, that is, to compute the next spacing of a link {$i, i+1$}, we first formalize the structure of the σ-chain around it in terms of a tuple (L, R, Λ, P). Here, L and R are the number of neighbours to the left and right of i, respectively, where an agent j is a neighbour of i if they trust each other, i.e., if $|x_i - x_j| \le \sigma$. Similarly, we let Λ and P be the number of neighbours to the left and right of i + 1, respectively. Moreover, we let u and v be the total number of trusted agents by agent i and i + 1, respectively.

**Definition 3.1.** Let $w$ be the spacings vector corresponding to a $\sigma$-chain of length $n$. For some $i \in \{1, \dots, n-1\}$, the *neighbourhood* of the link $\{i, i+1\}$ is given by $(L, R, \Lambda, P)$, where

$$
L = \max \{m \in \{1, \dots, i-1\} \mid \sum_{j=1}^{m} w_{i-j} \le \sigma\}, \quad R = \max \{m \in \{1, \dots, n-i\} \mid \sum_{j=1}^{m} w_{i+j-1} \le \sigma\},
$$

$$
\Lambda = \max \{m \in \{1, \dots, i-1\} \mid \sum_{j=1}^{m} w_{i-j+1} \le \sigma\}, \quad P = \max \{m \in \{1, \dots, n-i\} \mid \sum_{j=1}^{m} w_{i+j} \le \sigma\}.
$$

With a neighbourhood $(L, R, \Lambda, P)$, we associate the total number of agents trusted by $i$ and $i+1$, respectively, given by

$u = L + 1 + R$

$v = \Lambda + 1 + P.$
Figure 2 illustrates the neighbourhood of a link {$i, i+1$}. A fragment of a possibly much larger $\sigma$-chain is shown, where only the edges from agents $i$ and $i+1$ to their leftmost and rightmost neighbours are displayed.

<figure><img src="image_7.png" /><figcaption>Figure 2: Neighbourhood $(L, R, \Lambda, P)$ of a link {$i, i+1$}.</figcaption></figure>

The following proposition characterizes the next spacing of a link {$i, i+1$} in terms of the current spacings in its neighbourhood.

**Proposition 3.1.** Let $w$ be the spacings vector corresponding to a $\sigma$-chain of length $n$ and, for some $i \in \{1, ..., n-1\}$, consider the link {$i, i+1$} with its neighbourhood $(L, R, \Lambda, P)$. The next spacing of the link {$i, i+1$} is given by<fnref n="1" />

$$ \tau_i(w) = \frac{1}{uv} \left[ \sum_{l=\Lambda}^{L} [v \cdot (L-l+1)] \cdot w_{i-l} \right. \\ + \sum_{l=1}^{\Lambda-1} [v \cdot (L-l+1) - u \cdot (\Lambda-l)] \cdot w_{i-l} \\ + [uv - u \cdot \Lambda - v \cdot R] \cdot w_i \\ + \sum_{r=1}^{R-1} [u \cdot (P-r+1) - v \cdot (R-r)] \cdot w_{i+r} \\ \left. + \sum_{r=R}^{P} [u \cdot (P-r+1)] \cdot w_{i+r} \right] $$

The expression for $\tau_i(w)$ in Proposition 3.1 reveals what role the neighbourhood parameters play in the constitution of the next spacing of the link {$i, i+1$}. Notice that $\tau_i(w)$ is a linear combination of the spacings $w_{i-L}, ..., w_{i+P}$. Also notice that the parameters $L$ and $P$ contribute positively toward $\tau_i(w)$ and that $R$ and $\Lambda$ contribute negatively toward $\tau_i(w)$. Informally speaking, $L$ and $P$ can be said to stretch out the next spacing $\tau_i(w)$, whereas $R$ and $\Lambda$ compress it. In a similar spirit, without providing derivatives of $\tau_i(w)$ with respect to the neighbourhood parameters, we remark that disintegration of a link becomes more likely with increasing values of $L$ and $P$ and decreasing values of $R$ and $\Lambda$.

The following example demonstrates how Proposition 3.1 can be used to investigate the breaking of links in a specific $\sigma$-chain structure. In some cases, a link in a $\sigma$-chain can be guaranteed to remain intact for all spacings vectors satisfying a certain $\sigma$-chain structure.

**Example 3.3.** Consider a $\sigma$-chain of length 5 of the following structure:

<footnote n="1">¹Depending on the values of $(L, R, \Lambda, P)$, one or more of these sums should be omitted. Here, we adopt the convention that $\sum_{i=a}^{b} (...) = 0$ if $a > b$. For instance, if $\Lambda = 1$, then $\sum_{l=1}^{\Lambda} (...) = 0$.</footnote>
<figure><img src="image_8.png" /></figure>

We characterize this $\sigma$-chain with the following requirements on the spacings:

$$ \begin{cases} w_1, w_2, w_3, w_4 \le \sigma \\ w_2 + w_3 + w_4 \le \sigma \\ w_1 + w_2 + w_3 + w_4 > \sigma. \end{cases} $$

Now consider link $\{1, 2\}$, with neighbourhood $(L, R, \Lambda, P) = (0, 1, 1, 3)$ and with $u = 2$ and $v = 5$. By Proposition 3.1, the next spacing of $\{1, 2\}$ is given by

$$ \tau_1(w) = \frac{1}{10} (3w_1 + 6w_2 + 4w_3 + 2w_4). $$

Using the spacings requirements on this $\sigma$-chain structure, we derive as follows that the next spacing $\tau_1(w)$ is bounded above by $\sigma$:

$$ \tau_1(w) = \frac{1}{10} \left( 3 \underbrace{w_1}_{\le \sigma} + 2 \underbrace{(w_2 + w_3 + w_4)}_{\le \sigma} + 2 \underbrace{(w_2 + w_3)}_{\le \sigma} + 2 \underbrace{w_2}_{\le \sigma} \right) \le \frac{9}{10} \sigma. $$

Therefore, for any spacings vector $w$ that induces this $\sigma$-chain structure, we can guarantee that the link $\{1, 2\}$ does not disintegrate. $\triangle$

Even though Proposition 3.1 is insightful, to apply it to an extensive disintegration analysis of different $\sigma$-chain structures is tedious. To derive which $\sigma$-chains of length 5 can disintegrate, we apply the following approach to all possible structures of $\sigma$-chains of length 5. For a $\sigma$-chain in some period $t$, the following proposition expresses the next spacings vector $w(t+1)$ as a matrix-vector product of the spacings vector $w(t)$ and matrix that is derived from the adjacency matrix induced by $w(t)$.

**Proposition 3.2.** Let $x(t)$ be a $\sigma$-chain of length $n$ at some time $t$, with corresponding spacings vector $w(t)$. Let $A(t) \in \{0, 1\}^{n \times n}$ be the corresponding adjacency matrix, where $A_{ij}(t) = 1$ if and only if $|x_i(t) - x_j(t)| \le \sigma$. Then, the next spacings vector $w(t+1)$ is given by<fnref n="2" />

$$ w(t+1) = [B(diag(A(t)e))^{-1}A(t)C] w(t), \quad (1) $$

where the $(n-1) \times n$ matrix $B$ is given by

$$ B_{ij} = \begin{cases} -1 & \text{if } i = j \\ 1 & \text{if } i + 1 = j \\ 0 & \text{otherwise} \end{cases} $$

for all $i \in \{1, ..., n-1\}$ and $j \in \{1, ..., n\}$, and where the $n \times n-1$ matrix $C$ is given by

$$ C_{ij} = \begin{cases} 1 & \text{if } i > j \\ 0 & \text{otherwise} \end{cases} $$

for all $i \in \{1, ..., n\}$ and $j \in \{1, ..., n-1\}$.

<footnote n="2">²Here, $e$ denotes the $n \times 1$ all-ones vector.</footnote>
At the core of equation (1) is the row-stochastic matrix obtained by normalizing the adjacency matrix $A(t)$ such that every row sums up to one. In particular, one could use it to describe an H-K updating step as follows, for some opinion vector $x(t)$ and the corresponding adjacency matrix $A(t)$:

$$x(t+1) = [(\mathrm{diag}(A(t)e))^{-1} A(t)] x(t).$$

The role of auxiliary matrix $C$ in equation (1) is to transform a spacings vector $w(t)$ into a corresponding opinions vector. Vice versa, pre-multiplying an opinion vector by the auxiliary matrix $B$ yields the corresponding spacings vector.

Propositions 3.1 and 3.2 both compute next spacings as linear combinations of a current spacings vector. In Proposition 3.2, the weights occuring in the $i^{th}$ row of the matrix by which $w(t)$ is pre-multipled are the same weights that occur in the computation of the next spacing $\tau_i(w)$ in Proposition 3.1. The following example illustrates this.

**Example 3.4.** Reconsider the $\sigma$-chain structure of Example 3.3. For a spacings vector $w(t) = (w_1, w_2, w_3, w_4)$ in some period $t$ satisfying this structure, the corresponding adjacency matrix is given by

$$A(t) = \begin{bmatrix} 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 \end{bmatrix}.$$

Then, by Proposition 3.2, the next spacings vector $w(t+1)$ is given by

$$w(t+1) = \begin{bmatrix} -1 & 1 & 0 & 0 & 0 \\ 0 & -1 & 1 & 0 & 0 \\ 0 & 0 & -1 & 1 & 0 \\ 0 & 0 & 0 & -1 & 1 \end{bmatrix} \begin{bmatrix} \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 \\ \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} & \frac{1}{5} \\ 0 & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\ 0 & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \end{bmatrix} \begin{bmatrix} 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \end{bmatrix} w(t) \\ = \frac{1}{20} \begin{bmatrix} 6 & 12 & 8 & 4 \\ 4 & 3 & 2 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} w_1 \\ w_2 \\ w_3 \\ w_4 \end{bmatrix}. \qquad (2)$$

Observe that the weights in the first row of the matrix in equation (2) are equal to those in the computation of the next spacing of the link $\{1, 2\}$ in Example 3.3. $\Delta$

The advantage of Proposition 3.2 is that it allows for an efficient investigation of the transitions of many $\sigma$-chain structures, in order to obtain results such as the following. All $\sigma$-chains of length 5 remain intact, except for those of the form given in Figure 3 and its mirrored equivalent. The following theorem states this formally.

**Theorem 3.1.** Let $x(t) \in [0, 1]^5$ be a $\sigma$-chain of 5 agents at some time $t \in \mathbb{N}$, and let $w = w(t)$ be the associated spacings vector. Then, this $\sigma$-chain disintegrates if and only if one of the following (symmetric) conditions is satisfied:

$$\left\{ \begin{array}{l} w_1 + w_2 \le \sigma \\ w_2 + w_3 > \sigma \\ w_3 + w_4 > \sigma \\ \frac{1}{12}(3w_1 + 6w_2 + 5w_3 + 4w_4) > \sigma, \end{array} \right. \quad \text{or} \quad \left\{ \begin{array}{l} w_1 + w_2 > \sigma \\ w_2 + w_3 > \sigma \\ w_3 + w_4 \le \sigma \\ \frac{1}{12}(4w_1 + 5w_2 + 6w_3 + 3w_4) > \sigma. \end{array} \right.$$
<figure><img src="image_9.png" /><figcaption>Figure 3: The only structure of a σ-chain of length 5 that permits disintegration, together with its mirrored equivalent, as described by the conditions in Theorem 3.1.</figcaption></figure>

## 3.2 Likelihood of the disintegration of σ-chains

So far, we have studied the disintegration of σ-chains up to length 5 analytically. To develop a sense of the role that $n$ and $\sigma$ play in the disintegration of σ-chains, we now investigate by simulation the likelihood that σ-chains of given length $n$ disintegrate during the H-K dynamics. Let us denote a uniformly distributed initial vector of $n$ agents by $x(0) \sim U_n(0, 1)$, where the individual initial opinion of every agent $i \in \{1, ..., n\}$ is independently uniformly distributed on the interval $[0, 1]$, i.e., $x_i(0) \stackrel{iid}{\sim} U(0, 1)$. For several combinations of $n$ and $\sigma$, random vectors $x \sim U_n(0, 1)$ were generated, and for each it was checked if it was a σ-chain. This generation of random vectors was repeated until $10^4$ σ-chains were obtained. For each of these $10^4$ σ-chains, the H-K dynamics was computed with these σ-chains as the initial opinion vector, and it was recorded as a disintegration event if the H-K dynamics resulted in two or more clusters. For various combinations of $n$ and $\sigma$, Table 1 reports the fraction of $10^4$ randomly generated σ-chains that disintegrated.

<table><caption>Table 1: Fraction of $10^4$ σ-chains of length $n$ that disintegrate during the H-K dynamics, for various combinations of $n$ and $\sigma$.</caption><thead><tr><th>σ<br>n</th><th>0.05</th><th>0.1</th><th>0.2</th><th>0.3</th><th>0.4</th><th>0.5</th></tr></thead><tbody><tr><th>5</th><td>0.0181</td><td>0.0167</td><td>0.0152</td><td>0.0122</td><td>0.0002</td><td>0</td></tr><tr><th>6</th><td>0.1673</td><td>0.1621</td><td>0.1326</td><td>0.0681</td><td>0.0140</td><td>0</td></tr><tr><th>7</th><td>0.4307</td><td>0.4168</td><td>0.3453</td><td>0.1725</td><td>0.0354</td><td>0.0006</td></tr><tr><th>8</th><td>0.6312</td><td>0.6178</td><td>0.5170</td><td>0.2452</td><td>0.0530</td><td>0.0020</td></tr><tr><th>9</th><td>0.7735</td><td>0.7546</td><td>0.6364</td><td>0.2768</td><td>0.0511</td><td>0.0042</td></tr><tr><th>10</th><td>0.8804</td><td>0.8675</td><td>0.7306</td><td>0.3139</td><td>0.0517</td><td>0.0029</td></tr></tbody></table>

Table 1 suggests that for a given number of agents $n$, the likelihood of σ-chain disintegration is decreasing in $\sigma$. The role of the number of agents $n$ is ambiguous. Broadly speaking, for a given $\sigma$, the likelihood of σ-chain disintegration increases as the number of agents $n$ increases. However, notice that for $\sigma = 0.4$ and $\sigma = 0.5$, Table 1 seems to indicate that the estimated likelihood of disintegration is non-monotone.

# 4 Disintegration of σ-chains with a continuum of agents

## 4.1 The Hegselmann-Krause model with a continuum of agents

Consider a continuum of agents that form a population of mass one. Each agent will hold an opinion $x_t \in [0, 1]$ in every period of a discrete infinite time horizon $N = \{0, 1, 2, ...\}$. In the initial period $t = 0$, the agents' opinions are uniformly distributed on $[0, 1]$. Formally, we define the initial distribution in terms of the cumulative density function (CDF) $F_0$, given by

$$F_0(x_0) = x_0 \qquad \text{for all } x_0 \in [0, 1].$$
Associated with $F_0$ is its corresponding population density function (PDF)$^3$ $f_0$, given by

$$f_0(x_0) = \frac{\partial F_0(x_0)}{\partial x_0} = 1 \qquad \text{for all } x_0 \in [0, 1].$$

To obtain the CDF $F_t$ and the PDF $f_t$ for all periods $t \in \mathbb{N}$, we define how every agent in period $t$ computes his next opinion for period $(t+1)$. From each period $t \in \mathbb{N}$ to the next, agents update their opinion to the mean opinion held in time $t$ in a neighbourhood around their own opinion. Specifically, an agent with opinion $x_t$ in time $t$ will consider the neighbourhood $[x_t - \sigma, x_t + \sigma]$, where $\sigma \in [0, 1]$ is a given confidence parameter, common to all agents and invariant throughout time. Here, if $x_t - \sigma < 0$, the left bound of the neighbourhood is capped to 0, and similarly, if $x_t + \sigma > 1$, the right bound is capped to 1. Hence, the neighbourhood is given by

$$[l(x_t), r(x_t)] = [\max\{0, x_t - \sigma\}, \min\{1, x_t + \sigma\}].$$

In this neighbourhood, the mean opinion will be computed in several steps. First, we compute the total opinion mass in this neighbourhood, given by

$$\lambda([l(x_t), r(x_t)]) = F_t(r(x_t)) - F_t(l(x_t)).$$

Also, we compute the “unnormalized mean” in this neighbourhood, given by

$$\mu([l(x_t), r(x_t)]) = \int_{u=l(x_t)}^{r(x_t)} uf_t(u)du.$$

Then, the next opinion $\alpha_{t+1}(x_t)$ is given by normalizing $\mu([l(x_t), r(x_t)])$ with $\lambda([l(x_t), r(x_t)])$ as

$$\alpha_{t+1}(x_t) = \frac{\mu([l(x_t), r(x_t)])}{\lambda([l(x_t), r(x_t)])}.$$

We call $\alpha_t$ for $t \ge 1$ the one-stage transition function for the transition $(t-1) \to (t)$. As for notation, we conscientiously denote an opinion $x_t$ with the period to which it corresponds in the subscript. So, a function $\alpha_t$ takes as input some $x_{t-1}$ and gives as output some $x_t$. Also, we introduce the cumulative transition function $\beta_t$, for $t \ge 1$, as

$$\beta_t(x_0) = \alpha_t(\alpha_{t-1}(\dots \alpha_1(x_0)\dots)),$$

which assigns to every opinion$^4$ $x_0$ in period 0 the location to which it will have moved in period $t$. Notice that one can also represent $\beta_t$ as

$$\beta_t(x_0) = \alpha_t(\beta_{t-1}(x_0)).$$

Now we can compute the CDF and PDF in any period in terms of the $t$-stage transition functions $\beta_t$, as follows. Formally, $F_t(x_t)$ is the mass of agents with opinion in the interval $[0, x_t]$ at time step $t$. Due to Lemma 2.1, it turns out that at time step $t-1$, this corresponds to the mass of agents with opinion in the interval $[0, z]$, with $z = \sup\{x | \alpha_t(x) \le x_t\}$. Observe that the set $\{x | \alpha_t(x) \le x_t\}$ may be empty, in which case we set $z = 0$. Iterating the previous argument, we can go back to step 0, getting the interval $[0, z]$ with $z = \sup\{x | \beta_t(x) \le x_t\}$. As in step 0, the density of the population is uniformly equal to 1, it follows that $F_t(x_t)$ is equal to $z$. In summary:

$$F_t(x_t) = \begin{cases} 0, & \text{if } \beta^{-1}(\{x_t\}) = \emptyset \\ \sup\{x | \beta_t(x) \le x_t\}, & \text{otherwise.} \end{cases} \qquad (3)$$

<footnote>$^3$Note that we give the letter “P” in PDF the meaning “population”, instead of the usual “probability”. We will be concerned with the distribution of a population, not of probabilities. Conveniently, both start with the letter “p”.</footnote>

<footnote>$^4$To be precise, we should talk always about agents with a certain opinion in a certain period moving to another opinion in the next period. However, this quickly becomes tedious, so we simply talk about $x$'s moving from one place to the next.</footnote>
Unless $\beta_t$ is invertible, $F_t$ is not continuous, and therefore not differentiable in general. Assuming differentiability, we can compute the PDF by

$$f_t(x_t) = \frac{\partial F_t(x_t)}{\partial x_t},$$

for all $x_t \in [0, 1]$.

In a state of convergence, a certain number of clusters will have formed. A cluster in period $t$ will be identified by a real number $c \in [0, 1]$, such that $F_t$ is non-continuous, i.e., some $\epsilon > 0$ exists, such that for all $\delta > 0$,$^5$

$$F_t(c) - F_t(c - \delta) > \epsilon.$$

In words, a cluster is defined as “the accumulation of strictly positive mass on a real number between 0 and 1”. Notice that the PDF $f_t$ is not evaluated in the point $c$ itself, because it is not well-defined there; since $F_t$ is not continuous in $c$, it is certainly not differentiable in $c$.

As a last note, it will turn out to only focus on the interval $[\beta_t(0), \beta_t(1)]$ in period $t$, and disregard the remainder of $[0, 1]$ that is guaranteed to have zero mass. In this spirit, it will turn out to be convenient to slightly redefine the neighbourhoods:

$$[l_t(x_t), r_t(x_t)] = [\max\{\beta_t(0), x_t - \sigma\}, \min\{\beta_t(1), x_t + \sigma\}].$$

## 4.2 Formation of clusters

In this section, we attempt at analyzing in a formal way the formation of clusters, by observing how the initial $\sigma$-chain (the interval $[0, 1]$) disintegrates. We first perform a complete analysis of the two first time steps.

**Step t = 1.** At $t = 0$, the density is uniform and of value 1, therefore the computation of $\alpha_1(x_0)$ reduces to taking the midpoint of the interval $[l(x_0), r(x_0)]$. There are three zones for $x_0$ where the computation differs (supposing $\sigma \le 1 - \sigma$, i.e., $\sigma \le 1/2$), summarized below:

$$[l(x_0), r(x_0)] = \begin{cases} [0, x_0 + \sigma], & \text{if } x_0 \in [0, \sigma] \\ [x_0 - \sigma, x_0 + \sigma], & \text{if } x_0 \in [\sigma, 1 - \sigma] \\ [x_0 - \sigma, 1], & \text{if } x_0 \in [1 - \sigma, 1]. \end{cases}$$

Observe that everything is symmetric w.r.t. $x_0 = 1/2$, so we need to consider only the interval $[0, 1/2]$. We immediately obtain:

$$\alpha_1(x_0) = \beta_1(x_0) = \begin{cases} x_0/2 + \sigma/2, & \text{if } x_0 \in [0, \sigma] \\ x_0, & \text{if } x_0 \in [\sigma, 1/2]. \end{cases}$$

In particular, $\alpha_1(0) = \sigma/2$, showing that the initial interval $[0, 1]$ reduces to $[\sigma/2, 1 - \sigma/2]$. Using (3), the density $f_1(x)$ can be computed, however more simple considerations can be used: Observe that all agents in the interval $[0, \sigma]$ at $t = 0$ have opinion at $t = 1$ in the interval $[\sigma/2, \sigma]$. Therefore, in this interval the density is equal to 2. For all agents in $[\sigma, 1 - \sigma]$ at $t = 0$, the opinion does not change, so the density remains equal to 1. The results are summarized in Figure 4.

When $\sigma > 1/2$, things will be particularly simple as it will be seen at $t = 2$. Simply observe for the moment that, as above, $\alpha_1(0) = \sigma/2$ and $\alpha_1(1) = 1 - \sigma/2$.

<footnote>$^5$Notice that this definition does not allow for “clusters with mass zero”. In particular, according to this definition, it may occur that $1/2$ is not a cluster, despite the fact that it is always a fixed point of $\alpha_t$ and $\beta_t$ for any $t \in \mathbb{N}$, by symmetry.</footnote>
<figure><img src="image_10.png" /><figcaption>Figure 4: Step $t = 1$ with $\sigma = 0.3$.</figcaption></figure>

**Step t = 2.** Let us first treat the case $\sigma > 1/2$. By the previous result, the interval of opinions at $t = 1$ reduces to $[\sigma/2, 1 - \sigma/2]$. Observe that the length of this interval is $1 - \sigma < \sigma$. Therefore, $\alpha_2(x_1) = 1/2$ for all $x_1$ in this interval. The process has then converged in two steps to the value $1/2$ (1 cluster).

For the rest of this section, we consider $\sigma \le 1/2$. As said above, we consider $x_1 \in [0, 1/2]$, as there is symmetry w.r.t. $1/2$. Consequently, $1/2$ is invariant.

We consider below all values $x_1$ for which there is a discontinuity, either in $f_1(x_1)$ or in $f_1(x_1 - \sigma)$ or in $f_1(x_1 + \sigma)$. From Figure 4, in the interval $[0, 1/2]$, we see that discontinuities for $f_1(x_1)$ occur at $x_1 = \sigma/2$ and $\sigma$. Consequently, discontinuities for $f_1(x_1 - \sigma)$ happen for $x_1 = 3\sigma/2$ and $2\sigma$. On the other hand, discontinuities for $f_1(x_1 + \sigma)$ occur at $x_1 = 1 - 2\sigma$ and $x_1 = 1 - 3\sigma/2$. The condition $x_1 \in [0, 1/2]$ gives the following constraints on $\sigma$:

1. $x_1 = 3\sigma/2 \le 1/2$ implies $\sigma \le 1/3$

2. $x_1 = 2\sigma \le 1/2$ implies $\sigma \le 1/4$

3. $x_1 = 1 - 2\sigma \le 1/2$ implies $\sigma \ge 1/4$

4. $x_1 = 1 - 3\sigma/2 \le 1/2$ implies $\sigma \ge 1/3$.

Besides, we need to know the ordering between the different points of discontinuity, according to the value of $\sigma$:

<table><thead><tr><th>range of σ</th><th>values of x<sub>1</sub> ∈ [0, 1/2] in increasing order<br>causing discontinuities</th></tr></thead><tbody><tr><td>[0, 1/4]</td><td>σ/2, σ, 3σ/2, 2σ</td></tr><tr><td>[1/4, 2/7]</td><td>σ/2, σ, 3σ/2, 1 - 2σ</td></tr><tr><td>[2/7, 1/3]</td><td>σ/2, σ, 1 - 2σ, 3σ/2</td></tr><tr><td>[1/3, 2/5]</td><td>σ/2, 1 - 2σ, σ, 1 - 3σ/2</td></tr><tr><td>[2/5, 1/2]</td><td>1 - 2σ, σ/2, 1 - 3σ/2, σ</td></tr></tbody></table>

We have to compute the density $f_2(x)$ for any value of $\sigma$, and for this we need to compute $\alpha_2(x)$ for all $x$ corresponding to discontinuities, as given in the above table. A direct and exact computation via (3) seems to be too complex. We propose instead an approximate computation, where the densities are approximated by rectangles. The computations being nevertheless quite long, they are given in Appendix B, for any $\sigma \in [0, 1/3]$ (as it will be seen below, this is enough for our purpose). We give in Figure 5 the shape of $f_2(x)$ in the case $\sigma \in [0, 1/4]$. As explained in the Appendix, the shape is similar in all cases.

We are now in position to give a condition on $\sigma$ to have only one cluster when $t$ tends to infinity.
<figure><img src="image_11.png" /><figcaption>Figure 5: Step $t = 2$ with $\sigma < 1/4$ ($\sigma = 0.2$).</figcaption></figure>

**Lemma 4.1.** Consider the density $f_2(x)$ with the generic form described in Fig. 6. Then $f_3$ has only one peak centered at $1/2$ and $f_t$ converges when $t \to \infty$ to a Dirac at $x = 1/2$ if $a + \sigma \ge 1 - c$.

<figure><img src="image_12.png" /><figcaption>Figure 6: Generic form for $f_2(x)$.</figcaption></figure>

Let us apply the above lemma to the densities $f_2$ found in Appendix B. Let us consider $\sigma \in [2/7, 1/3]$. Then

$$a = \frac{11\sigma}{12}, \quad b = \frac{9\sigma}{8}, \quad c = \frac{3\sigma^2 - 4\sigma + 2}{4(1 - \sigma)}.$$

The condition $a + \sigma \ge 1 - c$ becomes

$$-14\sigma^2 + 23\sigma - 6 \ge 0$$

which yields $\sigma \in [\frac{1}{28}(23 - \sqrt{193}), \frac{1}{28}(23 + \sqrt{193})]$, approximately $[0.3253, 1.3176]$. Hence, the process converges to a unique cluster at $1/2$ as soon as $t = 3$ when $\sigma \ge 0.3253$.
# 5 Monotonicity of the number of clusters

Next, we investigate the H-K dynamics on a higher level. In the previous sections, the focus lies on single updating steps of the H-K dynamics, for a given opinion vector $x$ and confidence parameter $\sigma$. Now, for each value of $\sigma$, we let the H-K dynamics run until convergence and observe how many clusters form. For a given $\sigma \in [0, 1]$ and initial opinion vector $x(0) \in [0, 1]$, we denote by $\nu(\sigma, x(0))$ the number of clusters that are obtained when the H-K dynamics has converged.

## 5.1 Number of clusters for a given initial vector

A puzzling phenomenon that has been identified in the literature (see e.g., Proskurnikov and Tempo (2018)) is that there exist initial vectors $x(0)$ for which the number of clusters $\nu(\sigma, x(0))$ is non-monotone in $\sigma$. This contradicts the intuition that $\nu(\sigma, x(0))$ should be non-increasing in $\sigma$.

Using the results on $\sigma$-chains of the previous sections, we derive that such non-monotonicity cannot occur in case of 2, 3 or 4 agents.

**Fact 5.1.** Let $n \in \{2, 3, 4\}$ be the number of agents. Then, for any initial opinion vector $x(0) \in [0, 1]^n$, the number of clusters $\nu(\sigma, x(0))$ is non-increasing in $\sigma$.

In case of 5 agents, however, there exist initial vectors $x(0)$ for which the number of clusters $\nu(\sigma, x(0))$ is non-monotone in $\sigma$, as presented in the following example.

**Example 5.1.** Consider 5 agents and the initial opinion vector $x(0) = (0.19, 0.25, 0.40, 0.57, 0.77)$. We now compute the H-K dynamics three times, for each of the values $\sigma \in \{0.19, 0.20, 0.21\}$. It turns out that $\nu(0.19, x(0)) = 2$, $\nu(0.20, x(0)) = 1$, and $\nu(0.21, x(0)) = 2$. Therefore, $\nu(\sigma, x(0))$ is non-monotone in $\sigma$.

Here follows the H-K dynamics for $\sigma = 0.19$:

<figure><img src="image_13.png" /></figure>

<figure><img src="image_14.png" /></figure>

<figure><img src="image_15.png" /></figure>
<figure><img src="image_16.png" /><figcaption>Figure 7: H-K dynamics for $x(0) = (0.19, 0.25, 0.40, 0.57, 0.77)$ and $\sigma = 0.19$.</figcaption></figure>

Here follows the H-K dynamics for $\sigma = 0.20$:

<figure><img src="image_17.png" /></figure>

<figure><img src="image_18.png" /></figure>

<figure><img src="image_19.png" /></figure>

<figure><img src="image_20.png" /></figure>

<figure><img src="image_21.png" /></figure>
<figure><img src="image_22.png" /><figcaption>Figure 8: H-K dynamics for $x(0) = (0.19, 0.25, 0.40, 0.57, 0.77)$ and $\sigma = 0.20$.</figcaption></figure>

Here follows the H-K dynamics for $\sigma = 0.21$:

<figure><img src="image_23.png" /><figcaption>Figure 9: H-K dynamics for $x(0) = (0.19, 0.25, 0.40, 0.57, 0.77)$ and $\sigma = 0.21$.</figcaption></figure>

Δ

Similarly, we obtain by construction that for any number of agents greater or equal to 5, there exist vectors $x(0)$ such that $\nu(\sigma, x(0))$ is non-monotone in $\sigma$. The following example extends Example 5.1 and constructs such an initial vector for any number of agents $n \ge 5$.

**Example 5.2.** Consider $n \ge 5$ agents and the initial opinion vector

$$x(0) = (0.19, 0.25, 0.40, 0.57, 0.77, \underbrace{1, \dots, 1}_{(n-5) \text{ times}}).$$

It can be verified, using Example 5.1, that $\nu(0.19, x(0)) = 3$, $\nu(0.20, x(0)) = 2$, and $\nu(0.21, x(0)) = 3$. Therefore, $\nu(\sigma, x(0))$ is non-monotone in $\sigma$. Δ

## 5.2 Number of clusters in expectation

Even though there exist initial opinion vectors $x(0)$ for which $\nu(\sigma, x(0))$ is non-monotone, simulations suggest that, in expectation, the number of clusters is non-increasing in $\sigma$. To support this claim, we run simulations to estimate the expected number of clusters $\mathbb{E}_{x(0) \sim U_n(0,1)}[\nu(\sigma, x(0))]$ for a range of values of $\sigma$.
Here, we denote a uniformly distributed initial vector of $n$ agents by $x(0) \sim U_n(0, 1)$, where the individual initial opinion of every agent $i \in \{1, ..., n\}$ is independently uniformly distributed on the interval $[0, 1]$, i.e., $x_i(0) \stackrel{iid}{\sim} U(0, 1)$. In this way, we generate 10,000 initial vectors $x^1(0), x^2(0), ..., x^{10,000}(0)$. For each initial vector $x^k(0)$, we run the H-K dynamics until convergence and observe the number of clusters $\nu(\sigma, x^k(0))$, for each value $\sigma \in \{0, 0.01, 0.02, ..., 1\}$. Then we estimate, for each value of $\sigma$, the expected number of clusters as the average of the 10,000 vectors. This estimate is denoted by

$$ \bar{\nu}_n(\sigma) = \frac{1}{10,000} \sum_{k=1}^{10,000} \nu(\sigma, x^k(0)) $$

for all $\sigma \in \{0, 0.01, 0.02, ..., 1\}$.

To clarify our approach and to compare it with existing ones in the literature, it is useful to observe an excerpt of the table that is produced during the simulation. Table 2 displays the number of clusters $\nu(\sigma, x^k(0))$, for a few out of 10,000 initial vectors and for several values of $\sigma$. Increments of $\sigma$ where monotonicity of $\nu(\sigma, x^k(0))$ is breached are marked with an asterisk. The number $\bar{\nu}_n(\sigma)$ for some $\sigma$ is the average of the corresponding column of such a table. Proskurnikov and Tempo (2018) expose non-monotonicity by running the H-K dynamics until convergence on a single initial opinion vector $x(0)$ of 100 agents, for several values of $\sigma \in [0, 1]$. The H-K dynamics are plotted for six values of $\sigma$ and it is observed that for the two values $\sigma \in \{0.05, 0.11\}$, the number of clusters $\nu(\sigma, x(0))$ increases by one as $\sigma$ is incremented by 0.01. This analysis corresponds to a single row of Table 2.

<table><caption>Table 2: Number of clusters $\nu(\sigma, x^k(0))$, for all $\sigma \in \{0, 0.01, 0.02, ..., 1\}$, and for 10,000 uniformly drawn initial vectors with 100 agents.</caption><thead><tr><th>σ</th><th>0</th><th>0.01</th><th>0.02</th><th>0.03</th><th>0.04</th><th>0.05</th><th>0.06</th><th>0.07</th><th>0.08</th><th>0.09</th><th>0.10</th><th>...</th><th>1.00</th></tr></thead><tbody><tr><td>x<sup>1</sup>(0)</td><td>100</td><td>35</td><td>17</td><td>14</td><td>8</td><td>8</td><td>5</td><td>4</td><td>4</td><td>4</td><td>4</td><td>...</td><td>1</td></tr><tr><td>x<sup>2</sup>(0)</td><td>100</td><td>37</td><td>21</td><td>13</td><td>9</td><td>8</td><td>6</td><td>5</td><td>5</td><td>4</td><td><b>5</b>*</td><td>...</td><td>1</td></tr><tr><td>x<sup>3</sup>(0)</td><td>100</td><td>39</td><td>21</td><td>13</td><td>10</td><td>7</td><td>6</td><td>6</td><td>6</td><td>4</td><td>3</td><td>...</td><td>1</td></tr><tr><td>x<sup>4</sup>(0)</td><td>100</td><td>39</td><td>21</td><td>13</td><td>10</td><td>9</td><td>6</td><td>6</td><td>5</td><td>5</td><td>4</td><td>...</td><td>1</td></tr><tr><td>x<sup>5</sup>(0)</td><td>100</td><td>39</td><td>20</td><td>13</td><td>9</td><td>7</td><td>4</td><td>4</td><td>4</td><td><b>5</b>*</td><td>4</td><td>...</td><td>1</td></tr><tr><td>...</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>x<sup>10,000</sup>(0)</td><td>100</td><td>37</td><td>19</td><td>11</td><td>11</td><td>8</td><td>6</td><td>5</td><td>4</td><td>4</td><td><b>5</b>*</td><td>...</td><td>1</td></tr></tbody></table>

Figure 10 shows the estimations $\bar{\nu}_n(\sigma)$ for all $\sigma \in \{0, 0.01, ..., 1\}$ of the expected number of clusters, separated by the number of agents $n$. These simulation results indicate that, in expectation, the number of clusters is non-increasing in $\sigma$.

Moreover, non-monotonicity seems to occur more often as the number of agents increases. For every number of agents $n \in \{2, 5, 10, 50, 100, 500\}$, Table 3 displays the fraction of initial vectors $x^k(0)$ where the sequence $\nu(0, x(k)), \nu(0.01, x(k)), ..., \nu(1, x(k))$ is non-monotone. Note that this is an imperfect test for non-monotonicity for a given vector $x^k(0)$. After all, for vectors $x^k(0)$ where the number of clusters is observed to be monotone, it is possible that non-monotonicity would be observed for increments of $\sigma$ smaller than 0.01.
<figure><img src="image_24.png" /><figcaption>Figure 10: Average number of clusters $\bar{v}_n(\sigma)$ for all $\sigma \in \{0, 0.01, 0.02, \dots, 1\}$, for various numbers of agents $n$.</figcaption></figure>

<table><caption>Table 3: How often monotonicity is broken in the simulated opinion vectors, for various numbers $n$ of agents.</caption><thead><tr><th>Number of agents <i>n</i></th><th>2</th><th>5</th><th>10</th><th>50</th><th>100</th><th>500</th></tr></thead><tbody><tr><td>Observed fraction of generated opinion vectors <i>k</i> &isin; {1, ..., 10<sup>4</sup>} where &nu;(&sigma;, <i>x</i><sup><i>k</i></sup>(0)) is non-monotone in &sigma;</td><td>0</td><td>0.0256</td><td>0.2112</td><td>0.5059</td><td>0.5781</td><td>0.6770</td></tr></tbody></table>

# 6 Concluding remarks

We have investigated the Hegselmann-Krause model and analyzed the formation of clusters as well as their number. We have considered two situations: a finite number of agents, and a continuum of agents. In the case of a finite number of agents, we have contributed to the study of the formation of clusters when there are more than 5 agents, and have given some analytical insights into the breaking of maximal links, i.e., those precisely leading to the splitting of the society of agents. We have also measured experimentally the proportion of $\sigma$-chains that split, as a function of the length $n$ of the chain and the value of $\sigma$, a proportion which becomes close to 1 as soon as $n$ exceeds 8 and $\sigma$ is below 0.1. On the other hand, when there is a continuum of agents, formalization is easier but rapidly leads to intractable calculations. We have proposed an approximation method which permits to fully analyze the three first time steps, and have proved that convergence to a unique cluster happens already after three steps if $\sigma \le 0.3253$. We believe that this method could lead to a deeper analysis of the formation of clusters. Finally, we have addressed the well-known problem of non-monotonicity of the number of clusters as a function of $\sigma$. We have clarified the situation considering a random experiment, distinguishing between the notion of monotonicity in average (and which in fact seems to hold, at least experimentally), and non-monotonicity as a random event, which indeed appears. In the latter case, we have estimated its
probability of occurrence, depending on the number of agents. We believe that our findings, which contribute to the study of the simple but surprisingly difficult Hegselmann-Krause model, may lead to a deeper understanding of this intuitively appealing model often used in the literature.

References

Abelson, R. (1964). Mathematical models of the distribution of attitudes under controversy. In Frederiksen, N. and Guliksen, H., editors, *Contributions to Mathematical Psychology*, pages 142–160. Holt, Rinehart & Winston, Inc, New York.

Azzimonti, M. and Fernandes, M. (2023). Social media networks, fake news, and polarization. *European Journal of Political Economy*, 76:102256.

Bernardo, C., Altafini, C., Proskurnikov, A., and Vasca, F. (2024). Bounded confidence opinion dynamics: A survey. *Automatica*, 159:111302.

Bhattacharyya, A., Braverman, M., Chazelle, B., and Nguyen, H. L. (2013). On the convergence of the Hegselmann-Krause system. In *Proceedings of the 4th Conference on Innovations in Theoretical Computer Science*, pages 61–66.

Blondel, V. D., Hendrickx, J. M., Olshevsky, A., and Tsitsiklis, J. N. (2005). Convergence in multiagent coordination, consensus, and flocking. In *Proceedings of the IEEE Conference Decision and Control*, pages 2996–3000.

Blondel, V. D., Hendrickx, J. M., and Tsitsiklis, J. N. (2007). On the 2R conjecture for multi-agent systems. In *Proceedings of the 2007 European Control Conference (ECC)*, pages 874–881.

Blondel, V. D., Hendrickx, J. M., and Tsitsiklis, J. N. (2010). Continuous-time average-preserving opinion dynamics with opinion-dependent communications. *SIAM Journal of Control and Optimization*, 48:5214–5240.

Bolletta, U. and Paolo, P. (2025). Dynamic opinion updating with endogenous networks. *European Economic Review*, 176:105045.

Bullo, F. (2019). *Lectures on Network Systems*. Kindle Direct Publishing: Washington, DC, USA.

Deffuant, G., Neau, D., Amblard, F., and Weisbuch, G. (2000). Mixing beliefs among interacting agents. *Advances in Complex Systems*, 3(01n04):87–98.

DeGroot, M. H. (1974). Reaching a consensus. *Journal of the American Statistical Association*, 69:118–121.

Dittmer, J. C. (2001). Consensus formation under bounded confidence. *Nonlinear Analysis: Theory, Methods & Applications*, 47(7):4615–4621.

Etesami, S. R. and Basar, T. (2015). Game-theoretical analysis of the Hegselmann-Krause model for opinion dynamics in finite dimensions. *IEEE Transactions on Automatic Control*, 60(7):1886–1897.

Etesami, S. R., Basar, T., Nedić, A., and Touri, B. (2013). Termination time of multidimensional Hegselmann-Krause opinion dynamics. In *Proceedings of the American Control Conference (ACC)*, pages 1255–1260.

French, J. (1956). A formal theory of social power. *Psychological Review*, 63(3):181–194.

Genicot, G. (2022). Tolerance and compromise in social networks. *Journal of Political Economy*, 130(1):94–120.
Grabisch, M., Mandel, A., and Rusinowska, A. (2023). On the design of public debate in social networks. *Operations Research*, 71(2):626-648.

Grabisch, M. and Rusinowska, A. (2020). A survey on nonstrategic models of opinion dynamics. *Games*, 11(4):65.

Hegselmann, R. and Krause, U. (2002). Opinion dynamics and bounded confidence, models, analysis and simulation. *Journal of Artificial Societies and Social Simulation*, 5(3):1-33.

Hegselmann, R. and Krause, U. (2006). Truth and cognitive division of labor: First steps towards a computer aided social epistemology. *Journal of Artificial Societies and Social Simulation*, 9(3):1-10.

Hegselmann, R. and Krause, U. (2015). Opinion dynamics under the influence of radical groups, charismatic leaders and other constant signals: A simple unifying model. *Networks and Heterogeneous Media*, 10(3):477-509.

Krause, U. (2000). A discrete nonlinear and non-autonomous model of consensus formation. *Communications in Difference Equations*, 2000:227-236.

Lorenz, J. (2005). A stabilization theorem for dynamics of continuous opinions. *Physica A*, 355:217-223.

Lorenz, J. (2006). Consensus strikes back in the Hegselmann-Krause model of continuous opinion dynamics under bounded confidence. *Journal of Artificial Societies and Social Simulation (JASSS)*, 9(1):1-8.

Mavridis, C. and Tsakas, N. (2021). Social capital, communication channels and opinion formation. *Social Choice and Welfare*, 56:635-678.

Nedić, A. and Touri, B. (2012). Multi-dimensional Hegselmann-Krause dynamics. In *Proceedings of the IEEE Conference on Decision and Control (CDC)*, pages 68-73.

Pan, Z. (2010). Trust, influence, and convergence of behavior in social networks. *Mathematical Social Sciences*, 60:6978.

Parravano, A., Andina-Díaz, A., and Meléndez-Jiménez, M. (2016). Bounded confidence under prefer-ential flip: A coupled dynamics of structural balance and opinions. *PLoS ONE*, 11(10):e0164323.

Pinelis, I. (2019). Order statistics on the spacings between order statistics for the uniform distribution. *arXiv preprint arXiv:1909.06406*.

Proskurnikov, A. V. and Tempo, R. (2018). A tutorial on modeling and analysis of dynamic social networks. Part ii. *Annual Reviews in Control*, 45:166-190.

Seneta, E. (2006). *Non-negative Matrices and Markov Chains*. Springer Series in Statistics, Springer.

Wang, C., Li, Q., Weinan, E., and Chazelle, B. (2017). Noisy Hegselmann-Krause systems: Phase transition and the 2R-conjecture. *Journal of Statistical Physics*, 166(5):1209-1225.

Weisbuch, G., Deffuant, G., Amblard, F., and Nadal, J.-P. (2002). Meet, discuss, and segregate! *Complexity*, 7(3):5563.

Weisbuch, G., Kirman, A., and Herreiner, D. (2000). Market organization. *Economica*, 110:411-436.

Yang, Y., Dimarogonas, D., and Hu, X. (2014). Opinion consensus of modified Hegselmann-Krause models. *Automatica*, 50(2):622-627.
# Acknowledgements

The corresponding author acknowledges financial support from the Center of Economic Research (Cen- tER) from Tilburg University.

# A Proofs of the results and additional examples

## A.1 Proof of Proposition 3.1

The structure of this proof is as follows. First, $\Delta x_i$ and $\Delta x_{i+1}$ are computed in terms of the spacings $w$ and the neighbourhood $\Theta_i(w, \sigma) = (L, R, \Lambda, P)$. Second, $\tau_i(w) = w_i + \Delta x_{i+1} - \Delta x_i$ is computed to obtain the stated result. Denote the opinions of the next period by $x'_i$ and $x'_{i+1}$.

The shift of the opinion $x_i$ is given by

$$ 
\begin{aligned}
\Delta x_i &= x'_i - x_i \\
&= \frac{x_{i-L} + \cdots + x_{i-1} + x_i + x_{i+1} + \cdots x_{i+R}}{L+R+1} - x_i \\
&= \frac{1}{L+R+1} \left( \sum_{l=1}^{L} x_{i-l} + \sum_{r=1}^{R} x_{i+r} + x_i \right) - \frac{L+R+1}{L+R+1} (x_i) \\
&= \frac{1}{u} \left[ \sum_{l=1}^{L} (x_{i-l} - x_i) + \sum_{r=1}^{R} (x_{i+r} - x_i) + (x_i - x_i) \right] \\
&= \frac{1}{u} \left[ \sum_{l=1}^{L} \left( -\sum_{k=1}^{l} w_{i-l} \right) + \sum_{r=1}^{R} \left( \sum_{k=1}^{r} w_{i+k-1} \right) \right] \\
&= \frac{1}{n} \left[ -\sum_{l=1}^{L} (L-l+1) \cdot w_{i-l} + \sum_{r=1}^{R} (R-r+1) \cdot w_{i+r-1} \right].
\end{aligned}
$$

Then, by substituting $(i+1)$ for $(i)$, one obtains similarly the expression for $\Delta x_{i+1}$:

$$ \Delta x_{i+1} = \frac{1}{v} \left[ - \sum_{l=1}^{\Lambda} (\Lambda - l + 1) \cdot w_{i+1-l} + \sum_{r=1}^{P} (P - r + 1) \cdot w_{i+r} \right]. $$

Next, to obtain $\Delta w_i$, we will be subtracting $\Delta x_i$ from $\Delta x_{i+1}$, we need to 'match' the corresponding terms of the above two expressions. To do so, we first rewrite the above expressions for $\Delta x_i$ and $\Delta x_{i+1}$ in such a way that they are separated in summations with matching spacings. The following expression is organized such that it can be roughly read "from left to right" in the corresponding graph.

$$ 
\begin{aligned}
\Delta x_i &= \frac{1}{u} \left[ - \sum_{l=\Lambda}^{L} (L-l+1) \cdot w_{i-l} - \sum_{l=1}^{\Lambda-1} (L-l+1) \cdot w_{i-l} \right. \\
&\qquad \left. + R \cdot w_i + \sum_{r=1}^{R-1} (R-r) \cdot w_{i+r} \right] \\
\Delta x_{i+1} &= \frac{1}{v} \left[ - \sum_{l=1}^{\Lambda-1} (\Lambda-l) \cdot w_{i-l} - \Lambda \cdot w_i \right. \\
&\qquad \left. + \sum_{r=1}^{R-1} (P-r+1) \cdot w_{i+r} + \sum_{r=R}^{P} (P-r+1) \cdot w_{i+r} \right]
\end{aligned}
$$
Then, we obtain that the next spacing $w_i$ is given by

$$
\begin{aligned}
\tau_i(w) &= w_i + \Delta x_{i+1} - \Delta x_i \\
&= \frac{1}{uv} [uv \cdot w_i] \\
&\quad + \frac{1}{uv} \left[ - \sum_{l=1}^{\Lambda-1} u \cdot (\Lambda-l) \cdot w_{i-l} - u \cdot \Lambda \cdot w_i \right. \\
&\qquad \left. + \sum_{r=1}^{R-1} u \cdot (P-r+1) \cdot w_{i+r} + \sum_{r=R}^{P} u \cdot (P-r+1) \cdot w_{i+r} \right] \\
&\quad + \frac{1}{uv} \left[ \sum_{l=\Lambda}^{L} v \cdot (L-l+1) \cdot w_{i-l} + \sum_{l=1}^{\Lambda-1} v \cdot (L-l+1) \cdot w_{i-l} \right. \\
&\qquad \left. - v \cdot R \cdot w_i - \sum_{r=1}^{R-1} v \cdot (R-r) \cdot w_{i+r} \right] \\
&= \frac{1}{uv} \left[ \sum_{l=\Lambda}^{L} [v \cdot (L-l+1)] \cdot w_{i-l} \right. \\
&\qquad \left. + \sum_{l=1}^{\Lambda-1} [v \cdot (L-l+1) - u \cdot (\Lambda-l)] \cdot w_{i-l} \right. \\
&\qquad \left. + [uv - u \cdot \Lambda - v \cdot R] \cdot w_i \right. \\
&\qquad \left. + \sum_{r=1}^{R-1} [u \cdot (P-r+1) - v \cdot (R-r)] \cdot w_{i+r} \right. \\
&\qquad \left. + \sum_{r=R}^{P} [u \cdot (P-r+1)] \cdot w_{i+r} \right].
\end{aligned}
$$

## A.2 Proof of Proposition 3.2

First, note that applying the H-K updating step from $x(t)$ to $x(t+1)$ as defined in Section 2 can be written as a matrix-vector product, where $x(t)$ is pre-multiplied by the adjacency matrix $A(t)$ that is made row-stochastic by dividing each row by the sum of its entries. Hence, $x(t+1)$ is given by

$$x(t+1) = (\mathrm{diag}(Ae))^{-1} A(t)x(t).$$

Also, since spacings are related to opinions as $w_i(t) = x_{i+1}(t) - x_i(t)$ for all $i \in \{1, ..., n\}$, the spacings vector $w(t)$ is given in terms of $x(t)$ by

$$w(t) = Bx(t).$$

Vice versa, since, for all $i \in \{1, ..., n\}$, the opinion of agent $i$ is given by $x_i(t) = x_1(t) + \sum_{k=1}^{i-1} w_k(t)$, the opinions vector $x(t)$ is given in terms of spacings vector $w(t)$ by

$$x(t) = x_1(t)e + Cw(t).$$

Combining the expressions above, we obtain the following expression for the next spacings vector:

$$
\begin{aligned}
w(t+1) &= Bx(t+1) = B \left( (\mathrm{diag}(Ae))^{-1} A(t) (x_1(t)e + Cw(t)) \right) \\
&= x_1(t) \cdot B \underbrace{(\mathrm{diag}(Ae))^{-1} A(t)e}_{=e} + B (\mathrm{diag}(Ae))^{-1} A(t)Cw(t) \\
&= B (\mathrm{diag}(Ae))^{-1} A(t)Cw(t).
\end{aligned}
$$
Here, we used the fact that $Be = 0$ to obtain the desired result.

## A.3 Proof of Theorem 3.1

### Enumeration of all $\sigma$-chains of length 5

To prove Theorem 3.1, we consider all structures of $\sigma$-chains of length 5. To do so, we will denote the spacing between agents $i$ and $j$ by

$$w_{ij} = \sum_{k=i}^{j-1} w_k.$$

The following graph illustrates this notation:

<figure><img src="image_25.png" /><figcaption>Figure 11: Spacings in a $\sigma$-chain of length 5.</figcaption></figure>

The structure of a $\sigma$-chain is well-defined if for every pair of agents $i, j$ it is determined whether $w_{ij} \le \sigma$ or $w_{ij} > \sigma$. To enumerate all structures, it is useful to observe the “parent-child” relations between spacings, i.e.,

$$ \text{If } i \le k \text{ and } l \le j, \text{ then } w_{ij} \le \sigma \implies w_{kl} \le \sigma, \\ \text{and, equivalently, } w_{kl} > \sigma \implies w_{ij} > \sigma. $$

Figure 12 displays all such parent-child relations within $\sigma$-chains of length 5.

<figure><img src="image_26.png" /><figcaption>Figure 12: Parent-child relations between spacings, in $\sigma$-chains of length 5.</figcaption></figure>

Along Figure 12 in a top-down manner, we enumerate all structures of $\sigma$-chains of length 5 in Table 4.

### All cases of length-5 $\sigma$-chains

Now we analyze each of the 14 cases of structures of $\sigma$-chains of length 5, by considering the matrix-vector approach from Proposition 3.2, where we denote, for some period $t$, the transition matrix by

$$T(t) = B(\text{diag}(A(t)e))^{-1}A(t)C,$$

so that $w(t + 1) = T(t)w(t)$.
<table><caption>Table 4: Enumeration of all structures of $\sigma$-chains of length 5.</caption><thead><tr><th>Case</th><th>Size-4 spacings</th><th colspan="2">Size-3 spacings</th><th colspan="2">Size-2 spacings</th></tr></thead><tbody><tr><td>(1)</td><td>w<sub>15</sub> &le; &sigma;</td><td></td><td></td><td></td><td></td></tr><tr><td>(2)</td><td>w<sub>15</sub> &gt; &sigma;</td><td>w<sub>14</sub> &le; &sigma;</td><td>w<sub>25</sub> &le; &sigma;</td><td></td><td></td></tr><tr><td>(3)</td><td>"</td><td>w<sub>14</sub> &gt; &sigma;</td><td>w<sub>25</sub> &le; &sigma;</td><td>w<sub>13</sub> &le; &sigma;</td><td></td></tr><tr><td>(4)</td><td>"</td><td>"</td><td>"</td><td>w<sub>13</sub> &gt; &sigma;</td><td></td></tr><tr><td>(5)</td><td>"</td><td>w<sub>14</sub> &le; &sigma;</td><td>w<sub>25</sub> &gt; &sigma;</td><td></td><td>w<sub>35</sub> &le; &sigma;</td></tr><tr><td>(6)</td><td>"</td><td>"</td><td>"</td><td></td><td>w<sub>35</sub> &gt; &sigma;</td></tr><tr><td>(7)</td><td>"</td><td>w<sub>14</sub> &gt; &sigma;</td><td>w<sub>25</sub> &gt; &sigma;</td><td>w<sub>13</sub> &le; &sigma;</td><td>w<sub>24</sub> &le; &sigma;</td></tr><tr><td>(8)</td><td>"</td><td>"</td><td>"</td><td>w<sub>13</sub> &le; &sigma;</td><td>w<sub>24</sub> &le; &sigma;</td></tr><tr><td>(9)</td><td>"</td><td>"</td><td>"</td><td>w<sub>13</sub> &le; &sigma;</td><td>w<sub>24</sub> &gt; &sigma;</td></tr><tr><td>(10)</td><td>"</td><td>"</td><td>"</td><td>w<sub>13</sub> &le; &sigma;</td><td>w<sub>24</sub> &gt; &sigma;</td></tr><tr><td>(11)</td><td>"</td><td>"</td><td>"</td><td>w<sub>13</sub> &gt; &sigma;</td><td>w<sub>24</sub> &le; &sigma;</td></tr><tr><td>(12)</td><td>"</td><td>"</td><td>"</td><td>w<sub>13</sub> &gt; &sigma;</td><td>w<sub>24</sub> &le; &sigma;</td></tr><tr><td>(13)</td><td>"</td><td>"</td><td>"</td><td>w<sub>13</sub> &gt; &sigma;</td><td>w<sub>24</sub> &gt; &sigma;</td></tr><tr><td>(14)</td><td>"</td><td>"</td><td>"</td><td>w<sub>13</sub> &gt; &sigma;</td><td>w<sub>24</sub> &gt; &sigma;</td></tr></tbody></table>

First, for cases (1), (2), (3), (5), (7), (8), (9), (11), (12), and (14), it can be verified that each row in the associated transition matrix $T(t)$ sums up to at most 1. Hence, since $w_i(t) \le \sigma$ for all $i \in \{1, ..., 4\}$, the next spacings vector satisfies

$$w(t+1) = T(t)w(t) \le T(t)(\sigma e) = \sigma(T(t)e) \le \sigma e.$$

Therefore, $w_i(t+1) \le \sigma$ for all $i \in \{1, ..., 4\}$ so that the $\sigma$-chain of each of these cases remains intact.

For case (4), the transition matrix is given by

$$T_4(t) = \frac{1}{20} \begin{bmatrix} 6 & 12 & 8 & 4 \\ 4 & 3 & 2 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}.$$

Note that $T_4(t)e = (1\frac{1}{2}, 1\frac{1}{2}, 0, 0)$. Since all but the first row sum up to at most 1, it follows that $w_2(t+1)$, $w_3(t+1)$, $w_4(t+1) \le \sigma$, so that links $\{2, 3\}$, $\{3, 4\}$, $\{4, 5\}$ remain intact. As for link $\{1, 2\}$, note that

$$w_1(t+1) = \frac{1}{20} (6w_1 + 12w_2 + 8w_3 + 4w_4) = \frac{1}{20} \left( 6 \underbrace{w_1}_{\le \sigma} + 4 \underbrace{w_2}_{\le \sigma} + 4 \underbrace{w_24}_{\le \sigma} + 4 \underbrace{w_{25}}_{\le \sigma} \right) \le \frac{18}{20}\sigma,$$

where the conditions on $\sigma$-chains of case (6) as given in Table 4 were used. Since $w_1(t+1) \le \sigma$, link $\{1, 2\}$ also remains intact, so that $\sigma$-chains of case (4) remain intact.

Case (6) is symmetric to case (4).

For case (10), the transition matrix is given by

$$T_{10}(t) = \frac{1}{12} \begin{bmatrix} 0 & 0 & 0 & 0 \\ 1 & 2 & 3 & 0 \\ 3 & 6 & 5 & 4 \\ 0 & 0 & 4 & 2 \end{bmatrix}.$$

Note that $T_{10}(t)e = (0, 1\frac{1}{2}, 1\frac{1}{2}, 1\frac{1}{2})$. Since all but the third row sum up to at most 1, the links $\{1, 2\}$, $\{2, 3\}$ and $\{4, 5\}$ remain intact. As for the link $\{3, 4\}$, it can break or not break. An example where link $\{3, 4\}$ breaks is given by $\sigma = 0.1$ together with opinion vector $x(t) = (0, 0.05, 0.10, 0.20, 0.30)$ and associated
spacings vector $w(t) = (0.05, 0.05, 0.10, 0.10)$, where can verify that the conditions of case (10) are satisfied and we obtain

$$w_3(t + 1) = \frac{1}{12} (3 \cdot 0.05 + 6 \cdot 0.05 + 5 \cdot 0.10 + 4 \cdot 0.10) = \frac{9}{80} > \frac{1}{10}.$$

An example where link {3, 4} does not breaks is given by $\sigma = 0.1$ together with opinion vector $x(t) = (0, 0.01, 0.02, 0.12, 0.22)$ and associated spacings vector $w(t) = (0.01, 0.01, 0.10, 0.10)$, where one can verify that the conditions of case (10) are satisfied and we obtain

$$w_3(t + 1) = \frac{1}{12} (3 \cdot 0.01 + 6 \cdot 0.01 + 5 \cdot 0.10 + 4 \cdot 0.10) = \frac{33}{400} \le \frac{1}{10}.$$

Therefore, $\sigma$-chains of case (10) disintegrate if and only if

$$\frac{1}{12} (3w_1 + 6w_2 + 5w_3 + 4w_4) > \sigma.$$

Case (13) is symmetric to case (10).

## A.4 Proof of Lemma 4.1

Suppose that $a + \sigma \ge 1 - c$. We may suppose that $a + \sigma \le 1 - b$, as on the figure (the other case is simpler). Then the blue area is $(b - a)h_a + (1 - a - b - \sigma)h_b =: S_\sigma$. The average opinion over the blue part is

$$x_{\sigma} = \frac{1}{S_{\sigma}} \left[ (b-a)h_a \frac{(2-a-b)}{2} + (1-a-b-\sigma)h_b \frac{1+a-b+\sigma}{2} \right].$$

Recall that if we average over the whole density (blue part + white part), then we get $1/2$. Consequently, the quantity $\alpha(a)$ satisfies:

$$\frac{1}{2} = \frac{S_{\sigma}x_{\sigma} + (1 - S_{\sigma})\alpha(a)}{S_{\sigma}},$$

which yields

$$\alpha(a) = \frac{S_{\sigma}(1 - 2x_{\sigma})}{2(1 - S_{\sigma})}.$$

Now, if $x = b$, we have $\alpha(b) = \frac{1}{2}$, since the whole density is covered by $[l(b), r(b)]$. Hence, the interval $[a, b]$ on $f_2$ has been changed to the interval $[\alpha(a), 1/2]$, so that the density $f_3$ on the latter interval has height $h_a \frac{(b-a)}{1/2 - \alpha(a)}$.

If $x \in [b, 1/2]$, the whole density is covered, so that $\alpha(x) = 1/2$. It follows that the density at $1/2$ is a Dirac impulse. By symmetry, we obtain the density $f_3$ on the right of $1/2$. Consequently, the density $f_3$ exhibits one cluster centered at $1/2$.

# B Computation of the density $f_2(x)$ with a continuum of agents

## B.1 Case $\sigma \in [0, 1/4]$

We have to compute $\alpha_2(x_1)$ for $x_1 = \sigma/2$, $\sigma$, $3\sigma/2$, $2\sigma$.

**Computation for** $x_1 = \sigma/2$. Let us compute $\alpha_2(x_1)$. We have $[l(\sigma/2), r(\sigma/2)] = [\sigma/2, 3\sigma/2]$. We note that $3\sigma/2 < 1 - \sigma$, so that the interval does not intersect the right rectangle of height 2, but only the left rectangle of height 2 and the central rectangle of height 1 (on $f_1$). Therefore, the computation is done as follows (we compute the barycenter):

$$\alpha_2\left(\frac{\sigma}{2}\right) = \frac{2 \times \frac{3\sigma}{4} + 1 \times \frac{5\sigma}{4}}{2 + 1} = \frac{11\sigma}{12}.$$
(Explanation: we consider the rectangle of height 2 and width $\sigma/2$, on which the mean opinion is $3\sigma/4$, and the rectangle of height 1 and width $\sigma/2$ on which the mean opinion is $5\sigma/4$. The mean opinions are averaged, weighed by the surfaces of the respective rectangles, divided by the total surface).

**Computation for $x_1 = \sigma$.** Then $[l(\sigma), r(\sigma)] = [\sigma/2, 2\sigma]$. We observe that $2\sigma < 1 - \sigma$.

Proceeding as above to compute $\alpha_2(x_1)$, we have to take the rectangle of height 2 and width $\sigma/2$ and the rectangle of height 1 and width $\sigma$. This yields

$$\alpha_2(\sigma) = \frac{\frac{3\sigma}{4} + \frac{3\sigma}{2}}{2} = \frac{9\sigma}{8}.$$

**Computation for $x_1 = 3\sigma/2$.** This yields $[l(3\sigma/2), r(3\sigma/2)] = [\sigma/2, 5\sigma/2]$. We observe that $5\sigma/2 < 1 - \sigma$.

Therefore, in order to compute $\alpha_2(x_1)$, we take the rectangle of height 2 and width $\sigma/2$ and the rectangle of height 1 and width $3\sigma/2$. This yields

$$\alpha_2\left(\frac{3\sigma}{2}\right) = \frac{\frac{3\sigma}{4} + \frac{3}{2}\frac{7\sigma}{4}}{1 + \frac{3}{2}} = \frac{27\sigma}{20}.$$

**Computation for $x_1 = 2\sigma$.** We obtain $[l(2\sigma), r(2\sigma)] = [\sigma, 3\sigma]$. Observe that $3\sigma \le 1 - \sigma$. This yields

$$\alpha_2(2\sigma) = \frac{4\sigma}{2} = 2\sigma.$$

Observe also that $\alpha_2(x) = x$ for all $x \in [2\sigma, 1/2]$.

**Computation of the density $f_2$.** We do a rectangle approximation, in the sense that for each rectangle in $f_1$ delimited by two values $x_1, x'_1$, we compute the height of the corresponding rectangle in $f_2$ delimited by $\alpha_2(x_1), \alpha_2(x'_1)$, so as to make the surface invariant.

* The interval $[\sigma/2, \sigma]$ on $f_1$ (height = 2) is transformed in the interval $[11\sigma/12, 9\sigma/8]$. The ratio of widths is

$$r = \frac{\frac{\sigma}{2}}{\frac{9\sigma}{8} - \frac{11\sigma}{12}} = \frac{12}{5}.$$

Hence, a rectangle approximation of the density $f_2$ on this interval has height $2r = \frac{24}{5}$.

* The interval $[\sigma, 3\sigma/2]$ on $f_1$ (height = 1) is transformed in the interval $[9\sigma/8, 27\sigma/20]$. Then

$$r = \frac{\frac{\sigma}{2}}{\frac{27\sigma}{20} - \frac{9\sigma}{8}} = \frac{20}{9}.$$

Hence the rectangle approximation of $f_2$ on this interval has height $r = \frac{20}{9}$.

* The interval $[3\sigma/2, 2\sigma]$ on $f_1$ (height = 1) is transformed in the interval $[27\sigma/20, 2\sigma]$. Then

$$r = \frac{\frac{\sigma}{2}}{2\sigma - \frac{27\sigma}{20}} = \frac{10}{13}.$$

The height of (the rectangle approximation of) $f_2$ is then $r = \frac{10}{13}$.

* The interval $[2\sigma, 1/2]$ is invariant, so its height remains equal to 1.

The density is represented on Fig. 5.

## B.2 Case $\sigma \in [1/4, 2/7]$

We have to compute $\alpha_2(x_1)$ for $x_1 = \sigma/2$, $\sigma$, $3\sigma/2$, $1 - 2\sigma$.
**Computation for $x_1 = \sigma/2$.** There is no change w.r.t. the case $\sigma \le 1/4$, hence $\alpha_2(\sigma/2) = 11\sigma/12$.

**Computation for $x_1 = \sigma$.** There is no change w.r.t. the case $\sigma \le 1/4$, hence $\alpha_2(\sigma/2) = 9\sigma/8$.

**Computation for $x_1 = 3\sigma/2$.** There is no change w.r.t. the case $\sigma \le 1/4$, hence $\alpha_2(\sigma/2) = 27\sigma/20$.

**Computation for $x_1 = 1 - 2\sigma$.** Then $[l(1 - 2\sigma), r(1 - 2\sigma)] = [1 - 3\sigma, 1 - \sigma]$. We have to take the whole central rectangle and a part of width $4\sigma - 1$ of the left rectangle:

$$ \alpha_2(1 - 2\sigma) = \frac{(1 - 2\sigma)(4\sigma - 1) + \frac{1-2\sigma}{2}}{2(4\sigma - 1) + 1 - 2\sigma} = \frac{(1 - 2\sigma)(8\sigma - 1)}{12\sigma - 2}. $$

**Computation of the density $f_2$.**

* For the two first intervals, there is no change w.r.t. the case $\sigma \le 1/4$.

* The interval $[3\sigma/2, 1 - 2\sigma]$ on $f_1$ (height=1) is transformed into the interval $[27\sigma/20, \frac{(1-2\sigma)(8\sigma-1)}{12\sigma-2}]$. Then

$$ r = \frac{1 - \frac{7\sigma}{2}}{\frac{(1-2\sigma)(8\sigma-1)}{12\sigma-1} - \frac{27\sigma}{20}} = \frac{10(2 - 7\sigma)(6\sigma - 1)}{-322\sigma^2 + 127\sigma - 10}, $$

which is the height of $f_2$. Observe that for $\sigma = 1/4$, this yields 10/13. For $\sigma = 2/7$, the interval $[3\sigma/2, 1 - 2\sigma]$ reduces to the point 3/7, so there is no rectangle any more.

* The interval $[1 - 2\sigma, 1/2]$ (height =1) is transformed into the interval $[\frac{(1-2\sigma)(8\sigma-1)}{12\sigma-2}, 1/2]$. Then the height of $f_2$ is

$$ r = \frac{2\sigma - \frac{1}{2}}{\frac{1}{2} - \frac{(1-2\sigma)(8\sigma-1)}{12\sigma-1}} = \frac{6\sigma - 1}{4\sigma}. $$

For $\sigma = 1/4$, the interval $[1 - 2\sigma, 1/2]$ reduces to the point 1/2, hence the rectangle disappears. For $\sigma = 2/7$, we obtain 5/8.

In summary, the density has the same shape as in the case $\sigma \in [0, 1/4]$ (see Fig. 13). For the limit cases $\sigma = 1/4$ or $2/7$, one of the rectangles in the center disappears.

<figure><img src="image_27.png" /><figcaption>Figure 13: Step $t = 2$ with $\sigma \in [1/4, 2/7]$ ($\sigma = 0.26$).</figcaption></figure>
### B.3 Case $\sigma \in [2/7, 1/3]$

We have to compute $\alpha_2(x_1)$ for $x_1 = \sigma/2$, $\sigma$, $1 - 2\sigma$, $3\sigma/2$.

**Computation for $x_1 = \sigma/2$.** There is no change w.r.t. the case $\sigma \le 1/4$, hence $\alpha_2(\sigma/2) = 11\sigma/12$.

**Computation for $x_1 = \sigma$.** There is no change w.r.t. the case $\sigma \le 1/4$, hence $\alpha_2(\sigma/2) = 9\sigma/8$.

**Computation for $x_1 = 1 - 2\sigma$.** Then $[l(1 - 2\sigma), r(1 - 2\sigma)] = [1 - 3\sigma, 1 - \sigma]$. We have to take the whole left rectangle and the whole central rectangle. This yields

$$ \alpha_2(1 - 2\sigma) = \frac{\sigma \frac{3\sigma}{4} + (1 - 2\sigma) \frac{1}{2}}{\sigma + 1 - 2\sigma} = \frac{3\sigma^2 - 4\sigma + 2}{4(1 - \sigma)} $$

When $\sigma = 2/7$ and $1/3$, we obtain $\alpha_2(1 - 2\sigma) = 27/70$ and $3/8$, respectively.

**Computation for $x_1 = 3\sigma/2$.** Then $[l(1 - 2\sigma), r(1 - 2\sigma)] = [\sigma/2, 5\sigma/2]$. We have to consider the left rectangle of height 2 and width $\sigma/2$, the rectangle of height 1 and width $1 - 2\sigma$, and the right rectangle of height 2 and width $7\sigma/2 - 1$. This yields

$$ \alpha_2 \left( \frac{3\sigma}{2} \right) = \frac{\frac{3\sigma^2}{4} + \frac{(1-2\sigma)}{2} + \frac{(7\sigma-2)(3\sigma+2)}{4}}{\sigma + 1 - 2\sigma + 7\sigma - 2} = \frac{12\sigma^2 + 2\sigma - 1}{12\sigma - 2} $$

When $\sigma = 2/7$ and $1/3$, we obtain $\alpha_2(3\sigma/2) = 27/70$ and $1/2$, respectively.

**Computation of the density $f_2$**

* For the first interval $[\sigma/2, \sigma]$, there is no change w.r.t. the case $\sigma \in [1/4, 2/7]$.

* The interval $[\sigma, 1 - 2\sigma]$ on $f_1$ (height 1) is transformed into the interval $[9\sigma/8, \frac{3\sigma^2 - 4\sigma + 2}{4(1 - \sigma)}]$. Then the height is

$$ r = \frac{1 - 3\sigma}{\frac{3\sigma^2 - 4\sigma + 2}{4(1 - \sigma)} - \frac{9\sigma}{8}} = \frac{8(1 - 3\sigma)(1 - \sigma)}{15\sigma^2 - 17\sigma + 4} $$

We get $r = 20/9$ for $\sigma = 2/7$. For $\sigma = 1/3$, the interval $[\sigma, 1 - 2\sigma]$ reduces to the point $1/3$, so the rectangle disappears.

* The interval $[1 - 2\sigma, 3\sigma/2]$ (height 1) is transformed into the interval $[\frac{3\sigma^2 - 4\sigma + 2}{4(1 - \sigma)}, \frac{12\sigma^2 + 2\sigma - 1}{12\sigma - 2}]$. Then the height is

$$ r = \frac{\frac{3\sigma}{2} - 1 + 2\sigma}{\frac{12\sigma^2 + 2\sigma - 1}{12\sigma - 2} - \frac{3\sigma^2 - 4\sigma + 2}{4(1 - \sigma)}} = \frac{2(7\sigma - 2)(1 - \sigma)(6\sigma - 1)}{\sigma(-42\sigma^2 + 47\sigma - 10)} $$

This yields $r = 4/3$ for $\sigma = 1/3$. For $\sigma = 2/7$, the interval $[1 - 2\sigma, 3\sigma/2]$ reduces to the single point $3/7$, so the rectangle disappears.

* The interval $[3\sigma/2, 1/2]$ is transformed into the interval $[\frac{12\sigma^2 + 2\sigma - 1}{12\sigma - 2}, 1/2]$. Then the height is

$$ r = \frac{\frac{1}{2} - \frac{3\sigma}{2}}{\frac{1}{2} - \frac{12\sigma^2 + 2\sigma - 1}{12\sigma - 2}} = \frac{6\sigma - 1}{4\sigma} $$

(second expression valid only if $\sigma \ne 1/3$). This yields $r = 5/8$ for $\sigma = 2/7$. For $\sigma = 1/3$, the interval $[3\sigma/2, 1/2]$ reduces to the point $1/2$, hence the rectangle disappears.

In summary, the density has the same shape as in the case $\sigma \in [0, 1/4]$ (see Fig. 14). For the limit cases $\sigma = 2/7$ or $1/3$, one of the rectangles in the center disappears.
<figure><img src="image_28.png" /><figcaption>Figure 14: Step $t = 2$ with $\sigma \in [2/7, 1/3]$ ($\sigma = 0.3$).</figcaption></figure>