# Estimating Exposure to Information on Social Networks

Buddhika Nettasinghe<EMAIL_ADDRESS>Cornell University ,  Kowe Kadoma
<EMAIL_ADDRESS>Cornell Tech ,  Mor Naaman<EMAIL_ADDRESS>Cornell
Tech and  Vikram Krishnamurthy<EMAIL_ADDRESS>Cornell University

(2022)

###### Abstract.

This paper considers the problem of estimating exposure to information in a
social network. Given a piece of information (e.g., a URL of a news article on
Facebook, a hashtag on Twitter), our aim is to find the fraction of people on
the network who have been exposed to it. The exact value of exposure to a
piece of information is determined by two features: the structure of the
underlying social network and the set of people who shared the piece of
information. Often, both features are not publicly available (i.e., access to
the two features is limited only to the internal administrators of the
platform) and difficult to be estimated from data. As a solution, we propose
two methods to estimate the exposure to a piece of information in an unbiased
manner: a vanilla method which is based on sampling the network uniformly and
a method which non-uniformly samples the network motivated by the Friendship
Paradox. We provide theoretical results which characterize the conditions (in
terms of properties of the network and the piece of information) under which
one method outperforms the other. Further, we outline extensions of the
proposed methods to dynamic information cascades (where the exposure needs to
be tracked in real-time). We demonstrate the practical feasibility of the
proposed methods via experiments on multiple synthetic and real-world
datasets.

social networks, exposure to information, friendship paradox, information
diffusion, information cascades

††copyright: acmcopyright††journalyear: 2022††doi: 10.1145/TBD††conference:
KDD; 2022; KDD††booktitle: In Submission, KDD 2022††price: 15.00††isbn:
978-1-4503-TBD††ccs: Information systems Social networks††ccs: Information
systems Information retrieval

##  1\. Introduction

Online social networks are an important mechanism through which people are
exposed to information. Estimating the total number of people who are exposed
by their friends to a piece of information111 A “piece of information” refers
to any uniquely identifiable message (e.g., a URL, a hashtag) that is shared
by the users on a social network with their contacts. on an online social
network (e.g., the URL of an article on Facebook, a hashtag on Twitter, etc.)
is an important problem with key societal implications. Such estimates of
exposure can, for example, help researchers and the public track the
prevalence and reach of election misinformation (Dwoskin, line; Allcott and
Gentzkow, 2017) or improve the public health response to the Coronavirus
(Simpson and Conner, 2020; Tasnim et al., 2020).

To measure the exposure to a piece of information on a network, one needs
access to two features: the set of people who shared the piece of information,
and the structure of the underlying social network. Of these two features, the
structure of the underlying social network is often not publicly available
and, fully or partially estimating it from data is not a practically feasible
task due to the networks’ massive size (e.g., billions of nodes and edges in
Facebook), constantly evolving nature (Leskovec et al., 2008; Leskovec et al.,
2005), and limits placed by corporations on data collection. Similarly, the
set of people who shared the piece of information is often also not publicly
known and difficult to estimate from data since it evolves as the piece of
information spreads through the social network in the form of an information
cascade e.g., a URL of a news article that is being shared on Facebook. As a
result, calculating exposure to a piece of information on a social network in
a data-driven manner remains a challenging task.

This state of affairs is unfortunate as efficient (in terms of computation and
resources) and accurate (in terms of statistical properties) estimates of
exposure to information can provide two important benefits:

  * _1\. Analysis perspective:_ to identify the pieces of information that are most widely consumed and thus, shed light on how the information consumption patterns affect the outcomes of various high-stake events such as elections, COVID vaccine acceptance, etc. (Allcott and Gentzkow, 2017; Tasnim et al., 2020).

  * _2\. Intervention perspective:_ to prioritize various pieces of information in the content moderation and fact checking process of a social media platform. Such interventions could be useful to prevent large numbers of users from being exposed to harmful or misleading information.

Surprisingly, the problem of estimating exposure to information has received
relatively little attention in the literature despite its importance.
Formally, this problem can be stated as follows (in the context of an
undirected social network such as Facebook).

Problem of estimating exposure to information: Consider an undirected social
network ${G=(V,E)}$ and, let ${s(v)=1}$ if the node $v\in V$ shared (with the
set of their neighbors $\mathcal{N}(v)\subset V$) a piece of information and
$s(v)=0$ otherwise. Assuming the graph $G$ and the sharing function
$s:V\rightarrow\\{0,1\\}$ are unknown, estimate the fraction of nodes exposed
to the piece of information, (1) $\bar{f}=\frac{|\\{v\in V:f(v)=1\\}|}{|V|}$
where, $f(v)=1$ if the node $v\in V$ has been exposed to the piece of
information by one of their neighbors and $f(v)=0$ otherwise i.e.,
$f(v)=\mathds{1}_{\\{\exists\,u\,\in\,\mathcal{N}(v)\text{ such that
}s(u)=1\\}}(v)$.

In the above formulation, the value $s(v)\in\\{0,1\\}$ indicates whether the
user (i.e., node) $v\in V$ shared the piece of information in concern and
$f(v)\in\\{0,1\\}$ indicates whether the user $v\in V$ has been exposed to it
by one of their neighbours. Thus, the parameter of interest $\bar{f}$ denotes
the average exposure to the piece of information in the social network i.e.,
$\bar{f}=\operatorname*{{\mathbb{E}}}\\{f(X)\\}$ where $X$ denotes a uniformly
sampled node from the set of all nodes $V$. In this setting, we are tasked
with devising a method to estimate the average exposure $\bar{f}$. Since the
sharing function $s:V\rightarrow\\{0,1\\}$ and the network $G=(V,E)$ are both
unknown, the exposure function $f:V\rightarrow\\{0,1\\}$ is also unknown (as
it depends on $s$ and $G$). However, the exposure $f(v_{i})\in\\{0,1\\}$ of a
small number of sampled nodes $v_{i},i=1,2,\dots,n$ (where $n\ll|V|$) can
often be found by looking at whether at least one neighbor of $v_{i}$ (for
each $i=1,2,\dots,n$) shared the piece of information.

Main results:

  * (1) We propose two methods for estimating the exposure to a piece of information in an undirected social network (i.e., the problem that is formalized above): a vanilla method based on uniform sampling and a friendship paradox-based method. Both methods are intuitive and practically feasible.

  * (2) Via theoretical analysis and numerical experiments, we characterize the conditions (in terms of the properties of the underlying network and the piece of information in concern) under which the vanilla method outperforms the friendship paradox-based method and vice-versa. These conditions depend only on parameters that are typically known apriori (e.g., whether the network is assortative or disassortative). As such, these characterizing conditions help to choose the most accurate method for estimating exposure to information depending on the context of the problem.

  * (3) We extend the two proposed methods to the setting of a dynamic information cascade where the piece of information gradually spreads and more people become exposed to it over time. The resulting algorithms iteratively track the increasing average exposure in real-time. In addition, we show how the proposed methods can be extended to the context of directed networks (e.g., Twitter).

  * (4) We provide detailed numerical simulations (based on synthetic data) as well as empirical experiments (based on real-world data) to illustrate the usefulness and feasibility of the proposed methods under various practical settings.

##  2\. Related Work and Preliminaries

Our problem definition and methods are motivated by recent literature and
events, which we expand on below. We then present background preliminaries on
the main approach that we use in this work, the friendship paradox.

###  2.1. Motivation

The need for a principled method for estimating exposure to information in
social media has intensified recently.

One reason for this increased interest in exposure estimation is the role that
exposure to information on social networks can play in affecting the outcomes
of high-stake events that define the course of our society. In particular, the
question of reach of “fake news” on Facebook has become a major public concern
following the 2016 US presidential election (Dwoskin, line; Allcott and
Gentzkow, 2017). Similarly, large scale exposure to false information on
social media has complicated the public health response to the Coronavirus
(Simpson and Conner, 2020; Tasnim et al., 2020). Both examples highlight the
need for tracking and quantifying exposure, for example to prioritize fact-
checking of trending coronavirus and election-related information content.

It has also become clear that the platforms cannot be trusted to reliably
provide this information, in real-time or retroactively (Ghaffary, line;
Edelman, line). For example, Facebook recently acknowledged serious problems
in the data provided to academic researchers in 2020 (Alba, line; Timberg,
line), and reportedly shelved “most-viewed pages” reports when those
conflicted with the company’s publicity goals (Alba and Mac, line). Such
incidents have given rise to the need of methods which can accurately estimate
the exposure to various pieces of information independently without the
involvement of the social media companies.

Researchers looking to estimate exposure to information in social networks are
largely limited to survey-based methods. In such methods, a question is
presented to a set of respondents to gather information on the frequency and
pattern of their social media usage (Goldman and Warren, 2020). For example,
researchers had used a post-election online survey to assess how exposure to
fake news affected the 2016 US election (Allcott and Gentzkow, 2017). Other
research had used panels of users who provided access to their web traffic to
assess such exposure (Guess et al., 2020). Closer to our baseline method here,
researchers had used a panel of Twitter users to track their exposure to
specific ”fake news” URLs and domains shared by people they follow, but did
not offer network-wide measures (Grinberg et al., 2019).

