# On the design of public debate in social networks

Michel Grabisch, Antoine Mandel, Agnieszka Rusinowska

► To cite this version:

Michel Grabisch, Antoine Mandel, Agnieszka Rusinowska. On the design of public debate in social networks. 2022. halshs-03531788

HAL Id: halshs-03531788

https://shs.hal.science/halshs-03531788

Submitted on 18 Jan 2022

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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
CES

Centre d'Économie de la Sorbonne
UMR 8174

On the design of public debate in social networks

Michel GRABISCH, Antoine MANDEL, Agnieszka RUSINOWSKA

2022.01
# On the design of public debate in social networks

Michel Grabisch<sup>(a)(b)</sup>, Antoine Mandel<sup>(a)(b)</sup>; Agnieszka Rusinowska<sup>(a)(c)</sup>

<sup>(a)</sup> Centre d'Economie de la Sorbonne

106-112 Bd de l'Hôpital, 75647 Paris, France

<sup>{michel.grabisch,antoine.mandel,agnieszka.rusinowska}@univ-paris1.fr</sup>

<sup>(b)</sup> Paris School of Economics, Université Paris 1 Panthéon-Sorbonne

<sup>(c)</sup> Paris School of Economics, CNRS

January 4, 2022

## Abstract

We propose a model of the joint evolution of opinions and social relationships in a setting where social influence decays over time. The dynamics are based on bounded confidence: social connections between individuals with distant opinions are severed while new connections are formed between individuals with similar opinions. Our model naturally gives raise to strong diversity, i.e., the persistence of heterogeneous opinions in connected societies, a phenomenon that most existing models fail to capture. The intensity of social interactions is the key parameter that governs the dynamics. First, it determines the asymptotic distribution of opinions. In particular, increasing the intensity of social interactions brings society closer to consensus. Second, it determines the risk of polarization, which is shown to increase with the intensity of social interactions. Our results allow to frame the problem of the design of public debates in a formal setting. We hence characterize the optimal strategy for a social planner who controls the intensity of the public debate and thus faces a trade-off between the pursuit of social consensus and the risk of polarization. We also consider applications to political campaigning and show that both minority and majority candidates can have incentives to lead society towards polarization.

**JEL Classification:** D85, C65, D83

**Keywords:** opinion dynamics, network formation, network fragility, polarization, institution design, political campaign

## 1 Introduction

In his essay on the “spaces of democracy”, Sennett [1998] draws a simple but powerful sketch of efficient institutions *“A democracy supposes that people can consider views other”*

<footnote>*Corresponding author.</footnote>
than their own. This was Aristotle's notion in the Politics. He thought that the awareness
of difference occurs only in cities because every city is formed by synoikismos, a drawing
together of different families and tribes, of competing economic interests, of natives with
foreigners." This definition provides a clear objective for a social planner in the facilitation
of social interactions and the design of deliberative institutions: he or she ought to ensure
that diverse opinions can be sustained and debated while ensuring social cohesion.

In this paper, we provide a model of the co-evolution of opinions and social relations
that allow to frame this problem in a formal setting. We highlight that the social planner
faces a trade-off between fostering the convergence of opinions in society and increasing
the risk of polarization and instability. We show that to resolve this trade-off, he must
account for both structural and behavioral characteristics: how fragile is the social net-
work and to which extent individuals tolerate disagreement with their peers. We thus
provide a theory of the efficient design of public debate.

The prerequisite for such a theory is to develop a model of opinion dynamics that
account for the persistence of heterogeneous opinions in society [strong diversity in the
sense of Friedkin and Johnsen, 1990] and for the dynamic interactions between opinions
and social connections. The existing literature on opinion dynamics, following the seminal
contributions by French and DeGroot [French, 1956, DeGroot, 1974], has to a large extent
focused on the emergence of social consensus [see e.g. DeMarzo et al., 2003, Golub and
Jackson, 2010] but for the notable exception of Acemoglu et al. [2013], which shows
that the presence of stubborn agents can generate long-run disagreements and persistent
opinion fluctuations. The interplay between opinion dynamics and social connections
has been investigated in a number of contributions based on the “bounded-confidence
model” of Hegselmann and Krause [2002] but these consider only “weak diversity” in the
sense that diversity of opinions and social connectivity are asymptotically incompatible
(i.e., agents with different opinions must belong to different connected components of the
network).

Our model is formally close to the DeGroot and Hegselmann-Krause models as we
consider linear updating of opinions and that social connections break (resp., form) when
differences in opinions are above (resp., below) a certain threshold. However, a key dis-
tinctive feature of our approach is that we consider that social influence on opinions
decays over time. This leads to major qualitative differences. First and foremost, hetero-
geneous opinions can persist asymptotically within a connected network. Second, initial
conditions matter: the initial opinion of an individual influences both its asymptotic
opinion and its network position. Third, the mutual influence between two agents is
related to their social distance whereas in DeGroot’s type of models it is independent of
the distance and determined only by centrality.

Two main parameters govern the dynamics of our model: the intensity of social in-
teractions (or equivalently the speed at which opinions are crystalized) and the threshold
above which agents with different opinions sever their connection (resp., the threshold be-
low which they create a connection). Our first result is to provide a characterization of the
fragility of network links, i.e., of their propensity to break due to the evolution of opinions.
This characterization is based on the local structure of the network and independent of
the model’s parameters. From this local measure of link fragility, we derive network-level
measures of fragility, i.e., propensity to lose a link, and polarizability, i.e., propensity to
become disconnected. The network fragility, the intensity of interactions and the opinion
threshold determine the risk of polarization. We provide an explicit characterization of the maximal intensity of interaction for which one can guarantee the stability of the network as a function of its fragility/polarizability and of the opinion threshold. We then provide a complete analytical characterization of the asymptotic distribution of opinions in our setting. In particular, we show that the level of social consensus (i.e., the difference between the two most extreme opinions) decreases with the intensity of the debate. Overall, we demonstrate the existence of a trade-off between fostering the convergence of opinions and increasing the risk of polarization and instability.

We first investigate this trade-off from the view point of a social planner. We provide an explicit characterization of the level of interactions/debate that optimally balances the pursuit of social consensus with the risk of polarization. We show that the social planner must account for both structural (fragility of the network) and behavioral (opinion threshold) characteristics. We further investigate the impact that strategic parties/candidates can have on polarization by influencing the intensity of the public debate. We show that both the majority and the minority can have incentives to foster polarization. This strongly calls for precise regulation and independent oversight of political debates.

## Related literature

Opinion and beliefs are key determinants of individual and social decisions. Accordingly, their dynamic has been extensively investigated in a number of disciplines ranging from economics to computer science through sociology or statistical physics. A series of recent surveys, Golub and Sadler [2016], Anderson and Ye [2019], Sîrbu et al. [2017] highlight the specific approach of each discipline to the issue. Still, the common roots of these approaches are the seminal contributions by French [1956] and DeGroot [1974] who have introduced linear models of the evolution of opinions in a population.

Two major weaknesses have however been identified in the DeGroot model. First, the repetition of information: agents integrate their neighbours' opinions with a time-invariant weight despite the fact that the amount of (new) information transmitted decreases over time. Second, confidence in another agent's opinion is constant over time, despite the fact that opinions can become very dissimilar. The first issue is addressed by DeMarzo et al. [2003], which introduces time-varying weights in the DeGroot model. The second issue is addressed by bounded-confidence models. In this latter strand of literature, the seminal contribution by Hegselmann-Krause (see e.g., Krause [2000], Dittmer [2001], Hegselmann and Krause [2002]) model the dynamics of opinions in a setting where agents can only be influenced by peers with similar-enough opinions. More broadly, a large literature has investigated the role of homophily in social influence by considering the interplay between network structure and opinion dynamics (see e.g. Friedkin and Johnsen [1990], Deffuant et al. [2001], DeMarzo et al. [2003], Kozma and Barrat [2008], Golub and Jackson [2010]). Our model is, to our knowledge, the first to combine homophily/bounded-confidence with time-varying weights. It furthermore goes beyond the state of the art in both directions. With respect to information repetition, although DeMarzo et al. [2003] considers time-varying weight, the repetition of information still drives the convergence of the model towards a consensus while in our setting information decays exponentially fast. With respect to the literature on bounded confidence, we provide the first analytical characterization of the stability and of the polarizability of a
network.

In this latter respect, our work relates to a range of contributions that seek to explain polarization (in particular, bi-polarization) in opinion dynamics. Within this literature, early contributions such as Latané et al. [1994] and DiMaggio et al. [1996], Axelrod [1997] have put forward the major policy implications of social polarization and have shown it was amenable to a quantitative analysis. Recent contributions, notably Dandekar et al. [2013], Shi et al. [2016], Banisch and Olbrich [2019], Bolletta and Pin [2019], Shabayek [2020], have highlighted the role of social networks and individual behavior in the emergence of polarization.

More broadly, our work relates to the literature that analyses the impact of the structure of social networks on the distribution of opinions in society. Our result on the asymptotic behavior of opinions shows that, even if there is no polarization, there need not be a consensus in the network (contrarily to most models). This is related to the analysis of strong diversity versus weak diversity. While various models focus on weak diversity (Anderson and Ye [2019], Mäs et al. [2014]) meaning that opinion consensus is reached within each group (or cluster) and heterogeneity persist across groups, there is a growing interest in models which can capture strong diversity where different opinions can persist within a group [Friedkin and Johnsen, 1990]. In a series of contributions, Ace moglu et al. [2010, 2013], Yildiz et al. [2013], it is shown that the presence of stubborn agents (i.e., with a fixed opinion) can generate strong diversity (long-run disagreements) and persistent opinion fluctuations. In our setting, strong diversity also emerges from some form of stubbornness, but understood as the progressive crystallization of opinions rather than as a feature of a specific class of agents.

The remaining of the paper is organized as follows. Basic definitions of our framework and some structural properties of the dynamics are presented in Section 2. Section 3 analyzes the determinants of link fragility and network polarization. The convergence and asymptotic distribution of opinions are analyzed in Section 4. Section 5 analyzes the trade-off between convergence and polarization from the point of view of a social planner and that of political actors. Some concluding remarks are provided in Section 6. The appendix provides a detailed presentation of related models of opinion dynamics, additional results on network stability and the proofs of all results in the paper.

# 2 The model

## 2.1 General framework

We consider a fixed set of agents $\mathcal{N} = \{1, \dots, N\}$, having social relationships among them and holding opinions on a given topic, both supposed to vary with time. We assume that time is discrete. At each point of time $t \in \mathbb{N}$, the society is characterized by the vector of opinions $x(t) \in [-1, 1]^N$ held by the agents, and the set of social relationships is represented by an undirected graph (network) on $\mathcal{N}$, whose set of undirected edges (links) is denoted by $\mathcal{G}(t) \subseteq [\mathcal{N}]^2$, where $[\mathcal{N}]^2$ denotes the set of subsets of $\mathcal{N}$ with 2 elements, augmented with the “self-loops” $\{i, i\}, i \in \mathbb{N}$. We assume that $\{i, i\} \in \mathcal{G}(t)$ for all $t \in \mathbb{N}$ and $i \in \mathcal{N}$.

We denote by $\mathcal{G}(t)$ the $N \times N$ weight matrix of the graph $\mathcal{G}(t)$, where $G_{ij}(t)$ is the
confidence level of agent i in the opinion of agent j. Unless otherwise specified<fnref n="1" />, we shall assume in the following that the network is uniformly weighted, i.e., that $G_{ij}(t)$ is such that

$$G_{ij}(t) := \begin{cases} \frac{1}{\deg(i, \mathcal{G}(t))} & \text{if } \{i, j\} \in \mathcal{G}(t) \\ 0 & \text{otherwise} \end{cases} \qquad (1)$$

where $\deg(i, \mathcal{G}(t))$ denotes the degree of $i$ in $\mathcal{G}(t)$. Note that an isolated node $i$ has degree 1, because of the self-loop $\{i, i\}$.

We then describe the dynamics of the opinion vector and of the graph of social relationships, which are intertwined. At each step, opinions are updated first, then the network is updated.

(i) The opinion dynamics has the form

$$x(t + 1) = [\lambda^t G(t) + (1 - \lambda^t)I]x(t) \qquad (2)$$

for some $\lambda \in [0, 1]$, representing the speed at which opinions are crystalized, and with $I$ denoting the identity matrix of $\mathbb{R}^N$.

(ii) The dynamics of the network of social relationships are given by

$$\mathcal{G}(t+1) = \mathcal{G}(t) \cup \{\{i, j\} \in [\mathcal{N}]^2 : |x_i(t+1) - x_j(t+1)| < \tau\} \\ \setminus \{\{i, j\} \in [\mathcal{N}]^2 : |x_i(t+1) - x_j(t+1)| \ge \sigma\} \quad (3)$$

where $0 \le \tau \le \sigma \in \bar{\mathbb{R}}_+ = [0, +\infty]$. In other words, agents whose opinions differ from more than the threshold $\sigma$ terminate their relationships and agents whose opinions differ less than the threshold $\tau$ create a relationship.

In the following, we shall refer to the dynamical system defined by Equations (2) and (3) as an (opinion-) network formation process. This framework subsumes a number of models of opinion dynamics previously considered in the literature<fnref n="2" />. If we consider $\tau = 0$ and $\sigma = +\infty$, we retrieve models of opinion dynamics in a fixed network. In particular for $\lambda = 1$, we retrieve the French-DeGroot model (French [1956], DeGroot [1974]). For $\sigma = \tau$, $\lambda = 1$ and $\mathcal{G}(0)$ set to the complete network, we retrieve bounded confidence models (Krause [2000], Dittmer [2001], Hegselmann and Krause [2002]). Models of opinion dynamics within a fixed network generally focus on the emergence of a consensus and the relative impact of each agent on this consensus. Bounded confidence models focus on the emergence of disconnected clusters with local consensus.

Our approach introduces two new features that allow to build a more precise theory of the joint evolution of opinions and social interactions. First, we let social influence decay over time by introducing the coefficient $\lambda \in [0, 1]$. This implies that opinion formation is not entirely determined by asymptotic properties of the diffusion process, as in

<footnote n="1">¹In particular, the results in Section 4.1 are valid for an arbitrary weight matrix.</footnote>

<footnote n="2">²The appendix provides a detailed presentation of existing models and discusses their relation to our approach.</footnote>
the standard models of DeGroot [1974] and DeMarzo et al. [2003], but rather that transient dynamics and the initial distribution of opinions matter more. This also mitigates the persuasion bias identified in the existing literature when the same information is accounted for multiple times in opinion formation (in our setting information is accounted for multiple times but with a decaying weight). Second, we provide a finer and more general description of the evolution of the network than in standard bounded confidence models by considering an arbitrary initial network $G(0)$ and different thresholds, $\sigma$ and $\tau$, for the destruction and the creation of links (in particular we let $\tau = +\infty$ in Section 3.2). This allows to identify the impact of the initial structure of the network on emerging dynamics. More broadly, our extended framework allows to model <fnref n="3" /> the emergence of strong diversity, i.e., the persistence of heterogeneous opinions in a connected network, as opposed to weak diversity, i.e., the decomposition of the network in disconnected clusters with local consensus as observed in standard bounded confidence models. Finally, it allows to develop a theory of the design of public debate in social networks by analyzing how the intensity of public debate controls the trade-off between the risk of polarization and the search for social consensus.

## 2.2 Compatible opinion networks

In our setting, as links are created and deleted as a function of the distance between opinions, network structure ought to be strongly linked with the structure of opinions. In fact, the network tends to self-organize into a structure where the network neighborhoods of the agents are ordered in a manner consistent with the ordering of their opinions. Namely, let us denote by $N_G(i)$ the set of neighbors<fnref n="4" /> of $i$ in the network $G$ and define the left extreme and right extreme neighbors of $i \in \mathcal{N}$ as the agents $n_-(G, i)$ and $n_+(G, i)$ (we shall denote simply $n_-(i)$ and $n_+(i)$ for $n_-(G, i)$ and $n_+(G, i)$ in absence of ambiguity) such that:

$$x_{n_-(G, i)} := \min_{j \in N_G(i)} x_j \text{ and } x_{n_+(G, i)} := \max_{j \in N_G(i)} x_j$$

One shall then say that a network opinion pair is compatible if the ordering of opinions and network neighborhoods are consistent in the following sense.

**Definition 1** A pair $(x, G)$ is compatible if

* For all $i, j$, one has:

$$x_i \le x_j \Rightarrow (x_{n_-(i)} \le x_{n_-(j)}) \text{ and } (x_{n_+(i)} \le x_{n_+(j)})$$

* The neighborhood $N_G(i)$ of $i$ in $G$ is such that any agent $j$ with $x_{n_-(i)} \le x_j \le x_{n_+(i)}$ belongs to $N_G(i)$.

One can then remark that, if $\sigma = \tau$, the network formation process systematically leads to a compatible network opinion pair (proofs are given in the appendix).

<footnote n="3">³See Section 4.</footnote>

<footnote n="4">⁴By the existence of the self-loop, $i \in N_G(i)$.</footnote>
**Remark 1** If $\sigma = \tau \in \mathbb{R}_+$, for any initial network opinion pair, the network formation process leads in one step to a pair $(x(1), \mathcal{G}(1))$ such that for all $\{i, j\} \in [\mathcal{N}]^2$, one has:

