myfnsymbols¶¶ [para]math[fnsymbol] footnotemath

# Social System Inference from Noisy Observations

Yanbing Mao, Naira Hovakimyan, Tarek Abdelzaher, and Evangelos Theodorou Y.
Mao and N. Hovakimyan are with the Department of Mechanical Science and
Engineering, University of Illinois at Urbana–Champaign, Urbana, IL 61801, USA
(e-mail: {ybmao, nhovakim}@illinois.edu).T. Abdelzaher is with the Department
of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL
61801, USA (e-mail: zaher@illinois.edu).E. Theodorou is with the Department of
Aerospace Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA
(e-mail: evangelos.theodorou@gatech.edu).This work was supported by NSF
CNS-1932529, DARPA W911NF-17-C-0099 and AFOSR FA9550-15-1-0518.

###### Abstract

This paper studies social system inference from a single trajectory of public
evolving opinions, wherein observation noise leads to the statistical
dependence of samples on time and coordinates. We first propose a cyber-social
system that comprises individuals in a social network and a set of information
sources in a cyber layer, whose opinion dynamics explicitly takes confirmation
bias, negativity bias and process noise into account. Based on the proposed
social model, we then study the sample complexity of least-square auto-
regressive (AR(1)) model estimation, which governs the number of observations
that are sufficient for the identified model to achieve the prescribed levels
of accuracy and confidence. Building on the identified social model, we then
investigate social inference, with particular focus on the weighted network
topology, the subconscious bias and the model parameters of confirmation bias
and negativity bias. Finally, the theoretical results and the effectiveness of
the proposed social systems are validated by the US Senate Member Ideology
data.

###### Index Terms:

Social inference, network topology, subconscious bias, confirmation bias,
negativity bias, sample complexity,

##  I Introduction

Dynamical network identification from observed nodal states, with a particular
focus on graph topology identification/reconstruction, has gained widespread
attention in a wide variety of fields, ranging from power networks [1] to gene
regulatory networks [2] and social networks [3]. Leveraging Bayesian analysis
and estimation theory, compressed sensing, optimization theory with sparsity
constraints, and others [4], structural equation models [5], autoregressive
models [6] and Wiener filtering [7] have been employed to identify network
topology. However, in social networks, individual cognitive behaviors, e.g.,
confirmation bias [8], preferences for outlying content [9] and distancing and
striving for uniqueness [10], in conjunction with observation noise, pose a
formidable challenge to network topology identification, especially in the
modern information era with information overload [11, 12]. A fairly accurate
social model which explicitly takes cognitive behaviors as well as
subconscious bias into account is indispensable for the topology
identification with prescribed levels of accuracy and confidence (PAC).

The social model of opinion evolution has been an active subject for decades,
among which a few well-known models have been proposed to capture individual
conformity, cognitive and subconscious behaviors [13, 14]. For example,
DeGroot model [15] considers individual opinion evolution as an average of her
neighbors, which describes conformity behavior. Friedkin-Johnsen model [16]
incorporates individual subconscious bias into opinion evolution, thereby
making the model more suitable to several real-life scenarios and applications
[17]. Though imposing a bounded confidence on social influence, Hegselmann-
Krause model [18] has the capability of addressing confirmation bias [19],
which helps create “echo chambers” within networks, in which misinformation
and polarization thrive [20]. Hegselmann-Krause model involves a discontinuity
in the influence impact, i.e., an individual completely ignores the opinions
that are “too far” from hers, which renders the steady-state analysis
difficult. As a remedy, we proposed an opinion evolution model in [21, 22],
which is a variation of Friedkin-Johnsen model with continuous and symmetric
confirmation bias model. Recently, Abdelzaher et al. in [11] and Xu et al. in
[12] reveal the significant influence of consumer preferences for outlying
content on opinion polarization in the modern era of information overload.
Meanwhile, Lamberson and Stuart in [9] suggest that negative information,
which is far away from expectations, is more “outlying.” Motivated by these
discoveries, we incorporate negativity bias, which refers to a tendency to be
more attentive and/or responsive to a unit of negative information than to a
unit of positive information [9], to the previously proposed opinion dynamics
[21, 22]. Our opinion evolution model in this paper also includes random
process noise that describes model errors and uncertainty.

Ignoring negativity bias, our study of competitive information spread in
social networks uncovers the dependence of Nash equilibrium on network
topology, subconscious bias and confirmation bias parameters [21]; similar
discoveries appear in [23]. The studies therein indicate that inferring
network topology only is not sufficient for optimal decision making in social
networks [3]. Motivated by this observation, concurrent inference of network
topology and confirmation bias are primarily investigated in [24], which
however relies on several rather restrictive assumptions: 1) an individual’s
subconscious bias equates to her initial opinion, 2) observations of evolving
opinions are completely reliable, i.e., noise-free, and 3) negativity bias and
process noise have no influence on opinion evolution. To remove these
assumptions, we propose a social-system inference procedure, which is based on
least-square auto-regressive (AR(1)) model estimation. The inference
objectives include weighted network topology, public subconscious bias, model
parameters of confirmation bias and negativity bias.

Due to process and observation noise, one intuitive question pertaining to the
accuracy of social-system inference arises: how many observations are
sufficient for the inference solution to achieve PAC? To answer this question
in the context of system-matrix estimation, significant effort has been
devoted towards the sample complexity of ordinary least-square estimator in
recent three years [25, 26, 27, 28, 29]. We note that the analysis of sample
complexity therein relies on Hanson-Wright inequality [30], which requires
zero-mean, unit-variance, sub-gaussian independent coordinates for noise
vectors. Banerjee et al. in [31] considered the generalization of existing
results by allowing for statistical dependence on stochastic processes via
Johnson–Lindenstrauss transform, which however still requires the noise
variables to have zero mean and the marginal random variables to be
conditionally independent. In this paper, we reveal that even if the
observation noise vectors have $\mathrm{i.i.d}$ coordinates and time, the
noise leads to inevitable statistical dependence of opinion observations on
time and coordinates. The statistical dependence and possible non-zero mean of
noise hinder the application of obtained sample complexity in [25, 26, 27, 28,
29] to social system inference. These observations motivate to investigate the
sample complexity of social system estimation in the presence of observation
noise with none-zero mean, which paves the way for the derivation of social
system inference.

The contributions of this paper are summarized as follows.

  * •

Building on Friedkin-Johnsen model [16], we propose an opinion evolution model
with incorporation of confirmation bias, negativity bias and process noise.

  * •

In the presence of observation noise with non-zero mean, which results in
statistical dependence of opinion observations on time and coordinates, we
investigate the sample complexity of proposed social system estimation.

  * •

Building on social system estimation, we drive a social-system inference
procedure for weighted network topology, subconscious bias, model parameters
of confirmation bias and negativity bias.

  * •

We validate the theoretical results and the effectiveness of proposed opinion
evolution model by US Senate Member Ideology data.

This paper is organized as follows. In Section II, we present preliminaries.
In Sections III and IV, we investigate social system estimation and social
system inference, respectively. We present validation results in Section V. We
finally present conclusions in Section VI.

##  II Preliminaries

###  II-A Notation

We let $\mathbb{R}^{n}$ and $\mathbb{R}^{m\times n}$ denote the set of
n-dimensional real vectors and the set of $m\times n$-dimensional real
matrices, respectively. $\mathbb{N}$ stands for the set of natural numbers,
and $\mathbb{N}_{0}=\mathbb{N}\bigcup{0}$. We let $\mathbf{1}$ and
$\mathbf{0}$ denote the vectors of all ones and all zeros, compatible
dimensions. We define $\mathbf{I}_{n}$ as $n$-dimension identity matrix. The
superscript ‘$\top$’ stands for the matrix transposition. For a matrix $W$,
${\left[W\right]_{i,j}}$ denotes the element in row $i$ and column $j$. Other
important notations are highlighted as follows:

$||A||:$

spectral norm of matrix $A$;

$||A||_{\mathrm{F}}:$

Frobenius norm of matrix $A$;

$||x||:$

Euclidean norm of vector $x$;

$\mathbf{E}$

expectation operator;

$\mathcal{S}^{n-1}:$

unit sphere in $\mathbb{R}^{n}$;

$\Omega^{\mathrm{c}}:$

complement of event $\Omega$;

$\mathbf{P}(\Omega):$

probability of event $\Omega$;

$\lambda_{\min}(A):$

minimum eigenvalue of symmetric matrix $A$.

The social system is composed of $n$ individuals in social network and $m$
information sources. The interaction among individuals is modeled by a digraph
$\mathfrak{G}=(\mathbb{V},\mathbb{E})$, where $\mathbb{V}$ =
$\left\\{\mathrm{v}_{1},\ldots,\mathrm{v}_{n}\right\\}$ is the set of vertices
representing the individuals, and
$\mathbb{E}\subseteq\mathbb{V}\times\mathbb{V}$ is the set of edges of the
digraph $\mathfrak{G}$ representing the influence structure. The communication
from information sources to individuals is modeled by a bipartite digraph
$\mathfrak{B}=(\mathbb{V}\bigcup\mathbb{K},\mathbb{B})$, where $\mathbb{K}$ =
$\left\\{\mathrm{u}_{1},\ldots,\mathrm{u}_{m}\right\\}$ is the set of vertices
representing information sources, and
$\mathbb{B}\subset\mathbb{V}\times\mathbb{K}$ is the set of edges of the
digraph.

###  II-B Social Network Model

We consider the following model which is adopted from Friedkin-Johnsen model
[16] and its recent variation [21]:

$\displaystyle{x_{i}}(k\\!+\\!1)$
$\displaystyle\\!=\\!{\alpha_{i}}({{x_{i}}(k)}){s_{i}}\\!+\\!\sum\limits_{j\in\mathbb{V}}\\!{{w_{ij}}{x_{j}}(k)}\\!+\\!\sum\limits_{d\in\mathbb{K}}\\!{{c_{id}}({{x_{i}}(k)})h_{d}(k)}$
$\displaystyle\hskip
56.9055pt+\\!\sum\limits_{d\in\mathbb{K}}\\!{{n_{id}}({{x_{i}}(k)})h_{d}(k)}\\!+\\!{\mathfrak{p}_{i}}(k),$
(1a) $\displaystyle{y_{i}}(k)$
$\displaystyle\\!=\\!{x_{i}}(k)\\!+\\!{\mathfrak{o}_{i}}(k),\leavevmode\nobreak\
\leavevmode\nobreak\ i\\!\in\\!\mathbb{V},\leavevmode\nobreak\
k\\!\in\\!\mathbb{N}.$ (1b)

Here we clarify the notations and variables.

  * •

${x_{i}}\\!\left({k}\right)\in[-1,1]$ is individual $\mathrm{v}_{i}$’s
opinion, ${y_{i}}({k})\in[-1,1]$ is her observed opinion; ${s_{i}}\in[-1,1]$
is her subconscious bias (also referred to innate opinion), which is based on
inherent personal characteristics (e.g., socio-economic conditions where the
individual grew up and/or lives in) [16]; ${h_{d}}(k)\in[-1,1]$ is information
source $\mathrm{u}_{d}$’s opinion.

  * •

${\mathfrak{p}}_{i}(k)$ denotes process noise due to model error and
uncertainty, ${\mathfrak{o}}_{i}(k)$ denotes observation noise.

  * •

$w_{ij}$ represents the influence of individual $\mathrm{v}_{j}$ on
$\mathrm{v}_{i}$, and

$w_{ij}=\begin{cases}>0,&\text{if
}(\mathrm{v}_{i},\mathrm{v}_{j})\in\mathbb{E}\\\
=0,&\text{otherwise}.\end{cases}$

We note the individual-individual influence weights $w_{ij}$s are cognition or
knowledge trust based and thus fixed over time, since the cognitive factors
that can influence trust decisions are founded on a deeper knowledge of the
other person and the stability of the other’s behavior across time and
contexts [32].

  * •

The state-dependent influence weight $c_{id}({x_{i}}(k))$ models “confirmation
bias” as

$\displaystyle\\!\\!c_{id}({x_{i}}(k))\\!=\\!2\epsilon_{i}\\!-\\!\epsilon_{i}|x_{i}(k)\\!-\\!h_{d}(k)|,\leavevmode\nobreak\
\text{with}\leavevmode\nobreak\ \epsilon_{i}\\!\geq\\!0.$ (2)

We note that function (2) can also model homophily [10, 33]. It is used in
this paper to describe the symmetric confirmation bias, whose motivations are:
1) both polarization and homogeneity are the results of the conjugate effect
of confirmation bias and social influence [19, 34], 2) confirmation bias
happens when a person gives more weight to evidence that confirms their
beliefs and undervalues evidence that could disprove it [35].

  * •

The state-dependent influence weight $n_{id}({x_{i}}(k))$ models “negativity
bias” as

$\displaystyle
n_{id}({x_{i}}(k))=\eta_{i}|\bar{x}_{i}(k)-h_{d}(k)|,\leavevmode\nobreak\
\text{with}\leavevmode\nobreak\ \eta_{i}\geq 0,$ (3)

where ${{\bar{x}}_{i}}(k)$ denotes individual $\mathrm{v}_{i}$’s sensed
expectation from her neighbors, defined as the mean of her neighbors’
opinions, i.e.

$\displaystyle{{\bar{x}}_{i}}(k)\triangleq\frac{1}{{\sum\limits_{l\in\mathbb{V}}{{{w_{il}}}}}}\sum\limits_{j\in\mathbb{V}}{{{w_{ij}}}{x_{j}}(k)}.$
(4)

The motivation behind the models (3) and (4) can be explained by the
significant impact of consumer preferences for outlying content on opinion
polarization in the era of information overload revealed in [11, 12], and by
the discoveries in [9] that 1) negative information, which is far away from
expectations, is more “outlying” (which motivates the opinion distance between
sensed expectation and opinion of information source in (3)), and 2) the
negativity bias refers to a tendency that is more attentive and/or responsive
to a unit of negative information than to a unit of positive information
(which motivates the strictly increasing function (3) w.r.t. opinion distance,
if $\eta_{i}>0$).

  * •

$\alpha_{i}(x_{i}(k))\geq 0$ is the “resistance parameter” of individual
$\mathrm{v}_{\mathrm{i}}$. To guarantee $x_{i}(k)\in[-1,1]$ for $\forall
k\in\mathbb{N}$ and $\forall i\in\mathbb{V}$, it is determined in such a way
that

$\displaystyle{\alpha_{i}}({{x_{i}}(k)})+\sum\limits_{j\in\mathbb{V}}{{w_{ij}}}+\sum\limits_{d\in\mathbb{I}}{{c_{id}}({{x_{i}}(k)})}+\chi_{i}$
$\displaystyle\hskip
82.51282pt+\sum\limits_{d\in\mathbb{I}}{{n_{id}}({{x_{i}}(k)})}=1,\forall
i\\!\in\\!\mathbb{V},$ (5)

where $\chi_{1}$ denotes the bound on process noise in this paper, i.e.
$|{\mathfrak{p}_{i}}(k)|<\chi_{i}$, $\forall k\in\mathbb{N}$.

  * •

Another motivation behind the state-dependent influence (i.e.,
$c_{id}({x_{i}}(k))$ in (2) and $n_{id}({x_{i}}(k))$ in (3)) of information
sources on individuals is that information sources lack the rational basis of
trust, e.g., news media prioritizes outlying information for attentiveness.

###  II-C Inference Objectives

Our investigation of competitive information spread in social networks
revealed the dependence of optimal information spread strategies on
subconscious bias, network topology and confirmation bias [21]. Intuitively,
taking consumer preferences for outlying content into account, the optimal
decision would depend on negativity bias as well. Hereto, the social-system
inference objectives include subconscious bias, weighted network topology and
model parameters of confirmation and negativity bias. We thus denote the
social inference solution by

$\displaystyle\mathcal{S}\triangleq(\breve{W},\leavevmode\nobreak\
\breve{s},\leavevmode\nobreak\ \breve{\epsilon},\leavevmode\nobreak\
\breve{\eta}).$ (6)

Figure 1: Social-system inference framework for solution (6) with PAC: sample
complexity determines the dwell time of strategic extremal opinions.

