#  Active Sensing of Social Networks

Hoi-To Wai,  _Student Member, IEEE,_ Anna Scaglione,  _Fellow, IEEE,_ and Amir
Leshem,  _Senior Member, IEEE_ This material is based upon work supported by
NSF CCF-1011811 and partially supported by ISF 903/13. A preliminary version
of this work has been presented at IEEE CDC 2015, Osaka, Japan [1].H.-T. Wai
and A. Scaglione are with the School of Electrical, Computer and Energy
Engineering, Arizona State University, Tempe, AZ 85281, USA. E-mails:
<EMAIL_ADDRESS>A. Leshem is with Faculty of Engineering, Bar-
Ilan University, Ramat-Gan, Israel. Email<EMAIL_ADDRESS>
###### Abstract

This paper develops an active sensing method to estimate the relative weight
(or trust) agents place on their neighbors’ information in a social network.
The model used for the regression is based on the steady state equation in the
linear DeGroot model under the influence of stubborn agents; i.e., agents
whose opinions are not influenced by their neighbors. This method can be
viewed as a _social RADAR_ , where the stubborn agents excite the system and
the latter can be estimated through the reverberation observed from the
analysis of the agents’ opinions. The social network sensing problem can be
interpreted as a blind compressed sensing problem with a sparse measurement
matrix. We prove that the network structure will be revealed when a sufficient
number of stubborn agents independently influence a number of ordinary (non-
stubborn) agents. We investigate the scenario with a deterministic or
randomized DeGroot model and propose a consistent estimator of the steady
states for the latter scenario. Simulation results on synthetic and real world
networks support our findings.

###### Index Terms:

DeGroot model, opinion dynamics, social networks, sparse recovery, system
identification

##  I Introduction

Recently, the study of networks has become a major research focus in many
disciplines, where _networks_ have been used to model systems from biology,
physics to the social sciences [2]. From a signal processing perspective, the
related research problems can be roughly categorized into _analysis, control
and sensing_. While these are natural extensions of classical signal
processing problems, the spatial properties due to the underlying network
structure have yielded new insights and fostered the development of novel
signal processing tools [3, 4, 5].

The _network analysis_ problem has received much attention due to the
emergence of ‘big-data’ from social networks, biological networks, etc. Since
the networks to be analyzed consist of millions of vertices and edges,
computationally efficient tools have been developed to extract low-dimensional
structures, e.g., by detecting community structures [6, 7] and finding the
centrality measures of the vertices [8]. Techniques in the related studies
involve developing tools that run in (sub)-linear time with the size of the
network; e.g., see [9]. Another problem of interest is known as _network
control_ , where the aim is to choose a subset of vertices that can provide
full/partial control over the network. It was shown recently in [10] that the
Kalman’s classical control criterion is equivalent to finding a maximal
matching on the network; see also [11, 12].

This work considers the _social network sensing_ problem that has received
relatively less attention in the community than the two aforementioned
problems. We focus on social networks111 That said, the developed methodology
is general and may be applied to other types of networks with similar dynamics
models. and our aim is to _infer_ simultaneously the trust matrix and the
network structure by observing the opinion dynamics. We model the _opinion
dynamics_ in the social network according to the DeGroot model [13]. In
particular, at each time step, the opinions are updated by taking a convex
combination of the neighboring opinions, weighted with respect to a _trust
matrix_. Despite its simplicity, the DeGroot model has been widely popular in
the social sciences; some experimental papers indicated that the model is able
to capture the actual opinion dynamics, e.g., [14, 15, 16, 17, 18]. Notice
that the DeGroot model is analogous to the Average Consensus Gossiping (ACG)
model [19, 20] and drives the opinions of every agent in the network to
_consensus_ as time goes to infinity. Hence, in such situations the social
network sensing method is required to _track_ the individual opinion updates.
This is the _passive_ approach taken in previous works [21, 22, 14, 23]. As
agents’ interactions may occur asynchronously and at an unknown timescale,
these approaches may be impractical due to the difficulty in precisely
tracking the opinion evolution.

An interesting extension in the study of opinion dynamics is to consider the
effects of stubborn agents (or zealots), whose opinions remain unchanged
throughout the network dynamics. Theoretical studies have focused on
characterizing the steady-state of the opinion dynamics when stubborn agents
are present [24, 25, 26, 16, 27, 28, 29], developing techniques to effectively
_control_ the network and attain fastest convergence [29, 30, 31, 32]. The
model of stubborn agents has also been studied in the context of sensor
network localization [33]. More recently, experimental studies have provided
evidence supporting the existence of stubborn agents in social networks, for
instance, [15, 34] suggested that stubborn agents can be used to justify
several opinion dynamic models for data collected from controlled experiments;
[35] illustrated that the existence of stubborn agents is a plausible cause
for the emergence of extreme opinions in social networks; [36] studied the
controllability of opinions in real social networks using stubborn agents.

The aim of this paper is to demonstrate an important consequence of the
existence of _stubborn agents_. Specifically, we propose a _social RADAR_
formulation through exploiting the special role of stubborn agents. As will be
shown below, the stubborn agents will help expose the network structure
through a set of steady state equations. The proposed model shows that the
stubborn agents can play a role that is analogous to a traditional radar,
which _actively_ scans and probes the social network.

As the stubborn agents may constitute a small portion of the network, the set
of steady state equation may be an undetermined system. To handle this issue,
we formulate the network sensing problem as a sparse recovery problem using
the popular $\ell_{0}/\ell_{1}$ minimization technique. Finally, we derive a
low-complexity optimization method for social network sensing. The proposed
method is applicable to large networks. An additional contribution of our
investigation is a new recoverability result for a special case of _blind
compressive sensing_ ; e.g.,[37, 38]. In particular, we develop an
identifiability condition for active sensing of social networks based on
expander graph theories [39]. Compared to [40, 41, 42, 39], our result is
applicable when the sensing matrix is non-negative (instead of binary) and
subject to small multiplicative perturbations.

The remainder of this paper is organized as follows. Section II introduces the
DeGroot model for opinion dynamics and the effects of stubborn agents. Section
III formulates the social network sensing problem as a sparse recovery problem
and provides a sufficient condition for perfect recovery. Section IV further
develops a fast optimization method for approximately solving the sparse
recovery problem and shows that the developed methods can be applied when the
opinion dynamics is a time-varying system. Simulation results on both
synthetic and a real network example conclude the paper, in Section V.

_Notation:_ We use boldfaced small/capital letters to denote vectors/matrices
and $[n]=\\{1,...,n\\}$ to represent the index set from $1$ to $n$ and
$n\in\mathbb{N}$. ${\rm Diag}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n\times
n}$/${\rm diag}:\mathbb{R}^{n\times n}\rightarrow\mathbb{R}^{n}$ to denote the
diagonal operator that maps from a vector/square matrix to a square
matrix/vector, $\geq$ to represent the element-wise inequality. For an index
set $\Omega\subseteq[n]$, we use $\Omega^{c}$ to denote its natural
complement, e.g., $\Omega^{c}=[n]\setminus\Omega$. A vector ${\bm{x}}$ is
called $k$-sparse if $\|{\bm{x}}\|_{0}\leq k$. We denote ${\rm off}({\bm{W}})$
as the square matrix with only off-diagonal elements in ${\bm{W}}$.

##  II Opinion Dynamics Model

Consider a social network represented by a simple, connected weighted directed
graph $G=(V,E,\overline{\bm{W}})$, where $V=[n]$ is the set of agents,
$E\subseteq V\times V$ is the network topology and
$\overline{\bm{W}}\in\mathbb{R}^{n\times n}$ denotes the _trust_ matrix
between agents. Notice that $\overline{\bm{W}}$ can be asymmetric. The trust
matrix satisfies $\overline{\bm{W}}\geq{\bf 0}$ and $\overline{\bm{W}}{\bf
1}={\bf 1}$, i.e., $\overline{\bm{W}}$ is stochastic. Furthermore,
$\overline{W}_{ii}<1$ for all $i$ and $\overline{W}_{ij}>0$ if and only if
$ij\in E$.

We focus on the linear DeGroot model [13] for opinion dynamics. There are $K$
different discussions in the social network and each discussion is indexed by
$k\in[K]$. Let $x_{i}(t;k)$ be the opinion of the $i$th agent222 For example,
the $i$th agent’s opinion $x_{i}(t;k)$ may represent a probability
distribution function of his/her stance on the discussion. While our
discussion is focused on the case when $x_{i}(t;k)$ is a scalar, it should be
noted that the techniques developed can be easily extended to the vector case;
see [1]. at time $t\in\mathbb{N}$ during the $k$th discussion. Using the
intuition that individuals’ opinions are influenced by opinions of the others,
the DeGroot model postulates that the agents’ opinions are updated according
to the following random process:

${x}_{i}(t;k)=\sum_{j\in{\cal N}_{i}}W_{ij}(t;k)x_{j}(t-1;k),$ (1)

which can also be written as

${\bm{x}}(t;k)={\bm{W}}(t;k){\bm{x}}(t-1;k),$ (2)

where ${\bm{x}}(t;k)=(x_{1}(t;k),\ldots,x_{n}(t;k))^{T}$,
$[{\bm{W}}(t;k)]_{ij}={W}_{ij}(t;k)$ and ${\bm{W}}(t;k)$ is non-negative and
stochastic, i.e., ${\bm{W}}(t;k){\bf 1}={\bf 1}$ for all $t,s$. See [13] and
[43, Chapter 1] for a detailed description of the aforementioned model. We
assume the following regarding the random matrix ${\bm{W}}(t;k)$.

###### Assumption 1

${\bm{W}}(t;k)$ is an independently and identically distributed (i.i.d.)
random matrix drawn from a distribution that satisfies
$\mathbb{E}\\{{\bm{W}}(t;k)\\}=\overline{\bm{W}}$ for all
$t\in\mathbb{N},k\in[K]$.

The agents’ opinions can be observed as:

$\hat{\bm{x}}(t;k)={\bm{x}}(t;k)+{\bm{n}}(t;k),$ (3)

where ${\bm{n}}(t;k)$ is i.i.d. additive noise with zero-mean and bounded
variance. Eq. (1) & (3) constitute a time-varying linear dynamical system.
Since $\overline{\bm{W}}$ encodes both the network topology and the trust
strengths, the social network sensing problem is to infer $\overline{\bm{W}}$
through the set of observations $\\{\hat{\bm{x}}(t;k)\\}_{t\in{\cal
T},k\in[K]}$, where ${\cal T}$ is the set of sampling instances.

A well known fact in the distributed control literature [19] is that the
agents’ opinions in Eq. (1) attain consensus almost surely as
$t\rightarrow\infty$:

$\lim_{t\rightarrow\infty}{\bm{x}}(t;k)=^{a.s.}{\bf
1}{\bm{c}}^{T}(s){\bm{x}}(0;k),$ (4)

for some ${\bm{c}}(s)\in\mathbb{R}^{n}$, i.e., $x_{i}(t;k)=x_{j}(t;k)$ for all
$i,j$ as $t\rightarrow\infty$. In other words, the information about the
network structure vanishes in the steady state equation.

The aforementioned property of the DeGroot model has prompted most works on
social network sensing (or network reconstruction in general) to assume a
complete/partial knowledge of ${\cal T}$ such that the opinion dynamics can be
tracked. In particular, [14] assumes a static model such that
${\bm{W}}(t;k)=\overline{\bm{W}}$ and infers $\overline{\bm{W}}$ by solving a
least square problem; [21, 22] deals with a time-varying, non-linear dynamical
system model and applies sparse recovery to infer $\overline{\bm{W}}$. The
drawback of these methods is that they require knowing the discrete time
indices for the observations made. This knowledge may be difficult to obtain
in general. In contrast, the actual system states are updated with an
_unknown_ interaction rate and the interaction timing between agents is not
observable in most practical scenarios.

Our active sensing method relies on observing the steady state opinions; i.e.,
the opinions when $t\rightarrow\infty$. The observations are based on ${\cal
T}$ such that $\min(t\in{\cal T})\gg 0$ and are thus robust to errors in
tracking of the discrete time dynamics. Our approach is to reconstruct the
network via a set of _stubborn agents_ , as described next.

###  II-A Stubborn Agents (a.k.a. zealots)

Stubborn agents (a.k.a. zealots) are members whose opinions can not be swayed
by others. If agent $i$ is stubborn, then $x_{i}(t;k)=x_{i}(0;k)$ for all $t$.
The opinion dynamics of these agents can be characterized by the structure of
their respective rows in the trust matrix:

###### Definition 1

An agent $i$ is stubborn if and only if its corresponding row in the trust
matrix ${\bm{W}}(t;k)$ is the canonical basis vector; i.e., for all $j$,

${W}_{ij}(t;k)=\begin{cases}1,~{}{\rm if}~{}{j=i},\\\ 0,~{}{\rm
otherwise},\end{cases}\forall~{}t,k$ (5)

Note that stubborn agents are known to exist in social networks, as discussed
in the Introduction.

Suppose that there exists $n_{s}$ stubborn agents in the social network and
the _social RADAR_ is aware of their existence. Without loss of generality, we
let $V_{s}\triangleq[n_{s}]$ be the set of stubborn agents and
$V_{r}\triangleq V\setminus V_{s}$ be the set of ordinary agents. The trust
matrix $\overline{\bm{W}}$ and its realization can be written as the following
block matrices:

$\overline{\bm{W}}=\left(\begin{array}[]{cc}{\bm{I}}_{n_{s}}&{\bf 0}\\\
\overline{\bm{B}}&\overline{\bm{D}}\end{array}\right),~{}{\bm{W}}(t;k)=\left(\begin{array}[]{cc}{\bm{I}}_{n_{s}}&{\bf
0}\\\ {\bm{B}}(t;k)&{\bm{D}}(t;k)\end{array}\right),$ (6)

