# Transient Behavior of Gossip Opinion Dynamics
with Community Structure

Yu Xing  Karl H. Johansson  Division of Decision and Control Systems, School
of Electrical Engineering and Computer Science,
KTH Royal Institute of Technology, and Digital Futures, Stockholm, Sweden.

###### Abstract

We study transient behavior of gossip opinion dynamics, in which agents
randomly interact pairwise over a weighted graph with two communities. Edges
within a community have identical weights different from edge weights between
communities. We first derive an upper bound for the second moment of agent
opinions. Using this bound, we obtain upper bounds for probability that a
large portion of agents have opinions close to average ones. The results imply
a phase transition of transient behavior of the process: When edge weights
within communities are larger than those between communities and those between
regular and stubborn agents, most agents in the same community hold opinions
close to the average opinion of that community with large probability, at an
early stage of the process. However, if the difference between intra- and
inter-community weights is small, most of the agents instead hold opinions
close to everyone’s average opinion at the early stage. In contrast, when the
influence of stubborn agents is large, agent opinions settle quickly to steady
state. We then conduct numerical experiments to validate the theoretical
results. Different from traditional asymptotic analysis in most opinion
dynamics literature, the paper characterizes the influences of stubborn agents
and community structure on the initial phase of the opinion evolution.

###### keywords:

opinion dynamics, transient behavior, community structure, phase transition,
gossip model