The proposed social-system inference framework is first described in Figure 1,
where the information sources are required to strategically and temporarily
express extremal opinions $-1$ and $+1$ for obtaining the inference solution
(6). This requirement is due to the state-dependent influence weights (2) and
(3). If this requirement cannot be satisfied and is removed, i.e. the
information sources have no cooperation, the information sources will be
modeled as individuals in a social network, and the inference solution (6)
reduces to $({\breve{W},\breve{s}})$ for Friedkin-Johnsen model [16] or
${\breve{W}}$ for DeGroot model [15] as studied in [3].

Observing (2) and (3), we conclude that if information sources express
extremal opinions -1 or +1, the social dynamics (1) transforms to a linear
system, and if they express an identical opinion, they are regarded as one
information source from the perspective of individuals. The formed linear
systems under this consideration are described as follows.

####  II-C1 Extremal Opinion $-1$

Under the strategy that information sources express the identical extremal
opinion $-1$, i.e., $h_{d}(k)=-1$ and $|\mathbb{K}|=1$, the dynamics in (1)
transforms to

$\displaystyle x({k+1})$
$\displaystyle=\underline{\alpha}+\underline{\mathcal{W}}x(k)+\mathfrak{p}(k)$
(7a) $\displaystyle y({k})$ $\displaystyle=x(k)+\mathfrak{o}(k),\hskip
14.22636ptk\in\\{1,\ldots,\underline{p}-1,\underline{p}\\},$ (7b)

where we define:

$\displaystyle{\underline{\alpha}_{i}}\triangleq({1-\sum\limits_{j\in\mathbb{V}}{{w_{ij}}}}-\chi_{i})s_{i}-({{\epsilon_{i}}+{\eta_{i}}})({1+{s_{i}}}),$
(8a)
$\displaystyle{\left[\underline{\mathcal{W}}\right]_{i,j}}\triangleq\begin{cases}{w_{ii}}-\frac{{({{s_{i}}+1}){\eta_{i}}}}{{\sum\limits_{l\in\mathbb{V}}{{w_{il}}}}}{{{w_{ii}}}}+{({1+{s_{i}}}){\epsilon_{i}}},\\!&\text{if}\leavevmode\nobreak\
i\\!=\\!j\\\
{w_{ij}}-\frac{{({{s_{i}}+1}){\eta_{i}}}}{{\sum\limits_{l\in\mathbb{V}}{{w_{il}}}}}{{{w_{ij}}}},\\!&\text{if}\leavevmode\nobreak\
i\\!\neq\\!j.\end{cases}$ (8b)

####  II-C2 Extremal Opinion $1$

Under the strategy that information sources express the identical extremal
opinion $+1$, i.e., $h_{d}(k)=+1$ and $|\mathbb{K}|=1$, the dynamics in (1)
transforms to

$\displaystyle x({k+1})$
$\displaystyle=\overline{\alpha}+\overline{\mathcal{W}}x(k)+\mathfrak{p}(k),$
(9a) $\displaystyle y({k})$ $\displaystyle=x(k)+\mathfrak{o}(k),\hskip
14.22636ptk\\!\in\\!\\{\underline{p}\\!+\\!1,\leavevmode\nobreak\
\ldots,\leavevmode\nobreak\ \overline{p}\\!-\\!1,\leavevmode\nobreak\
\overline{p}\\},$ (9b)

where we define:

$\displaystyle{\overline{\alpha}_{i}}\triangleq({1-\sum\limits_{j\in\mathbb{V}}{{w_{ij}}}}-\chi_{i}){s_{i}}+({{\epsilon_{i}}+\eta_{i}})({1-{s_{i}}}),$
(10a)
$\displaystyle{\left[\overline{\mathcal{W}}\right]_{i,j}}\triangleq\begin{cases}w_{ii}+\frac{{({{s_{i}}-1}){\eta_{i}}}}{{\sum\limits_{l\in\mathbb{V}}{{{{w_{il}}}}}}}{{{{w_{ii}}}}}+{({1-{s_{i}}}){\epsilon_{i}}},\\!&\text{if}\leavevmode\nobreak\
i\\!=\\!j\\\
{w_{ij}}+\frac{{({{s_{i}}-1}){\eta_{i}}}}{{\sum\limits_{l\in\mathbb{V}}{{{{w_{il}}}}}}}{{{{w_{ij}}}}},\\!&\text{if}\leavevmode\nobreak\
i\\!\neq\\!j.\end{cases}$ (10b)

###### Remark 1

Ignoring process noise $\mathfrak{p}(k)$, the dynamics (9a) and (7a) have the
same form of Friedkin-Johnsen model [16], whose critical difference is that
the matrix entries in (9a) and (7a) are allowed to be negative, which is due
to negativity bias.

To obtain (6), the social-system inference framework first inputs observations
of evolving opinions to estimate vectors $\overline{\alpha}$ and
$\underline{\alpha}$ and matrices $\overline{\mathcal{W}}$ and
$\underline{\mathcal{W}}$, which are denoted in

$\displaystyle\mathcal{M}\triangleq({\widehat{\overline{\alpha}},\leavevmode\nobreak\
\leavevmode\nobreak\ \widehat{\underline{\alpha}},\leavevmode\nobreak\
\leavevmode\nobreak\ \widehat{\overline{\mathcal{W}}},\leavevmode\nobreak\
\leavevmode\nobreak\ \widehat{\underline{\mathcal{W}}}}).$ (11)

###  II-D Problem Formulation

In the context of learning-based competing camps in social networks,
competitive information sources leverage inference solution (6) for later
decision making of optimal opinions that should be spread to her followers.
Therefore, information sources can only express extremal opinions temporality
to infer (6). Hereto, the dwell times of strategic extremal opinions, or
equivalently the number of observations, that are sufficient for high accurate
inference (6) constitutes the first problem of this paper. Observing (10) and
(8), we discover that the matrices $\overline{\mathcal{W}}$ and
$\underline{\mathcal{W}}$ include all of the inference objectives included in
(6). Motivated by this observation, the dwell time is determined by the
estimations of $\overline{\mathcal{W}}$ and $\underline{\mathcal{W}}$ in this
problem, which is formally stated as follows.

Problem I: Find the dwell times of strategic extremal opinions that guarantee
the estimations of $\overline{\mathcal{W}}$ and $\underline{\mathcal{W}}$ to
be $(\phi,\delta)$–PAC, i.e.

$\displaystyle\\!\\!\mathbf{P}(||\widehat{\overline{\mathcal{W}}}\\!-\\!{\overline{\mathcal{W}}}||\leq\phi)\\!\geq\\!1\\!-\\!\delta\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\
\mathbf{P}(||\widehat{\underline{\mathcal{W}}}\\!-\\!{\underline{\mathcal{W}}}||\\!\leq\\!\phi)\\!\geq\\!1\\!-\\!\delta$
(12)

for $\phi>0$ and $0<\delta<1$.

Given the estimation solution (11), inferring (6) constitutes the second
problem.

Problem II: Determine a social-system inference procedure that generates an
estimation solution (11) with $\left(\phi,\delta\right)$–PAC and inference
solution (6).

Finally, to simplify the representations of investigations for Problem I and
Problem II, we define:

$\displaystyle\vartheta(k)\\!\triangleq\\!\begin{cases}\\!+1,\\!\\!\\!\\!\\!&k\\!\in\\!\\{\overline{k},\ldots,\overline{p}\\}\\\
\\!-1,\\!\\!\\!\\!\\!&k\\!\in\\!\\{1,\ldots,\underline{p}\\}\end{cases}\\!\\!,\\!\leavevmode\nobreak\
\mathcal{A}_{\vartheta(k)}\\!\triangleq\\!\begin{cases}\\!\overline{\mathcal{W}},\\!\\!\\!\\!\\!&\vartheta(k)\\!=\\!+1\\\
\\!\underline{\mathcal{W}},\\!\\!\\!\\!\\!&\vartheta(k)\\!=\\!-1\end{cases}\\!,$
(13a)
$\displaystyle\mathfrak{a}_{\vartheta(k)}\\!\triangleq\\!\begin{cases}\\!\overline{\alpha},\\!\\!\\!&\vartheta(k)\\!=\\!+1\\\
\\!\underline{\alpha},\\!\\!\\!&\vartheta(k)\\!=\\!-1\end{cases}\\!,\hskip
34.14322pt\overline{k}\triangleq\underline{p}+1,$ (13b)

based on which, we obtain the trajectory of observed public opinions from
the dynamics (7) and (9) as

$\displaystyle
y(j)\\!=\\!\sum\limits_{i=1}^{j-1}\\!{{\mathcal{M}_{(i,j)}}({{\alpha_{\vartheta(j-i)}}\\!+\\!\mathfrak{p}(j\\!-\\!i)})\\!+\\!\mathcal{M}_{j}^{\mathrm{c}}}x(1)\\!+\\!\mathfrak{o}(j),$
(14)

where

$\displaystyle{\mathcal{M}_{({i,j})}}$
$\displaystyle\triangleq\begin{cases}\mathcal{A}_{+1}^{j-\underline{p}}\\!\mathcal{A}_{-1}^{i-j+\underline{p}-1},&j>\underline{p}\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ i>j-\underline{p}\\\
\mathcal{A}_{+1}^{i-1},&j>\underline{p}\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ i\leq j-\underline{p}\\\
\mathcal{A}_{-1}^{i-1},&j\leq\underline{p}\end{cases},$ (15a)
$\displaystyle\mathcal{M}^{\mathrm{c}}_{j}$
$\displaystyle\triangleq\begin{cases}\mathcal{A}_{+1}^{j-\underline{p}}\mathcal{A}_{-1}^{\underline{p}-1},&j>\underline{p}\\\
\mathcal{A}_{-1}^{j-1},&j\leq\underline{p}.\end{cases}$ (15b)

##  III Problem I: Social System Estimation

In this section, we first present the least-square AR(1) model estimation. We
then present assumptions and investigate sample complexity of estimation,
leveraging which we derive the dwell times of strategic extremal opinions for
$\left(\phi,\delta\right)$–PAC.

We now present data processor of observations of public evolving opinions, as
shown in Figure 1, which is a necessary step for sample complexity analysis.

$\displaystyle\widetilde{\mathbf{y}}^{j}_{g}\triangleq
y(g)-y(j),\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
g<j\in\\{1,2,\ldots,\overline{p}\\}.$ (16)

Correspondingly, we define:

$\displaystyle\widetilde{\mathbf{x}}^{j}_{g}\\!\triangleq\\!x(g)\\!-\\!x(j),\leavevmode\nobreak\
\leavevmode\nobreak\
\widehat{\mathfrak{p}}^{j}_{g}\\!\triangleq\\!\mathfrak{p}(g)\\!-\\!\mathfrak{p}(j),\leavevmode\nobreak\
\leavevmode\nobreak\
\widetilde{\mathfrak{o}}^{j}_{g}\\!\triangleq\\!\mathfrak{o}(g)\\!-\\!\mathfrak{o}(j).$
(17)

With the consideration of (13), (16) and (17), we obtain the following
dynamics from systems (7) and (9):

$\displaystyle\widetilde{\mathbf{x}}^{j+1}_{g+1}=\mathcal{A}_{\vartheta(g)}\widetilde{\mathbf{x}}^{j}_{g}+\widehat{\mathfrak{p}}^{j}_{g},\leavevmode\nobreak\
\widetilde{\mathbf{y}}^{j}_{g}=\widetilde{\mathbf{x}}^{j}_{g}+\widetilde{\mathfrak{o}}^{j}_{g},\leavevmode\nobreak\
g\\!<\\!j\\!<\\!\underline{k}\\!\leavevmode\nobreak\
\text{or}\leavevmode\nobreak\ \\!j\\!>\\!g\\!\geq\\!\overline{k}$

by which we then obtain the dynamics of $\widetilde{\mathbf{y}}^{j}_{g}$ as

$\displaystyle\widetilde{\mathbf{y}}^{j+1}_{g+1}$
$\displaystyle=\mathcal{A}_{\vartheta(g)}\widetilde{\mathbf{y}}^{j}_{g}+\widehat{\mathfrak{g}}^{j}_{\vartheta(g)}$
(18a) $\displaystyle\widehat{\mathfrak{g}}^{j}_{\vartheta(g)}$
$\displaystyle=\widehat{\mathfrak{p}}^{j}_{g}+\widetilde{\mathfrak{o}}^{j+1}_{g+1}-\mathcal{A}_{\vartheta(g)}\widetilde{\mathfrak{o}}^{j}_{g},\\!\leavevmode\nobreak\
\leavevmode\nobreak\ g\\!<\\!j\\!<\\!\underline{k}\leavevmode\nobreak\
\text{or}\leavevmode\nobreak\ j\\!>\\!g\\!\geq\\!\overline{k}.$ (18b)

###### Remark 2

The noise term (18b) indicates the statistical dependence of observed evolving
opinions on time and coordinates, which is induced by observation noise.

###  III-A Least-Square AR(1) Model Estimation

We construct following data matrices:

$\displaystyle
Y_{(k,{p})}\\!\triangleq\\!\left[\widetilde{\mathbf{y}}^{k+2}_{k+1},\ldots,\widetilde{\mathbf{y}}^{p}_{k+1},\widetilde{\mathbf{y}}^{k+3}_{k+2},\ldots,\widetilde{\mathbf{y}}^{p}_{k+2},\ldots,\widetilde{\mathbf{y}}^{p}_{p-1}\right]\\!,$
(19) $\displaystyle
X_{(k,{p})}\\!\triangleq\\!\left[\widetilde{\mathbf{y}}^{k+1}_{k},\ldots,\widetilde{\mathbf{y}}^{p-1}_{k},\widetilde{\mathbf{y}}^{k+2}_{k+1},\ldots,\widetilde{\mathbf{y}}^{p-1}_{k+1},\ldots,\widetilde{\mathbf{y}}^{p-1}_{p-2}\right]\\!,$
(20) $\displaystyle
U_{\\!(k,p)}\\!\triangleq\\![\widehat{\mathfrak{g}}^{k+1}_{\vartheta(k)},\ldots,\widehat{\mathfrak{g}}^{p-1}_{\vartheta(k)},\widehat{\mathfrak{g}}^{k+2}_{\vartheta(k+1)},\ldots,\widehat{\mathfrak{g}}^{p-1}_{\vartheta(k+1)},\ldots,\widehat{\mathfrak{g}}^{p-1}_{\vartheta(p-2)}],$

considering which, we verify from systems (18) that

$\displaystyle{Y}_{(k,p)}=\mathcal{A}_{\vartheta(k)}{X}_{(k,p)}+{{U}}_{(k,p)},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
p\\!<\\!\overline{k}\leavevmode\nobreak\ \text{or}\leavevmode\nobreak\
k\\!\geq\\!\overline{k}.$ (21)

We note that matrix ${{U}}_{(k,p)}$ is unknown. The relation (18) thus
indicates the least-square AR(1) model estimation as

$\displaystyle{\widehat{\mathcal{A}}_{\vartheta(k)}}$
$\displaystyle=\mathop{\arg\min}\limits_{\widetilde{\mathcal{A}}_{\vartheta(k)}\in\mathbb{R}^{n\times
n}}||{{Y}_{(k,p)}-\widetilde{\mathcal{A}}_{\vartheta(k)}{X}_{(k,p)}}||_{2}^{2},$

from which we obtain the optimal estimation of matrix as

$\displaystyle{\widehat{\mathcal{A}}_{\vartheta(k)}}={Y}_{({k},{p})}{X}^{\top}_{({k},{p})}{({X}_{({k},{p})}{X}^{\top}_{({k},{p})})^{-1}}.$
(22)

Considering (9) and (10), with obtained estimation (22), the estimation of
$\mathfrak{a}_{\vartheta(k)}$ is obtained as

$\displaystyle\widehat{\mathfrak{a}}_{\vartheta(k)}=\frac{1}{{p-k}}\sum\limits_{q=k}^{p-1}{(y({q+1})-\widehat{\mathcal{A}}_{\vartheta(k)}y(q))}.$
(23)

Meanwhile, considering (20), we denote:

