## Maximum Likelihood Estimation of Power-law Degree Distributions via Friendship Paradox based Sampling

BUDDHIKA NETTASINGHE and VIKRAM KRISHNAMURTHY, School of Electrical and Computer Engineering, Cornell University

This paper considers the problem of estimating a power-law degree distribution of an undirected network using sampled data. Although power-law degree distributions are ubiquitous in nature, the widely used parametric methods for estimating them (e.g. linear regression on double-logarithmic axes, maximum likelihood estimation with uniformly sampled nodes) suffer from the large variance introduced by the lack of data-points from the tail portion of the power-law degree distribution. As a solution, we present a novel maximum likelihood estimation approach that exploits the friendship paradox to sample more efficiently from the tail of the degree distribution. We analytically show that the proposed method results in a smaller bias, variance and a Cramèr-Rao lower bound compared to the vanilla maximum-likelihood estimate obtained with uniformly sampled nodes (which is the most commonly used method in literature). Detailed numerical and empirical results are presented to illustrate the performance of the proposed method under different conditions and how it compares with alternative methods. We also show that the proposed method and its desirable properties (i.e. smaller bias, variance and Cramèr-Rao lower bound compared to vanilla method based on uniform samples) extend to parametric degree distributions other than the power-law such as exponential degree distributions as well. All the numerical and empirical results are reproducible and the code is publicly available on Github.

CCS Concepts: · Mathematics of computing → Probabilistic inference problems .

Additional Key Words and Phrases: power-law, friendship paradox, degree distribution, networks, maximum likelihood estimation, sampling bias

## 1 INTRODUCTION

Many real-world networks such as social networks [1, 21, 43], internet [25], world-wide web [34] power-grids [12], and biological networks [22, 36] have power-law degree distributions i.e. the probability 𝑝 𝑘 ( ) that a uniformly sampled node has 𝑘 neighbors is proportional to 𝑘 -𝛼 for a fixed value of the power-law exponent 𝛼 &gt; 0. A key reason for this ubiquity is that power-law distributions arise naturally from simple and intuitive generative processes such as preferential attachment [5, 27, 44, 52]. However, despite being ubiquitous in nature, the full structure of such networks is often not precisely known due to practical constraints such as large size, restrictions on accessing network data, etc. [47]. Hence, estimating the power-law exponent 𝛼 from small (compared to size of the network) and noisy samples of data is a key step in the study of networks and related topics such as spreading processes on networks [30, 53, 54] and network stability [17]. This problem is defined formally as follows:

Problem Definition (Estimating the exponent of a power-law degree distribution). Consider an undirected network 𝐺 = ( 𝑉, 𝐸 ) with a power-law degree distribution

$$p ( k ) \in k ^ { - \alpha }, \ \ k \geq k _$$

where the power-law exponent 𝛼 &gt; 0 is unknown. Assume 𝑘 𝑚𝑖𝑛 &gt; 0 is the known minimum degree. Estimate the power-law exponent 𝛼 using the degrees of 𝑛 nodes independently sampled from the network 𝐺 .

Main results and context: The most widely used solutions for the above problem (detailed in Sec. 1.2) are parametric methods based on uniform sampling of nodes from the network 𝐺 and,

Authors' address: Buddhika Nettasinghe, dwn26@cornell.edu; Vikram Krishnamurthy, vikramk@cornell.edu, School of Electrical and Computer Engineering, Cornell University, Frank H.T. Rhodes Hall, Ithaca, New York, 14850.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00310v4-figure-b8e4c2ec-bdec-407e-a1dc-26ebbdcf3a03.jpg)

## Main Conclusions from Statistical, Numerical and Empirical Analysis (Sec. 3, Sec. 4 and Sec. 5)

- · Statistical analysis (Sec. 3) shows that the proposed friendship paradox based maximum likelihood estimate (MLE) / 012 has, i. smaller bias ii. smaller variance iii. smaller Cramèr-Rao Lower Bound (CRLB) compared to the widely used vanilla MLE / 03456774
- · The proposed friendship paradox based MLE / 012 is strongly consistent (i.e. with probability 1 , the estimate / 012(9 : , 9 , … , 9 ; 5 ) converges to the true power-law exponent 0 as the sample size = goes to infinity).
- · Numerical experiments (in Sec. 4) show that the mean-squared error of the friendship paradox based MLE / 012 can be several orders of magnitude smaller (compared to / 03456774 ) and, its variance is approximately equal to the best achievable variance by any unbiased estimate (CRLB) under friendship paradox based sampling.
- · Empirical results (in Sec. 5) using 18 real-world datasets confirm that the conclusions reached from both theoretical and numerical results are valid in real-world settings.

Fig. 1. Summary of the key idea of this paper (maximum likelihood estimation with friendship paradox based sampling for estimating power-law degree distributions), how it compares with the widely used existing method, the conclusions drawn from its statistical and numerical analysis and how these ideas are organized in different sections of the paper. The widely used vanilla method samples nodes uniformly and therefore, fails to efficiently capture the characteristic heavy tail of the power-law degree distribution due to the lack of samples from that regime. In comparison, the proposed method exploits the parametric form of the degree distribution and the friendship paradox based sampling (detailed in Sec. 1.1) to obtain nodes with larger degrees with higher probabilities (indicated by node sizes in the figure) which then leads to a sample containing more high degree nodes that efficiently captures the characteristic heavy tail of the power-law degree distribution. Our results are backed by statistical analysis and detailed numerical simulation experiments and also generalize to parametric forms other than power-law.

tend to produce inaccurate (compared to the method we propose) results as a consequence of the large variance introduced by the heavy tail of the power-law degree distribution. As an alternative, [24] proposed a non-parametric estimation method called tail-scope (detailed in Sec. 1.2) based on a non-uniform sampling method motivated by the concept of the friendship paradox .

Since [24] is the closest idea to ours, let us briefly compare the results in [24] to our results. This friendship paradox based sampling method can be thought of as a more accurate measurement sensor (compared to the vanilla uniform sampling) that reduces the effect of measurement noise introduced by the heavy tail of the power-law degree distribution. However, the non-parametric method proposed in [24] does not exploit the explicit power-law form given in Eq. (1) and also does not provide analytical guarantees for its accuracy (e.g. bias, variance and mean-squared error for a given sample size compared to the widely used methods). Further, it is also not clear how the method proposed in [24] generalizes to degree distributions that take forms other than power-law

(e.g. exponential degree distributions). As a solution we propose an estimator which exploits both the parametric form of power-law given in Eq. (1) and the friendship paradox based sampling method. The proposed method is provably superior to the state of the art in both finite and asymptotic sample regimes and also possesses desirable statistical properties such as asymptotic unbiasedness, consistency and asymptotic normality. Further, the proposed method easily generalizes to other parametric forms of degree distributions that do not necessarily have heavy tails (e.g. exponential degree distributions) while preserving all its desirable statistical properties. More specifically, this paper presents:

- (1) A maximum likelihood estimation method that exploits the concept of friendship paradox for sampling nodes according to a non-uniform distribution.
- (2) Expressions for bias, variance and Cramèr-Rao lower bound of the proposed estimation method and their comparisons with alternative methods that prove how the proposed method outperforms the alternative methods.
- (3) Numerical experiments that illustrate the better performance (in terms of bias, variance mean-squared error) of the proposed method compared to alternative methods under various different conditions.
- (4) Empirical results that verify the conclusions reached from the statistical analysis and numerical experiments using 18 real-world network datasets.
- (5) Generalization of the main results to exponential degree distributions to illustrate how all desirable statistical properties of the proposed method are valid even in non heavy-tailed degree distributions.

An overview of the key ideas of this paper along with their organization in different sections is shown in Fig. 1 and is also outlined below in detail.

Organization: Sec. 1.1 reviews the friendship paradox and Sec. 1.2 discusses related literature. Sec. 2 presents our main idea of maximum likelihood estimation that exploits the friendship paradox based sampling. Sec. 3 presents the statistical analysis of the proposed estimate and compares it with widely used alternative methods. Sec. 4 presents detailed numerical experiments that support and complement the statistical analysis. Sec. 5 presents empirical results that compare the proposed method with alternative methods using several real-world datasets. Finally, Appendix D shows how the main results extend to other types of degree distributions and, Appendix E provides additional details on the numerical and empirical results. The code is publicly available on the Github repository [48] to ensure that all results in the paper are completely reproducible.

## 1.1 Friendship Paradox

The 'friendship paradox" is a form of observation bias first presented in [26] by Scott L. Feld in 1991. The friendship paradox states, ' on average, the number of friends of a random friend is always greater than the number of friends of a random individual ". Formally:

Theorem 1. (Friendship Paradox [26]) Consider an undirected graph 𝐺 = ( 𝑉, 𝐸 ) . Let 𝑋 be a node sampled uniformly from 𝑉 and, 𝑌 be a uniformly sampled end-node from a uniformly sampled edge 𝑒 ∈ 𝐸 . Then,

