Estimating network degree distributions under sampling: An inverse problem, with applications to monitoring social media networks
Estimating network degree distributions under sampling: An inverse problem, with applications to monitoring social media networks
复制标题
估计采样下的网络度分布：逆问题，应用于监控社交媒体网络
DOI：
10.1214/14-aoas800
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
B. Spencer
中科院分区：
文献类型：
--
作者：
Yaonan Zhang;E. Kolaczyk;B. Spencer
网络是表示系统中的元素及其相互联系的流行工具。许多观察到的网络可以被看作是一些真正的底层网络的样本。例如，在对大规模在线社交网络的监测和研究中，这种情况经常发生。我们研究了如何从一个真正的底层网络的采样网络中估计其度分布的问题。特别地，我们证明了这个问题可以被表述为一个逆问题。在这个公式中起关键作用的是一个矩阵，它将我们的采样度分布的期望与真正的底层度分布联系起来。在许多网络采样设计中，这个矩阵可以完全根据设计来定义，并且发现它是病态的。因此，我们的逆问题经常是不适定的。因此，我们提出了一种约束的、惩罚的加权最小二乘方法来解决这个问题。采用Stein无偏风险估计（SURE）的蒙特卡洛变体来选择惩罚参数。我们使用各种网络模型和抽样制度的组合，在模拟中探索我们得到的网络度分布估计器的行为。此外，我们证明了我们的方法能够准确地重建在线社交网络中对应于Friendster， Orkut和LiveJournal的各种子社区的程度分布。总体而言，我们的结果表明，从均匀和非均匀网络中恢复的真实度分布可以比原始采样产生的经验度分布反映的精度高得多。
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.