$\displaystyle\mathbf{E}[{{X_{(\\!{{k},{p}})}}X_{(\\!{{k},{p}})}^{\top}}]\\!=\\!\sum\limits_{g=k}^{p-2}{\sum\limits_{g<j=k+1}^{p-1}\\!\\!\\!\\!\\!\\!{\widetilde{\mathbf{y}}_{g}^{j}{{({\widetilde{\mathbf{y}}_{g}^{j}})^{\top}}}}}\\!\triangleq\\!{\Gamma_{({k,p})}}\\!\triangleq\\!\Psi^{-2}_{(k,p)}.$
(24)

###  III-B Assumption

We construct the following stacked vectors for presenting assumptions on
answering Problem I:

$\displaystyle{\theta}_{({k},{p})}\triangleq[{{\mathbf{o}}_{({{k},{p}})}},\leavevmode\nobreak\
\leavevmode\nobreak\
{{\mathbf{p}}_{({{k},{p}})}}]^{\top}\\!,\leavevmode\nobreak\
\leavevmode\nobreak\
{\widehat{\theta}}_{({k},{p})}\triangleq[{{\mathbf{a}}_{({{k},{p}})}},\leavevmode\nobreak\
\leavevmode\nobreak\ \mathbf{x}_{({p},{k})}]^{\top}\\!,$ (25)
$\displaystyle{\overline{\theta}_{({k,p})}}\triangleq{[{\theta_{({k,p})}^{\top},\leavevmode\nobreak\
{\mathbf{0}^{\top}}}]^{\top}},\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
{\underline{\theta}_{({k,p})}}\triangleq{[{{\mathbf{0}^{\top}},\leavevmode\nobreak\
\widehat{\theta}_{({k,p})}^{\top}}]^{\top}},$ (26)

where

$\displaystyle{{\mathbf{o}}_{k}}$
$\displaystyle\triangleq[{(\mathfrak{o}^{k+1}_{k})^{\top},\leavevmode\nobreak\
(\mathfrak{o}^{k+2}_{k})^{\top},\leavevmode\nobreak\
\ldots,\leavevmode\nobreak\ (\mathfrak{o}^{p-1}_{k})^{\top}}],$ (27a)
$\displaystyle{{\mathbf{o}}_{({k,p})}}$
$\displaystyle\triangleq[{\mathbf{o}_{k},\leavevmode\nobreak\
\mathbf{o}_{k+1},\leavevmode\nobreak\ \ldots,\leavevmode\nobreak\
{\mathbf{o}}_{p-3},\leavevmode\nobreak\ {\mathbf{o}}_{p-2}}],$ (27b)
$\displaystyle{{\widetilde{\mathbf{p}}}_{j}}$
$\displaystyle\triangleq[{\mathfrak{p}^{\top}(1),\leavevmode\nobreak\
\ldots,\leavevmode\nobreak\
\mathfrak{p}^{\top}(j\\!-\\!2),\leavevmode\nobreak\
\mathfrak{p}^{\top}(j\\!-\\!1)}],$ (27c) $\displaystyle{{{\mathbf{p}}}_{i}}$
$\displaystyle\triangleq[{{{\widetilde{\mathbf{p}}}_{i+1}},\leavevmode\nobreak\
{{\widetilde{\mathbf{p}}}_{i+2}},\leavevmode\nobreak\
\ldots,\leavevmode\nobreak\
{{\widetilde{\mathbf{p}}}_{p-2}},\leavevmode\nobreak\
{{\widetilde{\mathbf{p}}}_{p-1}}}],$ (27d)
$\displaystyle{{\mathbf{p}}_{(k,p)}}$
$\displaystyle\triangleq[{{{{\mathbf{p}}}_{k}},\leavevmode\nobreak\
{{{\mathbf{p}}}_{k+1}},\leavevmode\nobreak\ \ldots,\leavevmode\nobreak\
{{{\mathbf{p}}}_{p-3}},\leavevmode\nobreak\ {{{\mathbf{p}}}_{p-2}}}],$ (27e)
$\displaystyle{{\widetilde{\mathbf{a}}}_{j}}$
$\displaystyle\triangleq[{\alpha_{\vartheta(1)}^{\top},\leavevmode\nobreak\
\ldots,\leavevmode\nobreak\
\alpha_{\vartheta(j-2)}^{\top},\leavevmode\nobreak\
\alpha_{\vartheta(j-1)}^{\top}}],$ (27f) $\displaystyle{{{\mathbf{a}}}_{i}}$
$\displaystyle\triangleq[{{{\widetilde{\mathbf{a}}}_{i+1}},\leavevmode\nobreak\
{{\widetilde{\mathbf{a}}}_{i+2}},\leavevmode\nobreak\
\ldots,\leavevmode\nobreak\
{{\widetilde{\mathbf{a}}}_{p-2}},\leavevmode\nobreak\
{{\widetilde{\mathbf{a}}}_{p-1}}}],$ (27g)
$\displaystyle{{\mathbf{a}}_{(k,p)}}$
$\displaystyle\triangleq[{{{{\mathbf{a}}}_{k}},\leavevmode\nobreak\
{{{\mathbf{a}}}_{k+1}},\leavevmode\nobreak\ \ldots,\leavevmode\nobreak\
{{{\mathbf{a}}}_{p-3}},\leavevmode\nobreak\ {{{\mathbf{a}}}_{p-2}}}],,$ (27h)
$\displaystyle\mathbf{x}_{(p,k)}$
$\displaystyle\triangleq\left[{{x^{\top}}(1),{x^{\top}}(1),\ldots,{x^{\top}}(1)}\right]\in{\mathbb{R}^{\frac{{(p-k)(p-k-1)n}}{2}}}\\!.$
(27i)

Meanwhile, we define the following stacked matrices:

$\displaystyle{{\Upsilon}_{\\!(k,p)}}$
$\displaystyle\\!\triangleq\\!\text{diag}\\{\\!{\Psi_{\\!(k,p)}},\leavevmode\nobreak\
\ldots,\leavevmode\nobreak\
{\Psi_{\\!(k,p)}}\\!\\}\\!\in\\!\mathbb{R}^{\mathfrak{l}_{(k,p)}\times\mathfrak{l}_{(k,p)}},$
(28) $\displaystyle\mathbf{U}$
$\displaystyle\triangleq\text{diag}\left\\{{\mathbf{u}},\leavevmode\nobreak\
{\mathbf{u}},\leavevmode\nobreak\ \ldots,\leavevmode\nobreak\
{\mathbf{u}}\right\\}\\!\in\\!\mathbb{R}^{\mathfrak{l}_{(k,p)}\times\frac{\mathfrak{l}_{(k,p)}}{n}},$
(29) $\displaystyle{\Pi_{(k,p)}}$
$\displaystyle\triangleq[{\mathbf{I}_{\mathfrak{l}_{(k,p)}},\leavevmode\nobreak\
{\overline{\mathrm{W}}}_{(k,p)},\leavevmode\nobreak\
{\overline{\mathrm{W}}}_{(k,p)},\leavevmode\nobreak\
{\breve{\overline{\mathrm{W}}}}_{(k,p)}}],$ (30)

where $\mathbf{u}\in{\mathcal{S}^{n-1}}$ and

$\displaystyle{\mathfrak{l}_{(k,p)}}\triangleq\frac{{1}}{2}(p-k)(p-k-1)n,$
(31a)
$\displaystyle{\breve{\overline{\mathrm{W}}}}_{\\!(k,p)}\\!\\!\triangleq\\!{\text{diag}\\{{\mathcal{M}_{g}^{\mathrm{c}}\\!-\\!\mathcal{M}_{j}^{\mathrm{c}}}\\}_{\\!g<j\in\\{k,\ldots,p-1\\}}}\\!\in\\!\mathbb{R}^{\mathfrak{l}_{(k,p)}\\!\times\\!\mathfrak{l}_{(k,p)}}\\!,$
(31b)
$\displaystyle{\overline{\mathrm{A}}_{(g,j)}}\triangleq[{\mathcal{M}_{({g-1,g})}}(\mathbf{I}_{n}-\mathcal{M}_{(j-g+1,j)}),\leavevmode\nobreak\
\ldots,$ $\displaystyle\hskip
40.40285pt{\mathcal{M}_{({1,g})}}(\mathbf{I}_{n}-\mathcal{M}_{(j-g+1,j)}),\leavevmode\nobreak\
-{\mathcal{M}_{({j-g,j})}},$ $\displaystyle\hskip
40.40285pt-{\mathcal{M}_{({j-g-1,j})}},\leavevmode\nobreak\
\ldots,\leavevmode\nobreak\ -{\mathcal{M}_{({1,j})}}],\leavevmode\nobreak\
g<j$ (31c)
$\displaystyle{\overline{\mathrm{A}}_{k}}\triangleq{\text{diag}\\{{{\overline{\mathrm{A}}_{(k,k+1)}},\leavevmode\nobreak\
{\overline{\mathrm{A}}_{(k,k+2)}},\leavevmode\nobreak\
\ldots,\leavevmode\nobreak\ {\overline{\mathrm{A}}_{(k,p-1)}}}\\}},$ (31d)
$\displaystyle{\overline{\mathrm{W}}}_{(k,p)}\triangleq{\text{diag}\\{{{\overline{\mathrm{A}}_{k}},\leavevmode\nobreak\
{\overline{\mathrm{A}}_{k+1}},\leavevmode\nobreak\ \ldots,\leavevmode\nobreak\
{\overline{\mathrm{A}}_{p-3}},\leavevmode\nobreak\
{\overline{\mathrm{A}}_{p-2}}}\\}}.$ (31e)

We verify from (25)–(26), (30) and (31) that

$\displaystyle\breve{\mathrm{x}}_{(k,p)}={\Pi_{(k,p)}}({\overline{\theta}_{({k,p})}}+{\underline{\theta}_{({k,p})}}),$
(32a)
$\displaystyle\breve{\mathrm{x}}_{(k,p)}\triangleq\left[(\widetilde{\mathbf{y}}^{j}_{g})^{\top}\right]^{\top}_{g<j\in\\{k,\ldots,p-1\\}}\in\mathbb{R}^{\mathfrak{l}_{(k,p)}}.$
(32b)

With the definitions at hand, we make the following assumptions for solving
Problem I.

###### Assumption 1

Consider the social dynamics (1) with noise
$\widehat{\mathfrak{g}}^{j}_{\vartheta(k)}$ in (18b), vectors in (25) and
(26), matrices in (28)–(30).

  1. 1.

$\mathfrak{p}(k)$ $\stackrel{{\scriptstyle\mathrm{i.i.d.}}}{{\sim}}$
$\mathcal{D}_{\mathrm{p}}(\mathbf{0},\sigma^{2}_{\mathrm{p}}\mathbf{I}_{n})$,
$\mathfrak{o}(k)$ $\stackrel{{\scriptstyle\mathrm{i.i.d.}}}{{\sim}}$
$\mathcal{D}_{\mathrm{o}}(\mu_{\mathrm{o}}\mathbf{1},\sigma^{2}_{\mathrm{o}}\mathbf{I}_{n})$.

  2. 2.

${\overline{\theta}}_{({k},{p})}$ has the convex concentration property with
constant $\kappa>0$ for $k<p\in\mathbb{N}$.

  3. 3.

$[\widehat{\mathfrak{g}}^{j}_{\vartheta(k)}]_{i}$, $i\in\mathbb{V}$, is
$\mathcal{F}_{k}$-measurable and conditionally $\gamma$-sub-Gaussian for some
$\gamma$ $>$ $0$, i.e.,
$\mathbf{E}[{{e^{\left.{\lambda{[\widehat{\mathfrak{g}}^{j+1}_{\vartheta(k+1)}]_{i}}}\right|{\mathcal{F}_{k}}}}}]\leq{e^{{\frac{\lambda^{2}\gamma^{2}}{2}}}}$,
for all $\lambda$ $\in$ $\mathbb{R}$,
$k\\!<\\!j\\!\in\\!\\{k\\!+\\!1,\ldots,p\\!-\\!1\\}$.

  4. 4.

There exist scalars $\varrho_{1}>0$ and $\varrho_{2}>0$, such that

$\displaystyle\left|||\mathbf{U}^{\top}{{\Upsilon}^{\top}_{\\!(k,p)}}{{\Pi}_{\\!({k,p})}}{{{\overline{\theta}}_{\\!(k,p)}}}\\!||_{2}^{2}\\!+\\!||\mathbf{U}^{\top}{{\Upsilon}^{\top}_{\\!(k,p)}}{{\Pi}_{\\!({k,p})}}{{{\underline{\theta}}_{\\!(k,p)}}}\\!||_{2}^{2}\\!-\\!1\right|$
$\displaystyle\geq\left|\varrho_{1}-\varrho_{2}||\mathbf{U}^{\top}{{\Upsilon}^{\top}_{\\!(k,p)}}{{\Pi}_{\\!({k,p})}}({\overline{\theta}}_{\\!(k,p)}+{\underline{\theta}}_{\\!(k,p)})||_{2}^{2}\right|.$

###### Remark 3

Examples under Assumptions 1-2) include any random vector
$\eta\in\mathbb{R}^{s}$ with independent coordinates and almost sure
$|[\eta]_{i}|\leq 1$ for any $i\in\\{1,\ldots,s\\}$, random vectors obtained
via sampling without replacement, vectors with bounded coordinates satisfying
some uniform mixing conditions or Dobrushin type criteria, among many others
[36]. Examples of $[\widehat{\mathfrak{g}}^{j}_{\vartheta(k)}]_{i}$ under
Assumption 1-3) include a bounded zero-mean noise lying in an interval of
length at most $2\gamma$, a zero-mean Gaussian noise with variance at most
$\gamma^{2}$ [37].

######  Remark 4 (None-Zero Mean)

If $\mathfrak{p}(k)$ $\stackrel{{\scriptstyle\mathrm{i.i.d.}}}{{\sim}}$
$\mathcal{D}_{\mathrm{p}}(\mu_{\mathrm{p}}\mathbf{1},\sigma^{2}_{\mathrm{p}}\mathbf{I}_{n})$,
it can be rewritten as
$\mathfrak{p}(k)=\mu_{\mathrm{p}}\mathbf{1}+\widetilde{\mathfrak{p}}(k)$, with
$\widetilde{\mathfrak{p}}(k)$
$\stackrel{{\scriptstyle\mathrm{i.i.d.}}}{{\sim}}$
$\mathcal{D}_{\mathrm{p}}(\mathbf{0},\sigma^{2}_{\mathrm{p}}\mathbf{I}_{n})$.
In this scenario, model (9a), as an example, can be written as
$x({k+1})=(\overline{\alpha}+\mu_{\mathrm{p}}\mathbf{1})+\overline{\mathcal{W}}x(k)+\widetilde{\mathfrak{p}}(k)$.
Thus, Assumption 1-1) on process noise holds in general.

###  III-C Sample Complexity

We now investigate the sample complexity of estimation (22), whose associated
conditions will answer Problem I.

Under Assumption 1-1), we obtain the covariance matrix of vector
${\theta}_{({k},{p})}$ given in (25) as

$\displaystyle{\mathcal{C}}_{({k},{p})}\\!\triangleq\\!{\bf{E}}[{\theta}_{({{k},{p}})}{\theta}^{\top}_{({{k},{p}})}]\\!=\\!\left[\\!\\!\\!{\begin{array}[]{*{20}{c}}2{\sigma_{\mathrm{o}}^{2}{\mathbf{I}_{{\mathfrak{l}_{(k,p)}}}}}\\!\\!&\\!\\!\mathbf{O}\\\
\mathbf{O}\\!\\!&\\!\\!{\bf{E}}[{{\mathbf{p}}_{({{k},{p}})}}{{\mathbf{p}}^{\top}_{({{k},{p}})}}]\footnotemarkmath\end{array}}\\!\\!\\!\right]\\!\\!,$
(35)

Given the structure of ${\mathbf{p}}_{({{k},{p}})}$ in (27c)–(27e),
${\bf{E}}[{{\mathbf{p}}_{({{k},{p}})}}{{\mathbf{p}}^{\top}_{({{k},{p}})}}]$
can be straightforwardly computed under Assumption 1-1). Due to page limit,
its expression is not presented in this paper. where $\mathbf{O}$ denotes
zero matrix with compatible dimensions. Considering the covariance matrix, we
present an auxiliary proposition, whose proof appears in Appendix B.

###### Proposition 1

Under Assumption 1, the inequality (36) holds for
$\varepsilon\in[0,\frac{1}{2})$ and some universal constant $\mathfrak{c}>0$.