††thanks: _Emails:_<EMAIL_ADDRESS>(Yu Xing<EMAIL_ADDRESS>(Karl H.
Johansson).

,

##  1 Introduction

Opinion dynamics is the study of how personal opinions change through
interactions in social networks. Analysis of convergence and stability of
opinion dynamics has gained considerable attention in recent decades [1], but
less research has focused on transient behavior of the opinion formation
process. Social networks often have topologies where subgroups of nodes are
densely connected internally but loosely connected with others (that is,
community structure [2]). Such structure is observed to be able to influence
opinion dynamics [3, 4]. It is often difficult to determine whether a
realistic social network reaches steady state or not, and whether its
communities evolve homogeneously at the early stage. So it is necessary to
investigate how the opinion formation process, especially during its initial
phase, corresponds to its community structure. Such results can also provide
insight into design of community detection algorithms based on state
observations [5, 6] and design of model reduction tools for large-scale
networks [7].

###  1.1 Related Work

Individual opinion can be modeled by a continuous variable taking values in an
interval of real numbers, or a discrete variable in a finite set [1, 8]. There
are at least three types of continuous-opinion models explaining how
interpersonal interactions shape opinion profiles of social networks, namely,
models of assimilative, homophily, and negative social influences [1, 9].
Evidences for all three types have been found in recent empirical studies [10,
11, 12]. A crucial example of the first class of models is the DeGroot model
[13], in which agents update according to the average of their neighbors’
opinions. The Friedkin–Johnsen (FJ) model [14] generalizes the DeGroot model
and allows long-term disagreement, rather than consensus, by assuming that
agents are consistently affected by their initial opinions. The
Hegselmann–Krause (HK) model [15] and the Deffuant–Weisbuch (DW) model [16]
are representatives of the second class of models. In these models, agents
stay away from those who hold different beliefs, and hence the agents tend to
form clusters in the end. Negative influences presence in the third class of
models can increase opinion difference between individuals, and make the group
end in polarization [1, 17].

Most studies of opinion dynamics have focused on asymptotic behavior,
attempting to answer why opinion disagreement occurs in the long run even
though social interactions tend to reduce opinion difference [9, 18]. In
contrast, transient behavior has attracted less attention. As the availability
of large-scale datasets from the internet increases, there is a growing need
to understand how the process behaves over a finite time interval [19, 20,
21]. Important behavioral dynamics, such as election and online discussion,
often have finite duration, and their prediction based on transient evolution
is of great interest [10, 22]. Extensive amount of information produced by
social media nowadays may change public opinions only temporarily [23], making
it hard for the dynamics process to reach steady state. Asymptotic analysis
thus may not be sufficient for understanding such scenarios. Finally, real
large-scale networked dynamic processes may converge slowly [19, 24], but stay
close to a certain state for a long time [25, 26]. In practice, to distinguish
between two types of states can be challenging and requires knowledge of
transient system behavior. The authors in [19] propose a framework to analyze
the transient stage of discrete-state Markov chains that model opinion
dynamics. The paper [25] studies quasi-stationary distributions of a contact
process, and [27] analyzes the transient opinion profiles of a voter model.
The authors in [26] provide criteria for detecting transient clusters in a
generalized HK model that normally reaches a consensus asymptotically. A
recent paper [28] studies how opinion difference evolves over finite time
intervals for a stochastic bounded confidence model with two agents and the
model over a bistar graph.

The study of community structure can be traced back to [29], in which a
community is defined as a complete subgraph in a network. One of the modern
definitions for communities is modularity, which characterizes the
nonrandomness of a group partition [30]. The stochastic block model (SBM)
[31], generating random graphs with communities, is another popular framework
in the literature. Researchers have studied how community structure of a
network influences opinion evolution, based on several models such as the DW
model [32, 33], the Taylor model [34], and the Sznajd model [35]. The paper
[36] studies the DeGroot model with stubborn agents over a weighted graph, and
shows that the steady state of agents in the same community concentrates
around the state of some stubborn agent.

This paper considers transient behavior of a gossip model with stubborn
agents. This model, in which agents randomly interact in pairs, is a
stochastic counterpart of the DeGroot model. The model captures the random
nature of interpersonal influence and exhibits various behavior. Consensus of
the gossip model has been studied in [37, 38]. The authors in [39] show that
the existence of stubborn agents may explain fluctuation of social opinions,
and also that, if the network is highly fluid, then the expected steady state
of regular (non-stubborn) agents is close. In contrast, it is shown in [36]
that polarization can emerge, if the model evolves over a weighted graph with
two stubborn agents. Studying transient behavior of the gossip model can
provide insight into analysis of more complex models, because the linear
averaging rule is a key building block of most opinion models.

###  1.2 Contribution

In this paper, we study transient behavior of the gossip model over a weighted
graph with two communities. It is assumed that edges within communities have
identical weights different from edge weights between communities. We first
obtain an upper bound for the second moment of agent states (Lemma 4). Using
this bound, we are able to provide probability bounds for agent states
concentrating around average opinions (Corollary 1), expected average opinions
(Theorem 1), and average initial opinions (Theorem 2). The results reveal a
phase transition phenomenon [40, 41, 42]: When edge weights within communities
are larger than those between communities and those between regular and
stubborn agents, most agents in the same community have states with small
deviation from the average opinion of that community with large probability,
at the early stage of the process. But if the difference between intra- and
inter-community weights is not so large, most agents in the network have
states concentrating around everyone’s average opinion with small error and
large probability at the early stage (Corollary 2). In contrast, if weights
between regular and stubborn agents are larger than those between regular
agents, agent states have a distribution close to their stationary one, right
after the beginning of the process (Theorem 3 and Corollary 3).

These results indicate that the gossip model has entirely different transient
behavior, under different link strength parameters. It is known that the
expected steady state depends on the positions of stubborn agents [39], and
the model reaches a consensus if there are no stubborn agents [37, 38]. The
obtained results indicate that agents may form transient clusters if the
influence of stubborn agents is relatively small. These transient clusters may
not be the same as the stationary ones, because they only depend on initial
regular states and edge weights between the regular. In addition, the results
demonstrate how transient behavior of the model corresponds to community
structure of the network, by showing that the difference between intra- and
inter-community weights has to be large enough to ensure the existence of such
a correspondence and by showing how the relative magnitude of the weights
influences the duration of the transient clusters.

The obtained results can be directly applied to community detection based on
state observations [5, 6]. Suppose that a network is unknown but several
snapshots of an opinion dynamic are available. Then our results ensure that
partitioning agent states can recover the community labels of agents, if the
states are collected in certain transient time interval and intra-community
influence is large. The results can also provide insight into predicting and
distinguishing transient behavior of an opinion formation process in practice
[19, 22]. For example, when the size of a network and the difference between
intra- and inter-community interaction strength are large, the duration of
such transient interval is expected to be large as well. Given an estimate of
the runtime of a process, we may determine whether the current clusters are
steady or not. Finally, exploiting properties of transient clusters can help
improve model reduction at the initial phase of dynamics over large-scale
networks with community structure [7]. If agents in the same community have
states close to each other at the early stage of the process, then we may
track the opinion formation process with much less parameters than the
original system, by replacing topological data with community labels.

In the early work [43], we study how the expectation of agent states
concentrates around average initial states, which follows from Lemma 3 of the
current paper. Here we directly investigate how agent states evolve by
analyzing the second moment and thus provide more detailed characterization of
transient behavior.

###  1.3 Outline

In Section 2 we introduce the considered model and problem. Section 3 provides
theoretical results. Numerical experiments are presented in Section 4. Section
5 concludes the paper. Some proofs are given in the appendices.

Notation. Denote the $n$-dimensional Euclidean space by $\mathbb{R}^{n}$, the
set of $n\times m$ real matrices by $\mathbb{R}^{n\times m}$, the set of
nonnegative integers by $\mathbb{N}$, and
$\mathbb{N}^{+}=\mathbb{N}\setminus\\{0\\}$. Denote the natural logarithm by
$\log x$, $x\in\mathbb{R}$. Let $\mathbf{1}_{n}$ be the all-one vector with
dimension $n$, $e_{i}^{(n)}$ be the $n$-dimensional unit vector with $i$-th
entry being one, $I_{n}$ be the $n\times n$ identity matrix, and
$\mathbf{0}_{m,n}$ be the $m\times n$ all-zero matrix. Denote the Euclidean
norm of a vector by $\|\cdot\|$. For a vector $x\in\mathbb{R}^{n}$, denote its
$i$-th entry by $x_{i}$, and for a matrix $A\in\mathbb{R}^{n\times n}$, denote
its $(i,j)$-th entry by $a_{ij}$ or $[A]_{ij}$. The cardinality of a set
$\mathcal{S}$ is denoted by $|\mathcal{S}|$. The function
$\mathbb{I}_{[\textup{property}]}$ is the indicator function equal to one if
the property in the bracket holds, and equal to zero otherwise. Denote the
expectation of a random vector $X$ by $\mathbb{E}\\{X\\}$. For two sequences
of real numbers, $f(n)$ and $g(n)>0$, $n\in\mathbb{N}$, we write
$f(n)=O(g(n))$ if $|f(n)|\leq Cg(n)$ for all $n\in\mathbb{N}$ and some $C>0$,
$f(n)=o(g(n))$ if $|f(n)|/g(n)\to 0$, and $f(n)\sim g(n)$ if $f(n)/g(n)\to 1$
as $n\to\infty$. Further assuming $f(n)$ to be nonnegative, we say that
$f(n)=\omega(g(n))$ if $g(n)=o(f(n))$, that $f(n)=\Omega(g(n))$ if there is
$C>0$ such that $f(n)\geq Cg(n)$ for all $n\in\mathbb{N}$, and that
$f(n)=\Theta(g(n))$ if both $f(n)=O(g(n))$ and $f(n)=\Omega(g(n))$ hold. For
$x,y\in\mathbb{R}$, denote $x\vee y:=\max\\{x,y\\}$ and $x\wedge
y:=\min\\{x,y\\}$.

##  2 Problem Formulation

The gossip model with stubborn agents is a random process evolving over an
undirected graph $\mathcal{G}=(\mathcal{V},\mathcal{E},A)$, where
$\mathcal{V}$ is the node set with $|\mathcal{V}|=n\geq 2$, $\mathcal{E}$ is
the edge set, and $A=[a_{ij}]\in\mathbb{R}^{n\times n}$ is the weighted
adjacency matrix. The graph $\mathcal{G}$ has no self-loops (i.e., $a_{ii}=0$,
$\forall i\in\mathcal{V}$). $\mathcal{V}$ contains two types of agents,
regular and stubborn, denoted by $\mathcal{V}_{r}$ and $\mathcal{V}_{s}$,
respectively (so $\mathcal{V}=\mathcal{V}_{r}\cup\mathcal{V}_{s}$ and
$\mathcal{V}_{r}\cap\mathcal{V}_{s}=\emptyset$). In this paper we assume that
the regular agents form two disjoint communities $\mathcal{V}_{r1}$ and
$\mathcal{V}_{r2}$, and denote $\mathcal{C}_{i}=k$ if $i\in\mathcal{V}_{rk}$,
$k=1,2$. We call $\mathcal{C}$ the community structure of the graph. Regular
agent $i$ has state $X_{i}(t)\in\mathbb{R}$ at time $t\in\mathbb{N}$, and
stubborn agent $j$ has state $z^{s}_{j}$. Stacking these states, we denote the
state vector of regular agents at time $t$ by $X(t)\in\mathbb{R}^{n_{r}}$ and
the state vector of stubborn agents by $z^{s}\in\mathbb{R}^{n_{s}}$, where
$n_{r}:=|\mathcal{V}_{r}|$ and $n_{s}:=|\mathcal{V}_{s}|$. The random
interaction of the gossip model is captured by an interaction probability
matrix $W=[w_{ij}]\in\mathbb{R}^{n\times n}$ satisfying that
$w_{ij}=w_{ji}=a_{ij}/\alpha$, where
$\alpha=\sum_{i=1}^{n}\sum_{j=i+1}^{n}a_{ij}$ is the sum of all edge weights.
Hence $\mathbf{1}^{T}W\mathbf{1}/2=1$. At time $t$, edge $\\{i,j\\}$ is
selected with probability $w_{ij}$ independently of previous updates, and
agents update as follows,

$\displaystyle X(t+1)=Q(t)X(t)+R(t)z^{s},$ (1)

where $Q(t)\in\mathbb{R}^{n_{r}\times n_{r}}$, $R(t)\in\mathbb{R}^{n_{r}\times
n_{s}}$, and

$\displaystyle[Q(t),~{}R(t)]=$
$\displaystyle\begin{cases}[I_{n_{r}}-\frac{1}{2}(e_{i}^{(n_{r})}-e_{j}^{(n_{r})})(e_{i}^{(n_{r})}-e_{j}^{(n_{r})})^{T},~{}~{}~{}\mathbf{0}_{n_{r},n_{s}}],\\\
\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\text{if
}i,j\in\mathcal{V}_{r},\\\
[I_{n_{r}}-\frac{1}{2}e_{i}^{(n_{r})}(e_{i}^{(n_{r})})^{T},~{}~{}~{}\frac{1}{2}e_{i}^{(n_{r})}(e_{j}^{(n_{s})})^{T}],\\\
\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad~{}~{}~{}\text{if
}i\in\mathcal{V}_{r},j\in\mathcal{V}_{s}.\end{cases}$

In other words, only regular agents in $\\{i,j\\}$ update their states to the
average of $i$ and $j$’s previous states, and all other agents do not update.

We study how community structure and stubborn agents influence transient
behavior of agent states $X(t)$. The community structure will be defined in
Section 3.1. By transient behavior we mean a property of $X(t)$ that holds
over a finite time interval, as opposed to asymptotic behavior that holds as
time $t\to\infty$. As mentioned in Section 1.1, agents in the same community
tend to have similar states, but how well and how long these clusters form
still require rigorous analysis. We characterize the transient clusters of
$X(t)$ based on three types of references: (1) agents’ average states within
communities and everyone’s average state at time $t$, (2) expected average
states at time $t$, and (3) average initial states. As a comparison, we also
study the time when the distribution of $X(t)$ is close to the stationary
distribution. To sum up, the considered problem is as follows.

Figure 1:  Illustration of Assumption 1. The graph on the left demonstrates
the underlying network with two communities (dots and circles) and one
stubborn agent (the circle with a cross). Solid lines represent weighted
edges. The weights are indicated by line thickness. Edge weights within
communities are larger than between communities ($l_{s}^{(r)}>l_{d}^{(r)}$).
The edge weights between regular agents and the stubborn agent are the same.
The rest of the graphs show random interactions between agents, represented by
dashed lines. Agents interact more often if they have an edge with a larger
weight.

Problem. Given the initial regular states $X(0)$, the stubborn states $z^{s}$,
the community structure $\mathcal{C}$, and the weighted adjacency matrix $A$,
provide bounds for the deviation of $X(t)$ from the three types of average
states over finite time intervals, and bounds for the time when the
distribution of $X(t)$ is close to the stationary distribution.

Probability bounds for the deviation of $X(t)$ from average states at time $t$
are given in Corollary 1, which is a consequence of second-moment analysis
(Lemma 4). The deviation from expected average states is analyzed in Theorem
1. This result is stronger than the previous one because the references are
deterministic. Theorem 2 shows how $X(t)$ concentrates around average initial
states. Theorem 3 gives a lower bound of the time when $X(t)$ is close to
steady state.

##  3 Theoretical Analysis

We study transient behavior of gossip model with two communities. The analysis
provides crucial insight into understanding transient behavior of the model
under general conditions. Main results are presented in Section 3.1 and a
discussion is given in Section 3.2.

###  3.1 Main Results

We assume that the regular agents form two disjoint communities
$\mathcal{V}_{r1}$ and $\mathcal{V}_{r2}$ with equal size. For simplicity,
sort the agents as follows: $\mathcal{V}_{r1}=\\{1,\dots,r_{0}n/2\\}$,
$\mathcal{V}_{r2}=\\{1+r_{0}n/2,\dots,r_{0}n\\}$, and
$\mathcal{V}_{s}=\\{1+r_{0}n,\dots,n\\}$, with $r_{0}\in(0,1)$ such that
$r_{0}n=n_{r}$ is an even integer. The portion of stubborn agents is denoted
by $s_{0}:=1-r_{0}$. We introduce the following assumptions, illustrated in
Fig. 1, for the weighted adjacency matrix $A$ of graph $\mathcal{G}$.

######  Assumption 1 (Network topology).

  1. (i)

There exist $l_{s}^{(r)},l_{d}^{(r)}\in(0,1)$, depending on $n$, such that
$a_{ij}=l_{s}^{(r)}=l_{s}^{(r)}(n)$ for $i,j\in\mathcal{V}_{r}$ with $i\not=j$
and $\mathcal{C}_{i}=\mathcal{C}_{j}$, $a_{ij}=l_{d}^{(r)}=l_{d}^{(r)}(n)$ for
$i,j\in\mathcal{V}_{r}$ with $\mathcal{C}_{i}\not=\mathcal{C}_{j}$.

  2. (ii)

There exist $l_{ij}^{(s)}\in{\color[rgb]{0,0,0}[}0,1)$ with $1\leq i\leq
r_{0}n$ and $1\leq j\leq s_{0}n$, depending on $n$, such that
$a_{i,r_{0}n+j}=a_{r_{0}n+j,i}=l_{ij}^{(s)}=l_{ij}^{(s)}(n)$. For
$r_{0}n+1\leq i,j\leq n$, $a_{ij}=0$.

  3. (iii)

There exists a nonnegative number $l^{(s)}$ depending on $n$ such that
$\sum_{1\leq j\leq s_{0}n}l_{ij}^{(s)}=l^{(s)}=l^{(s)}(n)$ for all
$i\in\mathcal{V}_{r}$.

######  Remark 1.

Assumption 1 (i) indicates that the graph on regular agents is a weighted
graph such that edges between agents in the same community have the same
weight $l_{s}^{(r)}$ whereas those between communities have weight
$l_{d}^{(r)}$. In other words, the influence strength between agents depends
on their latent attributes. Such a weighted graph can be treated as the
expected adjacency matrix of an SBM, in which nodes are assigned with
community labels, and an edge exists with probability depending on the
community labels of that edge’s endpoints.  We introduce this simplified
assumption to highlight the phase transition phenomenon in the transient phase
of the dynamics, and proofs under this assumption are still nontrivial. It is
possible to generalize the results to the SBM case by considering the
concentration of adjacency matrices [44].  Although assuming that
interpersonal influence depends only on community labels is a simplified
setting, this model has been found to be efficient also in empirical studies
[10]. Note that the adjacency matrix $A$ has zeros entries in the diagonal
from the assumption that the graph has no self-loops. Parameter $l^{(s)}$
given in Assumption 1 (iii) is the sum of edge weights between one regular
agent and all stubborn agents, and thus represents the total influence of
stubborn agents on this regular agent. We assume that this sum is the same for
all regular agents for analysis simplicity. The results can be extended to the
case where the weight sums have upper and lower bounds.

We further impose an assumption for the initial vector.

######  Assumption 2 (Initial condition).

The initial regular states $X(0)$ and the stubborn states $z^{s}$ are
deterministic, and satisfy that $|X_{i}(0)|\leq c_{x}$ and $|z^{s}_{j}|\leq
c_{x}$, for all $1\leq i\leq r_{0}n$ and $1\leq j\leq s_{0}n$, and some
$c_{x}>0$.

From the definitions of $Q(t)$ and $R(t)$ in (1), it follows that

$\displaystyle\bar{Q}:=\mathbb{E}\\{Q(t)\\}$
$\displaystyle=I-\frac{1}{2\alpha}\begin{bmatrix}d_{1}&-a_{12}&\cdots&-a_{1,r_{0}n}\\\
-a_{21}&\ddots&&\vdots\\\ \vdots&&&\vdots\\\
-a_{r_{0}n,1}&\cdots&-a_{r_{0}n,r_{0}n-1}&d_{r_{0}n}\end{bmatrix},$ (2)
$\displaystyle\bar{R}:=\mathbb{E}\\{R(t)\\}$
$\displaystyle=\frac{1}{2\alpha}\tilde{M}:=\frac{1}{2\alpha}\begin{bmatrix}a_{1,r_{0}n+1}&\cdots&a_{1,n}\\\
\vdots&&\vdots\\\ a_{r_{0}n,r_{0}n+1}&\cdots&a_{r_{0}n,n}\end{bmatrix},$ (3)

where $d_{i}=\sum_{j\in\mathcal{V}}a_{ij}$, $i\in\mathcal{V}_{r}$. Note that
Assumption 1 implies
$d_{i}=r_{0}n(l_{s}^{(r)}+l_{d}^{(r)})/2+l^{(s)}-l_{s}^{(r)}=:\bar{d}$,
$i\in\mathcal{V}_{r}$, so

$\displaystyle\bar{Q}=I-\frac{1}{2\alpha}[(\bar{d}+l_{s}^{(r)})I-\tilde{A}],$

where

$\displaystyle\tilde{A}:=\begin{bmatrix}\mathbf{1}_{r_{0}n/2}&\mathbf{0}_{r_{0}n/2}\\\
\mathbf{0}_{r_{0}n/2}&\mathbf{1}_{r_{0}n/2}\end{bmatrix}\begin{bmatrix}l_{s}^{(r)}&l_{d}^{(r)}\\\
l_{d}^{(r)}&l_{s}^{(r)}\end{bmatrix}\begin{bmatrix}\mathbf{1}_{r_{0}n/2}&\mathbf{0}_{r_{0}n/2}\\\
\mathbf{0}_{r_{0}n/2}&\mathbf{1}_{r_{0}n/2}\end{bmatrix}^{T}.$

It can be shown that $\tilde{A}$ has a simple eigenvalue
$r_{0}n(l_{s}^{(r)}+l_{d}^{(r)})/2$, and a simple eigenvalue
$r_{0}n(l_{s}^{(r)}-l_{d}^{(r)})/2$, and the corresponding unit vectors are
$\eta:=\mathbf{1}_{r_{0}n}/\sqrt{r_{0}n}$ and
$\xi:=[\mathbf{1}_{r_{0}n/2}^{T}~{}-\mathbf{1}_{r_{0}n/2}^{T}]/\sqrt{r_{0}n}$,
respectively. Since $\tilde{A}$ is symmetric, it has the eigenvalue zero with
multiplicity $r_{0}n-2$ with orthogonal unit eigenvalues $w^{(i)}$, $3\leq
i\leq r_{0}n$. Moreover, $\eta$, $\xi$, $w^{(3)}$, $\dots$, $w^{(r_{0}n)}$
form an orthonormal basis of $\mathbb{R}^{r_{0}n}$. Denoting
$\lambda_{1}:=l^{(s)}/(2\alpha)$,
$\lambda_{2}:=(l_{d}^{(r)}r_{0}n+l^{(s)})/(2\alpha)$, and
$\lambda_{3}:=[(l_{s}^{(r)}+l_{d}^{(r)})r_{0}n/2+l^{(s)}]/(2\alpha)$, we
present the following summary of properties of $\bar{Q}$ and orthogonal
vectors, which will be used later.

######  Lemma 1.

Under Assumption 1, the following hold.
(i) The matrix $\bar{Q}\in\mathbb{R}^{r_{0}n\times r_{0}n}$ has a simple
eigenvalue $1-\lambda_{1}$ with a unit eigenvector $\eta$, a simple eigenvalue
$1-\lambda_{2}$ with a unit eigenvector $\xi$, and an eigenvalue
$1-\lambda_{3}$ with multiplicity $r_{0}n-2$ and with unit eigenvectors
$w^{(i)}$, $3\leq i\leq r_{0}n$. In addition, the vectors $\eta$, $\xi$,
$w^{(3)}$, $\dots$, $w^{(r_{0}n)}$ form an orthonormal basis of
$\mathbb{R}^{r_{0}n}$.
(ii) If $\\{x^{(i)}\in\mathbb{R}^{n},1\leq i\leq n\\}$ is an orthonormal basis
of $\mathbb{R}^{n}$, then it holds for all $z\in\mathbb{R}^{n}$ and $1\leq
j\leq n$ that

$\displaystyle I_{n}$ $\displaystyle=\sum_{i=1}^{n}x^{(i)}(x^{(i)})^{T},$
$\displaystyle\|z\|^{2}$
$\displaystyle=\Big{\|}\sum_{i=1}^{n}x^{(i)}(x^{(i)})^{T}z\Big{\|}^{2}=\sum_{i=1}^{n}\|x^{(i)}(x^{(i)})^{T}z\|^{2}$
$\displaystyle=\Big{\|}\sum_{i=1}^{j}x^{(i)}(x^{(i)})^{T}z\Big{\|}^{2}+\Big{\|}\sum_{i=j+1}^{n}x^{(i)}(x^{(i)})^{T}z\Big{\|}^{2}.$

Before presenting main theorems, we provide several properties of the gossip
model. The first lemma concerns the explicit expression of the weight sum of
the graph $\mathcal{G}$.

######  Lemma 2.

Under Assumption 1, the weight sum
$\alpha=r_{0}n[(l_{s}^{(r)}+l_{d}^{(r)})r_{0}n+4l^{(s)}-2l_{s}^{(r)}]/4$.

The conclusion follows directly from the definition of $\alpha$ and Assumption
1. $\Box$

The next lemma gives the expression of $\mathbb{E}\\{X(t)\\}$, and shows how
$\mathbb{E}\\{X(t)\\}$ evolves by decomposing it into three parts, which
correspond to the eigenspaces of $\bar{Q}$.

######  Lemma 3.

Suppose that Assumption 1 holds. Then the expectation of $X(t)$ satisfies
that, for all $t\in\mathbb{N}$,

$\displaystyle\mathbb{E}\\{X(t)\\}$
$\displaystyle=(1-\lambda_{1})^{t}\eta\eta^{T}X(0)+\frac{1}{\lambda_{1}}[1-(1-\lambda_{1})^{t}]\eta\eta^{T}\bar{R}z^{s}$
$\displaystyle+(1-\lambda_{2})^{t}\xi\xi^{T}X(0)+\frac{1}{\lambda_{2}}[1-(1-\lambda_{2})^{t}]\xi\xi^{T}\bar{R}z^{s}$
$\displaystyle+(1-\lambda_{3})^{t}\sum_{i=3}^{r_{0}n}w^{(i)}(w^{(i)})^{T}X(0)$
$\displaystyle+\frac{1}{\lambda_{3}}[1-(1-\lambda_{3})^{t}]\sum_{i=3}^{r_{0}n}w^{(i)}(w^{(i)})^{T}\bar{R}z^{s}.$

Lemma 1 yields that

$\displaystyle\bar{Q}$
$\displaystyle=(1-\lambda_{1})\eta\eta^{T}+(1-\lambda_{2})\xi\xi^{T}$
$\displaystyle+(1-\lambda_{3})\sum_{i=3}^{r_{0}n}w^{(i)}(w^{(i)})^{T}.$ (4)

Then the result follows from (1)–(3). $\Box$

We further introduce the following technical assumption.

######  Assumption 3.

Denote $\tilde{l}^{(s)}_{+}:=\max_{1\leq j\leq
s_{0}n}\sum_{i\in\mathcal{V}_{r}}l_{ij}^{(s)}$ and
$\tilde{l}^{(s)}_{-}:=\max_{1\leq j\leq
s_{0}n}\\{|\sum_{i\in\mathcal{V}_{r1}}l_{ij}^{(s)}-\sum_{i\in\mathcal{V}_{r2}}$
$l_{ij}^{(s)}|\\}$. It holds that
$\tilde{l}^{(s)}_{+}\vee\tilde{l}^{(s)}_{-}\leq c_{l}l^{(s)}$ for some
constant $c_{l}>0$.

######  Remark 2.

The assumption implies that both $\tilde{l}^{(s)}_{+}$ (the maximum influence
capability of a stubborn agent on all regular agents) and
$\tilde{l}^{(s)}_{-}$ (the maximum of absolute difference between the total
influences of a stubborn agent on the two communities) are of the same order
of $l^{(s)}$. Otherwise, the influence of stubborn agents may not be
homogeneous, which could be hard to analyze.

Now we present a lemma that will be used in the proof of main theorems. Denote
$X^{\eta}(t):=\eta\eta^{T}X(t)$, $X^{\xi}(t):=\xi\xi^{T}X(t)$,
$\Gamma:=\sum_{i=3}^{r_{0}n}w^{(i)}(w^{(i)})^{T}$ (thus,
$\Gamma^{T}\Gamma=\Gamma^{2}=\Gamma$), and $X^{\Gamma}(t):=\Gamma X(t)$. From
Lemma 1, $\eta\eta^{T}+\xi\xi^{T}+\Gamma=I_{r_{0}n}$, and we have the
decomposition $X(t)=X^{\eta}(t)+X^{\xi}(t)+X^{\Gamma}(t)$. Further, let
$X^{\bot}(t):=\tilde{\Gamma}X(t)$, where $\tilde{\Gamma}=\xi\xi^{T}+\Gamma$.
We get another decomposition of $X(t)$: $X(t)=X^{\eta}(t)+X^{\bot}(t)$ and
$X^{\eta}(t)^{T}X^{\bot}(t)=0$. Note that $X^{\eta}(t)+X^{\xi}(t)$ and
$X^{\eta}(t)$ represent the average states in each community and everyone’s
average state, respectively (the $i$-th entry of $X^{\eta}(t)+X^{\xi}(t)$ is
$(2\sum_{j\in\mathcal{V}_{r\mathcal{C}_{i}}}X_{j}(t))/(r_{0}n)$). So the two
decompositions reveal dynamics of average states. The following lemma gives
two upper bounds for the second moment of $X(t)$ under the two decompositions.

######  Lemma 4.

Suppose that Assumptions 1–3 hold. Denote $c_{s}:=\sqrt{s_{0}/r_{0}}$. It
holds for $t\in\mathbb{N}$ and $n\geq 4/r_{0}$ that

$\displaystyle~{}\mathbb{E}\\{\|X(t)\|^{2}\\}$
$\displaystyle\leq(1-\lambda_{1})^{t}\|X^{\eta}(0)\|^{2}+(1-\lambda_{2})^{t}\|X^{\xi}(0)\|^{2}+(1-\lambda_{3})^{t}$
$\displaystyle~{}\|X^{\Gamma}(0)\|^{2}+(1\wedge\lambda_{1}t)C_{11}c_{x}^{2}r_{0}n+\Big{(}\frac{\lambda_{2}}{\lambda_{3}}\wedge\lambda_{2}t\Big{)}[(1-\lambda_{2})^{t}$
$\displaystyle~{}\|X^{\xi}(0)\|^{2}+c_{x}^{2}]+(1\wedge\lambda_{2}t)c_{x}^{2},$
(5) $\displaystyle~{}\mathbb{E}\\{\|X(t)\|^{2}\\}$
$\displaystyle\leq(1-\lambda_{1})^{t}\|X^{\eta}(0)\|^{2}+(1-\lambda_{2}\wedge\lambda_{3})^{t}\|X^{\bot}(0)\|^{2}$
$\displaystyle+(1\wedge\lambda_{1}t)C_{21}c_{x}^{2}r_{0}n+\Big{(}\frac{\lambda_{1}}{\lambda_{2}\wedge\lambda_{3}}\wedge\lambda_{1}t\Big{)}C_{22}c_{x}^{2}r_{0}n,$
(6)

where $C_{11}:=3+c_{l}/2+16c_{s}c_{l}+(3c_{l}+23)/(2r_{0}n)$,
$C_{21}:=4c_{s}c_{l}+(5+c_{l})/(2r_{0}n)$, and
$C_{22}:=3+c_{l}/2+4c_{s}c_{l}+2/(r_{0}n)$.

The main idea of the proof is to separately bound the terms
$\mathbb{E}\\{\|X^{\eta}(t)\|^{2}\\}$, $\mathbb{E}\\{\|X^{\xi}(t)\|^{2}\\}$,
$\mathbb{E}\\{\|X^{\Gamma}(t)\|^{2}\\}$, and
$\mathbb{E}\\{\|X^{\bot}(t)\|\\}^{2}$. The conclusions then follow from Lemma
1. See Appendix A for the details. $\Box$

######  Remark 3.

Lemma 4 provides two bounds for how the second moment of agent states evolve
over time. Note that three types of terms appear in the bounds. The first type
is an exponentially decreasing term $(1-\lambda_{i})^{t}$, indicating the rate
of the averaging update. The second one is a linearly increasing term
$1\wedge\lambda_{i}t$, showing cumulative influence of stubborn agents.
Lastly, the ratios $\lambda_{2}t\wedge(\lambda_{2}/\lambda_{3})$ and
$\lambda_{1}t\wedge[\lambda_{1}/(\lambda_{2}\wedge\lambda_{3})]$ indicate the
effect of relative influence strength between the regular and the stubborn.
The bounds become trivial for $t=\omega(1/\lambda_{1})$. Hence they only
describe transient behavior.

An immediate consequence of the preceding analysis is that the difference
between the agent states and average states at each time step can be bounded.
For two vectors $X,Y\in\mathbb{R}^{r_{0}n}$ and $\varepsilon\in(0,1)$, we
denote the set of agents $i$ such that $|X_{i}-Y_{i}|>\varepsilon c_{x}$
(i.e., the difference between $X_{i}$ and $Y_{i}$ is large) by

$\displaystyle\mathcal{S}(X,Y,\varepsilon):=\\{i\in\mathcal{V}_{r}:|X_{i}-Y_{i}|>\varepsilon
c_{x}\\}.$

Then the proof of Lemma 4 ensures the following result.

######  Corollary 1.

Suppose that Assumptions 1–3 hold. Then it holds for $t\in\mathbb{N}$, $n\geq
4/r_{0}$, and $\varepsilon,\delta\in(0,1)$ that

$\displaystyle~{}\mathbb{P}\\{|\mathcal{S}(X(t),X^{\eta}(t)+X^{\xi}(t),\varepsilon)|>\delta
r_{0}n\\}$
$\displaystyle\leq\frac{1}{\varepsilon^{2}\delta}\Big{[}(1-\lambda_{3})^{t}\frac{\|X^{\Gamma}(0)\|^{2}}{c_{x}^{2}r_{0}n}+\Big{(}\frac{\lambda_{1}}{\lambda_{3}}\wedge\lambda_{1}t\Big{)}\Big{(}3+\frac{c_{l}}{2}$
$\displaystyle+10c_{s}c_{l}+\frac{c_{l}+13}{2r_{0}n}\Big{)}+\Big{(}\frac{\lambda_{2}}{\lambda_{3}}+\lambda_{2}t\Big{)}\Big{(}\frac{(1-\lambda_{2})^{t}\|X^{\xi}(0)\|^{2}}{c_{x}^{2}r_{0}n}$
$\displaystyle+\frac{1}{r_{0}n}\Big{)}\Big{]},$ (7)
$\displaystyle~{}\mathbb{P}\\{|\mathcal{S}(X(t),X^{\eta}(t),\varepsilon)|>\delta
r_{0}n\\}$
$\displaystyle\leq\frac{1}{\varepsilon^{2}\delta}\Big{[}(1-\lambda_{2}\wedge\lambda_{3})^{t}\frac{\|X^{\bot}(t)\|^{2}}{c_{x}^{2}r_{0}n}+\Big{(}\frac{\lambda_{1}}{\lambda_{2}\wedge\lambda_{3}}\wedge\lambda_{1}t\Big{)}$
$\displaystyle\Big{(}3+\frac{c_{l}}{2}+4c_{s}c_{l}+\frac{2}{r_{0}n}\Big{)}\Big{]}.$
(8)

######  Remark 4.

The first result (7) bounds the probability of at least $\delta r_{0}n$ agents
having states at least $\varepsilon c_{x}$ away from the average states in
their communities. This probability bound decreases first due to the decay of
$(1-\lambda_{3})^{t}$ and the relatively small value of $\lambda_{i}t$, and
then increases with $t$ to a constant bound (whether the constant bound is
trivial depends on the ratios $\lambda_{i}/\lambda_{3}$, $i=1,2$, which we
will discuss in detail in Corollary 2). Similarly, the second result (8) shows
that there can be a time interval, over which many agents have states close to
everyone’s average state with high probability.

To prove the results, note that by the Markov inequality, for
$X,Y\in\mathbb{R}^{r_{0}n}$ and $\varepsilon\in(0,1)$,

$\displaystyle\mathbb{P}\\{|\mathcal{S}(X,Y,\varepsilon)|\geq\delta r_{0}n\\}$
$\displaystyle\leq\mathbb{P}\\{\|X-Y\|^{2}\geq\varepsilon^{2}\delta
c_{x}^{2}r_{0}n\\}$
$\displaystyle\leq\frac{\mathbb{E}\\{\|X-Y\|^{2}\\}}{\varepsilon^{2}\delta
c_{x}^{2}r_{0}n}.$ (9)

Now note that $X(t)-X^{\eta}(t)-X^{\xi}(t)=X^{\Gamma}(t)$ and
$X(t)-X^{\eta}(t)=X^{\bot}(t)$, so (7) and (8) follow from the upper bound of
$\mathbb{E}\\{\|X^{\Gamma}(t)\|^{2}\\}$ and
$\mathbb{E}\\{\|X^{\bot}(t)\|^{2}\\}$ given in the proof of Lemma 4. $\Box$
The preceding results indicate that we can use average states as references to
describe how agent states evolve in finite time. Further analysis based on
Lemma 4 can yield stronger results. That is, we can use the expected average
states $\mathbb{E}\\{X^{\eta}(t)+X^{\xi}(t)\\}$ and
$\mathbb{E}\\{X^{\eta}(t)\\}$ as references.

######  Theorem 1.

Suppose that Assumptions 1–3 hold. It holds for $n\geq 4/r_{0}$ and
$\varepsilon,\delta\in(0,1)$ that

$\displaystyle\mathbb{P}\\{|\mathcal{S}(X(t),\mathbb{E}\\{X^{\eta}(t)+X^{\xi}(t)\\},\varepsilon)|>\delta
r_{0}n\\}\leq$
$\displaystyle\frac{1}{\varepsilon^{2}\delta}\Big{[}(1-\lambda_{3})^{t}\frac{\|X^{\Gamma}(0)\|^{2}}{c_{x}^{2}r_{0}n}+(4+C_{11})\lambda_{1}t+\lambda_{2}\Big{(}\frac{1}{\lambda_{3}}+t\Big{)}$
$\displaystyle~{}\Big{(}\frac{(1-\lambda_{2})^{t}\|X^{\xi}(0)\|^{2}}{c_{x}^{2}r_{0}n}+\frac{1}{r_{0}n}\Big{)}\Big{]},~{}\forall\frac{1}{\lambda_{3}}\leq
t\leq\frac{1}{\lambda_{2}},$ (10)
$\displaystyle\mathbb{P}\\{|\mathcal{S}(X(t),\mathbb{E}\\{X^{\eta}(t)\\},\varepsilon)|>\delta
r_{0}n\\}$
$\displaystyle\leq\frac{1}{\varepsilon^{2}\delta}\Big{[}(1-\lambda_{2}\wedge\lambda_{3})^{t}\frac{\|X^{\bot}(0)\|^{2}}{c_{x}^{2}r_{0}n}+(3+C_{21})\lambda_{1}t$
$\displaystyle+\frac{C_{22}\lambda_{1}}{\lambda_{2}\wedge\lambda_{3}}\Big{]},~{}\forall\frac{1}{\lambda_{2}\wedge\lambda_{3}}\leq
t\leq\frac{1}{\lambda_{1}},$ (11)

where $C_{11}$, $C_{21}$, and $C_{22}$ are given in Lemma 4.

To prove (10), from (9) it suffices to bound
$\mathbb{E}\\{\|X(t)-\mathbb{E}\\{X^{\eta}(t)\\}-\mathbb{E}\\{X^{\xi}(t)\\}\|^{2}\\}$.
From Lemma 1 (ii), we have that

$\displaystyle\mathbb{E}\\{\|X(t)-\mathbb{E}\\{X^{\eta}(t)\\}-\mathbb{E}\\{X^{\xi}(t)\\}\|^{2}\\}$
$\displaystyle=\mathbb{E}\\{\|X(t)\|^{2}\\}-2\mathbb{E}\\{X(t)\\}^{T}(\mathbb{E}\\{X^{\eta}(t)\\}+\mathbb{E}\\{X^{\xi}(t)\\})$
$\displaystyle+\|\mathbb{E}\\{X^{\eta}(t)\\}+\mathbb{E}\\{X^{\xi}(t)\\}\|^{2}$
$\displaystyle=\mathbb{E}\\{\|X(t)\|^{2}\\}-\|\mathbb{E}\\{X^{\eta}(t)\\}\|^{2}-\|\mathbb{E}\\{X^{\xi}(t)\\}\|^{2}.$
(12)

From Lemma 3 and the Bernoulli inequality, it holds that

$\displaystyle\|\mathbb{E}\\{X^{\eta}(t)\\}\|^{2}$
$\displaystyle=\\{(1-\lambda_{1})^{t}\eta^{T}X(0)+[1-(1-\lambda_{1})^{t}]\zeta_{1}\\}^{2}$
$\displaystyle\geq(1-\lambda_{1})^{2t}\|X^{\eta}(0)\|^{2}-2\lambda_{1}t(1-\lambda_{1})^{t}\|X^{\eta}(0)\||\zeta_{1}|$
$\displaystyle\|\mathbb{E}\\{X^{\xi}(t)\\}\|^{2}$
$\displaystyle=\Big{\\{}(1-\lambda_{2})^{t}\xi^{T}X(0)+\frac{\lambda_{1}}{\lambda_{2}}[1-(1-\lambda_{2})^{t}]\zeta_{2}\Big{\\}}^{2}$
$\displaystyle\geq(1-\lambda_{2})^{2t}\|X^{\xi}(0)\|^{2}-2\lambda_{1}t(1-\lambda_{2})^{t}\|X^{\xi}(0)\||\zeta_{2}|.$

Thus,

$\displaystyle-\|\mathbb{E}\\{X^{\eta}(t)\\}\|^{2}-\|\mathbb{E}\\{X^{\xi}(t)\\}\|^{2}$
$\displaystyle\leq-(1-\lambda_{1})^{2t}\|X^{\eta}(0)\|^{2}-(1-\lambda_{2})^{2t}\|X^{\xi}(0)\|^{2}$
$\displaystyle+3\lambda_{1}tc_{x}^{2}r_{0}n$

Hence, when $1/\lambda_{3}\leq t\leq 1/\lambda_{2}$, from (5) in Lemma 4, (12)
can be bounded by

$\displaystyle(1-\lambda_{3})^{t}\|X^{\Gamma}(0)\|^{2}+(4+C_{11})\lambda_{1}tc_{x}^{2}r_{0}n$
$\displaystyle+\lambda_{2}\Big{(}\frac{1}{\lambda_{3}}+t\Big{)}[(1-\lambda_{2})^{t}\|X^{\xi}(0)\|^{2}+c_{x}^{2}],$

which gives (10). Similarly, (11) follows from (6) . $\Box$

######  Remark 5.

The results provide bounds for the probability of agent states concentrating
around expected average states. In particular, consider the case where
stubborn-agent influence is small (i.e., $\lambda_{1}$ is small). If the
influence strength within communities is much larger than that between
communities (hence $\lambda_{2}/\lambda_{3}$ is small), then it follows from
(10) that most agent states concentrate around average states within
communities and thus form transient clusters with high probability, at the
early phase of the process. If the stubborn-agent influence is small
($\lambda_{1}/(\lambda_{2}\wedge\lambda_{3})$ is small), but the influence
strength within and between communities is similar ($\lambda_{2}$ and
$\lambda_{3}$ have similar values), then (11) yields that most agent states
concentrate around everyone’s average state with high probability. See
Corollary 2 for detailed discussion on how link strength parameters influence
the concentration.

######  Remark 6.

In this remark we compare the obtained results with existing transient
behavior analysis. The authors of [26] study a generalized HK model and define
a transient cluster as a subgroup of agents whose opinion range decreases
faster than the distance of the subgroup from other agents. Here we
characterize agent states based on their distance from the average states.
Such a framework includes situations where clusters approach each other, but
defining such references requires specifying subgroups beforehand. The paper
[28] provides bounds for opinion difference in finite time for a stochastic
bounded confidence model. These bounds coincide with the asymptotic behavior.
In contrast, here we study transient behavior of the gossip model that is
different from the asymptotic behavior. For the gossip model without stubborn
agents, [38] shows that $\|X(t)-X^{\eta}(t)\|^{2}$ is close to its expectation
at the early stage of the process, which provides insight into why both
average states and expected average states can be used as references. We will
study such concentration in the future.

It is possible to derive bounds similar to Theorem 1 but with slightly
different constants for $\mathcal{S}(X(t),X^{\eta}(0)+X^{\xi}(0),\varepsilon)$
and $\mathcal{S}(X(t),X^{\eta}(0),\varepsilon)$, that is, the deviation of
agent states from average intial states. The next theorem specifies the time
intervals over which agent states concentrate around average initial states.
Note that parallel results for the expected average states also hold.

######  Theorem 2.

Suppose that Assumptions 1–3 hold and $n\geq 4/r_{0}$. Let
$\varepsilon,\delta,\gamma\in(0,1)$ be such that
$\varepsilon^{2}\delta\gamma\leq 2/e$.
(i) Assume that
$\lambda_{2}\log[2/(\varepsilon^{2}\delta\gamma))]<\lambda_{3}$ and

