Fast graph clustering with a new description model for community detection
Fast graph clustering with a new description model for community detection
复制标题
DOI：
10.1016/j.ins.2017.01.026
复制
发表时间：
2017-05
期刊：
影响因子：
--
通讯作者：
Liang Bai;Xueqi Cheng;Jiye Liang;Yike Guo
中科院分区：
文献类型：
--
作者：
Liang Bai;Xueqi Cheng;Jiye Liang;Yike Guo
有效地描述和发现网络中的社区是图聚类的一个重要研究概念。在本文中，我们提出了一个社区描述模型，该模型评估了一个节点在社区中的局部重要性及其在所有社区中的重要性集中度，以反映其对社区的可代表性。基于描述模型，提出了一种新的社区检测评价准则和迭代搜索算法。由于平均线性时间复杂度随边数的增加，该算法可以快速发现大规模网络中的社区。此外，我们还提供了一种初始化算法，在算法实现前对输入参数进行初始化，包括社区数量和初始划分，从而提高了迭代算法的局部搜索质量。提出的算法与初始方法称为ISCD+。最后，在多个真实网络数据集上比较了ISCD+算法与6种代表性算法的有效性和效率。实验结果表明，该算法适用于大规模网络的寻址。
Efficiently describing and discovering communities in a network is an important research concept for graph clustering. In the paper, we present a community description model that evaluates the local importance of a node in a community and its importance concentration in all communities to reflect its representability to the community. Based on the description model, we propose a new evaluation criterion and an iterative search algorithm for community detection (ISCD). The new algorithm can quickly discover communities in a large-scale network, due to the average linear-time complexity with the number of edges. Furthermore, we provide an initial method of input parameters including the number of communities and the initial partition before algorithm implementation, which can enhance the local-search quality of the iterative algorithm. The proposed algorithm with the initial method is called ISCD+. Finally, we compare the effectiveness and efficiency of the ISCD+ algorithm with six representative algorithms on several real network data sets. The experimental results illustrate that the proposed algorithm is suitable to address large-scale networks.