$$\mathbb { E } \{ d ( Y ) \} \geq \mathbb { E$$

where, 𝑑 𝑋 ( ) and 𝑑 𝑌 ( ) denote the degrees of 𝑋 and 𝑌 , respectively.

In Theorem 1, the random variable 𝑌 depicts a random friend (or a random neighbor) since it is obtained by sampling a pair of friends (i.e. an edge from the graph) uniformly and then choosing one of them via an unbiased coin flip. Equivalently, a random friend 𝑌 is a node sampled from 𝑉 with a probability proportional to its degree. Further, the degree distribution 𝑞 of a random friend 𝑌

is given by

𝑞 𝑘 ( ) ∝ 𝑘𝑝 𝑘 , ( )

where, 𝑝 is the degree distribution defined in Eq. (1). Eq. (3) follows from the fact that each node with a degree 𝑘 appears as a friend of 𝑘 other individuals. Note from Eq. (3) that the degree distribution 𝑞 of random friend 𝑌 is a right-skewed version of the degree distribution 𝑝 and thus resulting in the friendship paradox in Theorem 1.

The intuition behind Theorem 1 is as follows. Individuals with large numbers of friends (high degree) appear as the friends of a large number of individuals. Hence, such popular individuals can contribute to an increase in the average number of friends of friends. On the other hand, individuals with small numbers of friends (low degree) appear as friends of a smaller number of individuals. Hence, they cannot cause a significant change in the average number of friends of friends. This asymmetric contribution of high and low degree individuals to the average number of friends of friends causes the friendship paradox. Further, [10] shows that the original version of the friendship paradox (Theorem 1) is a consequence of the monotone likelihood ratio stochastic ordering between random variables 𝑑 𝑌 ( ) and 𝑑 𝑋 ( ) .

## 1.2 Motivation and Related Work

Widely used methods for estimating the power-law exponent 𝛼 include:

- (1) Linear regression: Using the empirical degree distribution ˆ on double-logarithmic axes (i.e. ln ˆ 𝑝 𝑝 𝑘 ( ) with ln 𝑘 where ˆ is the empirical distribution of degrees of 𝑝 𝑛 uniformly sampled nodes), fit a straight line (using least squares) whose slope is the estimate of 𝛼 . The idea of this method is that ln 𝑝 𝑘 ( ) varies linearly with ln 𝑘 with a slope of -𝛼 according to Eq. (1).
- (2) Maximumlikelihood estimation with uniformly sampled nodes: Sample a set of nodes 𝑋 , 𝑋 , . . . 𝑋 1 2 𝑛 independently and uniformly and, compute ˆ vl which maximizes the likelihood of observing 𝛼 the degree sequence 𝑑 𝑋 ( 1 ) , 𝑑 ( 𝑋 2 ) , . . . , 𝑑 ( 𝑋 𝑛 ) .

Previous works [7, 29] show that linear regression (as well as its variants) for estimating the power-law exponent 𝛼 yields inaccurate results (compared to maximum likelihood estimation method) due to two main reasons. First, the lack of data points from the tail of the power-law degree distribution 𝑝 (to construct the empirical degree distribution ˆ) systematically underestimates the 𝑝 power-law exponent 𝛼 . Second, the log-log transformation of the empirical degree distribution violates several assumptions (such as constant variance across all data points and zero-mean Gaussian noise) that are required to make the least squares estimate unbiased and statistically efficient (see [15] for a detailed survey of these systematic inaccuracies in using linear regression method to estimate 𝛼 ). Therefore, the linear regression method for estimating power-laws is not well-justified from a statistical viewpoint. In comparison, maximum likelihood estimation with uniformly sampled nodes is a more principled approach which has been shown to achieve a better accuracy in estimating the power-law exponent 𝛼 [15, 57]. Maximum likelihood estimates also possess several appealing statistical properties including consistency, asymptotic unbiasedness and asymptotic efficiency. Hence, maximum likelihood estimation with uniformly sampled nodes is currently regarded as the state of the art method for estimating power-law degree distributions, and we use it as the main benchmark for evaluating the performance of the method proposed in this paper.

Use of friendship paradox in estimation problems: The friendship paradox has been used in several applications related to networks under the broad theme 'how network biases can be exploited effectively in estimation problems?" . For example, [14, 28] show how the friendship paradox can be used for quickly detecting a disease outbreak, [49] proposes polling algorithms that exploits the friendship paradox for efficiently estimating the fraction of individuals with a certain

attribute (e.g. intending to vote for a certain political party) in a social network. Apart from these, [2, 4, 13, 23, 32, 33, 35, 37, 39-41, 45, 50] also explore further generalizations (to directed graphs, attributes other than degree, etc.) and applications (influence maximization etc.) of friendship paradox.

More closely related to our work, [24] presents a method named tail-scope which utilizes the friendship paradox for non-parametric estimation of heavy-tailed degree distributions. Tail-scope first obtains an empirical estimate ˆ of the neighbor degree distribution 𝑞 𝑞 (defined in Eq. (3)) by sampling random neighbors (denoted by random variable 𝑌 in Theorem 1). Then, following Eq. (3), the empirical neighbor degree distribution ˆ 𝑞 𝑘 ( ) scaled by 𝑘 is used as the estimate of the degree distribution 𝑝 𝑘 ( ) i.e.

$$\hat { p } _ { \text{tail-scope} } ( k ) \in \frac$$

The rationale behind tail-scope is that the empirical neighbor degree distribution ˆ will include more 𝑞 high degree nodes (due to the friendship paradox) and hence, the scaled estimate ˆ tail-scope 𝑝 will capture the tail of the degree distribution better compared to the empirical degree distribution ˆ (which 𝑝 is obtained with uniformly sampled nodes). While the method we propose is motivated in part by tail-scope, there are several key differences between tail-scope method and our method. Firstly, the method proposed in this paper is a parametric method that makes use of the specific power-law form in Eq. (1) whereas tail-scope is a non-parametric method for general heavy-tailed degree distributions. Secondly, the method we propose has a provably better accuracy compared to the state of the art method (maximum likelihood estimation with uniformly sampled nodes) and it also possesses desirable statistical properties including strong consistency, asymptotic unbiasedness and asymptotic statistical efficiency whereas such analytical guarantees are not available for tail-scope method. Finally, as we show in Appendix D, the proposed parametric method easily generalizes to other parametric forms of degree distributions (e.g. exponential distribution) as well, while preserving the performance guarantees (compared to the vanilla method based on uniformly sampled nodes) that it offers. Further, there have been several other works (e.g. [55, 56]) which also suggest that edge sampling based methods (such as random walk methods) can offer better accuracy (compared to uniform sampling) in non-parametric estimation tasks by obtaining more samples from the tail of the degree distribution.

In summary, it has been shown in the literature [7, 15, 29] that maximum likelihood methods are more suitable for estimating power-law degree distributions of the form in Eq. (1) compared to alternative methods. Further, exploiting the friendship paradox (Theorem 1) has shown to be effective in empirical estimation of heavy-tailed degree distributions by including more high degree nodes into the sample [24]. Motivated by these findings, this paper combines maximum likelihood estimation with friendship paradox based sampling in a principled manner to obtain an asymptotically unbiased, strongly consistent and statistically efficient estimate that provably outperforms the state of the art.

## 2 MAXIMUM LIKELIHOOD ESTIMATION OF POWER-LAW EXPONENT

This section introduces two different network sampling methods (uniform sampling and friendship paradox based sampling); we then compare the maximum likelihood estimate of the power-law exponent 𝛼 for these two sampling methods. The statistical analysis (presented in Sec. 3) of the maximum likelihood estimates (MLEs) for the two sampling methods illustrates how the MLE obtained with friendship paradox based sampling (proposed method) outperforms the MLE obtained with uniform sampling (classically used method).

We first state the key assumptions used in deriving and analyzing the MLEs.

Assumption 1. The power-law distribution 𝑝 is continuous in 𝑘 and is of the form,

$$\begin{array} {$$

where, 𝑘 min is the minimum degree.

Assumption 2. The power-law exponent 𝛼 is greater than 2 i.e. 𝛼 &gt; 2 .

Assumption 1 allows us to derive closed-form expressions for MLEs for the power-law exponent 𝛼 . A similar assumption (on continuity) has been used in [24] that deals with estimating heavy-tailed degree distributions. Further, Assumption 1 is naturally applicable for weighted networks where the weighted degree (also called node strength) follows a continuous power-law distribution [3, 6]. For discrete power-law distributions, MLEs are not available in closed-form [15]. Thus, Assumption 1 is useful in our theoretical analysis. In Sec. 2.3, we also briefly discuss how the MLEs for discrete power-law distributions can be approximated using closed-form expressions.

All moments 𝑚 ≥ 𝛼 -1 diverge for the power-law distribution given in Eq. (5). Hence, both mean and variance diverge when 𝛼 ≤ 2 and variance diverges (and mean is finite) when 2 &lt; 𝛼 ≤ 3. Therefore, Assumption 2 ensures that the degree distribution 𝑝 in Eq. (5) has a finite mean which is necessary for the derivation of the proposed friendship paradox based MLE in Sec. 2.2.

## 2.1 Vanilla MLE with uniform sampling

In the classical vanilla maximum likelihood estimation method [15, 29], 𝑛 number of nodes 𝑋 , 𝑋 , . . . , 𝑋 1 2 𝑛 are independently and uniformly sampled from the network. Then, the likelihood of observing the degree sequence 𝑑 𝑋 ( 1 ) , 𝑑 ( 𝑋 2 ) , . . . , 𝑑 ( 𝑋 𝑛 ) is,

$$\mathbb { P } \{ d ( X _ { 1 } ), \dots, d$$

following Eq. (5). Therefore, the log-likelihood for the vanilla method is,

$$\mathcal { L } _ { \nu 1 } ( \alpha ) = \ln \mathbb { P } \{ d ( X _ { 1 } ), d ( X _ { 2 } ), \dots, d ( X _ { n } ) | \alpha \}$$

$$= n \ln ( \alpha - 1 ) - n \ln ( k _ { \min } ) - \alpha \sum _ { i = 1 } ^ { n } \ln \left ( \frac { d ( X _ { i } ) } { k _ { \min } } \right ).$$

Then, by solving 𝜕 L vl 𝜕𝛼 = 0, we get the vanilla MLE of the power-law exponent 𝛼 as,

$$\hat { \alpha } _ { v 1 } = \frac { n } { \sum _ { i = 1 } ^ { n } \ln \left ( \frac { d ( X _ { i } ) } { k _ { \min } } \right ) } + 1.$$

Next, we present a maximum likelihood estimator that exploits the friendship paradox.

## 2.2 MLE with friendship paradox based sampling

Neighbor Degree Distribution: Recall from Sec. 1.1 that 𝑌 denotes a random neighbor i.e. uniformly sampled end-node of a uniformly sampled edge. The neighbor degree distribution 𝑞 𝑘 ( ) is proportional to 𝑘𝑝 𝑘 ( ) as stated in Eq. (3). Hence, the normalizing constant 𝐶 𝑞 of the neighbor degree distribution 𝑞 can be derived as,

$$\stackrel { \mu } { C } _ { q } = \int _ { k _ { \min } } ^ { \infty } k p ( k ) d k = \int _ { k _ { \min } } ^ { \infty } k \frac { \alpha - 1 } { k _ { \min } } \left ( \frac { k } { k _ { \min } } \right ) ^ { - \alpha } d k = \frac { \alpha - 1 } { \alpha - 2 } k _ { \min }$$

where, 𝑝 𝑘 ( ) is the power-law degree distribution defined in Eq. (5) that is continuous in degree 𝑘 by Assumption 1. Note that the normalizing constant of the distribution 𝑞 is equal to the first

moment (i.e. mean) of the power-law degree distribution 𝑝 (defined in Eq. (5)) and, is guaranteed to exist by Assumption 2. Then, it follows that,

$$q ( k ) = \frac { 1 } { C _ { q } } k p ( k ) = \frac { \alpha - 2 } { k _ { \min } } \left ( \frac { k } { k _ { \min } } \right ) ^ { - ( \alpha - 1 ) }, \quad k \geq k _ { \min }.$$

Friendship Paradox based MLE: . The friendship paradox based maximum likelihood estimator begins with sampling 𝑛 number of random neighbors 𝑌 , 𝑌 , . . . , 𝑌 1 2 𝑛 from the network independently. Then, the likelihood of observing the neighbor degree sequence 𝑑 𝑌 ( 1 ) , 𝑑 ( 𝑌 2 ) , . . . , 𝑑 ( 𝑌 𝑛 ) can be written using the neighbor degree distribution in Eq. (9) as,

$$\mathbb { P } \{ d ( Y _ { 1 } ), \dots, d ( Y _ { n } ) | \alpha \} = \prod _ { i = 1 } ^ { n } \frac { \alpha - 2 } { k _ { \min } } \left ( \frac { d ( Y _ { i } ) } { k _ { \min } } \right ) ^ { - ( \alpha - 1 ) }.$$

Therefore, the log-likelihood for the friendship paradox based sampling method is,

$$\mathcal { L } _ { \text{fp} } ( \alpha ) = \ln \mathbb { P } \{ d ( Y _ { 1 } ), d ( Y _ { 2 } ), \dots, d ( Y _ { n } ) | \alpha \}$$

$$= n \ln ( \alpha - 2 ) - n \ln ( k _ { \min } ) - ( \alpha - 1 ) \sum _ { i = 1 } ^ { n } \ln \left ( \frac { d ( Y _ { i } ) } { k _ { \min } } \right ).$$

Then, by solving 𝜕 L fp 𝜕𝛼 = 0, we get the friendship paradox based MLE of the power-law exponent 𝛼 as,

$$\hat { \alpha } _ { \text{fp} } & = \frac { n } { \sum _ { i = 1 } ^ { n } \ln \left ( \frac { d ( Y _ { i } ) } { k _ { \min } } \right ) } + 2.$$

Remark 1 (Power-law form of the neighbor degree distribution). Note that the neighbor degree distribution 𝑞 𝑘 ( ) (given in Eq. (9)) is also a power-law degree distribution. More specifically, the neighbor degree distribution 𝑞 𝑘 ( ) can be obtained from the power-law degree distribution 𝑝 𝑘 ( ) (given in Eq. (5)) by simply replacing the power-law exponent 𝛼 with 𝛼 -1. Thus, the neighbor degree-distribution 𝑞 𝑘 ( ) is also a power-law but, with a heavier tail (i.e. a smaller power-law exponent) compared to the degree distribution 𝑝 𝑘 ( ) . This is due to the fact that 𝑞 𝑘 ( ) ∝ 𝑘𝑝 𝑘 ( ) where the scaling term 𝑘 reduces the power-law exponent of 𝑝 𝑘 ( ) by a value of 1.

Remark 2 (Alternative implementations). Recall (from Sec. 1.1) that a random neighbor 𝑌 is a uniformly sampled end node of a uniformly sampled edge 𝑒 ∈ 𝐸 . In applications such as online social networks, uniform link sampling (and therefore, sampling random neighbors) is possible since each edge has a unique integer ID assigned from a specific range of integers [42]. In applications where sampling uniform edges is not possible (e.g. unknown network, lack of edge IDs), one possible method to sample random neighbors (to implement the friendship paradox based MLE in Eq. (11)) is by using random walks. Assuming the underlying network 𝐺 = ( 𝑉, 𝐸 ) is a connected, non-bipartite graph, the stationary distribution of a random walk on 𝐺 samples each node 𝑣 ∈ 𝑉 with a probability proportional to the degree 𝑑 𝑣 ( ) of node 𝑣 (page 298, [20]) i.e. the stationary distribution of a random walk on a connected, non-bipartite graph samples random neighbors. Hence, a node sampled from a sufficiently long random walk has approximately the same distribution as a random neighbor 𝑌 . Another possibility is to use a second version of the friendship paradox which states 'uniformly sampled friend of a uniformly sampled node has more friends than a uniformly sampled node, on average' (see [10, 13] for more details on this second version). This second version does not require sampling links and, is equivalent to a one step random walk.

## 2.3 Approximating the maximum likelihood estimates for discrete data

In Sec. 2.1 and Sec. 2.2, we derived the MLEs for the power-law exponent 𝛼 assuming that the observations are from a continuous power-law distribution (Assumption 1). However, network degree distributions are discrete distributions for which a closed-form MLE for the power-law exponent is not available (as discussed at the beginning of Sec. 2). Therefore, the maximum likelihood estimates of the power-law exponent for such discrete distributions have to be obtained by numerical methods. Two solutions are available to overcome the lack of a closed-form expression for the MLE of the power-law exponent of a discrete power-law degree distribution.

The first solution is to simply apply the expressions derived under the Assumption 1 (in Sec. 2.1 and Sec. 2.2) to the discrete case i.e. pretending that the discrete data is from a continuous distribution for the estimation purpose. The second solution is to use an approximate closed-form solution for the power-law exponent of a discrete power-law distribution as proposed in [15]. The approximate MLE of the power-law exponent 𝛼 for the discrete case under the vanilla uniform sampling is:

$$\hat { \alpha } _ { v l \text{-d} } = \frac { n } { \sum _ { i = 1 } ^ { n } \ln \left ( \frac { d ( X _ { i } ) } { k _ { \min } = 0. 5 } \right ) } + 1$$

where, 𝑋 , 𝑋 , . . . , 𝑋 1 2 𝑛 are independently and uniformly sampled nodes [15]. Since the neighbor degree distribution 𝑞 of a network with a power-law degree distribution is also a power-law (as stated in Remark 1), the approximate MLE of the power-law exponent 𝛼 for the discrete case under the friendship paradox based sampling is:

$$\hat { \alpha } _ { \text{fp-d} } = \frac { n } { \sum _ { i = 1 } ^ { n } \ln \left ( \frac { d ( Y _ { i } ) } { k _ { \min } - 0. 5 } \right ) } + 2$$

where, 𝑌 , 𝑌 , . . . , 𝑌 1 2 𝑛 are independently sampled random neighbors. Henceforth, we refer to ˆ vl-d (in 𝛼 Eq. (12)) and ˆ fp-d 𝛼 (in Eq. (13)) as vanilla discrete MLE and friendship paradox based discrete MLE, respectively.

In Sec. 4 and Sec. 5, we will explore the performance vanilla discrete MLE ˆ vl-d 𝛼 and friendship paradox based discrete MLE ˆ fp-d in terms of bias, variance and mean-squared error using synthetic 𝛼 and real-world network datasets. Further, we will also compare their performance with the MLEs in Eq. (7) and Eq. (11) that were derived assuming a continuous power-law distribution.

## 3 STATISTICAL ANALYSIS OF THE ESTIMATES

This section presents the statistical analysis of the two estimates: vanilla MLE ˆ vl 𝛼 in Eq. (7) (which uses uniform sampling of nodes) and the friendship paradox based MLE ˆ fp 𝛼 in Eq. (11) (which samples nodes non-uniformly according to the friendship paradox). The statistical analysis below shows that the proposed friendship paradox based MLE ˆ fp outperforms the widely used vanilla 𝛼 MLE ˆvl in terms of bias, variance and Cramèr-Rao Lower Bound. 𝛼

Comparison of bias and variance of MLEs for finite sample size: The following result from [46] (also discussed in [15] in a broader context) characterizes the bias and variance of the vanilla MLE ˆ vl 𝛼 under finite sample sizes 𝑛 &lt; ∞ .

Theorem 2 (Bias and variance of the vanilla MLE [15, 46]). The bias and variance of the vanilla MLE ˆ 𝛼 vl in Eq. (7) for sample size 𝑛 are given by,

$$\dots - \gamma \cdot \sqrt { \, \sum \, J \cdot \cdot } \, \text{succeeded} \, \gamma \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \colon \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \, \gamma \,, \\ \text{Bias} \{ \hat { \alpha } _ { \nu l } \} & = \frac { \alpha - 1 } { n - 1 }, \quad \text{for $n > 1$} \\ \text{Var} \{ \hat { \alpha } _ { \nu l } \} & = \frac { n ^ { 2 } ( \alpha - 1 ) ^ { 2 } } { ( n - 1 ) ^ { 2 } ( n - 2 ) }, \quad \text{for $n > 2$}.$$

Fig. 2. Theoretical mean-squared error (MSE) values of the vanilla estimate ˆ 𝛼 vl and the friendship paradox based estimate ˆ 𝛼 fp (Fig. 2a) and their ratios (Fig. 2b) calculated analytically using Eq. (14) and Eq. (15) for sample size 𝑛 = 100 . The plots show that, theoretically, the proposed friendship paradox based estimate ˆ 𝛼 fp has a MSE which is smaller than the widely used vanilla MLE ˆ 𝛼 vl . The ratio between the MSEs increases as 𝛼 approaches 2 .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00310v4-figure-371955dd-705c-4cec-ae01-251d170e1b41.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00310v4-figure-229286b3-2ed8-4490-9f06-cff5b931501c.jpg)

The bias and variance of the proposed friendship paradox based MLE ˆ fp under a finite sample 𝛼 size 𝑛 &lt; ∞ are characterized in the following result, allowing it to be compared with the vanilla MLE ˆvl . 𝛼

Theorem 3 (Bias and variance of the friendship paradox based MLE). The bias and variance of the friendship paradox based MLE ˆ 𝛼 fp in Eq. (11) for sample size 𝑛 are given by,

$$r ^ { \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \ dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots$$

Proof. Recall from Remark 1 that the neighbor degree distribution 𝑞 𝑘 ( ) is also a power-law distribution with power-law exponent 𝛼 -1. Thus, Theorem 3 can be obtained by replacing 𝛼 in Theorem 2 with 𝛼 -1. The formal full proof is provided in Appendix A. □

The following immediate consequence of Theorem 2 and Theorem 3 shows that the proposed friendship paradox based MLE ˆ fp outperforms vanilla MLE ˆ vl for any finite sample size 𝛼 𝛼 𝑛 .

Corollary 4. The bias and variance of the vanilla MLE ˆ 𝛼 vl defined in Eq. (7) and the friendship paradox based MLE ˆ 𝛼 fp defined in Eq. (11) satisfy,

$$\text{Bias} & \{ \hat { \alpha } _ { f p } \} < \text{Bias} & \{ \hat { \alpha } _ { v l } \}, \quad \text{for $n>1$} \\ \text{Var} & \{ \hat { \alpha } _ { f p } \} < \text{Var} & \{ \hat { \alpha } _ { v l } \}, \quad \text{for $n>2$}.$$

From Corollary 4, it immediately follows that the mean-squared error (MSE) of the proposed friendship paradox based MLE ˆ fp is also smaller compared to the MSE of the vanilla MLE ˆ vl . Fig. 2 𝛼 𝛼 illustrates the MSE values of the two estimates calculated using Eq. (14) and Eq. (15) and the ratio between them for 𝑛 = 100. It can be seen that the the ratio between the MSEs of the two methods grows rapidly to several orders of magnitude as the power-law exponent 𝛼 becomes smaller since both bias and variance of the friendship paradox based MLE ˆ fp 𝛼 approaches 0 as 𝛼 goes to 2.

Having established that the proposed friendship paradox based MLE ˆ fp 𝛼 outperforms the vanilla MLE ˆfp for all sample sizes 𝛼 𝑛 &lt; ∞ , we now turn to the case where the sample size 𝑛 tends to infinity.

Comparison of the asymptotic properties of the MLEs: Based on Eq. (14), Eq. (15) and the strong law of large numbers, we have the following result:

Theorem 5 (Asymptotic unbiasedness and strong consistency of MLEs). The vanilla MLE ˆ 𝛼 vl (defined in Eq. (7) ) and the friendship paradox based MLE ˆ 𝛼 fp (defined in Eq. (11) ) are asymptotically unbiased and strongly consistent i.e. converge to the true power-law exponent 𝛼 with probability 1 as the sample size 𝑛 tends to infinity.

## Proof. See Appendix B.

□

In order to analytically compare the two MLEs in the asymptotic regime, we use the Cramèr-Rao Lower Bound (CRLB). For a scalar random variable (which is the case we deal with), CRLB simplifies to the reciprocal of the Fisher Information [11]. We stress that the CRLB is important because the variance of any unbiased estimate (or asymptotically unbiased estimate) is bounded below by the CRLB i.e. CRLB is the smallest variance achievable by any unbiased estimate. The following result characterizes the two Cramèr-Rao Lower Bounds, CRLBvl and CRLBfp , of the two estimates ˆ vl 𝛼 and ˆ fp . 𝛼

Theorem 6. The Cramèr-Rao Lower Bounds of the vanilla MLE ˆ 𝛼 vl in Eq. (7) and the friendship paradox based MLE ˆ 𝛼 fp in Eq. (11) are given by,

$$C R L B _ { v l } ( \alpha ) = \frac { ( \alpha - 1 ) ^ { 2 } } { n }, \quad C R L B _ { f p } ( \alpha ) = \frac { ( \alpha - 2 ) ^ { 2 } } { n }.$$

Proof. See Appendix C.

□

Since maximum likelihood estimates are asymptotically normal and efficient (achieves the CRLB), it follows that,

$$\sqrt { n } ( \hat { \alpha } _ { \text{v1} } - \alpha ) & \xrightarrow { d } \mathcal { N } ( 0, ( \alpha - 1 ) ^ { 2 } ) \\ \sqrt { n } ( \hat { \alpha } _ { \text{fp} } - \alpha ) & \xrightarrow { d } \mathcal { N } ( 0, ( \alpha - 2 ) ^ { 2 } ).$$

Hence, it can be seen that the asymptotic variance of √ 𝑛 𝛼 ( ˆ fp -𝛼 ) is smaller than that of √ 𝑛 𝛼 ( ˆ vl -𝛼 ) , implying that the proposed friendship paradox based MLE ˆ fp outperforms the vanilla MLE 𝛼 ˆ vl 𝛼 for large samples sizes.

Remark 3 (Exponential degree distributions). Apart from the power-law degree distribution, several real world networks (e.g. Worldwide Marine Transportation Network [58]) have exponential degree distributions i.e. probability 𝑝 𝑒𝑥𝑝 ( 𝑘 ) that a uniformly sampled node has 𝑘 neighbors is proportional to 𝑒 -𝜆𝑘 where 𝜆 &gt; 0 is the fixed rate parameter [19]. The results in Sec. 2 and Sec. 3 also extend to the case where the underlying network has an exponential degree distribution as shown in Appendix D. This result is important in that it shows that the proposed friendship paradox based maximum likelihood estimation method outperforms the vanilla method (based on uniform sampling) in the setting of light-tailed degree distributions as well.

SummaryofStatistical Analysis: Thestatistical analysis motivates the use of the proposed friendship paradox based MLE ˆ fp (defined in Eq. (11)) in place of the widely used vanilla MLE ˆ vl (defined 𝛼 𝛼 in Eq. (7)) for estimating power-law degree distributions. Theorems 2, 3 characterize the bias and

variance of the two estimates ˆ vl 𝛼 , 𝛼 ˆ fp and, Corollary 4 concludes that the proposed method has a smaller bias and a smaller variance under finite sample size 𝑛 &lt; ∞ . Then, Theorem 6 gives the Cramèr-Rao bounds for the two estimates ˆ vl 𝛼 , 𝛼 ˆ fp to show that the proposed MLE ˆ fp outperforms 𝛼 the vanilla MLE ˆ vl 𝛼 in the asymptotic regime and, possesses properties such as asymptotic unbiasedness, consistency and asymptotic normality. Thus, the statistical analysis concludes that the proposed friendship paradox based MLE ˆ fp outperforms the widely used vanilla MLE ˆ vl in both 𝛼 𝛼 finite and asymptotic regimes.

## 4 NUMERICAL COMPARISON OF THE PERFORMANCE OF THE ESTIMATES

This section presents detailed numerical examples that complement the statistical analysis in Sec. 3. More specifically, we:

- i. compare the four estimates of the power-law exponent 𝛼 (presented in Sec. 2): vanilla maximum likelihood estimate (MLE) ˆ vl 𝛼 (widely used method) given in Eq. (7), friendship paradox based MLE ˆfp (proposed method) given in Eq. (11) and their discrete versions 𝛼 ˆ vl-d 𝛼 , 𝛼 ˆ fp-d given in Eq. (12) and Eq. (13) respectively, in terms of empirically estimated bias, variance, MSE and the theoretical CRLB values
- ii. numerically evaluate the effect of the sample size 𝑛 on the performance of the friendship paradox based methods ( ˆ fp 𝛼 , 𝛼 ˆ fp-d ) in comparison to the widely used vanilla methods based on uniform sampling ( ˆ vl 𝛼 , 𝛼 ˆ vl-d ).

Simulation Setup: We use the configuration model [51] to generate networks with 50000 nodes that have degree sequences sampled from a power-law distribution with a given power-law exponent 𝛼 and a minimum degree 𝑘 min . Then, the bias, variance and MSE of the estimates (for power-law exponent 𝛼 in the interval [ 2 1 . , 3 5 . ] and minimum degree 𝑘 min = 1 , 5 , 50 , 500) are empirically estimated using a Monte-Carlo simulation over 5000 independent iterations. Additional details on the simulation setup are provided in the Appendix E and all the simulation codes are publicly available in the Github repository [48].

Numerical Comparison of bias, variance and mean-squared error: Fig. 3 shows the empirically estimated bias, variance, MSE and the CRLB values of the four estimates of the power-law exponent 𝛼 presented in Sec. 2: vanilla MLE ˆ vl 𝛼 (widely used method) given in Eq. (7), friendship paradox based MLE ˆfp (proposed method) given in Eq. (11) and their discrete versions 𝛼 ˆ vl-d 𝛼 , 𝛼 ˆ fp-d given in Eq. (12) and Eq. (13) respectively, for sample size 𝑛 = 100. Several important observations that complement the statistical analysis in Sec. 3 can be drawn from Fig. 3.

First, the MSE (shown in the 3 rd column of Fig. 3) of the friendship paradox based MLE ˆ fp 𝛼 (indicated in yellow) and its discrete version ˆ fp-d 𝛼 (indicated in red) are smaller compared to the widely used methods that are based on uniform sampling (i.e. vanilla MLE ˆ vl and its discrete version 𝛼 ˆ vl-d 𝛼 ). Further, the friendship paradox based MLE ˆ fp 𝛼 (indicated in yellow) has a slightly smaller MSE compared to its discrete version ˆ fp-d 𝛼 (indicated in red), especially for smaller minimum degree values (i.e. 𝑘 min ≤ 5) and larger power-law exponent values (i.e. 𝛼 &gt; 3). Thus, the numerical results suggest that the friendship paradox based MLEs ˆ fp 𝛼 , 𝛼 ˆ fp-d produce smaller overall errors (i.e. MSE values) compared to the currently used methods that are based on uniform sampling ˆ vl 𝛼 , 𝛼 ˆ vl-d and, verify the conclusions reached by the statistical analysis in Sec. 3.

Second, note that the empirical variance (shown in the 2 nd column of Fig. 3) of the proposed friendship paradox based MLE ˆ fp (indicated in yellow) and its discrete version 𝛼 ˆ fp-d 𝛼 (indicated in red) are smaller compared to the vanilla MLEs based on uniform sampling (i.e. vanilla MLE ˆ vl 𝛼 and its discrete version ˆ vl-d 𝛼 ). Importantly, it can be observed that the variance of the proposed

Fig. 3. Empirical bias, variance, mean-squared error (MSE) and theoretical Cramèr-Rao lower bound (CRLB) values of the four estimates (presented in Sec. 2): vanilla maximum likelihood estimate (MLE) ˆ 𝛼 vl given in Eq. (7) , friendship paradox based MLE ˆ 𝛼 fp given in Eq. (11) and their discrete versions ˆ 𝛼 vl-d , 𝛼 ˆ fp-d given in Eq. (12) and Eq. (13) respectively, for sample size 𝑛 = 100 . The plots show that the proposed friendship paradox based MLEs ˆ 𝛼 fp , 𝛼 ˆ fp-d outperform the vanilla MLEs ˆ 𝛼 vl , 𝛼 ˆ vl-d in terms of MSE for all considered values of power-law exponent 𝛼 and minimum-degree 𝑘 min . Further, the variance of the friendship paradox based MLEs are approximately equal to the best achievable variance (CRLB) under the friendship paradox based sampling and they also induce a smaller bias compared to the vanilla methods. Thus, the figure suggests that the friendship paradox based MLEs yield better results compared to the widely used vanilla methods based on uniform sampling for estimating power-law degree distributions.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00310v4-figure-aeb210fe-e690-4d41-a60b-4ec9eb7a554c.jpg)

friendship paradox based MLE ˆ fp is approximately equal to the theoretical CRLB value (CRLB fp 𝛼 blue dotted line) for all considered values of minimum degree 𝑘 min and power-law exponent 𝛼 . This observation indicates that the variance of the proposed friendship paradox based MLE ˆ fp 𝛼 is almost equal to the best achievable variance under the friendship paradox based sampling (since CRLB is the smallest achievable variance by any unbiased estimate of a parameter for a given sampling method as discussed in Sec. 3). In comparison, variance of the vanilla MLE ˆ vl 𝛼 achieves the CRLB (CRLBvl - blued dashed line) only for larger minimum degree values ( 𝑘 min &gt; 5) and, is still larger compared to the friendship paradox based MLE ˆ fp 𝛼 . In both vanilla and friendship paradox based cases, the discrete MLEs ˆ vl-d 𝛼 , 𝛼 ˆ fp-d reduce the variance for smaller minimum degree values ( 𝑘 min &lt; 5) while still maintaining the trend that friendship paradox based discrete MLE has a smaller variance compared to the vanilla discrete MLE (i.e. Var { ˆ fp-d 𝛼 } &lt; Var { ˆ vl-d 𝛼 } ). Thus, the numerical comparison of the estimates based on variance also suggests that the friendship paradox based MLE ˆfp and its discrete version 𝛼 ˆ fp-d 𝛼 are better compared to the currently used methods that are based on uniform sampling ˆ vl 𝛼 , 𝛼 ˆ vl-d . This numerical observation also agrees with the theoretical results (Corollary 4).

Third, it can be observed (from the 1 st column of Fig. 3) that the bias of the proposed friendship paradox based MLE ˆ fp is negligible and also smaller compared to that of the vanilla MLE 𝛼 ˆ vl 𝛼 when the power-law exponent 𝛼 is larger than 2 5 (for all considered values of the minimum degree . 𝑘 min ). This agrees with the theoretical conclusions (Corollary 4). However, it can be seen that the bias of the proposed estimate ˆ fp 𝛼 starts to slightly increase when the power-law exponent 𝛼 decreases below approximately 2 5 (especially for values of the minimum degree . 𝑘 min larger than 5). This does not affect the conclusion that the friendship paradox based methods outperform the vanilla methods based on uniform sampling because the friendship paradox based methods still have a smaller MSE as seem from the third column of Fig. 3. Further, this slight increase of the bias contradicts the statistical analysis (Theorem 3) which suggests that the bias of the friendship paradox based MLE ˆfp should be a monotone function of the power-law exponent 𝛼 𝛼 and should not depend on the minimum degree 𝑘 min . We believe that this disparity between the theoretical analysis and the numerical analysis for small values of the power-law exponent 𝛼 (i.e. 𝛼 &lt; 2 5) could be due to . the bias introduced when representing a heavy-tailed power-law degree distribution with a finite graph in our numerical experiments.

Effect of the sample size 𝑛 : Fig. 4 illustrates the MSE of the four estimates of the power-law exponent 𝛼 presented in Sec. 2: vanilla MLE ˆ vl 𝛼 given in Eq. (7), friendship paradox based MLE ˆ fp 𝛼 given in Eq. (11) and their discrete versions ˆ vl-d 𝛼 , 𝛼 ˆ fp-d given in Eq. (12) and Eq. (13) respectively, for four values of the sample size 𝑛 = 50 100 150 200. Note that the friendship paradox based MLE , , , ˆ fp 𝛼 and its discrete version ˆ fp-d 𝛼 have smaller MSEs compared to the widely used vanilla methods based on uniform sampling ˆ fp 𝛼 , 𝛼 ˆ fp-d for all considered values of the sample size. Further, Fig. 4 shows that the friendship paradox based MLE ˆ fp 𝛼 and its discrete version ˆ fp-d 𝛼 have approximately equal MSEs for larger values of the minimum degree ( 𝑘 min ≥ 50). The slight increase (approximately 0 01) . of the MSE of the friendship paradox based methods ˆ fp 𝛼 , 𝛼 ˆ fp-d when the power-law exponent 𝛼 decreases below 2 3 could be due to the bias introduced when representing a power-law degree . distribution with a finite graph in numerical experiments (as also discussed using the Fig. 3 earlier). Thus, Fig. 4 further verifies the conclusions drawn from both the statistical analysis in Sec. 3 and the observations from Fig. 3 regarding the better performance of the friendship paradox based MLE ˆ fp 𝛼 and its discrete version ˆ fp-d 𝛼 compared to the vanilla methods based on uniform sampling ˆ vl 𝛼 , 𝛼 ˆ vl-d .

SummaryofNumericalComparison: This section presented numerical results that complement and support the statistical analysis (Sec. 3) of the estimates. Specifically, it was shown that the

Fig. 4. Empirical mean-squared error (MSE) of the four estimates (presented in Sec. 2): vanilla maximum likelihood estimate (MLE) ˆ 𝛼 vl given in Eq. (7) , friendship paradox based MLE ˆ 𝛼 fp given in Eq. (11) and their discrete versions ˆ 𝛼 vl-d , 𝛼 ˆ fp-d given in Eq. (12) and Eq. (13) respectively, for different values of the sample size 𝑛 (recall that Fig. 3 was for 𝑛 = 100 ). The plots show that the proposed friendship paradox based MLEs ˆ 𝛼 fp , 𝛼 ˆ fp-d achieve smaller MSEs with only a smaller sample size 𝑛 compared to the widely used uniform sampling based vanilla MLEs ˆ 𝛼 vl , 𝛼 ˆ vl-d and thus, confirm the conclusions reached in the theoretical analysis (Sec. 3).

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00310v4-figure-402086d5-47e5-4b65-8be1-ec7ac4c247ec.jpg)

empirical MSE of the proposed friendship paradox based MLE ˆ fp 𝛼 and its discrete version ˆ fp-d 𝛼 have smaller MSEs compared to the currently used vanilla methods that are based on uniform sampling ˆ vl 𝛼 , 𝛼 ˆ vl-d for various values of the power-law exponent 𝛼 , the minimum degree 𝑘 min and the sample size 𝑛 . Further, the variance of the friendship paradox based MLE ˆ fp 𝛼 and its discrete version ˆ fp-d 𝛼 are approximately equal to the best achievable variance by any unbiased estimate under friendship paradox based sampling (CRLB fp ) which is smaller compared to the best achievable variance by any unbiased estimate under uniform sampling sampling (CRLB vl ). Further, the friendship paradox based MLEs have a negligible bias when the power-law exponent 𝛼 is larger than 2 5 and a slight increase in bias is observed when . 𝛼 decreases below 2 5 that could be due . to the error of imposing a power-law degree distribution on a finite sized graph. The friendship paradox based MLE ˆ fp has a slightly smaller MSE compared to its discrete version 𝛼 ˆ fp-d 𝛼 for smaller minimum degree values ( 𝑘 min ≤ 5). Therefore, the numerical results verify the conclusion reached from the statistical analysis (Sec. 3) that friendship paradox based MLEs ˆ fp 𝛼 , 𝛼 ˆ fp-d yield a better accuracy compared to the vanilla methods based on uniform sampling ˆ vl 𝛼 , 𝛼 ˆ vl-d and, the difference in the accuracy (in terms of MSE) could be up to several orders of magnitude.

## 5 EMPIRICAL RESULTS USING REAL-WORLD NETWORK DATASETS

In this section, we use several real-world network datasets to compare the performance of the four estimates presented in Sec. 2: vanilla MLE ˆ vl 𝛼 given in Eq. (7), friendship paradox based MLE ˆfp given in Eq. (11) and their discrete versions 𝛼 ˆ vl-d 𝛼 , 𝛼 ˆ fp-d given in Eq. (12) and Eq. (13) respectively. Our aim is to illustrate how the better performance of the proposed friendship paradox based methods ( ˆ fp 𝛼 , 𝛼 ˆ fp-d ) compared to the widely used vanilla methods ( ˆ vl-d 𝛼 , 𝛼 ˆ fp-d ) seen from the statistical analysis (Sec. 3) and numerical experiments (Sec. 4) holds in real-world scenarios as well.

Description of Datasets: We use 18 datasets obtained from the corpus used in the large scale study presented in [9]. The datasets are publicly available also from the Colorado Index of Complex Networks (ICON) [16]. The 18 datasets include:

- · twelve biological networks (metabolic networks of various species, protein interaction networks and a food-web network)
- · three informational networks (two networks of word adjacency in texts of two languages and the network of similarity scores among books sold on Amazon website)
- · three technological networks (three networks that represent dependencies in software systems as complex networks).

The complementary cumulative distribution function (complementary CDF) 𝑃 of the degree distribution (i.e. 𝑃 𝑘 ( ) denotes the fraction of nodes with degrees greater than 𝑘 ) of each network dataset was visually examined on double-logarithmic axes. Then, the minimum degree 𝑘 min is chosen such that the complementary CDF of the degree distribution 𝑃 𝑘 ( ) is approximately a straight line on double-logarithmic axes in the region 𝑘 ≥ 𝑘 min . This ensures that the network datasets we use (at least approximately) satisfy the power-law assumption (Assumption 1). Fig. 5 (biological networks) and Fig. 6 (informational and technological networks) show the chosen value of the minimum degree 𝑘 min , the number of nodes with degrees greater than the minimum degree 𝑛 tail (which is effectively the number of nodes in the network for our purpose) and the complementary CDF 𝑃 𝑘 ( ) (in blue color) for each considered dataset. The sizes of the datasets 𝑛 tail range from 226 nodes to 268940 nodes. Further information about the datasets are given in Appendix E.

Experimental Setup: For each network dataset, the sample size 𝑛 is set to be the minimum of 5% of network size 𝑛 tail (rounded to the nearest integer) or 1000. The four estimates ˆ vl 𝛼 , 𝛼 ˆ vl-d , 𝛼 ˆ fp , 𝛼 ˆ fp-d (discussed in Sec. 2) and their empirical variances are calculated using a Monte-Carlo average with 1000 iterations. Further, the re-weighted Kolmogorov-Smirnov (KS) statistic (referred simply as the KS-statistic henceforth) [15],

$$D ( \hat { \alpha } ) = \max _ { k \geq k _ { \min } } \frac { | P _ { \hat { \alpha } } ( k ) - P ( k ) | } { \sqrt { P ( k ) ( 1 - P ( k ) ) } }, \quad \hat { \alpha } \in \{ \hat { \alpha } _ { \nu l }, \hat { \alpha } _ { \nu l \cdot d }, \hat { \alpha } _ { \hat { \alpha } _ { \hat { \mathrm f p } } }, \hat { \alpha } _ { \hat { \mathrm f p } \cdot d } \}$$

is used to quantify the distance between the empirical complementary CDF 𝑃 and the complementary CDF 𝑃 ˆ 𝛼 of a power-law distribution (of the form Eq. (5)) with the estimated power-law exponent ˆ 𝛼 ∈ { ˆ vl 𝛼 , 𝛼 ˆ vl-d , 𝛼 ˆ fp , 𝛼 ˆ fp-d } via the four methods discussed in Sec. 2.

Empirical Results. : Fig. 5 (biological networks) and Fig. 6 (informational and technological networks) illustrate the empirical complementary CDF 𝑃 (using the 𝑛 tail number of nodes in each dataset) and the complementary CDFs of the power-law distributions (of the form Eq. (5)) with power-law exponent set to be the estimated values using the four method ˆ vl 𝛼 , 𝛼 ˆ vl-d , 𝛼 ˆ fp , 𝛼 ˆ fp-d . Further, Table 1 summarizes the value of the KS-statistic (given in Eq. (19)) and the variance of each of the four estimates ˆ vl 𝛼 , 𝛼 ˆ vl-d , 𝛼 ˆ fp , 𝛼 ˆ fp-d . Several important observations that complement the

Fig. 5. Plots show the complementary CDF 𝑃 of the degree distribution of each of the 12 real-world biological network datasets (discussed in Sec. 5 and Appendix E) and the complementary CDFs of power-law distributions ( 𝑃 ˆ 𝛼 vl , 𝑃 ˆ 𝛼 vl-d , 𝑃 ˆ 𝛼 fp , 𝑃 ˆ 𝛼 fp-d ) with the power-law exponent values estimated from the four methods discussed in Sec. 2 ( ˆ 𝛼 vl , 𝛼 ˆ vl-d , 𝛼 ˆ fp , 𝛼 ˆ fp-d ). The estimated values and their variances are given in Table 1. The plots indicate that the friendship paradox based maximum likelihood estimate (MLE) ˆ 𝛼 fp and its discrete version ˆ 𝛼 fp-d obtain better power-law fits compared to the vanilla methods based on uniform sampling ˆ 𝛼 vl , 𝛼 ˆ vl-d (that either overestimate or underestimate the power-law exponent). This observation confirms the conclusion reached from statistical analysis (Sec. 3) and numerical experiments (Sec. 4) that the proposed friendship paradox based MLEs ˆ 𝛼 fp , 𝛼 ˆ fp-d outperform the widely used vanilla MLEs based on uniform sampling ˆ 𝛼 vl , 𝛼 ˆ vl-d for estimating power-law degree distributions.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00310v4-figure-dc827c13-33b9-40f5-a8df-a0bcbe32a935.jpg)

