论文标题
自适应重量社区检测
Adaptive Weights Community Detection
论文作者
论文摘要
由于过去几十年的技术进步，社区发现已成为机器学习的主要主题。但是，实际结果和理论结果之间仍然存在巨大差距，因为理论上最佳程序通常缺乏可行的实施，反之亦然。本文旨在缩小这一差距，并提出一种新型算法，在数字和统计上既有效率又有效。我们的程序使用同质性测试来计算描述当地社区的自适应权重。该方法的灵感来自Adamyan等人的自适应重量社区检测（AWCD）算法。 （2019）。该算法在人工和现实生活数据上带来了一些有希望的结果，但是我们的理论分析表明，其性能在随机块模型上是次优的。特别是，涉及的估计器是偏差的，并且该过程对于稀疏图不起作用。我们提出了重大的修改，解决了缺点并在随机块模型上实现了近乎最佳的强度一致性。通过数值实验来说明和验证我们的理论结果。
Due to the technological progress of the last decades, Community Detection has become a major topic in machine learning. However, there is still a huge gap between practical and theoretical results, as theoretically optimal procedures often lack a feasible implementation and vice versa. This paper aims to close this gap and presents a novel algorithm that is both numerically and statistically efficient. Our procedure uses a test of homogeneity to compute adaptive weights describing local communities. The approach was inspired by the Adaptive Weights Community Detection (AWCD) algorithm by Adamyan et al. (2019). This algorithm delivered some promising results on artificial and real-life data, but our theoretical analysis reveals its performance to be suboptimal on a stochastic block model. In particular, the involved estimators are biased and the procedure does not work for sparse graphs. We propose significant modifications, addressing both shortcomings and achieving a nearly optimal rate of strong consistency on the stochastic block model. Our theoretical results are illustrated and validated by numerical experiments.