$\displaystyle\\!\\!\\!\\!\\!\mathbf{P}[{||\varrho_{2}\Psi_{\\!(k,p)}^{\top}{X_{\\!(k,p)}}X_{\\!(k,p)}^{\top}\\!{\Psi_{\\!(k,p)}}\\!-\\!\varrho_{1}\mathbf{I}_{n}||\\!>\\!\rho}]\leq
2\\!\cdot\\!{({\frac{2}{\varepsilon}\\!+\\!1})^{n}}\\!\cdot\\!e^{\frac{-1}{{\mathfrak{c}{\kappa^{2}}}}\\!\min\\!\left\\{\\!\\!{\frac{{{(1-2\varepsilon)^{2}n\rho^{2}}}}{{\mathfrak{l}_{({k},{p})}||{{\Pi}^{\top}_{(k,p)}}\\!{\Upsilon}_{(k,p)}\\!||^{4}||{\mathcal{C}}_{(k,p)}||}},\leavevmode\nobreak\
\frac{{(1-2\varepsilon)\rho}}{{||{{\Pi}^{\top}_{(k,p)}}\\!{{\Upsilon}_{(k,p)}}\\!||^{2}}}}\\!\\!\right\\}}\\!,\leavevmode\nobreak\
p\\!<\\!\overline{k}\leavevmode\nobreak\ \\!\text{or}\\!\leavevmode\nobreak\
k\\!\geq\\!\overline{k}.$ (36)

Leveraging Proposition 1, the sample complexity is presented in the following
theorem, whose proof is presented in Appendix C.

###### Theorem 1

Consider the estimated matrix ${\widehat{\mathcal{A}}_{\vartheta(k)}}$ in
(22), and the real matrix $\mathcal{A}_{\vartheta(k)}$ in (13). For any
$0\\!\leq\\!\varepsilon\\!<\\!\frac{1}{2}$, any
$0\\!<\\!\rho\\!<\\!\varrho_{1}$, any $\varrho_{2}\\!>\\!0$, any
$0\\!<\\!\delta\\!<\\!1$, and any $\phi\\!>\\!0$, we have

$\displaystyle\mathbf{P}[||{\widehat{\mathcal{A}}_{\vartheta(k)}}-\mathcal{A}_{\vartheta(k)}||>\phi]\leq\delta,\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\forall\vartheta(k)\in\\{-1,+1\\}$ (37)

if the followings hold for $k<p<\overline{k}$ and $p>k\geq\overline{k}$:

$\displaystyle\min\\!\left\\{\\!{\frac{{{{(1-2\varepsilon)}^{2}}n{\rho^{2}}}}{{\mathfrak{l}_{(k,p)}||\Pi_{(k,p)}^{\top}{\Upsilon_{(k,p)}}||^{4}||{\mathcal{C}_{(k,p)}}||}},\leavevmode\nobreak\
\leavevmode\nobreak\
\frac{{(1-2\varepsilon)\rho}}{{||\Pi_{(k,p)}^{\top}{\Upsilon_{(k,p)}}||^{2}}}}\\!\right\\}$
$\displaystyle\geq\frac{{\gamma^{2}}}{2}\ln\frac{{4{({\frac{2}{\varepsilon}+1})^{n}}}}{\delta},$
(38)
$\displaystyle{\lambda_{\min}}({{\Gamma_{\\!(k,p)}}})\\!\geq\\!\frac{{32\mathfrak{c}{\kappa^{2}}\varrho_{2}}}{{{\phi^{2}}(\varrho_{1}\\!-\\!\rho)}}\\!\ln\\!\left(\\!\\!{{{\left({\frac{{\varrho_{1}\\!-\\!\rho}}{2\varrho_{1}}}\right)^{0.5n}}}\frac{{2\cdot{5^{n}}}}{\delta}}\\!\\!\right)\\!>\\!0.$
(39)

###### Remark 5

The dwell times of strategic extremal opinions can be computed from the
conditions (38) and (39). However, the current forms are not ready for the
computation, which is due to the unknown $\mathcal{A}_{\vartheta(k)}$ included
in $\Pi_{(k,p)}$ and ${\Upsilon_{(k,p)}}$. Noting the relation (5) and the
fact that matrix $\mathcal{A}_{\vartheta(k)}$ is stable, it is practical to
know the matrix-norm bounds pertaining to $\mathcal{A}_{\vartheta(k)}$, which
can be further leveraged to estimate the bounds on the matrix norms of
$\Pi_{(k,p)}$ and ${\Upsilon_{(k,p)}}$ to compute the dwell times. This
computation is carried out in next subsection.

###  III-D Dwell Times of Strategic Extremal Opinions

With the consideration of $\mathcal{A}_{\vartheta(k)}$ in (13) and
$\Pi_{(k,p)}$ in (30), we present the following bounds pertaining to matrix
norm.

$\displaystyle\mathop{\min}\limits_{\\!\\!i,j,g,h\in\mathbb{N}_{0}}\\!\\!\left\\{\\!{{{||\mathcal{A}_{+1}^{j}\\!\mathcal{A}_{-1}^{i}\\!||}^{2}\\!,{||\mathcal{A}_{+1}^{g}\\!\mathcal{A}_{-1}^{h}\\!(\mathbf{I}_{n}\\!-\\!\mathcal{A}_{+1}^{j}\\!\mathcal{A}_{-1}^{i}\\!)||}^{2}}}\\!\right\\}\\!\geq\\!{\underline{\mathfrak{s}}},$
(40)
$\displaystyle\mathop{\max}\limits_{k<p\in\mathbb{N}_{0}}\left\\{{{{||\Pi_{(k,p)}||^{2}}}}\right\\}\leq{\overline{\mathfrak{s}}}\leq
1.$ (41)

###### Remark 6

The inequality (41) is obtained via considering (32), where
$-\mathbf{1}\leq\breve{\mathrm{x}}_{(k,p)}\leq\mathbf{1}$ and
$-\mathbf{1}\leq{\overline{\theta}_{({k,p})}}+{\underline{\theta}_{({k,p})}}\leq\mathbf{1}$
hold for any $k<p\in\mathbb{N}$ and any $x_{i}(1)\in[-1,1],i\in\mathbb{V}$.

With the bounds, we define:

$\displaystyle\mathfrak{f}_{(k,p)}$ $\displaystyle\triangleq
2\frac{{\mathfrak{l}_{(k,p)}}}{n}\sigma^{2}_{\mathrm{o}}+\underline{\mathfrak{s}}\frac{{\widehat{\mathfrak{l}}_{(k,p)}}}{n}\sigma^{2}_{\mathrm{p}},\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
{\mathfrak{j}_{(k,p)}}\triangleq\frac{\overline{\mathfrak{s}}}{\mathfrak{f}_{(k,p)}},$
(42) $\displaystyle{\widehat{\mathfrak{l}}_{({k,p})}}$
$\displaystyle\triangleq\sum\limits_{i=1}^{p-k-1}{({p-k-i})({p-1-i})n}.$ (43)

With the definitions at hand, we present a corollary of Theorem 1, whose proof
is given in Appendix D.

###### Corollary 1

The conditions (38) and (39) hold if

$\displaystyle\min\\!\left\\{\\!\\!{\frac{{{{(1\\!-\\!2\varepsilon)}^{2}}n{\rho^{2}}}}{{\mathfrak{l}_{(k,p)}{\mathfrak{j}^{2}_{(k,p)}}||{\mathcal{C}_{(k,p)}}||}},\\!\\!\leavevmode\nobreak\
\frac{{(1\\!-\\!2\varepsilon)\rho}}{{{\mathfrak{j}_{(k,p)}}}}}\\!\right\\}\\!\geq\\!\frac{{\gamma^{2}}}{2}\\!\ln\\!\frac{{4{({\frac{2}{\varepsilon}\\!+\\!1})^{n}}}}{\delta},$
(44)
$\displaystyle\mathfrak{f}_{(k,p)}\geq\frac{{32\mathfrak{c}{\kappa^{2}}\varrho_{2}}}{{{\phi^{2}}(\varrho_{1}-\rho)}}\\!\ln\\!\left(\\!{{{\left({\frac{{\varrho_{1}-\rho}}{2\varrho_{1}}}\right)^{0.5n}}}\frac{{2\cdot{5^{n}}}}{\delta}}\\!\right)>0.$
(45)

######  Remark 7 (Dwell Time Computation)

We denote the dwell times of strategic extremal opinions as
$\tau_{\vartheta(k)}=p-k+1$. Considering (13) and Corollary 1, they are
computed as

$\displaystyle\tau_{\vartheta(k)}=\begin{cases}p,&k\\!=\\!1,\vartheta(k)\\!=\\!-1\\\
p\\!-\\!\overline{k}\\!+\\!1,&k\\!=\\!\overline{k},\vartheta(k)\\!=\\!+1\end{cases}\\!,\leavevmode\nobreak\
s.t.\leavevmode\nobreak\ \eqref{fccq}\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ \eqref{fcc1}.$

##  IV Problem II: Social System Inference

With the obtained estimation (11), we investigate the computation of (6).
Considering the structures of real vectors and matrices in (8) and (10), we
write estimations (22) and (23) in the following forms:

$\displaystyle{[\widehat{\mathcal{A}}_{+1}]_{i,j}}$
$\displaystyle=\begin{cases}\\!{{\breve{w}_{ii}}+\frac{{({{\breve{s}_{i}}-1}){\breve{\eta}_{i}}}}{{\sum\limits_{l\in\mathbb{V}}{{{{{\breve{w}_{il}}}}}}}}{{{{\breve{w}_{ii}}}}}+({1-{\breve{s}_{i}}}){\breve{\epsilon}_{i}}}&\text{if}\leavevmode\nobreak\
i\\!=\\!j\\\
\\!{\breve{w}_{ij}}+\frac{{({{\breve{s}_{i}}-1}){\breve{\eta}_{i}}}}{{\sum\limits_{l\in\mathbb{V}}{{{{{\breve{w}_{il}}}}}}}}{{{{\breve{w}_{ij}}}}},&\text{if}\leavevmode\nobreak\
i\\!\neq\\!j\end{cases}$ (46a)
$\displaystyle{[\widehat{\mathcal{A}}_{-1}]_{i,j}}$
$\displaystyle=\begin{cases}\\!{{\breve{w}_{ii}}-\frac{{({{\breve{s}_{i}}+1}){\breve{\eta}_{i}}}}{{\sum\limits_{l\in\mathbb{V}}{{{{{\breve{w}_{il}}}}}}}}{{{{\breve{w}_{ii}}}}}+({1+{\breve{s}_{i}}}){\breve{\epsilon}_{i}}}&\text{if}\leavevmode\nobreak\
i\\!=\\!j\\\
\\!{\breve{w}_{ij}}-\frac{{({{\breve{s}_{i}}+1}){\breve{\eta}_{i}}}}{{\sum\limits_{l\in\mathbb{V}}{{{{{\breve{w}_{il}}}}}}}}{{{{\breve{w}_{ij}}}}},&\text{if}\leavevmode\nobreak\
i\\!\neq\\!j\end{cases}$ (46b)
$\displaystyle[\widehat{\mathfrak{a}}_{+1}]_{i}$
$\displaystyle=({1-\sum\limits_{j\in\mathbb{V}}{{\breve{w}_{ij}}}}){\breve{s}_{i}}+({{\breve{\epsilon}_{i}}+\breve{\eta}_{i}})({1-{\breve{s}_{i}}}),$
(46c) $\displaystyle[\widehat{\mathfrak{a}}_{-1}]_{i}$
$\displaystyle=({1-\sum\limits_{j\in\mathbb{V}}{{\breve{w}_{ij}}}})\breve{s}_{i}-({{\breve{\epsilon}_{i}}+{\breve{\eta}_{i}}})({1+{\breve{s}_{i}}}),$
(46d)

based on which the inference procedure is described by Algorithm 1. The
associated analysis are presented in the following theorem, whose proof
appears in Appendix E.

Input: Matrices $\widehat{\mathcal{A}}_{\vartheta}$ (22) and vectors
$\widehat{\mathfrak{a}}_{\vartheta}$ (23), $\vartheta\\!\in\\!\\{-1,+1\\}$.

1 Subconscious bias:
${{\breve{s}}_{i}}\\!\leftarrow\\!\frac{[\widehat{\mathfrak{a}}_{+1}]_{i}\\!+\\![\widehat{\mathfrak{a}}_{-1}]_{i}\\!+\\!\sum\limits_{j\in\mathbb{V}}\\!\\!{({{{[\widehat{\mathcal{A}}_{+1}]}_{i,j}}-{{[\widehat{\mathcal{A}}_{-1}]}_{i,j}}})}}{2-([\widehat{\mathfrak{a}}_{+1}]_{i}\\!-[\widehat{\mathfrak{a}}_{-1}]_{i})-\\!\\!\sum\limits_{j\in\mathbb{V}}\\!{({{{[\widehat{\mathcal{A}}_{+1}]}_{i,j}}\\!+{{[\widehat{\mathcal{A}}_{-1}]}_{i,j}}})}}$;

2 Confirmation bias:
${{\breve{\epsilon}}_{i}}\\!\leftarrow\\!\frac{[\widehat{\mathfrak{a}}_{+1}]_{i}-[\widehat{\mathfrak{a}}_{-1}]_{i}}{4}\\!-\\!\frac{\sum\limits_{j\in\mathbb{V}}\\!\\!{({{{[\widehat{\mathcal{A}}_{+1}]}_{i,j}}-{{[\widehat{\mathcal{A}}_{-1}]}_{i,j}}})}}{4\breve{s}_{i}}$;

3 Negativity bias:
${{\breve{\eta}}_{i}}\\!\leftarrow\\!\frac{[\widehat{\mathfrak{a}}_{+1}]_{i}-[\widehat{\mathfrak{a}}_{-1}]_{i}}{4}\\!+\\!\frac{\sum\limits_{j\in\mathbb{V}}\\!\\!{({{{[\widehat{\mathcal{A}}_{+1}]}_{i,j}}-{{[\widehat{\mathcal{A}}_{-1}]}_{i,j}}})}}{4\breve{s}_{i}}$;

4 Influence sum:
$\sum\limits_{j\in\mathbb{V}}{{\breve{w}_{ij}}}\\!\leftarrow\\!\frac{\sum\limits_{j\in\mathbb{V}}{({{{[\widehat{\mathcal{A}}_{+1}]}_{i,j}}+{{[\widehat{\mathcal{A}}_{-1}]}_{i,j}}})}}{2}+{\breve{\eta}_{i}}-{\breve{\epsilon}_{i}}$;

Topology:
$\breve{w}_{ij}\\!\leftarrow\\!\begin{cases}\\!\frac{{[\widehat{\mathcal{A}}_{+1}]_{i,i}}+{[\widehat{\mathcal{A}}_{-1}]_{i,i}}-2{\breve{\epsilon}_{i}}}{2(1-\frac{{{\breve{\eta}_{i}}}}{{\sum\limits_{l\in\mathbb{V}}{{{{{\breve{w}_{il}}}}}}}})}&\text{if}\leavevmode\nobreak\
i\\!=\\!j\\\
\\!\frac{{[\widehat{\mathcal{A}}_{+1}]_{i,j}}+{[\widehat{\mathcal{A}}_{-1}]_{i,j}}}{2(1-\frac{{{\breve{\eta}_{i}}}}{{\sum\limits_{l\in\mathbb{V}}{{{{{\breve{w}_{il}}}}}}}})},&\text{if}\leavevmode\nobreak\
i\\!\neq\\!j.\end{cases}$

Algorithm 1 Inference From Estimation

###### Theorem 2

Consider inference procedure in Algorithm 1.

  * •

If the inferred subconscious bias ${\breve{s}}_{i}\neq 0$ for $\forall
i\in\mathbb{V}$, Algorithm 1 generates inference solution (6).

  * •

If individual $\mathrm{v}_{i}$’s inferred subconscious bias is neutral, i.e.,
${\breve{s}}_{i}=0$, Algorithm 1 cannot infer her associated social structure
$\breve{w}_{ij}$ and model parameters of confirmation bias
$\breve{\epsilon}_{i}$ and negativity bias $\breve{\eta}_{i}$.

