标题： 加权随机块模型中社区估计的最优速率 显示英文标题

标题： Optimal Rates for Community Estimation in the Weighted Stochastic Block Model

摘要： 网络中的社区识别在社会科学、神经科学和遗传学等领域是一个重要的问题。 在过去的十年里，随机块模型（SBM）已成为解决该问题的一种流行的统计框架。 然而，SBM有一个重要的限制，即它只适用于具有无权边的网络；在各种科学应用中，忽略边的权重可能会导致有价值的信息丢失。 我们研究了SBM的一个加权推广，其中观察值以加权邻接矩阵的形式收集，并且每条边的权重独立地由其端点的社区隶属关系决定的未知概率密度生成。 我们用社区内边和社区间边的权重分布之间的1/2阶Renyi散度来刻画加权SBM的误聚类误差的最佳速率，这大大推广了现有无权SBM的结果。 此外，我们提出了一种基于离散化的可计算算法，实现了最佳误差率。 我们的方法具有适应性，也就是说，该算法在不知道权重密度的情况下，表现得与知道权重密度的最佳算法一样好。 显示英文摘要

摘要： Community identification in a network is an important problem in fields such as social science, neuroscience, and genetics. Over the past decade, stochastic block models (SBMs) have emerged as a popular statistical framework for this problem. However, SBMs have an important limitation in that they are suited only for networks with unweighted edges; in various scientific applications, disregarding the edge weights may result in a loss of valuable information. We study a weighted generalization of the SBM, in which observations are collected in the form of a weighted adjacency matrix and the weight of each edge is generated independently from an unknown probability density determined by the community membership of its endpoints. We characterize the optimal rate of misclustering error of the weighted SBM in terms of the Renyi divergence of order 1/2 between the weight distributions of within-community and between-community edges, substantially generalizing existing results for unweighted SBMs. Furthermore, we present a computationally tractable algorithm based on discretization that achieves the optimal error rate. Our method is adaptive in the sense that the algorithm, without assuming knowledge of the weight densities, performs as well as the best algorithm that knows the weight densities.