$\displaystyle
2\Big{[}(3+C_{11})\lambda_{1}\log\frac{2}{\varepsilon^{2}\delta\gamma}+C_{12}\Big{(}1+\log\frac{2}{\varepsilon^{2}\delta\gamma}\Big{)}\lambda_{2}\Big{]}$
$\displaystyle<\varepsilon^{2}\delta\gamma\lambda_{3}.$ (13)

Then for all $t\in(\underline{t}_{1},\overline{t}_{1})\not=\emptyset$ it holds
that

$\displaystyle\mathbb{P}\\{|\mathcal{S}(X(t),X^{\eta}(0)+X^{\xi}(0),\varepsilon)|\geq\delta
r_{0}n\\}\leq\gamma,$ (14)

where $C_{11}$ is given in Lemma 4,
$C_{12}=\|X^{\xi}(0)\|^{2}/(c_{x}^{2}r_{0}n)$ $+1/(r_{0}n)$,

$\displaystyle\underline{t}_{1}$
$\displaystyle=\frac{\log[2/(\varepsilon^{2}\delta\gamma)]}{\lambda_{3}},~{}\overline{t}_{1}=\frac{\varepsilon^{2}\delta\gamma/2-C_{12}\lambda_{2}/\lambda_{3}}{C_{11}\lambda_{1}+C_{12}\lambda_{2}}\wedge\frac{1}{\lambda_{2}}.$

(ii) Assume that

$\displaystyle
2\Big{[}(3+C_{21})\log\frac{2}{\varepsilon^{2}\delta\gamma}+C_{22}\Big{]}\lambda_{1}<\varepsilon^{2}\delta\gamma(\lambda_{2}\wedge\lambda_{3}).$
(15)

Then for all $t\in(\underline{t}_{2},\overline{t}_{2})\not=\emptyset$ it holds
that

$\displaystyle\mathbb{P}\\{|\mathcal{S}(X(t),X^{\eta}(0),\varepsilon)|\geq\delta
r_{0}n\\}\leq\gamma,$ (16)

