Estimating Distributions of Large Graphs from Incomplete Sampled Data
Estimating Distributions of Large Graphs from Incomplete Sampled Data
复制标题
DOI：
10.23919/ifipnetworking52078.2021.9472848
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Shiju Li;Xin Huang;Chul-Ho Lee
中科院分区：
文献类型：
--
作者：
Shiju Li;Xin Huang;Chul-Ho Lee
研究了当样本仅表示部分进入节点的边的存在，从而样本分布与原始分布相差甚远时，如何从随机样本中估计大有向图的潜在入度分布的问题.虽然这个问题可以作为一个逆问题，它往往是病态的，并导致估计性能差。因此，最近很少有研究来克服这个问题，其中包括一个约束，惩罚加权最小二乘估计和渐近估计。然而，最近的估计，计算昂贵或仅限于估计尾部分布，其性能可能不令人满意。在本文中，我们制定的问题作为一个最大似然估计问题。然后，我们采用期望最大化算法来解决这个问题，并得出一个简单的迭代估计，这是易于实现和计算速度快。最后，我们的经验表明，我们的估计是显着更准确的比国家的最先进的估计，它也可以进一步改善与适当选择其参数。
We study the problem of how to estimate the latent in-degree distribution of large directed graphs from random samples, when the samples only indicate the presence of partial incoming edges into nodes and thus their sampled distribution is far from the original one. While this problem can be cast as an inverse problem, it often appears to be ill-posed and leads to poor estimation performance. There have thus been few recent studies to overcome this problem, which include a constrained, penalized weighted least squares estimator and an asymptotic estimator. The recent estimators, however, are computationally expensive or only limited to estimating the tail distribution, and their performance may not be satisfactory. In this paper, we formulate the problem as a maximum-likelihood estimation problem. We then employ the expectation-maximization algorithm to solve this problem and derive a simple iterative estimator, which is easy to implement and computationally fast. Finally, we empirically demonstrate that our estimator is significantly more accurate than the state-of-the-art estimators and it can also be further improved with a proper choice of its parameter.