On the propagation of low-rate measurement error to subgraph counts in large networks

MaRDI QIDQ5361332zbMATH OpenFDO

Authors Prakash Balachandran, Eric D. Kolaczyk, Weston D. Viles

Publication date 27 September 2017

Full work available at URL https://arxiv.org/abs/1409.5640, http://jmlr.csail.mit.edu/papers/v18/16-497.html

zbMATH Keywords

limit distributionnetwork analysisSkellam distributionStein's method

Mathematics Subject Classification ID

Applications of graph theory (05C90) Asymptotic distribution theory in statistics (62E20) Probabilistic graphical models (62H22)

Abstract: Our work in this paper is inspired by a statistical observation that is both elementary and broadly relevant to network analysis in practice -- that the uncertainty in approximating some true network graph $G=(V,E)$ by some estimated graph $hatG=(V,hatE)$ manifests as errors in the status of (non)edges that must necessarily propagate to any estimates of network summaries $eta(G)$ we seek. Motivated by the common practice of using plug-in estimates $eta(hatG)$ as proxies for $eta(G)$, our focus is on the problem of characterizing the distribution of the discrepancy $D=eta(hatG)-eta(G)$, in the case where $eta(cdot)$ is a subgraph count. Specifically, we study the fundamental case where the statistic of interest is $|E|$, the number of edges in $G$. Our primary contribution in this paper is to show that in the empirically relevant setting of large graphs with low-rate measurement errors, the distribution of $D_E=|hatE|-|E|$ is well-characterized by a Skellam distribution, when the errors are independent or weakly dependent. Under an assumption of independent errors, we are able to further show conditions under which this characterization is strictly better than that of an appropriate normal distribution. These results derive from our formulation of a general result, quantifying the accuracy with which the difference of two sums of dependent Bernoulli random variables may be approximated by the difference of two independent Poisson random variables, i.e., by a Skellam distribution. This general result is developed through the use of Stein's method, and may be of some general interest. We finish with a discussion of possible extension of our work to subgraph counts $eta(G)$ of higher order.

Recommendations

• Approximation of the difference of two Poisson-like counts by Skellam
• Estimation of Subgraph Densities in Noisy Networks
• Subgraph counts in random graphs using incomplete U-statistics methods
• Poisson approximation of subgraph counts in stochastic block models and a graphon model
• Asymptotic distributions in random graphs with applications to social networks

Cited in

(6)

• Approximation of the difference of two Poisson-like counts by Skellam
• Estimation of Subgraph Densities in Noisy Networks
• Modeling Network Populations via Graph Distances
• Multiplex Depth for Network-Valued Data and Applications
• Tobit models for count time series
• Variational Inference for Stochastic Block Models From Sampled Data

This page was built for publication: On the propagation of low-rate measurement error to subgraph counts in large networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361332)