Fig. 6. Plots show the complementary CDF 𝑃 of the degree distribution of each of the 6 real-world information and technological network datasets (discussed in Sec. 5 and Appendix E) and the complementary CDFs of power-law distributions ( 𝑃 ˆ 𝛼 vl , 𝑃 ˆ 𝛼 vl-d , 𝑃 ˆ 𝛼 fp , 𝑃 ˆ 𝛼 fp-d ) with the power-law exponent values estimated from the four methods discussed in Sec. 2 ( ˆ 𝛼 vl , 𝛼 ˆ vl-d , 𝛼 ˆ fp , 𝛼 ˆ fp-d ). The estimated values and their variances are given in Table 1. The plots indicate that the friendship paradox based maximum likelihood estimate (MLE) ˆ 𝛼 fp and its discrete version ˆ 𝛼 fp-d obtain better power-law fits compared to the vanilla MLEs based on uniform sampling ˆ 𝛼 vl , 𝛼 ˆ vl-d (that either overestimate or underestimate the power-law exponent). This observation is similar to the one that is observed from biological networks (Fig. 5) and, also confirms the conclusion reached from statistical analysis (Sec. 3) and numerical experiments (Sec. 4) that the proposed friendship paradox based MLEs ˆ 𝛼 fp , 𝛼 ˆ fp-d outperform the widely used vanilla MLEs based on uniform sampling ˆ 𝛼 vl , 𝛼 ˆ vl-d for estimating power-law degree distributions.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00310v4-figure-e53b797c-fdaa-4212-bb56-31f5dd9db2d2.jpg)

