|
Abstract:
|
Networks are widely used to model the relationships among elements in a system. Many empirical networks observed today can be viewed as samples of an underlying network, for example, large-scale online social networks. Hence, it is of fundamental interest to investigate the impact of the network sampling mechanism on the quality of characteristics estimated from the sampled network. We focus on the degree distribution as a fundamental feature. Under many popular sampling designs, this problem can be stated as a linear inverse problem characterized by an ill-conditioned matrix. This matrix relates the expectation of the sampled degree distribution to the true underlying degree distribution and depends entirely on the sampling design. We propose an approximate solution for the degree distribution by regularizing the solution of the ill-conditioned least squares problem corresponding to the naïve estimator. We then study the rate at which the approximate solution tends to the true solution as a function of network size and sampling rate. This provides theoretical understanding of the accuracy of the approximate solution, whose properties have previously been studied only numerically.
|
