Methods to find community based on edge centrality
Methods to find community based on edge centrality
复制标题
DOI：
10.1016/j.physa.2012.12.024
复制
发表时间：
2013-05
影响因子：
3.3
通讯作者：
P. Sun;Yang Yang-Yang
中科院分区：
文献类型：
--
作者：
P. Sun;Yang Yang-Yang
分裂算法是复杂网络中社团发现的重要方法。Girvan和纽曼（GN）提出的一种基于边缘中心性（称为介数）的算法是该领域的典型代表。本文研究了基于网络拓扑、路径和行走的三种边中心度来量化网络中每条边的相关性，并基于GN算法的基本原理提出了一种分裂算法，该算法根据边中心度值按一定顺序迭代去除边。并将这些测度与边缘介数和信息中心度进行了比较分析。我们发现，这些措施之间的划分过程中的主要区别是，边中心度的基础上走第一次删除的边缘连接到一个叶顶点，但其他人首先删除的边缘作为社区之间的桥梁。这表明，基于行走的边中心性比其他边中心性更难发现社区。我们还测试了这些措施的社区检测。结果表明，边信息中心度优于其他测度，基于路径的边中心度效果最差，而基于网络拓扑的边介数比基于网络拓扑的边中心度效果更好。我们还讨论了我们的方法的效率，并发现基于行走的边缘中心性具有较高的时间复杂度，不适合大型网络。
Divisive algorithms are of great importance for community detection in complex networks. One algorithm proposed by Girvan and Newman (GN) based on an edge centrality named betweenness, is a typical representative of this field. Here we studied three edge centralities based on network topology, walks and paths respectively to quantify the relevance of each edge in a network, and proposed a divisive algorithm based on the rationale of GN algorithm for finding communities that removes edges iteratively according to the edge centrality values in a certain order. In addition, we gave a comparison analysis of these measures with the edge betweenness and information centrality. We found the principal difference among these measures in the partition procedure is that the edge centrality based on walks first removes the edge connected with a leaf vertex, but the others first delete the edge as a bridge between communities. It indicates that the edge centrality based on walks is harder to uncover communities than other edge centralities. We also tested these measures for community detection. The results showed that the edge information centrality outperforms other measures, the edge centrality based on walks obtains the worst results, and the edge betweenness gains better performance than the edge centrality based on network topology. We also discussed our method’s efficiency and found that the edge centrality based on walks has a high time complexity and is not suitable for large networks.