As opposed to the post-event survey-based approach, the social network
sampling-based methods proposed in this work can be implemented in real-time
(to track the progression of exposure as a piece of information spreads over
time). Further, these methods yield unbiased estimates of the exposure to
information across the entire social network. In addition, these techniques
can be implemented in a practically feasible manner without the full knowledge
of the network (e.g., via a random walk) as well as the set of people who
shared the piece of information.

###  2.2. The Friendship Paradox

Our work here is motivated by the graph theoretic consequence named
_friendship paradox_ which states “on average, the number of friends of a
random friend is always greater than or equal to the number of friends of a
random individual”. Formally:

###### Theorem 1 (Friendship paradox (Feld, 1991)).

Consider an undirected graph $G=(V,E)$. Let $X$ be a node sampled uniformly
from $V$ and $Y$ be a uniformly sampled end-node from a uniformly sampled edge
$e\in E$. Then,

(2)
$\operatorname*{{\mathbb{E}}}\\{d(Y)\\}\geq\operatorname*{{\mathbb{E}}}\\{d(X)\\},$

where $d(X)$ and $d(Y)$ denote the degrees of $X$ and $Y$, respectively.

In Theorem 1, the random variable $Y$ is called a random friend. This is
because it is a random person from a uniformly sampled pair of friends.222A
random friend $Y$ on an undirected graph $G=(V,E)$ has the distribution
$\operatorname*{\mathbb{P}}\\{Y=v\\}\propto d(v)$ for all $v\in V$. In other
words, a random friend is a node sampled with a probability proportional to
their degrees. The intuition behind the friendship paradox (Theorem 1) is that
individuals with large number of friends (i.e., high-degree nodes) appear as
the friends of many others. Therefore, a random end of a random link (i.e.,
the random variable $Y$) is more likely to yield a high degree node than a
uniformly sampled node (i.e., the random variable $X$). Consequently, sampling
random friends (i.e., $Y$) allows us to reach high-degree nodes in the network
without the full knowledge of the network.

The friendship paradox has been exploited in many statistical estimation
methods e.g., to reduce the variance in survey based polling methods
(Nettasinghe and Krishnamurthy, 2021a), to efficiently estimate power-law
degree distributions (Nettasinghe and Krishnamurthy, 2021b; Eom and Jo, 2015),
and to quickly detect the outbreak of a disease (Garcia-Herranz et al., 2014).
This paper differs from such existing friendship paradox-based methods in
several key ways. First, our focus is on the problem of estimating the
fraction of people exposed to a piece of information, which is different from
the problems studied in prior works (such as polling, estimating degree
distributions, detecting disease outbreaks) that are based on the friendship
paradox. Second, we do not claim that the friendship paradox-based method is
the better approach for any given setting. Instead, we provide an exact
characterization of the conditions where the friendship paradox-based method
outperforms the vanilla method based on uniform sampling. Finally, the methods
that we propose are provably unbiased whereas most previously proposed
estimators based on the friendship paradox attempt to trade-off the bias and
variance in order to achieve a smaller mean squared error.

##  3\. Algorithmic Approach

In this section, we present two methods for estimating the average exposure to
information: a vanilla method based on uniform sampling and a friendship
paradox-based method.

###  3.1. Vanilla method based on uniform sampling

The vanilla approach for estimating the average exposure $\bar{f}$ works by
obtaining a set of random nodes and checking whether these nodes have been
exposed to the piece of information via their contacts.

_Vanilla method for estimating exposure to information_

  * Step 1: Sample $n$ random nodes $X_{1},\dots,X_{n}$ uniformly and independently from the set of all nodes $V$.

  * Step 2: Use,

(3) $\hat{f}_{\textrm{Vl}}=\frac{\sum_{i=1}^{n}{f(X_{i})}}{n}$

as the estimate of the average exposure $\bar{f}$.

The vanilla estimator $\hat{f}_{\textrm{Vl}}$ given in Eq. 3 is unbiased i.e.,
$\operatorname*{{\mathbb{E}}}\\{\hat{f}_{\textrm{Vl}}\\}=\bar{f}$. However,
the vanilla estimator $\hat{f}_{\textrm{Vl}}$ would intuitively yield a larger
variance since random nodes are not likely exposed to the piece of information
when $s(\cdot)$ is a very sparse function (i.e., only very few people shared
the information).

###  3.2. Friendship paradox-based method

In order to reduce the variance in the estimate of average exposure, we can
exploit the friendship paradox-based sampling (instead of vanilla uniform
sampling) as follows:

_Friendship paradox-based method for estimating exposure to information_

  * Step 1: Sample $n$ random friends $Y_{1},\dots,Y_{n}$ from the network independently (a random friend $Y_{i}$ is a random end of a random link i.e., a link is sampled uniformly from the network and one end of that link is taken with an unbiased coin flip).

  * Step 2: Use,

(4)
$\hat{f}_{\textrm{FP}}=\frac{\bar{k}}{n}\sum_{i=1}^{n}\frac{f(Y_{i})}{d(Y_{i})}$

as the estimate of average exposure $\bar{f}$ where, $d(v)$ denotes the degree
of $v\in V$ and $\bar{k}$ the average degree of the graph $G=(V,E)$.

The friendship paradox-based estimator $\hat{f}_{\textrm{FP}}$ can be viewed
as an application of importance sampling in social networks where the samples
are generated from a different distribution (i.e., random friends $Y$) than
the distribution that is directly related to the parameter of interest
$\bar{f}=\operatorname*{{\mathbb{E}}}\\{f(X)\\}$ (i.e., random nodes $X$). In
particular, random friends are more popular than random nodes in expectation
(according to Theorem 1) and thus, sampling random friends will lower the
variance by accessing individuals who are more likely to be exposed to the
piece of information due to their large popularity (even when the sharing
function $s(\cdot)$ is sparse). The additional terms $d(Y_{i}),\bar{k}$ that
appear in $\hat{f}_{\textrm{FP}}$ (compared to $\hat{f}_{\textrm{Vl}}$)
correct for the bias resulting from sampling the more popular random friends
$Y_{i}$ instead of random nodes $X_{i}$.

The average degree $\bar{k}$ in Eq. 4 is typically a known statistic for most
social networks such as Facebook (Ugander et al., 2011), which makes the
implementation of the friendship paradox-based estimator
$\hat{f}_{\textrm{FP}}$ practically feasible. Further, in situations where the
edges cannot be sampled uniformly from the network, the friendship paradox-
based estimator $\hat{f}_{\textrm{FP}}$ can also be implemented via random
walks as described in Appendix C.

To summarize, Sec. 3 presented two methods to estimate the average exposure to
information based on uniform (vanilla) and friendship paradox-based sampling.
Extensions of the two proposed methods will be discussed in Sec. 5.

##  4\. Comparison of Statistical Properties of the two methods

In this section, we analyze and compare the statistical properties of the two
proposed estimators (the vanilla estimator $\hat{f}_{\textrm{Vl}}$ given in
Eq. 3 and the friendship paradox-based estimator $\hat{f}_{\textrm{FP}}$ given
in Eq. 4). The aim of this analysis is to identify the conditions under which
one estimator may be more accurate than the other for estimating the average
exposure to information $\bar{f}$.

The following result (see Appendix A.1 for proof) characterizes the bias and
variance of the two exposure estimators.

###### Theorem 1.

Consider the vanilla estimator $\hat{f}_{\textrm{Vl}}$ given in Eq. 3 and the
friendship paradox-based estimator $\hat{f}_{\textrm{FP}}$ given in Eq. 4.

  1. (1)

Both the vanilla estimator $\hat{f}_{\textrm{Vl}}$ and the friendship paradox-
based estimator $\hat{f}_{\textrm{FP}}$ are unbiased estimators of the
fraction of people exposed to a piece of information $\bar{f}$ (defined in Eq.
1) i.e.,

(5)
$\operatorname*{{\mathbb{E}}}\left\\{\hat{f}_{\textrm{Vl}}\right\\}=\operatorname*{{\mathbb{E}}}\left\\{\hat{f}_{\textrm{FP}}\right\\}=\bar{f}.$

  2. (2)

The variances of vanilla estimator $\hat{f}_{\textrm{Vl}}$ and the friendship
paradox-based estimator $\hat{f}_{\textrm{FP}}$ are,

(6)
$\displaystyle\begin{split}\operatorname*{Var}\left\\{\hat{f}_{\textrm{Vl}}\right\\}&=\frac{1}{n}\bar{f}\left(1-\bar{f}\right)\\\
\operatorname*{Var}\left\\{\hat{f}_{\textrm{FP}}\right\\}&=\frac{1}{n}\left(\bar{k}\operatorname*{{\mathbb{E}}}\left\\{\frac{f(X)}{d(X)}\right\\}-\bar{f}^{2}\right)\end{split}$

where $\bar{k}$ is the average degree of the graph.

As stated in the first part of Theorem 1, both the vanilla estimator
$\hat{f}_{\textrm{Vl}}$ and the friendship paradox-based estimator
$\hat{f}_{\textrm{FP}}$ are unbiased estimators of the average exposure
$\bar{f}$. Therefore, the method that has the smaller variance in the given
setting should be used for estimating the average exposure $\bar{f}$. In order
to do this, the rest of this section aims to identify the conditions under
which one method outperforms the other in terms of the variance.