Figure 2: (i): Seventeen states’ model-based prediction errors; (ii)-(v): four
states’ real and predicted trajectories of ideology.

##  V Empirical Validation

In this section, we use US Senate Member Ideology data [38] to validate the
theoretical results and model from perspectives of generalization error and
model error. Since a senate member usually retires after (at most) twelve
congresses, it is not practical to model the state member as an individual in
our proposed opinion evolution model. Alternatively, an individual in our
model represents one US state, and her opinion corresponds to the average of
ideological data of senate members from the same state. Meanwhile, we model US
President as information source in our model. To perform validation, we use
the first-dimension ideological data obtained via Nokken-Poole estimation,
which describes the economic liberalism-conservatism of a member. We consider
the data of the 37th Congress to the 116th Congress, during which US President
is from Republican Party or Democratic Party. However, the ideology of US
President is not estimated [38]. As an alternate, we set the default ideology
of the president as $+1$ if the president is from the Republican Party, and
$-1$ if the president is from the Democratic Party.

We make the worst-case assumptions on noise, i.e.,
$\sigma_{\mathrm{o}}=\sigma_{\mathrm{p}}=1$. To guarantee Assumptions 1-3) and
1-4) hold, we choose $\gamma=1.59$, $\varrho_{1}=0.394$ and $\varrho_{2}=0.2$.
For matrix-norm bounds, we choose ${\overline{\mathfrak{s}}}=1$ and
${\underline{\mathfrak{s}}}=0.0001$. We set other parameters as
$\varepsilon=0.056$, $\rho=\frac{\varrho_{1}}{1.06}$, $\mathfrak{c}=9.5$ and
$\kappa=2\sqrt{2}$.

###  V-A Prediction Error

The dynamics (7) and (9) show that when the information sources hold extremal
opinions, the proposed model (1) transforms to linear stochastic systems but
have distinctive differences. This observation indicates that if the inferred
social systems are leveraged for prediction, the inferred switching model that
corresponds to (7) and (9), i.e.,

$\displaystyle y({k+1})$
$\displaystyle=\widehat{\underline{\alpha}}+\widehat{\underline{\mathcal{W}}}y(k),\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \text{Democratic Party}$ (47a)
$\displaystyle y({k+1})$
$\displaystyle=\widehat{\overline{\alpha}}+\widehat{\overline{\mathcal{W}}}y(k),\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \text{Republican Party}$ (47b)

would have smaller prediction error than that of a fixed social model,
e.g., DeGroot model [15] or Friedkin-Johnsen model [16]. For the comparison,
the fixed model via estimations (22) and (23) is Friedkin-Johnsen model based,
i.e.,

$\displaystyle y({k+1})=\widehat{{\alpha}}+\widehat{{\mathcal{W}}}y(k).$ (48)

We use the ideological data of 40th Congress to 106th Congress to infer models
and save the rest of data to measure prediction error. Meanwhile, we assume we
know that in the 116th, 115th and 107th–110th Congresses, US Presidents are
from Republican Party, while in the 111th-114th Congresses, US Presidents are
from Democratic Party. We follow the following procedure to perform the model-
based prediction.

  * •

We consider three group data: Republican Data (extracted if president is from
Republican Party), Democratic Data (extracted if president is from Democratic
Party) and Mixed Data (no separation).

  * •

We use the Democratic Data, Republican Data and Mixed Data to respectively
infer the sub-models (47b) and (47a) and the fixed model (48), via estimations
(22) and (23).

  * •

For the prediction, we input the ideological data of the 107th Congress as the
same initial condition for the switching model (47) and the fixed model (48).

  * •

From the 107th to 110th Congresses, we use model (47b) for prediction, from
the 111th to 114th Congresses, we switch to model (47a) for prediction, in the
115th and 116th Congresses, we switch back to model (47b) for prediction.

We note the sizes of Republican Data and Democratic Data are 38 and 28, which
means $(\underline{k},\underline{p})=(1,28)$ and
$(\overline{k},\overline{p})=(29,69)$. Then, following Corollary 1, for the
$(1.39,0.1)$-PAC, the allowed maximum network size is 17. Hence, we consider a
network with 17 US states. We denote individual $\mathrm{v}_{i}$’s predicted
ideology at congress number $k$ by $\breve{y}_{i}(k)$. We define the following
metric to measure prediction error:

$\displaystyle{e_{i}}=\frac{1}{{10}}\sum\limits_{k=107}^{116}{\left|{{y_{i}}(k)-{{\breve{y}}_{i}}(k)}\right|},i\\!\in\\!\\{\text{MD},\text{SC},\text{AL},\ldots,\text{IL},\text{FL}\\}.$

The seventeen states’ prediction errors, and the picked four states’ real
ideology and predicted trajectories are respectively shown in Figure 2
(i)-(v), observing which we discover that switching social model (47) with
guaranteed $(1.39,0.1)$-PAC has more accurate prediction than a single fixed
model (48).

###  V-B Model Error and Fitting Error

Figure 3: (a)-(f): Evolving ideology under 1000 random initial conditions;
(g)-(h): fitting curve and trajectories under five random initial conditions.

Differentiating from numerical examples and man-made systems, e.g., cyber-
physical systems, we do not have real exact model parameters as references to
straightforwardly measure model error pertaining to $(\phi,\delta)$–PAC.
Observing the structures of matrices and vectors in (8) and (10) and recalling
the convex combination (5), we can perform model validation from the following
social-system properties:

  * •

$0\leq{\overline{\alpha}_{i}}+\sum\limits_{j\in\mathbb{V}}{{{\left[\overline{\mathcal{W}}\right]}_{i,j}}}\leq
1$, $\forall i\in\mathbb{V}$.

  * •

The magnitudes of all entries of $\overline{\mathcal{W}}$ and
$\underline{\mathcal{W}}$ are smaller than one.

  * •

The fitting curve and the trajectories of inferred model under arbitrary
initial condition in $[-1,1]$, are all constrained into $[-1,1]$ for any time.

We now consider the ideological data of the 40th to 116th Congresses. The
sizes of Republican Data and Democratic Data are 44 and 32, which means
$(\underline{k},\underline{p})=(1,32)$ and
$(\overline{k},\overline{p})=(33,77)$. Following Corollary 1, for the
$(1,0.1)$-PAC, the allowed network size is 6. Then, by (22) and (23), we have
${\widehat{\overline{\alpha}}}$ $=$ $[0.0156$, $-0.0461$, $0.0985$, $0.1476$,
$0.0012$, $-0.0679]^{\top}$,

$\displaystyle\small\widehat{\overline{\mathcal{W}}}\\!=\\!\\!\left[\\!\\!\\!{\begin{array}[]{*{21}{c}}0.5252\\!\\!&\\!\\!0.0873\\!\\!&\\!\\!-0.1641\\!\\!&\\!\\!0.0730\\!\\!&\\!\\!-0.3392\\!\\!&\\!\\!-0.0049\\\
-0.2307\\!\\!&\\!\\!0.4495\\!\\!&\\!\\!-0.0037\\!\\!&\\!\\!0.1190\\!\\!&\\!\\!0.0151\\!\\!&\\!\\!0.1655\\\
-0.2311\\!\\!&\\!\\!0.0762\\!\\!&\\!\\!0.2090\\!\\!&\\!\\!0.1117\\!\\!&\\!\\!0.0155\\!\\!&\\!\\!0.1779\\\
0.0914\\!\\!&\\!\\!0.0030\\!\\!&\\!\\!0.1943\\!\\!&\\!\\!0.4089\\!\\!&\\!\\!0.0589\\!\\!&\\!\\!0.0940\\\
-0.1274\\!\\!&\\!\\!-0.0977\\!\\!&\\!\\!0.1578\\!\\!&\\!\\!0.0076\\!\\!&\\!\\!0.6119\\!\\!&\\!\\!0.1121\\\
-0.2357\\!\\!&\\!\\!0.0309\\!\\!&\\!\\!0.1071\\!\\!&\\!\\!0.1157\\!\\!&\\!\\!-0.0139\\!\\!&\\!\\!0.7037\end{array}}\\!\\!\\!\right]\\!\\!,$
(55)

from which we verify that $|{[\widehat{\overline{\mathcal{W}}}]}_{i,j}|<1$,
$\forall i,j\in\mathbb{V}$, and $\mathbf{0}<\widehat{\overline{\alpha}}$ \+
$\sum\limits_{j\in\mathbb{V}}{{[\widehat{\overline{\mathcal{W}}}]}_{:,j}}$ =
$[0.1928$, $0.4685$, $0.4578$, $0.9982$, $0.6654$,
$0.6399]^{\top}<\mathbf{1}$. Thus, the properties of social-system matrix are
demonstrated to hold. The trajectories of inferred model under 1000 randomly
generated initial conditions in $[-1,1]$ are shown in Figure 3 (a)-(f), which
shows that all of the trajectories are constrained into $[-1,1]$. By Algorithm
1, some individuals are inferred to have negativity bias. The results together
also demonstrate the correctness of the statement in Remark 1.

We next increase the size of social network to include all of the 30 states in
the 40th Congress. We recall that the size of Democratic Data is 32, which
implies the maximum size of social network is 30. We thus can conclude the
inference of the social network with 30 individuals hardly achieves any
$\left(\phi,\delta\right)$–PAC. In this setting, the fitting curve and the
five trajectories under random initial conditions in $[-1,1]$ are shown in
Figure 3 (g) and (h), which show that although the inferred model fit the real
data well, without satisfying high PAC, the inferred model has larger model
error such that its evolving ideology under some initial condition exceeds the
range $[-1,1]$ and the inferred model can be unstable.

##  VI Conclusion

In this paper, we have proposed an opinion evolution model which explicitly
takes confirmation bias, negativity bias and process noise into account. Based
on the proposed model, we have studied the problem of social system inference
of network topology, subconscious and model parameters of confirmation and
negativity bias. We have analyzed the sample complexity of the proposed
inference procedure in the presence of observation noise, which leads to the
statistical dependence of observed public evolving opinions on time and
coordinates. Real data validations suggest the effectiveness of the obtained
theoretical results and the proposed opinion evolution model.

Some of future directions are listed as follows.

  * •

We will investigate the sample complexity of social system inference in the
scenario that process and observation noise have time-varying means and
variances.

  * •

We will investigate cost function learning for learning-based competitive
information spread in social networks.

## Appendix A: Auxiliary Lemmas

###### Lemma 1

[36] Let $\mathbf{f}$ be a mean zero random vector in $\mathbb{R}^{n}$, whose
covariance matrix is denoted by $\mathrm{Cov}(\mathbf{f})$. If $\mathbf{f}$
has the convex concentration property with constant $\kappa$, then for any
$A\in\mathbb{R}^{n\times n}$ and every $t>0$, we have

$\displaystyle\mathbf{P}\\!\\!\left[{{\mathbf{f}^{\top}}A\mathbf{f}-\mathbf{E}\left[{{\mathbf{f}^{\top}}A\mathbf{f}}\right]\geq
t}\right]$ $\displaystyle\leq
2{e^{\left({-\frac{1}{{\mathfrak{c}{\kappa^{2}}}}\min\left\\{{\frac{{{t^{2}}}}{{\left\|A\right\|_{\mathrm{F}}^{2}\mathrm{Cov}(\mathbf{f})}},\frac{t}{{\left\|A\right\|}}}\right\\}}\right)}}\\!$

for some universal constant $\mathfrak{c}$.

###### Lemma 2

[39] Let $W$ be an $d\times d$ a symmetric random matrix. Furthermore, let
$\mathcal{N}$ be an $\varepsilon$-net of $\mathcal{S}^{d-1}$ with minimal
cardinality. Then for all $\rho>0$, we have

$\displaystyle\mathbf{P}\left[||W||>\rho\right]$
$\displaystyle\leq{({\frac{2}{\varepsilon}+1})^{n}}\mathop{\max}\limits_{\mathbf{u}\in\mathcal{N}}\mathbf{P}\left[{||W\mathbf{u}||_{2}>({1-\varepsilon})\rho}\right],\leavevmode\nobreak\
\varepsilon\in[0,1).$ (56) $\displaystyle\mathbf{P}\left[||W||>\rho\right]$
$\displaystyle\leq{({\frac{2}{\varepsilon}\\!+\\!1})^{n}}\mathop{\max}\limits_{\mathbf{u}\in\mathcal{N}}\mathbf{P}\left[{\left|{{\mathbf{u}^{\top}}W\mathbf{u}}\right|\\!>\\!({1\\!-\\!2\varepsilon})\rho}\right]\\!,\leavevmode\nobreak\
\varepsilon\in[0,\frac{1}{2}).$ (57)

###### Lemma 3

[37] Let $\\{\mathcal{F}_{t}\\}_{t\geq 1}$ be a filtration. Let
$\\{\eta_{t}\\}_{t\geq 1}$ be a stochastic process adapted to
$\\{\mathcal{F}_{t}\\}_{t\geq 1}$ and taking values in $\mathbb{R}$. Let
$\\{x_{t}\\}_{t\geq 1}$ be a predictable stochastic process with respect to
$\\{\mathcal{F}_{t}\\}_{t\geq 1}$, taking values in $\mathbb{R}^{d}$.
Furthermore, assume that $\eta_{t}$ is $\mathcal{F}_{k}$-measurable and
conditionally $\gamma$-sub-Gaussian for some $\gamma>0$. Let $S>0$,
$\eta^{\top}=[\eta_{2},\eta_{3},\ldots,\eta_{t+1}]$, and
$X^{\top}=[x_{1},x_{2},\ldots,x_{t}]$. The following

$\displaystyle\left\|\\!{{{\left({{X^{\top}}X\\!+\\!S}\right)}^{-0.5}}{X^{\top}}\eta}\right\|_{2}^{2}\\!\leq\\!2{\gamma^{2}}\\!\ln\\!\\!\left(\\!\\!{\frac{{{{\left({\det\\!\\!\left(\\!{\left({{X^{\top}}X\\!+\\!S}\right)\\!{S^{-1}}}\right)}\\!\right)}^{0.5}}}}{\delta}}\\!\right)$

holds with the probability of at least $1-\delta$.

## Appendix B: Proof of Proposition 1

It follows from (24) that

$\displaystyle\mathbf{E}[{\Psi_{(k,p)}^{\top}{X_{(k,p)}}X_{(k,p)}^{\top}{\Psi_{(k,p)}}}]=\mathbf{I}_{n},$
(58)

by which, we obtain that

$\displaystyle\left\|\varrho_{2}{{{({X_{(k,p)}^{\top}{\Psi_{(k,p)}}})^{\top}}}X_{(k,{p})}^{\top}{\Psi_{(k,p)}}-\varrho_{1}\mathbf{I}_{n}}\right\|$
$\displaystyle\\!=\\!\left\|{{{\varrho_{2}({X_{(k,p)}^{\top}{\Psi_{(k,p)}}})^{\top}}}X_{(k,p)}^{\top}{\Psi_{(k,p)}}}\right.$
$\displaystyle\hskip
108.12054pt\left.{-\varrho_{1}\mathbf{E}[{\Psi_{(k,p)}^{\top}{X_{(k,p)}}X_{(k,p)}^{\top}{\Psi_{(k,p)}}}]}\right\|$
$\displaystyle\\!=\\!\\!\mathop{\sup}\limits_{\mathbf{u}\in{\mathcal{S}^{n-1}}}\left|\varrho_{2}{{\mathbf{u}^{\top}}{{({X_{(k,p)}^{\top}{\Psi_{(k,p)}}})^{\top}}}X_{(k,p)}^{\top}{\Psi_{(k,p)}}\mathbf{u}}\right.$
$\displaystyle\hskip
88.2037pt\left.{-\varrho_{1}{\mathbf{u}^{\top}}\mathbf{E}[{\Psi_{(k,p)}^{\top}{X_{(k,p)}}X_{(k,p)}^{\top}{\Psi_{(k,p)}}}]\mathbf{u}}\right|$
$\displaystyle\\!=\\!\\!\mathop{\sup}\limits_{\mathbf{u}\in{\mathcal{S}^{n-1}}}\\!\\!\left|{\varrho_{2}||{X_{\\!(k,p)}^{\top}\\!{\Psi_{\\!(k,p)}}\mathbf{u}}||_{2}^{2}-\varrho_{1}\mathbf{E}||{X_{\\!(k,p)}^{\top}\\!{\Psi_{\\!(k,p)}}\mathbf{u}}||_{2}^{2}}\right|\\!.$
(59)