where $C_{21}$ and $C_{22}$ are given in Lemma 4,

$\displaystyle\underline{t}_{2}=\frac{\log[2/(\varepsilon^{2}\delta\gamma)]}{\lambda_{2}\wedge\lambda_{3}},~{}\overline{t}_{2}=\frac{\varepsilon^{2}\delta\gamma/2-C_{22}\lambda_{1}/(\lambda_{2}\wedge\lambda_{3})}{C_{21}\lambda_{1}}.$

######  Remark 7.

The first part of the theorem states that, if $\lambda_{3}$ is large enough,
then we can uniformly upper-bound the probability that the minority of regular
agents have states different from the initial average opinion of their
community over a time interval. The second part indicates that it is possible
to uniformly upper-bound the probability of a small portion of regular agents
with states away from everyone’s average initial state over a time interval,
if $\lambda_{1}$ is much smaller than $\lambda_{2}$ and $\lambda_{3}$. We note
that similar results hold for the expected average states. To obtain a
nontrivial bound, $\delta$ (the portion of regular agents whose states do not
concentrate) and $\gamma$ (the probability that the concentration uniformly
happens) need to be small. But $\varepsilon$ (the error of the concentration)
does not need. For example, it is sufficient to set $\varepsilon$ to be less
than half of the distance between average states of the two communities, so
that the two transient clusters can be distinguished. For a fixed network,
setting smaller $\varepsilon$ and $\delta$ leads to a large bound of $\gamma$,
because stronger concentration occurs with less probability.

The conclusion is obtained by following the same argument of Theorem 1 and
then analyzing the obtained upperbounds. See Appendix C. $\Box$

So far we have studied concentration around average states based on conditions
of $\lambda_{i}$, The following corollary, which is a consequence of Theorem
2, explicitly shows how such phenomena depend on link strength parameters
$l_{s}^{(r)}$, $l_{d}^{(r)}$, and $l^{(s)}$. Parallel results also hold for
the expected average states.

######  Corollary 2.

Suppose that Assumptions 1–3 hold and denote $l_{0}^{(s)}:=l^{(s)}/(r_{0}n)$.

(i) If $l_{s}^{(r)}=\omega(l_{d}^{(r)}\vee l_{0}^{(s)})$, then for large
enough $n$ depending on $l_{s}^{(r)}$, $l_{d}^{(r)}$, and $l^{(s)}$, (14)
holds for all $t\in(\underline{t}_{1},\overline{t}_{1})$ with

$\displaystyle\underline{t}_{1}=\Big{(}\Theta(1)+O\Big{(}\frac{l_{0}^{(s)}}{l_{s}^{(r)}}\Big{)}\Big{)}r_{0}n,~{}\overline{t}_{1}=\Theta\Big{(}\frac{l_{s}^{(r)}}{l_{d}^{(r)}\vee
l_{0}^{(s)}}\Big{)}r_{0}n.$

(ii) If $l_{s}^{(r)}\leq l_{d}^{(r)}+o(l_{d}^{(r)})$ and
$l_{d}^{(r)}=\omega(l_{0}^{(s)})$, then for large enough $n$ depending on
$l_{d}^{(r)}$ and $l^{(s)}$, (16) holds for all
$t\in(\underline{t}_{2},\overline{t}_{2})$ with

$\displaystyle\underline{t}_{2}$
$\displaystyle=\Big{(}\Theta(1)+O\Big{(}\frac{[0\vee(l_{s}^{(r)}-l_{d}^{(r)})]+l_{0}^{(s)}}{l_{d}^{(r)}}\Big{)}\Big{)}r_{0}n$
$\displaystyle\overline{t}_{2}$
$\displaystyle=\Theta\Big{(}\frac{l_{d}^{(r)}}{l_{0}^{(s)}}\Big{)}r_{0}n.$

We follow the notation in Theorem 2. From definition of $\lambda_{i}$, it
follows that the assumptions of Theorem 2 (i) are equivalent to

$\displaystyle
2\Big{(}\log\frac{2}{\varepsilon^{2}\delta\gamma}-1\Big{)}l_{0}^{(s)}+\Big{(}2\log\frac{2}{\varepsilon^{2}\delta\gamma}-1\Big{)}l_{d}^{(r)}<l_{s}^{(r)}$
(17)
$\displaystyle~{}2\Big{[}2(3+C_{11}+C_{12})\log\frac{2}{\varepsilon^{2}\delta\gamma}+2C_{12}-\varepsilon^{2}\delta\gamma\Big{]}l_{0}^{(s)}$
$\displaystyle+\Big{[}4C_{12}\Big{(}1+\log\frac{2}{\varepsilon^{2}\delta\gamma}\Big{)}-\varepsilon^{2}\delta\gamma\Big{]}l_{d}^{(r)}<\varepsilon^{2}\delta\gamma
l_{s}^{(r)}.$ (18)

The condition $l_{s}^{(r)}=\omega(l_{d}^{(r)}\vee l_{0}^{(s)})$ guarantees
that (17) and (18) hold for large enough $n$ that depends on $l_{s}^{(r)}$,
$l_{d}^{(r)}$, and $l^{(s)}$. Hence the conclusion follows from the expression
of $\underline{t}_{1}$ and $\overline{t}_{1}$ given in Theorem 2. The proof of
(ii) is similar. It suffices to note that (15) is equivalent to

$\displaystyle~{}2\Big{[}2(3+C_{21})\log\frac{2}{\varepsilon^{2}\delta\gamma}+2C_{22}-\varepsilon^{2}\delta\gamma\Big{]}l_{0}^{(s)}$
$\displaystyle<\varepsilon^{2}\delta\gamma[l_{d}^{(r)}+(l_{d}^{(r)}\wedge
l_{s}^{(r)})].$ (19)

The condition $l_{d}^{(r)}=\omega(l_{0}^{(s)})$ ensures that (19) holds with
large enough $n$ that depends on $l_{d}^{(r)}$ and $l^{(s)}$. $\Box$

######  Remark 8.

The first part of the corollary indicates that, if the intra-community weights
are of higher order than the inter-community weights and the average weight
between regular and stubborn agents, then most agent states concentrate around
the initial average opinion of the corresponding community with high
probability over a finite time interval. The length of this interval depends
on relative strength within communities to that between communities and
between regular and stubborn agents. The assumption $l_{s}^{(r)}\leq
l_{d}^{(r)}+o(l_{d}^{(r)})$ of the second part means that intra-community
weights are less than or slightly larger than inter-community weights. If
stubborn influence is also small, then most agent states are close to
everyone’s initial average opinion with large probability at the early stage
of the process. Note that $l_{s}^{(r)}\leq l_{d}^{(r)}+o(l_{d}^{(r)})$ implies
$l_{s}^{(r)}=O(l_{d}^{(r)})$, so the corollary establishes a sharp phase
transition.

The preceding results study the case where the influence of stubborn agents is
small. In the following, we investigate the case with large stubborn
influence. It is known that gossip model (1) converges to a unique stationary
distribution $\pi$ (that is, if $X(0)$ has distribution $\pi$, then $X(t)$ has
the same distribution for all $t\in\mathbb{N}^{+}$), if there is at least one
stubborn agent and the network is connected [6, 39]. To characterize the
distance between transient and stationary distributions of agent states, we
introduce the Wasserstein metric between two measures $\mu$ and $\nu$,

$\displaystyle d_{W}(\mu,\nu):=\inf_{(X,Y)\in J}\mathbb{E}\\{\|X-Y\|\\},$

where $J$ is the set of pairs of random vectors $(X,Y)$ such that the marginal
distribution of $X$ is $\mu$ and the marginal distribution of $Y$ is $\nu$.
The following theorem provides the time interval over which the distribution
of $X(t)$ is close to $\pi$.

Table 1: Summary of Main Results Conditions |  Behavior of Agent States |  Results
---|---|---
$l_{s}^{(r)}=\omega(l_{d}^{(r)}\wedge l^{(s)}_{0})$ with
$l_{0}^{(s)}=l^{(s)}/(r_{0}n)$
(stubborn influence is small,
intra-community influence is large) |  Concentrate around average states/expected average states/average initial states within communities over the time interval $(\Theta(r_{0}n),\Theta(l_{s}^{(r)}r_{0}n/(l_{d}^{(r)}\vee l_{0}^{(s)})))$ |  (7), (10), Theorem 2 (i),
Corollary 2 (i)
$l_{s}^{(r)}\leq l_{d}^{(r)}+o(l_{d}^{(r)})$ and
$l_{d}^{(r)}=\omega(l_{0}^{(s)})$
(stubborn influence is small, intra-
community influence is moderate or small) |  Concentrate around everyone’s average state/expected average state/average initial state over the time interval $(\Theta(r_{0}n),\Theta(l_{d}^{(r)}r_{0}n/l_{0}^{(s)})))$ |  (8), (11), Theorem 2 (ii),
Corollary 2 (ii)
$l_{s}^{(r)}\vee l_{d}^{(r)}=o(l_{0}^{(s)})$
(stubborn influence is large) |  Close to the stationary distribution over the time interval $(\Theta(r_{0}n\log(r_{0}n)),+\infty)$ |  Corollary 3

######  Theorem 3.

Suppose that Assumptions 1–2 hold. Then, for $\varepsilon\in(0,1)$, it holds
that

$\displaystyle d_{W}(X(t),\pi)\leq\varepsilon,~{}\forall
t>\frac{\log\\{c_{x}{\color[rgb]{0,0,0}(r_{0}n)^{\frac{5}{2}}}[1+1/(2\lambda_{1})]/\varepsilon\\}}{\log[1/(1-\lambda_{1})]}.$

The conclusion is obtained from a coupling argument. See Appendix B. $\Box$

Theorem 3 provides a general characterization for behavior of the gossip model
in the long run. The following corollary focuses on the case where the
influence of stubborn agents is large.

######  Corollary 3.

Suppose that Assumptions 1–2 hold. If $(l_{d}^{(r)}\vee
l_{s}^{(r)})n=o(l^{(s)})$, then $d_{W}(X(t),\pi)\leq\varepsilon$ holds for
$\varepsilon\in(0,1)$ and $t>t_{0}$ with
$t_{0}=t_{0}(\varepsilon)=\Theta(r_{0}n\log(r_{0}n))$.

######  Remark 9.

Corollary 3 indicates that, if the influence of stubborn agents is large, then
the distribution of $X(t)$ can be close to the stationary distribution of the
gossip model at the early stage of the process.

(a) The case where $l_{s}^{(r)}=(\log^{2.5}n)/n$, $l_{d}^{(r)}=(\log n)/n$,
and $l^{(s)}=(s_{0}\log n)/2$. Most agent states in the same community are
close to the expected average state of that community (black dashed lines).

(b) The case where $l_{s}^{(r)}=(\log^{2.5}n)/n$, $l_{d}^{(r)}=(\log n)/n$,
and $l^{(s)}=(s_{0}\log^{2}n)/2$. Agents behave similar to Fig. 2(a), but move
towards the origin in the long run.

(c) The case where $l_{s}^{(r)}=(\log^{2.5}n)/n$,
$l_{d}^{(r)}=(\log^{2.4}n)/n$, and $l^{(s)}=(s_{0}\log n)/2$. Most states are
close to everyone’s expected average state (the black dashed line), and keep
fluctuating.

(d) The case where $l_{s}^{(r)}=(\log n)/n$, $l_{d}^{(r)}=(\log n)/n$, and
$l^{(s)}=(s_{0}\log^{3}n)/2$. Most agents move quickly towards stubborn agents
during the initial phase, and stay polarized.

Figure 2:  Behavior of the gossip model. The figure illustrates the evolution
of regular-agent states under four sets of parameters. The color of a
trajectory represents the community label of that agent (red represents
$\mathcal{V}_{r1}$, and blue represents $\mathcal{V}_{r2}$).

###  3.2 Discussion and Extension

In this subsection, we first summarize obtained transient behavior under
different parameter settings, then discuss the extensions of the results.

In the previous subsection, we obtained several probability bounds for agent
states concentrating around average states (Corollary 1), expected average
states (Theorem 1), and average initial states (Theorem 2). Note that these
bounds are the same except for some constants. So the explicit dependence of
transient behavior on link strength parameters $l_{s}^{(r)}$, $l_{d}^{(r)}$,
and $l^{(s)}$, given in Corollary 2, still holds for the cases of average
states and expected average states. Table 1 summarizes the findings. The
results indicate a phase transition phenomenon: the model behaves differently
at the early stage of the process under different parameter settings.

We note that the obtained bounds are not tight. As shown in Section 4,
expected average states are good references for transients. The concentration
occurs for small networks. In contrast, concentration around average initial
states requires much larger $n$. The key idea of studying transient behavior
in this paper is to find references such as the expected average states and
then to bound the deviation of agent states from such references. Following
this framework, it is possible to generalize the obtained results to multiple-
community cases. With the help of matrix perturbation theory, it is also
possible to deal with the case where communities do not have equal size or the
total influences of stubborn agents on regular agents are different (i.e.,
Assumption 1 (iii) does not hold). Studying the gossip model over an SBM needs
analysis of the deviation of the random graph from its expected graph based on
matrix concentration inequalities (e.g. [44]).

(a) Concentration around expected average states within communities, where
$n=60$, $l_{s}^{(r)}=(\log^{2.5}n)/n$, $l_{d}^{(r)}=(\log n)/n$, and
$\varepsilon=0.3$.

(b) Concentration around everyone’s expected average state, where $n=60$,
$l_{s}^{(r)}=(\log^{2.5}n)/n$, $l_{d}^{(r)}=(\log^{2.4}n)/n$, and
$\varepsilon=0.2$.

(c) Concentration around average initial states within communities, where $n$,
$l_{s}^{(r)}$, $l_{d}^{(r)}$, and $\varepsilon$ are the same as (a). (d)
Concentration around average initial states within communities, where
$l_{s}^{(r)}$, $l_{d}^{(r)}$, and $\varepsilon$ are the same as (a) and
$n=500$. (e) Concentration around everyone’s average initial state, where $n$,
$l_{s}^{(r)}$, $l_{d}^{(r)}$, and $\varepsilon$ are the same as (b).

Figure 3:  The probability $p_{t}$ of at least $\delta$ portion of agents with
states at least $\varepsilon c_{x}$ away from average states at time $t$. In
all experiments, $l^{(s)}=(s_{0}\log n)/2$. The expected average states are
considered in (a–b), whereas the average initial states in (c–e).

(a) The case where $l_{s}^{(r)}$ varies. $\beta_{2}=5$ and $\beta_{3}=1$.

(b) The case where $l^{(s)}$ varies. $\beta_{1}=1$ and $\beta_{2}=5$.

Figure 4:  Phase transition of transient behavior of the gossip model. In the
experiments, we set $l_{s}^{(r)}=(\log^{\beta_{1}}n)/n$,
$l_{d}^{(r)}=(\log^{\beta_{2}}n)/n$, and $l^{(s)}=\log^{\beta_{3}}n$, and
compute
$d_{c}=2|\sum_{i\in\mathcal{V}_{r1}}X_{i}(t)-\sum_{i\in\mathcal{V}_{r2}}X_{i}(t)|/(r_{0}n)$
with $t=\lfloor n\log n\rfloor$.

##  4 Numerical Simulation

In this section, we conduct numerical simulations to validate the theoretical
results obtained in Section 3.

In the first set of experiments shown in Fig. 2, we demonstrate transient
behavior of the gossip model. Set the size of the network $n=60$, the bound of
agent states $c_{x}=1$, and the portion of regular agents $r_{0}=0.9$.
Generate the initial value $X_{i}(0)$ independently from uniform distribution
on $(0,1)$ for all $i\in\mathcal{V}_{r1}$, $X_{j}(0)$ independently from
uniform distribution on $(-1,0)$ for all $j\in\mathcal{V}_{r2}$, and set
stubborn-agent states
$z^{s}=[\mathbf{1}_{s_{0}n/2}~{}-\mathbf{1}_{s_{0}n/2}]$.