To theoretically compare the variances, we consider the class of undirected
Markovian random networks that are completely characterized by their degree
distribution $P(k)$ (which gives the probability that a uniformly sampled node
from the network has degree $k$) and the conditional degree distribution
$P(k^{\prime}|k)$ (which gives the conditional probability that an edge from a
degree $k$ node connects to a degree $k^{\prime}$ node). The term “Markovian”
here refers to the fact that all higher-order correlations can be expressed
only in terms of the two functions $P(k)$ and $P(k^{\prime}|k)$. We can derive
a joint degree distribution using $P(k)$ and $P(k^{\prime}|k)$ as

(7)
$P\left(k,k^{\prime}\right)=\frac{kP(k)}{\bar{k}}P\left(k^{\prime}|k\right),$

which gives the probability that a uniformly sampled link connects two nodes
with degrees $k$ and $k^{\prime}$. The correlation coefficient corresponding
to this joint degree distribution $P\left(k,k^{\prime}\right)$ is called the
_assortativity coefficient_ , and we denote it with $r\in[-1,1]$. Networks for
which $r>0$ are called assortative networks since high-degree nodes are more
likely to be connected to other high-degree nodes and low-degree nodes are
more likely to be connected to other low-degree nodes. On the other hand,
networks for which $r<0$ are called disassortative networks since high-degree
nodes and low-degree nodes are more likely to be connected with each other. A
detailed description of Markovian random networks and assortativity can be
found in (Boguñá et al., 2003; Boguñá and Pastor-Satorras, 2002).

In addition to $P(k)$ and $P\left(k^{\prime}|k\right)$ which characterize the
Markovian random network, we also define $P_{s}(1|k)$ which is the conditional
probability that a node with degree $k$ shares the piece of information.
Consequently, $P_{s}(0|k)=1-P_{s}(1|k)$ is the probability that a node with
degree $k$ does not share the piece of information. Intuitively, if the
$P_{s}\left(1|k\right)$ is closer to $1$ for larger (resp. smaller) values of
$k$, then high-degree (resp. low-degree) nodes are more likely to share the
piece of information. In particular, if the sharing happens independently of
the node popularity (i.e., high-degree and low-degree nodes are equally likely
to share the piece of information), then $P_{s}(1|k)$ would be a constant that
does not depend on degree $k$. Such relations (between sharing and degree) can
be captured using the correlation coefficient between the sharing and the
degree, which we refer to as the _degree-sharing correlation coefficient_ and
denote by $\rho\in[-1,1]$.

The following result (see Appendix A.2 for proof) compares the variances of
the two estimators $\hat{f}_{\textrm{FP}},\hat{f}_{\textrm{Vl}}$ (given in Eq.
3 and Eq. 4, respectively) in terms of the degree distribution $P(k)$, the
conditional degree distribution $P\left(k^{\prime}|k\right)$ and the
conditional sharing probability $P_{s}(1|k)$ in the context of Markovian
random networks.

###### Theorem 2.

The variance of the friendship paradox-based estimator $\hat{f}_{\textrm{FP}}$
given in Eq. 4 is less than or equal to the variance of the vanilla estimator
$\hat{f}_{\textrm{Vl}}$ given in Eq. 3 (i.e.,
$\operatorname*{Var}\\{\hat{f}_{\textrm{FP}}\\}\leq\operatorname*{Var}\\{\hat{f}_{\textrm{Vl}}\\}$)
if and only if

(8) $\mathbb{E}_{k\sim
P(k)}\left\\{\left(1-\frac{\bar{k}}{k}\right)\operatorname*{\mathbb{P}}\left\\{f(X)=1|d(X)=k\right\\}\right\\}\geq
0,$

where $X$ is a uniformly sampled node from the network, $\mathbb{E}_{k\sim
P(k)}$ denotes the expectation with respect to the degree distribution $P(k)$,
and

(9)
$\operatorname*{\mathbb{P}}\left\\{f(X)=1|d(X)=k\right\\}=1-\left(\sum_{k^{\prime}}P\left(k^{\prime}|k\right)P_{s}\left(0|k^{\prime}\right)\right)^{k}.$

Discussion of Theorem 2:  Theorem 2 yields insights that help identify the
settings where one method is more accurate (in terms of variance) compared to
the other for estimating the average exposure to information $\bar{f}$. In
particular, these insights relate the variance of the methods to important
network parameters such as the degree distribution $P(k)$, assortativity
coefficient $r$ and the degree-sharing correlation coefficient $\rho$ as we
discuss in detail below.

1\. Choosing the best method based on assortativity coefficient $r$ and
degree-sharing correlation coefficient $\rho$:  Due to the term
$\left(1-{\bar{k}}/{k}\right)$, the condition Eq. 8 is more likely to be
satisfied when the value
$\operatorname*{\mathbb{P}}\left\\{f(X)=1|d(X)=k\right\\}$ is closer to $1$
for larger values of the degree $k$ and the value
$\operatorname*{\mathbb{P}}\left\\{f(X)=1|d(X)=k\right\\}$ is closer to $0$
for smaller values of the degree $k$. According to Eq. 9, this happens when,

  1. i.

$P\left(k^{\prime}|k\right)$ is closer to $1$ for $k^{\prime}\gg\bar{k}\gg k$
and $P_{s}\left(1|k^{\prime}\right)$ is closer to $0$ for
$k^{\prime}\gg\bar{k}$,
or,

  2. ii.

$P\left(k^{\prime}|k\right)$ is closer to $1$ for $k,k^{\prime}\ll\bar{k}$ and
$P_{s}\left(1|k^{\prime}\right)$ is closer to $0$ for $k^{\prime}\ll\bar{k}$.

Consequently, friendship paradox based estimator $\hat{f}_{\textrm{FP}}$ has a
smaller variance compared to the vanilla estimator $\hat{f}_{\textrm{Vl}}$
when $r,\rho>0$ (i.e., the network is assortative and the high-degree
individuals are more likely to share the piece of information) or $r,\rho<0$
(i.e., the network is disassortative and the low-degree individuals are more
likely to share the piece of information). The arithmetic signs of the
assortativity coefficient $r$ and the degree-sharing correlation coefficient
$\rho$ are typically known parameters based on the context. For example, it is
known that many social networks are assortative whereas technological networks
are disassortative (Newman, 2002). Similarly, for pieces of information that
get originated from highly popular individuals (e.g., political news, updates
on government policy, etc.), the degree-sharing correlation coefficient is
typically positive. Hence, this first insight allows us to choose the
estimator that best suits the given context based on arithmetic signs of the
assortativity coefficient $r$ and the degree-sharing correlation coefficient
$\rho$.

2\. When the sharing is independent from the popularity:  If the node degree
and the sharing are statistically independent, Eq. 9 yields that
$\operatorname*{\mathbb{P}}\left\\{f(X)=1|d(X)\right\\}=1-P_{s}(0)^{k}$, where
$P_{s}(0)=1-P_{s}(1)$ is the probability that any node (independent of the
degree $k$) does not share the piece of information. Consequently, when the
node degree and the sharing are statistically independent, the friendship
paradox-based estimator $\hat{f}_{\textrm{FP}}$ has a smaller variance
compared to the vanilla estimator $\hat{f}_{\textrm{Vl}}$ if and only if,

(10) $\mathbb{E}_{k\sim
P(k)}\left\\{\left(1-\frac{\bar{k}}{k}\right)\left(1-P_{s}(0)^{k}\right)\right\\}\geq
0,$

according to Eq. 8. We numerically evaluated the expected value in the left-
hand-side of Eq. 10 for two types of degree distributions: a power-law
distribution $P(k)\propto k^{-\alpha}$ (where $\alpha>2$ is the power-law
exponent) and an exponential distribution $P(k)=\frac{1}{\lambda}e^{-\lambda
k}$ (where $\lambda>0$ is a constant parameter). Our results suggest that the
condition Eq. 10 is not satisfied for all values of the power-law exponent
$\alpha>2$, the exponential parameter $\lambda>0$, and the probability
$P_{s}(0)\in[0,1]$. Therefore, the vanilla estimator $\hat{f}_{\textrm{Vl}}$
produces the theoretically better estimate when the node degree and the
sharing are statistically independent (implying that $\rho=0$) and the network
has either a power-law or an exponential degree distribution.

3\. A widely shared piece of information vs. a less widely shared piece of
information:  According to Eq. 10, smaller values of $P_{s}(0)$ lead to a
bigger disparity in the performance between the friendship paradox-based
estimator $\hat{f}_{\textrm{FP}}$ and the vanilla estimator
$\hat{f}_{\textrm{Vl}}$. This implies that choosing the right method is of
particular importance when the fraction of people who share a piece of
information is small (compared to the size of the network). An important
example for this situation is the starting phase of an information cascade
where a piece of information has been less widely shared. Since identifying
the correct exposure at this beginning stage is crucial for purposes such as
fact-checking before many people are exposed, this further highlights the
importance of choosing the right method by using the insight (1) discussed
earlier.

In summary, Sec. 4 theoretically analyzed the bias and variance of the two
estimators presented in Sec. 3 (vanilla estimator $\hat{f}_{\textrm{Vl}}$ and
the friendship paradox-based estimator $\hat{f}_{\textrm{FP}}$) in terms of
properties of the underlying network and the piece of information. Next, we
present some extensions of the proposed methods (in Sec. 5), and then verify
and complement the theoretical insights using numerical experiments (in Sec.
6).

##  5\. Extensions of Proposed Methods