$$|x(1)_i - x(1)_j| < \sigma \Leftrightarrow \{i, j\} \in \mathcal{G}(1)$$

and such a pair is compatible.

Arbitrary network formation processes lead to a compatible network opinion pair provided the initial distribution of opinions and the networks are initially consistent in the following sense.

**Remark 2** Assume that an initial opinion pair $(x(0), \mathcal{G}(0))$ is $(\sigma, \tau)$-consistent, for $\tau \le \sigma$, in the sense that for all $\{i, j\} \in [\mathcal{N}]^2$, one has:

$$\{i, j\} \in \mathcal{G}(0) \Rightarrow |x(0)_i - x(0)_j| < \tau \quad \text{and} \quad \{i, j\} \notin \mathcal{G}(0) \Rightarrow |x(0)_i - x(0)_j| \ge \sigma.$$

Then $(x(0), \mathcal{G}(0))$ is compatible in the sense of Definition 1 and, furthermore, for all $t \ge 0$, $(x(t), \mathcal{G}(t))$ remains $(\sigma, \tau)$-consistent.

Note that the property does not hold for arbitrary initial opinion pair because there are no constraints on the links between nodes whose difference in opinions is in $]\tau, \sigma[$.

Finally, the compatibility of a network opinion pair is preserved by the network formation process. More precisely, one has the following Lemma.

**Lemma 1** Let $(x(t), \mathcal{G}(t))$ be a compatible network-opinion pair. Then for any network formation process, one has:

(i) If $x_i(t) = x_j(t)$ then $x_i(t') = x_j(t')$ for all $t' \ge t$.

(ii) $x_i(t) < x_j(t)$ implies $x_i(t') \le x_j(t')$ for all $t' \ge t$, with strict inequality if $\lambda \ne 1$.

(iii) $(x(t'), \mathcal{G}(t'))$ is compatible for all $t' \ge t$.

Note that Property (ii) is a generalization of a classical result for the Hegselmann-Krause model (which corresponds to the case $\lambda = 1$ and $\sigma = \tau$).

Consistently with the above remarks, we shall focus in the following on compatible network-opinion pairs. In this setting, it shall prove useful to consider that agents are ordered by increasing opinions, i.e., $x_1 < x_2 < \dots < x_N$. Indeed, one can then remark that a pair $(x, \mathcal{G})$ is compatible if and only if the neighborhoods of agents are intervals whose end-points are ordered accordingly, i.e., for all $i, j$, one has<fnref n="5" />:

$$i < j \Rightarrow \{n_-(i) \le n_-(j), n_+(i) \le n_+(j) \text{ and } N_{\mathcal{G}}(i) \text{ is the interval } [n_-(i), n_+(i)]\}$$

We shall assume in the following that agents are initially ordered by increasing opinion value. According to Lemma 1, they will always remain ordered in this way.

<footnote n="5">⁵See also the corresponding definition in Bolletta and Pin [2019].</footnote>
# 3 Network fragility and the risk of polarization

In this section, we analyze the stability of the network structure during an opinion network formation process. We first derive sufficient conditions for the internal stability of the network, i.e., the absence of link destruction. Similar results for the external stability of the network, i.e., the absence of link creation, are provided in Appendix B. We then derive sufficient conditions for non-polarization, i.e., for the network to remain connected. Finally, we perform a broad analysis of the relation between network structure and its stability properties by means of numerical simulations.

## 3.1 Link and network fragility

We first investigate conditions under which a dynamic network is such that no link gets deleted in a one-step opinion update, independently of opinions x and the values of $\sigma$, $\tau$ and $\lambda$, provided the network-opinion pair is $(\sigma, \tau)$-compatible.

We shall first introduce the definition of a maximal link.

**Definition 2** A link (undirected edge) $\{i, j\} \in \mathcal{G}$ is said to be maximal if for all $\{i', j'\} \neq \{i, j\}$ such that $i' \le i$ and $j' \ge j$, one has $\{i', j'\} \notin \mathcal{G}$, i.e., $\{i', j'\}$ is not a link.

Note that, as a consequence of Lemma 1, if a link gets deleted at some time step, then necessarily a maximal link also gets deleted. It is therefore sufficient to study under which condition there is deletion of a maximal link. To this purpose, consider $\{i, j\} \in \mathcal{G}$ a maximal link, with $x_i < x_j$. The structure of the network in the neighborhood of $\{i, j\}$ is given by:

* $L$, the number of nodes to the left of $i$, i.e., in $[n_-(i), i[$;

* $R$, the number of nodes to the right of $j$, i.e., in $]j, n_+(j)]$;

* $M$, the number of nodes between $i$ and $j$, excluding them, i.e., in $]i, j[$;

* for all $m = 1, \dots, M$, the number of nodes $\ell_m$ (respectively $r_m$) to the left of $i$ (respectively to the right of $j$) to whom $m$ is connected.

We call $(L, R, M, (\ell_m)_{m=1,\dots,M}, (r_m)_{m=1,\dots,M})$ the *local structure* of the network around $\{i, j\}$. Note that $\{i, j\}$ being a maximal link, $i$ is not connected to any node to the right of $j$, and $j$ is not connected to any node to the left of $i$, and all the nodes between $i$ and $j$ are connected (because of compatibility).

**Definition 3** Using the above notation, the fragility of a (maximal) link $\{i, j\}$ in the network $\mathcal{G}$ is defined by:

$$ \phi_{i,j}(\mathcal{G}) = \max_{m \in \{0, \dots, M\}} \frac{(L+M+2)(2R-r_m) + (R+M+2)(L-\ell_{m+1}) + (L-R)(M-m+1)}{(L+M+2)(R+M+2)} \quad (4) $$

letting $r_0 = 0$ and $\ell_{M+1} = 0$.
The fragility of a link measures to which extent the link can be stretched away by its neighbors. Its precise meaning is revealed in the next two propositions.

**Proposition 1** Let $\sigma, \tau, \lambda$ be given and $\{i, j\}$ be a maximal link in the network $\mathcal{G}(t)$. Then one has $\{i, j\} \in \mathcal{G}(t+1)$ for any $x(t)$ that is $(\sigma, \tau)$-compatible with $\mathcal{G}(t)$ if and only if $\phi_{i,j}(\mathcal{G}(t)) \le 1$.

Proposition 1 induces an interpretation of $\phi_{i,j}$ as a measure of fragility. Namely $\phi_{i,j} \le 1$ is a necessary and sufficient condition for the link $\{i, j\}$ not to break provided the opinions are compatible.

The values of $\phi_{i,j}$ also determine the maximal extension/contraction of opinions during the updating process. In this respect, let us focus on opinions that are uniformly bounded in the following sense.

**Definition 4** The differences in opinions in a network opinion pair $(x, \mathcal{G})$ are said to be uniformly bounded by $\rho \ge 0$ if one has:

$$ \forall i, j \in \mathcal{N} : \{i, j\} \in \mathcal{G} \Rightarrow |x_i - x_j| \le \rho $$

Note, in particular, that if an opinion network pair $(x, \mathcal{G})$ is $(\sigma, \tau)$-consistent then the differences in opinions are uniformly bounded by $\sigma$. The following proposition then provides a bound on the growth of differences in opinions during the opinion updating process.

**Proposition 2** Let $\sigma, \tau, \lambda$ be given and $(x(t), \mathcal{G}(t))$ be $(\sigma, \tau)$-compatible network opinion pair with differences in opinions bounded by $\rho$. For every (maximal) link $\{i, j\} \in \mathcal{G}(t)$, one has:

$$ x_j(t+1) - x_i(t+1) \le \rho[1 + (\phi_{i,j}(\mathcal{G}(t)) - 1)\lambda^t]. \quad (5) $$

Propositions 1 and 2 highlight the fact that the dynamics of the network is governed by its local structure. In particular, the fragility of a link is determined by (i) the number of left and right neighbors of the link that exert a tension at both edges of the maximal link and (ii) the number of intermediary nodes between the two edges of a maximal link, which generate an inward attracting force and thus increase the resistance of the link. The max operator in the definition of $\phi_{i,j}$ amounts to consider a worst case scenario with respect to the positioning of left and right neighbors of the link, which, in turn, is constrained by the numbers of right and left neighbors of intermediary nodes.

Building on the local measure of fragility $\phi_{i,j}$, we can define measure of fragility at the network level, i.e., put forward conditions under which link destruction can (or cannot) be prevented. In full generality, creation and destruction of links can feedback on each other, certain links being made more fragile by the creation of new links at their edges. Thus, a characterization of the conditions leading to link destruction in the general case requires to solve a range of open conjectures on the dynamics of bounded confidence models [see e.g. Blondel et al., 2007]. In the following, we rather focus on the first-order determinants
of network fragility and thus restrict attention to decreasing network formation process, i.e., we place ourselves in a setting where $\tau = 0$ and $\sigma < +\infty$ and the initial network opinion pair $(x(0), \mathcal{G}(0))$ is assumed compatible. We then introduce a measure of network fragility as follows.

**Definition 5** A maximal link $\{i, j\}$ is said to be fragile if $\phi_{i,j} > 1$. Given a network $\mathcal{G}$, let $\mathcal{L}_G$ denote its set of maximal links, and let

$$ \bar{\phi}_G := \max_{\{i,j\} \in \mathcal{L}_G} \phi_{i,j} $$

A network has no fragile (maximal) link if $\bar{\phi}_G \le 1$. In a sense, $\bar{\phi}_G$ is a measure of fragility of the network.

**Proposition 3** If the initial network $\mathcal{G}(0)$ has no fragile link, i.e., $\bar{\phi}_{\mathcal{G}(0)} \le 1$, then for all $\lambda \in [0, 1]$, one has $\mathcal{G}(t) = \mathcal{G}(0)$ for all $t \in \mathbb{N}$, i.e., the network is stable for the dynamics independently of the choice of a compatible $x(0)$.

**Remark 3** Conversely, if $\bar{\phi}_G > 1$, then there exists a compatible initial vector of opinions $x(0)$ such that the network is unstable under the dynamics.

Let us further investigate the stability of network when there are fragile links. The above remark shows that the presence of a fragile link makes stability to fail. However, if the “length” of each link is uniformly bounded above by $\rho < \sigma$, we will show that one can ensure stability for $\lambda$ in an appropriate range.

Let us then consider a network opinion pair $(x(0), \mathcal{G}(0))$ such that differences in opinions are uniformly bounded above by $\rho < \sigma$ (in the sense of Definition 4) and assume there exists some fragile link in $\mathcal{G}(0)$, i.e., $\bar{\phi} := \bar{\phi}_{\mathcal{G}(0)} > 1$. Applying Proposition 2, we have for all maximal links $\{i, j\} \in \mathcal{G}(0)$:

$$ x_j(1) - x_i(1) \le \phi_{i,j}(x_j(0) - x_i(0)) \le \bar{\phi}\rho. \qquad (6) $$

If Equation (6) holds for all maximal links, it necessarily holds for all links, so that opinions in $(x(1), \mathcal{G}(1))$ are uniformly bounded above by $\bar{\phi}\rho$. Furthermore, observe that $x_j(1) - x_i(1) < \sigma$ if and only if $\frac{\sigma}{\rho} \ge \bar{\phi}$. Assuming this condition is satisfied, one has $\mathcal{G}(1) = \mathcal{G}(0)$. One can then apply Proposition 2 to $(x(1), \mathcal{G}(1))$, which yields that for all maximal links $\{i, j\} \in \mathcal{G}(1) = \mathcal{G}(0)$, one has:

$$ x_j(2) - x_i(2) \le [1 + (\bar{\phi} - 1)\lambda]\bar{\phi}\rho. $$

Hence, as above, opinions in $(x(1), \mathcal{G}(1))$ are uniformly bounded above by $[1 + (\bar{\phi} - 1)\lambda]\bar{\phi}\rho$ and we have stability of the network, i.e., $\mathcal{G}(2) = \mathcal{G}(0)$, if and only if $x_j(2) - x_i(2) \le \sigma$, which yields the following condition on $\lambda$:

$$ \lambda \le \frac{\sigma - \bar{\phi}\rho}{\bar{\phi}\rho(\bar{\phi} - 1)} $$
Iterating the process amounts to studying the sequence $(u_t)_{t \in \mathbb{N}}$ defined by

$$u_{t+1} = u_t(1 + (\bar{\phi} - 1)\lambda^t)$$

with $u_0 = \rho$. Indeed, sequential application of Proposition 2 shows that $u_t$ is the upper bound of the differences in opinions in $(x(t), \mathcal{G}(t))$. We find easily that for any $t \in \mathbb{N}$,

$$u_{t+1} = \rho \cdot \prod_{k=0}^{t} (1 + (\bar{\phi} - 1)\lambda^k).$$

The product $\prod_{k=0}^{t}(1 + (\bar{\phi} - 1)\lambda^k)$ defines a convergent series, well-known in mathematics under the name of q-series. A q-series has the form:

$$(a; q)_n = \prod_{k=0}^{n-1} (1 - a q^k)$$

where $(a; q)_n$ is called the q-Pochhammer symbol. With this notation, we have found that the upper bound of the differences in opinions is

$$u_t = \rho(1 - \bar{\phi}; \lambda)_t$$

and that this value has a limit when $t$ tends to infinity, denoted by $\rho(1 - \bar{\phi}; \lambda)_\infty$. Observe that for every $t \in \mathbb{N}$, $(1 - \bar{\phi}; \lambda)_t$ is continuous and increasing in $\lambda$, as we have $\bar{\phi} > 1$. It follows that there exists a unique $\lambda$ solving $(1 - \bar{\phi}; \lambda)_t = \alpha$ (provided $\alpha$ is in the range of the q-series), which we denote by $(1 - \bar{\phi}; \alpha)_t^{-1}$.

Using the above notation, we can see that the network is stable if $u_t \le \sigma$ as $t$ tends to infinity, i.e., if

$$\lambda \le (1 - \bar{\phi}; \frac{\sigma}{\rho})_\infty^{-1}.$$

In summary, we have shown the following result.

**Proposition 4** Consider an initial compatible pair $(x(0), \mathcal{G}(0))$ and a decreasing network, such that differences in opinions are bounded above by $\rho < \sigma$, and $\frac{\sigma}{\rho} \ge \bar{\phi}$. Then the network is stable, i.e., $\mathcal{G}(t) = \mathcal{G}(0)$ for all $t \in \mathbb{N}$, if $\lambda \in [0, (1 - \bar{\phi}; \frac{\sigma}{\rho})_\infty^{-1}]$.

Note that Proposition 4 provides a sufficient condition for stability. If $\lambda$ is below the bound, the network is stable. If $\lambda$ is greater than the bound, instability of the network is possible but not certain. Thus Proposition 4 implies that as the intensity of social interactions $\lambda$, the bound on initial difference in opinions $\rho$ or the fragility of the initial network $\bar{\phi}$ increase, it becomes more difficult to guarantee stability. However, it also implies that for any $\rho$ and $\bar{\phi}$, $\lambda$ can always be chosen small enough (possibly equal to 0) to ensure stability of the network.

## 3.2 Network polarization

In this subsection, we focus on the risk of polarization, i.e., the risk of the network becoming disconnected (note that this is a weaker condition than stability: a network
may be unstable while remaining connected). In particular, we shall put forward sufficient conditions for non-polarization, i.e., for the network to remain connected.

Preventing polarization amounts to ensure that no link of the form {$i, i + 1$} gets disconnected. A worst case scenario in this respect is to consider that the link {$i, i + 1$} is maximal. Let us then consider a maximal link {$i, i + 1$} in the graph $G(0)$. Observe that its local configuration has by definition $M = 0$, so that it reduces to $(L, R)$. By the above analysis, we know that we ensure {$i, i + 1$} to be present in $G(1)$ for any $x(0)$ compatible with $G(0)$ if and only if $\phi_{i,i+1} \le 1$. We have, as $M = 0$,

$$ \phi_{i,i+1} = \frac{3(R_i L_i + R_i + L_i)}{(L_i + 2)(R_i + 2)}, $$

where we have put the subindex $i$ to emphasize dependency to the local configuration of the link {$i, i + 1$}. As we consider that no link can be created, the possible deletion of links makes that $R, L$ can only decrease in $G(1)$. Namely, computing the first-order derivative of $\phi_{i,i+1}$ yields

$$ \frac{\partial \phi_{i,i+1}}{\partial R_i} = \frac{3(L_i^2 + 4L_i + 4)}{(L_i + 2)^2 (R_i + 2)^2} = \frac{3}{(R_i + 2)^2} \ge 0, \quad (7) $$

and similarly for $\frac{\partial \phi_{i,i+1}}{\partial L_i}$. As a consequence, $\phi_{i,i+1}$ can only decrease with time, and it is enough to check that $G(1)$ remains connected to ensure connectedness for all times. Introducing

$$ \bar{\psi}_G := \max_{\{i,i+1\} \in \mathcal{L}_G} \phi_{i,i+1} = \max_{\{i,i+1\} \in \mathcal{L}_G} \frac{3(R_i L_i + R_i + L_i)}{(L_i + 2)(R_i + 2)}, $$

we have shown:

**Proposition 5** If the initial network $G(0)$ is connected and satisfies $\bar{\psi}_{G(0)} \le 1$, then $G(t)$ remains connected under a decreasing formation process for all $t \in \mathbb{N}$ and for all $\lambda \in [0, 1]$, independently of the choice of a compatible $x(0)$.

We can further analyze the conditions for connectedness when $\bar{\psi}_{G(0)} > 1$ and differences in opinions are supposed to be uniformly bounded by $\rho \le \sigma$ for all $i$. Proceeding as for the proof of Proposition 4 and replacing $\bar{\phi}$ by $\bar{\psi} := \bar{\psi}_{G(0)}$, we find:

**Proposition 6** Consider a decreasing network formation process with initial compatible state $G(0)$ and a compatible opinion vector $x(0)$, such that $x_{i+1}(0) - x_i(0) \le \rho < \sigma$ for $i = 1, \dots, N - 1$, and $\frac{\sigma}{\rho} \ge \bar{\psi}$. Then the network $G(t)$ remains connected for all $t \in \mathbb{N}$ if $\lambda \in [0, (1 - \bar{\psi}; \frac{\sigma}{\rho})^{-1}]$.

Note that Proposition 6 provides a sufficient condition for non-polarization. If $\lambda$ is below the bound, the network cannot polarize. If $\lambda$ is greater than the bound, polarization is possible but not certain. Thus Proposition 6 implies that as the intensity of social interactions $\lambda$, the bound on initial difference in opinions $\rho$ or the polarizability of the initial network $\bar{\psi}$ increase, it becomes more difficult to guarantee non-polarization. However, it also implies that for any $\rho$ and $\bar{\psi}$, $\lambda$ can always be chosen small enough (possibly equal to 0) to prevent polarization of the network.

**Remark 4** Equation 7 also implies that initially adding (resp. deleting) a link left or right of a maximal link increases (resp. decreases) the risk of polarization. However, the increase in risk is smooth and the marginal effect of a link addition decreases rapidly (quadratically) with the number of links.
## 3.3 Numerical sensitivity analysis

Propositions 4 and 6 put forward sufficient conditions for ensuring, respectively, the stability and the connectedness of the network. They consider worst-case scenarios where, for each link, the difference in opinions assumes the maximal possible value $\rho\sigma$. Thus, the question arises if these worst-case scenarios are representative of network dynamics in the general case.

To investigate this issue, we perform a series of numerical simulations in which we let vary the network structure, its edge-connectedness$^6$, the upper bound on initial differences in opinions and the intensity of social interactions. Details of the simulation algorithm are provided in box 1. Overall, we run 50 000 simulations corresponding to 100 initial distributions of opinions, for each initial distribution of opinions 50 initial network structures (corresponding to edge-connectedness $\nu$ ranging in $\{1, \dots, 5\}$ and bound on initial difference in opinions ranging in $\{\frac{m\sigma}{10} \mid m = 1, \dots, 10\}$), and intensity of social interactions $\lambda$ ranging in $\{\ell/20 \mid \ell = 0, \dots, 20\}$.

-We first generate a sample of 500 initial opinion distributions by drawing independently uniformly at random in $[-1, 1]$, the opinion of $N$ agents (we consider $N = 100$).

-For each initial distribution $x(0)$ (assumed to be ordered by increasing opinion), each value of edge-connectedness $\nu \in \{1, \dots, 5\}$ and each $\mu \in \{m/10 \mid m = 1, \dots, 10\}$, we set $\sigma := \frac{1}{\mu} \max_{i=1,\dots,N-\nu} |x(0)_{i+\nu} - x(0)_i|$ and define an initial network $G(0)$ by letting $\{i,j\} \in G(0)$ if and only if $|x(i) - x(j)| \le \mu\sigma$. This ensures that the edge-connectedness of the network is $\nu$, that the initial differences of opinions in the network are bounded by $\rho = \mu\sigma$ and that the initial network-opinion pair is compatible.

-We then simulate the network-opinion dynamics according to the equations defined in section 2.1, letting $\lambda$ take value in $\{\ell/20 \mid \ell = 0, \dots, 20\}$.

Box 1: Algorithm for the initialisation of random network-opinion pairs and their simulation.

In this setting, we first investigate how the risks of instability and polarization vary with the intensity of social interactions $\lambda$ and the bound on initial difference in opinions $\rho$. We obtain results that are perfectly consistent with the sufficient conditions put forward in Propositions 4 and 6. As illustrated in Figure 1, the probability of instability and polarization both monotonically increase with $\lambda$ and $\rho$. Furthermore, one observes that $\lambda$ can always be chosen small enough to prevent polarization/instability and that the maximum acceptable $\lambda$ in this respect decreases with $\rho$.

We further build on our simulations to characterize more precisely the dynamics of polarization and the relation with network structure. With respect to the timing of polarization, Figure 3 shows that polarization mostly occurs in early periods, suggesting it can be linked to an initial vulnerability in the network. This fact is also consistent with

<footnote>$^6$A graph is *h*-edge-connected if the deletion of *h* edges can disconnect the graph, but the deletion of any set of *h* − 1 edges leaves the graph connected.</footnote>
<figure><img src="image_2.png" /><figcaption>Figure 1: Empirical probability (computed over the sample described in Box 1) of the destruction of at least one link (left panel) and of the disconnection/polarization of the network (right panel) for various levels of $\lambda$ and $\mu$.</figcaption></figure>

the positive impact of increasing $\lambda$ on polarization: increasing $\lambda$ leads to more abrupt opinion changes, in particular in early periods, and thus favors the disconnection of initially fragile links. Nevertheless, one also observes a few simulations where polarization occurs after a substantial amount of time, suggesting that it can also be the outcome of complex interactions between opinion and network dynamics.

With respect to the relation between polarization and network structure, the former results on the early occurrence of polarization suggest that the risk of polarization can be well approximated by low-order approximation of the *q*-series ($1 - \bar{\psi}; \frac{\sigma}{\rho}$). Indeed, Proposition 6 focuses on the asymptotic behavior of the *q*-series because polarization can, in theory, occur at arbitrarily large times. However, if polarization actually occurs mostly in early periods, low-order approximations of the series should be sufficient to characterize the risk of polarization. We empirically confirm this fact by running, separately for each value of the edge-connectedness parameter, a logistic regression of the probability of polarization on the first-order approximation of the *q*-series, i.e., $\bar{\psi}_1 := (1 + (\bar{\psi} - 1))(1 + (\bar{\psi} - 1)\lambda)$. The results are reported graphically in Figure 3 and in details in Appendix C. They show that $\bar{\psi}_1$ is a clear determinant of the risk of polarization. They also show that the risk of polarization decreases with the edge-connectedness of the network (for a given $\bar{\psi}_1$).

Overall, our numerical results show that the initial structure of the network, characterized by $\bar{\psi}$, the edge-connectedness of the network, and the intensity of social interactions $\lambda$ are key determinants of polarization. Most polarization episodes occur in early periods as initially fragile links, whose presence is characterized by $\bar{\psi}$ and the level of edge-connectedness, are destroyed when social interactions are sufficiently strong to pull apart the opinions of adjacent nodes to a distance greater than the disconnection threshold $\sigma$.

# 4 Convergence and asymptotic opinions

The preceding section highlights how the strength of social interactions determines the evolution of the network and its potential polarization. In this section, we investigate
<figure><img src="image_3.png" /><figcaption>Figure 2: Histogram (with a log-scale on the y-axis) of the time to disconnection/polarization for networks in the sample that actually disconnects.</figcaption></figure>

how the strength of social interactions impacts opinion dynamics. Therefore, we place ourselves in a setting where the network dynamics are assumed to have converged to a state $(x(0), G)$ where there is no more deletion or creation of links (this assumption is aligned with the findings of the preceding section on the timing of link destruction).

We assume $\lambda \neq 0$, otherwise there is no evolution of the opinion in time, and also $\lambda \neq 1$, otherwise the model reduces to the classical DeGroot model, whose convergence properties are fully known. In summary, $\lambda \in ]0, 1[$ in the whole section. Under these conditions, the dynamics reads<fnref n="7" />

$$x(t+1) = [\lambda^t G + (1-\lambda^t)I]x(t) = M(t)x(t) = M(t)M(t-1)\cdots M(1)x(1) = H(t)x(1)$$

with $x(1) = Gx(0)$, and

$$H(t) = \prod_{k=1}^{t} (\lambda^k G + (1-\lambda^k)I).$$

Hence, $H(t)$ is a polynomial in $G$ of degree $t$, i.e., of the form:

$$H(t) = h_{t,t}G^t + h_{t-1,t}G^{t-1} + \cdots + h_{1,t}G + h_{0,t}I. \quad (8)$$

<footnote n="7">⁷For simplicity we use the notation $M(t)$ and $H(t)$, but obviously these matrices depend also on $\lambda$ and the matrix $G$.</footnote>
<figure><img src="image_4.png" /><figcaption>Figure 3: Scatter plot of a binary indicator of disconnection (equal to 1 if the network disconnects/polarizes in the course of the simulation and to 0 otherwise) as a function of the polarizability of the initial network $\bar{\psi}$. Upper-left panel corresponds to initial networks with edge-connectedness 1, upper-right panel to initial networks with edge-connectedness 2, lower-left panel to initial networks with edge-connectedness 3, lower-right panel to initial networks with edge-connectedness 4. Logistic regression curve is displayed in red.</figcaption></figure>

## 4.1 Convergence of the opinion vector

We first provide an explicit expression of the coefficients of this polynomial and study their behavior when $t$ tends to infinity. To this aim, we will make use of the following special functions: the Euler function $\varphi$, defined by

$$ \varphi(q) = \prod_{k=1}^{\infty} (1 - q^k) \quad (q \in \mathbb{C}), \qquad (9) $$

and the $r$-Digamma function $\Psi_r$, with $0 < r < 1$ and $x$ real, defined by

$$ \Psi_r(x) = -\log(1-r) + \log r \sum_{k=0}^{\infty} \frac{r^{k+x}}{1-r^{k+x}}. \qquad (10) $$

One can then characterize the coefficients of $H(t)$ as follows.
**Proposition 7** The coefficients of the polynomial $H(t)$ in $G$ are given by

$$ 
\begin{aligned}
h_{t,t} &= \lambda^{t(t+1)/2} \\
h_{0,t} &= \prod_{i=1}^{t} (1 - \lambda^i) \\
h_{i,t} &= \lambda^{t(t+1)/2} \sum_{1 \le j_1 < j_2 < \dots < j_i \le t} \prod_{\substack{l=1 \\ l \ne j_1, \dots, j_i}}^{t} \frac{1 - \lambda^l}{\lambda^l} \quad (0 < i \le t)
\end{aligned}
$$

with the convention that $\Pi_\emptyset = 1$. The asymptotic behavior of the coefficients is given by $\lim_{t\to\infty} h_{i,t} > 0$ if $i \in \mathbb{N}$, while $\lim_{t\to\infty} h_{i(t),t} = 0$ if $i(t) \to \infty$. In particular, we have

$$ 
\begin{aligned}
\lim_{t \to \infty} h_{0,t} &= \varphi(\lambda) \\
\lim_{t \to \infty} h_{1,t} &= \varphi(\lambda) \left( 1 + \frac{\log(1-\lambda) - \log \lambda}{\log \lambda} + \frac{1}{\log \lambda} \Psi_{\lambda}(1) \right).
\end{aligned}
$$

Figure 4 complements Proposition 7 by providing a graphical representation of the variation of the coefficients of $H(t)$ as a function of $\lambda$. The results characterize the relative influence of the network structure on the formation of opinions. One shall first remark that, except in the degenerate case where $\lambda = 1$, one has $h_{0,\infty} > 0$ and thus the initial opinion of an individual retains some weight into its final opinion. More broadly, one has for all finite $i \in \mathbb{N}$, $h_{i,\infty} > 0$ and thus all peers within a finite distance of an agent have a distinguishable influence on the agent's asymptotic opinion. This implies in particular that, except in degenerate cases where all agents have similar opinions initially, some heterogeneity of opinions remains asymptotically. This is in strong contrast with most of the variants of the DeGroot model (see the appendix) in which (i) there is a complete mixing of opinions and convergence to a consensus (if only in a connected component), (ii) the influence of one agent on another is fully determined by its (eigenvector) centrality and thus independent of the bilateral distance, and (iii) the only potential impact of an agent's initial opinion is to determine the connected component of the network to which he will eventually belong.

Figure 4 also highlights that there is no monotonic decrease of influence with social distance. An agent at a social distance $i + 1$ can have more influence than an agent at distance $i$ on the asymptotic opinion. Nevertheless, as emphasized in Lemma 3, the influence of an agent at distance $i + 1$ can not increase (with $\lambda$) if that of an agent at distance $i$ decreases. This implies that as $\lambda$ grows, the overall influence of agents above a certain distance ($i_\lambda$ in the proof of Lemma 3) increases while that of the agents below the threshold distance decreases. In particular, for $\lambda = 0$, there is no influence of network peers while for $\lambda = 1$, influence is independent of social distance.
<figure><img src="image_5.png" /><figcaption>Figure 4: Graphical representation of the coefficients of $H(10)$ for $\lambda$ varying in $[0, 1]$.</figcaption></figure>

Building on Proposition 7, one can also provide simple approximations of the asymptotic opinions $x(\infty)$. To this end, we need to make some assumptions on $G$. If we suppose the graph $G$ to be connected, since self-loops exist on each node and the graph is undirected, its directed version is strongly connected and aperiodic, which means that $G$ is primitive. Consequently, $G^\infty = \mathbf{1}w^T$, where $w$ is the normalized left eigenvector of $G$ associated to eigenvalue 1, and the convergence is exponentially fast. Doing the approximation $G^3 \approx G^4 \approx \dots \approx G^\infty$, we obtain the following result.

**Proposition 8** Assume that the network $G$ is static and connected, with initial opinion vector $x(0)$, and denote by $w$ the normalized left eigenvector of $G$ associated to eigenvalue 1. Then the opinion vector $x(t)$ can be asymptotically approximated by

$$x(\infty) \approx \left[ \frac{\varphi(\lambda)}{\log(\lambda)} (\log(1-\lambda) + \Psi_{\lambda}(1)) G^2 + \varphi(\lambda) G + \left( 1 - \frac{\varphi(\lambda)}{\log(\lambda)} (\log(1-\lambda) + \log(\lambda) + \Psi_{\lambda}(1)) \right) \mathbf{1} w^T \right] x(0). \quad (11)$$

Some comments on the results:

* Formula (11) is an approximation, as $G^3$ and all successive powers of $G$ have been approximated by $G^\infty$. This is however reasonable as $G^t$ tends exponentially fast to $G^\infty$. Starting the approximation from $G^4$ would need an explicit expression for $\lim_{t \to \infty} h_{2,t}$, which seems difficult to obtain.

* Pushing the approximation one step further, i.e., assimilating $G^2$ to $G^\infty$ yields a very simple formula. Indeed, the formula becomes:

$$x(\infty) \approx [\varphi(\lambda)G + (1 - \varphi(\lambda))\mathbf{1}w^T]x(0).$$

Clearly, $\varphi(\lambda)$ tends to 0 when $\lambda$ tends to 1. We retrieve the fact that $x(t)$ converges to $\mathbf{1}w^T$ in the DeGroot model with a primitive matrix.
* Formula (11) tells us an important property of the model. We see that there is a term in $1w^T$, which is the “consensus” term because $1w^T x(0)$ is a vector with equal components, and there is a term in $G$ as well as a term in $G^2$, which does not give a consensus as these matrices do not have equal rows. Therefore, unless $\lambda$ tends to 1, $x(\infty)$ is not a consensus vector, showing that the model exhibits strong diversity.

## 4.2 Diameter of opinions

We end this section by showing that, for a static network, the asymptotic difference in opinions in the society decreases with $\lambda$. Let us write $H_\lambda(t)$ and $x_\lambda(t)$ instead of $H(t)$ and $x(t)$ to emphasize the dependency on $\lambda$. Given $x \in \mathbb{R}^N$ we denote its “diameter” by

$$ \delta(x) := \max_{i \in \mathcal{N}} x_i - \min_{i \in \mathcal{N}} x_i $$

Our aim in this section is to show that the diameter of an opinion vector $x_\lambda(t)$ is a decreasing function of $\lambda$. As agents are ordered by increasing opinions, we have that $\delta(x) = x_N - x_1$ and the following holds:

**Lemma 2** Suppose $(x, G)$ is compatible. Then for every opinion vector $x$, one has:

$$ \delta(Gx) \le \delta(x) $$

with strict inequality if, e.g., $G$ is connected and all $x_i$'s are pairwise distinct.

**Remark 5** The above property is well known, and usually called the contraction property. It is valid for any row-stochastic $G$ and an upper bound of the contraction rate is known (see, e.g., [Seneta, 2006, Th. 3.1]). Our additional conditions, corresponding to our framework, permit to provide a very short proof and to give examples of conditions where strict inequality obtains.

The following proposition underlines the monotonicity of the diameter of opinions with respect to $\lambda$.

**Proposition 9** Suppose $(x(0), G)$ is compatible, with $G$ static and uniform. For all $t \in \mathbb{N}$, for all $\lambda, \mu \in [0, 1]$, one has:

$$ \lambda > \mu \Rightarrow \delta(x_\lambda(t)) \le \delta(x_\mu(t)) $$

with strict inequality if, e.g., $G$ is connected and all $x_i(0)$'s are pairwise distinct.

The proof of Proposition 9 relies on the fact that the coefficients of the polynomial $H_\lambda(t)$ are differentiable with respect to $\lambda$ and on the fact that, letting $h_{i,t}(\lambda)$ denote the $i$th coefficient of $H_\lambda(t)$, the following holds:

**Lemma 3** For all $t \in \mathbb{N}$ and all $i \in \{0, \dots, t-1\}$, one has:

$$ h'_{i+1,t}(\lambda) \le 0 \Rightarrow h'_{i,t}(\lambda) \le 0. $$

Proposition 9 hence highlights that increasing $\lambda$ favours social consensus in the network.
# 5 Strategy and efficiency in the design of public debates

## 5.1 Consensus and polarization

The results of the preceding sections emphasize the existence of a trade-off between the convergence of opinions and the risk of polarization in the public debate. Indeed, according to Proposition 9, the diameter of the distribution of opinions decreases with $\lambda$ while according to Propositions 4 and 6, the risk of instability and polarization increases with $\lambda$. The parameter $\lambda$ can be interpreted as a measure of the intensity of the public debate in a society, e.g., during a political campaign. From this perspective, our results suggest that increasing the intensity of the public debate can contribute to social consensus or to efficient aggregation of information, [by harnessing the wisdom of crowds, see Golub and Jackson, 2010]. However, it also increases the risk that the issue being debated generates a major social division [and thus prevents the efficient aggregation of information as emphasized in Lorenz et al., 2011].

The 2016/2020 US presidential campaign and its aftermath or the Tunisian “Jasmine Revolution” are but two examples of major impacts of changes in the form of public debate on social dynamics. In the Tunisian case, the rise of social media increased the intensity of the public debate and contributed to the emergence of a social consensus on the change of political regime [see, e.g., Lowrance, 2016, Lavie, 2021]. In the US case, changes in the modes/intensity of communication by the Trump campaign contributed to a massive increase in polarization of US society [see, e.g., Homolar and Scholz, 2019, Hameleers, 2020]. More broadly, ever since the advent of the Greek polis, the organization of public debate has been a key part of the design of political institutions [see, e.g., “Aristotle’s politics” and Sennett, 1998, for an historical account]. In modern democratic societies, institutions and governments influence the intensity of the public debate through a number of means including (i) regulation of social and traditional media and of freedom of expression, (ii) regulation of parties and associations, (iii) regulation and organization of the political campaign process (e.g., the frequency and type of debates organized between parties, the type of electoral advertisement authorized, the organization of caucuses). Accordingly, parties and candidates seek to influence the form/intensity of the public debate to align them with their campaign objectives [see Plasser and Plasser, 2002, Chadwick, 2017]<fnref n="8" />.

In the following, we build on our above results, to provide formal models of the behavior of (i) a social planner controlling the intensity of the public debate with the objective to foster social consensus while avoiding the risk of polarization and (ii) candidates/parties aiming at influencing the intensity of the public debate in order to maximize their electoral support. The empirical relevance of both issues is well illustrated by the 2020 U.S. presidential campaign and its aftermath. Social networks have been pointed out as key actors in the polarization process because their recommendation algorithms have helped reinforce and amplify the bias of users [see e.g. Vaidhyanathan, 2018, Eisenstat, 2021]. Indeed, in order to increase engagement, recommendation algorithms tend to feed users with more biased/polarized content as they themselves become more bi-

<footnote n="8">⁸Or Quintus Tullius Cicero’s “Commentariolum Petitionis” for an early account.</footnote>
ased/polarized, hence creating a vicious circle of polarization. The regulation of social networks has thus emerged as a key issue in the aftermath of the campaign [see e.g. Ghosh, 2021]. A number of regulatory measures have been put forward: increasing platform li-ability for user-generated content, requiring algorithmic transparency, fostering platform self-regulation [Ghosh, 2020] and more broadly modifying the structure of interactions [Fagan, 2018]. Despite the variety of means, one common objective of these measures is to reduce the repetition of polarizing information. As put forward above, in our setting, this amounts to reduce the intensity of the public debate governed by the parameter $\lambda$.

## 5.2 Socially efficient public debates

We first consider a social planner who controls the intensity of the public debate, i.e., of the opinion network formation process, through the choice of the parameter $\lambda \in [0, 1]$. We assume that the social planner observes the initial structure of the network $\mathcal{G}$ but faces some uncertainty about the initial distribution of opinions and the threshold above which network connections break. To account for this uncertainty, we let $X_\kappa := \{(x, \sigma) \in [-1, 1]^N \times [0, 2] \mid \frac{\sigma}{x_N - x_1} \ge \kappa\}$, i.e., the set of opinion formation processes such that the ratio $\frac{\sigma}{\rho}$ is bounded below by $\kappa$.

Using Propositions 4 and 6, it is straightforward to characterize the optimal behavior of the social planner who aims to ensure with probability 1 the stability of the network.

* If the social planner knows that the initial opinion distribution is in $X_\kappa$ and aims at minimizing the diameter of opinions while preventing any change in the network structure, then he must choose $\lambda = (1 - \bar{\phi}(\mathcal{G}); \kappa)_{\infty}^{-1}$.

* If the social planner knows that the initial opinion distribution is in $X_\kappa$ and aims at minimizing the diameter of opinions while preventing polarization/division of the network, then he must choose $\lambda = (1 - \bar{\psi}(\mathcal{G}); \kappa)_{\infty}^{-1}$.

Yet, the social planner might be more broadly interested in the trade-off between opinion convergence and network stability. To investigate this issue, we consider a refined setting in which the benefit of increasing convergence of opinion is measured proportionally to $\lambda$ while the risk of network instability/polarization is evaluated probabilistically. Namely, building on the characterization of the stability condition in Subsection 3.2, we assume that the social planner has a utility function of either of the following forms:

$$u(\lambda) = \alpha\lambda - \mathbb{P}[(1 - \bar{\phi}(\mathcal{G}); \lambda) \ge \frac{\sigma}{\rho}] \quad (12)$$

$$v(\lambda) = \alpha\lambda - \mathbb{P}[(1 - \bar{\psi}(\mathcal{G}); \lambda) \ge \frac{\sigma}{\rho}] \quad (13)$$

where $\alpha > 0$ and the probability $\mathbb{P}$ is taken with respect to the distribution of $\frac{\sigma}{\rho}$. These functional forms are chosen for the sake of analytical tractability. Qualitatively similar results would be obtained for alternative measures of the risk of polarization, which would necessarily be increasing with $\lambda$ according to the results in Section 3.3.
The linear benefit in $\lambda$ is a first-order approximation of Proposition 9 according to which the diameter of the network is decreasing in $\lambda$. The term $\mathbb{P}[(1-\bar{\phi}(\mathcal{G}); \lambda) \ge \sigma/\rho]$ amounts to considering that the social planner faces a disutility proportional to the probability that the social network gets distabilized, i.e., loses some links, during the political process. Relatedly, the term $\mathbb{P}[(1-\bar{\psi}(\mathcal{G}); \lambda) \ge \sigma/\rho]$ amounts to considering that the social planner faces a disutility proportional to the probability that the social network gets polarized, i.e., becomes disconnected, during the political process.

To provide an analytical characterization of the optimal behavior for the social planner, we restrict attention to the case where $\frac{\sigma}{\rho}$ is assumed to be distributed uniformly over some interval $[0, S]$. Then one has

$$u(\lambda) = \alpha\lambda - \frac{1}{S} \min((1 - \bar{\phi}; \lambda), S) \quad (14)$$

which is equivalent, up to a linear transformation, to

$$u(\lambda) = S\alpha\lambda - \min((1 - \bar{\phi}; \lambda), S) \quad (15)$$

and similarly

$$v(\lambda) = S\alpha\lambda - \min((1 - \bar{\psi}; \lambda), S) \quad (16)$$

With the utility $u$ being continuous, there clearly exists an optimal choice of intensity $\lambda \in [0, 1]$ for the social planner. One has the following (partial) characterization.

**Proposition 10** If $\alpha < 1$ then a solution $\lambda^*$ to the social planner problem, $\max_{\lambda \in [0,1]} u(\lambda)$, is such that $\lambda^* \in ]0, 1[$ and satisfies

$$\frac{S\alpha}{(\bar{\phi} - 1)} = \frac{(1 - \bar{\phi}; \lambda^*)h(\lambda^*)}{\lambda^*} \quad (17)$$

$$\text{where } h(\lambda) = \sum_{k=0}^{+\infty} k \frac{\lambda^{k-1}}{1 + (\bar{\phi} - 1)\lambda^k}.$$

Similarly,

**Proposition 11** If $\alpha < 1$ then a solution $\lambda^*$ to the social planner problem, $\max_{\lambda \in [0,1]} v(\lambda)$, is such that $\lambda^* \in ]0, 1[$ and satisfies

$$\frac{S\alpha}{(\bar{\psi} - 1)} = \frac{(1 - \bar{\psi}; \lambda^*)\ell(\lambda^*)}{\lambda^*} \quad (18)$$

$$\text{where } \ell(\lambda) = \sum_{k=0}^{+\infty} k \frac{\lambda^{k-1}}{1 + (\bar{\psi} - 1)\lambda^k}.$$

The interpretation of Propositions 10 and 11 relies on the remark that $(1-\bar{\phi};\lambda)h(\lambda)/\lambda$ is an increasing function of $\lambda$ (see the proof of Proposition 10). Hence, the larger $\bar{\phi}$ or $\bar{\psi}$ are, the larger $\lambda^*$ is. Namely, the less fragile the network, the more intensive can the public debate be while avoiding the risk of instability. Similarly, the larger $S$ is, the larger $\lambda^*$ is. Hence, the more flexible the society is with respect to divergence in opinions (as measured through the threshold $\sigma$ at which a link breaks), the more intensive the public debate can be. Overall, to determine the optimal characteristics of the public debate, the social planner must account for both structural and behavioral characteristics: how fragile is the social network (as measured through $\bar{\phi}$ or $\bar{\psi}$) and to which extent individuals tolerate disagreement with their peers (as measured through the threshold $\sigma$).
## 5.3 Campaign strategies and polarization

We then consider the setting of a political campaign, in which the intensity of the debate might also be influenced by candidates and, in turn, how this might induce polarization in society. In practice, candidates might influence the intensity of the debate through a number of means such as the choice of more or less controversial campaign topics, the attitude they adopt towards their opponents (from direct attack to indifference) and more broadly, the frequency, target and content of their communication.

Formally, we consider a setting where two candidates $\mathcal{L}$ and $\mathcal{R}$ aim at maximizing their electorate that consists in the set of agents having a negative and a positive asymptotic opinion, respectively. That is, agents $\mathcal{L}$ and $\mathcal{R}$ have utility functions defined respectively by:

$$u_{\mathcal{L}}(x) = \mathrm{card}\{i \in \mathcal{N} \mid x(i) \le 0\}$$

and

$$u_{\mathcal{R}}(x) = \mathrm{card}\{i \in \mathcal{N} \mid x(i) \ge 0\}.$$

We assume that the agents focus on the limit opinions $x_{\lambda}(\infty)$ that get formed in a decreasing opinion network formation process (i.e., such $\tau = 0$ and $\sigma < +\infty$). Furthermore, for sake of simplicity, we restrict attention to initial distributions of opinions that are symmetric in the following sense:

**Definition 6** A distribution $x \in [-1, 1]^N$ of opinions is symmetric with respect to $\gamma \in [-1, 1]$ if for all $\omega \in [-1, 1]$,

$$\mathrm{card}\{i \in \mathcal{N} \mid x(i) = \omega\} = \mathrm{card}\{i \in \mathcal{N} \mid x(i) = 2\gamma - \omega\}.$$

It is straightforward to show that if the network $G$ is compatible (symmetric) and the initial distribution of opinions is symmetric with respect to $\gamma$, then the distribution of opinions remains symmetric with respect to $\gamma$ at each time as well as asymptotically.

If the initial distribution of opinions is symmetric with respect to 0, then one has for all $\lambda \in [0, 1]$, $u_{\mathcal{L}}(x_{\lambda}(\infty)) = u_{\mathcal{R}}(x_{\lambda}(\infty))$, and thus none of the agents has an incentive to influence $\lambda$. Situations of interest are rather settings where the initial distribution of opinions is symmetric with respect to $\gamma \neq 0$. In this setting, if $\gamma > 0$, then by symmetry one has for all $\lambda \in [0, 1]$, $u_{\mathcal{L}}(x_{\lambda}(\infty)) \le u_{\mathcal{R}}(x_{\lambda}(\infty))$ and thus agent $\mathcal{R}$ can be dubbed the majority candidate. Accordingly, if $\gamma < 0$, then one has for all $\lambda \in [0, 1]$, $u_{\mathcal{L}}(x_{\lambda}(\infty)) \ge u_{\mathcal{R}}(x_{\lambda}(\infty))$ and thus agent $\mathcal{L}$ can be dubbed the majority candidate. Note that, because symmetry with respect to $\gamma$ is conserved, the majority candidate remains so across time. Nevertheless, both candidates might have incentives to influence $\lambda$ so as to increase the absolute size of their electorate. The complex dynamics of the model prevents a general analytic characterization of polarization and asymptotic behavior as a function of $\lambda$, even in our simplified setting [see Blondel et al., 2007, for a related discussion, in particular, the 2R conjecture in the Hegselmann-Krause model]. However, we show below, by means of examples, that both the majority and the minority candidates can have incentives to increase the intensity of the debate up to the level where the society polarizes. Without loss of generality, we focus on the case where $\mathcal{R}$ is the majority candidate.
**Example 1 (Polarization by the minority candidate)** We first consider a setting with 7 agents where the initial distribution of opinions is given by

$$x(0) = [k, k, k, (3k+1)/4, (k+1)/2, (k+3)/4, 1, 1, 1]$$

for $k = -0.5$. Thus $x$ is symmetric with respect to $(k+1)/2 > 0$ and agent $R$ is the majority candidate. We further consider $\sigma = 0.5$. Figure 5 illustrates the incentives of each agent with respect to the intensity of the debate by reporting the utilities of both agents, $u_L(x_\lambda(\infty))$ and $u_R(x_\lambda(\infty))$, as well as the number of connected components as a function of $\lambda \in [0, 1]$. The majority candidate has incentives to maintain $\lambda$ in an intermediate range where no polarization takes place (there remains a single connected component), but the intensity of the debate is sufficient to shift all opinions towards a positive value. The utility of the minority candidate evolves non-monotonously with $\lambda$. On the one hand, he is satisfied with very low values of $\lambda$ for which opinions are hardly influenced by the network. On the other hand, and perhaps more importantly, once $\lambda$ is above a certain threshold, he has incentives to increase $\lambda$ up to the threshold where the network polarizes and agents with negative opinions can no longer be influenced by agents with positive opinions. In other words, the minority candidate has incentives to exacerbate the public debate so as to separate his electorate from the majority.

<figure><img src="image_6.png" /><figcaption>Figure 5: Values of $u_L(x_\lambda(\infty))$ (blue), of $u_R(x_\lambda(\infty))$ (orange) and of the number of connected components (yellow) in $G_\lambda$ for $\lambda$ varying between 0 and 1. 100 Simulations were run for values of $\lambda$ between 0 and 1 with a step size of 0.01 (values of $\lambda$ are reported in percentage terms). Values were approximated by setting $T = 100$.</figcaption></figure>

**Example 2 (Polarization by the majority candidate)** We then consider a setting with 30 agents where the initial distribution of opinions $x$ is such that 8 agents have opinion $k$, 1 agent has opinion $(5k+1)/6$, 4 agents have opinion $(4k+2)/6$, 1 agent has opinion $(k+1)/2$, 4 agents have opinion $(2k+4)/6$, 1 agent has opinion $(k+5)/6$, and 8 agents have opinion 1 for $k = -0.5$. Thus $x$ is symmetric with respect to $(k+1)/2 > 0$ and candidate $R$ is the majority candidate. We further consider $\sigma = 0.4$. As above, Figure 6 illustrates the
incentives of each candidate with respect to the intensity of the debate. Here, the majority candidate has incentives to increase the intensity of the debate up to the point where there is polarization of the network. More precisely, the network separates in three components (left, center and right) and, due to polarization, the majority candidate is able to fully "capture" the central component, whereas in the absence of polarization, the left part of this central component would remain in the electorate of the minority candidate.

<figure><img src="image_7.png" /><figcaption>Figure 6: Values of $u_L(x_\lambda(\infty))$ (blue), of $u_R(x_\lambda(\infty))$ (orange) and of the number of connected components (yellow) in $G_\lambda$ for $\lambda$ varying between 0 and 1. 100 Simulations were run for values of $\lambda$ between 0 and 1 with a step size of 0.01 (values of $\lambda$ are reported in percentage terms). Values were approximated by setting $T = 100$.</figcaption></figure>

These two examples show that both the minority and majority candidates can have incentives to lead the society towards polarization. In both cases, the “polarizing” candidates aim to prevent their voters from interacting with the rest of society and thus the emergence of more consensual opinions. In other words, sectarianism can be waged by both the minority and the majority.

# 6 Conclusion

In the paper we have proposed a model of the joint evolution of opinions and social relationships in which social influence decays over time. This simple model naturally gives rise to strong diversification: heterogeneous opinions can persist in a connected network. Two main parameters govern the dynamics of our model: the intensity of social interactions and the threshold above which agents with different opinions sever their connection. Notably, the risk of polarization increases and the distance to consensus, conditional on no polarization, decreases with the intensity of social interactions.

Our model allows to frame the problem of the design of public debates in a formal setting. We characterize the optimal strategy for a social planner who controls the intensity
of the public debate and thus faces a trade-off between the pursuit of social consensus and the risk of polarization. We also consider applications to political campaigning and show that both minority and majority candidates can have incentives to lead society towards polarization.

More broadly, the applications of existing models of opinion dynamics are strongly constrained by the built-in convergence of opinions towards a consensus. By defining simple dynamics leading to strong diversification, our model could substantially extend this scope of applications, e.g., to dynamics in multiplex networks, the evolution of preferences or the formation of trends and fashions.

## Appendix A: Some related models

We briefly recall some related frameworks with continuous opinions.

* The French-DeGroot model (French [1956], DeGroot [1974]):
Let $\mathcal{N} = \{1, \dots, N\}$ be the set of agents forming (continuous) opinions over time. Let $x_i(t) \in [0, 1]$ denote the opinion of agent $i$ at time $t$, and $x(t) \in [0, 1]^N$ the opinion vector at time $t$. By $w_{ij}$ we denote the weight put by agent $i$ on opinion of agent $j$. We suppose that $w_{ij} \ge 0$ and $\sum_j w_{ij} = 1$ for all $i$, i.e., the weight matrix $W = [w_{ij}]$ is row-stochastic. At each time step, every agent $i$ updates his opinion $x_i(t)$ by averaging the opinion of the others: $x_i(t+1) = \sum_j w_{ij}x_j(t)$. In other words, we have

$$x(t+1) = Wx(t) = W^{t+1}x(0)$$

To the matrix $W$ we associate a directed graph with the set of nodes $\{1, \dots, N\}$ such that an arc $(i, j)$ exists if and only if $w_{ij} > 0$. If $W$ is primitive (i.e., if $W^k > 0$ for some integer $k$, where $W^k = [w_{ij}^{(k)}]$ denotes the $k$th power of matrix $W$), then all agents converge to consensus $\bar{x}$, obtained by $\bar{x} = v^T x(0)$, where $v$ is the left eigenvector of $W$. As the final consensus is a weighted sum of the original opinion, $v_i$ can be seen as the weight or social power of agent $i$ in the final consensus.

* The Friedkin-Johnsen model (Friedkin and Johnsen [1990]):
We have

$$x(k+1) = \Lambda W x(k) + (I - \Lambda)u$$

where the matrix $W$ is as in the French-DeGroot model, $\Lambda = \text{diag}(\lambda_1, \dots, \lambda_n)$ with $\lambda_i \in [0, 1]$ being the susceptibility of agent $i$ to social influence, and $u$ is a constant vector of agents' prejudices, e.g., $u_i = x_i(0)$. If $\Lambda = I$, then we recover the French-DeGroot model.

* Time-varying (DeGroot) models (see Proskurnikov and Tempo [2018] for an overview):
In these models, typically

$$x(t+1) = A(t, x(t))x(t)$$

where $A(t)$ is (usually) a row-stochastic matrix. Below, we recall two examples of such time-varying models.
* The DeMarzo-Vayanos-Zwiebel model (DeMarzo et al. [2003]):
The updating is done as follows

$$x(t + 1) = [(1 - \lambda_t)I + \lambda_t G]x(t)$$

with $\lambda_t \in ]0, 1]$ and $W$ being row-stochastic. Supposing that $G$ is irreducible (i.e., for every $i, j \in N$ there exists an integer $m(i, j)$ such that $g_{ij}^{(m(i,j))} > 0$) and $\sum_{t=0}^{\infty} \lambda_t = \infty$, there is convergence to consensus:

$$\lim_{t \to \infty} x(t) = w^T x(0) \mathbf{1}$$

where $w$ is the left eigenvector of $G$ associated to 1.

Beyond considering a fixed network, i.e., $\tau = 0$ and $\sigma = +\infty$, a major difference between our approach and that of DeMarzo et al. [2003] is that we consider $\lambda_t = \lambda^t$ and thus generically, i.e., unless $\lambda = 1$, we have $\sum_{t=0}^{\infty} \lambda_t = 1/(1-\lambda) < +\infty$. In other words, DeMarzo et al. [2003] focus on dynamics where limit opinions are determined by the asymptotic properties of the diffusion process whereas, in our setting, transient properties matter.

* Bounded confidence models (Krause [2000], Dittmer [2001], Hegselmann and Krause [2002]):

Let $\delta > 0$ be the range of confidence. For a given opinion profile $x \in \mathbb{R}^N$, we define for each agent $i$, $I_i(x) = \{j : |x_j - x_i| \le \delta\} \ni \{i\}$ the set of “trusted” individuals by $i$, i.e., whose opinions lie in $i$'s confidence interval $[x_i - \delta, x_i + \delta]$. Agent $i$ updates his opinion by taking the average of opinions of the trusted individuals:

$$x_i(k + 1) = \frac{1}{|I_i(x(k))|} \sum_{j \in I_i(x(k))} x_j(k) \quad (i = 1, \dots, N)$$