We obtain from (14)–(16) that for $j<\bar{k}$ or $g\geq\bar{k}$,

$\displaystyle\widetilde{\mathbf{y}}^{j}_{g}$
$\displaystyle\\!=\\!({\mathcal{M}_{g}^{\mathrm{c}}\\!-\\!\mathcal{M}_{j}^{\mathrm{c}}})x(1)\\!-\\!\sum\limits_{i=1}^{j-g}\\!{\mathcal{M}_{(i,j)}}\\!({{\alpha_{\vartheta(j-i)}}\\!+\\!\mathfrak{p}(j\\!-\\!i)})\\!+\\!\mathfrak{o}_{g}^{j}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
\\!+\\!\sum\limits_{i=1}^{g-1}\\!{\mathcal{M}_{(i,g)}}\\!(\mathbf{I}_{n}\\!-\\!\mathcal{M}_{(j-g+1,j)}\\!)({{\alpha_{\vartheta(g-i)}}\\!+\\!\mathfrak{p}(g\\!-\\!i)}).$
(60)

Then, observing $\mathbf{U}$ in (29), ${{\Upsilon}_{(k,p)}}$ in (28),
$X_{(k,p)}$ in (20), and relation (32), we have

$\displaystyle
X_{(k,p)}^{\top}{\Psi_{(k,p)}}\mathbf{u}=\mathbf{U}^{\top}{{\Upsilon}^{\top}_{(k,p)}}{{\Pi}_{({k,p})}}({{\overline{\theta}}_{(k,p)}}+{{\underline{\theta}}_{(k,p)}}),$
(61)

substituting which into (59), we arrive at

$\displaystyle||\varrho_{2}{{{({X_{({k},{p})}^{\top}{\Psi_{(k,p)}}})^{\top}}}X_{(k,p)}^{\top}{\Psi_{(k,p)}}-\varrho_{1}\mathbf{I}_{n}}||$
$\displaystyle=\mathop{\sup}\limits_{\mathbf{u}\in{\mathcal{S}^{n-1}}}\left|{\varrho_{2}||\mathbf{U}^{\top}{{\Upsilon}^{\top}_{(k,p)}}{{\Pi}_{({k,p})}}{({{\overline{\theta}}_{(k,p)}}+{{\underline{\theta}}_{(k,p)}})}||_{2}^{2}}\right.$
$\displaystyle\hskip
42.67912pt\left.{-\varrho_{1}\mathbf{E}||\mathbf{U}^{\top}{{\Upsilon}^{\top}_{(k,p)}}{{\Pi}_{({k,p})}}({{\overline{\theta}}_{(k,p)}}+{{\underline{\theta}}_{(k,p)}})||_{2}^{2}}\right|\\!.$
(62)

We note that (58), in conjunction with (59) and (61), implies
$\mathbf{E}||{X_{(\vartheta(k),p)}^{\top}{\Psi_{(k,p)}}\\!\mathbf{u}}||_{2}^{2}=\mathbf{E}||\mathbf{U}^{\top}{{\Upsilon}^{\top}_{(k,p)}}{{\Pi}_{({k,p})}}({{\overline{\theta}}_{(k,p)}}+{{\underline{\theta}}_{(k,p)}})||_{2}^{2}=1$,
which thus with (62) and Assumption 1-4) indicate that

$\displaystyle\left|{||{{\bf{U}}^{\top}}\Upsilon_{(k,p)}^{\top}{\Pi_{(k,p)}}{\overline{\theta}_{(k,p)}}||_{2}^{2}-{\bf{E}}||{{\bf{U}}^{\top}}\Upsilon_{(k,p)}^{\top}{\Pi_{(k,p)}}{\overline{\theta}_{(k,p)}}||_{2}^{2}}\right|$
$\displaystyle=\left|{||{{\bf{U}}^{\top}}\Upsilon_{(k,p)}^{\top}{\Pi_{(k,p)}}{\overline{\theta}_{(k,p)}}||_{2}^{2}}\right.+||{{\bf{U}}^{\top}}\Upsilon_{(k,p)}^{\top}{\Pi_{(k,p)}}{\underline{\theta}_{(k,p)}}||_{2}^{2}$
$\displaystyle\hskip
39.83368pt\left.{-{\bf{E}}||{{\bf{U}}^{\top}}\Upsilon_{(k,p)}^{\top}{\Pi_{(k,p)}}({\overline{\theta}_{(k,p)}}+{\underline{\theta}_{(k,p)}})||_{2}^{2}}\right|$
(63)
$\displaystyle\geq\left|{\varrho_{2}||{{\bf{U}}^{\top}}\Upsilon_{(k,p)}^{\top}{\Pi_{(k,p)}}({\overline{\theta}_{(k,p)}}+{\underline{\theta}_{(k,p)}})||_{2}^{2}}\right.$
$\displaystyle\hskip
39.83368pt\left.{-\varrho_{1}{\bf{E}}||{{\bf{U}}^{\top}}\Upsilon_{(k,p)}^{\top}{\Pi_{(k,p)}}({\overline{\theta}_{(k,p)}}+{\underline{\theta}_{(k,p)}})||_{2}^{2}}\right|,$
(64)

where (63) from previous step is obtained via considering

$\displaystyle{\bf{E}}||{{\bf{U}}^{\top}}\Upsilon_{(k,p)}^{\top}{\Pi_{(k,p)}}({\overline{\theta}_{(k,p)}}+{\underline{\theta}_{(k,p)}})||_{2}^{2}$
$\displaystyle={\bf{E}}||{{\bf{U}}^{\top}}\Upsilon_{(k,p)}^{\top}{\Pi_{(k,p)}}\overline{\theta}_{(k,p)}||_{2}^{2}+||{{\bf{U}}^{\top}}\Upsilon_{(k,p)}^{\top}{\Pi_{(k,p)}}{\underline{\theta}_{(k,p)}}||_{2}^{2},$

which is due to Assumption 1-1) and definitions in (25)–(26).

Let us define:

$\displaystyle\Delta_{(k,p)}\triangleq{{\Pi}^{\top}_{({k,p})}}{{\Upsilon}_{(k,p)}}\mathbf{U}\mathbf{U}^{\top}{{\Upsilon}^{\top}_{(k,p)}}{{\Pi}_{({k,p})}},$
(65)

which follows from $\mathbf{u}\in\mathcal{S}^{n-1}$, (29), (31a) and the well-
known inequalities $||{AB}||$ $\leq$ $||A||||B||$ and $||{AB}||_{\mathrm{F}}$
$\leq$ $||A||||B||_{\mathrm{F}}$ that

$\displaystyle||\Delta_{\\!(k,p)}||^{2}_{\mathrm{F}}$
$\displaystyle\\!\leq\\!||{\Pi^{\top}_{\\!({k,p})}}\\!\\!{{\Upsilon}_{\\!(k,p)}}\\!||^{4}||\mathbf{U}||^{2}||\mathbf{U}||^{2}_{\mathrm{F}}\\!\leq\\!\frac{||{\Pi^{\top}_{\\!({k,p})}}\\!\\!{{\Upsilon}_{\\!(k,p)}}\\!||^{4}\mathfrak{l}_{(k,p)}}{n}$

and
$||\Delta_{(k,p)}||\leq||{\Pi^{\top}_{({k,p})}}{{\Upsilon}_{(k,p)}}||^{2}$,
which with $\rho>0$ imply

$\displaystyle\min\\!\left\\{\\!{\frac{{{\rho^{2}}}}{{||\Delta_{(k,p)}||_{\mathrm{F}}^{2}||{\overline{\mathcal{C}}}_{(k,p)}||}},\leavevmode\nobreak\
\frac{{\rho}}{{||\Delta_{(k,p)}||}}}\\!\right\\}$
$\displaystyle\\!\geq\\!\min\\!\left\\{\\!{\frac{{{n\rho^{2}}}}{{\mathfrak{l}_{(k,p)}||\Pi_{\\!(k,p)}^{\top}\\!\\!{\Upsilon_{\\!(k,p)}}\\!||^{4}||{{\overline{\mathcal{C}}}_{\\!(k,p)}}\\!||}}}\right.\\!,\left.{\frac{\rho}{{||\Pi_{\\!(k,p)}^{\top}\\!\\!{\Upsilon_{\\!(k,p)}}\\!||^{2}}}}\\!\right\\}.$
(66)

Under Assumption 1-1), we first verify from (26) and (25) with (27) that
${\overline{\theta}_{({k,p})}}$ has zero mean. Since $\mathfrak{c}>0$ and
$\rho>0$, under Assumption 1-2), applying Lemma 1 (in Appendix A) with (66)
and (65), we conclude that

$\displaystyle\left|{||{{\Upsilon}_{(k,p)}^{\top}{{\Pi}_{(k,p)}}{{\overline{\theta}}_{(k,p)}}}\\!||_{2}^{2}-{\bf{E}}||{{\Upsilon}_{(k,p)}^{\top}{{\Pi}_{(k,p)}}{{\overline{\theta}}_{(k,p)}}}\\!||_{2}^{2}}\right|>\rho$

holds with probability at most

$\displaystyle
2e^{\frac{-1}{{\mathfrak{c}{\kappa^{2}}}}\\!\min\left\\{\\!{\frac{{{n\rho^{2}}}}{{\mathfrak{l}_{(k,p)}||\Pi_{\\!(k,p)}^{\top}\\!\\!{\Upsilon_{\\!(k,p)}}\\!||^{4}||{{\overline{\mathcal{C}}}_{\\!(k,p)}}\\!||}}}\right.\\!,\left.{\frac{\rho}{{||\Pi_{\\!(k,p)}^{\top}\\!\\!{\Upsilon_{\\!(k,p)}}\\!||^{2}}}}\\!\right\\}}\\!,$

where
${\overline{\mathcal{C}}}_{({k},{p})}\triangleq{\bf{E}}[{\overline{\theta}}_{({{k},{p}})}{\overline{\theta}}^{\top}_{({{k},{p}})}]$.
It follows from ${\overline{\theta}}_{({{k},{p}})}$ in (26) and
${\mathcal{C}}_{({k},{p})}$ in (35) that
$||{\overline{\mathcal{C}}}_{({k},{p})}||=||{{\mathcal{C}}}_{({k},{p})}||$,
noting which, (62), (64) and (66) we conclude that

$\displaystyle||{{\varrho_{2}({X_{(k,p)}^{\top}{\Psi_{(k,p)}}})^{\top}}X_{(k,p)}^{\top}{\Psi_{(k,p)}}-\varrho_{1}{\bf{I}_{n}}}||$
$\displaystyle\\!=\\!\\!\mathop{\sup}\limits_{\mathbf{u}\in{\mathcal{S}^{n-1}}}\\!\\!\\!\\!|{{\mathbf{u}^{\top}}\\!\\!({{{\varrho_{2}(\\!{X_{\\!(k,p)}^{\top}\\!{\Psi_{\\!(k,p)}}}\\!)^{\top}}}\\!X_{\\!(k,p)}^{\top}\\!{\Psi_{\\!(k,p)}}\\!-\\!\varrho_{2}{\bf{I}_{n}}})\mathbf{u}}|\\!\geq\\!(1\\!-\\!2\varepsilon)\rho$

holds with probability at most

$\displaystyle
2e^{\frac{-1}{{\mathfrak{c}{\kappa^{2}}}}\\!\min\left\\{{\frac{{{n(1-2\varepsilon)^{2}\rho^{2}}}}{{\mathfrak{l}_{(k,p)}||\Pi_{(k,p)}^{\top}{\Upsilon_{(k,p)}}||^{4}||{{{\mathcal{C}}}_{(k,p)}}||}}}\right.,\leavevmode\nobreak\
\left.{\frac{(1-2\varepsilon)\rho}{{||\Pi_{(k,p)}^{\top}\\!\\!{\Upsilon_{(k,p)}}||^{2}}}}\\!\right\\}},$

Then, applying (57) in Lemma 2 leads to Proposition 1.

## Appendix C: Proof of Theorem 1

Observing the relation (21) and the optimal estimation (22), we obtain
$\widehat{\mathcal{A}}_{\vartheta(k)}\\!-\\!{{\mathcal{A}}_{\vartheta(k)}}$
$\\!=\\!$
${{U}}_{(k,p)}{X}^{\top}_{(k,p)}{({X}_{(k,p)}{X}^{\top}_{(k,p)})^{-1}}$. Thus,

$\displaystyle||\widehat{\mathcal{A}}_{\vartheta(k)}-{{\mathcal{A}}_{\vartheta(k)}}||$
$\displaystyle\\!=\\!||{{U}}_{(k,p)}{X}^{\top}_{(k,p)}{({X}_{(k,p)}{X}^{\top}_{(k,p)})^{-1}}||$
$\displaystyle\\!\leq\\!||{{U}}_{(k,p)}{X}^{\top}_{(k,p)}{({X}_{(k,p)}{X}^{\top}_{(k,p)})^{-0.5}}||||{{{({{{X}_{(k,p)}}X_{(k,p)}^{\top}})^{-0.5}}}}||,$

for which we define two events:

$\displaystyle{\mathfrak{E}_{1}}$
$\displaystyle\triangleq\left\\{||{{U}}_{(k,p)}{X}^{\top}_{(k,p)}{({X}_{(k,p)}{X}^{\top}_{(k,p)})^{-0.5}}||\right.$
$\displaystyle\hskip
88.2037pt\left.{\cdot||{{{({{{X}_{(k,p)}}X_{(k,p)}^{\top}})^{-0.5}}}}||>\phi}\right\\},$
(67) $\displaystyle{\mathfrak{E}_{2}}$
$\displaystyle\triangleq\left\\{{||{\varrho_{2}{\Psi^{\top}_{(k,p)}}{X_{(k,p)}}X_{(k,p)}^{\top}{{\Psi_{(k,p)}}}-\varrho_{1}\mathbf{I}_{n}}||\leq\rho}\right\\},$
(68)

from which we have

$\displaystyle\mathbf{P}[||\widehat{\mathcal{A}}_{\vartheta(k)}-{{\mathcal{A}}_{\vartheta(k)}}||>\phi]\leq\mathbf{P}[{\mathfrak{E}_{1}}\bigcap{{\mathfrak{E}_{2}}}]+\mathbf{P}[\mathfrak{E}_{2}^{\mathrm{c}}].$
(69)

We next derive the upper bounds on
$\mathbf{P}({\mathfrak{E}_{2}^{\mathrm{c}}})$ and
$\mathbf{P}({{\mathfrak{E}_{1}}\bigcap{{\mathfrak{E}_{2}}}})$.

#### Upper Bound on $\mathbf{P}({\mathfrak{E}_{2}^{\mathrm{c}}})$

Let us set $\gamma=\sqrt{2\mathfrak{c}}\kappa$, inserting which into (38)
results in

$\displaystyle\min\\!\left\\{\\!{\frac{{{{(1-2\varepsilon)}^{2}}n{\rho^{2}}}}{{\mathfrak{l}_{(k,p)}||\Pi_{(k,p)}^{\top}{\Upsilon_{(k,p)}}||^{4}||{\mathcal{C}_{(k,p)}}||}},\leavevmode\nobreak\
\frac{{(1-2\varepsilon)\rho}}{{||\Pi_{(k,p)}^{\top}{\Upsilon_{(k,p)}}\\!||^{2}}}}\\!\right\\}$
$\displaystyle\geq\mathfrak{c}{\kappa^{2}}\ln\frac{{4\cdot{({\frac{2}{\varepsilon}+1})^{n}}}}{\delta},$

which is equivalent to

$\displaystyle
2\\!\cdot\\!{({\frac{2}{\varepsilon}\\!+\\!1})^{n}}\\!\cdot\\!{e^{\\!\frac{-1}{{\mathfrak{c}{\kappa^{2}}}}\\!\min\left\\{\\!\\!{\frac{{{{(1-2\varepsilon)}^{2}}n{\rho^{2}}}}{{\mathfrak{l}_{(k,p)}\\!||\Pi_{\\!(k,p)}^{\top}\\!\\!{\Upsilon_{\\!(k,p)}}\\!||^{4}||{\mathcal{C}_{\\!(k,p)}}\\!||}},\frac{{(1-2\varepsilon)\rho}}{{||\Pi_{\\!(k,p)}^{\top}\\!{\Upsilon_{\\!(k,p)}}\\!||^{2}}}}\\!\\!\right\\}}}\\!\leq\\!\frac{\delta}{2}$