In this section, we extend the vanilla estimator $\hat{f}_{\textrm{Vl}}$ in
Eq. 3 and the friendship paradox-based estimator $\hat{f}_{\textrm{FP}}$ Eq. 4
to directed networks (Sec. 5.1) and dynamic information cascades (Sec. 5.2).

###  5.1. Directed networks

In a directed network $G=(V,E)$ (e.g., Twitter), a link $u\rightarrow v$
(pointing from a node $u\in V$ to $v\in V$) indicates that the node $v$
follows the node $u$ i.e., $u$ is the friend and $v$ is the follower. Hence,
the out-degree $d_{o}(v)$ and in-degree $d_{i}(v)$ of a node $v\in V$ denote
the number of followers and friends of $v$, respectively. We say that a node
$v\in V$ in a directed network is exposed to a piece of information (i.e.,
$f(v)=1$) if at least one friend of $v$ shared it. In this context, our aim is
to estimate the average exposure to the piece of information which is denoted
by $\bar{f}$.

In order to estimate the average exposure $\bar{f}$, a directed network can be
sampled in three different ways: a random node $\mathcal{X}$ (sampled
uniformly from $V$), a random friend $\mathcal{Y}$ which is the tail end of a
uniformly sampled link (i.e.,
$\operatorname*{\mathbb{P}}(\mathcal{Y}=v)\propto d_{o}(v)$), a random
follower $\mathcal{Z}$ which is the source end of a uniformly sampled link
(i.e., $\operatorname*{\mathbb{P}}(\mathcal{Z}=v)\propto d_{i}(v)$).
Consequently, we can construct three estimators of the average exposure
$\bar{f}$ as follows:

(11)
$\hat{f}_{\textrm{Vl}}=\frac{\sum_{i=1}^{n}{f(\mathcal{X}_{i})}}{n},\hskip
2.84544pt\hat{f}_{\textrm{Fr}}=\frac{\bar{k}}{n}\sum_{i=1}^{n}\frac{f(\mathcal{Y}_{i})}{d_{o}(\mathcal{Y}_{i})},\hskip
2.84544pt\hat{f}_{\textrm{Fo}}=\frac{\bar{k}}{n}\sum_{i=1}^{n}\frac{f(\mathcal{Z}_{i})}{d_{i}(\mathcal{Z}_{i})}$

where $\bar{k}$ corresponds to the average in-degree
$\operatorname*{{\mathbb{E}}}\\{d_{i}(\mathcal{X})\\}$ (which is also same as
the average out-degree $\operatorname*{{\mathbb{E}}}\\{d_{o}(\mathcal{X})\\}$)
and indices $i=1,\dots,n$ denote iid samples of each sampling method. The
three estimators given in Eq. 11 are motivated by the four versions of the
friendship paradox that can exist on directed networks (Alipourfard et al.,
2020; Higham, [n. d.]). In particular, one version says that a random follower
on average has more friends than a random node (i.e.,
$\operatorname*{{\mathbb{E}}}\\{d_{i}(\mathcal{Z})\\}\geq\operatorname*{{\mathbb{E}}}\\{d_{i}(\mathcal{X})\\}$),
implying that random followers ($\mathcal{Z}_{i}$) are more likely to be
exposed to a piece of information. Hence, $\hat{f}_{\textrm{Fo}}$ in Eq. 11
can reduce the variance by incorporating more exposed individuals into the
sample.

###  5.2. Dynamic information cascades

The vanilla estimator $\hat{f}_{\textrm{Vl}}$ in Eq. 3 and the friendship
paradox-based estimator $\hat{f}_{\textrm{FP}}$ in Eq. 4 assume that the
function $s(\cdot)$ indicating the set of people who have shared the piece of
information is static. However, the set of people who have shared a piece of
information typically grows over time as it gets reshared and reposted by the
users who were exposed it, leading to an information cascades. This subsection
extends the vanilla estimator $\hat{f}_{\textrm{Vl}}$ and the friendship
paradox-based estimator $\hat{f}_{\textrm{FP}}$ to track the increasing
average exposure to such information cascades in real-time. The key idea is to
use a stochastic approximation algorithm with a constant step-size.

To simplify the notation, let us assume that only one sample can be collected
at each time instant and there are no samples at time $0$, allowing us to use
the same variable $n$ for discrete time and the number of samples available.
Further, let the vanilla and friendship paradox-based estimators at time $n$
be denoted by $\hat{f}_{\textrm{Vl}}^{(n)}$ and $\hat{f}_{\textrm{FP}}^{(n)}$
respectively. Then, note that,

(12)
$\displaystyle\begin{split}\hat{f}_{\textrm{Vl}}^{(n)}&=\hat{f}_{\textrm{Vl}}^{(n-1)}+\frac{1}{n}\left(f\left(X_{n}\right)-\hat{f}_{\textrm{Vl}}^{(n-1)}\right)\\\
\hat{f}_{\textrm{FP}}^{(n)}&=\hat{f}_{\textrm{FP}}^{(n-1)}+\frac{1}{n}\left(\bar{k}\frac{f\left(Y_{n}\right)}{d\left(Y_{n}\right)}-\hat{f}_{\textrm{FP}}^{(n-1)}\right)\end{split}$

where, $X_{n},Y_{n}$ denote a random node and a random friend at time $n$,
respectively. The recursions in Eq. 12 are obtained under the assumption that
the average exposure $\bar{f}$ is time-invariant and therefore, the update
term decays with time (due to the decreasing step-size $1/n$) and converges to
zero. Intuitively, this means that one new sample would not make a significant
difference to an estimate (of a time-invariant parameter) derived with a
relatively large number of samples (i.e., $n\gg 1$). In particular, it can be
shown that the recursions in Eq. 12 converge to the average exposure $\bar{f}$
with probability $1$ under mild conditions.

However, the decreasing step-size $1/n$ in Eq. 12 is not suitable when the
average exposure is evolving over time (denoted by $\bar{f}^{(n)}$). This is
because the decreasing step-size $1/n$ will stop updating eventually even
though the average exposure $\bar{f}^{(n)}$ will keep changing. As a solution,
the decreasing step-size in Eq. 12 can be replaced with a constant step-size
$\epsilon>0$ for the case of time evolving average exposure $\bar{f}^{(n)}$.
Then, the new recursive methods for tracking the time evolving average
exposure $\bar{f}^{(n)}$ using the vanilla and friendship paradox-based
methods will be as follows:

(13) $\displaystyle\hat{f}_{\textrm{Vl}}^{(n)}$
$\displaystyle=\hat{f}_{\textrm{Vl}}^{(n-1)}+\epsilon\left(f\left(X_{n}\right)-\hat{f}_{\textrm{Vl}}^{(n-1)}\right)$
(14) $\displaystyle\hat{f}_{\textrm{FP}}^{(n)}$
$\displaystyle=\hat{f}_{\textrm{FP}}^{(n-1)}+\epsilon\left(\bar{k}\frac{f\left(Y_{n}\right)}{d\left(Y_{n}\right)}-\hat{f}_{\textrm{FP}}^{(n-1)}\right).$

The above two methods can track the progression of average exposure
$\bar{f}^{(n)}$ when it is evolving on a slower time scale compared to the
collection of samples. In other words, $\bar{f}^{(n)}$ is assumed to remain
approximately constant for every $c>1$ samples being collected; if $c\approx
1$ (resp. $c\gg 1$), we say the piece of information is spreading rapidly
(resp. slowly). The value of the step-size parameter $\epsilon>0$ in Eq. 13
and Eq. 14 determines the effect of the update at each time. In particular,
the value of $\epsilon$ should be relatively large (resp. small) to track the
the average exposure to a piece of information that is spreading rapidly
(resp. slowly) through the social network.

In summary, Sec. 5 extended the vanilla and friendship paradox-based
estimators proposed in Sec. 3 to two settings: directed networks and dynamic
information cascades. These extensions are numerically and empirically
evaluated in the subsequent sections.

##  6\. Numerical Experiments

(a) Absolute error values for a power-law exponent $\mathbf{\alpha=2.5}$

(b) Absolute error values for a power-law exponent $\mathbf{\alpha=2.2}$.

Figure 1. The absolute error values of the vanilla estimate
$\hat{f}_{\textrm{Vl}}$ (given in Eq. 3) and the friendship paradox-based
estimate $\hat{f}_{\textrm{FP}}$ (given in Eq. 4) for two synthetically
generated power-law networks (with power-law exponents $\mathbf{\alpha=2.5}$
and $\mathbf{\alpha=2.5}$) with various values of the assortativity
coefficient $\mathbf{r}$, degree-sharing correlation coefficient
$\mathbf{\rho}$ and the unconditional probability of sharing the piece of
information $p_{s}$ (i.e.,
$p_{s}=\sum_{k}P_{s}\left(1|k\right)P\left(k\right)$ is the probability that a
uniformly chosen node shares the piece of information). The shown values were
estimated via a Monte Carlo simulation as explained in Sec. 6. The plots show
that the numerical results agree with the conclusions reached in the
statistical analysis in Sec. 4. In particular, the $\hat{f}_{\textrm{FP}}$ is
the better choice when both $\mathbf{r}$ and $\mathbf{\rho}$ have the same
sign. Further, comparing Fig 1(a) with Fig. 1(b) shows that heavy-tails
increase the disparity between the performances of the two estimators.