where ${\bm{B}}(t;k)$ and ${\bm{D}}(t;k)$ are the partial matrices of
${\bm{W}}(t;k)$, note that $\mathbb{E}\\{{\bm{B}}(t;k)\\}=\overline{\bm{B}}$
and $\mathbb{E}\\{{\bm{D}}(t;k)\\}=\overline{\bm{D}}$. Notice that
$\overline{\bm{B}}$ is the network between stubborn and ordinary agents, and
$\overline{\bm{D}}$ is the network among the ordinary agents themselves.

We further impose the following assumptions:

###### Assumption 2

The support of $\overline{\bm{B}}$,
$\Omega_{\overline{\bm{B}}}=\\{ij:\overline{B}_{ij}>0\\}=E(V_{r},V_{s})$, is
known. Moreover, each agent in $V_{r}$ has non-zero trust in at least one
agent in $V_{s}$.

###### Assumption 3

The induced subgraph $G[V_{r}]=(V_{r},E(V_{r}))$ is connected.

Consequently, the principal submatrix $\overline{\bm{D}}$ of
$\overline{\bm{W}}$ satisfies $\|\overline{\bm{D}}\|_{2}<1$.

We are interested in the steady state opinion resulting from (1) at
$t\rightarrow\infty$.

###### Observation 1

[33, 29] Let
${\bm{x}}(t;k)\triangleq({\bm{z}}(t;k),~{}{\bm{y}}(t;k))^{T}\in\mathbb{R}^{n}$
where ${\bm{z}}(t;k)\in\mathbb{R}^{n_{s}}$ and
${\bm{y}}(t;k)\in\mathbb{R}^{n-n_{s}}$ are the opinions of stubborn agents and
ordinary agents, respectively. Consider (1) by setting $t\rightarrow\infty$,
we have:

$\lim_{t\rightarrow\infty}\mathbb{E}\\{{\bm{x}}(t;k)|{\bm{x}}(0;k)\\}=\overline{\bm{W}}^{\infty}{\bm{x}}(0;k),$
(7)

where

$\overline{\bm{W}}^{\infty}=\left(\begin{array}[]{cc}{\bm{I}}_{n_{s}}&{\bm{0}}\\\
({\bm{I}}-\overline{\bm{D}})^{-1}\overline{\bm{B}}&{\bm{0}}\end{array}\right).\vspace{.2cm}$
(8)

The expected opinions of ordinary agents at $t\rightarrow\infty$ are:

$\lim_{t\rightarrow\infty}\mathbb{E}\\{{\bm{y}}(t;k)|{\bm{z}}(0;k)\\}=({\bm{I}}-\overline{\bm{D}})^{-1}\overline{\bm{B}}{\bm{z}}(0;k).$
(9)

As seen, the steady state opinions are dependent on the stubborn agents and
the structure of the network. Furthermore, unlike the case _without_ stubborn
agents (cf. (4)), information about the network structure
$\overline{\bm{D}},\overline{\bm{B}}$ will be retained in the steady state
equation (9). Leveraging on Observation 1, the next section formulates a
regression problem that estimates $\overline{\bm{D}},\overline{\bm{B}}$ from
observing opinions that fit these steady state equations.

##  III Social Network Sensing via Stubborn Agents

We now study the problem of social network sensing using stubborn agents.
Instead of tracking the opinion evolution in the social networks similar to
the _passive_ methods [14, 21, 22], our method is based on collecting the
steady-state opinions from $K\geq n_{s}$ discussions. Define the data
matrices:

$\displaystyle{\bm{Y}}\triangleq$
$\displaystyle\Big{(}\mathbb{E}\\{{\bm{y}}(\infty;1)\\}~{}\cdots~{}\mathbb{E}\\{{\bm{y}}(\infty;K)\\}\Big{)}\in\mathbb{R}^{(n-n_{s})\times
K},$ (10a) $\displaystyle{\bm{Z}}\triangleq$
$\displaystyle\Big{(}{\bm{z}}(0;1)~{}\cdots~{}{\bm{z}}(0;K)\Big{)}\in\mathbb{R}^{n_{s}\times
K}.$ (10b)

Notice that (9) implies that
${\bm{Y}}=({\bm{I}}-\overline{\bm{D}})^{-1}\overline{\bm{B}}{\bm{Z}}$. Fig. 1
illustrates the relationship between the data matrices/vectors used in the
social network sensing problem. One often obtains a noisy estimate of
${\bm{Y}}$; i.e.,

$\hat{\bm{Y}}=({\bm{I}}-\overline{\bm{D}})^{-1}\overline{\bm{B}}{\bm{Z}}+{\bm{N}}.$
(11)

We relegate the discussion on obtaining $\hat{\bm{Y}}$ when the agents’
interactions are asynchronous to Section IV-B.

Figure 1: Data matrices used in the social network sensing problem (cf. (10)).

From Eq. (11), a natural solution to estimate
$(\overline{\bm{B}},\overline{\bm{D}})$ is to obtain a tuple
$({\bm{B}},{\bm{D}})$ that minimizes the square loss
$\|\hat{\bm{Y}}-({\bm{I}}-{\bm{D}})^{-1}{\bm{B}}{\bm{Z}}\|_{F}^{2}$. However,
the system equation (11) admits an implicit ambiguity:

###### Lemma 1

Consider the pair of tuples, $({\bm{B}},{\bm{D}})$ and
$(\tilde{\bm{B}},\tilde{\bm{D}})$, where
${\bm{B}}{\bm{1}}+{\bm{D}}{\bm{1}}={\bm{1}}$ and the latter is defined as

$\displaystyle\tilde{\bm{B}}=\bm{\Lambda}{\bm{B}},~{}{\rm
off}(\tilde{\bm{D}})=\bm{\Lambda}{\rm off}({\bm{D}}),$ (12a)
$\displaystyle{\rm diag}(\tilde{\bm{D}})={\bf 1}-\bm{\Lambda}({\bm{B}}{\bf
1}+{\rm off}({\bm{D}}){\bf 1}),$ (12b)

for some diagonal matrix $\bm{\Lambda}>{\bm{0}}$ such that ${\rm
diag}(\tilde{\bm{D}})\geq{\bm{0}}$. Under (12), the equalities
$({\bm{I}}-{\bm{D}})^{-1}{\bm{B}}=({\bm{I}}-\tilde{\bm{D}})^{-1}\tilde{\bm{B}}$
and $\tilde{\bm{B}}{\bm{1}}+\tilde{\bm{D}}{\bm{1}}={\bm{1}}$ hold.

The proof is relegated to Appendix A. Lemma 1 indicates that there are
infinitely many tuples $(\tilde{\bm{B}},\tilde{\bm{D}})$ with the same product
$({\bm{I}}-\tilde{\bm{D}})^{-1}\tilde{\bm{B}}$. The diagonal entries of
$\tilde{\bm{D}}$; i.e., the magnitude of _self trust_ , are ambiguous. In
fact, the ambiguity described in Lemma 1 is due to the fact that the collected
data $\hat{\bm{Y}},{\bm{Z}}$ lacks information about the rate of social
interaction.

In light of Lemma 1, we determine an _invariant_ quantity among the ambiguous
solutions. Define the equivalence class:

$({\bm{B}},{\bm{D}})\sim(\tilde{\bm{B}},\tilde{\bm{D}}):\exists~{}\bm{\Lambda}>{\bm{0}}~{}{\rm
s.t.}~{}\eqref{eq:equiv}~{}{\rm holds},~{}{\rm
diag}(\tilde{\bm{D}})\geq{\bm{0}}.$ (13)

A quick observation on (12) is that $\bm{\Lambda}$ modifies the magnitude of
${\rm diag}({\bm{D}})$. This inspires us to resolve the ambiguity issue by
imposing constraints on ${\rm diag}({\bm{D}})$:

###### Observation 2

The pair of relative trust matrices resulting from $({\bm{B}},{\bm{D}})$,
denoted by the superscript $(\cdot)^{\prime}$:

$\begin{array}[]{l}{\bm{B}}^{\prime}=({\bm{I}}-{\rm
Diag}({\bm{c}}))\bm{\Lambda}_{s}^{-1}{\bm{B}},~{}{\rm
diag}({\bm{D}}^{\prime})={\bm{c}},\\\ {\rm
off}({\bm{D}}^{\prime})=({\bm{I}}-{\rm
Diag}({\bm{c}}))\bm{\Lambda}_{s}^{-1}{\rm off}({\bm{D}}),\end{array}$ (14)

where $\bm{\Lambda}_{s}={\bm{I}}-{\rm Diag}({\rm diag}({\bm{D}}))$ and
${\bm{0}}\leq{\bm{c}}<{\bm{1}}$, is unique for each equivalence class when
${\bm{c}}$ is fixed. In other words, if
$({\bm{B}},{\bm{D}})\sim(\tilde{\bm{B}},\tilde{\bm{D}})$, their resultant
pairs of relative trust matrices are equal,
$({\bm{B}}^{\prime},{\bm{D}}^{\prime})=(\tilde{\bm{B}}^{\prime},\tilde{\bm{D}}^{\prime})$.

Notice that the pair of relative trust matrices is an important quantity for a
social network since it contains the relative trust strengths and connectivity
of the network.

We are now ready to present the regression problems pertaining to recovering
$\tilde{\bm{B}}^{\prime},\tilde{\bm{D}}^{\prime}$. As we often have access to
a superset ${\cal S}$ of the support of $\overline{\bm{D}}$; i.e.,
$\Omega_{\overline{\bm{D}}}\subseteq{\cal S}$ and $\Omega_{\overline{\bm{D}}}$
denotes the support of $\overline{\bm{D}}$, we propose two different
formulations when different knowledge on $\Omega_{\overline{\bm{D}}}$ is
accessible.

_Case 1: nearly full support information —_ When
$\Omega_{\overline{\bm{D}}}\subseteq{\cal S}$ and $|{\cal
S}|\approx|\Omega_{\overline{\bm{D}}}|$, the support of $\overline{\bm{D}}$ is
mostly known. We formulate the following least square problem:

$\displaystyle\displaystyle\min_{{\bm{D}},{\bm{B}}}~{}$
$\displaystyle\|({\bm{I}}-{\bm{D}})\hat{\bm{Y}}-{\bm{B}}{\bm{Z}}\|_{F}^{2}$
(15a) $\displaystyle{\rm s.t.}~{}$ $\displaystyle{\bm{B}}{\bf 1}+{\bm{D}}{\bf
1}={\bf 1},~{}{\bm{D}}\geq{\bf 0},~{}{\bm{B}}\geq{\bm{0}},$ (15b)
$\displaystyle{\cal
P}_{\Omega_{\overline{\bm{B}}}^{c}}({\bm{B}})={\bm{0}},{\cal P}_{{\cal
S}^{c}}({\bm{D}})={\bm{0}},{\rm diag}({\bm{D}})={\bm{c}}.$ (15c)

The projection operator ${\cal P}_{\Omega}(\cdot)$ is defined as:

$[{\cal P}_{\Omega}({\bm{A}})]_{ij}=\begin{cases}A_{ij},~{}ij\in\Omega,~{}\\\
0,~{}{\rm otherwise,}\end{cases}$ (16)

where $\Omega\subseteq[n]\times[m]$ is an index set for the matrix
${\bm{A}}\in\mathbb{R}^{n\times m}$. Problem (15) is a constrained least-
square problem that can be solved efficiently, e.g., using cvx [44].

_Case 2: partial support information —_ When
$\Omega_{\overline{\bm{D}}}\subseteq{\cal S}$ and $|{\cal
S}|\gg|\Omega_{\overline{\bm{D}}}|$, the system equation (11) constitutes an
undetermined system. This motivates us to exploit that $\overline{\bm{D}}$ is
sparse and consider the sparse recovery problem:

$\displaystyle\displaystyle\min_{{\bm{D}},{\bm{B}}}~{}$ $\displaystyle\|{\rm
vec}({\bm{D}})\|_{0}$ (17a) $\displaystyle{\rm s.t.}~{}$
$\displaystyle\|({\bm{I}}-{\bm{D}})\hat{\bm{Y}}-{\bm{B}}{\bm{Z}}\|_{F}^{2}\leq\epsilon,~{}{\bm{B}}{\bf
1}+{\bm{D}}{\bf 1}={\bf 1},$ (17b) $\displaystyle{\bm{D}}\geq{\bf
0},~{}{\bm{B}}\geq{\bm{0}},~{}{\rm diag}({\bm{D}})={\bm{c}},$ (17c)
$\displaystyle{\cal
P}_{\Omega_{\overline{\bm{B}}}^{c}}({\bm{B}})={\bm{0}},~{}{\cal P}_{{\cal
S}^{c}}({\bm{D}})={\bm{0}},$ (17d)

for some $\epsilon\geq 0$ and ${\rm vec}({\bm{D}})$ denotes the vectorization
of the matrix ${\bm{D}}$. Note that Problem (17) is an $\ell_{0}$ minimization
problem that is NP-hard to solve in general. In practice, the following convex
problem is solved in lieu of (17):

$\min_{{\bm{B}},{\bm{D}}}\|{\rm vec}({\bm{D}})\|_{1}~{}{\rm s.t.}~{}{\rm
Eq.}~{}\eqref{eq:const_a}-\eqref{eq:const_b}.$ (18)

###### Remark 1

A social network sensing problem similar to Case 1 has been studied in [31]
and its identifiability conditions have been discussed therein. In fact, we
emphasize that our focus in this paper is on the study of Case 2, which
presents a more challenging problem due to the lack of support information.

###  III-A Identifiability Conditions for Social Network Sensing

We derive the conditions for recovering the relative trust matrix
$(\overline{\bm{B}}^{\prime},\overline{\bm{D}}^{\prime})$ resulting from
$(\overline{\bm{B}},\overline{\bm{D}})$ by solving (15) or (17). As a common
practice in signal processing, the following analysis assumes noiseless
measurements such that $\sigma^{2}={\bm{0}}$. We set $\epsilon=0$ in (17b) and
assume $K\geq n_{s}$.

As $\sigma^{2}=0$, the optimization problem (15) admits an optimal objective
value of zero. Now, let us denote

$\tilde{\bm{A}}\triangleq\left(\begin{array}[]{cc}\hat{\bm{Y}}^{T}&{\bm{Z}}^{T}\end{array}\right).$
(19)

