Journal article
Maximum Likelihood Estimation of Power-law Degree Distributions via Friendship Paradox-based Sampling
ACM transactions on knowledge discovery from data, Vol.15(6), pp.1-28
12/01/2021
DOI: 10.1145/3451166
Abstract
This article 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 and 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.
Details
- Title: Subtitle
- Maximum Likelihood Estimation of Power-law Degree Distributions via Friendship Paradox-based Sampling
- Creators
- Buddhika Nettasinghe - Cornell UniversityVikram Krishnamurthy - Cornell University
- Resource Type
- Journal article
- Publication Details
- ACM transactions on knowledge discovery from data, Vol.15(6), pp.1-28
- DOI
- 10.1145/3451166
- ISSN
- 1556-4681
- eISSN
- 1556-472X
- Publisher
- Assoc Computing Machinery
- Number of pages
- 28
- Grant note
- W911NF-19-1-0365 / U.S. Army Research Office CCF-1714180 / National Science Foundation; National Science Foundation (NSF)
- Language
- English
- Date published
- 12/01/2021
- Academic Unit
- Business Analytics
- Record Identifier
- 9984422858702771
Metrics
3 Record Views