Locally-biased spectral approximation for community detection
Locally-biased spectral approximation for community detection
复制标题
用于社区检测的局部偏置谱近似
DOI：
10.1016/j.knosys.2018.11.012
复制
发表时间：
2019-01-15
影响因子：
8.8
通讯作者：
Hoperoft, John E.
中科院分区：
文献类型：
--
作者：
Shi, Pan;He, Kun;Hoperoft, John E.
我们提出了一种局部偏置谱近似（LBSA）方法，用于从极少数种子成员中识别出当地社区的所有潜在成员。为了降低计算复杂度，我们首先应用快速随机游走、个性化 PageRank 和热核扩散来采样一个相对较小的子图，覆盖种子周围几乎所有潜在的社区成员。然后从种子的归一化指示向量开始，通过对采样子图进行Lanczos迭代或幂迭代的几步，获得局部特征向量，用于近似具有最大特征值的转移矩阵的特征向量。该局部特征向量的元素是对应节点与目标社区的隶属概率的宽松指标。我们对各个领域的真实数据集以及合成数据集进行了广泛的实验。结果表明，所提出的方法优于最先进的本地社区检测算法。据我们所知，这是第一个将 Lanczos 方法应用于当地社区检测的工作，这是自然且潜在有效的。此外，我们首次尝试使用热核作为采样方法，而不是直接检测社区，经验证明这是非常高效和有效的。 (C) 2018 Elsevier B.V. 保留所有权利。
We propose a Locally-Biased Spectral Approximation (LBSA) approach for identifying all latent members of a local community from very few seed members. To reduce the computation complexity, we first apply a fast random walk, personalized PageRank and heat kernel diffusion to sample a comparatively small subgraph covering almost all potential community members around the seeds. Then starting from a normalized indicator vector of the seeds and by a few steps of either Lanczos iteration or power iteration on the sampled subgraph, a local eigenvector is gained for approximating the eigenvector of the transition matrix with the largest eigenvalue. Elements of this local eigenvector is a relaxed indicator for the affiliation probability of the corresponding nodes to the target community. We conduct extensive experiments on real-world datasets in various domains as well as synthetic datasets. Results show that the proposed method outperforms state-of-the-art local community detection algorithms. To the best of our knowledge, this is the first work to adapt the Lanczos method for local community detection, which is natural and potentially effective. Also, we did the first attempt of using heat kernel as a sampling method instead of detecting communities directly, which is proved empirically to be very efficient and effective. (C) 2018 Elsevier B.V. All rights reserved.