The identifiability condition for (15) and (17) can be analyzed by studying
the linear system:

$\hat{\bm{y}}_{i}=\tilde{\bm{A}}\left(\begin{array}[]{c}{\bm{d}}_{i}\\\
{\bm{b}}_{i}\end{array}\right),~{}\forall~{}i,~{}{\rm
Eq.}~{}\eqref{eq:const_full1}-\eqref{eq:const_full2},$ (20)

where $\hat{\bm{y}}_{i}$ is the $i$th column of $\hat{\bm{Y}}$,
${\bm{d}}_{i},{\bm{b}}_{i}$ are the $i$th row of ${\bm{D}},{\bm{B}}$,
respectively. Note that the above condition is equivalent to (17b)–(17d) with
$\epsilon=0$. In the following, we denote ${\cal S}_{i}$ and
$\Omega_{\overline{\bm{B}}}^{i}$ as the index sets restricted to the $i$th row
of ${\bm{D}}$ and ${\bm{B}}$.

_Case 1: nearly full support information —_ Due to the constraints in (15c),
the number of unknowns in the right hand side of the first equality in (20) is
$|\Omega_{\overline{\bm{B}}}^{i}|+|{\cal S}_{i}|-1$. From linear algebra, the
following is straightforward to show:

###### Proposition 1

The system (20) admits a unique solution if

${\rm rank}(\tilde{\bm{A}}_{:,{\cal
S}_{i}\cup\Omega_{\overline{\bm{B}}}^{i}})\geq|\Omega_{\overline{\bm{B}}}^{i}|+|{\cal
S}_{i}|-1,~{}\forall~{}i,$ (21)

where $\tilde{\bm{A}}_{:,{\cal S}_{i}\cup\Omega_{\overline{\bm{B}}}^{i}}$ is a
submatrix of $\tilde{\bm{A}}$ with the columns taken from the respective
entries of ${\cal S}_{i}$ and $\Omega_{\overline{\bm{B}}}^{i}$.

Similar result has also been reported in [31, Lemma 10].

_Case 2: partial support information —_ As $|{\cal
S}|\gg|\Omega_{\overline{\bm{D}}}|$, this case presents a more challenging
scenario to analyze since (20) is an underdetermined system. In particular,
(21) is often not satisfied. However, a sufficient condition can be given by
exploiting the fact that (17) finds the sparsest solution:

###### Proposition 2

There is a unique optimal solution to (17) if for all $\tilde{\cal
S}_{i}\subseteq{\cal S}_{i}$ and $|\tilde{\cal S}_{i}|\leq
2|\Omega_{\overline{\bm{D}}}^{i}|$, we have

${\rm rank}(\tilde{\bm{A}}_{:,\tilde{\cal
S}_{i}\cup\Omega_{\overline{\bm{B}}}^{i}})\geq|\Omega_{\overline{\bm{B}}}^{i}|+2|\Omega_{\overline{\bm{D}}}^{i}|-1,~{}\forall~{}i,$
(22)

where $\tilde{\bm{A}}_{:,\tilde{\cal S}\cup\Omega_{\overline{\bm{B}}}^{i}}$ is
a submatrix of $\tilde{\bm{A}}$ with the columns taken from the respective
entries of ${\cal S}_{i}$ and $\Omega_{\overline{\bm{B}}}^{i}$.

Proposition 2 is equivalent to characterizing the _spark_ of the matrix
$\tilde{\bm{A}}$; see [45].

Checking (22) is non-trivial and it is not clear how many stubborn agents are
needed. We next show that using an optimized placement of stubborn agents, one
can derive a sufficient condition for unique recovery using (17).

###  III-B Optimized placement of stubborn agents

We consider an _optimized placement of stubborn agents_ when only partial
support information is given. In other words, we design
$\Omega_{\overline{\bm{B}}}$ for achieving better sensing performance. This is
possible in a controlled experiment where the stubborn agents are directly
controlled to interact with a target group of ordinary agents. Note also that
[25] has studied an optimal stubborn agent placement formulation for the
voter’s model opinion dynamics with a different objective.

To fix ideas, the following discussion draws a connection between _blind
compressed sensing_ and our social network sensing problem. Consider the
following equivalent form of (17b):

$({\bm{Y}}{\bm{Z}}^{\dagger})^{T}={\bm{B}}^{T}({\bm{I}}-{\bm{D}})^{-T},$ (23)

where ${\bm{Z}}^{\dagger}$ denotes the psuedo-inverse of ${\bm{Z}}$. By noting
that
${\bm{Y}}{\bm{Z}}^{\dagger}=({\bm{I}}-\overline{\bm{D}}^{\prime})^{-1}\overline{\bm{B}}^{\prime}$,
we have:

$\begin{array}[]{c}\overline{\bm{B}}^{{}^{\prime}T}({\bm{I}}-\overline{\bm{D}}^{\prime})^{-T}={\bm{B}}^{T}({\bm{I}}-{\bm{D}})^{-T}\\\
\Longleftrightarrow\overline{\bm{B}}^{{}^{\prime}T}({\bm{I}}-\overline{\bm{D}}^{\prime})^{-T}(\overline{\bm{D}}^{\prime}-{\bm{D}})^{T}=({\bm{B}}-\overline{\bm{B}}^{\prime})^{T}\\\
\Longleftrightarrow\overline{\bm{B}}^{{}^{\prime}T}({\bm{I}}-\overline{\bm{D}}^{\prime})^{-T}(\overline{\bm{d}}_{i}^{\prime}-{\bm{d}}_{i})={\bm{b}}_{i}-\overline{\bm{b}}_{i}^{\prime},~{}\forall~{}i,\end{array}$
(24)

where
$\overline{\bm{d}}_{i}^{\prime},{\bm{d}}_{i},\overline{\bm{b}}_{i}^{\prime}$
and ${\bm{b}}_{i}$ are the $i$th row of
$\overline{\bm{D}}^{\prime},{\bm{D}},\overline{\bm{B}}^{\prime}$ and
${\bm{B}}$, respectively. Due to the constraint ${\cal P}_{{\cal
S}^{c}}({\bm{D}})={\bm{0}}$ and ${\rm diag}({\bm{D}})={\bm{c}}$, the number of
unknowns in ${\bm{d}}_{i}$ is $n_{i}\triangleq n-n_{s}-s_{i}-1$, where
$s_{i}=|{\cal S}^{c}_{i}|$ and ${\cal S}^{c}_{i}$ is the complement of support
set restricted to the $i$th row of ${\bm{D}}$.

The matrix
$\overline{\bm{B}}^{{}^{\prime}T}({\bm{I}}-\overline{\bm{D}}^{\prime})^{-T}$
can be regarded as a sensing matrix in (24). Note that because
$\overline{\bm{B}}^{\prime}$ is unknown, we have a _blind compressed sensing_
problem, which was studied in [37, 38]. However, the scenarios considered
there were different from ours since the zero values of the sensing matrix are
partially known in that case.

To study an identifiability condition for (24), we note that
$\overline{\bm{B}}^{{}^{\prime}T}({\bm{I}}-\overline{\bm{D}}^{\prime})^{-T}=\overline{\bm{B}}^{{}^{\prime}T}({\bm{I}}+\overline{\bm{D}}^{\prime}+(\overline{\bm{D}}^{\prime})^{2}+\ldots)^{T}$;
i.e., the sensing matrix is equal to a perturbed
$\overline{\bm{B}}^{{}^{\prime}T}$. When the perturbation is small, we could
study $\overline{\bm{B}}$ alone. Moreover, as the entries in
$\overline{\bm{B}}$ are unknown, it is desirable to consider a sparse
construction to reduce the number of unknowns.

As suggested in [42, 41], a good choice is to construct
$\Omega_{\overline{\bm{B}}}$ randomly such that each row in
$\overline{\bm{B}}$ has a constant number $d$ of non-zero elements
(independent of $n_{i}^{\prime}$). We have the following sufficient condition:

###### Theorem 1

Define ${\rm supp}(\overline{\bm{B}})=\\{ij:\overline{B}_{ij}>0\\}$,
$b_{min}=\min_{ij\in{\rm supp}(\overline{\bm{B}})}\overline{B}_{ij}^{\prime}$,
$b_{max}=\max_{ij\in{\rm supp}(\overline{\bm{B}})}\overline{B}_{ij}^{\prime}$,
$\beta_{i}=n_{s}/n_{i}$ and $\beta_{i}^{\prime}=\beta_{i}-d/n_{i}$. Let the
support of $\overline{\bm{B}}^{\prime}\in\mathbb{R}^{n\times n_{s}}$ be
constructed such that each row has $d$ non-zero elements, selected randomly
and independently. If

$d>\max\Big{\\{}4,1+\frac{H(\alpha_{i})+\beta^{\prime}H(\alpha_{i}/\beta_{i}^{\prime})}{\alpha_{i}\log(\beta_{i}^{\prime}/\alpha_{i})}\Big{\\}},$
(25)

and

$b_{min}(2d-3)-1-2b_{max}>0,$ (26)

where $H(x)$ is the binary entropy function, and
$\|\overline{\bm{d}}_{i}^{\prime}\|_{0}\leq\alpha_{i}n_{i}/2$ for all $i$,
then as $n-n_{s}\rightarrow\infty$, there is a unique optimal solution to (17)
that
$({\bm{B}}^{\star},{\bm{D}}^{\star})=(\overline{\bm{B}}^{\prime},\overline{\bm{D}}^{\prime})$
with probability one. Moreover, the failure probability is bounded as:

$\begin{array}[]{l}\displaystyle{\rm
Pr}(({\bm{B}}^{\star},{\bm{D}}^{\star})\neq(\overline{\bm{B}}^{\prime},\overline{\bm{D}}^{\prime}))\vspace{.2cm}\\\
\displaystyle~{}~{}~{}~{}\leq\max_{i}\left(\frac{d}{\beta_{i}}\right)^{4}\frac{d-1}{{n_{i}}^{2}}+{\cal
O}({n_{i}}^{2-(d-1)(d-3)}).\end{array}$ (27)

The proof of Theorem 1 is in Appendix B where the claim is proven by treating
the unknown entries of $\overline{\bm{B}}^{{}^{\prime}T}$ as _erasure bits_ ,
and showing that the sensing matrix with erasure corresponds to a high quality
expander graph with high probability. To the best of our knowledge, Theorem 1
is a new recoverability result proven for blind compressed sensing problems.

Condition (25) gives a guideline for choosing the number of stubborn agents
$n_{s}$ employed. In fact, if we set $\alpha\rightarrow 0$ while keeping the
ratio $\beta/\alpha$ constant, condition (25) can be approximated by
$\beta>\alpha=2p$, where $\|\overline{\bm{d}}_{i}^{\prime}\|_{0}\leq
p(n-n_{s})$. Notice that in the limit as $n-n_{s}\rightarrow\infty$, if every
ordinary agent in the sub-network that corresponds to $\overline{\bm{D}}$ has
an in-degree bounded by $p(n-n_{s})$, then we only need:

$n_{s}\geq 2p(n-n_{s})$ (28)

stubborn agents to perfectly reconstruct $\overline{\bm{D}}$.

On the other hand, condition (26) indicates that the amount of _relative
trust_ in stubborn agents cannot be too small. This is reasonable in that the
network sensing performance should depend on the influencing power of the
stubborn agents. The effect of the known support is also reflected. In
particular, an increase in $s_{i}$ leads to a decrease in $n_{i}$ and an
increase in $\beta_{i}$. The maximum allowed sparsity $\alpha_{i}$ is
increased as a result. We conclude this subsection with the following remarks.

###### Remark 2

When $n$ is finite, the failure probability may grow with the size of
$\Omega_{\overline{\bm{B}}}$, i.e., it is ${\cal O}(d^{5})$, coinciding with
the intuition concerning the tradeoff between the size of
$\Omega_{\overline{\bm{B}}}$ and the sparse recovery performance. Although the
failure probability vanishes as $n-n_{s}\rightarrow\infty$, the parameter $d$
should be chosen judiciously in the design.

###### Remark 3

Another important issue that affects the recoverability of (17) is the degree
distribution in $G$ as the conditions in Theorem 1 requires the sparsity level
of $\overline{\bm{D}}$ to be small for every row. Given a fixed total number
of edges, it is easier to recover a network with a concentrated degree
distribution (e.g., the Watts-Strogatz network [46]) while a network with
power law degree distribution (e.g., the Barabasi-Albert network [47]) is more
difficult to recover.

###### Remark 4

The requirement on the number of stubborn agents in Theorem 1 may appear to be
restrictive. However, note that only the expected value $\overline{\bm{B}}$ is
considered in the model. Theoretically, one only need to employ a small number
of stubborn agents that _randomly_ wander in different positions of the social
network and ‘act’ as agents with different opinion, thus achieving an effect
similar to that of a synthetic aperture RADAR. This effectively creates a vast
number of _virtual_ stubborn agents from a small number of _physically
present_ stubborn agents.

##  IV Implementations of Social Network Sensing

In this section we discuss practical issues involved in implementing our
network sensing method. First, we develop a fast algorithm for solving large-
scale network sensing problems. Second, we consider a random opinion dynamics
model and propose a consistent estimator for the steady state.

###  IV-A Proximal Gradient Method for Network Sensing

This subsection presents a practical implementation method for large-scale
network sensing when $n\gg 0$. We resort to a first order optimization method.
The main idea is to employ a proximal gradient method [48] to the following
problem:

$\begin{array}[]{rl}\displaystyle\min_{{\bm{D}},{\bm{B}}}&\lambda\|{\rm
vec}({\bm{D}})\|_{1}+f({\bm{B}},{\bm{D}})\\\ {\rm s.t.}&{\bm{B}}\geq{\bf
0},~{}{\bm{D}}\geq{\bf 0},~{}{\cal P}_{{\cal S}^{c}}({\bm{D}})={\bm{0}},\\\
&{\cal P}_{\Omega_{\overline{\bm{B}}}^{c}}({\bm{B}})={\bm{0}},~{}{\rm
diag}({\bm{D}})={\bm{c}},\end{array}$ (29)

