Estimating Network Degree Distributions from Sampled Networks: An Inverse Problem

• Activity Number: 465
• Type: Contributed
• Date/Time: Wednesday, August 1, 2012 : 8:30 AM to 10:20 AM
• Sponsor: Section on Statistical Learning and Data Mining
• Author(s): Yaonan Zhang*+ and Eric D Kolaczyk and Bruce D. Spencer
• Companies: Boston University and Boston University and Northwestern University
• Keywords: networks ; degree distribution ; inverse problem ; penalized least-squares

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. We study the problem of how to estimate the degree distribution of a true underlying network from its sampled network, focusing on the case of induced sub-graph sampling. We show that it can be formulated as an ill-posed inverse problem. Accordingly, we offer a penalized least-squares approach to solving this problem, with the option of additional constraints. The resulting estimator is a linear combination of singular vectors of a matrix, relating the expectation of our sampled degree distribution to the true underlying degree distribution, which is defined entirely in terms of the sampling plan. We apply our method to simulated and real data for both homogenous and inhomogeneous networks. Our results show that the estimators from both types of networks can be appropriately smoothed with proper choice of the penalization parameters. We explore various approaches to selecting the penalization parameter, including methods based on the bootstrap and Stein's unbiased risk estimation.