which together with Proposition 1 imply that when (38) holds:

$\displaystyle\mathbf{P}({\mathfrak{E}_{2}^{\mathrm{c}}})\leq\frac{\delta}{2}.$
(70)

#### Upper Bound on
$\mathbf{P}({{\mathfrak{E}_{1}}\bigcap{{\mathfrak{E}_{2}}}})$

When ${\mathfrak{E}_{2}}$ occurs, we have

$\displaystyle{\frac{\varrho_{1}-\rho}{\varrho_{2}}}\mathbf{I}_{n}\leq{\Psi^{\top}_{(k,p)}}{X_{(k,p)}}X^{\top}_{(k,p)}{\Psi_{(k,p)}}\leq{\frac{\varrho_{1}+\rho}{\varrho_{2}}}\mathbf{I}_{n},$

where $0<\rho<\varrho_{1}$. We then have

$\displaystyle{\frac{\varrho_{1}-\rho}{\varrho_{2}}}\Psi^{-2}_{(k,p)}\leq{X_{(k,p)}}X_{(k,p)}^{\top}\leq{\frac{\varrho_{1}+\rho}{\varrho_{2}}}\Psi^{-2}_{(k,p)},$
(71)

which implies

$\displaystyle\lambda^{0.5}_{\min}({X_{(k,p)}}X_{(k,p)}^{\top})\geq\lambda^{0.5}_{\min}({\frac{\varrho_{1}-\rho}{\varrho_{2}}}{\Psi^{-2}_{(k,p)}})\triangleq\breve{\beta}.$
(72)

We note that

$\displaystyle||\\!{{{({{X_{\\!(k,p)}}X_{\\!(k,p)}^{\top}})^{0.5}}}}\\!||\\!=\\!\lambda_{\max}^{0.5}\\!(\\!{{X_{\\!(k,p)}}X_{\\!(k,p)}^{\top}}\\!)\\!\geq\\!\lambda_{\min}^{0.5}\\!(\\!{{X_{\\!(k,p)}}X_{\\!(k,p)}^{\top}}\\!),$

by which and (72), we obtain
$\frac{1}{\breve{\beta}}\geq||{{{({{X_{(k,p)}}X_{(k,p)}^{\top}})}^{-0.5}}}||$.
We then conclude from (67) and (68) that

$\displaystyle\\!{\mathfrak{E}_{1}}\\!\bigcap\\!{\mathfrak{E}_{2}}\\!\subseteq\\!\\!\left\\{\\!{||{{U}}_{\\!(k,p)}\\!{X}^{\top}_{\\!(k,p)}\\!{({X}_{\\!(k,p)}\\!{X}^{\top}_{\\!(k,p)})^{-0.5}}||\\!>\\!\breve{\beta}\phi}\\!\right\\}\\!\bigcap\\!{\mathfrak{E}_{2}}.$
(73)

The left-hand inequality of (71) implies

$\displaystyle
2{X_{(k,p)}}X_{(k,p)}^{\top}\geq{\frac{\varrho_{1}-\rho}{\varrho_{2}}}\Psi_{(k,p)}^{-2}+{X_{(k,p)}}X_{(k,p)}^{\top},$

which means, with $0<\rho<1$, that

$\displaystyle{({{X_{(k,p)}}X_{(k,p)}^{\top}})^{-1}}\leq
2{({{\frac{\varrho_{1}-\rho}{\varrho_{2}}}\Psi_{(k,p)}^{-2}+{X_{(k,p)}}X_{(k,p)}^{\top}})^{-1}},$

which, in conjunction with (73), leads to

$\displaystyle{\mathfrak{E}_{1}}\\!\bigcap\\!{{\mathfrak{E}_{2}}}$
$\displaystyle\\!\subseteq\\!\\!\left\\{\\!\\!{\sqrt{2}||{{{U}}_{\\!(k,p)}\\!{X}^{\top}_{\\!(k,p)}\\!{{({{S}\\!+\\!{X_{\\!(k,p)}}\\!X_{\\!(k,p)}^{\top}})}^{-0.5}}}||\\!>\\!\breve{\beta}\phi}\\!\right\\}\\!\bigcap\\!{{\mathfrak{E}_{2}}},$
(74)

where we denote

$\displaystyle
S\triangleq{\frac{\varrho_{1}-\rho}{\varrho_{2}}}\Psi_{(k,p)}^{-2}.$ (75)

With $\mathbf{u}\in\mathcal{S}^{n-1}$, we now define two additional events:

$\displaystyle{\mathfrak{A}_{1}}\\!\triangleq\\!\left\\{\\!{{{||{{{({S+{X_{(k,p)}}X_{(k,p)}^{\top}})^{-0.5}}}X_{(k,p)}}{{U}}^{\top}_{(k,p)}||}^{2}}}\right.$
$\displaystyle\hskip
31.2982pt\left.{\\!>\\!16\mathfrak{c}{\kappa^{2}}\\!\ln(\\!{{{(\\!{\det(\\!{({S\\!+\\!{X_{\\!(k,p)}}X_{\\!(k,p)}^{\top}}\\!)\\!{S^{-1}}}\\!)}\\!)}^{0.5}}\\!\delta^{-1}_{0}})}\\!\right\\}\\!\\!,$
(76)
$\displaystyle{\mathfrak{A}_{2}}\\!(\mathbf{u})\\!\triangleq\\!\left\\{\\!{{{||{{{({S+{X_{(k,p)}}X_{(k,p)}^{\top}})}^{-0.5}}\\!X_{(k,p)}{{U}}^{\top}_{(k,p)}\mathbf{u}}||_{2}^{2}}}}\right.$
$\displaystyle\hskip
36.98866pt\left.{\\!>\\!4\mathfrak{c}{\kappa^{2}}\\!\ln({{{\\!(\\!{\det(\\!{({S\\!+\\!\\!{X_{\\!(k,p)}}X_{\\!(k,p)}^{\top}})\\!{S^{-1}}})})}^{0.5}}\\!\delta^{-1}_{0}})}\\!\right\\}\\!\\!.$
(77)

We note that under Assumption 1-3), $\mathbf{u}\in\mathcal{S}^{n-1}$ implies
that $(\widehat{\mathfrak{g}}^{j+1}_{\vartheta(k+1)})^{\top}\mathbf{u}$ is
$\mathcal{F}_{k}$-measurable and conditionally $\gamma$-sub-Gaussian for some
$\gamma>0$. Meanwhile, we note that $4\mathfrak{c}{\kappa^{2}}=2{\gamma^{2}}$.
In light of Lemma 3 in Appendix A, we then have
$\mathbf{P}[{\mathfrak{A}_{2}}(\mathbf{u})]\leq\delta_{0}$. Furthermore,
applying (56) with the setting of $\varepsilon=\frac{1}{2}$ in Lemma 2, we
obtain

$\displaystyle\mathbf{P}[{\mathfrak{A}_{1}}]\leq{5^{n}}\mathop{\max}\limits_{\mathbf{u}\in\mathcal{N}}\mathbf{P}[{{\mathfrak{A}_{2}(\mathbf{u})}}]\leq{5^{n}}{\delta_{0}}.$
(78)

We let ${\delta_{0}}=\frac{\delta}{{2\cdot{5^{n}}}}$, such that

$\displaystyle\breve{\beta}$
$\displaystyle\geq\frac{{4\sqrt{2\mathfrak{c}}\kappa}}{\phi}\sqrt{\ln\left(\frac{{2\cdot{5^{1.5n}}}}{\delta}{{\left({\frac{{\varrho_{1}-\rho}}{{10\varrho_{1}}}}\right)}^{0.5n}}\right)}$
$\displaystyle\\!=\\!\frac{{4\sqrt{2\mathfrak{c}}\kappa}}{\phi}\sqrt{\ln\left(\frac{{2\cdot{5^{1.5n}}}}{{2\cdot{5^{n}}\cdot{\delta_{0}}\cdot{5^{0.5n}}}}{{\left({\frac{{\varrho_{1}-\rho}}{2\varrho_{1}}}\right)}^{0.5n}}\right)}$
$\displaystyle\\!=\\!\frac{{4\sqrt{2\mathfrak{c}}\kappa}}{\phi}\sqrt{\ln\left({\frac{1}{{{\delta_{0}}}}{{\left({\det\left({\left({S+\frac{{\varrho_{1}+\rho}}{{\varrho_{1}-\rho}}S}\right){S^{-1}}}\right)}\right)}^{-0.5}}}\right)}$
$\displaystyle\\!\geq\\!\frac{{4\sqrt{2\mathfrak{c}}\kappa}}{\phi}\\!\sqrt{\ln\\!\left(\\!{\frac{1}{{{\delta_{0}}}}\\!{{\left({\det({\\!({S\\!+\\!{X_{(k,p)}}X_{(k,p)}^{\top}}){S^{-1}}}\\!)}\\!\right)^{-0.5}}}}\\!\right)}\\!,$
(79)

where the last inequality from its previous step is obtained via considering
the inequality
${X_{(k,p)}}X_{(k,p)}^{\top}\leq\frac{{\varrho_{1}+\rho}}{{\varrho_{1}-\rho}}S$
that follows from (75) and (71).

Combining the inequality in (74) with (79) yields

$\displaystyle||{{{U}}_{(k,p)}{X}^{\top}_{(k,p)}{{({S+{X_{(k,p)}}X_{(k,p)}^{\top}})}^{-0.5}}}||$
$\displaystyle\\!>\\!\frac{{\breve{\beta}\phi}}{{\sqrt{2}}}\\!\geq\\!4\sqrt{\mathfrak{c}}\kappa\sqrt{\ln({\frac{1}{{{\delta_{0}}}}{{({\det(({S\\!+\\!{X_{(k,p)}}X_{(k,p)}^{\top}){S^{-1}}})})^{-0.5}}}})},$

by which, and considering (74) and (76), we deduce that under condition (79),
if the event ${\mathfrak{E}_{1}}$ occurs, the event ${\mathfrak{A}_{1}}$
occurs consequently. We thus obtain

$\displaystyle\mathbf{P}[{\mathfrak{E}_{1}}\bigcap{{\mathfrak{E}_{2}}}]\leq\mathbf{P}[{{\mathfrak{A}_{1}}}\bigcap{{\mathfrak{E}_{2}}}].$
(80)

We note that the condition (39) is equivalent to

$\displaystyle\lambda_{\min}^{0.5}({\frac{\varrho_{1}-\rho}{\varrho_{2}}{\Gamma_{(k,p)}}})\\!\geq\\!\frac{{4\sqrt{2\mathfrak{c}}\kappa}}{\phi}\\!\sqrt{\\!\ln\\!\left({\frac{{2\\!\cdot\\!{5^{1.5n}}}}{\delta}{{\left({\frac{{\varrho_{1}-\rho}}{{10\varrho_{1}}}}\right)}^{0.5n}}}\right)}\\!,$

inserting $\breve{\beta}$ in (72) with $\Gamma_{({k,p})}$ in (24) into which
yields

$\displaystyle\breve{\beta}\geq\frac{{4\sqrt{2\mathfrak{c}}\kappa}}{\phi}\\!\sqrt{\\!\ln\\!\left(\\!{\frac{{2\cdot{5^{1.5n}}}}{\delta}{{\left(\\!{\frac{{\varrho_{1}-\rho}}{{10\varrho_{1}}}}\\!\right)}^{0.5n}}}\\!\right)},$

by which we conclude that (79) holds if the condition (39) is satisfied.
Moreover, recalling that the event $\mathfrak{E}_{2}$ always occurs under the
condition (38) (proved in Upper Bound on
$\mathbf{P}({\mathfrak{E}_{2}^{\mathrm{c}}})$), we conclude from (80) and (78)
that

$\displaystyle\mathbf{P}[{{\mathfrak{E}_{1}}\bigcap{{\mathfrak{E}_{2}}}}]\leq\mathbf{P}[{\mathfrak{A}_{1}}]\leq{5^{n}}{\delta_{0}}$

holds as long as both (38) and (39) hold. In addition, due to
${\delta_{0}}=\frac{\delta}{{2\cdot{5^{n}}}}$, we have

$\displaystyle\mathbf{P}[{{\mathfrak{E}_{1}}\bigcap{{\mathfrak{E}_{2}}}}]\leq\frac{\delta}{2}.$
(81)

Finally, combining (69) with (70) and (81) yields (37).

## Appendix D: Proof of Corollary 1

#### Condition (45)

Under Assumption 1-1), we obtain from (60) and (40) that

$\displaystyle\mathbf{E}[\widetilde{\mathbf{y}}^{j}_{g}(\widetilde{\mathbf{y}}^{j}_{g})^{\top}]$
$\displaystyle\\!\geq\\!\mathbf{E}[\mathfrak{o}_{g}^{j}(\mathfrak{o}_{g}^{j})\\!^{\top}]\\!+\\!\\!\sum\limits_{i=1}^{g-1}\\!{\mathcal{M}_{\\!(i,g)}}\\!(\mathbf{I}_{n}\\!-\\!\\!\mathcal{M}_{\\!(j-g+1,j)}\\!)\mathbf{E}[\mathfrak{p}(g\\!-\\!j)\mathfrak{p}\\!^{\top}\\!\\!(g\\!-\\!j)]$
$\displaystyle\cdot\\!(\mathbf{I}_{n}\\!-\\!\mathcal{M}_{\\!(j-g+1,j)}\\!)\\!^{\top}\\!\\!{\mathcal{M}^{\top}_{\\!(i,g)}}\\!+\\!\\!\sum\limits_{i=1}^{j-g}\\!{\mathcal{M}_{(i,j)}}\\!\mathbf{E}[\mathfrak{p}(j\\!-\\!i)\mathfrak{p}\\!^{\top}\\!\\!(j\\!-\\!i)]\mathcal{M}^{\top}_{\\!(i,j)}$
$\displaystyle\geq
2\sigma^{2}_{\mathrm{o}}\mathbf{I}_{n}+(j-1)\sigma^{2}_{\mathrm{p}}{\underline{\mathfrak{s}}}\mathbf{I}_{n},$

which together with (24) lead to

$\displaystyle{\Gamma_{({k,p})}}\geq
2\frac{{\mathfrak{l}_{(k,p)}}}{n}\sigma^{2}_{\mathrm{o}}\mathbf{I}_{n}+\underline{\mathfrak{s}}\frac{{\widehat{\mathfrak{l}}_{(k,p)}}}{n}\sigma^{2}_{\mathrm{p}}\mathbf{I}_{n},$

where $\mathfrak{l}_{(k,p)}$ and $\widehat{\mathfrak{l}}_{(k,p)}$ are given in
(31a) and (43), respectively. As a consequence, we have

$\displaystyle{\lambda_{\min}}(\Gamma_{({k,p})})\geq
2\frac{{\mathfrak{l}_{(k,p)}}}{n}\sigma^{2}_{\mathrm{o}}+\underline{\mathfrak{s}}\frac{{\widehat{\mathfrak{l}}_{(k,p)}}}{n}\sigma^{2}_{\mathrm{p}}=\mathfrak{f}_{(k,p)},$
(82)

which implies that (39) holds if (45) is satisfied.

#### Condition (44)

With the consideration of (41), it follows from (28) and (30) with (31) that
${||{{\Upsilon}_{(k,p)}}||^{2}}={||\Psi_{(k,p)}||^{2}}$. We obtain from (24)
and (82) that
$\Psi_{({k,p})}^{2}\leq\frac{{{{\bf{I}}_{n}}}}{2\frac{{\mathfrak{l}_{(k,p)}}}{n}\sigma^{2}_{\mathrm{o}}+\underline{\mathfrak{s}}\frac{{\widehat{\mathfrak{l}}_{(k,p)}}}{n}\sigma^{2}_{\mathrm{p}}}$,
which thus leads to

