Estimating network degree distributions under sampling: an inverse problem, with applications to monitoring social media networks
From MaRDI portal
Publication:2349562
Abstract: Networks are a popular tool for representing elements in a system and their interconnectedness. Many observed networks can be viewed as only samples of some true underlying network. Such is frequently the case, for example, in the monitoring and study of massive, online social networks. We study the problem of how to estimate the degree distribution - an object of fundamental interest - of a true underlying network from its sampled network. In particular, we show that this problem can be formulated as an inverse problem. Playing a key role in this formulation is a matrix relating the expectation of our sampled degree distribution to the true underlying degree distribution. Under many network sampling designs, this matrix can be defined entirely in terms of the design and is found to be ill-conditioned. As a result, our inverse problem frequently is ill-posed. Accordingly, we offer a constrained, penalized weighted least-squares approach to solving this problem. A Monte Carlo variant of Stein's unbiased risk estimation (SURE) is used to select the penalization parameter. We explore the behavior of our resulting estimator of network degree distribution in simulation, using a variety of combinations of network models and sampling regimes. In addition, we demonstrate the ability of our method to accurately reconstruct the degree distributions of various sub-communities within online social networks corresponding to Friendster, Orkut and LiveJournal. Overall, our results show that the true degree distributions from both homogeneous and inhomogeneous networks can be recovered with substantially greater accuracy than reflected in the empirical degree distribution resulting from the original sampling.
Recommendations
- Modeling social networks from sampled data
- Estimating sizes of social networks via biased sampling
- Sampling for conditional inference on network data
- Estimation of local degree distributions via local weighted averaging and Monte Carlo cross-validation
- Horvitz-Thompson estimator under partial information with an application to network degree distribution
Cites work
- Estimation of the number of vertices of different degrees in a graph
- Generalized SURE for Exponential Families: Applications to Regularization
- Graph spectra for complex networks
- scientific article; zbMATH DE number 3523369 (Why is no real title available?)
- scientific article; zbMATH DE number 3549966 (Why is no real title available?)
- scientific article; zbMATH DE number 1307590 (Why is no real title available?)
- scientific article; zbMATH DE number 487720 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 5070369 (Why is no real title available?)
- Modeling social networks from sampled data
- On Smoothing Sparse Multinomial Data
- On the bias of traceroute sampling
- Statistical analysis of network data. Methods and models
Cited in
(15)- Using isotope composition and other node attributes to predict edges in fish trophic networks
- A framework for imperfectly observed networks
- Motif estimation via subgraph sampling: the fourth-moment phenomenon
- Asymptotic distribution of Bernoulli quadratic forms
- Estimation of local degree distributions via local weighted averaging and Monte Carlo cross-validation
- Estimation of a local-aggregate network model with sampled networks
- On the question of effective sample size in network modeling: an asymptotic inquiry
- Impact of spatially constrained sampling of temporal contact networks on the evaluation of the epidemic risk
- Inverse network sampling to explore online brand allegiance
- Estimating sizes of social networks via biased sampling
- Sampling Based Estimation of In-Degree Distribution for Directed Complex Networks
- Horvitz-Thompson estimator under partial information with an application to network degree distribution
- Monitoring social networks based on Zero-inflated Poisson regression model
- Regularisation and central limit theorems for an inverse problem in network sampling applications
- Consistency of empirical distributions of sequences of graph statistics in networks with dependent edges
This page was built for publication: Estimating network degree distributions under sampling: an inverse problem, with applications to monitoring social media networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2349562)