statistical analysis (Sec. 3) and the numerical experiments (Sec. 4) can be drawn from the empirical results (Fig. 5, Fig. 6 and Table 1).

First, it can be visually observed from Fig. 5 and Fig. 6 that the proposed friendship paradox based MLE ˆfp and its discrete version 𝛼 ˆ fp-d 𝛼 fit the empirical degree distributions better compared to the vanilla methods that are based on uniform sampling ˆ vl 𝛼 , 𝛼 ˆ vl-d . Especially, it can be seen that the vanilla MLE ˆ vl 𝛼 overestimates the value of the power-law exponent 𝛼 while its discrete version ˆ vl-d 𝛼 underestimates it (compared to the two friendship paradox based methods), especially when the minimum degree is small (i.e. 𝑘 min ≤ 5). This observation also agrees with the theoretical results (Corollary 4) as well as the numerical experiments (presented in Sec. 4) - for example, note from the sub-figure for 𝑘 min = 1 in Fig. 3 that vanilla MLE ˆ vl 𝛼 has a positive bias and its approximation to discrete distributions ˆ vl-d 𝛼 has a negative bias which are both larger in magnitude

compared to the friendship paradox based MLEs. Apart from visual observation, the values of the KS-statistic given in Table 1 also verify that the friendship paradox based MLEs ˆ fp 𝛼 , 𝛼 ˆ fp-d of the power-law exponent 𝛼 fit the empirical data better compared to the vanilla MLEs based on uniform sampling ˆ vl 𝛼 , 𝛼 ˆ vl-d . Of the two proposed friendship paradox based estimates, the discrete version ˆ fp-d 𝛼 seems to have a better performance compared to ˆ fp 𝛼 in terms of the KS-statistic based comparison in all cases except two (Informational Network 1 and Informational Network 2) - in those two cases the friendship paradox based MLE ˆ fp does better (see Table 1). Thus, the empirical 𝛼 results indicate that the friendship paradox based MLE ˆ fp 𝛼 and its discrete version ˆ fp-d 𝛼 offer better accuracy in fitting power-law degree distributions to networks compared to the widely used vanilla MLEs based on uniform sampling ˆ vl 𝛼 , 𝛼 ˆ vl-d .