$\displaystyle{||{{\Upsilon}_{(k,p)}}||^{2}}\leq\frac{1}{2\frac{{\mathfrak{l}_{(k,p)}}}{n}\sigma^{2}_{\mathrm{o}}+\underline{\mathfrak{s}}\frac{{\widehat{\mathfrak{l}}_{(k,p)}}}{n}\sigma^{2}_{\mathrm{p}}}.$
(83)

Considering (41) and (83) and recalling the well-known inequality
$\left\|AB\right\|\leq\left\|A\right\|\left\|B\right\|$, we arrive at

$\displaystyle||{{\Pi}^{\top}_{(k,p)}}{{\Upsilon}_{(k,p)}}||^{2}$
$\displaystyle\leq||{{\Pi}_{(k,p)}}||^{2}||{{\Upsilon}_{(k,p)}}||^{2}\leq{\mathfrak{j}_{(k,p)}},$
(84)

where ${\mathfrak{j}_{(k,p)}}$ is given in (42). We note that (84) implies

$\displaystyle\min\\!\left\\{\\!{\frac{{{{(1-2\varepsilon)}^{2}}n{\rho^{2}}}}{{\mathfrak{l}_{(k,p)}||\Pi_{(k,p)}^{\top}{\Upsilon_{(k,p)}}||^{4}||{\mathcal{C}_{(k,p)}}||}},\leavevmode\nobreak\
\frac{{(1-2\varepsilon)\rho}}{{||\Pi_{(k,p)}^{\top}{\Upsilon_{(k,p)}}||^{2}}}}\\!\right\\}$
$\displaystyle\geq\min\\!\left\\{\\!{\frac{{{{(1-2\varepsilon)}^{2}}n{\rho^{2}}}}{{\mathfrak{l}_{(k,p)}{\mathfrak{j}^{2}_{(k,p)}}||{\mathcal{C}_{(k,p)}}||}},\leavevmode\nobreak\
\frac{{(1-2\varepsilon)\rho}}{{{\mathfrak{j}_{(k,p)}}}}}\\!\right\\},$

which indicates that if (44) is satisfied, (38) holds.

## Appendix E: Proof of Theorem 2

We obtain from (46) that

$\displaystyle[\widehat{\mathfrak{a}}_{+1}]_{i}-[\widehat{\mathfrak{a}}_{-1}]_{i}=2({\breve{\epsilon}_{i}+{\breve{\eta}_{i}}}),$
(85)
$\displaystyle[\widehat{\mathfrak{a}}_{+1}]_{i}+[\widehat{\mathfrak{a}}_{-1}]_{i}=2({1-\sum\limits_{j\in\mathbb{V}}{{\breve{w}_{ij}}}}){\breve{s}_{i}}-2({{\breve{\epsilon}_{i}}+{\breve{\eta}_{i}}}){\breve{s}_{i}},$
(86)
$\displaystyle\sum\limits_{j\in\mathbb{V}}{({{{[\widehat{\mathcal{A}}_{+1}]}_{i,j}}-{{[\widehat{\mathcal{A}}_{-1}]}_{i,j}}})}=2({\breve{\eta}_{i}}-{\breve{\epsilon}_{i}}){\breve{s}_{i}},$
(87)
$\displaystyle\sum\limits_{j\in\mathbb{V}}{({{{[\widehat{\mathcal{A}}_{+1}]}_{i,j}}+{{[\widehat{\mathcal{A}}_{-1}]}_{i,j}}})}=2\sum\limits_{j\in\mathbb{V}}{{\breve{w}_{ij}}}-2{\breve{\eta}_{i}}+2{\breve{\epsilon}_{i}}.$
(88)

Combining (85) with (86) yields

$\displaystyle\frac{1}{\breve{s}_{i}}([\widehat{\mathfrak{a}}_{+1}]_{i}\\!+\\![\widehat{\mathfrak{a}}_{-1}]_{i})\\!=\\!2({1\\!-\\!\sum\limits_{j\in\mathbb{V}}{{\breve{w}_{ij}}}})\\!-\\!([\widehat{\mathfrak{a}}_{+1}]_{i}\\!-\\![\widehat{\mathfrak{a}}_{-1}]_{i}).$
(89)

Meanwhile, combining (87) with (88) leads to

$\displaystyle\frac{1}{\breve{s}_{i}}\\!\sum\limits_{\\!j\in\mathbb{V}}\\!\\!{({{{[\widehat{\mathcal{A}}_{+1}]}_{i,j}}\\!-\\!{{[\widehat{\mathcal{A}}_{-1}]}_{i,j}}}\\!)}\\!=\\!2\\!\sum\limits_{\\!j\in\mathbb{V}}\\!{{\breve{w}_{ij}}}\\!-\\!\\!\sum\limits_{\\!j\in\mathbb{V}}\\!\\!{({{{[\widehat{\mathcal{A}}_{+1}]}_{i,j}}\\!+\\!{{[\widehat{\mathcal{A}}_{-1}]}_{i,j}}}\\!)},$

adding (89) into which, we arrive at

$\displaystyle\frac{1}{\breve{s}_{i}}([\widehat{\mathfrak{a}}_{+1}]_{i}+[\widehat{\mathfrak{a}}_{-1}]_{i}+\sum\limits_{j\in\mathbb{V}}\\!{({{{[\widehat{\mathcal{A}}_{+1}]}_{i,j}}\\!-\\!{{[\widehat{\mathcal{A}}_{-1}]}_{i,j}}})})$
$\displaystyle\\!=\\!2-([\widehat{\mathfrak{a}}_{+1}]_{i}-[\widehat{\mathfrak{a}}_{-1}]_{i})-\sum\limits_{j\in\mathbb{V}}\\!{({{{[\widehat{\mathcal{A}}_{+1}]}_{i,j}}+{{[\widehat{\mathcal{A}}_{-1}]}_{i,j}}})},$

which results in the computation of $\breve{s}_{i}$ in Line 1 of Algorithm 1.
With computed $\breve{s}_{i}$, from (85) and (87) we have

$\displaystyle[\widehat{\mathfrak{a}}_{+1}]_{i}-[\widehat{\mathfrak{a}}_{-1}]_{i}-\frac{1}{\breve{s}_{i}}\sum\limits_{j\in\mathbb{V}}{({{{[\widehat{\mathcal{A}}_{+1}]}_{i,j}}-{{[\widehat{\mathcal{A}}_{-1}]}_{i,j}}})}=4\breve{\epsilon}_{i},$
$\displaystyle[\widehat{\mathfrak{a}}_{+1}]_{i}-[\widehat{\mathfrak{a}}_{-1}]_{i}+\frac{1}{\breve{s}_{i}}\sum\limits_{j\in\mathbb{V}}{({{{[\widehat{\mathcal{A}}_{+1}]}_{i,j}}-{{[\widehat{\mathcal{A}}_{-1}]}_{i,j}}})}=4\breve{\eta}_{i},$

which indicates the computations of $\breve{\epsilon}_{i}$ and
$\breve{\eta}_{i}$ in in Lines 2 and 3 of Algorithm 1, respectively. With the
obtained $\breve{\epsilon}_{i}$ and $\breve{\eta}_{i}$, the relation (88)
implies the computation of the sum of social-influence weights in Line 4 of
Algorithm 1. We obtain from (46a) and (46b) that

$\displaystyle{[\widehat{\mathcal{A}}_{+1}]_{i,j}}+{[\widehat{\mathcal{A}}_{-1}]_{i,j}}=\begin{cases}\\!2{(1-\frac{{{\breve{\eta}_{i}}}}{{\sum\limits_{l\in\mathbb{V}}{{{{{\breve{w}_{il}}}}}}}})\breve{w}_{ii}+2{\breve{\epsilon}_{i}}}&\text{if}\leavevmode\nobreak\
i\\!=\\!j\\\
\\!2(1-\frac{{{\breve{\eta}_{i}}}}{{\sum\limits_{l\in\mathbb{V}}{{{{{\breve{w}_{il}}}}}}}}){\breve{w}_{ij}},&\text{if}\leavevmode\nobreak\
i\\!\neq\\!j\end{cases}$

which, with the computed ${\breve{\epsilon}_{i}}$ and the sum
$\sum\limits_{j\in\mathbb{V}}{{\breve{w}_{ij}}}$, lead to the computation of
weighted network topology in Line 5 of Algorithm 1.

Finally, we note that the computations in Lines 2–5 rely on the assumption
that ${{\breve{s}}_{i}}\neq 0$, otherwise individual $\mathrm{v}_{i}$’s
associated social structure and model parameters of confirmation and
negativity bias cannot be inferred.

## References

  * [1] Y. Weng, Y. Liao, and R. Rajagopal, “Distributed energy resources topology identification via graphical modeling,” _IEEE Transactions on Power Systems_ , vol. 32, no. 4, pp. 2682–2694, 2016.
  * [2] Y. R. Wang and H. Huang, “Review on statistical methods for gene network reconstruction using expression data,” _Journal of Theoretical Biology_ , vol. 362, pp. 53–61, 2014.
  * [3] H.-T. Wai, A. Scaglione, and A. Leshem, “The social system identification problem,” in _54th IEEE Conference on Decision and Control_ , pp. 406–411, 2015.
  * [4] I. Brugere, B. Gallagher, and T. Y. Berger-Wolf, “Network structure inference, a survey: Motivations, methods, and applications,” _ACM Computing Surveys_ , vol. 51, no. 2, pp. 1–39, 2018.
  * [5] V. N. Ioannidis, Y. Shen, and G. B. Giannakis, “Semi-blind inference of topologies and dynamical processes over dynamic graphs,” _IEEE Transactions on Signal Processing_ , 2019.
  * [6] E. Nozari, Y. Zhao, and J. Cortés, “Network identification with latent nodes via autoregressive models,” _IEEE Transactions on Control of Network Systems_ , vol. 5, no. 2, pp. 722–736, 2017.
  * [7] D. Materassi and M. V. Salapaka, “On the problem of reconstructing an unknown topology via locality properties of the wiener filter,” _IEEE Transactions on Automatic Control_ , vol. 57, no. 7, pp. 1765–1777, 2012.
  * [8] R. S. Nickerson, “Confirmation bias: A ubiquitous phenomenon in many guises,” _Review of General Psychology_ , vol. 2, no. 2, pp. 175–220, 1998.
  * [9] P. Lamberson and S. Soroka, “A model of attentiveness to outlying news,” _Journal of Communication_ , vol. 68, no. 5, pp. 942–964, 2018.
  * [10] M. Mäs, A. Flache, and J. A. Kitts, “Cultural integration and differentiation in groups and organizations,” in _Perspectives on Culture and Agent-Based Simulations_. Springer, 2014, pp. 71–90.
  * [11] T. Abdelzaher, H. Ji, J. Li, C. Yang, J. Dellaverson, L. Zhang, C. Xu, and B. K. Szymanski, “The paradox of information access: Growing isolation in the age of sharing,” _arXiv:2004.01967_.
  * [12] C. Xu, J. Li, T. Abdelzaher, H. Ji, B. K. Szymanski, and J. Dellaverson, “The paradox of information access: On modeling social-media-induced polarization,” _arXiv:2004.01106_.
  * [13] A. V. Proskurnikov and R. Tempo, “A tutorial on modeling and analysis of dynamic social networks. Part I,” _Annual Reviews in Control_ , vol. 43, pp. 65–79, 2017.
  * [14] ——, “A tutorial on modeling and analysis of dynamic social networks. Part II,” _Annual Reviews in Control_ , vol. 45, pp. 166–190, 2018.
  * [15] M. H. DeGroot, “Reaching a consensus,” _Journal of the American Statistical Association_ , vol. 69, no. 345, pp. 118–121, 1974.
  * [16] N. E. Friedkin and E. C. Johnsen, “Social influence and opinions,” _Journal of Mathematical Sociology_ , vol. 15, no. 3-4, pp. 193–206, 1990\.
  * [17] A. Das, S. Gollapudi, R. Panigrahy, and M. Salek, “Debiasing social wisdom,” in _Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pp. 500–508, 2013.
  * [18] 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.
  * [19] M. Del Vicario, A. Scala, G. Caldarelli, H. E. Stanley, and W. Quattrociocchi, “Modeling confirmation bias and polarization,” _Scientific Reports_ , vol. 7, p. 40391, 2017.
  * [20] D. M. Lazer, M. A. Baum, Y. Benkler, A. J. Berinsky, K. M. Greenhill, F. Menczer, M. J. Metzger, B. Nyhan, G. Pennycook, D. Rothschild _et al._ , “The science of fake news,” _Science_ , vol. 359, no. 6380, pp. 1094–1096, 2018.
  * [21] Y. Mao, E. Akyol, and N. Hovakimyan, “Impact of confirmation bias on competitive information spread in social networks,” _IEEE Transactions on Control of Network Systems, conditionally accepted, arXiv:1908.09812_.
  * [22] Y. Mao, S. Bolouki, and E. Akyol, “Spread of information with confirmation bias in cyber-social networks,” _IEEE Transactions on Network Science and Engineering_ , vol. 7, no. 2, pp. 688–700, 2020.
  * [23] S. Dhamal, W. Ben-Ameur, T. Chahed, and E. Altman, “Optimal investment strategies for competing camps in a social network: A broad framework,” _IEEE Transactions on Network Science and Engineering_ , vol. 6, no. 4, pp. 628–645, 2018.
  * [24] Y. Mao and E. Akyol, “On inference of network topology and confirmation bias in cyber-social networks,” _IEEE Transactions on Signal and Information Processing over Networks_ , vol. 6, pp. 633–644, 2020.
  * [25] Y. Jedra and A. Proutiere, “Finite-time identification of stable linear systems: Optimality of the least-squares estimator,” _arXiv:2003.07937_.
  * [26] M. Simchowitz, H. Mania, S. Tu, M. I. Jordan, and B. Recht, “Learning without mixing: Towards a sharp analysis of linear system identification,” in _Conference On Learning Theory_ , pp. 1–35, 2018.
  * [27] T. Sarkar and A. Rakhlin, “Near optimal finite time identification of arbitrary linear dynamical systems,” in _International Conference on Machine Learning_ , pp. 5610–5618, 2019.
  * [28] T. Sarkar, A. Rakhlin, and M. A. Dahleh, “Finite-time system identification for partially observed LTI systems of unknown order,” _arXiv:1902.01848_.
  * [29] S. Oymak and N. Ozay, “Non-asymptotic identification of LTI systems from a single trajectory,” in _2019 American Control Conference_ , pp. 5655–5661, 2019.
  * [30] M. Rudelson, R. Vershynin _et al._ , “Hanson-Wright inequality and sub-Gaussian concentration,” _Electronic Communications in Probability_ , vol. 18, 2013.
  * [31] A. Banerjee, Q. Gu, V. Sivakumar, and S. Z. Wu, “Random quadratic forms with dependence: Applications to restricted isometry and beyond,” in _Advances in Neural Information Processing Systems_ , pp. 12 599–12 609, 2019.
  * [32] R. Borum, “The science of interpersonal trust,” _Mental Health Law & Policy Faculty Publications, 574_, 2010.
  * [33] P. Duggins, “A psychologically-motivated model of opinion change with applications to american politics,” _arXiv:1406.7770_.
  * [34] M. Del Vicario, A. Bessi, F. Zollo, F. Petroni, A. Scala, G. Caldarelli, H. E. Stanley, and W. Quattrociocchi, “The spreading of misinformation online,” _Proceedings of the National Academy of Sciences_ , vol. 113, no. 3, pp. 554–559, 2016.
  * [35] I. Noor, “Confirmation bias,” _Simply Psychology_ , 2020, https://www.simplypsychology.org/confirmation-bias.html, accessed 2020-11-20.
  * [36] R. Adamczak _et al._ , “A note on the Hanson-Wright inequality for random vectors with dependencies,” _Electronic Communications in Probability_ , vol. 20, 2015.
  * [37] Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári, “Improved algorithms for linear stochastic bandits,” in _Advances in Neural Information Processing Systems_ , pp. 2312–2320, 2011.
  * [38] J. B. Lewis, K. Poole, H. Rosenthal, A. Boche, A. Rudkin, and L. Sonnet, “Voteview: Congressional roll-call votes database (2018),” _URl: https://voteview. com_ , 2018.
  * [39] R. Vershynin, _High-dimensional probability: An introduction with applications in data science_. Cambridge university press, 2018, vol. 47.