This is known as the Hegselmann-Krause (HK) model and can be seen as a French-DeGroot model with time-varying matrix $W$. The HK model supposes that every agent is aware of the opinion of every other agent, implying the existence of an underlying complete network. For any $x(0)$, we get convergence to a vector $\bar{x}$ in a finite number of steps, with the property that for each distinct $i, j$, either $\bar{x}_i = \bar{x}_j$ (consensus) or $|\bar{x}_i - \bar{x}_j| > \delta$ (distrust).

There is some fundamental property: if $x_{j_1}(k) \le x_{j_2}(k) \le \dots \le x_{j_N}(k)$, then it holds $x_{j_1}(k') \le x_{j_2}(k') \le \dots \le x_{j_N}(k')$ for every $k' > k$.

$(x_i, \dots, x_m)$ is a $\delta$-chain if all the distances between two consecutive opinions are $\le \delta$. Then the opinion vector $x$ is formed by a set of maximal $\delta$-chains. Maximal $\delta$-chains of length at least 5 can split. Others necessarily collapse into a consensus.

# Appendix B: External stability

Symmetrically to the case of “internal” stability considered above, we can provide necessary and sufficient conditions for the network to be “externally” stable, i.e., conditions
under which there is no creation of links<fnref n="9" />. In this setting, the dual notion to that maximal link is that of minimal gap.

**Definition 7** A pair {$i, j$} $\notin \mathcal{G}$ is a minimal gap if for all {$i', j'$} $\neq \{i, j\}$ such that $i \le i'$ and $j' \le j$, one has {$i', j'$} $\in \mathcal{G}$, i.e., {$i', j'$} is a link.

As for maximal link and internal stability, it is sufficient to study under which condition a minimal gap {$i, j$} becomes a link to ensure external stability of the network. We also use the same notion of local structure ($L, R, M, (\ell_m)_{m=1,...,M}, (r_m)_{m=1,...,M}$) around {$i, j$}. Then we introduce the repulsiveness of $i, j$ as

$$ \pi_{i,j}(\mathcal{G}) = \min_{m \in \{0,...,M\}} \frac{(L+M+1)(2R-r_{m+1}+1) + (R+M+1)(L-\ell_m) + (L-R)(M-m)}{(L+M+1)(R+M+1)} \quad (19) $$

letting $r_0 = 0$ and $\ell_{M+1} = 0$.

We then have the following counterpart for Proposition 1.

**Proposition 12** Let $\sigma, \tau, \lambda$ be given and {$i, j$} be a minimal gap in a network $\mathcal{G}(t)$. Then one has {$i, j$} $\notin \mathcal{G}(t+1)$ for every $x(t)$ ($\sigma, \tau$)-consistent with $\mathcal{G}(t)$ if and only if $\pi_{i,j}(\mathcal{G}(t)) \ge 1$.

Accordingly, we have the counterpart of Proposition 2 that bounds the contraction of a minimal gap as a function of $\pi_{i,j}$.

**Proposition 13** Let $\sigma, \tau, \lambda$ be given and $(x(t), \mathcal{G}(t))$ be a $(\sigma, \tau)$-consistent network opinion pair. Let then {$i, j$} $\in \mathcal{G}(t)$ be a minimal gap, one has:

$$ x_j(t+1) - x_i(t+1) \ge \tau[1 + (\pi_{i,j}(\mathcal{G}(t)) - 1)\lambda^t], \quad (20) $$

Note that this Proposition can be extended along the lines of Proposition 2 by considering network opinion pairs with differences in opinions that are uniformly bounded below by $\rho \ge \tau$.

We end this section by giving some illustrative particular cases.

* Considering $L = R$, the optimal value of $m$ is easy to obtain as a solution of the minimization problem

$$ \min_{m \in \{0,...,m\}} (r_{m+1} + \ell_m). $$

* The case $\ell_m = r_m = 0$ for all $m$ yields, as optimal value of $m$, $m = M$ when $L > R$ and $m = M$ when $L < R$, while for $L = R$, the value of the fraction does not depend on $m$ anymore, so that

$$ \pi_{i,j} = \frac{3L+1}{L+M+1}. $$

Then $\pi_{i,j} \le 1$ if and only if $2L \le M$.

<footnote n="9">⁹As it is our core focus in the remaining of the paper, we use indifferently internal stability and stability. Accordingly, we explicitly refer to external stability when the latter is implied.</footnote>
# Appendix C: Estimation of the probability of polarization

Table 1 provides the results of the logistic regression of the probability of polarization over the first-order approximation of the q-series $\bar{\psi}_1 := (1 + (\bar{\psi} - 1))(1 + (\bar{\psi} - 1)\lambda)$ performed separately for each value of the edge-connectedness parameter. For each model, the estimation relies on 104990 observations with varying initial distribution of

<table><caption>Table 1: Logistic regression of the probability of polarization Each column corresponds to the estimation of the probability of polarization for different values of the edge-connectedness parameter. For each column, the model was specified as follows: $\text{logit}(y) \sim \alpha + \beta \bar{\psi}_1$.</caption><thead><tr><th></th><th>edge-connect=1</th><th>edge-connect=2</th><th>edge-connect=3</th><th>edge-connect=4</th></tr></thead><tbody><tr><td>(Intercept)</td><td>β = -13.6<br>SE = 0.331<br><b>p&lt;0.0001</b></td><td>β = -14.1<br>SE = 0.367<br><b>p&lt;0.0001</b></td><td>β = -15.9<br>SE = 0.463<br><b>p&lt;0.0001</b></td><td>β = -18.4<br>SE = 0.597<br><b>p&lt;0.0001</b></td></tr><tr><td>ψ<sub>1</sub></td><td>β = +4.68<br>SE = 0.115<br><b>p&lt;0.0001</b></td><td>β = +3.64<br>SE = 0.0969<br><b>p&lt;0.0001</b></td><td>β = +3.65<br>SE = 0.109<br><b>p&lt;0.0001</b></td><td>β = +3.88<br>SE = 0.129<br><b>p&lt;0.0001</b></td></tr><tr><td>adj.R<sup>2</sup></td><td>0.84</td><td>0.77</td><td>0.76</td><td>0.77</td></tr><tr><td>N<sub>obs</sub></td><td>104990</td><td>104990</td><td>104990</td><td>104990</td></tr></tbody></table>

,

# Appendix D: Proofs

## Proof of Remark 1

Assume $(x(1), G(1))$ is not compatible. To simplify notations, let us denote $x$ for $x(1)$. If $x$ is not compatible, there exist $i, j$ such that $x_i < x_j$ and either $x_{n_{-}(i)} > x_{n_{-}(j)}$ or $x_{n_{+}(i)} > x_{n_{+}(j)}$. Assuming the former (the argument is much the same for the latter case) implies that $x_i - x_{n_{-}(j)} < x_j - x_{n_{-}(j)} < \sigma$. Therefore, by compatibility $i$ and $n_{-}(j)$ should be linked, which contradicts the definition of $n_{-}(i)$. □

## Proof of Remark 2

Assume $(x(0), G(0))$ is not compatible. Then, there exist $i, j$ such that $x(0)_i < x(0)_j$ and either $x(0)_{n_{-}(i)} > x(0)_{n_{-}(j)}$ or $x(0)_{n_{+}(i)} > x(0)_{n_{+}(j)}$. Assuming the former (the argument is much the same for the latter case) implies that $\sigma \le x(0)_i - x(0)_{n_{-}(j)} < x(0)_j - x(0)_{n_{-}(j)} < \tau$, which contradicts $\tau \le \sigma$. □

## Proof of Lemma 1

(i) If $x_i(t) = x_j(t)$ then, as $(x(t), G(t))$ is compatible, $i$ and $j$ have the same neighbors, so they will evolve identically.
We shall then prove that (ii) and (iii) hold for $t' = t + 1$. The general case follows by an immediate recursion.

(ii) Observe that if $\lambda = 0$, then $x_i(t') = x_i(t)$ for all $t' > t$ and $i$. Hence, the result is trivially true. We consider then $\lambda \neq 0$. By (2), $x_i(t+1)$ is a weighted arithmetic mean of the $x_j(t)$, $j \in N_{\mathcal{G}(t)}(i)$, with positive weights, from which we deduce that $x_{n_{-}(i)} < x_i(t+1) < x_{n_{+}(i)}$. It follows that if the neighborhoods of $i$ and $j$ are disjoint, we have $x_i(t+1) < x_j(t+1)$.

Suppose then that they intersect. Suppose first that $i$ and $j$ are separated only by common neighbors and that there is no agent to the left of $i$ in its neighborhood, and no agent to the right of $j$ in its neighborhood. If $i$ and $j$ are neighbors, then $N_{\mathcal{G}(t)}(i) = N_{\mathcal{G}(t)}(j)$, and we have by uniformity of the graph, letting $m := |N_{\mathcal{G}(t)}(i)|$,

$$ 
\begin{aligned}
x_i(t+1) &= (1-\lambda)x_i(t) + \frac{\lambda}{m} \sum_{k \in N_{\mathcal{G}(t)}(i)} x_k(t) \\
x_j(t+1) &= (1-\lambda)x_j(t) + \frac{\lambda}{m} \sum_{k \in N_{\mathcal{G}(t)}(i)} x_k(t),
\end{aligned} 
\quad (21) $$

from which we deduce that $x_i(t+1) \le x_j(t+1)$, with strict inequality if $\lambda \neq 1$. If $i$ and $j$ are not neighbors, then $N_{\mathcal{G}(t)}(i) = \{i\} \cup N_{\mathcal{G}(t)}(i) \cap N_{\mathcal{G}(t)}(j)$ and $N_{\mathcal{G}(t)}(j) = N_{\mathcal{G}(t)}(i) \cap N_{\mathcal{G}(t)}(j) \cup \{j\}$. Putting $m := |N_{\mathcal{G}(t)}(i) \cap N_{\mathcal{G}(t)}(j)|$, we have

$$ 
\begin{aligned}
x_i(t+1) &= \left(1 - \lambda + \frac{\lambda}{m+1}\right)x_i(t) + \frac{\lambda}{m+1} \sum_{k \in N_{\mathcal{G}(t)}(i) \cap N_{\mathcal{G}(t)}(j)} x_k(t) \\
x_j(t+1) &= \left(1 - \lambda + \frac{\lambda}{m+1}\right)x_j(t) + \frac{\lambda}{m+1} \sum_{k \in N_{\mathcal{G}(t)}(i) \cap N_{\mathcal{G}(t)}(j)} x_k(t),
\end{aligned} 
\quad (22) $$

from which we deduce that $x_i(t+1) < x_j(t+1)$. Next, suppose that $N_{\mathcal{G}(t)}(j)$ contains some agent $j' \neq j$ and $j' \notin N_{\mathcal{G}(t)}(i)$. Then, supposing $i$ and $j$ are neighbors, (21) becomes

$$ x_j(t+1) = (1-\lambda)x_j(t) + \frac{\lambda}{m+1} \left( \sum_{k \in N_{\mathcal{G}(t)}(i)} x_k(t) + x_{j'}(t) \right). $$

We have

$$ 
\begin{aligned}
& \frac{\lambda}{m+1} \left( \sum_{k \in N_{\mathcal{G}(t)}(i)} x_k(t) + x_{j'}(t) \right) - \frac{\lambda}{m} \sum_{k \in N_{\mathcal{G}(t)}(i)} x_k(t) \\
&= \left( -\frac{\lambda}{m(m+1)} \right) \sum_{k \in N_{\mathcal{G}(t)}(i)} x_k(t) + \frac{\lambda}{m+1} x_{j'}(t) \\
&= \frac{\lambda}{m+1} \left( -\frac{1}{m} \sum_{k \in N_{\mathcal{G}(t)}(i)} x_k(t) + x_{j'}(t) \right) > 0
\end{aligned} 
$$
because $x'_j(t) > x_k(t)$ for any $k \in N_{\mathcal{G}(t)}(i)$. It follows that the addition of $j'$ makes $x_j(t+1)$ strictly greater, and so will be the addition of any number of such $j'$. Suppose now that $i$ and $j$ are not neighbors. Rewriting (22) as

$$x_j(t+1) = (1-\lambda)x_j(t) + \frac{\lambda}{m+1}\left(\sum_{k \in N_{\mathcal{G}(t)}(i) \cap N_{\mathcal{G}(t)}(j)} x_k(t) + x_j(t)\right)$$

and proceeding as above yields to the same conclusion. By a similar reasoning, one finds that the addition of any (number of) $i'$ in $N_{\mathcal{G}(t)}(i)$ not in $N_{\mathcal{G}(t)}(j)$ makes $x_i(t+1)$ strictly smaller. Therefore, $x_i(t+1) \le x_j(t+1)$ in any situation, with strict inequality if $\lambda \ne 1$.

(iii) Assume thus that $(x(t+1), \mathcal{G}(t+1))$ is not compatible. Then, there exist $i, j$ such that $x(t+1)_i < x(t+1)_j$ and either $x(t+1)_{n_-(\mathcal{G}(t+1),i)} > x(t+1)_{n_-(\mathcal{G}(t+1),j)}$ or $x(t+1)_{n_+(\mathcal{G}(t+1),i)} > x(t+1)_{n_+(\mathcal{G}(t+1),j)}$. Let us assume the former (the argument is much the same for the latter case), which implies in particular that $n_-(\mathcal{G}(t+1),j) \notin N_{\mathcal{G}(t+1)}(i)$ and $n_-(\mathcal{G}(t+1),j) \in N_{\mathcal{G}(t+1)}(j)$. Furthermore, one either has $n_-(\mathcal{G}(t+1),j) \in N_{\mathcal{G}(t)}(i)$ or $n_-(\mathcal{G}(t+1),j) \notin N_{\mathcal{G}(t)}(i)$.

* If $n_-(\mathcal{G}(t+1),j) \in N_{\mathcal{G}(t)}(i)$, as $n_-(\mathcal{G}(t+1),j) \notin N_{\mathcal{G}(t)}(i)$, one must have

$$\sigma \le x(t+1)_i - x_{n_-(\mathcal{G}(t+1),j)} \le x(t+1)_j - x_{n_-(\mathcal{G}(t+1),j)},$$

which contradicts $n_-(\mathcal{G}(t+1),j) \in N_{\mathcal{G}(t+1)}(j)$.

* If $n_-(\mathcal{G}(t+1),j) \notin N_{\mathcal{G}(t)}(i)$, using (ii) one has $x(t)_i < x(t)_j$ and by compatibility of $(x(t), \mathcal{G}(t))$ that $n_-(\mathcal{G}(t+1),j) \notin N_{\mathcal{G}(t)}(j)$. Thus $n_-(\mathcal{G}(t+1),j) \notin N_{\mathcal{G}(t+1)}(j)$ implies

$$x(t+1)_i - x_{n_-(\mathcal{G}(t+1),j)} \le x(t+1)_j - x_{n_-(\mathcal{G}(t+1),j)} < \tau$$

which contradicts $n_-(\mathcal{G}(t+1),j) \notin N_{\mathcal{G}(t+1)}(i)$.

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

## Proof of Proposition 1

Let us decompose the opinion vector $x(t)$ as follows in the vicinity of $i, j$:

* $(x_m)_{m=0,...,M+1}$ the opinions of the nodes between $i$ and $j$ ($x_0$ being the opinion of $i$ and $x_{M+1}$ the opinion of $j$),

* $(y_l)_{l=1,...,L}$ the opinions of the nodes to the left of $i$ (assuming the nodes are labelled by increasing distance to $i$),

* $(z_r)_{r=1,...,R}$ the opinions of the nodes to the right of $j$ (assuming the nodes are labelled by increasing distance to $j$).
Assuming $\lambda = 1$, the difference between the updated opinions of $j$ and $i$ is then given by:

$$ \Delta(x, y, z) = x_j(t+1) - x_i(t+1) = \frac{\sum_{r=1}^{R} z_r + \sum_{m=0}^{M+1} x_m}{R+M+2} - \frac{\sum_{\ell=1}^{L} y_\ell + \sum_{m=0}^{M+1} x_m}{L+M+2}, $$

that is,

$$ \Delta(x, y, z) = \frac{(L+M+2)\sum_{r=1}^{R} z_r + (L+M+2)\sum_{m=0}^{M+1} x_m - (R+M+2)\sum_{\ell=1}^{L} y_\ell - (R+M+2)\sum_{m=0}^{M+1} x_m}{(L+M+2)((R+M+2))} $$

or equivalently

$$ \Delta(x, y, z) = \frac{(L + M + 2) \sum_{r=1}^{R} z_r - (R + M + 2) \sum_{\ell=1}^{L} y_\ell + (L - R) \sum_{m=0}^{M+1} x_m}{(L + M + 2)(R + M + 2)} \quad (23) $$

The local structure being fixed, we want to know the maximum value taken by $\Delta(x, y, z)$, under the constraint that $(x(t), \mathcal{G}(t))$ is $(\sigma, \tau)$-compatible. In particular, we want to know when this maximal value exceeds $x_j(t) - x_i(t)$, in which case we say that there is expansion of the link.

1. We claim that $\lambda = 1$ is the most unfavorable case, in the sense that if expansion occurs with $\lambda = 1$, then its extent is smaller with $\lambda < 1$, and if it does not occur with $\lambda = 1$ then it does no occur with $\lambda < 1$. Indeed, denoting by $\Delta_\lambda(x, y, z)$ the difference of the opinions $x_j(t+1) - x_i(t+1)$ with $\lambda < 1$, we find:

$$ \Delta_{\lambda}(x, y, z) = \lambda^{t}\Delta(x, y, z) + (1 - \lambda^{t})(x_{j}(t) - x_{i}(t)) < \Delta(x, y, z) $$

as $x_j(t) - x_i(t) < \Delta(x, y, z)$ when assuming expansion. Now, if there is no expansion, then $\Delta_\lambda(x, y, z) < x_j(t) - x_i(t)$, and again no expansion occurs. As a consequence, we can assume $\lambda = 1$ w.l.o.g.

Also, without loss of generality, we can fix $x_0 = 0$ and $x_{M+1} = \sigma$, in which case expansion means severance of the link.

2. Assuming the network-opinion pair is $(\sigma, \tau)$ compatible yields the following constraints on opinions in the vicinity of $i, j$.

$$ \left\{ \begin{array}{ll} \forall m \in \{1, \dots, M\} & \forall \ell \le \ell_m \qquad x_m - y_\ell \le \sigma \\ \forall m \in \{1, \dots, M\} & \forall \ell > \ell_m \qquad x_m - y_\ell > \tau \\ \forall m \in \{1, \dots, M\} & \forall r \le r_m \qquad z_r - x_m \le \sigma \\ \forall m \in \{1, \dots, M\} & \forall r > r_m \qquad z_r - x_m > \tau \\ \forall m \in \{0, \dots, M+1\} & \forall r \in \{1, \dots, R\} \qquad x_m < z_r \\ \forall m \in \{0, \dots, M+1\} & \forall \ell \in \{1, \dots, L\} \qquad x_m > y_\ell \\ \forall m \in \{0, \dots, M\} & x_m \le x_{m+1} \\ & x_{M+1} \le x_0 + \sigma \end{array} \right. $$

Determining the largest value of $\Delta(x, y, z)$ among all possible network-opinion pairs thus amounts to solving the linear program corresponding to the maximization of $\Delta(x, y, z)$ under the latter constraints. One can further note that, by an immediate continuity argument, the value of the problem is unchanged if the strict inequalities $z_r - x_m > \tau$ and $z_r - x_m > \tau$ are replaced by weak ones.
Let us then observe that

$$y_L \le \cdots \le y_1 \le 0 \le x_1 \le \cdots \le x_M \le \sigma \le z_1 \le \cdots \le z_R$$

and that the constants satisfy

$$0 \le \ell_M \le \cdots \le \ell_1 \le L, \quad 0 \le r_1 \le \cdots \le r_M \le R$$

we come up with the following LP, where the set of constraints is irredundant:

$$\max_{x,y,z} \Delta(x,y,z) \text{ under}$$

$$x_m \le x_{m+1}, \qquad m = 0, \dots, M$$

$$z_r \le z_{r+1}, \qquad r = 1, \dots, R-1$$

$$z_1 \ge \sigma$$

$$z_R \le 2\sigma \qquad \ell = 1, \dots, L-1$$

$$y_\ell \ge y_{\ell+1},$$

$$y_L \ge -\sigma$$

$$x_m - y_{\ell_m} \le \sigma, \qquad m = 1, \dots, M$$

$$x_m - y_{\ell_m+1} \ge \tau, \qquad m = 1, \dots, M$$

$$z_{r_m} - x_m \le \sigma, \qquad m = 1, \dots, M$$

$$z_{r_m+1} - x_m \ge \tau, \qquad m = 1, \dots, M.$$

and $y_0 = 0$, $z_0 = \sigma$. Note however that when $\ell_m = 0$ or $r_m = 0$, the corresponding constraints are redundant and can be omitted. There are $L + R + M$ variables and $R + L + 5M + 3$ constraints.

3. Note that for a given $\bar{x} := (\bar{x}_m)_{m=0,\dots,M+1}$, the solution of the LP is trivially determined by maximizing $\sum_{r=1}^R z_r$ and minimizing $\sum_{\ell=1}^L y_\ell$ while satisfying the constraints, i.e., by setting for each $r \in \{1, \dots, R\}$:

$$\bar{z}_r(\bar{x}) = \min_{\{m|r \le r_m\}} (\bar{x}_m + \sigma) := \bar{z}_r$$

and for each $\ell \in \{1, \dots, L\}$,

$$\bar{y}_\ell(\bar{x}) = \max_{\{m|\ell \le \ell_m\}} (\bar{x}_m - \sigma) := \bar{y}_\ell.$$

Hence, the solution of the LP amounts to determining $\bar{x}$ such that $\Delta(\bar{x}, \bar{y}(\bar{x}), \bar{z}(\bar{x}))$ is maximal.

We now show that only solutions with $x_m = 0$ or $x_m = \sigma$ for all $m$ can be optimal. It suffices to show that they are basic solutions (in the LP sense) and others are not.

Take $\bar{x}$ with $\bar{x}_m = 0$ for $m \le m_0$ and $\bar{x}_m = \sigma$ for $m > m_0$, for a fixed $0 \le m_0 \le M$. Observe that this imposes that $\bar{y}_1 = \cdots = \bar{y}_{\ell_{m_0+1}} = 0$ and $\bar{y}_{\ell_{m_0+1}+1} = \cdots = \bar{y}_L = -\sigma$, and $\bar{z}_1 = \cdots = \bar{z}_{r_{m_0}} = \sigma$, $\bar{z}_{r_{m_0+1}} = \cdots = \bar{z}_R = 2\sigma$, taking the convention $r_0 = 0$ and
$\ell_{M+1} = 0$. This solution $(\bar{x}, \bar{y}, \bar{z})$ is feasible and the set of tight constraints contains in particular the following system, assuming $0 < m_0 < M$ (the other cases are similar):

$$
\begin{align*}
x_m &= x_{m+1}, & m &= 0, \dots, m_0 - 1, m_0 + 1, \dots, M \\
z_r &= z_{r+1}, & r &= 1, \dots, r_{m_0} - 1, r_{m_0} + 1, \dots, R - 1 \\
z_1 &= \sigma \\
z_R &= 2\sigma \\
y_\ell &= y_{\ell+1}, & \ell &= 1, \dots, \ell_{m_0+1} - 1, \ell_{m_0+1} + 1, \dots, L - 1 \\
y_1 &= 0 \\
y_L &= -\sigma
\end{align*}
$$

which gives as unique solution $(\bar{x}, \bar{y}, \bar{z})$. Hence, it is a basic solution (extreme point of the polyhedron of feasible points).

Let us modify the point as follows: $\bar{x}_m = 0$ for $m < m_0$, $\bar{x}_{m_0} \in ]0, \sigma[$ fixed, and $\bar{x}_m = \sigma$ for $m > m_0$. Then $\bar{y}_1 = \cdots = \bar{y}_{\ell_{m_0+1}} = 0$, $\bar{y}_{\ell_{m_0+1}+1} = \cdots = \bar{y}_{\ell_{m_0}} = x_{m_0} - \sigma$, and $\bar{y}_{\ell_{m_0}+1} = \cdots = \bar{y}_L = -\sigma$, and $\bar{z}_1 = \cdots = \bar{z}_{r_{m_0-1}} = \sigma$, $\bar{z}_{r_{m_0-1}+1} = \cdots = \bar{z}_{r_{m_0}} = x_{m_0} + \sigma$, and $\bar{z}_{r_{m_0}+1} = \cdots = \bar{z}_R = 2\sigma$. This solution is still feasible and induces the following set of tight constraints:

$$
\begin{align*}
x_m &= x_{m+1}, & m &= 0, \dots, m_0 - 2, m_0 + 1, \dots, M \\
z_r &= z_{r+1}, & r &= 1, \dots, r_{m_0-1} - 1, r_{m_0-1} + 1, \dots, r_{m_0} - 1, r_{m_0} + 1, \dots, R - 1 \\
z_1 &= \sigma \\
z_R &= 2\sigma \\
y_\ell &= y_{\ell+1}, & \ell &= 1, \dots, \ell_{m_0+1} - 1, \ell_{m_0+1} + 1, \dots, \ell_{m_0} - 1, \ell_{m_0} + 1, \dots, L - 1 \\
y_1 &= 0 \\
y_L &= -\sigma \\
x_m - y_{\ell m} &= \sigma, & m &= 1, \dots, M \\
z_{r_m} - x_m &= \sigma, & m &= 1, \dots, M,
\end{align*}
$$

and possibly some of the inequalities $x_m - y_{\ell m+1} \ge \tau$ and $z_{r m+1} - x_m \ge \tau$. Observe that
$x_{m_0}, y_{\ell m_0}$ and $z_{r m_0}$ remain undetermined Hence $(\bar{x}, \bar{y}, \bar{z})$ is not a basic solution.

4. Therefore, candidate optimal solutions are the $M + 1$ basic solutions indexed by $m_0$. Plugging these solutions into (23), we find

$$
\begin{align}
\Delta(\bar{x}, \bar{y}, \bar{z})
&= \frac{(L+M+2)(r_{m_0}\sigma + (R-r_{m_0})2\sigma) + (R+M+2)(L-\ell_{m_0+1})\sigma + (L-R)(M-m_0+1)\sigma}{(L+M+2)(R+M+2)} \nonumber \\
&= \sigma\left(\frac{(L+M+2)(2R-r_{m_0}) + (R+M+2)(L-\ell_{m_0+1}) + (L-R)(M-m_0+1)}{(L+M+2)(R+M+2)}\right). \tag{24}
\end{align}
$$

Letting

$$
\phi_{i,j}(\mathcal{G}) = \max_{m_0 \in \{0, \dots, M\}} \frac{(L+M+2)(2R-r_{m_0}) + (R+M+2)(L-\ell_{m_0+1}) + (L-R)(M-m_0+1)}{(L+M+2)(R+M+2)}
$$
yields the desired result, and the link breaks iff $\phi_{i,j}(\mathcal{G}) > 1$. $\square$

**Proof of Proposition 2**

The proof amounts to find the maximal value of $\Delta(\bar{x}, \bar{y}, \bar{z})$, as in the case of Proposition 1, under the additional constraint that all difference in opinions are bounded by $\rho$. Proceeding as in the proof of Proposition 1, we consider $\lambda = 1$ and $x_j(t) - x_i(t) = \rho$ (most unfavorable case). The maximum value for $x_j(t+1) - x_i(t+1)$ is then given by $\Delta(\bar{x}, \bar{y}, \bar{z}) = \rho\phi_{i,j}$ (see 29), which is attained by the optimal solution.

Letting $x_{M+1} \le \rho$ be arbitrary while keeping the link maximal yields an optimal solution where the $y_\ell$ are either at 0 or $-\rho$ and the $z_r$ are either at $x_{M+1}$ or $x_{M+1} + \rho$. This yields, keeping $\lambda = 1$:

$$ \Delta(\bar{x}, \bar{y}, \bar{z}) = \frac{(L + M + 2)((R - r_{m_0})x_{M+1} + R\rho) + (R + M + 2)(L - \ell_{m_0+1})\rho + (L - R)(M - m_0 + 1)x_{M+1}}{(L + M + 2)(R + M + 2)} $$

Supposing $x_{M+1} \le \rho$ implies that $\Delta(\bar{x}, \bar{y}, \bar{z}) \le \phi_{i,j}\rho$. Thus, we obtain:

$$ x_j(t+1) - x_i(t+1) = G(t)(x_j(t) - x_i(t)) \le \phi_{i,j}\rho $$

so that we can write, with arbitrary $\lambda$:

$$ \begin{aligned} x_j(t+1) - x_i(t+1) &= \lambda^t G(t)(x_j(t) - x_i(t)) + (1 - \lambda^t)(x_j(t) - x_i(t)) \\ &\le \lambda^t \phi_{i,j}\rho + (1 - \lambda^t)(x_j(t) - x_i(t)) \\ &\le [1 + (\phi_{i,j} - 1)\lambda^t]\rho. \end{aligned} $$

$\square$

**Proof of Proposition 3**

We show by induction that $\mathcal{G}(t) = \mathcal{G}(0)$. The result is clearly true for $t = 0$.

Supposing it is true at $t$, then by using (5) one has for every maximal link $\{i, j\}$, $x_j(t+1) - x_i(t+1) \le [1 + (\phi_{i,j} - 1)\lambda^t]\sigma$. Given that the link $\{i, j\}$ is not fragile in $\mathcal{G}(t) = \mathcal{G}(0)$, one has $\phi_{i,j} \le 1$. This yields

$$ x_j(t+1) - x_i(t+1) \le \sigma $$

and thus $\{i, j\} \in \mathcal{G}(t+1)$.

As this holds for all maximal links in $\mathcal{G}(t)$, all maximal links in $\mathcal{G}(t)$ are in $\mathcal{G}(t+1)$ and thus

$$ \mathcal{G}(t+1) = \mathcal{G}(t) = \mathcal{G}(0). $$

$\square$

**Proof of Proposition 7**
We first express the general form of $H(t)$. We have

$$ 
\begin{aligned}
H(1) &= \lambda G + (1 - \lambda)I \\
\cdots &= \cdots \\
H(t-1) &= h_{t-1,t-1}G^{t-1} + h_{t-2,t-1}G^{t-2} + \cdots + h_{0,t-1}I \\
H(t) &= (\lambda^t G + (1 - \lambda^t)I)(h_{t-1,t-1}G^{t-1} + h_{t-2,t-1}G^{t-2} + \cdots + h_{0,t-1}I) \\
&= h_{t,t}G^t + h_{t-1,t}G^{t-1} + \cdots + h_{0,t}I
\end{aligned}
$$

which yields

$$ 
\begin{aligned}
h_{t,t} &= \lambda^t h_{t-1,t-1} = \lambda^{1+2+\cdots+t} = \lambda^{t(t+1)/2} \\
h_{0,t} &= (1 - \lambda^t)h_{0,t-1} = \prod_{i=1}^{t} (1 - \lambda^i) = \lambda^{1+\cdots+t} \prod_{i=1}^{t} \frac{1 - \lambda^i}{\lambda^i} \\
h_{i,t} &= \lambda^t h_{i-1,t-1} + (1 - \lambda^t)h_{i,t-1} \quad (0 < i < t).
\end{aligned}
$$

Observe that $\lim_{t \to \infty} h_{t,t} = 0$. Also, $0 \le h_{0,t} \le 1$ and it is easy to see that the sequence is decreasing. Therefore it converges and $\lim_{t \to \infty} h_{0,t} = \varphi(1/q)$, where $\varphi$ is the Euler function recalled in (9).

We now try to express the general term $h_{i,t}$. To this end, we recall Vieta's formula relating the coefficients of a polynomial with its roots. Let $P(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0$ be a real polynomial of degree $n$ having $n$ roots (distinct or not) $r_1, \dots, r_n$. Then Vieta's formula is

$$ \sum_{1 \le i_1 < i_2 < \cdots < i_k \le n} \left( \prod_{j=1}^{k} r_{i_j} \right) = (-1)^k \frac{a_{n-k}}{a_n}. \qquad (25) $$

Consider our polynomial (8) in $G$ of degree $t$. As $H(t) = M(t)M(t-1)\cdots M(1)$, its $t$ roots are simply $G = (1 - \frac{1}{\lambda^k})I$, for $k = 1, \dots, t$. As $h_{t,t} = \lambda^{t(t+1)/2}$, we obtain

$$ h_{i,t} = (-1)^{t-i} \lambda^{t(t+1)/2} \sum_{1 \le j_1 < j_2 < \cdots < j_{t-i} \le t} \left( \prod_{i=1}^{t-i} \frac{\lambda^{j_i} - 1}{\lambda^{j_i}} \right) $$

which can be equivalently rewritten as

$$ h_{i,t} = \lambda^{t(t+1)/2} \sum_{1 \le j_1 < j_2 < \cdots < j_i \le t} \prod_{\substack{l=1 \\ l \ne j_1, \dots, j_i}}^{t} \left( \frac{1 - \lambda^l}{\lambda^l} \right), $$

for $i = 1, \dots, t$. Substituting $q$ by $1/\lambda$ yields the desired result.

Let us study the asymptotic behavior of these coefficients when $t$ tends to infinity. We have already remarked that $\lim_{t \to \infty} h_{t,t} = 0$ and $\lim_{t \to \infty} h_{0,t} = \varphi(\lambda)$. From the above formula, the expression of $h_{1,t}$ is

$$ h_{1,t} = \lambda^{t(t+1)/2} \sum_{i=1}^{t} \prod_{\substack{l=1 \\ l \ne i}}^{t} \left( \frac{1 - \lambda^l}{\lambda^l} \right) $$
which can be rewritten in the form

$$h_{1,t} = \prod_{i=1}^{t} (1 - \lambda^i) \sum_{i=1}^{t} \frac{\lambda^i}{1 - \lambda^i}.$$

We have $h_{1,t} \ge 0$. Let us prove that it is a decreasing sequence.

$$ \begin{aligned} h_{1,t} - h_{1,t-1} &= \lambda^{1+\cdots+t} \left( \sum_{i=1}^{t} \prod_{j \neq i} \frac{1-\lambda^j}{\lambda^j} - 2^t \sum_{i=1}^{t-1} \prod_{j \neq i} \frac{1-\lambda^j}{\lambda^j} \right) \\ &= \lambda^{1+\cdots+t} \left( \sum_{i=1}^{t} \prod_{j \neq i} \frac{1-\lambda^j}{\lambda^j} - \sum_{i=2}^{t-1} \prod_{j \neq i} \frac{1-\lambda^j}{\lambda^j} \frac{1}{\lambda^t} \right) \\ &\quad - \prod_{\substack{j=1,\dots,t-1 \\ j \neq 1}} \frac{1-\lambda^j}{\lambda^j} (\frac{1}{\lambda^t} - 1) - \prod_{\substack{j=1,\dots,t-1 \\ j \neq 1}} \frac{1-\lambda^j}{\lambda^j} \le 0. \end{aligned} $$

Therefore, the sequence converges, and we obtain

$$\lim_{t \to \infty} h_{1,t} = \prod_{i=1}^{\infty} (1 - \lambda^i) \sum_{i=1}^{\infty} \frac{\lambda^i}{1 - \lambda^i} = \varphi(\lambda) \left( 1 + \frac{\log(1 - \lambda) - \log \lambda}{\log \lambda} + \frac{1}{\log \lambda} \Psi_{\lambda}(1) \right).$$

where $\Psi_r$ is the r-Digamma function recalled in (10). Let us study the convergence of $h_{i,t}$ for other values of $i$. We remark that the term of highest degree in $\lambda$ in the denominator of $h_{i,t}$ is $\lambda^{(i+1)+(i+2)+\cdots+t}$. Therefore, as $\lambda < 1$, the convergence is governed by the term

$$\lambda^{1+2+\cdots+i}$$

in $h_{i,t}$, the others being smaller. If $i \in \mathbb{N}$, then the limit will be a positive quantity, while if $i$ tends to infinity with $t$, the limit of $h_{i,t}$ is 0. $\square$

## Proof of Proposition 8

We first show that

$$\sum_{j=0}^{t} h_{j,t} = 1 \quad (t \ge 1). \qquad (26)$$

Indeed, observe that $M(t)$ is row-stochastic for every $t = 1, 2, \dots$, so that $H(t)$ too is row-stochastic as a product of row-stochastic matrices. For the same reason, $G^t$ is row-stochastic for every $t = 0, 1, \dots$. Denoting the elements of $H(t)$ by $H_{ij}(t)$ and those of $G^t$ by $G_{ij}^{[t]}$, we obtain from (8):

$$ \begin{aligned} 1 &= \sum_{j=1}^{N} H_{1j}(t) = h_{t,t} \sum_{j=1}^{N} G_{1j}^{[t]} + h_{t-1,t} \sum_{j=1}^{N} G_{1j}^{[t-1]} + \cdots + h_{0,t} \cdot 1 \\ &= h_{t,t} + h_{t-1,t} + \cdots + h_{0,t}. \end{aligned} $$
We have also that $H(\infty)$ is row-stochastic as (infinite) product of row-stochastic matrices.
Using the approximation $G^3 \approx G^4 \approx \dots \approx G^\infty$, we obtain

$$
\begin{align*}
x(t+1) &= (h_{t,t}G^{t+1} + \dots + h_{1,t}G^2 + h_{0,t}G)x(0) \\
&\approx ((h_{t,t} + \dots + h_{2,t})\mathbf{1}w^T + h_{1,t}G^2 + h_{0,t}G)G(0) \\
&\approx ((1 - h_{0,t} - h_{1,t})\mathbf{1}w^T + h_{1,t}G^2 + h_{0,t}G)x(0).
\end{align*}
$$

Taking the limit as $t \to +\infty$, it follows that

$$
x(\infty) \approx ((1 - h_{0,\infty} - h_{1,\infty})\mathbf{1}w^T + h_{1,\infty}G^2 + h_{0,\infty}G)x(0)
$$

which yields, using the previous results:

$$
x(\infty) \approx \left[ \frac{\varphi(\lambda)}{\log(\lambda)} (\log(1-\lambda) + \Psi_{\lambda}(1)) G^2 + \varphi(\lambda) G \right. \\
\left. \qquad + \left( 1 - \frac{\varphi(\lambda)}{\log(\lambda)} (\log(1-\lambda) + \log(\lambda) + \Psi_{\lambda}(1)) \right) \mathbf{1} w^T \right] x(0).
$$

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

**Proof of Lemma 2**

As $G$ is row-stochastic and $x_1 \le x_2 \le \cdots \le x_N$, we have

$$
\sum_{k=1}^{N} G_{1,k} x_k \ge G_{1,1} x_1 + (1 - G_{1,1}) x_2 \ge x_1.
$$

Similarly, $\sum_{k=1}^N G_{N,k}x_k \le x_N$, which proves the result since by Lemma 1(ii), the order $x_1 \le x_2 \le \cdots \le x_N$ is preserved. Supposing $G$ to be connected implies $G_{1,1} < 1$, and if $x_2 > x_1$ or $x_N > x_{N-1}$, then one obtains the strict inequality. $\square$

**Proof of Proposition 9**

Using Equation (8), it is straightforward to see that

$$
\delta(x_{\lambda}(t)) = \sum_{i=0}^{t} h_{i,t}(\lambda) \delta(G^{i+1}x(0)) \quad (27)
$$

where $h_{i,t}(\lambda)$ denotes the $i$th coefficient of the polynomial $H_\lambda(t)$.

It is straightforward to see that each of the $h_{i,t}(\lambda)$ and thus $\delta(x_\lambda(t))$ is differentiable
with respect to $\lambda$. We shall hence prove this proposition by showing that

$$
\delta'(x_{\lambda}(t)) = \sum_{i=0}^{t} h'_{i,t}(\lambda) \delta(G^{i+1}x(0)) < 0
$$

Using Lemma 3 and the fact that for all $\lambda \in [0,1]$, $h'_{0,t}(\lambda) \le 0$ and $h'_{t,t}(\lambda) \ge 0$ (see Proposition 7), one has that there exists $i_\lambda \in \{0, \dots, t-1\}$ such that for all $i \le i_\lambda$, $h'_{i,t}(\lambda) \le 0$ and for all $i > i_\lambda$, $h'_{i,t}(\lambda) \ge 0$.
Thus, one can write:

$$ \delta'(x_{\lambda}(t)) = \sum_{i=0}^{i_{\lambda}} h'_{i,t}(\lambda)\delta(G^{i+1}x(0)) + \sum_{i=i_{\lambda}+1}^{t} h'_{i,t}(\lambda)\delta(G^{i+1}x(0)) $$

and then

$$ \delta'(x_{\lambda}(t)) \le \min_{j=0, \dots, i_{\lambda}} \delta(G^{j+1}x(0)) \sum_{i=0}^{i_{\lambda}} h'_{i,t}(\lambda) + \max_{j=i_{\lambda}+1, \dots, t} \delta(G^{j+1}x(0)) \sum_{i=i_{\lambda}+1}^{t} h'_{i,t}(\lambda) $$

Now, it is straightforward that $H$ is row-stochastic as a product of row-stochastic matrices and thus $\sum_{i=0}^{t} h'_{i,t}(\lambda) = 0$. Hence, one has:

$$ \delta'(x_{\lambda}(t)) \le \min_{j=0, \dots, i_{\lambda}} \delta(G^{j+1}x(0)) \left( - \sum_{i=i_{\lambda}+1}^{t} h'_{i,t}(\lambda) \right) + \max_{j=i_{\lambda}+1, \dots, t} \delta(G^{j+1}x(0)) \sum_{i=i_{\lambda}+1}^{t} h'_{i,t}(\lambda) $$

and thus:

$$ \delta'(x_{\lambda}(t)) \le \sum_{i=i_{\lambda}+1}^{t} h'_{i,t}(\lambda) \left( \max_{j=i_{\lambda}+1, \dots, t} \delta(G^{j+1}x(0)) - \min_{j=0, \dots, i_{\lambda}} \delta(G^{j+1}x(0)) \right) $$

Finally, it is a straightforward consequence of Lemma 2 that

$$ \max_{j=i_{\lambda}+1, \dots, t} \delta(G^{j+1}x(0)) = \delta(G^{i_{\lambda}+2}x(0)) < \delta(G^{i_{\lambda}+1}x(0)) = \min_{j=0, \dots, i_{\lambda}} \delta(G^{j+1}x(0)) $$

This clearly yields

$$ \delta'(x_{\lambda}(t)) < 0, $$

which ends the proof. □

### Proof of Lemma 3

Let us consider $t \in \mathbb{N}$, $i \in \{0, \dots, t-1\}$ and let $T = \{1, \dots, t\}$. We shall use the following notations:

* For any $J \subset T$ we let $\sigma(J) := \sum_{j \in J} j$ and $g_J(\lambda) := \lambda^{\sigma(J)} \prod_{\ell \in T \setminus J} (1 - \lambda^{\ell})$

* For any $k \in T$, we let $P_i := \{J \subset T \mid \text{card}(J) = i\}$ and $P_i^k := \{J \subset T \mid \text{card}(J) = i \text{ and } k \notin J\}$.

* For any $k \in T$ and $i = 1, \dots, t$, we let $f_{k,i}(\lambda) := \sum_{J \in P_i^k} g_J(\lambda)$.

One can then remark the following relations:

(i) For all $k, m \in T$, $(1 - \lambda^m)f_{k,i}(\lambda) = (1 - \lambda^k)f_{m,i}(\lambda)$. In particular:

$$ f_{k,i}(\lambda) = \frac{1 - \lambda^k}{1 - \lambda} f_{1,i}(\lambda) $$
(ii) $h_{i,t}(\lambda) = \sum_{J \in P_i} g_J(\lambda) = \frac{1}{t-i} \sum_{k=1}^{t} f_{k,i}(\lambda)$. The latter equality is obtained by observing that by summing the $f_{k,i}(\lambda)$s, one obtains $(t-i)$ times each of the $g_J(\lambda)$.

$$ (iii) \quad h_{i+1,t}(\lambda) = \frac{1}{i+1} \sum_{k=1}^{t} \frac{\lambda^k}{1-\lambda^k} f_{k,i}(\lambda). $$

Combining the preceding three relations, one obtains:

$$ h_{i,t}(\lambda) = \frac{1}{t-i} \frac{f_{1,i}(\lambda)}{1-\lambda} \sum_{k=1}^{t} (1-\lambda^k) $$

$$ h_{i+1,t}(\lambda) = \frac{1}{i+1} \frac{f_{1,i}(\lambda)}{1-\lambda} \sum_{k=1}^{t} \lambda^k $$

Letting $F(\lambda) := \frac{f_{1,i}(\lambda)}{1-\lambda}$, their derivatives are respectively given by

$$ h'_{i,t}(\lambda) = \frac{1}{t-i} \left( F'(\lambda) \sum_{k=1}^{t} (1-\lambda^k) - F(\lambda) \sum_{k=1}^{t} k\lambda^{k-1} \right) $$

$$ h'_{i+1,t}(\lambda) = \frac{1}{i+1} \left( F'(\lambda) \sum_{k=1}^{t} \lambda^k + F(\lambda) \sum_{k=1}^{t} k\lambda^{k-1} \right) $$

Let us finally remark that one clearly has $F(\lambda) \sum_{k=1}^{t} k\lambda^{k-1} \ge 0$. The following sequence of implications follows:

$$ h'_{i+1,t}(\lambda) \le 0 \Rightarrow F'(\lambda) \le 0 \Rightarrow h'_{i,t}(\lambda) \le 0. $$

This ends the proof of the lemma. □

### Proof of Proposition 10

Let us set $g(\lambda) = (1 - \bar{\phi}; \lambda)$. The function $g$ is clearly twice differentiable on $[0, 1[$ and

$$ g'(\lambda) = \sum_{k=0}^{+\infty} (\bar{\phi}-1)k\lambda^{k-1} \prod_{j \neq k} (1+(\bar{\phi}-1)\lambda^j) = (\bar{\phi}-1) \sum_{k=0}^{+\infty} k \frac{\lambda^{k-1}}{1+(\bar{\phi}-1)\lambda^k} g(\lambda) = (\bar{\phi}-1)g(\lambda)h(\lambda) $$

One has $g'(0) = 0$ so that $u'(0) = S\alpha - g'(0) > 0$, and thus 0 cannot be a solution to the social planner problem.

Furthermore, one has $\lim_{\lambda \to 1} (1 - \bar{\phi}; \lambda) = +\infty$ so that $u(1) = \alpha S - S$. As $\alpha < 1$, this yields $u(1) < 0 = u(0)$, and thus 1 cannot be a solution to the social planner problem. More broadly, this implies that a solution must satisfy $(1 - \bar{\phi}; \lambda) < S$.

Hence, any solution $\lambda^*$ must be interior and first order conditions yield (17). □

### Proof of Proposition 12
The proof is similar to the proof of Proposition 1. We use the same notation $(x_m)_{m=0,...,M+1}$, $(y_\ell)_{\ell=1,...,L}$, and $(z_r)_{r=1,...,R}$ for the opinions of the nodes, with same convention for the ordering.

Assuming $\lambda = 1$, the difference between the updated opinions of $i$ and $j$ are:

$$ \Delta(x, y, z) = x_j(t+1) - x_i(t+1) = \frac{\sum_{r=1}^{R} z_r + \sum_{m=1}^{M+1} x_m}{R+M+1} - \frac{\sum_{\ell=1}^{L} y_\ell + \sum_{m=0}^{M} x_m}{L+M+1}, $$

which yields

$$ \Delta(x, y, z) = \frac{(L + M + 1)(x_{M+1} + \sum_{r=1}^{R} z_r) - (R + M + 1)(x_0 + \sum_{\ell=1}^{L} y_\ell) + (L - R) \sum_{m=1}^{M} x_m}{(L + M + 1)(R + M + 1)} \quad (28) $$

Our aim is to find the minimal value of $\Delta(x, y, z)$ under the constraint of $(\sigma, \tau)$-compatibility.

1. We prove that $\lambda = 1$ is the most defavorable case, i.e., if contraction occurs with $\lambda = 1$, it occurs with a less extent for $\lambda < 1$. We have

$$ \Delta_{\lambda}(x, y, z) = \lambda^{t} \Delta(x, y, z) + (1 - \lambda^{t})(x_{j}(t) - x_{i}(t)) > \Delta(x, y, z) $$

as $x_j(t) - x_i(t) > \Delta(x, y, z)$ if we assume contraction. Otherwise, $\Delta_{\lambda}(x, y, z) > x_j(t) - x_i(t)$, and again no contraction occurs.

As a consequence, we can fix $\lambda = 1$. Also, we fix $x_0 = 0$ and place ourselves in the limit case $x_{M+1} = \tau$, assuming that no link exists between $i$ and $j$. Any contraction implies then creation of $\{i, j\}$.

2. Proceeding as for Proposition 1, we come up with the following linear program:

$$
\begin{array}{ll}
\min_{x,y,z} & \Delta(x,y,z) \text{ under} \\
& x_m \le x_{m+1}, \qquad m = 0, \dots, M \\
& z_r \le z_{r+1}, \qquad r = 1, \dots, R-1 \\
& z_1 \ge \tau \\
& z_R \le \tau + \sigma \\
& y_\ell \ge y_{\ell+1}, \qquad \ell = 1, \dots, L-1 \\
& y_1 \le 0 \\
& y_L \ge -\sigma \\
& x_m - y_{\ell m} \le \sigma, \qquad m = 1, \dots, M \\
& x_m - y_{\ell m+1} \ge \tau, \qquad m = 1, \dots, M \\
& z_{r_m} - x_m \le \sigma, \qquad m = 1, \dots, M \\
& z_{r_m+1} - x_m \ge \tau, \qquad m = 1, \dots, M.
\end{array}
$$

and $y_0 = 0, z_0 = \tau$.

3. Given $x = \bar{x}$ fixed, finding the optimal solution $(\bar{x}, \bar{y}, \bar{z})$ consists in minimizing $\sum_{r=1}^{R} z_r$ and maximizing $\sum_{\ell=1}^{L} y_\ell$, which amounts to put the $\bar{y}_\ell$'s as close as possible to 0 and the $\bar{z}_r$'s as close as possible to $\tau$.
Proceeding as for link deletion, we show that the only basic solutions are those with $\bar{x}_m = 0$ or $\tau$.

Take $\bar{x}$ with $\bar{x}_m = 0$ for $m \le m_0$ and $\bar{x}_m = \tau$ for $m > m_0$, for a fixed $0 \le m_0 \le M$. Observe that this imposes that $\bar{y}_1 = \cdots = \bar{y}_{\ell_{m_0}} = 0$ and $\bar{y}_{\ell_{m_0+1}} = \cdots = \bar{y}_L = -\tau$, and $\bar{z}_1 = \cdots = \bar{z}_{r_{m_0+1}} = \tau$, $\bar{z}_{r_{m_0+1}+1} = \cdots = \bar{z}_R = 2\tau$, taking the convention $r_0 = 0$ and $\ell_{M+1} = 0$. This solution $(\bar{x}, \bar{y}, \bar{z})$ is feasible and the set of tight constraints contains in particular the following system, assuming $0 < m_0 < M$ (the other cases are similar):

$$x_m = x_{m+1}, \qquad m = 0, \dots, m_0 - 1, m_0 + 1, \dots, M$$

$$z_r = z_{r+1}, \qquad r = 1, \dots, r_{m_0+1} - 1, r_{m_0+1} + 1, \dots, R - 1$$

$$z_1 = \tau$$

$$y_{\ell} = y_{\ell+1} \qquad \ell = 1, \dots, \ell_{m_0} - 1, \ell_{m_0} + 1, \dots, L - 1$$

$$y_1 = 0$$

$$x_{m_0} - y_{\ell_{m_0}+1} = \tau$$

$$z_{r_{m_0+1}+1} - x_{m_0+1} = \tau$$

which gives as unique solution $(\bar{x}, \bar{y}, \bar{z})$. Hence, it is a basic solution.

Let us modify the point as follows: $\bar{x}_m = 0$ for $m < m_0$, $\bar{x}_{m_0} \in ]0, \tau[$ fixed, and $\bar{x}_m = \tau$ for $m > m_0$. Then $\bar{y}$ and $\bar{z}$ are modified as follows:

$$\bar{y}_{\ell_{m_0+1}} = \cdots = \bar{y}_{\ell_{m_0-1}} = \bar{x}_{m_0} - \tau, \quad \bar{z}_{r_{m_0+1}} = \cdots = \bar{z}_{r_{m_0-1}} = \bar{x}_{m_0} + \tau,$$

the rest being unchanged. This induces the following set of tight constraints:

$$x_m = x_{m+1}, \qquad m = 0, \dots, m_0 - 2, m_0 + 1, \dots, M$$

$$z_r = z_{r+1}, \quad r = 1, \dots, r_{m_0-1} - 1, r_{m_0-1} + 1, \dots, r_{m_0} - 1, r_{m_0} + 1, \dots, R - 1$$

$$z_1 = \tau$$

$$y_{\ell} = y_{\ell+1} \qquad \ell = 1, \dots, \ell_{m_0+1} - 1, \ell_{m_0+1} + 1, \dots, \ell_{m_0} - 1, \ell_{m_0} + 1, \dots, L - 1$$

$$y_1 = 0$$

$$x_m - y_{\ell_{m_0}+1} = \tau, \qquad m = 1, \dots, M$$

$$z_{r_m} - x_m = \tau, \qquad m = 1, \dots, M,$$

and possibly some of the inequalities $x_m - y_{\ell_m} \le \sigma$ and $z_{r_m} - x_m \le \sigma$. Observe that $x_{m_0}$, $y_{\ell_{m_0}}$ and $z_{r_{m_0}}$ remain undetermined. Hence $(\bar{x}, \bar{y}, \bar{z})$ is not a basic solution.

4. Therefore, candidate optimal solutions are the $M+1$ basic solutions indexed by $m_0$. Plugging these solutions into (23), we find

$$\begin{align}
\Delta(\bar{x}, \bar{y}, \bar{z}) &= \frac{(L+M+1)(r_{m_0+1}\tau + (R-r_{m_0+1})2\tau + \tau) + (R+M+1)(L-\ell_{m_0})\tau + (L-R)(M-m_0)\tau}{(L+M+1)(R+M+1)} \nonumber \\
&= \tau \left( \frac{(L+M+1)(2R-r_{m_0+1}+1) + (R+M+1)(L-\ell_{m_0}) + (L-R)(M-m_0)}{(L+M+1)(R+M+1)} \right). \tag{29}
\end{align}$$

Letting

$$\pi_{i,j}(\mathcal{G}) = \min_{m_0 \in \{0, \dots, M\}} \frac{(L+M+1)(2R-r_{m_0+1}+1) + (R+M+1)(L-\ell_{m_0}) + (L-R)(M-m_0)}{(L+M+1)(R+M+1)}$$
yields the desired result, and {$i, j$} becomes a link iff $\pi_{i,j}(\mathcal{G}) < 1$.

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

### Proof of Proposition 13

We proceed similarly as in the proof of Proposition 2.

Letting $x_{M+1} \ge \tau$ be arbitrary while keeping the gap minimal yields an optimal solution where the $y_\ell$ are either at 0 or $-\tau$ as before, and the $z_r$ are either at $x_{M+1}$ or $x_{M+1} + \tau$. This yields, keeping $\lambda = 1$:

$$ \Delta(\bar{x}, \bar{y}, \bar{z}) = \frac{(L + M + 1)((R + 1)x_{M+1} + (R - r_{m_0+1})\tau) + (R + M + 1)(L - \ell_{m_0})\tau + (L - R)(M - m_0)\tau}{(L + M + 1)(R + M + 1)} $$

Supposing $x_{M+1} \ge \tau$ implies that $\Delta(\bar{x}, \bar{y}, \bar{z}) \ge \pi_{i,j}\tau$. Thus, we obtain:

$$ x_j(t+1) - x_i(t+1) = G(t)(x_j(t) - x_i(t)) \ge \pi_{i,j}\tau $$

so that we can write, with arbitrary $\lambda$:

$$ \begin{aligned} x_j(t+1) - x_i(t+1) &= \lambda^t G(t)(x_j(t) - x_i(t)) + (1 - \lambda^t)(x_j(t) - x_i(t)) \\ &\ge \lambda^t \pi_{i,j}\tau + (1 - \lambda^t)(x_j(t) - x_i(t)) \\ &\ge [1 + (\pi_{i,j} - 1)\lambda^t]\tau. \end{aligned} $$

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

## 7 Acknowledgments

The authors acknowledge the financial support from the European Union's Horizon 2020 research and innovation programme under the grant agreement No 721846, “Expectations and Social Influence Dynamics in Economics (ExSIDE)”.

### References

D. Acemoglu, A. Ozdaglar, and A. ParandehGheibi. Spread of (mis)information in social networks. Games and Economic Behavior, 70:194–227, 2010.

D. Acemoglu, G. Como, F. Fagnani, and A. Ozdaglar. Opinion fluctuations and disagreement in social networks. Mathematics of Operations Research, 38(1):1–27, 2013.

B. D. O. Anderson and M. Ye. Recent advances in the modelling and analysis of opinion dynamics on influence networks. International Journal of Automation and Computing, 16:129–149, 2019.

R. Axelrod. The dissemination of culture, a model with local convergence and global polarization. The Journal of Conflict Resolution, 41(2):203–226, 1997.

S. Banisch and E. Olbrich. Opinion polarization by learning from social feedback. The Journal of Mathematical Sociology, 43(2):76–103, 2019.
V. D. Blondel, J. M. Hendrickx, and J. N. Tsitsiklis. On the 2R conjecture for multi-agent systems. In *2007 European Control Conference (ECC)*, pages 874–881, 2007.

U. Bolletta and P. Pin. Polarization when people choose their peers. Available at SSRN: https://ssrn.com/abstract=3245800 or http://dx.doi.org/10.2139/ssrn.3245800, 2019.

A. Chadwick. *The Hybrid Media System: Politics and Power*. Oxford University Press, 2017.

P. Dandekar, A. Goel, and D. T. Lee. Biased assimilation, homophily, and the dynamics of polarization. *Proceedings of the National Academy of Sciences*, 110(15):5791–5796, 2013.

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

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

P. DeMarzo, D. Vayanos, and J. Zwiebel. Persuasion bias, social influence, and unidimensional opinions. *Quarterly Journal of Economics*, 118:909–968, 2003.

P. DiMaggio, J. Evans, and B. Bryson. Have American's social attitudes become more polarized? *American Journal of Sociology*, 102(3):690–755, 1996.

J. C. Dittmer. Consensus formation under bounded confidence. *Nonlinear Analysis*, 47: 4615–4621, 2001.

Y. Eisenstat. How to hold social media accountable for undermining democracy. *Harvard Business Review*, January 2021.

F. Fagan. Systemic social media regulation. *Duke Law & Technology Review*, 16(1): 393–439, 2018.

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

N. E. Friedkin and E. C. Johnsen. Social influence and opinions. *Journal of Mathematical Sociology*, 15:193–206, 1990.

D. Ghosh. What will tech regulation look like in the biden era? *Harvard Business Review*, December 2020.

D. Ghosh. Are we entering a new era of social media regulation? *Harvard Business Review*, January 2021.

B. Golub and M. O. Jackson. Naïve learning in social networks and the wisdom of crowds. *American Economic Journal: Microeconomics*, 2(1):112–149, 2010.

B. Golub and E. Sadler. Learning in social networks. In Y. Bramoullé, A. Galeotti, and B. W. Rogers, editors, *The Oxford Handbook of the Economics of Networks*, chapter 19, pages 504–542. Oxford University Press, 2016.
M. Hameleers. Augmenting polarization via social media? a comparative analysis of trump's and wilders' online populist communication and the electorate's interpretations surrounding the elections. *Acta Politica*, 55(3):331-350, 2020.

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

A. Homolar and R. Scholz. The power of Trump-speak: Populist crisis narratives and ontological security. *Cambridge Review of International Affairs*, 32(3):344-364, 2019.

B. Kozma and A. Barrat. Consensus formation on adaptive networks. *Physical Review E*, 77(1):016102, 2008.

U. Krause. A discrete nonlinear and nonautonomous model of consensus formation. In S. Elaydi, G. Ladas, J. Popenda, and J. Rakowski, editors, *Communications in Difference Equations*. Amsterdam: Gordon and Breach, 2000.

B. Latané, A. Nowak, and J. H. Liu. Measuring emergent social phenomena: dynamism, polarization, and clustering as order parameters of social systems. *Behavioral Science*, 39(1):1-24, 1994.

L. Lavie. Consensus vs. dissensus over the 'civil state' model: a key to understanding the diverse outcomes of the Arab Spring in Egypt and Tunisia. *British Journal of Middle Eastern Studies*, 48(3):455-472, 2021.

J. Lorenz, H. Rauhut, F. Schweitzer, and D. Helbing. How social influence can undermine the wisdom of crowd effect. *Proceedings of the National Academy of Sciences*, 108(22): 9020-9025, 2011.

S. Lowrance. Was the revolution tweeted? Social media and the Jasmine Revolution in Tunisia. *Digest of Middle East Studies*, 25(1):155-176, 2016.

M. Mäs, A. Flache, and J. A. Kitts. Cultural integration and differentiation in groups and organizations. In V. Dignum and F. Dignum, editors, *Perspectives on Culture and Agent-based Simulations: Integrating Cultures*, pages 71-90. Springer: Berlin/Heidelberg, Germany, 2014.

F. Plasser and G. Plasser. *Global political campaigning: A worldwide analysis of campaign professionals and their practices*. Greenwood Publishing Group, 2002.

A. V. Proskurnikov and R. Tempo. A tutorial on modeling and analysis of dynamic social networks (ii). arXiv:1801.06719v1, 2018.

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

R. Sennett. *The Spaces of Democracy*. University of Michigan, College of Architecture+ Urban Planning, 1998.
S. Shabayek. Hidden opinions. Working Paper, Paris School of Economics and University of Paris 1 Panthéon-Sorbonne, 2020.

G. Shi, A. Proutiere, M. Johansson, J. S. Baras, and K. H. Johansson. The evolution of beliefs over signed social networks. *Operations Research*, 64(3):585–604, 2016.

A. Sîrbu, V. Loreto, V. DP Servedio, and F. Tria. Opinion dynamics: models, extensions and external effects. In A. E. Roth, editor, *Participatory Sensing, Opinions and Collective Awareness*, pages 363–401. Springer, 2017.

S. Vaidhyanathan. *Antisocial media: How Facebook disconnects us and undermines democracy*. Oxford University Press, 2018.

E. Yildiz, D. Acemoglu, A. Ozdaglar, A. Saberi, and A. Scaglione. Binary opinion dynamics with stubborn agents. *ACM Transactions on Economics and Computation*, 1(4), 2013.