First, we set the edge weight between agents in the same community to be
$l_{s}^{(r)}=(\log^{2.5}n)/n$, greater than the edge weight between
communities $l_{d}^{(r)}=(\log n)/n$. The edge weights between regular and
stubborn agents are as follows: for all $i\in\mathcal{V}_{r1}$,
$l_{ij}^{(s)}=(\log n)/n$ for $1\leq j\leq s_{0}n/2$, and $a_{ij}=0$ for
$1+s_{0}n/2\leq j\leq s_{0}n$; for all $i\in\mathcal{V}_{r2}$,
$l_{ij}^{(s)}=0$ for $1\leq j\leq s_{0}n/2$, and $a_{ij}=(\log n)/n$ for
$1+s_{0}n/2\leq j\leq s_{0}n$. Hence $l^{(s)}=(s_{0}\log n)/2$. This setting
intuitively means that the first half of stubborn agents influence only
$\mathcal{V}_{r1}$, whereas the second half influence only $\mathcal{V}_{r2}$.
We use this setting for all numerical experiments. Fig. 2(a) shows that agents
form two transient clusters corresponding to their community labels and
centered around the expected average states within communities. Asymptotic
behavior of the system can be different from what shown in Fig. 2(a). As an
example, set $l_{s}^{(r)}=(\log^{2.5}n)/n$, $l_{d}^{(r)}=(\log n)/n$, and
$l^{(s)}=(s_{0}\log^{2}n)/2$. As in Fig. 2(b), agents in the same community
also form transient clusters, but they get close in the end. Next, we set
$l_{s}^{(r)}=(\log^{2.5}n)/n$, $l_{d}^{(r)}=(\log^{2.4}n)/n$, and
$l^{(s)}=(s_{0}\log n)/2$. In this case, the influence of stubborn agents is
small, and inter-community influence strength is similar to intra-community
strength. Hence all agents form a single transient cluster and concentrate
around everyone’s average state, as shown in Fig. 2(c). However, they cannot
reach a consensus and keep fluctuating in the long run, because of the
presence of stubborn agents. Finally, set $l_{s}^{(r)}=(\log n)/n$,
$l_{d}^{(r)}=(\log n)/n$, and $l^{(s)}=(s_{0}\log^{3}n)/2$. Fig. 2(d)
illustrates the case where the influence of stubborn agents is large. The
figure shows that agent states move quickly towards the positions of stubborn
agents.

Next we study the probability of concentration around average states,
investigated in Theorems 1 and 2. We first study concentration around expected
average states. Set $n=60$, $l_{s}^{(r)}=(\log^{2.5}n)/n$, $l_{d}^{(r)}=(\log
n)/n$, and $l^{(s)}=(s_{0}\log n)/2$ (i.e., intra-community edge weights are
large). The model is run for $200$ times and the final time step is $\lfloor
n(\log n)^{2}\rfloor$. We estimate the probability $p_{t}$ that the
concentration fails by computing
$\frac{1}{200}\sum_{k=1}^{200}\mathbb{I}_{[|\mathcal{S}_{t}^{\varepsilon}(k)|\geq\delta
r_{0}n]}$. Here $\mathcal{S}_{t}^{\varepsilon}(k)$ is the set
$\mathcal{S}(X(t),\mathbb{E}\\{X^{\eta}(t)+X^{\xi}(t)\\},\varepsilon)$ at the
$k$-th run, that is, the set of agents with states at least $\varepsilon
c_{x}$ away from the expected average state of their communities at time $t$.
The concentration error $\varepsilon$ and the portion of non-concentrating
agents $\delta$ are defined in Theorem 1. Fig. 3(a) shows that $p_{t}$ first
decreases with time and then fluctuates around a constant, and it decreases
with $\delta$. These findings validate the bound (10). Although the bound (10)
is not tight (e.g., the ratio
$\lambda_{2}/(\lambda_{3}\varepsilon^{2}\delta)\approx 18.7>1$), the
experiment shows that the concentration still occurs for small networks. Next,
we set $l_{d}^{(r)}=(\log^{2.4}n)/n$ for the case of moderate intra-community
influence. Fig. 3(b) illustrates that the probability varies similarly,
validating the bound (11). Now we examine the concentration around average
initial states. Fig. 3(c) shows that the concentration around average initial
states within communities happens with less probability than that around
expected average states shown in Fig. 3(a). Larger networks ensure more
concentration, as shown in Fig. 3(d) with $n=500$. The concentration around
everyone’s average initial state, given in Fig. 3(e), is similar to the
expected state case.

Finally, for concentration around average initial states, we conduct two
experiments to demonstrate how the phase transition occurs when edge weights
vary. In the first simulation, we set
$l_{d}^{(r)}=(\log^{\beta_{2}}n)/n=(\log^{5}n)/n$ and $l^{(s)}=\log n$, and
consider $l_{s}^{(r)}=(\log^{\beta_{1}}n)/n$ with $\beta_{1}=1,\dots,10$. We
run the gossip model for $50$ times, for each value of $\beta_{1}$ and for
$n=60,500,1000,2000$, and compute the difference
$d_{c}=2|\sum_{i\in\mathcal{V}_{r1}}X_{i}(t)-\sum_{i\in\mathcal{V}_{r2}}X_{i}(t)|/(r_{0}n)$
with $t=\lfloor n\log n\rfloor$. The difference $d_{c}$ represents the
difference between the averages of agent states in the two communities. The
case $d_{c}=1$ means local concentration whereas $d_{c}=0$ represents global
concentration. Fig. 4(a) presents the phase transition phenomenon (the effect
becomes stronger as $n$ grows). It shows that the local concentration appears
when $\beta_{1}-\beta_{2}>0$ (i.e., $l_{d}^{(r)}=o(l_{s}^{(r)})$), as
predicted by Corollary 2. On the other hand, Fig. 4(a) indicates that the
global concentration appears when $\beta_{1}-\beta_{2}<0$. In the second
simulation, we set $l_{s}^{(r)}=(\log n)/n$ and
$l_{d}^{(r)}=(\log^{\beta_{2}}n)/n=(\log^{5}n)/n$, and consider
$l^{(s)}=\log^{\beta_{3}}n$ with $\beta_{3}=1,\dots,10$. This simulation
examines the phase transition in the influence of stubborn agents. Under this
circumstance, $d_{c}=2$ means regular agents have states close to stubborn
ones, whereas $d_{c}=0$ represents the global concentration. Fig. 4(b)
illustrates that the transition occurs at $nl_{d}^{(s)}=\Theta(l^{(s)})$
(i.e., $\beta_{3}=\beta_{2}$), as predicted by Corollary 3.

##  5 Conclusion

In this paper, we investigated transient behavior of the gossip model with two
communities. By analyzing the second moment of agent states, we found a phase
transition phenomenon: When edge weights within communities are large and
weights between regular and stubborn agents are small, most agents in the same
community have states close to the average opinion of that community at the
early stage of the process. When the difference between intra- and inter-
community weights is small or the inter-community weights are larger than the
intra-community ones, most agents in the network have states close to
everyone’s average opinion. In contrast, if weights between regular and
stubborn agents are large, the distribution of agent states is close to the
stationary distribution. Future work includes to study the gossip model over
general graphs, to investigate transient behavior of other models, and to link
theoretical findings to empirical data.

## Acknowledgment

This work was supported by the Knut & Alice Wallenberg Foundation and the
Swedish Research Council.

Appendix

##  Appendix A Proof of Lemma 4

PROOF OF (5). We divide the proof of (5) into four steps. Step 1 provides an
upper and a lower bound for $\mathbb{E}\\{\|X^{\eta}(t)\|^{2}\\}$. Bounds of
$\mathbb{E}\\{\|X^{\xi}(t)\|^{2}\\}$ are given in step 2. The lower bounds of
$\mathbb{E}\\{\|X^{\eta}(t)\|^{2}\\}$ and $\mathbb{E}\\{\|X^{\xi}(t)\|^{2}\\}$
are used in step 3, obtaining an upper bound for
$\mathbb{E}\\{\|X^{\Gamma}(t)\|^{2}\\}$. Step 4 puts everything together and
completes the proof.

Step 1 (Upper and lower bounds of $\mathbb{E}\\{\|X^{\eta}(t)\|^{2}\\}$). Note
that

$\displaystyle\mathbb{E}\\{\|X^{\eta}(t+1)\|^{2}|X(t)\\}$
$\displaystyle=\mathbb{E}\\{X(t+1)^{T}\eta\eta^{T}\eta\eta^{T}X(t+1)|X(t)\\}$
$\displaystyle=\mathbb{E}\\{X(t)^{T}Q(t)^{T}\eta\eta^{T}Q(t)X(t)|X(t)\\}+2\mathbb{E}\\{X(t)^{T}Q(t)^{T}$
$\displaystyle~{}\eta\eta^{T}R(t)z^{s}|X(t)\\}+\mathbb{E}\\{(z^{s})^{T}R(t)^{T}\eta\eta^{T}R(t)z^{s}|X(t)\\}$
$\displaystyle=X(t)^{T}\mathbb{E}\\{Q(t)^{T}\eta\eta^{T}Q(t)\\}X(t)+2X(t)^{T}\mathbb{E}\\{Q(t)^{T}\eta\eta^{T}$
$\displaystyle
R(t)\\}z^{s}+(z^{s})^{T}\mathbb{E}\\{R(t)^{T}\eta\eta^{T}R(t)\\}z^{s}.$ (20)

In the last equation, $X(t)$ and $z^{s}$ are taken outside the conditional
expectations because of measurability, and the conditional expectations
degenerate into expectations because $[Q(t),R(t)]$ is independent of $X(t)$.
Let $\mathcal{E}_{r}$ be the collection of edges whose end points are regular
agents, and let $\mathcal{E}_{s}$ be the set of edges connecting regular and
stubborn agents. Hence, $\mathcal{E}=\mathcal{E}_{r}\cup\mathcal{E}_{s}$. From
the definition of $Q(t)$, we have that, at time $t$,
$Q(t)^{T}\eta\eta^{T}Q(t)=\eta\eta^{T}$ when an edge in $\mathcal{E}_{r}$ is
selected, and
$Q(t)^{T}\eta\eta^{T}Q(t)=(\eta-\eta_{u}e_{u}/2)(\eta-\eta_{u}e_{u}/2)^{T}$
when $\\{u,v\\}\in\mathcal{E}_{s}$ is selected. Put it together, we get that

$\displaystyle\mathbb{E}\\{Q(t)\eta\eta^{T}Q(t)\\}$
$\displaystyle=\eta\eta^{T}+\frac{l^{(s)}}{2\alpha}\sum_{u\in\mathcal{V}_{r}}(-\eta_{u}e_{u})\eta^{T}+\frac{l^{(s)}}{2\alpha}\sum_{u\in\mathcal{V}_{r}}\eta(-\eta_{u}e_{u})^{T}$
$\displaystyle+\frac{l^{(s)}}{4\alpha}\sum_{u\in\mathcal{V}_{r}}\eta_{u}^{2}e_{u}e_{u}^{T}$
$\displaystyle=(1-2\lambda_{1})\eta\eta^{T}+\frac{\lambda_{1}}{2r_{0}n}I_{r_{0}n},$

where $e_{i}:=e^{(r_{0}n)}_{i}$. Denote $e^{s}_{i}:=e^{(s_{0}n)}_{i}$,
$\tilde{l}^{(s)}_{v}:=\sum_{u\in\mathcal{V}_{r}}l_{uv}^{(s)}$, and
$\tilde{\eta}:=\sum_{1\leq v\leq
s_{0}n}\tilde{l}_{v}^{(s)}e_{v}^{s}/\sqrt{s_{0}n}$. Then

$\displaystyle\mathbb{E}\\{Q(t)^{T}\eta\eta^{T}R(t)\\}$
$\displaystyle=\sum_{\\{u,v+r_{0}n\\}\in\mathcal{E}_{s}}\Big{(}\eta-\frac{1}{2}\eta_{u}e_{u}\Big{)}\Big{(}\frac{1}{2}\eta_{u}e^{s}_{v}\Big{)}^{T}\frac{l_{uv}^{(s)}}{\alpha}$
$\displaystyle=\sum_{1\leq v\leq
s_{0}n}\sum_{u\in\mathcal{V}_{r}}\Big{(}\frac{l_{uv}^{(s)}}{2\alpha}\eta_{u}\eta(e_{v}^{s})^{T}-\frac{l_{uv}^{(s)}}{4\alpha}\eta_{u}^{2}e_{u}(e_{v}^{s})^{T}\Big{)}$
$\displaystyle=\frac{c_{s}\lambda_{1}}{l^{(s)}}\eta\tilde{\eta}^{T}-\frac{\lambda_{1}}{2r_{0}nl^{(s)}}\tilde{M},$
$\displaystyle\mathbb{E}\\{R(t)^{T}\eta\eta^{T}R(t)\\}$
$\displaystyle=\frac{1}{4}\sum_{1\leq v\leq
s_{0}n}\sum_{u\in\mathcal{V}_{r}}\frac{l_{uv}^{(s)}}{\alpha}\eta_{u}^{2}e^{s}_{v}(e^{s}_{v})^{T}=\frac{\lambda_{1}\tilde{D}^{(s)}}{2r_{0}nl^{(s)}},$

where $\tilde{D}^{(s)}:=\sum_{1\leq v\leq
s_{0}n}\tilde{l}_{v}^{(s)}e^{s}_{v}(e^{s}_{v})^{T}$. Hence, (20) is

$\displaystyle
X(t)^{T}\Big{[}(1-2\lambda_{1})\eta\eta^{T}+\frac{\lambda_{1}}{2r_{0}n}I_{r_{0}n}\Big{]}X(t)+2X(t)^{T}$
$\displaystyle\Big{[}\frac{c_{s}\lambda_{1}}{l^{(s)}}\eta\tilde{\eta}^{T}-\frac{\lambda_{1}}{2r_{0}nl^{(s)}}\tilde{M}\Big{]}z^{s}+(z^{s})^{T}\frac{\lambda_{1}\tilde{D}^{(s)}}{2r_{0}nl^{(s)}}z^{s}$
$\displaystyle=(1-2\lambda_{1})\|X^{\eta}(t)\|^{2}+\frac{\lambda_{1}}{2r_{0}n}\|X(t)\|^{2}+\frac{2c_{s}\lambda_{1}}{l^{(s)}}X(t)^{T}$
$\displaystyle\eta\tilde{\eta}^{T}z^{s}-\frac{\lambda_{1}}{r_{0}nl^{(s)}}X(t)^{T}\tilde{M}z^{s}+\frac{\lambda_{1}}{2r_{0}nl^{(s)}}(z^{s})^{T}\tilde{D}^{(s)}z^{s}.$

Taking expectation yields the following upper and lower bounds for
$\mathbb{E}\\{\|X^{\eta}(t)\|^{2}\\}$ when $n\geq 1/r_{0}$,

$\displaystyle\mathbb{E}\\{\|X^{\eta}(t+1)\|^{2}\\}$
$\displaystyle\leq\Big{(}1-\frac{3}{2}\lambda_{1}\Big{)}\mathbb{E}\\{\|X^{\eta}(t)\|^{2}\\}+\frac{\lambda_{1}}{2r_{0}n}(\mathbb{E}\\{\|X^{\xi}(t)\|^{2}\\}$
$\displaystyle+\mathbb{E}\\{\|X^{\Gamma}(t)\|^{2}\\})+\frac{2c_{s}\lambda_{1}}{l^{(s)}}\mathbb{E}\\{X(t)\\}^{T}\eta\tilde{\eta}^{T}z^{s}$
$\displaystyle-\frac{\lambda_{1}}{r_{0}nl^{(s)}}\mathbb{E}\\{X(t)\\}^{T}\tilde{M}z^{s}+\frac{\lambda_{1}\tilde{l}^{(s)}_{+}}{2r_{0}nl^{(s)}}\|z^{s}\|^{2},$
(21)
$\displaystyle\mathbb{E}\\{\|X^{\eta}(t+1)\|^{2}\\}\geq(1-2\lambda_{1})\mathbb{E}\\{\|X^{\eta}(t)\|^{2}\\}+\frac{2c_{s}\lambda_{1}}{l^{(s)}}$
$\displaystyle\mathbb{E}\\{X(t)\\}^{T}\eta\tilde{\eta}^{T}z^{s}-\frac{\lambda_{1}}{r_{0}nl^{(s)}}\mathbb{E}\\{X(t)\\}^{T}\tilde{M}z^{s}.$
(22)

Furthermore, by induction and from (21), Assumptions 2 and 3, and Lemma 5 at
the end of this section,