Second, the values of the variances of the four estimates ˆ vl 𝛼 , 𝛼 ˆ vl-d , 𝛼 ˆ fp , 𝛼 ˆ fp-d given in Table 1 indicate that the friendship paradox based methods have smaller variances compared to the vanilla methods based on uniform sampling. More specifically, the friendship paradox based discrete MLE ˆfp-d has the smallest variance amongst all four methods in all considered cases. The difference 𝛼 in variance between ˆ fp-d 𝛼 and the vanilla methods is several orders of magnitude in most cases as seen from Table 1. This observation also agrees with the conclusions reached from the statistical analysis 3 (Corollary 4) and the numerical experiments (second column of Fig. 3).

Summary of Empirical Results: This section used 18 real-world network datasets to empirically evaluate the performance of the four methods presented in Sec. 2: vanilla maximum likelihood estimate ˆ vl 𝛼 (given in Eq. (7)), friendship paradox based MLE ˆ fp 𝛼 (given in Eq. (11)) and their discrete versions ˆ vl-d 𝛼 , 𝛼 ˆ fp-d (given in Eq. (12) and Eq. (13), respectively). The empirical results indicate that the proposed friendship paradox based methods yield a better estimate of the powerlaw exponent for network data in the sense that the estimated power-law distribution results in a smaller (in comparison to the vanilla methods) Kolmogorov-Smirnov (KS) statistic. Further, the friendship paradox based methods also result in a smaller (up to several orders of magnitude) variance compared to the widely used vanilla methods that are based on uniform sampling. Of the two friendship paradox based methods, the friendship paradox based discrete MLE ˆ fp-d 𝛼 shows a better accuracy compared to ˆ fp 𝛼 in terms of both KS-statistic and variance in most cases. The empirical results support and verify the conclusion reached from the statistical analysis in Sec. 3 and the numerical experiments in Sec. 4: the proposed friendship paradox based maximum likelihood estimation method yields better results in estimating the exponent of power-law degree distributions compared to the widely used vanilla methods based on uniform sampling.

Table 1. Empirical results obtained by applying the estimates presented in Sec. 2 to 18 real-world datasets

| Name                    |   𝑛 tai 𝑙 |   𝑘 min |   ˆ 𝛼 vl |   ˆ 𝛼 vl-d |   ˆ 𝛼 fp |   ˆ 𝛼 fp-d |   𝐷 ( ˆ 𝛼 vl ) |   𝐷 ( ˆ 𝛼 vl-d ) |   𝐷 ( ˆ 𝛼 fp ) |   𝐷 ( ˆ 𝛼 fp-d ) |   Var { ˆ 𝛼 vl } |   Var { ˆ 𝛼 vl-d } |   Var { ˆ 𝛼 fp } |   Var { ˆ 𝛼 fp-d } |
|-------------------------|-----------|---------|----------|------------|----------|------------|----------------|------------------|----------------|------------------|------------------|--------------------|------------------|--------------------|
| Biological Network 1    |       813 |       1 |     3.44 |       1.89 |     2.89 |       2.55 |          0.549 |           0.383  |         0.286  |           0.116  |          0.436   |           0.006    |         0.0173   |           0.00242  |
| Biological Network 2    |      1278 |       1 |     2.67 |       1.77 |     2.63 |       2.44 |          0.372 |           0.358  |         0.351  |           0.246  |          0.0853  |           0.00368  |         0.00342  |           0.000791 |
| Biological Network 3    |       767 |       1 |     3.26 |       1.86 |     2.46 |       2.35 |          0.862 |           0.448  |         0.164  |           0.131  |          0.693   |           0.0113   |         0.00334  |           0.00103  |
| Biological Network 4    |      1042 |       2 |     3.34 |       2.39 |     3.08 |       2.82 |          0.321 |           0.193  |         0.2    |           0.0801 |          0.159   |           0.0193   |         0.0217   |           0.00683  |
| Biological Network 5    |       226 |       2 |     4.28 |       2.63 |     3.63 |       3.09 |          0.578 |           0.19   |         0.32   |           0.137  |          1.83    |           0.0937   |         0.222    |           0.0394   |
| Biological Network 6    |       515 |       1 |     3.19 |       1.85 |     2.87 |       2.54 |          0.546 |           0.389  |         0.384  |           0.212  |          0.402   |           0.00904  |         0.0205   |           0.00279  |
| Biological Network 7    |       537 |       1 |     3.79 |       1.93 |     2.89 |       2.55 |          0.765 |           0.363  |         0.221  |           0.0788 |          0.889   |           0.0104   |         0.0326   |           0.00412  |
| Biological Network 8    |      2528 |       1 |     2.64 |       1.77 |     2.56 |       2.4  |          0.352 |           0.327  |         0.297  |           0.191  |          0.0373  |           0.00166  |         0.00126  |           0.000338 |
| Biological Network 9    |      1496 |       1 |     3.26 |       1.87 |     2.69 |       2.46 |          0.471 |           0.353  |         0.152  |           0.0348 |          0.214   |           0.00407  |         0.00546  |           0.00112  |
| Biological Network 10   |      1237 |       1 |     2.8  |       1.79 |     2.6  |       2.42 |          0.402 |           0.351  |         0.28   |           0.169  |          0.0894  |           0.00348  |         0.00349  |           0.000848 |
| Biological Network 11   |       476 |       3 |     2.77 |       2.32 |     2.63 |       2.57 |          0.187 |           0.17   |         0.141  |           0.117  |          0.186   |           0.0546   |         0.0121   |           0.00766  |
| Biological Network 12   |       310 |       2 |     3.17 |       2.3  |     2.82 |       2.66 |          0.395 |           0.19   |         0.205  |           0.139  |          0.645   |           0.0775   |         0.0427   |           0.0156   |
| Informational Network 1 |      1954 |       2 |     2.72 |       2.14 |     2.39 |       2.35 |          0.339 |           0.3    |         0.174  |           0.192  |          0.0619  |           0.0121   |         0.000924 |           0.000599 |
| Informational Network 2 |      8412 |       2 |     2.56 |       2.08 |     2.29 |       2.27 |          0.245 |           0.286  |         0.167  |           0.179  |          0.0116  |           0.00262  |         0.000102 |           7.35e-05 |
| Informational Network 3 |    268940 |      11 |     4.23 |       3.81 |     4.2  |       3.99 |          0.124 |           0.0699 |         0.115  |           0.0624 |          0.0125  |           0.00713  |         0.00581  |           0.00393  |
| Technological Network 1 |     10734 |       3 |     2.46 |       2.15 |     2.39 |       2.36 |          0.111 |           0.102  |         0.0697 |           0.0547 |          0.00429 |           0.00167  |         0.000205 |           0.000155 |
| Technological Network 2 |      8457 |       1 |     2.37 |       1.7  |     2.23 |       2.19 |          0.298 |           0.335  |         0.184  |           0.161  |          0.00975 |           0.000654 |         2.96e-05 |           1.66e-05 |
| Technological Network 3 |      3842 |       1 |     2.87 |       1.81 |     2.45 |       2.34 |          0.418 |           0.388  |         0.198  |           0.137  |          0.0329  |           0.00116  |         0.000916 |           0.000305 |

