论文标题
用动态的伯特·希西安（Bethe-Hessian
Community detection in sparse time-evolving graphs with a dynamical Bethe-Hessian
论文作者
论文摘要
本文考虑了稀疏的动力学图中社区检测的问题，其中社区结构随着时间的流逝而演变。提出了一种基于Bethe-Hessian矩阵扩展的快速频谱算法，该算法受益于班级标签的正相关和其时间进化，因此受益于具有社区结构的任何动态图。在两种相等大小的类别的情况下，我们通过广泛的模拟证明和支持我们所提出的算法能够在理论上尽快进行非平凡的社区重建，从而在理论上实现非平凡的社区重建，从而达到最佳可检测性阈值，并实现竞争性的光谱方法，从而表现出非平凡的社区重建。
This article considers the problem of community detection in sparse dynamical graphs in which the community structure evolves over time. A fast spectral algorithm based on an extension of the Bethe-Hessian matrix is proposed, which benefits from the positive correlation in the class labels and in their temporal evolution and is designed to be applicable to any dynamical graph with a community structure. Under the dynamical degree-corrected stochastic block model, in the case of two classes of equal size, we demonstrate and support with extensive simulations that our proposed algorithm is capable of making non-trivial community reconstruction as soon as theoretically possible, thereby reaching the optimal detectability threshold and provably outperforming competing spectral methods.