$\displaystyle\mathbb{E}\\{\|X^{\eta}(t)\|^{2}\\}\leq(1-\lambda_{1})^{t}\|X^{\eta}(0)\|^{2}+\lambda_{1}\Big{(}\frac{1}{\lambda_{1}}\wedge
t\Big{)}$
$\displaystyle\Big{[}2c_{s}c_{l}(\|X^{\eta}(0)\|+|\zeta_{1}|)\|z^{s}\|+\frac{1}{2r_{0}n}(c_{x}^{2}r_{0}n+\|X(0)\|^{2}$
$\displaystyle+3\|\tilde{z}^{s}\|^{2}+c_{l}\|z^{s}\|^{2})\Big{]},$ (23)

where $\tilde{z}^{s}:=\tilde{M}z^{s}/l^{(s)}$ and
$\zeta_{1}:=\eta^{T}\bar{R}z^{s}/\lambda_{1}=\eta^{T}\tilde{M}z^{s}/l^{(s)}$.

Step 2 (Upper and lower bounds of $\mathbb{E}\\{\|X^{\xi}(t)\|^{2}\\}$). For
$X^{\xi}(t)$, it holds that

$\displaystyle\mathbb{E}\\{\|X^{\xi}(t+1)\|^{2}|X(t)\\}$
$\displaystyle=\mathbb{E}\\{X(t)^{T}Q(t)^{T}\xi\xi^{T}Q(t)X(t)|X(t)\\}+2\mathbb{E}\\{X(t)^{T}Q(t)^{T}$
$\displaystyle\xi\xi^{T}R(t)z^{s}|X(t)\\}+\mathbb{E}\\{(z^{s})^{T}R(t)^{T}\xi\xi^{T}R(t)z^{s}|X(t)\\}$
$\displaystyle=X(t)^{T}\mathbb{E}\\{Q(t)^{T}\xi\xi^{T}Q(t)\\}X(t)+2X(t)^{T}\mathbb{E}\\{Q(t)^{T}\xi\xi^{T}$
$\displaystyle
R(t)\\}z^{s}+(z^{s})^{T}\mathbb{E}\\{R(t)^{T}\xi\xi^{T}R(t)\\}z^{s},$ (24)

where the last equation is obtained in the same way as (20). For
$Q(t)^{T}\xi\xi^{T}$$Q(t)$, we have that

$\displaystyle\mathbb{E}\\{Q(t)^{T}\xi\xi^{T}Q(t)\\}$
$\displaystyle=\underset{\mathcal{C}_{u}=\mathcal{C}_{v}}{\sum_{\\{u,v\\}\in\mathcal{E}_{r}}}\frac{l_{s}^{(r)}}{\alpha}\xi\xi^{T}+\underset{\mathcal{C}_{u}\not=\mathcal{C}_{v}}{\sum_{\\{u,v\\}\in\mathcal{E}_{r}}}\frac{l_{d}^{(r)}}{\alpha}(\xi-\xi_{u}e_{u}-\xi_{v}e_{v})$
$\displaystyle(\xi-\xi_{u}e_{u}-\xi_{v}e_{v})^{T}+\sum_{\\{u,v\\}\in\mathcal{E}_{s}}\frac{l_{u,v-r_{0}n}^{(s)}}{\alpha}\Big{(}\xi-\frac{1}{2}\xi_{u}e_{u}\Big{)}$
$\displaystyle\Big{(}\xi-\frac{1}{2}\xi_{u}e_{u}\Big{)}^{T}$
$\displaystyle=\Big{(}\underset{\mathcal{C}_{u}=\mathcal{C}_{v}}{\sum_{\\{u,v\\}\in\mathcal{E}_{r}}}+\underset{\mathcal{C}_{u}\not=\mathcal{C}_{v}}{\sum_{\\{u,v\\}\in\mathcal{E}_{r}}}+\sum_{\\{u,v\\}\in\mathcal{E}_{s}}\Big{)}\Big{(}\frac{a_{uv}}{\alpha}\xi\xi^{T}\Big{)}+\frac{l_{d}^{(r)}}{\alpha}$
$\displaystyle\underset{\mathcal{C}_{u}\not=\mathcal{C}_{v}}{\sum_{\\{u,v\\}\in\mathcal{E}_{r}}}[-\xi(\xi_{u}e_{u}+\xi_{v}e_{v})^{T}-(\xi_{u}e_{u}+\xi_{v}e_{v})\xi^{T}]+\frac{l_{d}^{(r)}}{\alpha}$
$\displaystyle\underset{\mathcal{C}_{u}\not=\mathcal{C}_{v}}{\sum_{\\{u,v\\}\in\mathcal{E}_{r}}}(\xi_{u}e_{u}+\xi_{v}e_{v})(\xi_{u}e_{u}+\xi_{v}e_{v})^{T}+\sum_{u\in\mathcal{V}_{r}}\sum_{1\leq
v\leq s_{0}n}$ $\displaystyle\frac{l_{uv}^{(s)}}{2\alpha}(-\xi_{u}\xi
e_{u}^{T}-\xi_{u}e_{u}\xi^{T})+\sum_{u\in\mathcal{V}_{r}}\sum_{1\leq v\leq
s_{0}n}\frac{l_{uv}^{(s)}}{4\alpha}\xi_{u}^{2}e_{u}e_{u}^{T}$
$\displaystyle=\xi\xi^{T}-\frac{l_{d}^{(r)}}{\alpha}r_{0}n\xi\xi^{T}+\frac{l_{d}^{(r)}}{\alpha}\underset{\mathcal{C}_{u}\not=\mathcal{C}_{v}}{\sum_{\\{u,v\\}\in\mathcal{E}_{r}}}(\xi_{u}e_{u}+\xi_{v}e_{v})$
$\displaystyle(\xi_{u}e_{u}+\xi_{v}e_{v})^{T}-\frac{l^{(s)}}{\alpha}\xi\xi^{T}+\frac{l^{(s)}}{4\alpha
r_{0}n}I_{r_{0}n}$
$\displaystyle=\Big{(}1-\frac{l_{d}^{(r)}r_{0}n+l^{(s)}}{\alpha}\Big{)}\xi\xi^{T}+\frac{\lambda_{1}}{2r_{0}n}I_{r_{0}n}+\frac{2(\lambda_{2}-\lambda_{1})}{r_{0}n}$
$\displaystyle\underset{\mathcal{C}_{u}\not=\mathcal{C}_{v}}{\sum_{\\{u,v\\}\in\mathcal{E}_{r}}}(\xi_{u}e_{u}+\xi_{v}e_{v})(\xi_{u}e_{u}+\xi_{v}e_{v})^{T}$
$\displaystyle=(1-2\lambda_{2})\xi\xi^{T}+\frac{\lambda_{1}}{2r_{0}n}I_{r_{0}n}+\frac{2(\lambda_{2}-\lambda_{1})}{r_{0}n}\Big{(}\xi\xi^{T}+\frac{1}{2}\Gamma\Big{)},$

where the last equation is obtained from

$\displaystyle\underset{\mathcal{C}_{u}\not=\mathcal{C}_{v}}{\sum_{\\{u,v\\}\in\mathcal{E}_{r}}}(\xi_{u}e_{u}+\xi_{v}e_{v})(\xi_{u}e_{u}+\xi_{v}e_{v})^{T}$
$\displaystyle=\frac{1}{2}I_{r_{0}n}+\sum_{u\in\mathcal{V}_{r1}}\sum_{v\in\mathcal{V}_{r2}}(\xi_{u}\xi_{v}e_{u}e_{v}^{T}+\xi_{u}\xi_{v}e_{v}e_{u}^{T})$
$\displaystyle=\frac{1}{2}I_{r_{0}n}+\frac{1}{2}(\xi\xi^{T}-\eta\eta^{T})=\xi\xi^{T}+\frac{1}{2}\Gamma.$

Recall that $e^{s}_{i}=e^{(s_{0}n)}_{i}$. Similary to Step 1, we have that

$\displaystyle\mathbb{E}\\{Q(t)^{T}\xi\xi^{T}R(t)\\}=\frac{c_{s}\lambda_{1}}{l^{(s)}}\xi\tilde{\xi}^{T}-\frac{\lambda_{1}}{2r_{0}nl^{(s)}}\tilde{M},$

where we denote $\tilde{\xi}:=\frac{1}{\sqrt{s_{0}n}}\sum_{1\leq v\leq
s_{0}n}(\sum_{u\in\mathcal{V}_{r1}}l_{uv}^{(s)}-\sum_{u\in\mathcal{V}_{r2}}l_{uv}^{(s)})e^{s}_{v}$.
In addition,
$\mathbb{E}\\{R(t)^{T}\xi\xi^{T}R(t)\\}=\lambda_{1}\tilde{D}^{(s)}/(2r_{0}nl^{(s)})$.
Therefore,

$\displaystyle\eqref{eq_complete_secondmoment_x_xi1}=(1-2\lambda_{2})\|X^{\xi}(t)\|^{2}+\frac{\lambda_{1}}{2r_{0}n}\|X^{\eta}(t)\|^{2}+\frac{4\lambda_{2}-3\lambda_{1}}{2r_{0}n}$
$\displaystyle\|X^{\xi}(t)\|^{2}+\frac{2\lambda_{2}-\lambda_{1}}{2r_{0}n}\|X^{\Gamma}(t)\|^{2}+\frac{2c_{s}\lambda_{1}}{l^{(s)}}X(t)^{T}\xi\tilde{\xi}^{T}z^{s}$
$\displaystyle-\frac{\lambda_{1}}{r_{0}nl^{(s)}}X(t)^{T}\tilde{M}z^{s}+\frac{\lambda_{1}}{2r_{0}nl^{(s)}}(z^{s})^{T}\tilde{D}^{(s)}z^{s}.$

Hence when $n\geq 4/r_{0}$, the following bounds hold

$\displaystyle\mathbb{E}\\{\|X^{\xi}(t+1)\|^{2}\\}$
$\displaystyle\leq\Big{(}1-\frac{3}{2}\lambda_{2}\Big{)}\mathbb{E}\\{\|X^{\xi}(t)\|^{2}\\}+\frac{\lambda_{1}}{2r_{0}n}\mathbb{E}\\{\|X^{\eta}(t)\|^{2}\\}$
$\displaystyle+\frac{\lambda_{2}}{r_{0}n}\mathbb{E}\\{\|X^{\Gamma}(t)\|^{2}\\}+\frac{2c_{s}\lambda_{1}}{l^{(s)}}\mathbb{E}\\{X(t)\\}^{T}\xi\tilde{\xi}^{T}z^{s}$
$\displaystyle-\frac{\lambda_{1}}{r_{0}nl^{(s)}}\mathbb{E}\\{X(t)\\}^{T}\tilde{M}z^{s}+\frac{\lambda_{1}\tilde{l}^{(s)}_{+}}{2r_{0}nl^{(s)}}\|z^{s}\|^{2},$
(25)
$\displaystyle\mathbb{E}\\{\|X^{\xi}(t+1)\|^{2}\\}\geq(1-2\lambda_{2})\mathbb{E}\\{\|X^{\xi}(t)\|^{2}\\}+\frac{2c_{s}\lambda_{1}}{l^{(s)}}$
$\displaystyle\mathbb{E}\\{X(t)\\}^{T}\xi\tilde{\xi}^{T}z^{s}-\frac{\lambda_{1}}{r_{0}nl^{(s)}}\mathbb{E}\\{X(t)\\}^{T}\tilde{M}z^{s}.$
(26)

Furthermore, by induction and from (25), Assumptions 2 and 3, and Lemma 5 at
the end of this section,

$\displaystyle\mathbb{E}\\{\|X^{\xi}(t)\|^{2}\\}\leq(1-\lambda_{2})^{t}\|X^{\xi}(0)\|^{2}+\lambda_{1}\Big{(}\frac{1}{\lambda_{2}}\wedge
t\Big{)}$
$\displaystyle\Big{[}2c_{s}c_{l}(\|X^{\xi}(0)\|+|\zeta_{2}|)\|z^{s}\|+\frac{1}{2r_{0}n}(c_{x}^{2}r_{0}n+\|X(0)\|^{2}$
$\displaystyle+3\|\tilde{z}^{s}\|^{2}+c_{l}\|z^{s}\|^{2})\Big{]}+\lambda_{2}\Big{(}\frac{1}{\lambda_{2}}\wedge
t\Big{)}c_{x}^{2},$ (27)

where
$\zeta_{2}:=\xi^{T}\bar{R}z^{s}/\lambda_{1}=\xi^{T}\tilde{M}z^{s}/l^{(s)}$.

Step 3 (Upper bound of $\mathbb{E}\\{\|X^{\Gamma}(t)\|^{2}\\}$). Expanding
$X(t+1)$ yields that

$\displaystyle\mathbb{E}\\{\|X(t+1)\|^{2}|X(t)\\}$
$\displaystyle=X(t)^{T}\mathbb{E}\\{Q(t)^{T}Q(t)\\}X(t)+2X(t)^{T}\mathbb{E}\\{Q(t)^{T}R(t)\\}z^{s}$
$\displaystyle+z^{s}\mathbb{E}\\{R(t)^{T}R(t)\\}z^{s}.$ (28)

Note that

$\displaystyle\mathbb{E}\\{Q(t)^{T}Q(t)\\}$
$\displaystyle=\sum_{\\{u,v\\}\in\mathcal{E}_{r}}\Big{[}I-\frac{1}{2}(e_{u}-e_{v})(e_{u}-e_{v})^{T}\Big{]}\frac{a_{uv}}{\alpha}$
$\displaystyle+\sum_{\\{u,v\\}\in\mathcal{E}_{s}}\Big{(}I-\frac{3}{4}e_{u}e_{u}^{T}\Big{)}\frac{a_{uv}}{\alpha}$
$\displaystyle=\bar{Q}-\frac{\lambda_{1}}{2}I_{r_{0}n}$
$\displaystyle=\Big{(}1-\frac{3}{2}\lambda_{1}\Big{)}\eta\eta^{T}+\Big{(}1-\lambda_{2}-\frac{1}{2}\lambda_{1}\Big{)}\xi\xi^{T}$
$\displaystyle+\Big{(}1-\lambda_{3}-\frac{1}{2}\lambda_{1}\Big{)}\Gamma,$
$\displaystyle\mathbb{E}\\{Q(t)^{T}R(t)\\}$ $\displaystyle=\sum_{1\leq v\leq
s_{0}n}\sum_{u\in\mathcal{V}_{r}}\Big{(}I-\frac{1}{2}e_{u}e_{u}^{T}\Big{)}\Big{(}\frac{1}{2}e_{u}(e^{s}_{v})^{T}\Big{)}\frac{l_{uv}^{(s)}}{\alpha}=\frac{\lambda_{1}\tilde{M}}{2l^{(s)}},$
$\displaystyle\mathbb{E}\\{R(t)^{T}R(t)\\}$
$\displaystyle=\frac{1}{4\alpha}\sum_{1\leq v\leq
s_{0}n}\sum_{u\in\mathcal{V}_{r}}e^{s}_{v}(e^{s}_{v})^{T}l_{uv}^{(s)}=\frac{\lambda_{1}\tilde{D}^{(s)}}{2l^{(s)}}.$

Thus,

$\displaystyle\eqref{eq_complete_secondmoment_x_gamma1}=\Big{(}1-\frac{3}{2}\lambda_{1}\Big{)}\|X^{\eta}(t)\|^{2}+\Big{(}1-\lambda_{2}-\frac{1}{2}\lambda_{1}\Big{)}$
$\displaystyle\|X^{\xi}(t)\|^{2}+\Big{(}1-\lambda_{3}-\frac{1}{2}\lambda_{1}\Big{)}\|X^{\Gamma}(t)\|^{2}+\frac{\lambda_{1}}{l^{(s)}}X(t)^{T}\tilde{M}z^{s}$
$\displaystyle+\frac{\lambda_{1}}{2l^{(s)}}(z^{s})^{T}\tilde{D}^{(s)}z^{s}.$
(29)

It follows from the preceding equation, Lemma 1 (ii), (22) and (26) that