· Table 1 shows:

i.) values of the four estimates presented in Sec. 2: vanilla MLE ˆ vl 𝛼 (Eq. (7)), friendship paradox based MLE ˆ fp 𝛼 (Eq. (11)) and their discrete versions ˆ vl-d 𝛼 (Eq. (12)) and ˆ fp-d 𝛼 (Eq. (13)), obtained using 18 real-world datasets discussed in Sec. 5.

ii.) Kolmogorov-Smirnov (KS) statistic 𝐷 𝛼 ( ˆ ) given in Eq. (19) which quantifies the distance between the empirical complementary CDF 𝑃 and the complementary CDF 𝑃 ˆ 𝛼 of a power-law distribution (of the form Eq. (5)) with the estimated power-law exponent ˆ 𝛼 ∈ { ˆ vl 𝛼 , 𝛼 ˆ vl-d , 𝛼 ˆ fp , 𝛼 ˆ fp-d } . The values in bold-font indicate the smallest value of the KS-statistic for each dataset.

iii.) Variance of each of the four estimates Var { ˆ vl 𝛼 } , Var { ˆ vl-d 𝛼 } , Var { ˆ fp 𝛼 } , Var { ˆ fp-d 𝛼 } with the smallest of them for each dataset highlighted in bold-font.

· The values shown in the Table 1 indicate that the friendship paradox based MLEs, especially the discrete version ˆ fp-d , yield the best results 𝛼 amongst all four considered methods. This observation agrees with both statistical analysis (Sec. 3) and numerical experiments (Sec. 4).

## 6 CONCLUSION AND EXTENSIONS

Conclusion: This paper proposed a maximum likelihood estimator that exploits the friendship paradox based sampling of nodes in order to estimate a power-law degree distribution of a network. Most widely used parametric methods such as linear regression, vanilla maximum likelihood estimation with uniformly sampled nodes can produce unreliable results due to the lack of samples from the characteristic heavy tail of the degree distribution. Other non-parametric methods have used friendship paradox based sampling (to yield more samples from the heavy tail of the degree distribution) but do not exploit the explicit parametric form of the power-law degree distribution and also do not provide any analytical quantification of the estimation accuracy. In contrast, by exploiting both the friendship paradox based sampling (to capture the heavy tail of the degree distribution) and the explicit parametric form of the power-law degree distribution (to derive the precise expression of the estimator), the proposed method results in a provably better accuracy compared to the state of the art methods. The analytical results show that the proposed method is strongly consistent and has a smaller bias, a smaller variance and a smaller Cramèr-Rao lower bound compared to the widely used vanilla maximum likelihood estimation method (with uniform samples). Numerical and empirical results illustrate the better accuracy of the proposed method (compared to widely used alternative methods) including its properties such as smaller bias, near optimal variance and sample efficiency. All analytical, numerical and empirical results lead to the conclusion that the proposed friendship paradox based maximum likelihood estimation method achieves an improved accuracy compared to the widely used vanilla maximum likelihood estimation method in both finite and asymptotic sample size regimes. It was also shown that the proposed method easily generalizes to degree distributions with parametric forms other than power-law (such as exponential degree distributions) while preserving all its desirable statistical properties.

Limitations and Extensions: There are several limitations of the proposed method that open up future research directions. Firstly, the proposed estimate is based on the assumption that the underlying social network has a power-law degree distribution. However, recent works (e.g. [9]) have pointed out that there might be other types of degree distributions that fit some real-world networks better than a power-law. Though our results indicate that the proposed method easily generalizes to other types of degree distributions such as the exponential degree distribution (Appendix D), it remains to be extended to other types of distributions such as the log-normal distribution which is also prevalent in real-world networks. Secondly, extending the proposed framework to directed networks by using the versions of friendship paradox for directed graphs [2, 32] is of importance due to the power-law behavior of the in- and out- degree distributions of real world directed networks [8, 18]. Such extensions might also be able to exploit the correlations [59] between in- and out- degrees to make the estimation further efficient. Thirdly, extending the proposed framework to a setting where the aim is to track a time-evolving power-law degree distribution (i.e. the power-law exponent 𝛼 of the degree distribution evolves over time) is also an interesting future research direction. Bayesian and stochastic approximation methods (such as [31, 38]) based on friendship paradox based sampling might be suitable for such contexts. Finally, the method we proposed in this paper is based on the original version of the friendship paradox (Theorem 1). Exploring how other versions of the friendship paradox (such as spectral friendship paradox [32]) can be used in estimating network properties other than degree distributions (e.g. spectra of networks) also remains an interesting future direction.

## ACKNOWLEDGMENTS

The authors thank Aaron Clauset at University of Colorado at Boulder and Johan Ugander at Stanford University for helpful comments. 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] William Aiello, Fan Chung, and Linyuan Lu. 2000. A random graph model for massive graphs. In Proceedings of the thirty-second annual ACM symposium on Theory of computing . ACM, 171-180.
- [2] Nazanin Alipourfard, Buddhika Nettasinghe, Andres Abeliuk, Vikram Krishnamurthy, and Kristina Lerman. 2020. Friendship Paradox Biases Perceptions in Directed Networks. Nature Communications (2020).
- [3] Ioannis E Antoniou and ET Tsompa. 2008. Statistical analysis of weighted networks. Discrete dynamics in Nature and Society 2008 (2008).
- [4] James P Bagrow, Christopher M Danforth, and Lewis Mitchell. 2017. Which friends are more popular than you?: Contact strength and the friendship paradox in social networks. In Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2017 . ACM, 103-108.
- [5] Albert-László Barabási and Réka Albert. 1999. Emergence of scaling in random networks. science 286, 5439 (1999), 509-512.
- [6] Alain Barrat, Marc Barthelemy, Romualdo Pastor-Satorras, and Alessandro Vespignani. 2004. The architecture of complex weighted networks. Proceedings of the national academy of sciences 101, 11 (2004), 3747-3752.
- [7] Heiko Bauke. 2007. Parameter estimation for power-law distributions by maximum likelihood methods. The European Physical Journal B 58, 2 (2007), 167-173.
- [8] Béla Bollobás, Christian Borgs, Jennifer Chayes, and Oliver Riordan. 2003. Directed scale-free graphs. In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms . Society for Industrial and Applied Mathematics, 132-139.
- [9] Anna D Broido and Aaron Clauset. 2019. Scale-free networks are rare. Nature communications 10, 1 (2019), 1-10.
- [10] Yang Cao and Sheldon M Ross. 2016. The friendship paradox. Mathematical Scientist 41, 1 (2016), 61-64.
- [11] George Casella and Roger L Berger. 2002. Statistical inference . Vol. 2. Duxbury Pacific Grove, CA.
- [12] David P Chassin and Christian Posse. 2005. Evaluating North American electric grid reliability using the Barabási-Albert network model. Physica A: Statistical Mechanics and its Applications 355, 2-4 (2005), 667-677.
- [13] Alex Chin, Dean Eckles, and Johan Ugander. 2018. Evaluating stochastic seeding strategies in networks. arXiv preprint arXiv:1809.09561 (2018).
- [14] Nicholas A Christakis and James H Fowler. 2010. Social network sensors for early detection of contagious outbreaks. PloS one 5, 9 (2010), e12948.
- [15] Aaron Clauset, Cosma Rohilla Shalizi, and Mark EJ Newman. 2009. Power-law distributions in empirical data. SIAM review 51, 4 (2009), 661-703.
- [16] Aaron Clauset, Ellen Tucker, and Matthias Sainz. The Colorado Index of Complex Networks . https://icon.colorado.edu/#!/
- [17] Reuven Cohen, Keren Erez, Daniel Ben-Avraham, and Shlomo Havlin. 2000. Resilience of the internet to random breakdowns. Physical review letters 85, 21 (2000), 4626.
- [18] Reuven Cohen, Alejandro Fabian Rozenfeld, Nehemia Schwartz, Daniel Ben-Avraham, and Shlomo Havlin. 2003. Directed and non-directed scale-free networks. In Statistical Mechanics of Complex Networks . Springer, 23-45.
- [19] Weibing Deng, Wei Li, Xu Cai, and Qiuping A Wang. 2011. The exponential degree distribution in complex networks: Non-equilibrium network theory, numerical simulation and empirical data. Physica A: Statistical Mechanics and its Applications 390, 8 (2011), 1481-1485.
- [20] Rick Durrett. 2010. Probability: Theory and Examples (4 ed.). Cambridge University Press.
- [21] Holger Ebel, Lutz-Ingo Mielsch, and Stefan Bornholdt. 2002. Scale-free topology of e-mail networks. Physical review E 66, 3 (2002), 035103.
- [22] Victor M Eguiluz, Dante R Chialvo, Guillermo A Cecchi, Marwan Baliki, and A Vania Apkarian. 2005. Scale-free brain functional networks. Physical review letters 94, 1 (2005), 018102.
- [23] Young-Ho Eom and Hang-Hyun Jo. 2014. Generalized friendship paradox in complex networks: The case of scientific collaboration. Scientific Reports 4 (April 2014).
- [24] 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 (2015), 09752.
- [25] Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. 1999. On power-law relationships of the internet topology. In ACM SIGCOMM computer communication review , Vol. 29. ACM, 251-262.
- [26] Scott L Feld. 1991. Why your friends have more friends than you do. Amer. J. Sociology 96, 6 (1991), 1464-1477.
- [27] Xavier Gabaix. 2009. Power laws in economics and finance. Annu. Rev. Econ. 1, 1 (2009), 255-294.

