Title: Estimation of subgraph densities in noisy networks
Authors: Jinyuan Chang - Southwestern University of Finance and Economics (China) [presenting]
Eric Kolaczyk - Boston University (United States)
Qiwei Yao - London School of Economics (UK)
Abstract: While it is common practice in applied network analysis to report various standard network summary statistics, these numbers are rarely accompanied by some quantification of uncertainty. Yet any error inherent in the measurements underlying the construction of the network, or in the network construction procedure itself, necessarily must propagate to any summary statistics reported. We first study the problem of estimating the density of edges in a noisy network. Under a simple model of network error, we show that consistent estimation of such densities is impossible when the rates of error are unknown and only a single network is observed. We then develop method-of-moment estimators of network edge density and error rates for the case where a minimal number of network replicates are available. These estimators are shown to be asymptotically normal. We also provide the confidence intervals for quantifying the uncertainty in these estimates based on either the asymptotic normality or a bootstrap procedure. We further investigate the estimation for higher-order subgraph counts such as those for 2-star edges and triangles. Bootstrap confidence intervals for those high-order counts are constructed based on a new algorithm for constructing a graph with the pre-determined counts for edges, two-star edges and triangles.