# Echo Chambers and Segregation in Social Networks: Markov Bridge Models and
Estimation

Rui Luo, Buddhika Nettasinghe, and Vikram Krishnamurthy R. Luo is with the
Sibley School of Mechanical and Aerospace Engineering, Cornell University,
Ithaca, NY, 14850.
E-mail<EMAIL_ADDRESS>B. Nettasinghe and V. Krishnamurthy are with the
School of Electrical and Computer Engineering, Cornell University, Ithaca, NY,
14850.
E-mail: {dwn26<EMAIL_ADDRESS>research was supported by the U. S.
Army Research Office under grant W911NF-19-1-0365, and the National Science
Foundation under grant 1714180.

###### Abstract

This paper deals with the modeling and estimation of the sociological
phenomena called _echo chambers_ and _segregation_ in social networks.
Specifically, we present a novel community-based graph model that represents
the emergence of segregated echo chambers as a Markov bridge process. A Markov
bridge is a one-dimensional Markov random field that facilitates modeling the
formation and disassociation of communities at deterministic times which is
important in social networks with known timed events. We justify the proposed
model with six real world examples and examine its performance on a recent
Twitter dataset. We provide model parameter estimation algorithm based on
maximum likelihood and, a Bayesian filtering algorithm for recursively
estimating the level of segregation using noisy samples obtained from the
network. Numerical results indicate that the proposed filtering algorithm
outperforms the conventional hidden Markov modeling in terms of the mean-
squared error. The proposed filtering method is useful in computational social
science where data-driven estimation of the level of segregation from noisy
data is required.

###### Index Terms:

Markov bridge, Bayesian filtering, social network, echo chamber, segregation.

##  1 Introduction

ONLINE Social networks (OSNs) lay the foundation for online community
formation. Billions of users rely on OSNs to connect with friends, share
information, and advertise products. Echo chambers, i.e., situations where one
is exposed only to opinions that agree with their own, are an increasing
concern for the usage of OSNs. According to the theory of preferential
attachment or homophily [1], users tend to link with other users who share
similar attributes (e.g. opinions, interests, etc.). Further, social influence
[2] also increases users’ tendency of becoming more similar to somebody as a
result of social interaction. These two factors lead to segregated and
polarized clusters known as “echo chambers” on social networks.

Echo chambers are studied on various social networks from different modelling
perspectives. However, the evolution of echo chambers is characterised by
certain temporal patterns in many cases, which is neglected by many proposed
models. Having an anticipatory model of segregation in social networks allows
us to incorporate the effects of periodic (i.e.,seasonal) events into the
model. This enables the real time statistical inference as well as tasks such
as offering incentives to reduce the effects of segregation (control
strategies for preventing segregation and echo chambers). For example, one can
imagine a control strategy which offers incentives to users at each time
instant (subject to budget restrictions) to influence the link formation in
order to hinder the segregation in social networks.

Towards this end, the aim of this paper is to develop and analyze a model for
the anticipatory nature of the segregation process in a social network i.e.
one can assign probabilities to the event that the social network will be
segregated at a certain fixed time instant.111A shorter version of this paper
is under review for IEEE International Conference on Acoustics, Speech and
Signal Processing (2021).

Main Results:

(1) We present a dynamic network formation model that captures the dynamics of
how a social network segregates into communities (and then integrates back
again). The key idea behind our model is to represent the strength of the ties
between communities (in terms of a graph clustering metric) as a Markov bridge
process which is a special case of an anticipatory process.

(2) Based on the proposed Markov Bridge based segregation model, we propose a
time-inhomogeneous Bayesian filter (called Hidden Markov bridge filter) for
recursively estimating the state of the graph clustering metric. The Hidden
Markov bridge filter uses only a few (compared to graph size) noisy samples
from the social network at each time instant.

(3) We numerically compare the performance the proposed Hidden Markov bridge
(HMB) filter with conventional Hidden Markov Model (HMM) filter in terms of
mean-squared error. Our results show that the proposed method outperforms the
traditional HMM filter. This shows that the Bayesian filter yields useful real
time information about the dis-association and association of communities in a
network.

(4) We evaluate the performance on a public available dataset [3] which
encompasses 7 million tweets related to the 2020 U.S. presidential election.
Our results illustrate the proposed model and filter are useful in estimating
Twitter users’ state of political opinion polarization under real-world
settings.

###  1.1 Why Markov Bridge Dynamics?

In this subsection, we justify the usage of Markov bridge model in modeling
social network phenomena based on six examples and a real world Twitter
dataset. The temporal dynamics of social networks give rise to states where
the network is segregated into multiple communities at certain time instants
and integrate back into a single community at other time instants. In
statistical signal processing (e.g. in target tracking, etc.), dynamical
processes with long-range dependencies are typically modeled as Markov bridge
processes [4, 5, 6, 7]. A Markov bridge process can be viewed as a special
case of an anticipatory process in which a the distribution at a certain time
instant is fixed. Below we discuss how the temporal dynamics of segregation in
many scenarios on social networks can be modeled using Markov bridge
processes.

Example 1. Schelling’s Segregation Model:  The segregation model developed by
Schelling [8] is set in an $N\times N$ grid. Agents are split into two groups
and occupy the spaces of the grid. Agents desire a fraction $B_{\textrm{a}}$
of their neighborhood to be from the same group. This model shows how
segregated community and weak inter-community connectivity might arise even
with a moderate individual preference $B_{\textrm{a}}$. The physical grid
space can be generalized to a social network as a grid graph. In case of
external stimulus such as elections, the value of $B_{\textrm{a}}$ or its
distribution is anticipatory and can be modeled as a Markov bridge process.

Example 2. Polarization of Political Opinion:  OSNs (e.g. Twitter) users have
different political leanings and tend to follow or retweet users of similar
opinions. Such tendency can be moderate, i.e. users are open-minded to follow
or hear someone from different ideology groups. However, during a politically
polarization event, such as election or legislation, the tendency will become
stronger and hinder users from connecting with others of different opinions,
which results in highly segregated online echo chambers, as shown in Fig. 1.
We can formulate the portion $x^{(t)}$ of interactions between users of
different political leanings as a Markov bridge process. It is anticipatory to
be at a low level during the polarization event.

Figure 1: This figure indicates how Twitter users’ political opinions are
polarized into two communities (echo chambers) before the 2020 presidential
election. Nodes represent Twitter users and edges represent retweets during
the one-month period before election (Oct. 1 to Nov 1). Multiple snapshots
illustrating the graph evolution during this period is shown in Fig. 6. The
graph is laid out using DrL (a force-directed graph layout) and the nodes are
assigned different colors and shapes (blue circles and red triangles)
according to the two communities detected by the Louvain method [9]. Details
can be found at section 4.2.1.

Example 3. Spread of Coronavirus Fake News:  On social media, people’s
perception of Coronavirus evolves during the out-break of this pandemic and
leaves room for related fake news. Many factors prevent the spread of fake
news, including scientific reports from reliable news sources, government
releases, and users’ tendency to share health and prevention messaging. We can
model user’s tendency $x^{(t)}$ to share Coronavirus fake news as a Markov
bridge process. It will decrease with the elucidations from reliable sources
and also bring down the probability that fake news echo chambers emerge. This
example is related to the first one 1.1 because it is found in [10] that
partisanship correlates with sentiment toward government measures. Therefore,
the evolution of Coronavirus fake news echo chambers is correlated with that
of political ideology echo chambers.

Example 4. Active Level of Seasonal Sports League:  Sports leagues typically
have season and off-season. In different periods of a year, fans will have
different involvement in the sports leagues on social media such as online
sports forums. We can formulate the active level $x^{(t)}$ as a hidden state
following a Markov bridge process. We can then use the data of posting,
commenting, and time of stay on the forums as the observation. $x^{(t)}$ will
evolve from a high level to a low level during the off-season, and will evolve
back into a high level in the next sports season and lead to the segregated
fan’s community. Online merchants may take advantage of this information to
maximize their advertisement coverage and return on investment.

Example 5. E-commerce Sequential Recommendation:  Relevance and diversity
usually act as two competing objectives in recommender systems, where the
former causes growing concern that it might lead to the self-reinforcing of
user’s interests due to narrowed exposure of similar items. The existence of
echo chambers has been validated on user clicks, purchases, and browse logs
from Alibaba Taobao in [11]. To examine and quantify the echo chambers in
recommender systems, we can use a measure $x^{(t)}$ to represent the
similarity of recommended items during the interaction with users. For
conventional recommender systems which narrow down the contents provided to
users, $x^{(t)}$ can be modeled as a Markov bridge process which evolves from
a low level to a high level. In this context, an extended recommendation
framework can potentially avoid such echo chambers emergence by using
collaborative filtering and sequential forecasting to recommend users items
that they may find useful in the future, thus improving both user satisfaction
and E-commerce platform’s revenue.

Example 6. Social Media Marketing:  Consider a social media marketing scenario
(e.g. Facebook Business page) where a company is connected with customers.
Customers are classified into fans and utilitarian customers [12]. As depicted
in Fig. 2, while fans (bottom left vertices) have a stable connection strength
(i.e. fixed edge weight) with the company (center vertex), utilitarian
customers (top right vertices) have time-varying connection strength (i.e.
time varying edge weights) with the company due to reasons such as sales
events. The variable connection leads to segregation and integration of the
company-customer social network.

Figure 2: Snapshots of a dynamic company-customer social network model in (1)
at four time instants. The edges between utilitarian customers (top right
vertices) and the company (center vertex) grow weaker as the social network
evolves into segregation with two communities.

###  1.2 Related Work

Echo chambers are studied in various social networks from different modelling
perspectives. [13] studies users’ leaning about controversial news by
analyzing features of their interaction networks on social media, such as
shared links domain and follower relationship. [2] formulates the emergence of
echo chambers on Twitter’s follower network by introducing a model of social
influence and unfriending. Users can change both their opinions and social
connections based on the information to which they are exposed. [14] proposes
a group polarization dynamic model from a social psychology perspective. It
proposes radicalization as a reinforcing mechanism to drive the evolution of
echo chambers with extreme opinions from moderate initial conditions. [11]
analyzes the echo chamber phenomenon in e-commerce recommender systems. It
illustrates that user interests are self-reinforced through repeated exposure
to similar contents and further polarized through the echo chamber formed by
such recommendations. [15] estimates the ideology political preferences of
Twitter users using correspondence analysis and analyzes cross-ideological
dissemination of liberals and conservatives. It concludes that the echo
chamber effect might be overestimated in social-media usage. [16] computes the
ideology political leaning of Twitter users based on the news organization
they follow. It studies the echo chambers in both spread and consumption of
information.

Many other works view echo chambers as a polarized consensus state of a multi-
agent system and build upon DeGroot’s well-known model of opinion formation
[17]. [18] complements a biased assimilation mechanism into DeGroot’s model
which strengthens the individual’s self-opinion and ensures polarization. [19]
proposes a mechanism considering the co-evolution between information states
and network topology. It finds threshold values for the emergence of echo
chambers. [20] models individual users’ opinions over time by marked jump
diffusion stochastic differential equations, and leverage parameter estimation
from historical fine grained event data to identify conditions under which
opinions converge to a steady state.

##  2 Markov Bridge Model for dynamic social networks

This section presents a stochastic model to represent the evolution of a
social network whose state is fixed at the beginning and at the end. The two
fixed states correspond to a segregated social network (with multiple
communities) and a social network which has a single community (i.e. an
integrated network). Thus, the model presented in this section is a useful,
intuitive representation of the process of social network segregation.
Further, as we show later in Section 3, the proposed model is easily amenable
to Bayesian statistical inference, making it useful in data-driven contexts in
computational social science.

###  2.1 Time-varying Edge Weight Graph Model

This subsection explains the graph model with time-varying edge weights using
a company-customer social network consisting of a company and two types of
customers as the graph vertices. The binary classification of customers is
motivated from the topological study of Facebook fans in [12].

The social network at discrete time instant $t$ is modeled by an undirected,
weighted graph $G^{(t)}(V,E,w^{(t)})$, with $|V|$ number of agents, $|E|$
number of undirected edges representing their connectivity, and
$w^{(t)}:E^{(t)}\rightarrow\mathbb{R}^{+}$ representing the weights of the
edges (i.e. the strengths of each connection).

Let $|V|=n$ be the number of vertices in the network,
$M=\\{v_{1},\cdots,v_{m}\\}\subset V$ be the set of utilitarian customers who
are all connected with each other (i.e., form a complete subgraph),
$v_{m+1}\in V$ be the company, and $N=\\{v_{m+2},\cdots,v_{n}\\}\subset V$ be
the set of other customers (fans) that form another complete subgraph. Then,
edge weight function $w_{ij}^{(t)}$ between $v_{i}$ and $v_{j}$ where
$(v_{i},v_{j})\in E$ is as follows:

$w_{ij}^{(t)}=\left\\{\begin{array}[]{lr}W_{ij}(t)&if\;v_{i}=v_{m+1}\ \&\
v_{j}\in M\\\ &\vee\;v_{j}=v_{m+1}\ \&\ v_{i}\in M\\\ 1&if\;v_{i}=v_{m+1}\ \&\
v_{j}\in N\\\ &\vee\;v_{j}=v_{m+1}\ \&\ v_{i}\in N\\\ 1&if\;(v_{i},v_{j})\in
M\ \&\ v_{i}\neq v_{j}\\\ &\vee\;(v_{i},v_{j})\in N\ \&\ v_{i}\neq v_{j}\\\
\end{array}\right.$ (1)

where, $W_{ij}(t),\,t=1,2,..$ is the Markov bridge process that we define in
Section 2.2.

Note that (1) classifies the edge weights into three groups: between company
and utilitarian customers, between company and fans, and between two customers
of the same type. Note that there is no edge between two customers of
different types. The edge weights between company and utilitarian customers is
subject to sales events and therefore described as a time-evolving random
process $W(t)$ (specified in Section 2.2). Other weights are simply set to be
one. The simplification is reasonable because fans would be indifferent about
sales events and have a more stable relationship with the company. Further, we
also assume that the customers of the same type are all connected with each
other motivated by the concept of homophily [1].

###  2.2 Markov Bridge Model of Edge Weights

We now propose a Markov bridge model (MB) for the evolution of the weight
$W_{ij}(t)$ in the graph. Recall [21] a MB is a one-dimensional Markov random
field. It is clamped at the beginning and end time point and evolves in
between with a three point transition probability
$p\\{W_{ij}(t)|W_{ij}(t+1),W_{ij}(t-1))\\}$. A MB for $W_{ij}(t)$ facilitates
modeling a community that separates and then reintegrates with another
community in a network. Unlike a Markov chain which enters a state at a
geometrically distributed time, a MB enters a state at a fixed deterministic
time [4].

We consider $(2T-1)$ time steps as the period between two consecutive sales
events. The edge weight $W_{ij}(t)$ between company and utilitarian customers
reaches maximum at time $1$ and time $2T-1$ when sales event happens, and
decreases to minimum at time $T$ in the middle of two sales events. The
process can be described as two consecutive MBs as we explain next.

The Markov process $W_{ij}(t)$, $t=1,\cdots,2T-1$ takes value in some finite
state space $S=\\{0,\frac{1}{N_{S}-1},\
\cdots,\frac{N_{S}-2}{N_{S}-1},\,1\\}$, which is an arithmetic sequence with
$N_{S}$ elements. The transition matrix of the Markov process is chosen to be
a $N_{S}\times N_{S}$ row-normalized Toeplitz matrix such that transitions
from a given state to neighboring states (i.e., values in $S$ that are closer
to the given state) are more likely. Let the entries of the transition matrix
be $P_{a,b}=\emph{P}\\{W_{ij}(t+1)=b|W_{ij}(t)=a\\}$ for all edge weights
$W_{ij}$ in (1), where $a,b\in S$ are two states of the social network. In
this setup, we fix the states at $t=1,T,2T-1$ of a Markov process - this can
be viewed as two sequential MBs: one that starts at time $1$ and another one
that starts at time $T$. Both MBs have their starting and end states fixed.
The first MB’s end state overlaps the second MB’s starting state. The first MB
(for each edge) is initialized as $1$ and the state at time $T$ is set to be
$0$, i.e. $W_{ij}^{1}=1,\,W_{ij}^{T}=0$. Thus, the transition probability of
the first MB going from state $a$ to state $b$ is obtained by applying the
Bayes rule as follows [21]:

$\begin{split}B^{c}_{a,b}(t)&=\emph{P}\\{W_{ij}(t+1)=b|W_{ij}(t)=a,W_{ij}(T)=0\\}\\\
&=\frac{P_{a,b}(P^{T-(t+1)})_{b,c}}{(P^{T-t})_{a,c}}\end{split}$ (2)

for $t=0,\cdots,T-2$, where $c=1$ which is the order of $0$ in the state
space.

Likewise, the state of social network is fixed to be $1$ at $2T-1$ (i.e., the
last time step) We can then formulate the transition probability of the second
MB in a similar manner as follows:

$\begin{split}B^{c^{\prime}}_{a,b}(t)&=\frac{P_{a,b}(P^{2T-(t+1)})_{b,c^{\prime}}}{(P^{2T-t})_{a,c^{\prime}}}\end{split}$
(3)

for $t=T-1,\cdots,2T-2$, where $c^{\prime}=N_{S}$ which is the order of $1$ in
the state space. Thus, the dynamics of edge weights is specified by two MBs
with transition probability matrices given by (2), (3) and the fixed initial
state of the first MB.

###  2.3 Graph Clustering Metrics

The aim of this subsection is to discuss the graph metric called graph
conductance that we use to express segregation and set as the state of our
model. Graph conductance is a measurement of the level of clustering in a
graph and is explained below.

We first define a cut $(S,\overline{S})$ as a partition of the vertices of a
graph into two disjoint subsets $S$ and $\overline{S}$. The conductance of a
cut $(S,\overline{S})$ in a graph is defined as:

$\phi(S)=\frac{\sum_{i\in S}\sum_{j\notin S}w_{ij}}{\min\\{a(S),a(V\setminus
S)\\}},\;S\subset V$ (4)

where $a(S)=\sum_{i\in S}\sum_{j\in V}w_{ij}$ is the sum of the weights of all
edges with at least one endpoint in $S$. Then, given a graph $G$, we define
the graph conductance as the minimum conductance over all possible cuts

$\phi(G)=\min_{S\subset V}\phi(S).$ (5)

Graph conductance is also related to the algebraic connectivity which is the
second-smallest eigenvalue of the Laplacian matrix of $G$. Algebraic
connectivity is used in many results in spectral graph theory such as
Cheeger’s inequality [22]. The derivation of algebraic connectivity can be
found in [23]. The weighted adjacency matrix $A^{(t)}$ of the graph is given
by

$A^{(t)}_{ij}=w_{ij}^{(t)},\ $ (6)

The degree matrix $D^{(t)}$ is given by

$D^{(t)}_{ij}=\left\\{\begin{array}[]{lll}\sum_{k}A^{(t)}_{ik}&&\text{if}\;i=j\\\
0&&\text{otherwise}\end{array}\right.$ (7)

The Laplacian $L^{(t)}$ of the graph is given by

$L^{(t)}=D^{(t)}-A^{(t)}$ (8)

Fig. 3 shows the variation of both graph conductance and algebraic
connectivity follow a similar dynamics. This implies that an estimate of the
graph conductance also serves as a proxy for the algebraic connectivity under
our model.

Figure 3: Two metrics (left: graph conductance $\phi(G)$, right: algebraic
connectivity $\lambda_{2}$) that indicate the strength of connectivity between
communities in a graph. The figure shows that conductance (the state random
variable in our model) resembles other metrics such as the algebraic
connectivity.

##  3 Bayesian Estimation of Graph Metrics

Section 2 presented a MB for a social network segregation. A natural question
is: assuming the MB with known parameters, how can one estimate the level of
segregation in a data driven manner? An answer to this question is useful in
computational social science and network science that deal with large scale,
partially observable (via noisy samples) social networks. As a solution, we
propose a Bayesian filtering method based on the proposed segregation model.

###  3.1 Measuring Conductance via Sampled Edges

This subsection discusses our criteria for obtaining a noisy estimate of the
conductance of the underlying dynamic graph (explained in Section 2) using a
sampled subgraph. We demonstrate that the sampling noise can be approximated
as a Gaussian noise from the central limit theorem.

We assume that $\gamma N$ of the total $N$ edges are uniformly sampled and
observed at each time $t$ (random sampling of edges has been used widely in
literature in statistical estimation tasks e.g. [24, 25, 26]). $\gamma$ is a
fixed ratio in $(0,1]$. The observed graph conductance $\phi(\tilde{G}^{(t)})$
is computed from the partially sampled graph $\tilde{G}^{(t)}$ at time $t$.
Graph conductance is a static function of edge weights,

$\phi(G^{(t)})=f(w^{(t)}_{1},\cdots,w^{(t)}_{N})$ (9)

And the observed graph conductance is the same function of sampled edge
weights,

$\phi(\tilde{G}^{(t)})=f(w^{(t)}_{i_{1}},\cdots,w^{(t)}_{i_{\gamma N}})$ (10)

where $i_{1},\cdots,i_{\gamma N}$ are sampled from $1,\cdots,N$ with equal
probabilities. From (9), it follows straight forwardly that graph conductance
as a static function of the edge weights, follows the same MB dynamics. For
the rest of the paper, we denote $\phi(G^{(t)})$ and $\phi(\tilde{G}^{(t)})$
as $\phi^{(t)}$ and $\tilde{\phi}^{(t)}$ respectively.

To estimate the observation probabilities
$p(\tilde{\phi}^{(t)}|\phi^{(t)}=j)$, we use a Monte Carlo simulation to
obtain sample trajectories of the $(2T-1)$ step graph evolution and compute
the empirical CDF of noise of the conductance computed from the partial
observation i.e. the CDF of the difference between the estimated conductance
$\gamma\tilde{\phi}^{(t)}$ and the true conductance $\phi^{(t)}$. Fig. 4 shows
that the observation noise is approximately (in the sense of Kolmogorov-
Smirnov test) a Gaussian distribution i.e.

$p(\tilde{\phi}^{(t)}|\phi^{(t)}=i)\sim\mathcal{N}(\gamma\tilde{\phi}^{(t)}-\phi^{(t)}|\mu^{(t)},{(\sigma^{(t)})}^{2})$
(11)

The normal distribution form of the observation noise (11) can also be viewed
as a consequence of the central limit theorem: since we are sampling i.i.d
edge sequences from the social network and approximate the graph conductance
using the average of their weights, it follows from the central limit theorem
that the sample mean (scaled by the square root of the number of samples)
converges in distribution to a Gaussian distribution centered around the true
state.

Figure 4: This figure shows that the empirical CDF of the sampling noise for
graph conductance can be fitted as a Gaussian distribution. It contains the
empirical and fitted cumulative probability at four states in a simulation of
6-state model. The _p_ -value of KS test is above 0.05 significance level and
therefore the Gaussian distribution null hypothesis is unrejectable.

###  3.2 Hidden Markov Bridge Filter

In this subsection, we aim to estimate the segregation level of a social
network by computing the posterior probability of the graph conductance given
its sampled observation (the conductance computed from sampled edges of the
graph). Section 3.1 exploits the Gaussian approximation of measurement noise
and we propose a Hidden Markov bridge (HMB) filter here for recursively
tracking the state of the graph conductance. HMB filter is a generalization of
the time-homogeneous HMM filter [27] and have been widely used in signal
processing methods for target tracking [7, 5, 6]).

Suppose that the MB process ${\Phi}=\\{\phi^{(1)},\cdots,\phi^{(t)}\\}$ is
observed via the observation process
$\tilde{\Phi}=\\{\tilde{\phi}^{(1)},\cdots,\tilde{\phi}^{(t)}\\}$. Assume that
the observation at time $t$ given the state $\phi^{(t)}$ is conditionally
independent of $\phi^{(\tau)}$ and $\tilde{\phi}^{(\tau)}$, $\tau\neq t$. This
conditional independence implies that

$\emph{P}(\tilde{\phi}^{(1)},\cdots,\tilde{\phi}^{(t)}|\phi^{(1)},\cdots,\phi^{(t)})=\prod_{k=0}^{t}\emph{P}(\tilde{\phi}^{(k)}|\phi^{(k)})$
(12)

The process $\tilde{\Phi}$ is called a Hidden Markov bridge (HMB) because the
property (12) is analogous to the assumption made for Hidden Markov Model
(HMM). Consider the HMB $\tilde{\Phi}$ with state $\Phi$, known MB transition
probability (2), and pre-computed observation probability (11). The posterior
probability can be evaluated recursively via Bayes’ rule

$q_{j}(t+1)=\frac{p(\tilde{\phi}^{t+1}|\phi^{t+1}=j)\sum_{i=1}^{\Phi}B_{i,j}^{k}(t)q_{i}(t)}{\sum_{l=1}^{\Phi}p(\tilde{\phi}^{t+1}|\phi^{t+1}=l)\sum_{i=1}^{\Phi}B_{i,j}^{k}(t)q_{i}(t)}$
(13)

as shown in [28].

##  4 Numerical Examples on Social Media Marketing and Twitter Political
Retweets

In this section, we numerically illustrate that the proposed HMB filter
(Section 3) outperforms (in terms of mean-squared error) the widely used HMM
filter for estimating the level of segregation on synthetic data. This
highlights how the proposed model and filtering method can be useful in
estimating the level of segregation with a better accuracy compared to the
baseline method of HMM filtering. We also evaluate the proposed model on a
public Twitter election dataset.

###  4.1 Simulation on Weighted Customer-Merchant Graph

In this subsection, we consider a social media marketing scenario where the
connection between company and customers is modeled as a MB. A HMB filter is
implemented to estimate the inter-community distance based on sampled
observation of single edge weights and an additive Gaussian noise. It
outperforms a hidden Markov chain filter regarding the mean-squared error.

####  4.1.1 Simulation setup

We consider a company-customer network of 10 utilitarian customers, 20 fans,
and 1 company as discussed in Section 2 for $2T-1$ time steps ($T=20$). The
state space of the weight of each edge between utilitarian customers and
company is an arithmetic sequence
$\big{[}1,\frac{N_{S}-2}{N_{S}-1},\cdots,\frac{1}{N_{S}-1},0\big{]}$. The
weight evolves according to a transition matrix which is a Toeplitz matrix.
Each descending diagonal from left to right is constant:
$\big{[}(\frac{1}{4})^{\scriptstyle{N_{S}-1}},\cdots,1,\
\cdots,(\frac{1}{4})^{\scriptstyle{N_{S}-1}}\big{]}$. Each row vector of the
Toeplitz matrix is normalized so that the row elements add up to $1$. We then
implement the HMB filter in assuming the measurement noise is Gaussian with
the empirically estimated mean and covariance in Section 3.1. To assess the
performance, we compare the mean-squared error of the HMB filter with a HMM
filter that assumes the underlying process is a Markov chain (instead of a
MB).

Figure 5: Mean-squared error of the proposed Hidden Markov bridge (HMB) filter
compared with a Hidden Markov Model (HMM) filter in the company-customer
marketing network simulation. HMB filter outperforms HMM filter by
approximately $20\%$, which indicates its better prediction ability of
segregation in social networks.

####  4.1.2 Numerical Results of Filters

Fig. 5 depicts the results obtained using the above simulation setup. Results
show that the proposed HMB filter outperforms the HMM filter for all
considered number of states ($N_{S}$ values). Thus, the numerical results
indicate that the proposed Bayesian filter is capable of accurately estimating
the level of segregation in a company-consumer network from noisy sampled
edges.

###  4.2 Hidden Markov Bridge Model of Political Polarization during 2020
Election

In this subsection, we propose that the MB model is sociologically beneficial
for predicting the emergence and segregation level of echo chambers on a
social network. We justify our conclusion on a real-world Twitter dataset
where a polarization score is defined on the Twitter retweet network. We
determine the model parameters (i.e. the transition matrix) from maximum
likelihood algorithm which is derived in Appendix B. We apply the HMB filter
to estimate the polarization score. The filter’s estimation accuracy
outperforms a HMM filter regarding mean-squared error. We also verify that the
observation noise can be approximated as a Gaussian distribution based on
statistical hypothesis testing.

####  4.2.1 Construction of Retweet Network and Polarization Score

account name |  political party
---|---
@realDonaldTrump |  R
@GovBillWeld |  R
@MarkSanford |  R
@WalshFreedom |  R
@JohnDelaney |  R
@AmbassadorRice |  R
@TrumpWarRoom |  R
@TeamTrump |  R
@JoeBiden |  D
@CoryBooker |  D
@GovernorBullock |  D
@SenKamalaHarris |  D
@BernieSanders |  D
@SenWarren |  D
@marwilliamson |  D
@AndrewYang |  D
TABLE I: A sample of Election-related Twitter accounts tracked in the dataset.
Figure 6: Snapshots of a dynamic retweet network with two communities at 4
different timestamps before the Nov. 3 presidential election. The ratio of
intra-community connections and total connections (sum of intra- and inter-
community connections) evolves and is modeled as a Markov bridge in (14). The
graph is laid out using DrL (same as Fig.1).

We leverage a publicly available dataset which encompasses 240 million tweets
related to the 2020 U.S. presidential election. The dataset captured tweets
with specific user mentions and accounts (57 in total) that are tied to
president candidates and politicians. A sample of such accounts is shown in
Table I. The column of political party denotes the party which this account
belongs to (D-democratic, R-republican). We select and sample tweets from Oct.
1 to Nov. 1, spanning a 30-day period before the election day (Nov. 3) which
is about 7 million tweets in total. See Appendix A for data collection and
sampling procedure.

From this subset of tweets, we constructed a dynamic retweet graph
$G^{(t)}(V,E^{(t)}),\;t=1,\cdots,30$, where the nodes represents $|V|$ Twitter
accounts, directed and unweighted edges $E_{ij}^{(t)}$ from node $i$ to node
$j$ if user $j$ retweets a message222Here we do not consider ”quote tweets”
(retweet with a comment added) to avoid the use of ”quote tweets” for ironic
or criticizing purposes. originally posted by user $i$ on day $t$. We filtered
out nodes with out-degree fewer than 2 (which means they only retweets once
during the 30-day period). In summary, the retweet network has $|V|=1399644$
vertices and $\sum_{t=1}^{30}|E^{(t)}|=5047498$ edges during the specified
period. In Fig. 6, we take a sample of the retweet graph and plot 4 snapshots
of its largest weakly connected component. It clearly shows the pattern of
partitioning into two polarized community.

To study the evolution of political opinion polarization during the 30-day
period, we define a temporal variable named polarization score. We select
users who have retweeted election-related accounts from both political
parties. We estimate these users’ political leaning (interchangeably referred
to as ideology) as follows: Every retweet to accounts from either political
party increases the count for that side by +1. The user’s political leaning is
classified as the side with more accumulated retweets. We dismiss the users
whose retweets are equally sourced from two political parties. After this
ideology classification, we denote $D=\\{v_{1},\cdots,v_{m}\\}\subset V$ be
the set of $m$ left-leaning users, and $R=\\{v_{m+1},\cdots,v_{m+n}\\}\subset
V$ be the set of $n$ right-leaning users. We then define the polarization
score of the retweet network on day $t$ as the ratio of the amount of intra-
ideological retweets (e.g. user from $D$ retweets an election-related account
who is from the Democratic party) to the amount of intra-ideological retweets
plus the amount of cross-ideological retweets (e.g. user from $D$ retweets an
election-related account who is from the Republican party) on day $t$. We
collected 28 such 30-day sequences of polarization scores, which are used for
training the transition matrix and computing the empirical distribution of the
observation error.

$y^{(t)}=\frac{|E_{ij}^{(t)}|_{(v_{i},v_{j})\in D\;\vee\;(v_{i},v_{j})\in
R}}{|E_{ij}^{(t)}|\forall(v_{i},v_{j})}$ (14)

####  4.2.2 Hidden Markov Bridge Filter Estimation Results

We formulate $x^{(t)}$ as a hidden Markov bridge with $y^{(t)}$ as its
observation. The hidden states form an arithmetic sequence with maximum and
minimum corresponding to those of the observation. We anticipate a high-level
opinion polarization near or on election day since people are required to vote
to one candidate from one party. Therefore we set the destination, i.e. the
final state to be the maximal state.

$x^{(t)}$ follows transition probabilities as depicted by (2) with $c$ as the
maximal state, and transition matrix $P$ derived from maximum likelihood
algorithm in Appendix B. The observation noise is hypothetically verified to
follow a Gaussian distribution as shown in Fig. 7.

Figure 7: The empirical CDF of the observation noise for polarization score on
the Twitter dataset and the CDF of a Gaussian distribution of four hidden
states (state 2, 3, 4, 5) in the 6-state model. The _p_ -value of KS test
indicates that the observation noise can be approximated by Gaussian noise.

To assess the performance of the proposed filter in (13), we compare its mean-
squared error with a HMM filter. Results show that the proposed HMB filter
outperforms the HMM filter for all considered number of hidden states and
reduces the mean-squared error by 10% (Fig. 8).

Figure 8: Mean-squared estimation error of the polarization score on Twitter
dataset. It shows that the proposed Hidden Markov bridge (HMB) filter
outperforms a Hidden Markov Model (HMM) filter in estimating the level of
polarization in a social network.

###  4.3 Discussion on the Experiment with Real-world Twitter Data

The numerical evaluation section explored modeling and estimation of
segregation in social networks. For the first social media marketing example,
we proposed a tractable model for segregation based on Markov bridge processes
of the connection strength between company and customers. We also proposed a
Bayesian filter (named HMB filter) to estimate the level of segregation (as
measured by graph conductance) by polling some random pairs of neighbors (i.e.
edges) in the network.

To validate the proposed model with real world data, our second opinion
polarization example studied Twitter users’ retweet behavior before 2020
presidential election. We anticipated a high level of polarization near the
election and modeled the portion of users’ retweets to someone of same
political ideology as a Markov bridge process. Extension of this study could
help answer the following two research questions:

(1) As has been demonstrated in [15], are liberals more likely than
conservatives to involve in cross-ideological dissemination?

(2) In addition to political events such as election, would other topics
elicit similar polarized echo chambers in online conversation?

Nevertheless, one major limitation of the study is that we equally weight each
retweet. As further improvement, we could consider the following four aspects:

(1) Consider tweet’s temporal effect. We could formulate the influence of
tweets to decrease exponentially after posted so that newer tweets would be
more informative and representative of user’s political opinion. While many
tweets spread within a limited time window, some could achieve high virality.
Therefore we could assign different decay rate for each tweet as well.

(2) Define user’s political ideology as a time-evolving variable instead of a
constant. Although a user is typically unchanged as to his favorable party,
his political leaning might change due to personal experience and external
information. We could adapt the correspondence analysis or the maximum
likelihood logit model in [29] to obtain user’ political ideology at different
times and assign political scores accordingly to the user-related tweets.

(3) Explore the content and sentiment of tweets. It is found in [30] that
tweets with negative emotion tend to get reposted more rapidly and frequently
than positive and neutral messages. Take one step forward, we could decompose
each tweet’s popularity into its political effect and content effect, and
mitigate the unbalance of different sentiments or wording among different
tweets.

(4) Combine information from multi-level social graphs. In addition to retweet
network, we could construct other types of social network from Twitter data,
including mention, follow and comment. We could certainly analyze the trend of
polarization separately on these networks and average the results, however, it
is more promising to construct a multi-level heterogeneous graph to learn a
structural representation of polarization.

##  5 Conclusion

This paper studied the sociological phenomena of segregation and echo chambers
in social networks. We proposed a Markov bridge dynamics based model for
evaluating the interaction between customers and company in a social media
marketing scenario. We then justified the model by looking at the evolution of
political opinion polarization on a real-world Twitter dataset. We formulated
an additive Gaussian measurement noise model for the Markov bridge, derived
the EM algorithm for estimating parameters of the hidden Markov bridge model,
and proposed a Hidden Markov Bridge filter to estimate the state of
segregation and echo chambers based on sample of the social network. The
numerical results indicated that our filter outperforms time homogeneous
filters such as a HMM filter.

Future directions of this work include further improving the accuracy of the
proposed method using different sampling methods based on friendship paradox
(e.g. [24, 25, 26]); enriching this framework to handle more sophisticated
network topologies such as heterogeneous graphs; incorporating the hidden
Markov bridge model with generation models to forecast opinion dynamics (e.g.
[20, 31, 32]).

##  Appendix A Twitter Dataset Details

The Twitter dataset was provided by [3] and publicly available333The dataset
website: https://github.com/echen102/us-pres-elections-2020. The authors used
Twitter’s streaming API through Tweepy and kept track of tweets with specific
keyword mentions and accounts related to the 2020 US presidential election
since May 2019. The data contains approximately $1\%$ stream of all tweets in
real-time.

In obedience to Twitter’s Developer Agreement & Policy, only tweet’s Tweet ID
is shared. The Tweet ID is preserved in text files in temporal order. We used
Doc-Now’s Hydrator444https://github.com/DocNow/hydrator to retrieve the tweet
objects555https://developer.twitter.com/en/docs/twitter-api/v1/data-
dictionary/object-model/tweet with full tweet payloads including the tweet
poster, content, timestamp, and the author who is retweeted from.

To reduce the amount of data, we use systematic sampling, which means we pick
every $n^{th}$ tweets ($n=20$) to comprise the data used in the research. For
each tweet, we keep its poster, author and timestamp if it is a retweet (if
the tweet object has a ’retweeted_status’ attribute).

##  Appendix B EM Algorithm for Hidden Markov bridge parameters

For real-life application of the Markov bridge model proposed in section 2, we
need to obtain the model parameters which are useful for filtering and
forecasting the segregation state of the social network. This section presents
the EM algorithm which serves the purpose of finding the maximum-likelihood
estimate of the parameters.

###  B.1 Forward-Backward Smoothing Algorithm for Hidden Markov Bridge

In this subsection we derive the forward-backward (also named Baum-Welch)
algorithm for smoothing the hidden Markov bridge (HMB) model. Consider HMB
model with parameter $\theta=(S,P,O)$ where $S$ is a $X$-state Markov chain
with transition matrix $P=(P_{a,b}),\,a,b\in S=\\{s_{1},\cdots,s_{X}\\}$, and
$O$ is the HMB emission probability function. The HMB model has unknown state
sequence $X^{(T)}=(x^{(1)},\cdots,x^{(T)})$ and observation sequence
$Y^{(T)}=(y^{(1)},\cdots,y^{(T)})$. We know the destination of the state
sequence $X^{(T)}$ is $c\in S$.

We first go through the forward procedure by defining

$\alpha_{\theta}^{(t)}(a)=P(x^{(t)}=a,y^{(1)},\cdots,y^{(t)}|\theta)=P(x^{(t)}=a,Y^{(t)}|\theta)$
(15)

which is the probability of seeing the partial sequence
$(y^{(1)},\cdots,y^{(t)})$ and ending up in state $a$ at time $t$.

The backward procedure is similar by defining a backward variable

$\beta_{\theta}^{(t|T)}(a)=P(y^{(t+1)},\cdots,y^{(T)}|x^{(t)}=a)$ (16)

We now define

$\gamma_{\theta}^{(t)}(a)=P(x^{(t)}=a,Y^{(T)}|\theta)$ (17)

which is the probability of being in state $a$ at time $t$ for the observation
sequence $(y^{(1)},\cdots,y^{(T)})$. It can be derived in terms of
$\alpha_{\theta}^{(t)}$ and $\beta_{\theta}^{(t|T)}$

$\gamma_{\theta}^{(t)}(a)=\frac{\alpha_{\theta}^{(t)}(a)\beta_{\theta}^{(t|T)}(a)}{\sum_{b=s_{1}}^{s_{X}}\alpha_{\theta}^{(t)}(b)\beta_{\theta}^{(t|T)}(b)}$
(18)

We also define

$\gamma_{\theta}^{(t)}(a,b)=P(x^{(t)}=a,x^{(t+1)}=b,Y^{(T)}|\theta)$ (19)

which is the probability of being in state $a$ at time $t$ and being in state
$b$ at time $t+1$. This can be expressed in terms of $\alpha_{\theta}^{(t)}$
and $\beta_{\theta}^{(t|T)}$

$\begin{split}&\gamma_{\theta}^{(t)}(a,b)=\\\
&\frac{\alpha_{\theta}^{(t)}(a)B_{a,b}(t)O(y^{(t+1)}|x^{(t+1)}=b)\beta_{\theta}^{(t+1|T)}(b)}{\sum_{a=s_{1}}^{s_{X}}\sum_{b=s_{1}}^{s_{X}}\alpha_{\theta}^{(t)}(a)B_{a,b}(t)O(y^{(t+1)}|x^{(t+1)}=b)\beta_{\theta}^{(t+1|T)}(b)}\end{split}$
(20)

###  B.2 Maximum Likelihood Estimation Algorithm

We assume the HMB model is observed in Gaussian noise, i.e. the emission
probability follows a zero-mean Gaussian distribution.

$y^{(t)}=x^{(t)}+v^{(t)},\;v^{(t)}\sim N\big{(}0,\sigma^{2}\big{)}$ (21)

The E-step of the EM algorithm finds the expected value of the complete-data
log-likelihood with respect to the unknown state
$X^{(T)}=(x^{(1)},\cdots,x^{(T)})$ given the observation
$Y^{(T)}=(y^{(1)},\cdots,y^{(T)})$ and the current parameter estimates
$\theta^{I}=(S,P,\sigma)$. This log-likelihood is defined as the Q function

$Q(\theta,\theta^{I})=E\\{\log{P(Y^{(T)},X^{(T)}|\theta)}|Y^{(T)},\theta^{I}\\}$
(22)

The second step (the M-step) of the EM algorithm is to maximize the
expectation we computed in the first step. That is, we find

$\theta^{I+1}=\operatorname*{argmax}_{\theta}Q(\theta,\theta^{I})$ (23)

The joint probability of states $X^{(T)}$ and observations $Y^{(T)}$ given the
parameter is formulated as

$\begin{split}&\log{P(Y^{(T)},X^{(T)}|\theta)}\\\
&=\log{\prod_{t=1}^{T}P(y^{(t)}|x^{(t)})}P(x^{(t)}|x^{(t-1)},x^{(T)}=c)\\\
&=\sum_{t=1}^{T}\log{P(y^{(t)}|x^{(t)})}+\log{P(x^{(t)}|x^{(t-1)},x^{(T)}=c)}\\\
&=\sum_{t=1}^{T}\sum_{a=s_{1}}^{s_{X}}I(x^{(t)}=a)\log{P(y^{(t)}|x^{(t)}=a)}+\\\
&\sum_{t=1}^{T}\sum_{a=s_{1}}^{s_{X}}\sum_{b=s_{1}}^{s_{X}}\big{[}I(x^{(t)}=a,x^{(t+1)}=b)\\\
&\log{P(x^{(t+1)}=b|x^{(t)}=a,x^{(T)}=c)}\big{]}\\\
&=\sum_{t=1}^{T}\sum_{a=s_{1}}^{s_{X}}I(x^{(t)}=a)\big{[}\log{(\frac{1}{\sqrt{2\pi}\sigma})}-\frac{{(y^{(t)}-a)}^{2}}{2\sigma^{2}}\big{]}+\\\
&\sum_{t=1}^{T}\sum_{a=s_{1}}^{s_{X}}\sum_{b=s_{1}}^{s_{X}}I(x^{(t)}=a,x^{(t+1)}=b)\log{B_{a,b}^{c}(t)}\\\
\end{split}$ (24)

The Q function can then be simplified as

$\begin{split}Q(\theta,\theta^{I})=-\frac{T}{2}\log{\sigma^{2}}-\frac{1}{2\sigma^{2}}\sum_{t=1}^{T}\sum_{a=s_{1}}^{s_{X}}{(y^{(t)}-a)}^{2}\gamma^{(t)}_{\theta^{I}}(a)\\\
+\sum_{t=1}^{T}\sum_{a=s_{1}}^{s_{X}}\sum_{b=s_{1}}^{s_{X}}\gamma^{(t)}_{\theta^{I}}(a,b)\log{B_{a,b}^{c}(t)}\\\
=\cdots+\sum_{t=1}^{T}\sum_{a=s_{1}}^{s_{X}}\sum_{b=s_{1}}^{s_{X}}\gamma^{(t)}_{\theta^{I}}(a,b)\log{P_{a,b}\frac{{(P^{T-(t+1)})}_{b,c}}{{(P^{T-t})}_{a,c}}}\end{split}$
(25)

Recursively solving $\frac{\partial Q(\theta,\theta^{I})}{\partial\theta}=0$
for the model parameter $\theta^{I+1}$. Each iteration is guaranteed to
improve log-likelihood, and the algorithm is guaranteed to converge to a local
maximum.

## Acknowledgments

This research was supported by the U. S. Army Research Office under grant
W911NF-19-1-0365, and the National Science Foundation under grant 1714180.

## References

  * [1] M. McPherson, L. Smith-Lovin, and J. M. Cook, “Birds of a feather: Homophily in social networks,” _Annual review of sociology_ , vol. 27, no. 1, pp. 415–444, 2001.
  * [2] K. Sasahara, W. Chen, H. Peng, G. L. Ciampaglia, A. Flammini, and F. Menczer, “On the inevitability of online echo chambers,” _arXiv preprint arXiv:1905.03919_ , 2019.
  * [3] E. Chen, A. Deb, and E. Ferrara, “# election2020: The first public twitter dataset on the 2020 us presidential election,” _arXiv preprint arXiv:2010.00600_ , 2020.
  * [4] M. Fanaswala, V. Krishnamurthy, and L. White, “Destination-aware target tracking via syntactic signal processing,” in _2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2011, pp. 3692–3695.
  * [5] M. Fanaswala and V. Krishnamurthy, “Detection of anomalous trajectory patterns in target tracking via stochastic context-free grammars and reciprocal process models,” _IEEE Journal of Selected Topics in Signal Processing_ , vol. 7, no. 1, pp. 76–90, 2012.
  * [6] ——, “Spatiotemporal trajectory models for metalevel target tracking,” _IEEE Aerospace and Electronic Systems Magazine_ , vol. 30, no. 1, pp. 16–31, 2015.
  * [7] M. Fanaswala, V. Krishnamurthy, and L. White, “Destination-aware target tracking via syntactic signal processing,” in _2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2011, pp. 3692–3695.
  * [8] T. C. Schelling, “Dynamic models of segregation,” _Journal of mathematical sociology_ , vol. 1, no. 2, pp. 143–186, 1971.
  * [9] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks,” _Journal of statistical mechanics: theory and experiment_ , vol. 2008, no. 10, p. P10008, 2008.
  * [10] J. Jiang, E. Chen, S. Yan, K. Lerman, and E. Ferrara, “Political polarization drives online conversations about covid-19 in the united states,” _Human Behavior and Emerging Technologies_ , vol. 2, no. 3, pp. 200–211, 2020\.
  * [11] Y. Ge, S. Zhao, H. Zhou, C. Pei, F. Sun, W. Ou, and Y. Zhang, “Understanding echo chambers in e-commerce recommender systems,” in _Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval_ , 2020, pp. 2261–2270.
  * [12] E. Wallace, I. Buil, L. de Chernatony, and M. Hogan, “Who “likes” you… and why? a typology of facebook fans: From “fan”-atics and self-expressives to utilitarians and authentics,” _Journal of Advertising Research_ , vol. 54, no. 1, pp. 92–109, 2014.
  * [13] M. Cinelli, G. D. F. Morales, A. Galeazzi, W. Quattrociocchi, and M. Starnini, “Echo chambers on social media: A comparative analysis,” _arXiv preprint arXiv:2004.09603_ , 2020.
  * [14] F. Baumann, P. Lorenz-Spreen, I. M. Sokolov, and M. Starnini, “Modeling echo chambers and polarization dynamics in social networks,” _Physical Review Letters_ , vol. 124, no. 4, p. 048301, 2020.
  * [15] P. Barberá, J. T. Jost, J. Nagler, J. A. Tucker, and R. Bonneau, “Tweeting from left to right: Is online political communication more than an echo chamber?” _Psychological science_ , vol. 26, no. 10, pp. 1531–1542, 2015\.
  * [16] K. Garimella, G. De Francisci Morales, A. Gionis, and M. Mathioudakis, “Political discourse on social media: Echo chambers, gatekeepers, and the price of bipartisanship,” in _Proceedings of the 2018 World Wide Web Conference_ , 2018, pp. 913–922.
  * [17] M. H. DeGroot, “Reaching a consensus,” _Journal of the American Statistical Association_ , vol. 69, no. 345, pp. 118–121, 1974.
  * [18] P. Dandekar, A. Goel, and D. T. Lee, “Biased assimilation, homophily, and the dynamics of polarization,” _Proceedings of the National Academy of Sciences_ , vol. 110, no. 15, pp. 5791–5796, 2013.
  * [19] C. Liu, N. Zhou, X.-X. Zhan, G.-Q. Sun, and Z.-K. Zhang, “Markov-based solution for information diffusion on adaptive social networks,” _Applied Mathematics and Computation_ , vol. 380, p. 125286, 2020.
  * [20] A. De, I. Valera, N. Ganguly, S. Bhattacharya, and M. G. Rodriguez, “Learning and forecasting opinion dynamics in social networks,” in _Advances in Neural Information Processing Systems_ , 2016, pp. 397–405.
  * [21] L. B. White and F. Carravetta, “Optimal smoothing for finite state hidden reciprocal processes,” _IEEE transactions on automatic control_ , vol. 56, no. 9, pp. 2156–2161, 2011.
  * [22] F. R. Chung and F. C. Graham, _Spectral graph theory_. American Mathematical Soc., 1997, no. 92.
  * [23] N. M. M. De Abreu, “Old and new results on algebraic connectivity of graphs,” _Linear algebra and its applications_ , vol. 423, no. 1, pp. 53–73, 2007\.
  * [24] B. Nettasinghe and V. Krishnamurthy, ““what do your friends think?”: Efficient polling methods for networks using friendship paradox,” _IEEE Transactions on Knowledge and Data Engineering_ , 2019.
  * [25] ——, “The friendship paradox: Implications in statistical inference of social networks,” in _2019 IEEE 29th International Workshop on Machine Learning for Signal Processing (MLSP)_. IEEE, 2019, pp. 1–6.
  * [26] ——, “Maximum likelihood estimation of power-law degree distributions using friendship paradox based sampling,” _arXiv preprint arXiv:1908.00310_ , 2019\.
  * [27] V. Krishnamurthy, _Partially observed Markov decision processes_. Cambridge University Press, 2016.
  * [28] G. Stamatescu, L. B. White, and R. Bruce-Doust, “Track extraction with hidden reciprocal chains,” _IEEE Transactions on Automatic Control_ , vol. 63, no. 4, pp. 1097–1104, 2017.
  * [29] P. Barberá, “Birds of the same feather tweet together: Bayesian ideal point estimation using twitter data,” _Political analysis_ , vol. 23, no. 1, pp. 76–91, 2015.
  * [30] S. Tsugawa and H. Ohsaki, “Negative messages spread rapidly and widely on social media,” in _Proceedings of the 2015 ACM on Conference on Online Social Networks_ , 2015, pp. 151–160.
  * [31] G. Amati, S. Angelini, F. Capri, G. Gambosi, G. Rossi, and P. Vocca, “Twitter temporal evolution analysis: Comparing event and topic driven retweet graphs.” _IADIS International Journal on Computer Science & Information Systems_, vol. 11, no. 2, 2016.
  * [32] M. Ten Thij, T. Ouboter, D. Worm, N. Litvak, H. van den Berg, and S. Bhulai, “Modelling of trends in twitter using retweet graph dynamics,” in _International Workshop on Algorithms and Models for the Web-Graph_. Springer, 2014, pp. 132–147.