When is non-trivial estimation possible for graphons and stochastic block models?‡
When is non-trivial estimation possible for graphons and stochastic block models?‡
复制标题
什么时候可以对图子和随机块模型进行非平凡的估计？
DOI：
10.1093/imaiai/iax010
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Smith, Adam
中科院分区：
文献类型：
--
作者：
McMillan, Audra;Smith, Adam
块图子（也称为随机块模型）是一类重要且广泛研究的随机网络模型。我们提供了一个下界的准确性估计块graphons大量的块。我们表明，只给的块的数量和一个上界的值（连接概率）的图子，每个估计招致误差在themetric与常数概率至少有一些图子。特别是，我们的界限排除了任何非平凡的估计（即，witherror大大小于）时。结合以前的上限和下限，我们的结果特征，对数项，在themetric的graphon估计的准确性。类似的下限，我们得到了独立的Klovalal。
Block graphons (also called stochastic block models) are an important and widely studied class of models for random networks. We provide a lower bound on the accuracy of estimators for block graphons with a large number of blocks. We show that, given only the numberof blocks and an upper boundon the values (connection probabilities) of the graphon, every estimator incurs errorin themetric with constant probability for at least some graphons. In particular, our bound rules out any non-trivial estimation (that is, witherror substantially less than) when. Combined with previous upper and lower bounds, our results characterize, up to logarithmic terms, the accuracy of graphon estimation in themetric. A similar lower bound to ours was obtained independently by Kloppet al.