where

$f({\bm{B}},{\bm{D}})=\|({\bm{I}}-{\bm{D}})\hat{\bm{Y}}{\bm{Z}}^{\dagger}-{\bm{B}}\|_{F}^{2}+\gamma\|{\bm{B}}{\bf
1}+{\bm{D}}{\bf 1}-{\bf 1}\|_{2}^{2}$

and $\gamma>0$. Note that ${\bm{Z}}^{\dagger}$ is the right pseudo-inverse of
${\bm{Z}}$. Problem (29) can be seen as the Lagrangian relaxation of (18).
Meanwhile, similar to the first case considered in Section III, we take
$\lambda=0$ when $|{\cal S}|\approx|\Omega_{\overline{\bm{D}}}|$.

The last term in (29) is continuously differentiable. Let us denote the
feasible set of (29) as ${\cal L}$:

$\begin{split}{\cal L}=&\\{({\bm{B}},{\bm{D}}):{\bm{B}}\geq{\bf
0},~{}{\bm{D}}\geq{\bf 0},~{}{\cal P}_{{\cal S}^{c}}({\bm{D}})={\bm{0}}\\\
&{\cal P}_{\Omega_{\overline{\bm{B}}}^{c}}({\bm{B}})={\bm{0}},~{}{\rm
diag}({\bm{D}})={\bm{c}}\\}.\end{split}$ (30)

Let $\ell\in\mathbb{N}$ be the iteration index of the proximal gradient
method. At the $\ell$th iteration, we perform the following update:

$\begin{array}[]{rl}\displaystyle({\bm{B}}^{\ell},{\bm{D}}^{\ell})=\arg\min_{({\bm{B}},{\bm{D}})\in{\cal
L}}&\hskip 11.38092pt\alpha\lambda\|{\rm vec}({\bm{D}})\|_{1}\\\
&+\|{\bm{B}}-\tilde{\bm{B}}^{\ell-1}\|_{F}^{2}+\|{\bm{D}}-\tilde{\bm{D}}^{\ell-1}\|_{F}^{2}\end{array}$
(31)

where

$\displaystyle\tilde{\bm{D}}^{\ell}$
$\displaystyle={\bm{D}}^{\ell}-\alpha\nabla_{{\bm{D}}}f({\bm{B}}^{\ell},{\bm{D}})\big{|}_{{\bm{D}}={\bm{D}}^{\ell}}$
(32a) $\displaystyle\tilde{\bm{B}}^{\ell}$
$\displaystyle={\bm{B}}^{\ell}-\alpha\nabla_{{\bm{B}}}f({\bm{B}},{\bm{D}}^{\ell})\big{|}_{{\bm{B}}={\bm{B}}^{\ell}},$
(32b)

and $\alpha>0$ is a fixed step size such that $\alpha<1/L$, where $L$ is the
Lipschitz constant for the gradient of $f$.

Importantly, the proximal update (31) admits a closed form solution using the
soft-thresholding operator:

$\displaystyle{\bm{B}}^{\ell}$ $\displaystyle=\max\\{{\bm{0}},{\cal
P}_{\Omega_{\overline{\bm{B}}}^{c}}(\tilde{\bm{B}}^{\ell-1})\\}$ (33a)
$\displaystyle{\rm off}({\bm{D}}^{\ell})$ $\displaystyle={\cal P}_{{\cal
S}^{c}}(\texttt{soft\\_th}_{\alpha\lambda}({\rm
off}(\tilde{\bm{D}}^{\ell-1}))),$ (33b)

where $\texttt{soft\\_th}_{\lambda}(\cdot)$ is a _one-sided_ soft thresholding
operator [49] that applies element-wisely and
$\texttt{soft\\_th}_{\lambda}(x)=u(x)\max\\{0,x-\lambda\\}$. To further
accelerate the algorithm, we adopt an update rule similar to the fast
iterative shrinkage (FISTA) algorithm in [49], as summarized in Algorithm 1.
As seen, the per-iteration complexity is ${\cal O}(n^{2}+n\cdot n_{s})$; i.e.,
it is linear in the number of variables.

Algorithm 1 FISTA algorithm for (29).

1: Initialize: $({\bm{B}}^{0},{\bm{D}}^{0})\in{\cal L}$, $t_{0}=0$, $\ell=1$;

2: while  _convergence is not reached_ do

3: Compute the proximal gradient update direction:
$\displaystyle\bm{dB}^{\ell}$ $\displaystyle\leftarrow\max\\{{\bm{0}},{\cal
P}_{\Omega_{\overline{\bm{B}}}^{c}}(\tilde{\bm{B}}^{\ell-1})\\}$
$\displaystyle\bm{dD}^{\ell}$ $\displaystyle\leftarrow{\cal P}_{{\cal
S}^{c}}(\texttt{soft\\_th}_{\alpha\lambda}({\rm
off}(\tilde{\bm{D}}^{\ell-1}))),$ where
$\tilde{\bm{B}}^{\ell-1},\tilde{\bm{D}}^{\ell-1}$ are given by (32).

4: Update $t_{\ell}\leftarrow(1+\sqrt{1+4t_{\ell-1}^{2}})/2$.

5: Update the variables as:  $\displaystyle\bm{B}^{k}$
$\displaystyle\leftarrow\bm{dB}^{\ell}+\frac{t_{\ell-1}-1}{t_{\ell}}(\bm{dB}^{\ell}-\bm{dB}^{\ell-1})$
$\displaystyle{\rm off}(\bm{D}^{\ell})$
$\displaystyle\leftarrow\bm{dD}^{\ell}+\frac{t_{\ell-1}-1}{t_{\ell}}(\bm{dD}^{\ell}-\bm{dD}^{\ell-1}),$

6: $\ell\leftarrow\ell+1.$

7: end while

8: Set ${\rm diag}({\bm{D}}^{\ell})\leftarrow{\bm{c}}$.

9: Return: $({\bm{B}}^{\ell},{\bm{D}}^{\ell})$.

We conclude this subsection with a discussion on the convergence of Algorithm
1. As (29) is convex and $f$ is continuously differentiable, the proximal
gradient method using (31) is guaranteed [49] to converge to an optimal
solution of (29). Moreover, the convergence speed is ${\cal O}(1/\ell^{2})$.

###  IV-B Random Opinion Dynamics

So far, our method for network sensing only requires collecting the asymptotic
states $\mathbb{E}\\{{\bm{y}}(\infty;k)|{\bm{x}}(0;k)\\}$. Importantly, the
data matrices $\hat{\bm{Y}}$ and ${\bm{Z}}$ (cf. (10)) can be collected easily
when the trust matrix ${\bm{W}}(t;k)$ is deterministic; i.e.,
${\bm{W}}(t;k)=\overline{\bm{W}}$ for all $t,k$, and the observations are
noiseless. For the case where ${\bm{D}}(t;k)$ is random, computing the
expectation may be difficult since the latter is an average taken over an
ensemble of the sample paths of $\\{{\bm{W}}(t;k)\\}_{\forall t,\forall k}$.

This section considers adopting the proposed active sensing method to the case
with randomized opinion dynamics, which captures the possible randomness in
social interactions. Our idea is to propose a consistent estimator for
$\mathbb{E}\\{{\bm{y}}(\infty;k)|{\bm{z}}(0;k)\\}$ using the opinions gathered
from the same time series $\\{\hat{\bm{x}}(t;k)\\}_{t\in{\cal T}_{k}}$, where
${\cal T}_{k}\subseteq\mathbb{Z}^{+}$ is now an arbitrary sampling set.
Specifically, we show that the random process ${\bm{x}}(t;k)$ is ergodic. We
first make an interesting observation pertaining to random opinion dynamics:

###### Observation 3

[26, Theorem 2] [30] When $n_{s}\geq 2$ and under a random opinion dynamics
model, the opinions will not converge; i.e.,
${\bm{x}}(t;k)\neq{\bm{x}}(t-1;k)$ almost surely.

Observation 3 suggests that a natural approach to computing the expectation
$\mathbb{E}\\{{\bm{y}}(\infty;k)|{\bm{x}}(0;k)\\}$ is by taking averages over
the temporal samples. We propose the following estimator:

$\mathbb{E}\\{{\bm{x}}(\infty;k)|{\bm{x}}(0;k)\\}\approx\hat{\bm{x}}({\cal
T}_{k};k)\triangleq\frac{1}{|{\cal T}_{k}|}\sum_{t\in{\cal
T}_{k}}\hat{\bm{x}}(t;k),$ (36)

where we recall the definition for $\hat{\bm{x}}(t;k)$ from (3). Notice that
$\mathbb{E}\\{{\bm{y}}(\infty;k)|{\bm{x}}(0;k)\\}$ can be retrieved from
$\mathbb{E}\\{{\bm{x}}(\infty;k)|{\bm{x}}(0;k)\\}$ by taking the last
$n-n_{s}$ elements of the latter. In order to compute the right hand side in
(36), we only need to know the cardinality of ${\cal T}_{k}$; i.e., the number
of samples collected. Knowledge on the members in ${\cal T}_{k}$ is not
required. Specifically, the temporal samples can be collected through random
(and possibly noisy) sampling at time instances on the opinions. The following
theorem characterizes the performance of (36):

###### Theorem 2

Consider the estimator in (36) with a sampling set ${\cal T}_{k}$. Denote
$\overline{\bm{x}}(\infty;k)\triangleq\lim_{t\rightarrow\infty}\mathbb{E}\\{{\bm{x}}(t;k)|{\bm{x}}(0;k)\\}=\overline{\bm{W}}^{\infty}{\bm{x}}(0;k)$
and assume that $\mathbb{E}\\{\|{\bm{D}}(t;k)\|_{2}\\}<1$. If
$T_{o}\rightarrow\infty$, then

  1. 1.

the estimator (36) is unbiased:

$\mathbb{E}\\{\hat{\bm{x}}({\cal
T}_{k};k)|{\bm{z}}(0;k)\\}=\overline{\bm{x}}(\infty;k).$ (37)

  2. 2.

the estimator (36) is asymptotically consistent:

$\lim_{|{\cal T}_{k}|\rightarrow\infty}\mathbb{E}\\{\|\hat{\bm{x}}({\cal
T}_{k};k)-\overline{\bm{x}}(\infty;k)\|_{2}^{2}|{\bm{x}}(0;k)\\}=0.\vspace{.2cm}$
(38)

For the latter case, we have

$\begin{array}[]{l}\displaystyle\mathbb{E}\\{\|\hat{\bm{x}}({\cal
T}_{k};k)-\overline{\bm{x}}(\infty;k)\|_{2}^{2}|{\bm{x}}(0;k)\\}\\\
\displaystyle~{}~{}\leq\frac{{C^{\prime}}}{|{\cal
T}_{k}|}\Big{(}\sum_{i=0}^{|{\cal
T}_{k}|-1}\lambda^{\min_{\ell}|t_{\ell+i}-t_{\ell}|}\Big{)},\end{array}$ (39)

where $C^{\prime}<\infty$ is a constant and
$\lambda=\lambda_{max}(\overline{\bm{D}})<1$, i.e., the latter term is a
geometric series with bounded sum.

Note that a similar result to Theorem 2 was reported in [50]. Our result is
specific to the case with stubborn agents, which allows us to find a precise
characterization of the mean square error. The proof of Theorem 2 can be found
in Appendix C.

###### Remark 5

From (39), we observe that the upper bound on the mean square error can be
optimized by maximizing $\min_{i,j,i\neq j}|t_{i}-t_{j}|$. Suppose that the
samples $\hat{\bm{x}}({\cal T}_{k};k)$ have to be taken from a finite interval
$[T_{max}]\setminus[T_{o}]$, $T_{max}<\infty$ and $|{\cal T}_{k}|<\infty$;
here, the best estimate can be obtained by using sampling instances that are
drawn uniformly from $[T_{max}]\setminus[T_{o}]$.

##  V Numerical Results

To validate our methods, we conducted several numerical simulations,
reconstructing both synthetic networks and real networks. In this section, we
focus on cases where the network dynamics model (2) is exact (while the
measurement may be noisy),but emphasize the crucial importance of considering
data collected from real networks, e.g., the online social networks (e.g.,
Facebook, Twitter). The Monte-Carlo simulations were obtained by averaging
over at least $100$ simulation trials. We also set $K=2n_{s}$ and
${\bm{c}}={\bm{0}}$ to respect the requirement $K\geq n_{s}$ and for ease of
comparison.

###  V-A Synthetic networks with noiseless measurement

We evaluate the sensing performance on a synthetic network with noiseless
measurement on the steady system state. In light of Theorem 1, for the
placement of the stubborn agents, we randomly connect $d$ stubborn agents to
each ordinary agent.

Figure 2: Comparing performance against the number of stubborn agents $n_{s}$.
(Left) The NMSE. (Right) The average support recovery error. In the legend,
‘full’ denotes the case with full support information; ‘(ps=0.1)’ and ‘(d=5)’
denotes the case where $\overline{\bm{B}}$ is constructed as a random
bipartite graph and a random $d$-regular bipartite graph, respectively.

The first numerical example compares performance in recovering
$\overline{\bm{D}}^{\prime}$ and $\overline{\bm{B}}^{\prime}$ against the
number of stubborn agents $n_{s}$. We fix the number of ordinary agents at
$n-n_{s}=60$. The network $G$ is constructed as an Erdos-Renyi (ER) graph with
connectivity $p=0.1$. Furthermore, the weights in $\overline{\bm{W}}$ are
generated uniformly first, and normalized to satisfy
$\overline{\bm{W}}{\bm{1}}={\bm{1}}$ afterwards. As the problem size
considered is moderate $(n\leq 100)$, the network reconstruction problem (18)
is solved using cvx.

