Local Spectral Clustering for Overlapping Community Detection
Local Spectral Clustering for Overlapping Community Detection
复制标题
用于重叠社区检测的局部谱聚类
DOI：
10.1145/3106370
复制
发表时间：
2018-03-01
影响因子：
3.6
通讯作者：
Hopcroft, John
中科院分区：
文献类型：
--
作者：
Li, Yixuan;He, Kun;Hopcroft, John
大型图出现在许多背景下，理解它们的结构并从中提取信息是一个重要的研究领域。早期的社区挖掘算法主要关注全局图结构，并且通常与整个图的大小成比例地运行。当我们探索具有数百万个顶点的网络并找到数百个大小的社区时，将我们的注意力从宏观结构转移到大型网络的微观结构变得非常重要。越来越多的工作采用了地方扩展方法，以便从一些模范种子成员中确定社区。在这篇文章中，我们提出了一种新的方法来寻找重叠的社区，称为柠檬（通过最小一个范数的本地扩展）。提供了一些已知的种子，该算法通过执行局部谱扩散来找到社区。Lemon的核心思想是使用短随机游走来近似种子集附近的不变子空间，我们称之为局部谱。局部谱可以被看作是低维嵌入，它捕获了节点在局部网络结构中的接近程度。我们表明，柠檬的性能在检测社区是有竞争力的国家的最先进的方法。此外，运行时间与社区的大小而不是整个图的大小成比例。该算法易于实现，具有高度的并行性。我们进一步提供了理论分析的本地频谱特性，边界的措施，使用图拉普拉斯算子的特征值提取社区的紧密性。我们使用不同领域的合成数据集和真实数据集对我们的方法进行了全面评估，并分析了将我们的方法应用于实际中固有的不同网络时的经验变化。此外，还对结实质量和数量对产量的影响进行了分析。
Large graphs arise in a number of contexts and understanding their structure and extracting information from them is an important research area. Early algorithms for mining communities have focused on global graph structure, and often run in time proportional to the size of the entire graph. As we explore networks with millions of vertices and find communities of size in the hundreds, it becomes important to shift our attention from macroscopic structure to microscopic structure in large networks. A growing body of work has been adopting local expansion methods in order to identify communities from a few exemplary seed members. In this article, we propose a novel approach for finding overlapping communities called Lemon (Local Expansion via Minimum One Norm). Provided with a few known seeds, the algorithm finds the community by performing a local spectral diffusion. The core idea of Lemon is to use short random walks to approximate an invariant subspace near a seed set, which we refer to as local spectra. Local spectra can be viewed as the low-dimensional embedding that captures the nodes’ closeness in the local network structure. We show that Lemon’s performance in detecting communities is competitive with state-of-the-art methods. Moreover, the running time scales with the size of the community rather than that of the entire graph. The algorithm is easy to implement and is highly parallelizable. We further provide theoretical analysis of the local spectral properties, bounding the measure of tightness of extracted community using the eigenvalues of graph Laplacian. We thoroughly evaluate our approach using both synthetic and real-world datasets across different domains, and analyze the empirical variations when applying our method to inherently different networks in practice. In addition, the heuristics on how the seed set quality and quantity would affect the performance are provided.