(a) Assortative network (i.e., assortativity coefficient $r>0$)

(b) Disassortative network (i.e., assortativity coefficient $r<0$)

Figure 2. The performance of the vanilla and friendship paradox-based
stochastic approximation algorithms (given in Eq. 13 and Eq. 14, respectively)
for tracking the exposure to an information cascade (in real-time) under the
Independent Cascade model (ICM) on a synthetic power-law network with the
power-law exponent $\mathbf{\alpha=2.5}$. The top-row shows the two estimates
together with the true parameter $\bar{f}$ and the middle-row shows the
absolute errors corresponding to the two estimates at each time instant and
the average error over all time instants. The third row shows the variation of
the degree-sharing correlation coefficient $\rho$ with time. The friendship
paradox-based stochastic approximation algorithm works better for the
assortative network (Fig. 2(a)) while the the vanilla stochastic approximation
algorithm works better for the disassortative network (Fig. 2(b)). This
observation agrees with the theoretical conclusions reached in Sec. 4.

In this section, we numerically compare the two estimators (vanilla estimator
$\hat{f}_{\textrm{Vl}}$ given in Eq. 3 and the friendship paradox-based
estimator $\hat{f}_{\textrm{FP}}$ given in Eq. 4) using detailed simulation
experiments. The aim of this comparison is to verify and complement the
theoretical analysis in Sec. 4, and obtain additional insight into the
performance of the two methods and how they compare with each other in various
settings.

Simulation setup:  To compare the vanilla estimator $\hat{f}_{\textrm{Vl}}$
and the friendship paradox-based estimator $\hat{f}_{\textrm{FP}}$ (given in
Eq. 3 and Eq. 4), we use synthetically generated power-law networks from the
configuration model (Newman, 2003) with $10000$ nodes and power-law exponents
$\alpha=2.5$ and $\alpha=2.2$. The edges in each network $G=(V,E)$ are re-
wired using the method proposed in (Van Mieghem et al., 2010) to explore the
three possible regions of the assortativity coefficient $r\in[0,1]$
($r<0,r=0,r>0$). Next, the value $s(v)\in\\{0,1\\}$ for each node $v\in V$ is
first assigned as an iid Bernoulli random variable whose parameter determines
the fraction of the people that share the piece of information. Then, the
values $s(v),v\in V$ are swapped amongst the nodes using the label-swapping
method used in (Lerman et al., 2016) to correlate the sharing and degree to
consider the three cases of the degree-label correlation coefficient
$\rho\in[0,1]$ ($\rho<0$, $\rho=0$ and $\rho>0$). The results obtained using
this simulation setup are shown in Fig. 1. To compare the recursive algorithms
based on the vanilla and friendship paradox-based estimators (given in Eq. 13
and Eq. 14, respectively), we use two well-known information diffusion models:
the Independent Cascade model (ICM) and the Linear Threshold Model (LTM). The
results for the ICM are shown in Fig. 2 and the results for the LTM are given
in Appendix B. Additional details about the simulation setup are given in
Appendix B.

Discussion of the Numerical Results (Fig. 1 and Fig. 2):  The numerical
results verify the theoretical conclusions (from Sec. 4) and yield additional
insight into the practical usefulness of the two methods as we discuss below.

1\. Choosing the method that is best for the context:  Fig. 1(a) shows that
the friendship paradox-based estimate $\hat{f}_{\textrm{FP}}$ is more accurate
(compared to the vanilla estimate $\hat{f}_{\textrm{Vl}}$) when the
assortativity coefficient $r$ and the degree-sharing correlation coefficient
$\rho$ have the same signs (i.e., Fig. 1(a)(i) and Fig. 1(a)(ix)). When the
assortativity coefficient $r$ and the degree-sharing correlation coefficient
$\rho$ have different signs (i.e., Fig. 1(a)(iii) and Fig. 1(a)(vii)), the
vanilla estimate $\hat{f}_{\textrm{Vl}}$ is more accurate compared to the
friendship paradox-based estimate $\hat{f}_{\textrm{FP}}$. In addition, the
vanilla estimate $\hat{f}_{\textrm{Vl}}$ has a smaller error when the degree
and sharing are uncorrelated (i.e., $\rho=0$ corresponding to middle column of
Fig. 1(a) and Fig. 1(b)) for when the sharing probability is not too small (so
that both methods yield absolute errors smaller than $100\%$ of the true
parameter $\bar{f}$). Further, each subfigure of Fig. 1(a) and Fig. 1(b) shows
that the difference in the accuracy of the two estimates is larger when the
unconditional sharing probability $p_{s}$ (i.e.,
$p_{s}=\sum_{k}P_{s}\left(1|k\right)P\left(k\right)$) is smaller, highlighting
that choosing the best method is crucial when the piece of information has
been shared by only a smaller fraction of people. These numerical observations
verify the theoretical expectations captured in the first and second points in
the discussion related to Theorem 2 in Sec. 4, and emphasizes the importance
of the choice for less widely shared pieces of information, per the third
point.

2\. Implications of the heavy-tails: Comparing Fig. 1(a) with Fig. 1(b)
indicates that the difference in the accuracy of the two methods is larger
when the tail of the degree distribution is heavier. Since real-world social
networks have been empirically shown to have heavy-tails, this observation
highlights the importance of utilizing the theoretical insight to pick the
best method for the given context.

3\. Tracking the exposure to an information cascade in real-time:  Fig. 2
shows the performance of the vanilla and the friendship paradox-based
stochastic approximation algorithms (Eq. 13 and Eq. 14, respectively) for
tracking the exposure to an information cascade simulated from the ICM. In
Fig. 2(a), it can be clearly seen that the friendship paradox-based stochastic
approximation Eq. 14 outperforms the vanilla stochastic approximation Eq. 13,
especially after the time-step $40$ where the diffusion process speeds up and
the degree-sharing correlation coefficient starts increasing rapidly. In
particular, the friendship paradox-based method closely detects the sudden
phase transition of the diffusion process approximately at time-step $55$
where the exposure suddenly jumps to a larger value. This result aligns with
the theoretical conclusions in Sec. 4, since both assortativity coefficient
$r$ and the degree-sharing correlation coefficient $\rho$ are both positive,
leading to the friendship paradox-based method to outperform the vanilla
method. On the other hand, the Fig. 2(b) corresponds to the disassortative
networks. Since the assortativity coefficient $r$ and the degree-sharing
correlation coefficient $\rho$ have opposite signs, the vanilla method
outperforms the friendship paradox-based method.

4\. Implications of assortativity $r$ and degree-sharing correlation $\rho$ on
the overall accuracy:  It can be seen from Fig. 1 that both estimates
($\hat{f}_{\textrm{Vl}}$ and $\hat{f}_{\textrm{FP}}$) tend to be less accurate
when the degree and sharing are negatively correlated (i.e., $\rho<0$ in first
column of Fig. 1). Although the friendship paradox-based estimator performs
better in Fig. 1(a)(i), its accuracy decreases when moving to Fig.
1(a)(iv,vii). This result is due to the fact that when $\rho<0$, the nodes who
share the piece of information are the less popular nodes, which makes the
average exposure $\bar{f}$ smaller and more difficult to estimate. If $r<0$ in
addition to $\rho<0$ (e.g., a star graph where outer nodes are sharing), then
the friendship paradox-based estimator $\hat{f}_{\textrm{FP}}$ can easily
reach the core nodes that are more likely to be exposed due to their
popularity, and thus reduce the variance as in Fig. 1(a)(i). However, when
$r>0$ and $\rho<0$ (i.e., Fig. 1(a)(vii)), the less popular fringe nodes who
share the piece of information are more likely to be separated from the core
of the network so that the friendship paradox-based estimator cannot reach
them. As such, both estimators tend to be the least accurate when
$\rho<0,r>0$. An important example of this is the case where a piece of
information originates with the less visible (i.e., fringe) nodes of the
network. As such, special attention should be paid to choosing the best method
when $\rho<0$ to get the best possible accuracy.

In summary, Sec. 6 numerically compared the absolute errors of the estimates
obtained using the two estimators presented in Sec. 3 (vanilla estimator
$\hat{f}_{\textrm{Vl}}$ and the friendship paradox-based estimator
$\hat{f}_{\textrm{FP}}$). The numerical results agree with the theoretical
conclusions provided in Sec. 4 and shed more light on the conditions under
which one method outperforms the other.

##  7\. Results on Real-World Networks

Evaluating the accuracy of the two estimators
$\hat{f}_{\textrm{Vl}},\hat{f}_{\textrm{FP}}$ (proposed in Sec. 3) requires
the true exposure $\bar{f}$ (i.e., the ground truth). However, as we stressed
in Sec. 1, the exact value of the ground truth $\bar{f}$ depends on two
features (the full network and the set of sharers) which are highly difficult
to obtain, and our study was motivated by this difficulty in the first place.
As such, comparing the estimates with the ground truth $\bar{f}$ in real-world
networks (e.g., Twitter, Facebook) is not feasible from a resource and
computation viewpoint. Therefore, in this section, we first use real-world
undirected networks with the sharing function generated synthetically (Sec.
7.1). We then evaluate our estimators on a real-world network with actual
sharing data, using the directed ACM citation network (Sec. 7.2).

###  7.1. Undirected Networks