| [28]   | 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.                                                     |
|--------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [29]   | Michel L Goldstein, Steven A Morris, and Gary G Yen. 2004. Problems with fitting to the power-law distribution. The European Physical Journal B-Condensed Matter and Complex Systems 41, 2 (2004), 255-258.                                                   |
| [30]   | Manuel Gomez-Rodriguez, Jure Leskovec, and Andreas Krause. 2012. Inferring networks of diffusion and influence. ACM Transactions on Knowledge Discovery from Data (TKDD) 5, 4 (2012), 21.                                                                     |
| [31]   | Maziyar Hamdi, Vikram Krishnamurthy, and George Yin. 2014. Tracking a Markov-modulated stationary degree distribution of a dynamic random graph. IEEE Transactions on Information Theory 60, 10 (2014), 6609-6625.                                            |
| [32]   | Desmond J Higham. 2018. Centrality-friendship paradoxes: when our friends are more important than us. Journal of Complex Networks 7, 4 (11 2018), 515-528.                                                                                                    |
| [33]   | Nathan O Hodas, Farshad Kooti, and Kristina Lerman. 2013. Friendship Paradox Redux: Your Friends Are More Interesting Than You. In Seventh International AAAI Conference on Weblogs and Social Media .                                                        |
| [34]   | Bernardo A Huberman and Lada A Adamic. 1999. Internet: growth dynamics of the world-wide web. Nature 401, 6749 (1999), 131.                                                                                                                                   |
| [35]   | Matthew O Jackson. 2019. The friendship paradox and systematic biases in perceptions and social norms. Journal of Political Economy 127, 2 (2019), 777-818.                                                                                                   |
| [36]   | Hawoong Jeong, Sean P Mason, A-L Barabási, and Zoltan N Oltvai. 2001. Lethality and centrality in protein networks. Nature 411, 6833 (2001), 41.                                                                                                              |
| [37]   | Farshad Kooti, Nathan O Hodas, and Kristina Lerman. 2014. Network weirdness: Exploring the origins of network paradoxes. In Eighth International AAAI Conference on Weblogs and Social Media .                                                                |
| [38]   | Vikram Krishnamurthy, Sujay Bhatt, and Tavis Pedersen. 2017. Tracking infection diffusion in social networks: Filtering algorithms and threshold bounds. IEEE Transactions on Signal and Information Processing over Networks 3, 2 (2017), 298-315.           |
| [39]   | Silvio Lattanzi and Yaron Singer. 2015. The power of random neighbors in social networks. In Proceedings of the Eighth ACM International Conference on Web Search and Data Mining . ACM, 77-86.                                                               |
| [40]   | Eun Lee, Sungmin Lee, Young-Ho Eom, Petter Holme, and Hang-Hyun Jo. 2019. Impact of perception models on friendship paradox and opinion formation. Physical Review E 99, 5 (2019), 052302.                                                                    |
| [41]   | Kristina Lerman, Xiaoran Yan, and Xin-Zeng Wu. 2016. The 'majority illusion" in social networks. PloS one 11, 2 (2016), e0147617.                                                                                                                             |
| [42]   | Jure Leskovec and Christos Faloutsos. 2006. Sampling from large graphs. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining . ACM, 631-636.                                                                 |
| [43]   | Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. 2007. Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data (TKDD) 1, 1 (2007), 2.                                                                  |
| [44]   | Michael Mitzenmacher. 2004. A brief history of generative models for power law and lognormal distributions. Internet mathematics 1, 2 (2004), 226-251.                                                                                                        |
| [45]   | Naghmeh Momeni and Michael Rabbat. 2016. Qualities and inequalities in online social networks through the lens of the generalized friendship paradox. PloS one 11, 2 (2016), e0143633.                                                                        |
| [46]   | ANM Muniruzzaman. 1957. On measures of location and dispersion and tests of hypotheses in a pare to population. Calcutta Statistical Association Bulletin 7, 3 (1957), 115-123.                                                                               |
| [47]   | Fabricio Murai, Bruno Ribeiro, Don Towsley, and Pinghui Wang. 2013. On set size distribution estimation and the characterization of large networks via sampling. IEEE Journal on Selected Areas in Communications 31, 6 (2013), 1017-1025.                    |
| [48]   | Buddhika Nettasinghe and Vikram Krishnamurthy. Simulation Code Repository . https://github.com/ComplexInfo/ Powerlaw_Estimation                                                                                                                               |
| [49]   | Buddhika Nettasinghe and Vikram Krishnamurthy. 2021. 'What Do Your Friends Think?": Efficient Polling Methods for Networks Using Friendship Paradox. IEEE Transactions on Knowledge & Data Engineering 33, 03 (2021), 1291-1305.                              |
| [50]   | Buddhika Nettasinghe, Vikram Krishnamurthy, and Kristina Lerman. 2019. Diffusion in Social Networks: Effects of Monophilic Contagion, Friendship Paradox, and Reactive Networks. IEEE Transactions on Network Science and Engineering 7, 3 (2019), 1121-1132. |
| [51]   | Mark EJ Newman. 2003. The structure and function of complex networks. SIAM review 45, 2 (2003), 167-256.                                                                                                                                                      |
| [52]   | Mark EJ Newman. 2005. Power laws, Pareto distributions and Zipf's law. Contemporary physics 46, 5 (2005), 323-351.                                                                                                                                            |
| [53]   | Romualdo Pastor-Satorras, Claudio Castellano, Piet Van Mieghem, and Alessandro Vespignani. 2015. Epidemic processes in complex networks. Reviews of modern physics 87, 3 (2015), 925.                                                                         |
| [54]   | Romualdo Pastor-Satorras and Alessandro Vespignani. 2001. Epidemic spreading in scale-free networks. Physical review letters 86, 14 (2001), 3200.                                                                                                             |
| [55]   | Bruno Ribeiro and Don Towsley. 2010. Estimating and sampling graphs with multidimensional random walks. In                                                                                                                                                    |

- [55] Bruno Ribeiro and Don Towsley. 2010. Estimating and sampling graphs with multidimensional random walks. In Proceedings of the 10th ACM SIGCOMM conference on Internet measurement . ACM, 390-403.