We present the normalized mean square error (NMSE) under the above scenario in
Fig. 2. The NMSE of $\overline{\bm{D}}^{\prime}$ is defined as
$\|\hat{\bm{D}}-\overline{\bm{D}}^{\prime}\|_{F}^{2}/\|\overline{\bm{D}}^{\prime}\|_{F}^{2}$
(and similarly for $\overline{\bm{B}}^{\prime}$). The NMSE against $n_{s}$ is
shown for two cases: (i) solving (15) when ${\cal
S}=\Omega_{\overline{\bm{D}}}$; (ii) solving (18) when ${\cal
S}=[n-n_{s}]\times[n-n_{s}]$. We also include the NMSE curve when
$\overline{\bm{B}}$ corresponds to a random ER bipartite graph with edge
connectivity $p=0.1$. The figure shows, first that only $n_{s}\approx 20$
stubborn agents are needed when the full support information is given. By
contrast, we need $n_{s}\approx 40$ to attain a similar NMSE when there is no
support information. Comparing the NMSE to $d$-regular/random graph
construction for $\overline{\bm{B}}$ shows that the recovery performance is
significantly better when using the $d$-regular graph construction; e.g., if
$d=5$, the NMSE of $\overline{\bm{D}}^{\prime}$ is less than $10^{-3}$ with
$n_{s}\geq 33$. This implies that by inserting almost half the number of
ordinary agents into the network, the social network structure can be revealed
with high accuracy. This result is consistent with the Theorem 1, which
predicts that when $\beta\geq 0.604$, i.e., $n_{s}\approx 36$, perfect
recovery can be achieved. The discrepancy between the simulation results and
Theorem 1 is possibly due to the fact that we are solving (18) instead of
(17). Moreover, in an ER graph, $\overline{\bm{d}}_{i}^{\prime}$ is only
$p(n-n_{s})$-sparse on average, but Theorem 1 requires that _every_ row of
$\overline{\bm{D}}^{\prime}$ to be $p(n-n_{s})$-sparse.

Figure 3: Comparing performance against the number of stubborn agents $n_{s}$
with different network models. (Left) The NMSE. (Right) The average support
recovery error.

In the second example, we examine the scenarios when $G$ is constructed as the
Barabasi-Albert (BA) graph with minimum degree $m=2$ for each incoming node
[47] or the Strogatz-Watts (SW) graph where each node is initially connected
to $b=2$ left and right nodes and the rewiring probability is $p=0.08$ [46].
The results are shown in Fig. 3. It shows that the SW network can be recovered
with high accuracy by using a much smaller number of stubborn agents than
either the ER or BA networks. One possible explanation is that most of the
vertices in SW have the same degree.

Figure 4: Comparing the NMSE against the number of ordinary agents $n-n_{s}$.
Fix $p=0.08$ and $\beta$ is given by Theorem 1 as $0.528~{}(d=5)$,
$0.385~{}(d=6)$ and $0.319~{}(d=7)$.

The third numerical example examines the claim in Theorem 1. Recall that the
latter requires $n-n_{s}\rightarrow\infty$ for its validity. We consider the
ER graph as in the first example and fix the connectivity of $G$ at $p=0.08$
where the smallest $\beta$ required by Theorem 1 are respectively
$0.528~{}(d=5)$, $0.385~{}(d=6)$ and $0.319~{}(d=7)$. We set
$n_{s}=\lceil\beta(n-n_{s})\rceil$ and vary the number of ordinary agents
$n-n_{s}$ to compare the NMSE. The NMSE comparison against $n-n_{s}$ can be
found in Fig. 4. In all three cases tested $(d=5,6,7)$, there is a decreasing
trend of the NMSE with $n-n_{s}$, suggesting that the failure probability
decreases with $n-n_{s}\rightarrow\infty$. Moreover, although $d=7$ places the
least requirement on $\beta$, it also has the highest probability of failure
when $n$ is finite, since the upper bound to failure probability grows with
${\cal O}(d^{5})$. The simulation results suggest that $d$ needs to be chosen
judiciously when deciding on the required number/placement of stubborn agents.

Figure 5: Comparing the NMSE against the percentage of known sparsity indices
in $\Omega_{\overline{\bm{W}}}^{c}$, i.e., $|{\cal S}|$ decreases when
$p_{known}$ increases .

Figure 6: Comparing the social network of ReedCollege from the facebook100
dataset: (Left) the original network; (Right) the estimated network.

The next simulation example in Fig. 5 examines the case where a superset
${\cal S}$ of $\Omega_{\overline{\bm{D}}}$ is known. In particular, we
consider the ER network model with $n-n_{s}=60$ and connectivity $p=0.1$ and
compare the NMSE against the percentage of exposed
$\Omega_{\overline{\bm{D}}}^{c}$. The figure shows that the network sensing
performance improves as $p_{known}$ increases. When $40\%$ of the support of
$\overline{\bm{D}}$ is exposed, employing $n_{s}=28$ stubborn agents yields a
satisfactory NMSE of $10^{-3}$.

###  V-B Real world networks

This subsection examines the performance of the proposed method applied to
real network data. Specifically, we consider the facebook100 dataset [51] and
focus on the medium-sized network example ReedCollege. The randomized opinion
exchange model is based on the randomized broadcast gossip protocol in [52]
with uniformly assigned trust weights. Out of the available agents, we picked
$n_{s}=180$ agents with degrees closest to the median degree as the stubborn
agents and removed the agents that are not adjacent to _any_ of the stubborn
agents. The selection of the stubborn agents is motivated by Theorem 1 as we
require a moderate average degree for the resultant stubborn-to-nonstubborn
agent network with better recovery guarantees. Our aim is to estimate the
trust matrix $\overline{\bm{D}}$, which corresponds to the subgraph with
$n-n_{s}=666$ ordinary agents, $|E|=13,269$ edges and mean degree $19.92$.
Note that the bipartite graph from stubborn agents to ordinary agents has a
mean degree of $25.07$.

The opinion dynamics data $\hat{\bm{Y}}$ is collected using the estimator in
Section IV-B, where we set $|{\cal T}_{k}|=5\times 10^{5}$ and the sampling
instances are uniformly taken from the interval $[10^{5},5\times 10^{7}]$. We
apply the FISTA algorithm developed in Section IV to approximately solve the
network reconstruction problem (18), with $\lambda=n\times 10^{-12}$ and
$\gamma=10^{-3}/\gamma$. The NMSE of the reconstructed
$\overline{\bm{D}}^{\prime}$ is $0.1035$ after $4\times 10^{4}$ iterations.
The program has terminated in about $30$ minutes on an Intel™ Xeon™ server
running MATLAB™ 2014b. It is computationally infeasible to deploy generic
solvers such as cvx as the number of variables involved is $563,436$.

We compared the estimated social network in both macroscopic and microscopic
levels. Fig. 6 shows the true/estimated network plotted in gephi [53] using
the ‘Force Atlas 2’ layout (with random initialization), where the edge
weights are taken into account333Readers are advised to read the figures on a
color version of this paper.. While it is impossible to compare every edges in
the network, the figure gives a macroscopic view of the efficacy of the
network reconstruction method. In particular, using $n_{s}=180$ stubborn
agents, the estimated network follows a similar topology as the original one.
For instance, there are clearly two clusters in both the estimated and
original network. Moreover, the relative roles for individual agents are
matched in both networks. For example, agents $\\{39,...,608\\}$ are found in
the larger cluster, agents $\\{378,...,663\\}$ are found at the boundary
between the clusters and agents $\\{43,...,404\\}$ are found in the smaller
cluster, in both networks.

Figure 7: Comparing the reconstructed network for the ReedCollege social
network in facebook100 dataset. (Left) Original network. (Right) Reconstructed
network.

Finally, in Fig. 7 we compare the estimated principal sub-matrix of
$\overline{\bm{D}}^{\prime}$ taken from the first 60 rows/columns, i.e., this
corresponds to the social network between 60 agents. As seen, the original and
estimated matrices appears to be similar to each other, both in terms of the
support set and the weights on individual edges between the agents.

##  VI Conclusions

In this paper, we considered the social network sensing problem using data
collected from steady states of opinion dynamics. The opinion dynamics is
based on an extension of the linear DeGroot model with stubborn agents, where
the latter plays a key role in exposing the network structure. Our main result
is that the social network sensing problem can be cast as a sparse recovery
problem and a sufficient condition for perfect recovery was proven. In
addition, a consistent estimator was also derived to handle the case where the
network dynamics is random and a low complexity algorithm is proposed. Our
simulation results on synthetic and real networks indicate that the network
structure can be reconstructed with high accuracy when a sufficient number of
stubborn agents is present.

Ongoing research is focused on extending the active sensing method to
nonlinear opinion dynamics models such as the Hegselmann and Krause model,
working on real social network data collected from social media and combining
this approach with the detection of stubborn agents.

## Acknowledgement

The authors are indebted to the anonymous reviewers for their invaluable
comments to improve the current paper.

##  Appendix A Proof of Lemma 1

It is easy to check that:

$\tilde{\bm{B}}{\bf 1}+\tilde{\bm{D}}{\bf 1}=\bm{\Lambda}({\bm{B}}{\bf 1}+{\rm
off}({\bm{D}}){\bf 1})+{\rm diag}(\tilde{\bm{D}})={\bf 1},$ (40)

where the last equality is due to
${\bm{B}}{\bm{1}}+{\bm{D}}{\bm{1}}={\bm{1}}$. Furthermore,

$\begin{array}[]{l}({\bm{I}}-\tilde{\bm{D}})^{-1}\tilde{\bm{B}}=({\bm{I}}-\bm{\Lambda}{\rm
off}({\bm{D}})-{\rm Diag}({\rm
diag}(\tilde{\bm{D}})))^{-1}\bm{\Lambda}{\bm{B}}.\end{array}$ (41)

As ${\rm Diag}({\rm
diag}(\tilde{\bm{D}}))={\bm{I}}-\bm{\Lambda}+\bm{\Lambda}{\rm Diag}({\rm
diag}({\bm{D}}))$, we have:

$\begin{array}[]{l}({\bm{I}}-\tilde{\bm{D}})^{-1}\tilde{\bm{B}}=({\bm{I}}-{\bm{D}})^{-1}{\bm{B}}.\end{array}$
(42)

##  Appendix B Proof of Theorem 1

With a slight abuse of notations, in this appendix we assume that there are
$n$ ordinary agents and $n_{s}$ stubborn agents. In particular, the dimensions
of the variables are $\overline{\bm{D}}^{\prime}\in\mathbb{R}^{n\times n}$ and
$\overline{\bm{B}}^{\prime}\in\mathbb{R}^{n\times n_{s}}$. For simplicity, we
set $n_{i}=n$, $\alpha_{i}=\alpha$ and $\beta_{i}=\beta$ for all $i$.

The proof of Theorem 1 is divided into two parts. The first part shows a
sufficient condition for recovering
$(\overline{\bm{B}}^{\prime},\overline{\bm{D}}^{\prime})$ using (17); and the
second part shows that the sufficient condition holds with high probability as
$n\rightarrow\infty$.

Let $d(v)$ denote the degree of a vertex $v$. Our proof relies on the
following definition of an unbalanced expander graph:

###### Definition 2

An $(\alpha,\delta)$-unbalanced expander graph is an $A,B$-bipartite graph
(bigraph) with $|A|=n,|B|=m$ with left degree bounded in $[d_{l},d_{u}]$,
i.e., $d(v_{i})\in[d_{l},d_{u}]$ for all $v_{i}\in A$, such that for any
$S\subseteq A$ with $|S|\leq\alpha n$, we have $\delta|E(S,B)|\leq|N(S)|$,
where $E(S,B)$ is the set of edges connected from $S$ to $B$ and
$N(S)=\\{v_{j}\in B:\exists~{}v_{i}\in S~{}s.t.~{}v_{j}v_{i}\in E\\}$ is the
neighbor set of $S$ in $B$.

We imagine that $A$ ($B$) is the set of ordinary (stubborn) agents and
$E(A,B)$ represents the connection between stubborn and ordinary agents; see
the illustration in Fig. 8. We denote the collection of
$(\alpha,\delta)$-unbalanced expander graphs by ${\cal G}(\alpha,\delta)$.
Previous works [40, 41, 42, 39] have shown that the expander graph structure
allows for the construction of measurement matrices with good sparse recovery
performance.

Figure 8: Illustrating the properties of the expander graph. In the above
example bipartite graph, if $\alpha=1/3$, $\delta$ is at most $3/4$ since
$|E(S,B)|=4$ and $|N(S)|=3$ when $S$ is the first two vertices in the set of
ordinary agents.

We now proceed by showing the sufficient condition. Denote the support of
${\bm{b}}_{i}-\overline{\bm{b}}_{i}^{\prime}$ as
$\Omega_{\overline{\bm{B}}}^{i}$, where $|\Omega_{\overline{\bm{B}}}^{i}|=d$.
Since $\Omega_{\overline{\bm{B}}}^{i}$ is known a-priori,
${\bm{b}}_{i}-\overline{\bm{b}}_{i}^{\prime}$ is a sparse vector supported on
$\Omega_{\overline{\bm{B}}}^{i}$. We can thus treat the rows where
${\bm{b}}_{i}$ is supported on as ‘erasure bits’, which can be ignored. In
particular, the following rows-deleted linear system can be deduced from the
last line in (24):

$\overline{\bm{B}}_{(\Omega_{\overline{\bm{B}}}^{i})^{c}}^{{}^{\prime}T}({\bm{I}}-\overline{\bm{D}}^{\prime})^{-T}(\overline{\bm{d}}_{i}^{\prime}-{\bm{d}}_{i})={\bm{0}},$
(43)

where
$\overline{\bm{B}}_{(\Omega_{\overline{\bm{B}}}^{i})^{c}}^{{}^{\prime}T}$ is a
$d$-rows-deleted matrix obtained from $\overline{\bm{B}}^{{}^{\prime}T}$.

We prove the sufficient condition by deriving a Restricted Isometry Property-1
(RIP-1) condition for
${\bm{A}}={\bm{B}}_{(\Omega_{\overline{\bm{B}}^{i}})^{c}}^{T}$ and its
perturbation ${\bm{A}}({\bm{I}}-\overline{\bm{D}}^{\prime})^{-T}$. We define
$a_{min}=\min_{ij\in{\rm supp}({\bm{A}})}A_{ij}$ and $a_{max}=\max_{ij\in{\rm
supp}({\bm{A}})}A_{ij}$ and prove the following proposition:

###### Proposition 3

Let $n>m$ and ${\bm{A}}\in\mathbb{R}^{m\times n}$ be a non-negative matrix
that has the same support as the adjacency matrix of an
$(\alpha,\delta)$-unbalanced bipartite expander graph with bounded left
degrees $[d_{l},d_{u}]$. Then ${\bm{A}}$ satisfies the RIP-1 property:

$\big{(}a_{min}\delta d_{l}-a_{max}(d_{u}-\delta
d_{l})\big{)}\|{\bm{x}}\|_{1}\leq\|{\bm{A}}{\bm{x}}\|_{1}\leq
d_{u}a_{max}\|{\bm{x}}\|_{1},$ (44)

for all $k$-sparse ${\bm{x}}$ such that $k\leq\alpha n$. Furthermore, we have

$\upsilon^{\star}\cdot\|{\bm{x}}\|_{1}\leq\|{\bm{A}}({\bm{I}}-\overline{\bm{D}}^{\prime})^{-T}{\bm{x}}\|_{1},$
(45)

where $\upsilon^{\star}=a_{min}\delta d_{l}-a_{max}(d_{u}-\delta
d_{l})-(1-d_{l}a_{min})$.

Proof. The following proof is a generalization of [42, Appendix D]. First of
all, the upper bound in (44) follows from
$\|{\bm{A}}{\bm{x}}\|_{1}\leq\|{\bm{A}}\|_{1,1}\|{\bm{x}}\|_{1}$, where
$\|{\bm{A}}\|_{1,1}$ is the matrix norm induced by $\|\cdot\|_{1}$ on
${\bm{A}}$ [54], i.e.,

$\|{\bm{A}}\|_{1,1}=\max_{1\leq j\leq n}\sum_{i=1}^{m}|A_{ij}|.$ (46)

Obviously we have $\|{\bm{A}}\|_{1,1}\leq d_{u}a_{max}$.

To prove the lower bound in (44), using the expander property, we observe that

$\delta d_{l}|S|\leq\delta|E(S,B)|\leq|N(S)|,$ (47)

for all $S\subseteq{\rm supp}({\bm{x}})=\\{i:x_{i}\neq 0\\}$ and
$|S|\leq\alpha n$. As a consequence of Hall’s theorem [55], the bigraph
induced by ${\bm{A}}$ contains $\delta d_{l}$ disjoint matchings for ${\rm
supp}({\bm{x}})$. We can thus decompose ${\bm{A}}$ as:

${\bm{A}}={\bm{A}}_{M}+{\bm{A}}_{C},$ (48)

where the decomposition is based on dividing the support such that ${\rm
supp}({\bm{A}}_{M})\cap{\rm supp}({\bm{A}}_{C})=\emptyset$. In particular,
${\bm{A}}_{M}$ is supported on the $\delta d_{l}$ matchings for ${\rm
supp}({\bm{x}})$; i.e., by the matching property, each row of ${\bm{A}}_{M}$
has at most one non-zero, and each column of ${\bm{A}}_{M}$ has $\delta d_{l}$
non-zeros, and the remainder ${\bm{A}}_{C}$ has at most $d_{u}-\delta d_{l}$
non-zeros per column. Applying the triangular inequality gives:

$\|{\bm{A}}{\bm{x}}\|_{1}\geq\|{\bm{A}}_{M}{\bm{x}}\|_{1}-\|{\bm{A}}_{C}{\bm{x}}\|_{1},$
(49)

since $\|{\bm{A}}_{M}{\bm{x}}\|_{1}\geq a_{min}\delta d_{l}\|{\bm{x}}\|_{1}$
and $\|{\bm{A}}_{C}{\bm{x}}\|_{1}\leq a_{max}(d_{u}-\delta
d_{l})\|{\bm{x}}\|_{1}$, this implies:

$\|{\bm{A}}{\bm{x}}\|_{1}\geq\big{(}a_{min}\delta d_{l}-a_{max}(d_{u}-\delta
d_{l})\big{)}\|{\bm{x}}\|_{1}.$ (50)

For the second part in the lemma, i.e., (45), note that:

$\|{\bm{A}}({\bm{I}}-\overline{\bm{D}}^{\prime})^{-T}{\bm{x}}\|_{1}\geq\|{\bm{A}}{\bm{x}}\|_{1}-\|{\bm{A}}\overline{\bm{D}^{\prime}}^{T}({\bm{I}}-\overline{\bm{D}}^{\prime})^{-T}{\bm{x}}\|_{1},$
(51)

since
${\bm{A}}({\bm{I}}-\overline{\bm{D}}^{\prime})^{-T}{\bm{x}}={\bm{A}}{\bm{x}}+{\bm{A}}\overline{\bm{D}}^{\prime
T}({\bm{I}}-\overline{\bm{D}}^{\prime})^{-T}{\bm{x}}$. The latter quantity can
be upper bounded by

$\begin{array}[]{l}\|{\bm{A}}\overline{\bm{D}^{\prime}}^{T}({\bm{I}}-\overline{\bm{D}}^{\prime})^{-T}{\bm{x}}\|_{1}\\\
~{}\leq\|{\bm{A}}\|_{1,1}\|\overline{\bm{D}^{\prime}}^{T}\|_{1,1}\|({\bm{I}}-\overline{\bm{D}}^{\prime})^{-T}\|_{1,1}\|{\bm{x}}\|_{1}\\\
\displaystyle~{}\leq
d_{u}a_{max}\frac{\|\overline{\bm{D}^{\prime}}^{T}\|_{1,1}}{1-\|\overline{\bm{D}^{\prime}}^{T}\|_{1,1}}\|{\bm{x}}\|_{1}\leq(1-d_{l}a_{min})\|{\bm{x}}\|_{1},\end{array}$
(52)

where in the second to last inequality, we used the property
$\|({\bm{I}}-{\bm{C}})^{-1}\|\leq 1/(1-\|{\bm{C}}\|)$ for any $\|{\bm{C}}\|<1$
[54]; and in the last inequality, we used the fact that
$1-d_{u}a_{max}\leq\|\overline{\bm{D}^{\prime}}^{T}\|_{1,1}\leq
1-d_{l}a_{min}$ (note that each row in $\overline{\bm{D}^{\prime}}$ sums to at
most $1-d_{l}a_{min}$ and at least $1-d_{u}a_{max}$). Combining (50), (51) and
(52) yields the desired inequality. Q.E.D.

A sufficient condition for $\ell_{0}$ recovery can be obtained by proving the
following simple corollary:

###### Corollary 1

Let the conditions from Proposition 3 on ${\bm{A}}$ holds. Suppose that both
${\bm{x}}_{1},{\bm{x}}_{2}$ are $(k/2)$-sparse such that $k\leq\alpha n$ and:

${\bm{A}}({\bm{I}}-\overline{\bm{D}}^{\prime})^{-T}{\bm{x}}_{1}={\bm{A}}({\bm{I}}-\overline{\bm{D}}^{\prime})^{-T}{\bm{x}}_{2},$
(53)

then ${\bm{x}}_{1}={\bm{x}}_{2}$ if

$\upsilon^{\star}=a_{min}\delta d_{l}-a_{max}(d_{u}-\delta
d_{l})-(1-d_{l}a_{min})>0.$ (54)

Proof. Observe that ${\bm{x}}_{1}-{\bm{x}}_{2}$ is at most $k$-sparse, using
Proposition 3, we have

$\upsilon^{\star}\|{\bm{x}}_{1}-{\bm{x}}_{2}\|_{1}\leq\|{\bm{A}}({\bm{I}}-\overline{\bm{D}}^{\prime})^{-T}({\bm{x}}_{1}-{\bm{x}}_{2})\|_{1}=0.$
(55)

This implies that ${\bm{x}}_{1}={\bm{x}}_{2}$. Q.E.D.

As $\overline{\bm{d}}_{i}^{\prime}$ is $k/2$-sparse, $b_{min}\leq a_{min}$ and
$b_{max}\geq a_{max}$, Eq. (26) and Corollary 1 guarantee that
$\overline{\bm{d}}_{i}^{\prime}$ is the _unique_ solution out of all
$k/2$-sparse vectors that ${\bm{d}}_{i}$ satisfies (43). This means that any
${\bm{d}}_{i}$ that satisfies (43) must be either
$\overline{\bm{d}}_{i}^{\prime}$ or have $\|{\bm{d}}_{i}\|_{0}>(k/2)$. Since
the optimization problem (17) finds the sparsest solution satisfying (43), we
must have ${\bm{d}}_{i}^{\star}=\overline{\bm{d}}_{i}^{\prime}$ for all $i$.
Furthermore, this implies
${\bm{b}}_{i}^{\star}=\overline{\bm{b}}_{i}^{\prime}$ in (24) and we have
$({\bm{B}}^{\star},{\bm{D}}^{\star})=(\overline{\bm{B}},\overline{\bm{D}}^{\prime})$.

The second part of our proof shows that for all $i$, the support set of the
$d$-rows-deleted matrix
$\overline{\bm{B}}_{(\Omega_{\overline{\bm{B}}}^{i})^{c}}^{{}^{\prime}T}$
corresponds to an $(\alpha,\delta)$-expander graph with high probability. Our
plan is to first prove that the corresponding bipartite graph has a bounded
degree $r\in[d-1,d]$ with high probability (w.h.p.), and then show that a
randomly constructed bipartite with bounded degree $r\in[d-1,d]$ is also an
expander graph w.h.p..

Now, let us observe the following proposition:

###### Proposition 4

Let $G$ be a random $A,B$-bigraph with $|A|=n$, $|B|=n_{s}=\beta n$,
constructed by randomly connecting $d$ vertices from $A$ to each vertex of
$B$. All of the subgraphs $G_{1},...,G_{n}$ have left degree $r\in[d-1,d]$
with high probability (as $n\rightarrow\infty$) if each of these subgraphs is
formed by randomly deleting $d$ vertices from $B$ in $G$.

Proof. We lower bound the desired probability as follows:

$\begin{array}[]{l}{\rm Pr}\Big{(}G_{1},...,G_{n}=\text{bipartite with (left)
deg.~{}$r\in[d-1,d]$}\Big{)}\\\ =1-{\rm
Pr}\Big{(}\cup_{i=1}^{n}(G_{i}=\text{bipartite with
min.~{}deg.~{}$r<d-1$})\Big{)}\\\ \geq 1-n\cdot{\rm
Pr}\Big{(}\cup_{k=1}^{n}(d(v_{k})<d-1,~{}v_{k}\in A_{i},~{}A_{i}\subseteq
V(G_{i}))\Big{)}\\\ \geq 1-n^{2}\cdot{\rm Pr}\Big{(}d(v_{k})<d-1,~{}v_{k}\in
A_{i},~{}A_{i}\subseteq V(G_{i})\Big{)}\end{array}$ (56)

Note that the event described in the last term is equivalent to deleting at
least $2$ neighbors of $v_{k}\in A_{i}$ from $B$. As the neighbors of $A$ are
also randomly selected, the latter probability can be upper bounded by:

$\begin{array}[]{l}{\rm Pr}\Big{(}d(v_{k})<d-1,~{}v_{k}\in
A_{i},~{}A_{i}\subseteq V(G_{i})\Big{)}\\\ \displaystyle={\rm
Pr}\big{(}d(v_{k})=0\cup\cdots\cup d(v_{k})=d-2\big{)}\\\
\displaystyle\leq(d-1)\cdot\left(\frac{d^{2}}{(\beta
n)^{2}}\right)^{2}=(d-1)\cdot\left(\frac{d}{\beta n}\right)^{4},\end{array}$
(57)

Plugging this back into (56) yields the desired result. Q.E.D.

The proof of Theorem 1 is completed by the proposition:

###### Proposition 5

Let $G$ be a random $A,B$-bigraph with $|A|=n$, $|B|=\beta^{\prime}n=n_{s}-d$,
constructed by randomly connecting $r\in[d-1,d]$ vertices from $A$ to each
vertex of $B$. Then $G$ is an $(\alpha,1-1/(d-1))$-expander graph with high
probability if $d\geq 4$, $\alpha<\beta^{\prime}$ and
$d-1>(H(\alpha)+\beta^{\prime}H(\alpha/\beta^{\prime}))/\alpha\log(\beta^{\prime}/\alpha)$.

