标题： 基于Glauber动力学的Ising模型半监督社区检测 显示英文标题

标题： Semi-supervised Community Detection using Glauber Dynamics for an Ising Model

摘要： 我们研究具有两个社区的图，并分析了一种在图的边以及一小部分标签事先已知时学习社区标签的算法。 该算法基于一个伊辛模型的Glauber动力学，其中能量函数包括对磁化强度的二次惩罚。 分析集中在从随机块模型（SBM）采样的图上，该模型的平均度数增长缓慢。 我们推导了每个社区磁化强度的平均场极限，这可以用来选择算法的运行时间以达到目标精度水平。 此外，我们证明了几乎精确恢复可以在与节点数量成准线性关系的迭代次数内实现。 作为一个特殊情况，我们的结果为平均度数缓慢发散的SBM中的标签传播算法提供了首次严格的分析。 我们通过多个数值实验补充了理论结果。 显示英文摘要

摘要： We consider graphs with two communities and analyze an algorithm for learning the community labels when the edges of the graph and only a small fraction of the labels are known in advance. The algorithm is based on the Glauber dynamics for an Ising model where the energy function includes a quadratic penalty on the magnetization. The analysis focuses on graphs sampled from a Stochastic Block Model (SBM) with slowly growing mean degree. We derive a mean-field limit for the magnetization of each community, which can be used to choose the run-time of the algorithm to obtain a target accuracy level. We further prove that almost exact recovery is achieved in a number of iterations that is quasi-linear in the number of nodes. As a special case, our results provide the first rigorous analysis of the label propagation algorithm in the SBM with slowly diverging mean degree. We complement our theoretical results with several numerical experiments.