- [56] Bruno Ribeiro and Don Towsley. 2012. On the estimation accuracy of degree distributions from graph sampling. In 2012 IEEE 51st IEEE Conference on Decision and Control (CDC) . IEEE, 5240-5247.
- [57] Yogesh Virkar and Aaron Clauset. 2014. Power-law distributions in binned empirical data. The Annals of Applied Statistics (2014), 89-119.
- [58] Deng Wei-Bing, Guo Long, Li Wei, and Cai Xu. 2009. Worldwide marine transportation network: Efficiency and container throughput. Chinese Physics Letters 26, 11 (2009), 118901.
- [59] Oliver Williams and Charo I Del Genio. 2014. Degree correlations in directed scale-free networks. PloS one 9, 10 (2014), e110121.
- [60] Viktor Witkovsk`. 2001. Computing the distribution of a linear combination of inverted gamma variables. y Kybernetika 37, 1 (2001), 79-90.

## A PROOF OF THEOREM 3

The proof of Theorem 3 is inspired by the ideas used in the proof of Theorem 2. Note from the expression for ˆ fp 𝛼 in Eq. (11) that,

$$\dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \\ \text{Bias} & \{ \hat { \alpha } _ { \text{p} } \} = \mathbb { E } \{ \hat { \alpha } _ { \text{fp} } \} - \alpha = n \mathbb { E } \left \{ \frac { 1 } { \sum _ { i = 1 } ^ { n } \ln \left ( \frac { d ( Y _ { i } ) } { k _ { \min } } \right ) } \right \} + 2 - \alpha \,, \\ & \text{Var} \{ \hat { \alpha } _ { \text{fp} } \} = n ^ { 2 } \text{Var} \left \{ \frac { 1 } { \sum _ { i = 1 } ^ { n } \ln \left ( \frac { d ( Y _ { i } ) } { k _ { \min } } \right ) } \right \}. \\ \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \cdots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots.$$

It can easily be shown that

$$\mathbb { P } \left \{ \ln \left ( \frac { d ( Y _ { i } ) } { k _ { \min } } \right ) \leq c \right \} = 1 - e ^ { - c ( \alpha - 2 ) } \ \ i = 1, \dots, n,$$

and therefore, ln GLYPH&lt;16&gt; 𝑑 𝑌 ( 𝑖 ) 𝑘 min GLYPH&lt;17&gt; 𝑖 = 1 , . . . , 𝑛 are independent and identically distributed (iid) exponential random variables with parameter 𝛼 -2. Since the sum of iid exponential random variables is a Gamma random variable, it follows that

$$\frac { 1 } { \sum _ { i = 1 } ^ { n } \ln \left ( \frac { d ( Y _ { i } ) } { k _ { \min } } \right ) } \sim \ln v \text{-Gamma} ( n, \alpha - 2 )$$

where, Inv-Gamma ( 𝑛, 𝛼 -2 ) denotes Inverse-Gamma distribution (distribution of the reciprocal of a Gamma distributed random variable) with parameters 𝑛 and 𝛼 -2. Eq. (21) then implies that [60],

$$\cdot \underset { \begin{array} { c } \mathbb { S } \left \{ \frac { 1 } { \sum _ { i = 1 } ^ { n } \ln \left ( \frac { d ( Y _ { i } ) } { k _ { \min } } \right ) } \end{array} \right ) } { \mathbb { S } \left \{ \frac { \alpha - 2 } { n - 1 } }, \text{ for } n > 1 \\ \text{Var} \left \{ \frac { 1 } { \sum _ { i = 1 } ^ { n } \ln \left ( \frac { d ( Y _ { i } ) } { k _ { \min } } \right ) } \right \} = \frac { ( \alpha - 2 ) ^ { 2 } } { ( n - 1 ) ^ { 2 } ( n - 2 ) }, \text{ for } n > 2. \\ \cdot \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \circ \OC }. \end{array} \right ).$$

The result follows by substituting Eq. (22) in the expressions for bias and variance in Eq. (20).

## B PROOF OF THEOREM 5

The asymptotic unbiasedness and strong consistency of the vanilla MLE ˆ vl 𝛼 have been established in [46]. We establish the strong consistency of the proposed friendship paradox based MLE ˆ fp 𝛼 below.

Note from Eq. (14) and Eq. (15) that bias of both vanilla MLE ˆ vl 𝛼 and friendship paradox based MLE ˆfp goes to zero as the sample size 𝛼 𝑛 tends to infinity. Hence, both estimates are asymptotically unbiased.

Next, note from Eq. (11) and Eq. (21) that,

$$\hat { \alpha } _ { \text{fp} } = \frac { 1 } { \bar { G } _ { n } } + 2$$

where, ¯ 𝐺 𝑛 is the empirical mean of 𝑛 iid exponential random variables with parameter 𝛼 -2. Hence, by strong law of large numbers, ¯ 𝐺 𝑛 converges almost surely to 1 /( 𝛼 -2 . Since the friendship ) paradox based MLE ˆ fp is a continuous function of 𝛼 ¯ 𝐺 𝑛 , ˆ fp 𝛼 converges almost surely to 𝛼 .

## C PROOF OF THEOREM 6

By definition [11]

$$C R L B _ { \text{fp} } ( \alpha ) = - \left [ \mathbb { E } \left \{ \frac { \partial ^ { 2 } \mathcal { L } _ { \text{fp} } } { \partial ^ { 2 } \alpha } \right \} \right ] ^ { - 1 }$$

where, L fp is the log-likelihood function for the friendship paradox based sampling defined in Eq. (10). By evaluating Eq. (24), we get,

$$\mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \quad \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u \ \mu _ { \ } u.$$

Then, the fact that 𝑞 𝑘 ( ) ∝ 𝑘𝑝 𝑘 ( ) (as discussed in Remark 1) can be used to obtain the expression for CRLBvl ( 𝛼 ) as a special case of CRLB fp ( 𝛼 ) by replacing 𝛼 with 𝛼 + 1.

## D EXTENSION OF RESULTS TO EXPONENTIAL DEGREE DISTRIBUTIONS

In this appendix, we briefly explain how the main results of this paper extend to exponential degree distributions.

Analogous to the power-law case, the following assumption is made for the derivation and analysis of MLEs for exponential case.

Assumption 3. The exponential distribution is continuous in 𝑘 and is of the form,

$$p _ { e x p } ( k ) = \lambda e ^ { - \lambda k }, \quad k \geq 0.$$

## D.1 Maximum Likelihood Estimation of the Exponential Distribution

Vanilla MLE for exponential degree distribution: The vanilla maximum likelihood estimation of the rate parameter 𝜆 of the degree distribution (defined in Eq. (25)) begins by sampling 𝑛 nodes 𝑋 , 𝑋 , . . . , 𝑋 1 2 𝑛 independently and uniformly from the network. Then, the likelihood of observing the degree sequence 𝑑 𝑋 ( 1 ) , . . . , 𝑑 ( 𝑋 𝑛 ) is,

$$\mathbb { P } \{ d ( X _ { 1 } ), \dots, d ( X _ { n } ) | \lambda \} = \prod _ { i = 1 } ^ { n } \lambda e ^ { - \lambda d ( X _ { i } ) }$$

following Eq. (25). Therefore, the log-likelihood for vanilla MLE of the rate parameter 𝜆 is,

$$\mathcal { L } _ { \text{v1} } ( \lambda ) = \ln \mathbb { P } \{ d ( X _ { 1 } ), \dots, d ( X _ { n } ) | \lambda \} = n \ln ( \lambda ) - \lambda \sum _ { i = 1 } ^ { n } d ( X _ { i } ).$$

Then, by solving 𝜕 L vl 𝜕𝜆 = 0, we get the vanilla MLE of the rate parameter 𝜆 as,

$$\hat { \lambda } _ { v l } & = \frac { n } { \sum _ { i = 1 } ^ { n } d ( X _ { i } ) }.$$

Next, we present a maximum likelihood estimator for the exponential distribution that exploits the friendship paradox.

MLEfor exponential degree distribution with friendship paradox based sampling: Recall (from Eq. (3)) that the neighbor degree distribution is defined by 𝑞 𝑒𝑥𝑝 ( 𝑘 ) ∝ 𝑘𝑝 𝑒𝑥𝑝 ( 𝑘 ) and hence, its normalizing constant is given by the mean 𝜆 -1 of the degree distribution 𝑝 𝑒𝑥𝑝 . Therefore, the neighbor degree distribution for a network with an exponential distribution (of the form Eq. (25)) is given by,

$$q _ { e x p } ( k ) = \frac { k p _ { e x p } ( k ) } { \lambda ^ { - 1 } } = \lambda ^ { 2 } k e ^ { - \lambda k } = \text{Gamma} ( 2, \lambda ).$$

The friendship paradox based maximum likelihood estimator for the rate parameter 𝜆 begins with sampling 𝑛 number of random neighbors 𝑌 , 𝑌 , . . . , 𝑌 1 2 𝑛 from the network independently. Then, the likelihood of observing the neighbor degree sequence 𝑑 𝑌 ( 1 ) , 𝑑 ( 𝑌 2 ) , . . . , 𝑑 ( 𝑌 𝑛 ) can be written using the neighbor degree distribution in Eq. (27) as,

$$\mathbb { P } \{ d ( Y _ { 1 } ), \dots, d ( Y _ { n } ) | \alpha \} = \prod _ { i = 1 } ^ { n } \lambda ^ { 2 } d ( Y _ { i } ) e ^ { - \lambda d ( Y _ { i } ) }.$$

Therefore, the log-likelihood for the rate parameter 𝜆 is,

$$\mathcal { L } _ { \text{fp} } ( \lambda ) = \ln \mathbb { P } \{ d ( Y _ { 1 } ), \dots, d ( Y _ { n } ) | \lambda \} = 2 n \ln ( \lambda ) + \sum _ { i = 1 } ^ { n } \left ( \ln ( d ( Y _ { i } ) ) - \lambda d ( Y _ { i } ) \right )$$

Then, by solving 𝜕 L fp 𝜕𝜆 = 0, we get the FP based MLE of the rate parameter 𝜆 as,

$$\hat { \lambda } _ { \text{fp} } & = \frac { 2 n } { \sum _ { i = 1 } ^ { n } d ( Y _ { i } ) }.$$

## D.2 Statistical Analysis of MLEs for Exponential Degree Distribution

This section presents the statistical analysis (analogous to the results in Sec. 3) of the two MLEs for the exponential degree distribution: vanilla MLE ˆ 𝜆 vl in Eq. (26) and friendship paradox based MLE ˆfp in Eq. (28). 𝛼

Comparison of bias and variance for finite sample size: The following two results characterizes the bias and variance of the vanilla MLE ˆ 𝜆 vl and the proposed friendship paradox based MLE ˆ 𝜆 fp under a finite samples size 𝑛 &lt; ∞ .

Theorem 7. The bias and variance of the vanilla MLE ˆ 𝜆 vl in Eq. (26) for sample size 𝑛 are given by,

$$\text{Bias} \{ \hat { \lambda } _ { \nu l } \} & = \frac { \lambda } { n - 1 }, \quad \text{for $n>1$} \\ \text{Var} \{ \hat { \lambda } _ { \nu l } \} & = \frac { n ^ { 2 } \lambda ^ { 2 } } { ( n - 1 ) ^ { 2 } ( n - 2 ) }, \quad \text{for $n>2$}.$$

Proof. Note that ˝ 𝑛 𝑖 = 1 𝑑 𝑋 ( 𝑖 ) (in Eq. (26)) is a sum of iid random variables sampled from the exponential distribution specified in Eq. (25). Since sum of iid exponential random variables is a Gamma random variable, it follows that,

$$\frac { 1 } { \sum _ { i = 1 } ^ { n } d ( X _ { i } ) } \sim \text{Inv-Gamma} ( n, \lambda )$$

and hence,

$$\mathbb { E } \left \{ \frac { 1 } { \sum _ { i = 1 } ^ { n } d ( X _ { i } ) } \right \} & = \frac { \lambda } { n - 1 }, \quad \text{for $n>1$} \\ \text{Var} \left \{ \frac { 1 } { \sum _ { i = 1 } ^ { n } d ( X _ { i } ) } \right \} & = \frac { \lambda ^ { 2 } } { ( n - 1 ) ^ { 2 } ( n - 2 ) }, \quad n > 2. \\. \. \. \. \. \. \. \. \.$$

Then, the result follows from Eq. (26) and Eq. (31).

Theorem 8. The bias and variance of the friendship paradox based MLE MLE ˆ 𝜆 fp in Eq. (28) for sample size 𝑛 are given by,

$$\text{Bias} \{ \hat { \lambda } _ { f p } \} & = \frac { \lambda } { 2 n - 1 }, \quad \text{for $n>1$} \\ \text{Var} \{ \hat { \lambda } _ { f p } \} & = \frac { 2 n ^ { 2 } \lambda ^ { 2 } } { ( 2 n - 1 ) ^ { 2 } ( n - 1 ) }, \quad \text{for $n>2$}. \\. \quad \text{--} \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots \ \dots$$

Proof. Note that ˝ 𝑛 𝑖 = 1 𝑑 𝑌 ( 𝑖 ) (in Eq. (28)) is sum of iid random variables sampled from the Gamma distribution in Eq. (27). Since sum of iid Gamma random variables is a Gamma random variable, it follows that,

$$\frac { 1 } { \sum _ { i = 1 } ^ { n } d ( Y _ { i } ) } \sim \text{Inv-Gammama} ( 2 n, \lambda ).$$

and hence,

$$\mathbb { E } & \left \{ \frac { 1 } { \sum _ { i = 1 } ^ { n } d ( Y _ { i } ) } \right \} = \frac { \lambda } { 2 n - 1 }, \quad \text{for $n>1$} \\ \text{Var} & \left \{ \frac { 1 } { \sum _ { i = 1 } ^ { n } d ( Y _ { i } ) } \right \} = \frac { \lambda ^ { 2 } } { ( 2 n - 1 ) ^ { 2 } ( 2 n - 2 ) }, \quad \text{for $n>2$}. \\ \text{Result for all one from $\mathbb{E}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb {E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{
E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{ \mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{F}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\mathbb{E}}_{\nu}}_{\nu}}_{\nu}}_{\nu}}_{\nu}}_{\nu}}_{\nu}}_{\nu}}$$

Then, the result follows from Eq. (28) and Eq. (34).

□

The following consequence of Theorem 7 and Theorem 8 shows that the proposed friendship paradox based MLE ˆ 𝜆 fp outperforms vanilla MLE ˆ 𝜆 vl for any finite sample size 𝑛 for exponential degree distributions.

Corollary 9. The bias and variance of the vanilla MLE ˆ 𝜆 vl defined in Eq. (26) and the friendship paradox based MLE ˆ 𝜆 fp defined in Eq. (28) satisfy,

$$\text{Bias} & \{ \hat { \lambda } _ { f p } \} < \text{Bias} & \{ \hat { \lambda } _ { v l } \}, \quad \text{for $n>1$} \\ \text{Var} & \{ \hat { \lambda } _ { f p } \} < \text{Var} & \{ \hat { \lambda } _ { v l } \}, \quad \text{for $n>2$}.$$

We now turn to the case where the sample size 𝑛 tends to infinity.

Comparison of the asymptotic properties of the MLEs: We have the following two results (whose proofs follow from arguments similar to Theorem 5 and Theorem 6) for the MLEs of rate parameter 𝜆 of the exponential degree distribution:

Theorem 10. The vanilla MLE ˆ 𝜆 vl (defined in Eq. (26) and friendship paradox based MLE ˆ 𝜆 fp (defined in Eq. (28) ) are asymptotically unbiased and strongly consistent i.e. converges to the true rate parameter 𝜆 with probability 1 as the sample size 𝑛 tends to infinity.

Theorem 11. The Cramèr-Rao Lower Bounds of the vanilla MLE ˆ 𝜆 vl in Eq. (26) and the friendship paradox based MLE ˆ 𝜆 fp in Eq. (28) are given by,

$$C R L B _ { v l } ( \lambda ) = \frac { \lambda ^ { 2 } } { n }, \quad C R L B _ { f p } ( \lambda ) = \frac { \lambda ^ { 2 } } { 2 n }.$$

Summary of Results for Exponential Degree Distributions: The analytical results presented in Sec. 2 and Sec. 3 for power-law degree distributions extend to exponential degree distributions as well. More specifically, the proposed friendship paradox based MLE ˆ 𝜆 fp (defined in Eq. (28)) outperforms the vanilla MLE ˆ 𝜆 vl (defined in Eq. (26)) in the finite sample regime (in terms of bias and variance) as well as the asymptotic regime (in terms of CRLB).

## E DETAILS FOR REPRODUCING THE NUMERICAL AND EMPIRICAL RESULTS

This appendix provides additional details on the simulations that produced all numerical results (Fig. 3 and Fig. 4 in Sec. 4) and empirical results (Fig. 5, Fig. 6 and Table 1 in Sec. 5) in order to facilitate the full reproducibility of the results in this paper.

Code Availability: Codes that produced all three figures in Sec. 4 and Sec. 5 are available in the Github repository [48]. Further, a detailed outline of the steps followed in each numerical experiment as well as empirical methodology with addition details is presented below.

Reproducibility: All simulations were performed using version 3.7.3 of the software Python . The random number generators were initialized with seed 123 (using the random.seed function) in each simulation.

## E.1 Simulation Details for Numerical Experiments

Simulation Details for Fig. 3. Twenty five equally spaced values of the parameter 𝛼 in the range from 2 1 to 3 5 (satisfying the Assumption 2 and including typical values observed in most . . real world networks) were considered. For each considered value of 𝛼 and 𝑘 min , 50000 random variables from the power-law distribution in Eq. (5) were sampled (using the scipy.stats.pareto.rvs function) independently and rounded off to the nearest integer. The degree sequences produced using this simulation setup are guaranteed to satisfy Assumptions 1, 2. This helps to rule out the possibility that the conclusions drawn from the numerical results could be due to violations of assumptions made on the underlying parametric model (such as not possessing a power-law degree distribution or parameters out of the considered range). Then, 𝑛 = 100 elements (denoted by 𝑑 𝑋 ( 1 ) , . . . , 𝑑 ( 𝑋 𝑛 ) ) were drawn from the degree sequence by uniformly and independently sampling. Another 𝑛 = 100 elements (denoted by 𝑑 𝑌 ( 1 ) , . . . , 𝑑 ( 𝑌 𝑛 ) ) were drawn from the degree sequence by independently sampling with a probability proportional to the value of each element. 1 Next, the vanilla MLEs ˆ vl 𝛼 , 𝛼 ˆ vl-d (by plugging in 𝑑 𝑋 ( 1 ) , . . . , 𝑑 ( 𝑋 𝑛 ) to expressions in Eq. (7) and Eq. (12), respectively) and friendship paradox based MLEs ˆ fp 𝛼 , 𝛼 ˆ fp-d (by plugging in 𝑑 𝑌 ( 1 ) , . . . , 𝑑 ( 𝑌 𝑛 ) to expression in Eq. (11) and Eq. (13), respectively) were computed and stored. This process was repeated 5000 times (for each considered value of the power-law exponent 𝛼 and the minimum degree 𝑘 min ) and the empirically estimated bias, variance and MSE using all 5000 independent iterations were plotted in Fig. 3. The Cramèr-Rao Lower Bounds were computed by directly plugging in the values of the power-law exponent 𝛼 into the expressions in Theorem 6.

Simulation Details for Fig. 4. For Fig. 4, the steps followed for obtaining Fig. 3 (detailed above) were repeated for four different values of the sample size 𝑛 = 50 100 150 200 for each considered , , , value of the minimum degree 𝑘 min . The obtained empirical MSE values for different values of the sample size 𝑛 are plotted in different colors in Fig. 4.

## E.2 Details on the Real-World Datasets

The 18 network degree sequences that we use in Sec. 5 are obtained from the dataset used for the study presented in [9]. The full network datasets are also available via the ICON network data library [16]. The degree sequence files that we use (which were extracted by the authors of [9]) for each of the 18 datasets and the code that produces the empirical results in Sec. 5 are available in the Github repository [48].

1 This is equivalent to sampling an edge uniformly and then taking the degree of the node at a random end of that edge i.e. equivalent to sampling from the neighbor degree distribution 𝑞 given in Eq. (3). This is because the neighbor degree distribution 𝑞 𝑘 ( ) is the same as degree distribution 𝑝 𝑘 ( ) scaled by degree 𝑘 .
Buddhika Nettasinghe Vikram Krishnamurthy
Maximum Likelihood Estimation of Power-law Degree Distributions via Friendship Paradox based Sampling
This paper considers the problem of estimating a power-law degree
distribution of an undirected network using sampled data. Although power-law
degree distributions are ubiquitous in nature, the widely used parametric
methods for estimating them (e.g. linear regression on double-logarithmic axes,
maximum likelihood estimation with uniformly sampled nodes) suffer from the
large variance introduced by the lack of data-points from the tail portion of
the power-law degree distribution. As a solution, we present a novel maximum
likelihood estimation approach that exploits the friendship paradox to sample
more efficiently from the tail of the degree distribution. We analytically show
that the proposed method results in a smaller bias, variance and a Cramer-Rao
lower bound compared to the vanilla maximum-likelihood estimate obtained with
uniformly sampled nodes (which is the most commonly used method in literature).
Detailed numerical and empirical results are presented to illustrate the
performance of the proposed method under different conditions and how it
compares with alternative methods. We also show that the proposed method and
its desirable properties (i.e. smaller bias, variance and Cramer-Rao lower
bound compared to vanilla method based on uniform samples) extend to parametric
degree distributions other than the power-law such as exponential degree
distributions as well. All the numerical and empirical results are reproducible
and the code is publicly available on Github.