Proof. The following proof is similar in flavor to the proof of [42,
Proposition 1], with the additional complexity that the left degree is
variable. For simplicity, we denote ${\bm{A}}$ as the adjacency matrix of $G$
and let $E_{i_{1},...,i_{r}}$ be the event such that
${\bm{A}}_{:,i_{1},...,i_{r}}$ contains at least $m-r+1$ zero rows, where
${\bm{A}}_{:,i_{1},...,i_{r}}$ is the submatrix formed by choosing the
$\\{i_{1},...,i_{r}\\}$ columns. Note that if $r\leq\alpha n$ and
$E_{i_{1},...,i_{r}}$ occurs, $G\notin{\cal G}(\alpha,1-1/(d-1))$ since
$(1-1/(d-1))|E(\\{i_{1},...,i_{r}\\})|\geq
r>r-1=|N(\\{\\{i_{1},...,i_{r}\\})|$. The failure probability can thus be
upper bounded as:

$\begin{array}[]{l}\displaystyle{\rm Pr}\Big{(}G\notin{\cal
G}(\alpha,1-1/(d-1))\Big{)}\\\ \displaystyle\leq{\rm
Pr}\Big{(}\bigcup_{d-1\leq r\leq\alpha n,1\leq
i_{1}<i_{2}<\cdots<i_{r}}E_{i_{1},...,i_{r}}\Big{)}\\\
\displaystyle\leq\sum_{r=d-1}^{\alpha n}{n\choose r}{\rm
Pr}(E_{1,...,r}).\end{array}$ (58)

Suppose that there are $r-s$ columns with $d-1$ non-zero entries and $s$
columns with $d$ non-zero entries; hence we have ${\beta n\choose
d-1}^{r-s}{\beta n\choose d}^{s}$ possible sub-matrices to choose from. Now, a
necessary condition for $E_{1,...,r}$ is such that all the non-zero entries
are contained in a sub-sub-matrix of size $r\times r$. There are at most
${r\choose d-1}^{r-s}{r\choose d}^{s}$ possible configurations and ${\beta
n\choose r}$ such sub-sub-matrices. For this case, we obtain the upper bound:

$\begin{split}{\rm Pr}(E_{1,...,r},~{}{\rm
fix}~{}s)&\leq\frac{{\beta^{\prime}n\choose r}{r\choose d-1}^{r-s}{r\choose
d}^{s}}{{\beta^{\prime}n\choose d-1}^{r-s}{\beta^{\prime}n\choose d}^{s}}\\\
&\leq{\beta^{\prime}n\choose
r}\cdot\left(\frac{r}{\beta^{\prime}n}\right)^{(r-s)(d-1)}\cdot\left(\frac{r}{\beta^{\prime}n}\right)^{sd}\\\
&={\beta^{\prime}n\choose
r}\cdot\left(\frac{r}{\beta^{\prime}n}\right)^{(r-s)(d-1)+sd}\end{split}$ (59)

where we used the fact that ${r\choose d}/{m\choose d}\leq(r/m)^{d}$ if $r<m$.
Taking the union bound for all configurations $s\in[0,r]$ gives:

$\begin{array}[]{l}{\rm Pr}(E_{1,...,r})\leq\sum_{s=0}^{r}{\rm
Pr}(E_{1,...,r},~{}{\rm fix}~{}s)\vspace{.1cm}\\\
\displaystyle\leq{\beta^{\prime}n\choose
r}\cdot\left(\left(\frac{r}{\beta^{\prime}n}\right)^{r(d-1)}+\left(\frac{r}{\beta^{\prime}n}\right)^{r(d-1)+1}+\cdots+\left(\frac{r}{\beta^{\prime}n}\right)^{rd}\right)\\\
\displaystyle={\beta^{\prime}n\choose
r}\cdot\frac{1}{1-r/(\beta^{\prime}n)}\left(\left(\frac{r}{\beta^{\prime}n}\right)^{r(d-1)}-\left(\frac{r}{\beta^{\prime}n}\right)^{rd+1}\right)\\\
\displaystyle<\frac{1}{1-\alpha/\beta^{\prime}}{\beta^{\prime}n\choose
r}\cdot\left(\frac{r}{\beta^{\prime}n}\right)^{r(d-1)}\end{array}$ (60)

The second equality is due to the geometric series and the last inequality is
due to $r\leq\alpha n$. We thus have:

$\begin{array}[]{l}{\rm Pr}\Big{(}G\notin{\cal G}(\alpha,1-1/(d-1))\Big{)}\\\
~{}~{}~{}~{}~{}~{}~{}\displaystyle\leq\frac{1}{1-\frac{\alpha}{\beta^{\prime}}}\sum_{r=d-1}^{\alpha
n}{n\choose r}{\beta^{\prime}n\choose
r}\left(\frac{r}{\beta^{\prime}n}\right)^{r(d-1)}\end{array}$ (61)

The remainder of the proof follows from that of [42]; i.e., Lemma A.1 and A.2,
through replacing $d$ by $d-1$. In particular, we can show that

${\rm Pr}\Big{(}G\notin{\cal G}(\alpha,1-1/(d-1))\Big{)}\leq{\cal
O}(n^{1-(d-1)(d-3)})$ (62)

if
$d-1>(H(\alpha)+\beta^{\prime}H(\alpha/\beta^{\prime}))/\alpha\log(\beta^{\prime}/\alpha)$.
This completes the proof. Q.E.D.

Combining Proposition 4 & 5 indicates that the $d$-rows-deleted sensing matrix
$\overline{\bm{B}}_{(\Omega_{\overline{\bm{B}}}^{i})^{c}}^{{}^{\prime}T}$
corresponds to an $(\alpha,1-1/(d-1))$-expander graph with high probability.
Therefore, the conclusion in Corollary 1 follows by setting
$\delta=1-1/(d-1)$. Moreover, by applying the union bound, the probability of
failure is upper bounded as:

${\rm Pr}(Fail)\leq\left(\frac{d}{\beta}\right)^{4}\frac{d-1}{n^{2}}+{\cal
O}(n^{2-(d-1)(d-3)}),$ (63)

which vanishes as $n\rightarrow\infty$.

##  Appendix C Proof of Theorem 2

To simplify the notations, in this section, we drop the dependence on the
discussion index $k$ for the opinion vectors ${\bm{x}}(t;k)$ and the trust
matrices ${\bm{W}}(t;k)$. We first prove that the estimator is unbiased.
Consider the following chain:

$\begin{array}[]{l}\displaystyle\mathbb{E}\\{\hat{\bm{x}}({\cal
T}_{k})|{\bm{x}}(0)\\}=\frac{1}{|{\cal T}_{k}|}\sum_{t_{i}\in{\cal
T}_{k}}\mathbb{E}\\{\hat{\bm{x}}(t_{i})|{\bm{x}}(0)\\}\\\
\displaystyle~{}~{}=\frac{1}{|{\cal T}_{k}|}\sum_{t_{i}\in{\cal
T}_{k}}\overline{\bm{W}}^{t_{i}}{\bm{x}}(0)=\overline{\bm{W}}^{\infty}{\bm{x}}(0),\end{array}$
(64)

where we used the fact that $T_{o}\rightarrow\infty$ and $t_{i}\geq T_{o}$ for
all $t_{i}$ in the last equality.

Next, we prove that the estimator is asymptotically consistent, i.e., (38).
Without loss of generality, we let $t_{1}<t_{2}<\ldots<t_{|{\cal T}_{k}|}$ as
the sampling instances. The following shorthand notation will be useful:

$\bm{\Phi}(s,t)\triangleq\bm{W}(t)\bm{W}(t-1)\ldots\bm{W}(s+1)\bm{W}(s),$ (65)

where $t\geq s$ and $\bm{\Phi}(s,t)$ is a random matrix. Our proof involves
the following lemma:

###### Lemma 2

When $|t-s|\rightarrow\infty$, the random matrix $\bm{\Phi}(s,t)$ converges
almost surely to the following:

$\lim_{|t-s|\rightarrow\infty}\bm{\Phi}(s,t)=\left(\begin{array}[]{cc}{\bm{I}}&{\bm{0}}\\\
{\bm{B}}(s,t)&{\bm{0}}\end{array}\right),$ (66)

where ${\bm{B}}(s,t)=\sum_{q=s}^{t}({\bm{D}}(t)\ldots{\bm{D}}(q)){\bm{B}}(q)$.
Moreover, ${\bm{B}}(s,t)$ is bounded almost surely.

_Proof:_ We first establish the almost sure convergence of
${\bm{D}}(t){\bm{D}}(t-1)\ldots{\bm{D}}(s)$ to ${\bf 0}$. Define

$\beta(s,t)\triangleq\|{\bm{D}}(t){\bm{D}}(t-1)\ldots{\bm{D}}(s)\|_{2},$ (67)

and observe the following chain

$\begin{array}[]{l}\mathbb{E}\\{\beta(s,t)|\beta(s,t-1),...,\beta(s,s)\\}\vspace{.05cm}\\\
=\mathbb{E}\\{\|{\bm{D}}(t){\bm{D}}(t-1)\ldots{\bm{D}}(s)\|_{2}|\beta(s,t-1)\\}\vspace{.05cm}\\\
\leq\mathbb{E}\\{\|{\bm{D}}(t)\|_{2}\|{\bm{D}}(t-1)\ldots{\bm{D}}(s)\|_{2}|\beta(s,t-1)\\}\vspace{.05cm}\\\
=\mathbb{E}\\{\|{\bm{D}}(t)\|_{2}\\}\beta(s,t-1)\leq
c\beta(s,t-1),\end{array}$ (68)

where $c=\|\overline{\bm{D}}\|_{2}<1$. The almost sure convergence of
$\beta(s,t)$ follows from [56, Lemma 7]. Now, expanding the multiplication
(65) yields:

$\bm{\Phi}(s,t)=\left(\begin{array}[]{cc}{\bm{I}}&{\bm{0}}\\\
{\bm{B}}(s,t)&{\bm{D}}(t)\ldots{\bm{D}}(s)\end{array}\right).$ (69)

The desired result is achieved by observing
${\bm{D}}(t)\ldots{\bm{D}}(s)\rightarrow{\bf 0}$ as $|t-s|\rightarrow\infty$.
Lastly, the almost sure boundedness of ${\bm{B}}(s,t)$ can be obtained from
the fact that $\bm{\Phi}(s,t)$ is stochastic. Q.E.D.

We consider the following chain:

$\begin{array}[]{l}\displaystyle\mathbb{E}\\{\|\hat{\bm{x}}({\cal
T}_{k})-\overline{\bm{x}}(\infty)\|_{2}^{2}|{\bm{x}}(0)\\}=\vspace{.1cm}\\\
\displaystyle~{}~{}=\mathbb{E}\Big{\\{}\Big{\|}\frac{1}{|{\cal
T}_{k}|}\sum_{t_{i}\in{\cal
T}_{k}}\big{(}\hat{\bm{x}}(t_{i})-\overline{\bm{x}}(\infty)\big{)}\Big{\|}_{2}^{2}|{\bm{x}}(0)\Big{\\}}.\end{array}$
(70)

Recall that $\hat{\bm{x}}(t_{i})={\bm{x}}(t_{i})+{\bm{n}}(t_{i})$ and the
noise term ${\bm{n}}(t_{i})$ is independent of ${\bm{W}}(t)$ for all $t$. The
above expression reduces to:

$\begin{array}[]{l}\mathbb{E}\Big{\\{}\Big{\|}\frac{1}{|{\cal
T}_{k}|}\sum_{t_{i}\in{\cal
T}_{k}}\big{(}{\bm{x}}(t_{i})-\overline{\bm{x}}(\infty)\big{)}\Big{\|}_{2}^{2}|{\bm{x}}(0)\Big{\\}}\\\
\hfill+\mathbb{E}\Big{\\{}\Big{\|}\frac{1}{|{\cal T}_{k}|}\sum_{t_{i}\in{\cal
T}_{k}}{\bm{n}}(t_{i})\Big{\|}_{2}^{2}\Big{\\}}.\end{array}$ (71)

It is easy to check that the latter term vanishes when $|{\cal
T}_{k}|\rightarrow\infty$. We thus focus on the former term, which gives

$\begin{array}[]{l}\displaystyle\mathbb{E}\Big{\\{}\Big{\|}\frac{1}{|{\cal
T}_{k}|}\sum_{t_{i}\in{\cal
T}_{k}}\big{(}{\bm{x}}(t_{i})-\overline{\bm{x}}(\infty)\big{)}\Big{\|}_{2}^{2}|{\bm{x}}(0)\Big{\\}}\\\
\displaystyle=\frac{1}{|{\cal
T}_{k}|^{2}}\mathbb{E}\Big{\\{}\Big{\|}\sum_{t_{i}\in{\cal
T}_{k}}\big{(}\bm{\Phi}(0,t_{i})-\overline{\bm{W}}^{\infty}\big{)}{\bm{x}}(0)\Big{\|}_{2}^{2}\Big{\\}}\\\
\displaystyle=\frac{1}{|{\cal T}_{k}|^{2}}\mathbb{E}\big{\\{}{\rm
Tr}\big{(}\bm{\Xi}{\bm{x}}(0){\bm{x}}(0)^{T}\big{)}\big{\\}},\end{array}$ (72)

where

$\bm{\Xi}=\sum_{t_{j}\in{\cal
T}_{k}}\big{(}\bm{\Phi}(0,t_{j})-\overline{\bm{W}}^{\infty}\big{)}^{T}\sum_{t_{i}\in{\cal
T}_{k}}\big{(}\bm{\Phi}(0,t_{i})-\overline{\bm{W}}^{\infty}\big{)}.$ (73)

Expanding the above product yields two groups of terms — when $t_{i}=t_{j}$
and when $t_{i}\neq t_{j}$. When $t_{i}=t_{j}$, using $T_{o}\rightarrow\infty$
and Lemma 2, it is straightforward to show that:

$\begin{array}[]{l}\displaystyle\|\mathbb{E}\big{\\{}\big{(}\bm{\Phi}(0,t_{i})-\overline{\bm{W}}^{\infty}\big{)}^{T}\big{(}\bm{\Phi}(0,t_{i})-\overline{\bm{W}}^{\infty}\big{)}\big{\\}}\|\leq
C,\end{array}$ (74)

for some constant $C<\infty$. As a matter of fact, we observe that the above
term will not vanish at all. This is due to Observation 3, the random matrix
$\bm{\Phi}(0,t_{i})$ does not converge in mean square sense.

For the latter case, we assume $t_{j}>t_{i}$. We have

$\begin{array}[]{l}\displaystyle\big{(}\bm{\Phi}(0,t_{j})-\overline{\bm{W}}^{\infty}\big{)}^{T}\big{(}\bm{\Phi}(0,t_{i})-\overline{\bm{W}}^{\infty}\big{)}\vspace{.1cm}\\\
\displaystyle=\big{(}\bm{\Phi}(t_{i}+1,t_{j})\bm{\Phi}(0,t_{i})-\overline{\bm{W}}^{\infty}\big{)}^{T}\big{(}\bm{\Phi}(0,t_{i})-\overline{\bm{W}}^{\infty}\big{)}.\end{array}$
(75)

Taking expectation of the above term gives:

$\begin{array}[]{l}\displaystyle\mathbb{E}\big{\\{}\big{(}\bm{\Phi}(0,t_{i})-\overline{\bm{W}}^{\infty}\big{)}^{T}\overline{\bm{W}}^{t_{j}-t_{i}}\big{(}\bm{\Phi}(0,t_{i})-\overline{\bm{W}}^{\infty}\big{)}\big{\\}},\end{array}$
(76)

where we used the fact that $\bm{\Phi}(t_{i}+1,t_{j})$ is independent of the
other random variables in the expression and
$\overline{\bm{W}}^{\infty}\overline{\bm{W}}^{\ell}=\overline{\bm{W}}^{\infty}$
for any $\ell\geq 0$. Now, note that

$\overline{\bm{W}}^{t_{j}-t_{i}}=\overline{\bm{W}}^{\infty}+{\cal
O}(\lambda^{t_{j}-t_{i}}),$ (77)

for some $0<\lambda\triangleq\lambda_{max}(\overline{\bm{D}})<1$. This is due
to the fact that $\overline{\bm{D}}$ is sub-stochastic.

As $T_{o}\rightarrow\infty$ and by invoking Lemma 2, the matrix
$(\bm{\Phi}(0,t_{i})-\overline{\bm{W}}^{\infty})$ has almost surely _only_
non-empty entries in the lower left block. Carrying out the block matrix
multiplications and using the boundedless of $\bm{\Phi}(0,t_{i})$ gives

$\begin{array}[]{l}\displaystyle\big{\|}\mathbb{E}\big{\\{}\big{(}\bm{\Phi}(0,t_{j})-\overline{\bm{W}}^{\infty}\big{)}^{T}\big{(}\bm{\Phi}(0,t_{i})-\overline{\bm{W}}^{\infty}\big{)}\big{\\}}\big{\|}\displaystyle\leq{\cal
O}(\lambda^{t_{j}-t_{i}}).\end{array}$ (78)

Combining these results, we can show

$\begin{array}[]{l}\displaystyle\frac{\mathbb{E}\big{\\{}{\rm
Tr}\big{(}\bm{\Xi}{\bm{x}}(0){\bm{x}}(0)^{T}\big{)}\big{\\}}}{|{\cal
T}_{k}|^{2}}\leq\frac{{C^{\prime}}}{|{\cal T}_{k}|}\Big{(}\sum_{i=0}^{|{\cal
T}_{k}|-1}\lambda^{\min_{k}|t_{k+i}-t_{k}|}\Big{)},\end{array}$ (79)

for some $C^{\prime}<\infty$. Notice that
$\min_{\ell}|t_{\ell+i}-t_{\ell}|\geq i$ and the terms inside the bracket can
be upper bounded by the summable geometric series $\sum_{i=0}^{|{\cal
T}_{k}|-1}\lambda^{i}$, since $\lambda<1$. Consequently, the mean square error
goes to zero as $|{\cal T}_{k}|\rightarrow\infty$. The estimator (36) is
consistent.

## References

  * [1] H.-T. Wai, A. Scaglione, and A. Leshem, “The social system identification problem,” in _Proc CDC_ , Dec. 2015, pp. 406–411. [Online]. Available: http://arxiv.org/abs/1503.07288
  * [2] M. O. Jackson, _Social and Economic Networks_. Princeton, NJ, USA: Princeton University Press, 2008.
  * [3] A. H. Sayed, S.-y. Tu, J. Chen, X. Zhao, and Z. J. Towfic, “Diffusion strategies for adaptation and learning over networks: an examination of distributed strategies and network behavior,” _IEEE Signal Process. Mag._ , vol. 30, no. 3, pp. 155–171, May 2013.
  * [4] A. Anis, A. Gadde, and A. Ortega, “Towards a sampling theorem for signals on arbitrary graphs,” in _Proc ICASSP_ , 2014, pp. 3864–3868.
  * [5] A. Sandryhaila and J. M. Moura, “Big Data Analysis with Signal Processing on Graphs: Representation and processing of massive data sets with irregular structure,” _IEEE Signal Process. Mag._ , vol. 31, no. 5, pp. 80–90, 2014\.
  * [6] A. Clauset, M. Newman, and C. Moore, “Finding community structure in very large networks,” _Physical Review E_ , vol. 70, pp. 1–6, 2004.
  * [7] S. Fortunato, “Community detection in graphs,” _Physics Reports_ , vol. 486, pp. 75–174, 2010.
  * [8] L. Page, S. Brin, R. Motwani, and T. Winograd, “The pagerank citation ranking: Bringing order to the web.” _technical report_ , 1999.
  * [9] H. Ishii and R. Tempo, “The pagerank problem, multiagent consensus, and web aggregation: A systems and control viewpoint,” _IEEE Control Systems Magazine_ , vol. 34, pp. 34–53, 2014.
  * [10] Y.-Y. Liu, J.-J. Slotine, and A.-L. Barabási, “Controllability of complex networks.” _Nature_ , vol. 473, pp. 167–173, 2011.
  * [11] ——, “Observability of complex systems.” _PNAS_ , vol. 110, no. 7, pp. 2460–5, 2013.
  * [12] M. Doostmohammadian and U. A. Khan, “Graph-theoretic distributed inference in social networks,” _IEEE J. Sel. Topics Signal Process._ , vol. 8, pp. 613–623, 2014.
  * [13] M. DeGroot, “Reaching a consensus,” in _Journal of American Statistcal Association_ , vol. 69, 1974, pp. 118–121.
  * [14] A. De, S. Bhattacharya, P. Bhattacharya, N. Ganguly, and S. Chakrabarti, “Learning a linear influence model from transient opinion dynamics,” _Proc CIKM_ , pp. 401–410, 2014.
  * [15] A. Das, S. Gollapudi, and K. Munagala, “Modeling opinion dynamics in social networks,” in _Proc WSDM_ , 2014, pp. 403–412.
  * [16] P. Jia, A. Mirtabatabaei, N. E. Friedkin, and F. Bullo, “Opinion Dynamics and the Evolution of Social Power in Influence Networks,” _SIAM Review_ , pp. 1–27, 2013.
  * [17] A. G. Chandrasekhar, H. Larreguy, and J. P. Xandri, “Testing models of social learning on networks: evidence from a framed field experiment,” _Working Paper_ , 2012.
  * [18] D. Acemoglu and A. Ozdaglar, “Opinion dynamics and learning in social networks,” _Dynamic Games and Applications_ , vol. 1, no. 1, pp. 3–49, 2011\.
  * [19] V. D. Blondel, J. M. Hendrickx, A. Olshevsky, and J. N. Tsitsiklis, “Convergence in multiagent coordination, consensus, and flocking,” in _Proc CDC-ECC ’05_ , vol. 2005, 2005, pp. 2996–3000.
  * [20] L. Xiao, S. Boyd, and S. Kim, “Distributed average consensus with least-mean-square deviation,” in _Journal of Parallel and Distributed Computing_ , vol. 67, 2007, pp. 33–46.
  * [21] M. Timme, “Revealing network connectivity from response dynamics,” _Physical Review Letters_ , vol. 98, no. 22, pp. 1–4, 2007.
  * [22] W.-X. Wang, Y.-C. Lai, C. Grebogi, and J. Ye, “Network Reconstruction Based on Evolutionary-Game Data via Compressive Sensing,” _Physical Review X_ , vol. 1, no. 2, pp. 1–7, 2011.
  * [23] J. Mei and J. M. F. Moura, “Signal Processing on Graphs: Modeling Causal Relations in Big Data,” no. 412, pp. 1–22, 2015. [Online]. Available: http://arxiv.org/abs/1503.0017
  * [24] M. E. Yildiz, D. Acemoglu, A. Ozdaglar, A. Saberi, and A. Scaglione, “Discrete opinion dynamics with stubborn agents,” _SSRN eLibrary_ , 2011.
  * [25] M. E. Yildiz, A. Ozdaglar, D. Acemoglu, A. Saberi, and A. Scaglione, “Binary opinion dynamics with stubborn agents,” _ACM Trans. Econ. Comput._ , vol. 1, no. 4, p. 19, 2013.
  * [26] D. Acemoglu, G. Como, F. Fagnani, and A. Ozdaglar, “Opinion Fluctuations and Disagreement in Social Networks,” _Mathematics of Operations Research_ , vol. 38, no. 1, pp. 1–27, Feb. 2013.
  * [27] M. Mobilia, “Does a single zealot affect an infinite group of voters ?” _Physical Review Letters_ , July 2003.
  * [28] A. Waagen, G. Verma, K. Chan, A. Swami, and R. D’Souza, “Effect of zealotry in high-dimensional opinion dynamics models,” _Physical Review E_ , Feb. 2015\.
  * [29] M. E. Yildiz and A. Scaglione, “Computing along routes via gossiping,” _IEEE Trans. on Signal Process._ , vol. 58, no. 6, pp. 3313–3327, 2010.
  * [30] W. Ben-Ameur, P. Bianchi, and J. Jakubowicz, “Robust Average Consensus using Total Variation Gossip Algorithm,” in _VALUETOOLS_ , 2012, pp. 99–106.
  * [31] U. A. Khan, S. Kar, and J. M. F. Moura, “Higher dimensional consensus: Learning in large-scale networks,” _IEEE Trans. Signal Process._ , vol. 58, no. 5, pp. 2836–2849, 2010.
  * [32] T. Wang, H. Krim, and Y. Viniotis, “Analysis and Control of Beliefs in Social Networks,” _IEEE Trans. on Signal Process._ , vol. 62, no. 21, pp. 5552–5564, 2014.
  * [33] U. A. Khan, S. Kar, and J. M. F. Moura, “Distributed sensor localization in random environments using minimal number of anchor nodes,” _IEEE Trans. Signal Process._ , vol. 57, no. 5, pp. 2000–2016, May 2009.
  * [34] M. Moussaıd, J. E. Kammer, P. P. Analytis, and H. Neth, “Social influence and the collective dynamics of opinion formation,” _PLoS ONE_ , vol. 8, no. 11, November 2013.
  * [35] M. Ramos, J. Shao, S. D. S. Reis, C. Anteneodo, J. S. A. Jr, S. Havlin, and H. A. Makse, “How does public opinion become extreme?” _Sci. Rep._ , no. 10032, May 2015.
  * [36] C. J. Kuhlman, V. S. A. Kumar, and S. S. Ravi, “Controlling opinion bias in online social networks,” in _Proc. WebSci_ , 2012, pp. 165–174.
  * [37] S. Gleichman and Y. C. Eldar, “Blind compressed sensing,” _IEEE Trans. Inf. Theory_ , vol. 57, no. 10, pp. 6958–6975, 2011.
  * [38] C. Studer and R. G. Baraniuk, “Dictionary learning from sparsely corrupted or compressed signals,” in _Proc ICASSP_ , no. Dl, 2012, pp. 3341–3344.
  * [39] A. Gilbert and P. Indyk, “Sparse recovery using sparse matrices,” _Proceedings of the IEEE_ , vol. 98, no. 6, pp. 937–947, 2010.
  * [40] R. Berinde, A. C. Gilbert, P. Indyk, H. Karloff, and M. J. Strauss, “Combining geometry and combinatorics: A unified approach to sparse signal recovery,” in _46th Annual Allerton Conference on Communication, Control, and Computing_ , 2008, pp. 798–805.
  * [41] M. Wang, W. Xu, and A. Tang, “A unique ”nonnegative” solution to an underdetermined system: From vectors to matrices,” _IEEE Trans. Signal Process._ , vol. 59, no. 3, pp. 1007–1016, 2011.
  * [42] M. A. Khajehnejad, A. G. Dimakis, W. Xu, and B. Hassibi, “Sparse recovery of nonnegative signals with minimal expansion,” _IEEE Trans. Signal Process._ , vol. 59, no. 1, pp. 196–208, 2011.
  * [43] N. E. Friedkin and E. C. Johnsen, _Social Influence Network Theory: A Sociological Examination of Small Group Dynamics_. Cambridge University Press, 2011.
  * [44] M. Grant and S. Boyd, “CVX: Matlab software for disciplined convex programming, version 2.1,” http://cvxr.com/cvx, Mar. 2014.
  * [45] Y. C. Eldar, _Sampling Theory: Beyond Bandlimited Systems_. New York, NY, USA: Cambridge University Press, 2014.
  * [46] D. J. Watts and S. H. Strogatz, “Collective dynamics of ’small-world’ networks.” _Nature_ , vol. 393, no. 6684, pp. 440–442, 1998.
  * [47] R. Albert and A. L. Barabási, “Statistical mechanics of complex networks,” _Reviews of Modern Physics_ , vol. 74, no. 1, pp. 47–97, 2002\.
  * [48] N. Parikh and S. Boyd, “Proximal Algorithms,” _Foundations and Trends in Optimization_ , vol. 1, no. 3, pp. 123–231, 2014.
  * [49] A. Beck and M. Teboulle, “A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems,” _SIAM Journal on Imaging Sciences_ , vol. 2, no. 1, pp. 183–202, 2009.
  * [50] C. Ravazzi, P. Frasca, R. Tempo, and H. Ishii, “Ergodic Randomized Algorithms and Dynamics over Networks,” _IEEE Trans. Control of Network Sys._ , pp. 1–11, to appear.
  * [51] A. L. Traud, P. J. Mucha, and M. A. Porter, “Social structure of Facebook networks,” _Physica A: Statistical Mechanics and its Applications_ , vol. 391, no. 16, pp. 4165–4180, 2012.
  * [52] T. C. Aysal, M. E. Yildiz, A. D. Sarwate, and A. Scaglione, “Broadcast gossip algorithms for consensus,” _IEEE Trans. Signal Process._ , vol. 57, no. 7, pp. 2748–2761, 2009.
  * [53] M. Bastian, S. Heymann, and M. Jacomy, “Gephi: An open source software for exploring and manipulating networks,” 2009. [Online]. Available: http://www.aaai.org/ocs/index.php/ICWSM/09/paper/view/154
  * [54] R. A. Horn and C. R. Johnson, Eds., _Matrix Analysis_. Cambridge University Press, 1986.
  * [55] D. B. West, _Introduction to Graph Theory_ , 2nd ed. Prentice Hall, September 2000.
  * [56] B. Polyak, _Introduction to Optimization_. New York: Optimization Software, Inc., 1987.