$\displaystyle\mathbb{E}\\{\|X^{\Gamma}(t+1)\|^{2}\\}$
$\displaystyle\leq\lambda_{1}\mathbb{E}\\{\|X^{\eta}(t)\|^{2}\\}+\lambda_{2}\mathbb{E}\\{\|X^{\xi}(t)\|^{2}\\}+(1-\lambda_{3})$
$\displaystyle~{}\mathbb{E}\\{\|X^{\Gamma}(t)\|^{2}\\}+\Big{(}1+\frac{2}{r_{0}n}\Big{)}\frac{\lambda_{1}}{l^{(s)}}\mathbb{E}\\{X(t)\\}^{T}\tilde{M}z^{s}+\frac{\lambda_{1}\tilde{l}^{(s)}_{+}}{2l^{(s)}}$
$\displaystyle\|z^{s}\|^{2}-\frac{2c_{s}\lambda_{1}}{l^{(s)}}(\mathbb{E}\\{X(t)\\}^{T}\eta\tilde{\eta}^{T}z^{s}+\mathbb{E}\\{X(t)\\}^{T}\xi\tilde{\xi}^{T}z^{s}).$

From Lemma 5, Assumptions 2 and 3, and (27) and by induction, we know that

$\displaystyle\mathbb{E}\\{\|X^{\Gamma}(t)\|^{2}\\}$
$\displaystyle\leq\lambda_{2}\mathbb{E}\\{\|X^{\xi}(t-1)\|^{2}\\}+(1-\lambda_{3})\mathbb{E}\\{\|X^{\Gamma}(t-1)\|^{2}\\}$
$\displaystyle+\lambda_{1}c_{x}^{2}r_{0}n+\Big{(}1+\frac{2}{r_{0}n}\Big{)}\frac{\lambda_{1}}{2}(\|X(0)\|^{2}+3\|\tilde{z}^{s}\|^{2})+\frac{c_{l}\lambda_{1}}{2}$
$\displaystyle\|z^{s}\|^{2}+2c_{s}c_{l}\lambda_{1}\|z^{s}\|(\|X^{\eta}(0)\|+\|X^{\xi}(0)\|+|\zeta_{1}|+|\zeta_{2}|)$
$\displaystyle\leq(1-\lambda_{3})^{t}\|X^{\Gamma}(0)\|^{2}+\lambda_{1}\Big{(}\frac{1}{\lambda_{3}}\wedge
t\Big{)}\Big{[}\Big{(}1+\frac{1}{2r_{0}n}\Big{)}c_{x}^{2}r_{0}n$
$\displaystyle+\frac{1}{2}\Big{(}1+\frac{3}{r_{0}n}\Big{)}(\|X(0)\|^{2}+3\|\tilde{z}^{s}\|^{2})+\Big{(}1+\frac{1}{r_{0}n}\Big{)}\frac{c_{l}}{2}$
$\displaystyle~{}\|z^{s}\|^{2}+2c_{s}c_{l}\|z^{s}\|(\|X^{\eta}(0)\|+2\|X^{\xi}(0)\|+|\zeta_{1}|+2|\zeta_{2}|)\Big{]}$
$\displaystyle+\lambda_{2}\Big{(}\frac{1}{\lambda_{3}}\wedge
t\Big{)}[(1-\lambda_{2})^{t}\|X^{\xi}(0)\|^{2}+c_{x}^{2}].$ (30)

Step 4 (Putting everything together). Lemma 1 (ii) yields that

$\displaystyle\mathbb{E}\\{\|X(t)\|^{2}\\}$
$\displaystyle=\mathbb{E}\\{\|X^{\eta}(t)\|^{2}\\}+\mathbb{E}\\{\|X^{\xi}(t)\|^{2}\\}+\mathbb{E}\\{\|X^{\Gamma}(t)\|^{2}\\}$

So the bound (5) follows from summarizing (23), (27), and (30) and using the
fact $1/\lambda_{1}\geq 1/\lambda_{k}$, $k=2,3$.

PROOF OF (6). The derivation of the upper bound (6) is similar to the proof of
(5). Decompose $X(t)=X^{\eta}(t)+X^{\bot}(t)$. In step 1 of (i), we have
obtained an upper bound and a lower bound for
$\mathbb{E}\\{\|X^{\eta}(t)\|^{2}\\}$, so it suffices to obtain an upper bound
for $\mathbb{E}\\{\|X^{\bot}(t)\|^{2}\\}$. Note that, from (22) and (29)

$\displaystyle\mathbb{E}\\{\|X^{\bot}(t+1)\|^{2}\\}$
$\displaystyle\leq\bigg{(}1-\frac{3}{2}\lambda_{1}\bigg{)}\mathbb{E}\\{\|X^{\eta}(t)\|^{2}\\}+\bigg{(}1-\lambda_{2}\wedge\lambda_{3}-\frac{1}{2}\lambda_{1}\bigg{)}$
$\displaystyle~{}\mathbb{E}\\{\|X^{\bot}(t)\|^{2}\\}+\frac{\lambda_{1}}{l^{(s)}}\mathbb{E}\\{X(t)\\}^{T}\tilde{M}z^{s}+\frac{\lambda_{1}}{2l^{(s)}}(z^{s})^{T}\tilde{D}^{(s)}z^{s}$
$\displaystyle-\mathbb{E}\\{\|X^{\eta}(t+1)\|^{2}\\}$
$\displaystyle\leq(1-\lambda_{2}\wedge\lambda_{3})\mathbb{E}\\{\|X^{\bot}(t)\|^{2}\\}+\lambda_{1}c_{x}^{2}r_{0}n\Big{(}3+\frac{c_{l}}{2}$
$\displaystyle+4c_{s}c_{l}+\frac{2}{r_{0}n}\Big{)}$
$\displaystyle\leq(1-\lambda_{2}\wedge\lambda_{3})^{t}\|X^{\bot}(0)\|^{2}+\lambda_{1}\Big{(}\frac{1}{\lambda_{2}\wedge\lambda_{3}}\wedge
t\Big{)}c_{x}^{2}r_{0}n$
$\displaystyle~{}\Big{(}3+\frac{c_{l}}{2}+4c_{s}c_{l}+\frac{2}{r_{0}n}\Big{)}.$
(31)

Therefore, the bound (6) follows from combining the preceding bound and (23).
$\Box$

######  Lemma 5.

Under the conditions of Lemma 4, the following bounds hold,

$\displaystyle|\mathbb{E}\\{X(t)\\}^{T}\eta\tilde{\eta}^{T}z^{s}|$
$\displaystyle\leq\tilde{l}_{+}^{(s)}(\|X^{\eta}(0)\|+|\zeta_{1}|)\|z^{s}\|,$
$\displaystyle|\mathbb{E}\\{X(t)\\}^{T}\xi\tilde{\xi}^{T}z^{s}|$
$\displaystyle\leq\tilde{l}^{(s)}_{-}(\|X^{\xi}(0)\|+|\zeta_{2}|)\|z^{s}\|,$
$\displaystyle\Big{|}\frac{\mathbb{E}\\{X(t)\\}^{T}\tilde{M}z^{s}}{l^{(s)}}\Big{|}$
$\displaystyle\leq\frac{1}{2}(\|X(0)\|^{2}+3\|\tilde{z}^{s}\|^{2}).$

It follows from Lemma 3 that, for all $t\in\mathbb{N}$,

$\displaystyle|\mathbb{E}\\{X(t)\\}^{T}\eta\tilde{\eta}^{T}z^{s}|$
$\displaystyle=\Big{|}\Big{\\{}(1-\lambda_{1})^{t}\eta^{T}X(0)+\frac{1}{\lambda_{1}}[1-(1-\lambda_{1})^{t}]\eta^{T}\bar{R}z^{s}\Big{\\}}\tilde{\eta}^{T}z^{s}\Big{|}$
$\displaystyle\leq(1-\lambda_{1})^{t}|\eta^{T}X(0)\tilde{\eta}^{T}z^{s}|+[1-(1-\lambda_{1})^{t}]$
$\displaystyle\Big{|}\eta^{T}\frac{\bar{R}}{\lambda_{1}}z^{s}\tilde{\eta}^{T}z^{s}\Big{|}$
$\displaystyle\leq|\eta^{T}X(0)\tilde{\eta}^{T}z^{s}|+\Big{|}\eta^{T}\frac{\bar{R}}{\lambda_{1}}z^{s}\tilde{\eta}^{T}z^{s}\Big{|}$
$\displaystyle\leq\tilde{l}_{+}^{(s)}(\|X^{\eta}(0)\|+|\zeta_{1}|)\|z^{s}\|,$
$\displaystyle|\mathbb{E}\\{X(t)\\}^{T}\xi\tilde{\xi}^{T}z^{s}|$
$\displaystyle=\Big{|}\Big{\\{}(1-\lambda_{2})^{t}\xi^{T}X(0)+\frac{1}{\lambda_{2}}[1-(1-\lambda_{2})^{t}]\xi^{T}\bar{R}z^{s}\Big{\\}}\tilde{\xi}^{T}z^{s}\Big{|}$
$\displaystyle\leq(\|X^{\xi}(0)\|+|\zeta_{2}|)\|\tilde{\xi}\|\|z^{s}\|$
$\displaystyle\leq\tilde{l}^{(s)}_{-}(\|X^{\xi}(0)\|+|\zeta_{2}|)\|z^{s}\|.$

Again from Lemma 3, it holds that

$\displaystyle\Big{|}\frac{1}{l^{(s)}}(\mathbb{E}\\{X(t)\\})^{T}\tilde{M}z^{s}\Big{|}$
$\displaystyle=\Big{|}(1-\lambda_{1})^{t}\eta^{T}X(0)\eta^{T}\frac{\tilde{M}}{l^{(s)}}z^{s}+[1-(1-\lambda_{1})^{t}]\eta^{T}\frac{\bar{R}}{\lambda_{1}}z^{s}$
$\displaystyle~{}\eta^{T}\frac{\tilde{M}}{l^{(s)}}z^{s}+(1-\lambda_{2})^{t}\xi^{T}X(0)\xi^{T}\frac{\tilde{M}}{l^{(s)}}z^{s}+\frac{\lambda_{1}}{\lambda_{2}}[1-(1$
$\displaystyle-\lambda_{2})^{t}]\xi^{T}\frac{\bar{R}}{\lambda_{1}}z^{s}\xi^{T}\frac{\tilde{M}}{l^{(s)}}z^{s}+(1-\lambda_{3})^{t}\sum_{i=3}^{r_{0}n}(w^{(i)})^{T}X(0)$
$\displaystyle(w^{(i)})^{T}\frac{\tilde{M}}{l^{(s)}}z^{s}+\frac{\lambda_{1}}{\lambda_{3}}[1-(1-\lambda_{3})^{t}]\sum_{i=3}^{r_{0}n}(w^{(i)})^{T}\frac{\bar{R}}{\lambda_{1}}z^{s}$
$\displaystyle(w^{(i)})^{T}\frac{\tilde{M}}{l^{(s)}}z^{s}\Big{|}$
$\displaystyle\leq\Big{|}\eta^{T}X(0)\eta^{T}\frac{\tilde{M}}{l^{(s)}}z^{s}\Big{|}+\Big{|}\eta^{T}\frac{\bar{R}}{\lambda_{1}}z^{s}\eta^{T}\frac{\tilde{M}}{l^{(s)}}z^{s}\Big{|}+\Big{|}\xi^{T}X(0)\xi^{T}$
$\displaystyle~{}\frac{\tilde{M}}{l^{(s)}}z^{s}\Big{|}+\Big{|}\xi^{T}\frac{\bar{R}}{\lambda_{1}}z^{s}\xi^{T}\frac{\tilde{M}}{l^{(s)}}z^{s}\Big{|}+\Big{|}\sum_{i=3}^{r_{0}n}(w^{(i)})^{T}X(0)(w^{(i)})^{T}$
$\displaystyle~{}\frac{\tilde{M}}{l^{(s)}}z^{s}\Big{|}+\Big{|}\sum_{i=3}^{r_{0}n}(w^{(i)})^{T}\frac{\bar{R}}{\lambda_{1}}z^{s}(w^{(i)})^{T}\frac{\tilde{M}}{l^{(s)}}z^{s}\Big{|}$
$\displaystyle\leq(\|X^{\eta}(0)\|~{}|\zeta_{1}|+|\zeta_{1}|^{2}+\|X^{\xi}(0)\|~{}|\zeta_{2}|+|\zeta_{2}|^{2}$
$\displaystyle+\|X^{\Gamma}(0)\|~{}|\zeta_{3}|+|\zeta_{3}|^{2})$ (32)
$\displaystyle\leq\frac{1}{2}[\|X^{\eta}(0)\|^{2}+\|X^{\xi}(0)\|^{2}+\|X^{\Gamma}(0)\|^{2}+3(|\zeta_{1}|^{2}$
$\displaystyle+|\zeta_{2}|^{2}+|\zeta_{3}|^{2})]$ (from $2ab\leq a^{2}+b^{2}$,
$\forall a,b\in\mathbb{R}$)
$\displaystyle=\frac{1}{2}(\|X(0)\|^{2}+3\|\tilde{z}^{s}\|^{2}).$

Here, the last equation follows from Lemma 1 (ii), and (32) is obtained from
the following fact,

$\displaystyle\Big{|}\sum_{i=3}^{r_{0}n}(w^{(i)})^{T}X(0)(w^{(i)})^{T}\frac{\tilde{M}}{l^{(s)}}z^{s}\Big{|}$
$\displaystyle\leq\Big{(}\sum_{i=3}^{r_{0}n}((w^{(i)})^{T}X(0))^{2}\Big{)}^{\frac{1}{2}}\Big{(}\sum_{i=3}^{r_{0}n}\Big{(}(w^{(i)})^{T}\frac{\tilde{M}}{l^{(s)}}z^{s}\Big{)}^{2}\Big{)}^{\frac{1}{2}}$
$\displaystyle=\Big{\|}\sum_{i=3}^{r_{0}n}w^{(i)}(w^{(i)})^{T}X(0)\Big{\|}~{}\Big{\|}\sum_{i=3}^{r_{0}n}w^{(i)}(w^{(i)})^{T}\frac{\tilde{M}}{l^{(s)}}z^{s}\Big{\|}$
$\displaystyle=\|X^{\Gamma}(0)\|~{}|\zeta_{3}|,$

where the first inequality follows from the Cauchy-Schwarz inequality, and the
first equation is from the orthogonality of $w^{(i)}$, $3\leq i\leq r_{0}n$.
$\Box$

##  Appendix B Proof of Theorem 3

In this section, we denote the maximum-column-sum, spectral, and maximum-row-
sum norm by $\|\cdot\|_{1}$, $\|\cdot\|$, and $\|\cdot\|_{\infty}$,
respectively. Let $\\{[Q^{\prime}(t)~{}U^{\prime}(t)],t\in\mathbb{N}\\}$ be an
i.i.d. sequence having the same distribution as and independent of the
original sequence $\\{[Q(t)~{}U(t)],t\in\mathbb{N}\\}$, where
$U(t):=R(t)z^{s}$. Denote $\Phi_{Q^{\prime}}(s,t)=Q^{\prime}(t)\cdots
Q^{\prime}(s)$, $\overleftarrow{\Phi}_{Q^{\prime}}(s,t)=Q^{\prime}(s)\cdots
Q^{\prime}(t)$, and
$\Phi_{Q^{\prime}}(t+1,t)=\overleftarrow{\Phi}_{Q^{\prime}}(t+1,t)=I$, for all
$t\geq s\geq 0$. Define

$\displaystyle\tilde{X}(t)$
$\displaystyle:=\Phi_{Q^{\prime}}(0,t)X(0)+\sum_{i=0}^{t}\Phi_{Q^{\prime}}(t+1-i,t)U^{\prime}(t-i),$
$\displaystyle\tilde{X}^{*}(t)$
$\displaystyle:=\sum_{i=0}^{t}\Phi_{Q^{\prime}}(t+1-i,t)U^{\prime}(t-i)+\Phi_{Q^{\prime}}(0,t)$
$\displaystyle~{}\sum_{i=t+1}^{\infty}\overleftarrow{\Phi}_{Q^{\prime}}(t+1,i-1)U^{\prime}(i),$

so $\tilde{X}(t)$ and $\tilde{X}^{*}(t)$ have the same distribution as $X(t)$
and $\pi$ respectively (the latter correspondence is because $\pi$ has the
same distribution as $\sum_{i=0}^{\infty}\overleftarrow{\Phi}_{Q}(0,i-1)U(i)$
from [6, 39]). Hence, the following observation yields the conclusion.