(a) For a astrophysics co-authorship network ($r=0.21$)

(b) For a general relativity co-authorship network ($r=0.66$)

(c) For a company Facebook page dataset ($r=0.01$)

(d) For an athlete Facebook page dataset ($r=-0.03$)

Figure 3. The absolute error values of the vanilla estimate
$\hat{f}_{\textrm{Vl}}$ (given in Eq. 3) and the friendship paradox-based
estimate $\hat{f}_{\textrm{FP}}$ (given in Eq. 4) for four real-world network
datasets. These results validate the theoretical insights (Sec. 4) and
complement the numerical experiments (Sec. 6).

We tested the vanilla and friendship paradox-based estimators
($\hat{f}_{\textrm{Vl}},\hat{f}_{\textrm{FP}}$) on four publicly available
real-world network datasets in the SNAP database (Leskovec and Krevl, 2014).
These networks include: a collaboration network between authors of papers
submitted to Astrophysics and General Relativity in the Arxiv website, a
network of Facebook pages of athletes, and a Facebook page network of
different companies. For these four networks, the sharing function
$s:V\rightarrow\\{0,1\\}$ was synthetically generated using the methods in
Sec. 6. The results obtained using these five real-world networks are shown in
Fig. 3.

For the network datasets corresponding to Fig. 3(a)-Fig. 3(c) (where $r>0$),
the friendship paradox-based estimator $\hat{f}_{\textrm{FP}}$ outperforms the
vanilla estimator $\hat{f}_{\textrm{Vl}}$ when $\rho>0$ while both methods
have relatively large error values (above 100%) when $\rho<0$. This result is
as we expected since $\hat{f}_{\textrm{FP}}$ works better when $r,\rho>0$ (as
per the first point in the discussion related to Theorem 2) and both
$\hat{f}_{\textrm{Vl}},\hat{f}_{\textrm{FP}}$ tend to be less accurate when
$\rho<0,r>0$ (as per the fourth point in the discussion of numerical results).
For the network dataset correponding to Fig. 3(d), $\hat{f}_{\textrm{FP}}$
(resp. $\hat{f}_{\textrm{Vl}}$) works better when $\rho<0$ (resp. $\rho>0$)
since the network has $r<0$ (as we theoretically expected). Therefore, the
empirical findings align with both the theoretical and numerical results (Sec.
4 and Sec. 6, respectively).

###  7.2. ACM Citation Network

In this analysis, we provide a full real-world network (i.e., without
subsampling the network) as well as actual sharing data from that network. We
use a network of academic papers and their references. We consider a paper
that contains a phrase in its title as a “sharer” of that phrase and all
papers that cite that paper as the “exposed”. We obtain a dataset of 629,814
papers from DBLP, ACM, and MAG (Microsoft Academic Group) (Tang et al., 2008).
We filtered out papers that did not have references within the original
dataset or were not referenced by another paper in the original dataset to
create a final dataset of 217,335 papers. We determine phrases of varying
popularity to see how our estimates perform depending on the fraction of
sharers. To generate the set of phrases, we first filter the papers’ titles
for stopwords and determine the frequency of each word to create a numerically
sorted dictionary with word frequency pairs. Then, we use NLTK’s bigram
association measures to create word pairs (i.e., phrases) using a subset of
words from the dictionary’s beginning. We define popular phrases as having
more than 400 sharers (e.g., data mining, information systems), average
phrases with between 200 and 400 sharers (e.g., computer graphics, embedded
systems), and unpopular phrases with 100 to 200 sharers (e.g., network design,
optimization problems). We perform this experiment with 25 popular phrases, 25
average phrases, and 25 unpopular phrases.

Based on the detailed results in Section 4 and their extension in Section 5.1,
we expect the friendship paradox estimate based on random followers
$\hat{f}_{\textrm{Fo}}$ to have the lowest absolute mean error, and the
vanilla estimate $\hat{f}_{\textrm{Vl}}$ to outperform the friendship paradox
estimate based on random friends $\hat{f}_{\textrm{Fr}}$. This is due to one
version of the friendship paradox that states on average, a random follower
has more friends than a random node; therefore, a random follower is more
likely to be exposed to a piece of information.

Discussion of the ACM Citation Results (Fig. 4): Fig. 4 shows the average
vanilla estimate $\hat{f}_{\textrm{Vl}}$, friend-based estimate
$\hat{f}_{\textrm{Fr}}$, and follower-based estimate $\hat{f}_{\textrm{Fo}}$
for popular phrases (a), average phrases (b), and unpopular phrases (c). In
each case, the follower-based estimate $\hat{f}_{\textrm{Fo}}$ outperforms the
other two as we expected from the directed versions of the friendship paradox
mentioned in Sec. 5.1. In particular, Fig. 4 shows that the absolute error of
all three estimates increase as the popularity of the phrases decrease.
However, the follower-based estimate $\hat{f}_{\textrm{Fo}}$ is more accurate
compared to the other two estimates (i.e., the difference in the accuracy is
larger) for unpopular phrases (Fig. 4(c)). This is because random followers
are more likely to be exposed even to an unpopular piece of information due to
their larger friend count (according to the directed versions of the
friendship paradox) and hence, sampling random friends lowers the variance of
the estimate. In comparison, uniform and friend-based sampling are less likely
to reach the smaller number of exposed individuals when the popularity of the
piece of information is lower and as such, they yield a larger variance.

Figure 4. The absolute error values of the vanilla estimate
$\hat{f}_{\textrm{Vl}}$, the friendship paradox estimate based on friends
$\hat{f}_{\textrm{Fr}}$, and the friendship paradox estimate based on
followers $\hat{f}_{\textrm{Fo}}$ given in Eq. (11) on a real-world, directed
network. These results validate the theoretical insights (Sec. 4) and their
extension (Sec. 5.1).

##  8\. Conclusion

We presented a practically feasible framework for estimating the fraction of
people who have been exposed to a piece of information by their contacts
(i.e., average exposure) in a social network. In particular, we proposed two
methods to estimate the average exposure: a method that is based on uniform
sampling and a method that samples random friends (random ends of random
links). The latter method can be thought of as a variance reduction method
motivated by the friendship paradox which incorporates more high-degree
individuals (who are more likely to be exposed to the piece of information due
to their large popularity) into the sample. Both methods are unbiased; we
provided theoretical results which characterize the conditions (in terms of
properties of the underlying network as well as the piece of information)
where one method outperforms the other in terms of the variance. We also
presented extensions of the proposed methods to directed networks and dynamic
information cascades (where the average exposure needs to be tracked in real-
time). The proposed methods and the theoretical conclusions were verified
numerically (via simulations) as well as via experiments on several real-world
network datasets.

