体积正则图的逐步社区检测

作者：Luca Becchetti,Emilio Cruciani,Francesco Pasquale,Sara Rizzo

摘要：光谱技术已被证明是最有效的图聚类方法之一。然而，通常它们需要显式计算合适矩阵（通常是图的拉普拉斯矩阵）的主特征向量。

最近研究（例如，Becchetti等人，SODA 2017）表明，观察应用于初始随机向量的幂方法的时间演变，至少在某些情况下，可以提供关于前两个特征向量所跨越的空间的足够信息，以便在没有显式特征向量计算的情况下恢复隐藏分区。虽然Becchetti等人的结果。适用于表现出非常强的规律性的完美平衡的分区和/或图形，我们将它们的方法扩展到包含隐藏的k分区的图形，并以更温和的体积规律形式为特征。我们证明了k-体积正则图的类是最大类的无向（可能是加权的）图，其转移矩阵允许k个逐步的特征向量（即，在每组隐藏分区上是恒定的向量）。为了获得这个结果，我们强调了马尔可夫链的体积规律性和可变性之间的联系。此外，我们证明了如果逐步特征向量是与第一个k个特征值相关的那些，并且第k个和第（k + 1）个特征值之间的间隙足够大，那么Becchetti等人的平均动态。在对数时间内以高概率恢复图的基础社区结构。

原文标题：Step-by-Step Community Detection for Volume-Regular Graphs

原文摘要：Spectral techniques have proved amongst the most effective approaches to graph clustering. However, in general they require explicit computation of the main eigenvectors of a suitable matrix (usually the Laplacian matrix of the graph).

Recent work (e.g., Becchetti et al., SODA 2017) suggests that observing the temporal evolution of the power method applied to an initial random vector may, at least in some cases, provide enough information on the space spanned by the first two eigenvectors, so as to allow recovery of a hidden partition without explicit eigenvector computations. While the results of Becchetti et al. apply to perfectly balanced partitions and/or graphs that exhibit very strong forms of regularity, we extend their approach to graphs containing a hiddenkpartition and characterized by a milder form of volume-regularity. We show that the class ofk-volume regular graphs is the largest class of undirected (possibly weighted) graphs whose transition matrix admitskstepwise eigenvectors (i.e., vectors that are constant over each set of the hidden partition). To obtain this result, we highlight a connection between volume regularity and lumpability of Markov chains. Moreover, we prove that if the stepwise eigenvectors are those associated to the firstkeigenvalues and the gap between thek-th and the (k+1)-th eigenvalues is sufficiently large, the Averaging dynamics of Becchetti et al. recovers the underlying community structure of the graph in logarithmic time, with high probability.

地址：https://arxiv.org/abs/1907.07149