$\displaystyle~{}d_{W}(X(t),\pi)\leq\mathbb{E}\\{\|\tilde{X}(t)-\tilde{X}^{*}(t)\|\\}$
$\displaystyle=\mathbb{E}\Big{\\{}\Big{\|}\Phi_{Q^{\prime}}(0,t)X(0)-\Phi_{Q^{\prime}}(0,t)\sum_{i=t+1}^{\infty}\overleftarrow{\Phi}_{Q^{\prime}}(t+1,i-1)$
$\displaystyle~{}U^{\prime}(i)\Big{\|}\Big{\\}}$ $\displaystyle\leq
c_{x}\sqrt{r_{0}n}\mathbb{E}\\{\|\Phi_{Q^{\prime}}(0,t)\|\\}+\frac{1}{2}c_{x}\sum_{i=t+1}^{\infty}\mathbb{E}\\{\|\Phi_{Q^{\prime}}(0,t)$
$\displaystyle~{}\overleftarrow{\Phi}_{Q^{\prime}}(t+1,i-1)\|\\}$
$\displaystyle\leq\frac{1}{2}c_{x}r_{0}n\Big{(}2\mathbb{E}\\{\|\Phi_{Q^{\prime}}(0,t)\|_{1}\\}+\sum_{i=t+1}^{\infty}\mathbb{E}\\{\|\Phi_{Q^{\prime}}(0,t)$
$\displaystyle~{}\overleftarrow{\Phi}_{Q^{\prime}}(t+1,i-1)\|_{1}\\}\Big{)}$
$\displaystyle\leq
c_{x}{\color[rgb]{0,0,0}(r_{0}n)^{\frac{5}{2}}}\Big{(}1+\frac{1}{2\lambda_{1}}\Big{)}(1-\lambda_{1})^{t+1},$

where the first inequality follows from the definition of the Wasserstein
metric, the second inequality from Assumption 2, and the last inequality is
obtained by noticing the following fact

$\displaystyle\mathbb{E}\\{\|\overleftarrow{\Phi}_{Q}(0,t)\|_{1}\\}\leq\sum_{1\leq
j\leq r_{0}n}\sum_{1\leq i\leq
r_{0}n}\mathbb{E}\\{|[\overleftarrow{\Phi}_{Q}(0,t)]_{ij}|\\}$
$\displaystyle\leq
r_{0}n\|\mathbb{E}\\{\overleftarrow{\Phi}_{Q}(0,t)\\}\|_{\infty}=r_{0}n\|\bar{Q}^{t+1}\|_{\infty}$
$\displaystyle\leq{\color[rgb]{0,0,0}(r_{0}n)^{\frac{3}{2}}}(1-\lambda_{1})^{t+1}.$

##  Appendix C Proof of Theorem 2

We first bound the probability
$\mathbb{P}\\{|\mathcal{S}(X(t),X^{\eta}(0)+X^{\xi}(0),\varepsilon)|\geq\delta
r_{0}n\\}$. From Lemma 3 and the Bernoulli inequality we have that

$\displaystyle\mathbb{E}\\{\|X(t)-(X^{\eta}(0)+X^{\xi}(0))\|^{2}\\}$
$\displaystyle=\mathbb{E}\\{\|X(t)\|^{2}\\}+\|X^{\eta}(0)+X^{\xi}(0)\|^{2}-2\mathbb{E}\\{X(t)\\}^{T}$
$\displaystyle~{}(X^{\eta}(0)+X^{\xi}(0))$
$\displaystyle=\mathbb{E}\\{\|X(t)\|^{2}\\}+\|X^{\eta}(0)\|^{2}+\|X^{\xi}(0)\|^{2}-2(1-\lambda_{1})^{t}$
$\displaystyle~{}\|X^{\eta}(0)\|^{2}-[1-(1-\lambda_{1})^{t}]\zeta_{1}\eta^{T}X(0)-2(1-\lambda_{2})^{t}$
$\displaystyle~{}\|X^{\xi}(0)\|^{2}-\frac{\lambda_{1}}{\lambda_{2}}[1-(1-\lambda_{2})^{t}]\zeta_{2}\xi^{T}X(0)$
$\displaystyle\leq\mathbb{E}\\{\|X(t)\|^{2}\\}+[1-2(1-\lambda_{1})^{t}]\|X^{\eta}(0)\|^{2}$
$\displaystyle+[1-2(1-\lambda_{2})^{t}]\|X^{\xi}(0)\|^{2}+2\lambda_{1}t|\zeta_{1}|\|X^{\eta}(0)\|$
$\displaystyle+2\lambda_{1}t|\zeta_{2}|\|X^{\xi}(0)\|$
$\displaystyle\leq\mathbb{E}\\{\|X(t)\|^{2}\\}+[1-2(1-\lambda_{1})^{t}]\|X^{\eta}(0)\|^{2}$
$\displaystyle+[1-2(1-\lambda_{2})^{t}]\|X^{\xi}(0)\|^{2}+2\lambda_{1}tc_{x}^{2}r_{0}n$
$\displaystyle\leq(1-\lambda_{3})^{t}\|X^{\Gamma}(0)\|^{2}+\lambda_{1}tc_{x}^{2}r_{0}n\Big{(}6+\frac{c_{l}}{2}+16c_{s}c_{l}$
$\displaystyle+\frac{3c_{l}+23}{2r_{0}n}\Big{)}+\Big{(}\frac{\lambda_{2}}{\lambda_{3}}+\lambda_{2}t\Big{)}(\|X^{\xi}(0)\|^{2}+c_{x}^{2}),$

where the last inequality follows from (5) with $1/\lambda_{3}\leq t\leq
1/\lambda_{2}$. Hence from (9),

$\displaystyle\mathbb{P}\\{|\mathcal{S}(X(t),X^{\eta}(0)+X^{\xi}(0),\varepsilon)|\geq\delta
r_{0}n\\}$
$\displaystyle\leq\frac{1}{\varepsilon^{2}\delta}\Big{[}(1-\lambda_{3})^{t}\frac{\|X^{\Gamma}(0)\|^{2}}{c_{x}^{2}r_{0}n}+\lambda_{1}t\Big{(}6+\frac{c_{l}}{2}+16c_{s}c_{l}$
$\displaystyle+\frac{3c_{l}+23}{2r_{0}n}\Big{)}+\Big{(}\frac{\lambda_{2}}{\lambda_{3}}+\lambda_{2}t\Big{)}\Big{(}\frac{\|X^{\xi}(0)\|^{2}}{c_{x}^{2}r_{0}n}+\frac{1}{r_{0}n}\Big{)}\Big{]}$
$\displaystyle\leq\frac{1}{\varepsilon^{2}\delta}\Big{[}(1-\lambda_{3})^{t}+C_{11}\lambda_{1}t+C_{12}\Big{(}\frac{\lambda_{2}}{\lambda_{3}}+\lambda_{2}t\Big{)}\Big{]}.$

When $t\geq\underline{t}_{1}\geq 1/\lambda_{3}$, $(1-\lambda_{3})^{t}\leq
e^{t\log(1-\lambda_{3})}\leq e^{-\lambda_{3}t}\leq
e^{-\lambda_{3}\underline{t}_{1}}\leq\varepsilon^{2}\delta\gamma/2$. On the
other hand, when $t\leq\overline{t}_{1}$,

$\displaystyle
C_{11}\lambda_{1}t+C_{12}\Big{(}\frac{\lambda_{2}}{\lambda_{3}}+\lambda_{2}t\Big{)}\leq\frac{\varepsilon^{2}\delta\gamma}{2}.$

If the assumptions of (i) hold, then
$(\underline{t}_{1},\overline{t}_{1})\not=\emptyset$. The first part of the
theorem thus follows. The second part of the theorem can be obtained from the
similar argument.

## References

  * [1] A. V. Proskurnikov and R. Tempo, “A tutorial on modeling and analysis of dynamic social networks. Part II,” Annual Reviews in Control, vol. 45, pp. 166–190, 2018.
  * [2] S. Fortunato and D. Hric, “Community detection in networks: A user guide,” Physics Reports, vol. 659, pp. 1–44, 2016.
  * [3] M. Conover, J. Ratkiewicz, M. Francisco, B. Gonçalves, F. Menczer, and A. Flammini, “Political polarization on twitter,” in Proceedings of the International AAAI Conference on Web and Social Media, vol. 5, pp. 89–96, 2011.
  * [4] W. Cota, S. C. Ferreira, R. Pastor-Satorras, and M. Starnini, “Quantifying echo chamber effects in information spreading over political communication networks,” EPJ Data Science, vol. 8, no. 1, pp. 1–13, 2019.
  * [5] M. T. Schaub, S. Segarra, and J. N. Tsitsiklis, “Blind identification of stochastic block models from dynamical observations,” SIAM Journal on Mathematics of Data Science, vol. 2, no. 2, pp. 335–367, 2020.
  * [6] Y. Xing, X. He, H. Fang, and K. H. Johansson, “Community structure recovery and interaction probability estimation for gossip opinion dynamics,” arXiv preprint arXiv:2102.09683, 2021.
  * [7] X. Cheng, Y. Kawano, and J. M. Scherpen, “Model reduction of multiagent systems using dissimilarity-based clustering,” IEEE Transactions on Automatic Control, vol. 64, no. 4, pp. 1663–1670, 2018.
  * [8] C. Castellano, S. Fortunato, and V. Loreto, “Statistical physics of social dynamics,” Reviews of Modern Physics, vol. 81, no. 2, p. 591, 2009.
  * [9] A. Flache, M. Mäs, T. Feliciani, E. Chattoe-Brown, G. Deffuant, S. Huet, and J. Lorenz, “Models of social influence: Towards the next frontiers,” Journal of Artificial Societies and Social Simulation, vol. 20, no. 4, 2017\.
  * [10] A. De, S. Bhattacharya, P. Bhattacharya, N. Ganguly, and S. Chakrabarti, “Learning linear influence models in social networks from transient opinion dynamics,” ACM Transactions on the Web, vol. 13, no. 3, pp. 1–33, 2019\.
  * [11] N. E. Friedkin, A. V. Proskurnikov, and F. Bullo, “Group dynamics on multidimensional object threat appraisals,” Social Networks, vol. 65, pp. 157–167, 2021.
  * [12] I. V. Kozitsin, “Opinion dynamics of online social network users: A micro-level analysis,” The Journal of Mathematical Sociology, vol. 47, no. 1, pp. 1–41, 2023.
  * [13] M. H. DeGroot, “Reaching a consensus,” Journal of the American Statistical Association, vol. 69, no. 345, pp. 118–121, 1974.
  * [14] N. E. Friedkin and E. C. Johnsen, “Social influence and opinions,” Journal of Mathematical Sociology, vol. 15, no. 3-4, pp. 193–206, 1990.
  * [15] R. Hegselmann and U. Krause, “Opinion dynamics and bounded confidence models, analysis, and simulation,” Journal of Artificial Societies and Social Simulation, vol. 5, no. 3, 2002.
  * [16] G. Deffuant, D. Neau, F. Amblard, and G. Weisbuch, “Mixing beliefs among interacting agents,” Advances in Complex Systems, vol. 3, no. 01n04, pp. 87–98, 2000.
  * [17] G. Shi, C. Altafini, and J. S. Baras, “Dynamics over signed networks,” SIAM Review, vol. 61, no. 2, pp. 229–257, 2019.
  * [18] R. P. Abelson, “Mathematical models of the distribution of attitudes under controversy,” Contributions to Mathematical Psychology, 1964.
  * [19] S. Banisch, R. Lima, and T. Araújo, “Agent based models and opinion dynamics as Markov chains,” Social Networks, vol. 34, no. 4, pp. 549–561, 2012.
  * [20] G. Chowell, L. Sattenspiel, S. Bansal, and C. Viboud, “Mathematical models to characterize early epidemic growth: A review,” Physics of Life Reviews, vol. 18, pp. 66–97, 2016.
  * [21] H. Noorazar, K. R. Vixie, A. Talebanpour, and Y. Hu, “From classical to modern opinion dynamics,” International Journal of Modern Physics C, vol. 31, no. 07, p. 2050101, 2020.
  * [22] S. Banisch and T. Araújo, “On the empirical relevance of the transient in opinion models,” Physics Letters A, vol. 374, no. 31-32, pp. 3197–3200, 2010.
  * [23] S. J. Hill, J. Lo, L. Vavreck, and J. Zaller, “How quickly we forget: The duration of persuasion effects from mass communication,” Political Communication, vol. 30, no. 4, pp. 521–547, 2013.
  * [24] J. Lorenz, “Consensus strikes back in the Hegselmann-Krause model of continuous opinion dynamics under bounded confidence,” Journal of Artificial Societies and Social Simulation, vol. 9, no. 1, 2006.
  * [25] P. Barbillon, M. Thomas, I. Goldringer, F. Hospital, and S. Robin, “Network impact on persistence in a finite population dynamic diffusion model: Application to an emergent seed exchange network,” Journal of Theoretical Biology, vol. 365, pp. 365–376, 2015.
  * [26] F. Dietrich, S. Martin, and M. Jungers, “Transient cluster formation in generalized Hegselmann-Krause opinion dynamics,” in European Control Conference, pp. 531–536, 2016.
  * [27] F. Xiong, Y. Liu, and J. Cheng, “Modeling and predicting opinion formation with trust propagation in online social networks,” Communications in Nonlinear Science and Numerical Simulation, vol. 44, pp. 513–524, 2017.
  * [28] S. S. Shree, C. Avhishek, and J. Krishna, “Finite time bounds for stochastic bounded confidence dynamics,” arXiv preprint arXiv:2212.13387, 2022.
  * [29] L. Festinger, “The analysis of sociograms using matrix algebra,” Human Relations, vol. 2, no. 2, pp. 153–158, 1949.
  * [30] M. E. Newman and M. Girvan, “Finding and evaluating community structure in networks,” Physical Review E, vol. 69, no. 2, p. 026113, 2004.
  * [31] E. Abbe, “Community detection and stochastic block models: Recent developments,” The Journal of Machine Learning Research, vol. 18, no. 1, pp. 6446–6531, 2017.
  * [32] F. Gargiulo and S. Huet, “Opinion dynamics in a group-based society,” Europhysics Letters, vol. 91, no. 5, p. 58004, 2010.
  * [33] S. C. Fennell, K. Burke, M. Quayle, and J. P. Gleeson, “Generalized mean-field approximation for the Deffuant opinion dynamics model on networks,” Physical Review E, vol. 103, no. 1, p. 012314, 2021.
  * [34] F. Baumann, I. M. Sokolov, and M. Tyloo, “A Laplacian approach to stubborn agents and their role in opinion formation on influence networks,” Physica A: Statistical Mechanics and its Applications, vol. 557, p. 124869, 2020\.
  * [35] X. Si, Y. Liu, and Z. Zhang, “Opinion dynamics in populations with implicit community structure,” International Journal of Modern Physics C, vol. 20, no. 12, pp. 2013–2026, 2009.
  * [36] G. Como and F. Fagnani, “From local averaging to emergent global behaviors: The fundamental role of network interconnections,” Systems & Control Letters, vol. 95, pp. 70–76, 2016.
  * [37] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, “Randomized gossip algorithms,” IEEE Transactions on Information Theory, vol. 52, no. 6, pp. 2508–2530, 2006.
  * [38] F. Fagnani and S. Zampieri, “Randomized consensus algorithms over large scale networks,” IEEE Journal on Selected Areas in Communications, vol. 26, no. 4, pp. 634–649, 2008.
  * [39] D. Acemoğlu, G. Como, F. Fagnani, and A. Ozdaglar, “Opinion fluctuations and disagreement in social networks,” Mathematics of Operations Research, vol. 38, no. 1, pp. 1–27, 2013.
  * [40] P. Holme and M. E. Newman, “Nonequilibrium phase transition in the coevolution of networks and opinions,” Physical Review E, vol. 74, no. 5, p. 056108, 2006.
  * [41] S. Biswas, A. Chatterjee, and P. Sen, “Disorder induced phase transition in kinetic models of opinion dynamics,” Physica A: Statistical Mechanics and its Applications, vol. 391, no. 11, pp. 3257–3265, 2012.
  * [42] G. Shi, A. Proutiere, M. Johansson, J. S. Baras, and K. H. Johansson, “The evolution of beliefs over signed social networks,” Operations Research, vol. 64, no. 3, pp. 585–604, 2016.
  * [43] Y. Xing and K. H. Johansson, “What is the expected transient behavior of opinion evolution for two communities?,” arXiv preprint arXiv:2304.12495, 2023.
  * [44] F. Chung and M. Radcliffe, “On the spectra of general random graphs,” The Electronic Journal of Combinatorics, p. P215, 2011.