## References

  * (1)
  * Alba (line) Davey Alba. 2021 [Online].  Facebook sent flawed data to misinformation researchers.  New York Times.  https://www.nytimes.com/live/2020/2020-election-misinformation-distortions#facebook-sent-flawed-data-to-misinformation-researchers
  * Alba and Mac (line) Davey Alba and Ryan Mac. 2021 [Online].  Facebook, Fearing Public Outcry, Shelved Earlier Report on Popular Posts.  New York Times.  https://www.nytimes.com/2021/08/20/technology/facebook-popular-posts.html
  * Alipourfard et al. (2020) Nazanin Alipourfard, Buddhika Nettasinghe, Andrés Abeliuk, Vikram Krishnamurthy, and Kristina Lerman. 2020.  Friendship paradox biases perceptions in directed networks.  _Nature communications_ 11, 1 (2020), 1–9.
  * Allcott and Gentzkow (2017) Hunt Allcott and Matthew Gentzkow. 2017.  Social media and fake news in the 2016 election.  _Journal of economic perspectives_ 31, 2 (2017), 211–36.
  * Boguñá and Pastor-Satorras (2002) Marián Boguñá and Romualdo Pastor-Satorras. 2002.  Epidemic spreading in correlated complex networks.  _Physical Review E_ 66, 4 (2002), 047104.
  * Boguñá et al. (2003) Marián Boguñá, Romualdo Pastor-Satorras, and Alessandro Vespignani. 2003.  Epidemic spreading in complex networks with degree correlations.  In _Statistical mechanics of complex networks_. Springer, 127–147.
  * Cao and Ross (2016) Yang Cao and Sheldon M Ross. 2016.  The friendship paradox.  _Mathematical Scientist_ 41, 1 (2016), 61–64.
  * Durrett (2010) Rick Durrett. 2010\.  _Probability: Theory and Examples_ (4 ed.).  Cambridge University Press.
  * Dwoskin (line) Elizabeth Dwoskin. 2021 [Online].  Misinformation on Facebook got six times more clicks than factual news during the 2020 election, study says.  The Washington Post.  https://www.washingtonpost.com/technology/2021/09/03/facebook-misinformation-nyu-study/
  * Edelman (line) Gilad Edelman. 2021 [Online].  What Social Media Needs to Learn From Traditional Media.  Wired.  https://www.wired.com/story/what-social-media-needs-to-learn-from-traditional-media/
  * Eom and Jo (2015) Young-Ho Eom and Hang-Hyun Jo. 2015.  Tail-scope: Using friends to estimate heavy tails of degree distributions in large-scale complex networks.  _Scientific reports_ 5, 1 (2015), 1–9.
  * Feld (1991) Scott L Feld. 1991\.  Why your friends have more friends than you do.  _American journal of sociology_ 96, 6 (1991), 1464–1477.
  * Garcia-Herranz et al. (2014) Manuel Garcia-Herranz, Esteban Moro, Manuel Cebrian, Nicholas A Christakis, and James H Fowler. 2014.  Using friends as sensors to detect global-scale contagious outbreaks.  _PloS one_ 9, 4 (2014), e92413.
  * Ghaffary (line) Shirin Ghaffary. 2021 [Online].  Why no one really knows how bad Facebook’s vaccine misinformation problem is.  Vox.  https://www.vox.com/22622070/facebook-data-covid-19-vaccine-misinformation-researchers-access-nyu-academics
  * Goldman and Warren (2020) Seth K Goldman and Stephen Warren. 2020.  Debating How to Measure Media Exposure in Surveys.  _The Oxford Handbook of Electoral Persuasion_ (2020).
  * Grinberg et al. (2019) Nir Grinberg, Kenneth Joseph, Lisa Friedland, Briony Swire-Thompson, and David Lazer. 2019\.  Fake news on Twitter during the 2016 US presidential election.  _Science_ 363, 6425 (2019), 374–378.
  * Guess et al. (2020) Andrew M Guess, Brendan Nyhan, and Jason Reifler. 2020\.  Exposure to untrustworthy websites in the 2016 US election.  _Nature human behaviour_ 4, 5 (2020), 472–480.
  * Higham ([n. d.]) Desmond J Higham. [n. d.].  Centrality-friendship paradoxes: when our friends are more important than us.  _Journal of Complex Networks_ ([n. d.]).
  * Lerman et al. (2016) Kristina Lerman, Xiaoran Yan, and Xin-Zeng Wu. 2016.  The” majority illusion” in social networks.  _PloS one_ 11, 2 (2016), e0147617.
  * Leskovec et al. (2008) Jure Leskovec, Lars Backstrom, Ravi Kumar, and Andrew Tomkins. 2008.  Microscopic evolution of social networks. In _Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining_. 462–470.
  * Leskovec et al. (2005) Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. 2005\.  Graphs over time: densification laws, shrinking diameters and possible explanations. In _Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining_. 177–187.
  * Leskovec and Krevl (2014) Jure Leskovec and Andrej Krevl. 2014.  SNAP Datasets: Stanford Large Network Dataset Collection.  http://snap.stanford.edu/data.
  * Nettasinghe and Krishnamurthy (2021a) Buddhika Nettasinghe and Vikram Krishnamurthy. 2021a.  ” What Do Your Friends Think?”: Efficient Polling Methods for Networks Using Friendship Paradox.  _IEEE Transactions on Knowledge and Data Engineering_ 33, 3 (2021), 1291– 1305.
  * Nettasinghe and Krishnamurthy (2021b) Buddhika Nettasinghe and Vikram Krishnamurthy. 2021b.  Maximum Likelihood Estimation of Power-law Degree Distributions via Friendship Paradox-based Sampling.  _ACM Transactions on Knowledge Discovery from Data (TKDD)_ 15, 6 (2021), 1–28.
  * Newman (2002) Mark EJ Newman. 2002\.  Assortative mixing in networks.  _Physical review letters_ 89, 20 (2002), 208701\.
  * Newman (2003) Mark EJ Newman. 2003\.  The structure and function of complex networks.  _SIAM review_ 45, 2 (2003), 167–256.
  * Simpson and Conner (2020) Erin M Simpson and Adam Conner. 2020.  Fighting coronavirus misinformation and disinformation: preventive product recommendations for social media platforms.  (2020).
  * Tang et al. (2008) Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. 2008.  ArnetMiner: Extraction and Mining of Academic Social Networks. In _Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ (Las Vegas, Nevada, USA) _(KDD ’08)_. Association for Computing Machinery, New York, NY, USA, 990–998.  https://doi.org/10.1145/1401890.1402008
  * Tasnim et al. (2020) Samia Tasnim, Md Mahbub Hossain, and Hoimonty Mazumder. 2020\.  Impact of rumors and misinformation on COVID-19 in social media.  _Journal of preventive medicine and public health_ 53, 3 (2020), 171–174.
  * Timberg (line) Craig Timberg. 2021 [Online].  Facebook made big mistake in data it provided to researchers, undermining academic work.  The Washington Post.  https://www.washingtonpost.com/technology/2021/09/10/facebook-error-data-social-scientists/
  * Ugander et al. (2011) Johan Ugander, Brian Karrer, Lars Backstrom, and Cameron Marlow. 2011.  The anatomy of the facebook social graph.  _arXiv preprint arXiv:1111.4503_ (2011).
  * Van Mieghem et al. (2010) Piet Van Mieghem, Huijuan Wang, Xin Ge, Siyu Tang, and Fernando A Kuipers. 2010.  Influence of assortativity and degree-preserving rewiring on the spectra of networks.  _The European Physical Journal B_ 76, 4 (2010), 643–652.

##  Appendix A Proofs of Theorems

###  A.1. Proof of Theorem 1

_Part 1:_ For the vanilla estimate $\hat{f}_{\textrm{Vl}}$, it follows that
$\operatorname*{{\mathbb{E}}}\left\\{\hat{f}_{\textrm{Vl}}\right\\}=\bar{f}$
since it is the average of $n$ iid Bernoulli random variables (with parameter
$\bar{f}$). For the friendship paradox-based estimate $\hat{f}_{\textrm{FP}}$,

$\displaystyle\operatorname*{{\mathbb{E}}}\left\\{\hat{f}_{\textrm{FP}}\right\\}$
$\displaystyle=\operatorname*{{\mathbb{E}}}\left\\{\frac{\bar{k}}{n}\sum_{i=1}^{n}\frac{f(Y_{i})}{d(Y_{i})}\right\\}$
$\displaystyle={\bar{k}}\operatorname*{{\mathbb{E}}}\left\\{\frac{f(Y_{1})}{d(Y_{1})}\right\\}\quad\text{($\because$
$Y_{1},\dots,Y_{n}$ are iid samples.)}$ $\displaystyle=\bar{k}\sum_{v\in
V}\frac{f(v)}{d(v)}\times\frac{d(v)}{\sum_{v\in V}d(v)}\quad\text{($\because$
$\operatorname*{\mathbb{P}}(Y_{1}=v)=\frac{d(v)}{\sum_{v\in V}d(v)}$)}$
$\displaystyle=\bar{k}\sum_{v\in V}\frac{f(v)}{n\bar{k}}=\sum_{v\in
V}\frac{f(v)}{n}=\bar{f}.$

Therefore, both $\hat{f}_{\textrm{Vl}},\hat{f}_{\textrm{FP}}$ are unbiased
estimates of $\bar{f}$.

_Part 2:_ Consider the variance of the vanilla estimate
$\hat{f}_{\textrm{Vl}}$. Since the estimate is the average of $n$ iid
Bernoulli random variables (with parameter $\bar{f}$), their variance is given
by $\bar{f}(1-\bar{f})/n$. For the friendship paradox-based estimate
$\hat{f}_{\textrm{FP}}$,

$\displaystyle\operatorname*{Var}\left\\{\hat{f}_{\textrm{FP}}\right\\}$
$\displaystyle=\operatorname*{Var}\left\\{\frac{\bar{k}}{n}\sum_{i=1}^{n}\frac{f(Y_{i})}{d(Y_{i})}\right\\}$
$\displaystyle=\frac{1}{n}\operatorname*{Var}\left\\{\bar{k}\frac{f(Y_{1})}{d(Y_{1})}\right\\}\quad\text{($\because$
$Y_{1},\dots,Y_{n}$ are iid samples.)}$
$\displaystyle=\frac{1}{n}\left(\operatorname*{{\mathbb{E}}}\left\\{\left(\bar{k}\frac{f(Y_{1})}{d(Y_{1})}\right)^{2}\right\\}-\bar{f}^{2}\right)\quad\text{($\because$
$\operatorname*{{\mathbb{E}}}\left\\{\hat{f}_{\textrm{FP}}\right\\}=\bar{f}$)}$
$\displaystyle=\frac{1}{n}\left(\bar{k}^{2}\sum_{v\in
V}\frac{f^{2}(v)}{d^{2}(v)}\times\frac{d(v)}{\sum_{v\in
V}d(v)}-\bar{f}^{2}\right)$ ($\because$
$\operatorname*{\mathbb{P}}(Y_{1}=v)=\frac{d(v)}{\sum_{v\in V}d(v)}$)
$\displaystyle=\frac{1}{n}\left(\bar{k}^{2}\sum_{v\in
V}\frac{f(v)}{d(v)}\times\frac{1}{n\bar{k}}-\bar{f}^{2}\right)=\frac{1}{n}\left(\bar{k}\operatorname*{{\mathbb{E}}}\left\\{\frac{f(X)}{d(X)}\right\\}-\bar{f}^{2}\right).$

###  A.2. Proof of Theorem 2

Note that $P\left(k^{\prime}|k\right)P_{s}\left(0|k^{\prime}\right)$ is the
probability that a degree $k$ node connects to a degree $k^{\prime}$ node that
hasn’t shared the piece of information. Therefore, averaging this term over
the value $k^{\prime}$
(i.e.,
$\sum_{k^{\prime}}P\left(k^{\prime}|k\right)P_{s}\left(0|k^{\prime}\right)$)
yields the probability that a degree $k$ node having a neighbor that hasn’t
shared the piece of information. For a degree $k$ node to not be exposed to
the information, all $k$ neighbors of that node must not have shared the piece
of information. Hence,
$\left(\sum_{k^{\prime}}P\left(k^{\prime}|k\right)P_{s}\left(0|k^{\prime}\right)\right)^{k}$
is the probability that a node with degree $k$ has not been exposed to the
piece of information i.e.,

(15)
$\operatorname*{\mathbb{P}}\left\\{f(X)=0|d(X)=k\right\\}=\left(\sum_{k^{\prime}}P\left(k^{\prime}|k\right)P_{s}\left(0|k^{\prime}\right)\right)^{k},$

which yields Eq. 9.

Next, using the expressions for the variance in Eq. 6 and the fact that
$\bar{f}=\operatorname*{{\mathbb{E}}}\left\\{f(X)\right\\}$ (where $X$ is a
uniformly sampled node), we get,

$\displaystyle\operatorname*{Var}\\{\hat{f}_{\textrm{Vl}}\\}\geq\operatorname*{Var}\\{\hat{f}_{\textrm{FP}}\\}\iff\frac{1}{n}\left(\bar{k}\operatorname*{{\mathbb{E}}}\left\\{\frac{f(X)}{d(X)}\right\\}-\bar{f}^{2}\right)\geq\frac{1}{n}\bar{f}\left(1-\bar{f}\right)$
$\displaystyle\hskip
5.69046pt\iff\bar{f}-\bar{k}\operatorname*{{\mathbb{E}}}\left\\{\frac{f(X)}{d(X)}\right\\}\geq
0$ $\displaystyle\hskip
5.69046pt\iff\operatorname*{{\mathbb{E}}}\left\\{f(X)\left(1-\frac{\bar{k}}{d(X)}\right)\right\\}\geq
0\quad\text{($\because\operatorname*{{\mathbb{E}}}\left\\{f(X)\right\\}=\bar{f}$
from \lx@cref{creftype~refnum}{eq:bias})}$ $\displaystyle\hskip
5.69046pt\iff\mathbb{E}_{k\sim
P}\left\\{\operatorname*{{\mathbb{E}}}\left\\{f(X)\left(1-\frac{\bar{k}}{d(X)}\right)\bigg{|}d(X)=k\right\\}\right\\}\geq
0$ (by conditioning on $d(X)=k$ and then averaging over $k$)
$\displaystyle\hskip 5.69046pt\iff\mathbb{E}_{k\sim
P}\left\\{\left(1-\frac{\bar{k}}{k}\right)\operatorname*{\mathbb{P}}\left\\{f(X)=1|d(X)=k\right\\}\right\\}\geq
0$

This completes the proof.

##  Appendix B Additional Numerical Results and Details for Reproducibility

The Github repository will be made publicly available for full
reproducibility. Below, we provide additional details related to the
simulation setup used to generate the numerical results in Sec. 6.

_Detailed Simulation setup for comparing the estimators
$\hat{f}_{\textrm{Vl}},\hat{f}_{\textrm{FP}}$ (Fig. 1): _ To generate the
power-law networks, a sequence of $10k$ random variables from a power-law
distribution with the required power-law exponent $\alpha$ were generated and
rounded up to the nearest integer. Then, the first number in the sequence was
altered by a value of $1$ if needed to make sure that the sum of the numbers
is even (to be valid sequence of degrees). Then, the configuration model
(configuration_model function in the networkx package) was used to generate
the networks with the given degree sequence.

To change the assortativity of the generated power-law networks, we first
sample two edges from the network uniformly (without replacement) and rewire
them to increase or decrease the assortativity coefficient $r$ from the
initial value. The Lemma 1 of (Van Mieghem et al., 2010), which orders the
three possible ways to rewire the two selected edges based on the resulting
assortativity coefficient values, is used to get the maximum increase or
decrease in the assortativity coefficient when rewiring. This process is
repeated until the required assortativiy coefficient values
($r\in\\{-0.2,0,0.2\\}$) are reached or the maximum number of iterations
($100k$) is reached.

To change the degree-sharing correlation coefficient $\rho$, we follow the
attribute swapping procedure used in (Lerman et al., 2016) as follows. We
first pick a node $u$ from the set of nodes who shared the piece of
information uniformly (i.e., $s(u)=1$) and another node $v$ from the set of
the people who has not shared the piece of information uniformly (i.e.,
$s(v)=0$). Then, to increase degree-sharing correlation coefficient $\rho$, we
swap $s(v)$ and $s(u)$ if $d(u)<d(v)$ (resp. $d(u)>d(v)$). This process is
continued until the required degree-sharing correlation coefficient values
($\rho\in\\{-0.2,0,0.2\\}$) are reached or the maximum number of iterations
($100k$) is reached.

(a) Assortative network (i.e., assortativity coefficient $r>0$)

(b) Disassortative network (i.e., assortativity coefficient $r<0$)

Figure 5. The performance of the two stochastic approximation algorithms based
on the vanilla and friendship paradox-based estimates (given in Eq. 13 and Eq.
14, respectively) for tracking the exposure to an information cascade under
the Linear Threshold Model (LTM) for a synthetic power-law network with the
power-law exponent $\mathbf{\alpha=2.5}$. This result complements the reult
shown in Fig. 2 for the Independent Cascade Model (ICM). It can be seen that
the conclusions reached under the ICM also hold for the LTM as well. Thus, the
proposed vanilla and friendship paradox-based stochastic approximation
algorithms can be used to track (in real-time) the exposure to information
cascades with various dynamical properties.

_Simulation setup for comparing the vanilla and the friendship paradox-based
stochastic approximations (given in Eq. 13 and Eq. 14): _ Under the ICM used
to generate Fig. 2, each neighbor of a node who shared a piece of information
at a previous time instant shares in the current time instant with a pre-
specified probability named the _infection probability_. For Fig. 2, the
diffusion was initialized with $10$ uniformly chosen nodes and the infection
probability is set to $0.05$. Additionally, the step size $\epsilon$ of the
stochastic approximations Eq. 13, Eq. 14 is set to $0.01$. Further, it is
assumed that the stochastic approximations Eq. 13, Eq. 14 are updated $100$
times for each step of the diffusion process i.e., the samples are collected
$100$ times faster than the evolution of the diffusion process.

Fig. 5 shows analogous results obtained using LTM where, a node shares a piece
of information at the current time instant if the fraction of its neighbors
that have already shared it by the previous time instant exceeds a certain
threshold. We choose the threshold value to be $5\%$ for the Fig. 5. The step-
size of both stochastic approximations Eq. 13, Eq. 14 as well as the number of
samples collected at each time instant are the same as the case for the ICM.

##  Appendix C Practical Implementation Details

When edges cannot be sampled uniformly: The implementation of the friendship
paradox-based estimate $\hat{f}_{\textrm{FP}}$ given in Eq. 4 requires the
uniform sampling of links from the underlying social network to obtain random
friends $Y_{1},Y_{2},\dots,Y_{n}$. This sampling approach is feasible in
situations where links have unique IDs from a range of integers and the link
corresponding to a given integer can be accessed. In settings where such
uniform edge sampling is not possible (e.g., a fully unknown social network),
the friendship paradox-based estimate $\hat{f}_{\textrm{FP}}$ can be
implemented via the use of random walks, since a stationary distribution of a
random walk on an undirected, connected, non-bipartite graph samples nodes
with probabilities proportional to their degrees (page 298, (Durrett, 2010)).
Hence, the random variables $Y_{1},Y_{2},\dots,Y_{n}$ could be replaced with
samples from a sufficiently long random walk. Alternatively, one can also use
a second version of the friendship paradox which states that “uniformly
sampled friend of a uniformly sampled node has more friends than a uniformly
sampled node, on average” (Cao and Ross, 2016). Hence, taking $n$ uniformly
sampled nodes and then taking one random friend of each of them would also be
an alternative approach for friendship paradox-based sampling in undirected
networks.

When the set of sharers is known: The set of sharers $S=\\{v\in V:s(v)=1\\}$
maybe publicly known in some contexts (e.g. Twitter users who shared a
particular hashtag). In such cases, several improvements can be made to the
proposed methods.

First, $S$ is typically an array that can be ordered (e.g., a set of unique
Twitter handles, a set of integer node IDs, etc.). Thus, for each sampled node
$v\in V$, calculating $f(v)\in\\{0,1\\}$ becomes equivalent to the problem of
finding out whether two ordered arrays (the node $v$’s neighbors
$\mathcal{N}(v)$ and the set of sharers $S$) intersect or not. Hence, it is
computationally easier to calculate $f(v)$ when the set of sharers $S\subset
V$ is known.

Second, when $S\subset V$ is known, the average degree of the sharers
$\operatorname*{{\mathbb{E}}}\\{d(X)|s(X)=1\\}=\frac{\sum_{v\in S}d(v)}{|S|}$
(which is typically hard to estimate if the set $S$ is small compared to $V$)
can be calculated. Further, the average degree of the people who have not
shared (i.e., $\operatorname*{{\mathbb{E}}}\\{d(X)|s(X)=0\\}$) can be
estimated by sampling. Then, comparing the two values can be used as a
heuristic estimate of the sign of the degree-sharing correlation coefficient
$\rho$.