Community detection based on network communicability
Community detection based on network communicability
复制标题
DOI：
10.1063/1.3552144
复制
发表时间：
2011-03-01
期刊：
影响因子：
2.9
通讯作者：
Estrada, Ernesto
中科院分区：
文献类型：
--
作者：
Estrada, Ernesto
我们提出了一种新的方法来检测社区的基础上的概念，在复杂网络中的节点之间的可通信性。该方法被称为N-ComBa K-means，使用邻接矩阵的归一化版本来构建可通信性矩阵，然后应用K-means聚类来找到图中的社区。我们分析了这种方法如何执行的一些病理情况下发现的社区的检测限分析，并提出了一些可能的解决方案的基础上的分析图中的局部与全局密度的比率。我们使用四种不同的质量标准来检测最佳聚类，并将新方法与Girvan-Newman算法进行比较，以分析两个“经典”网络：空手道俱乐部和海豚。最后，我们分析了具有社区结构的同构网络的更具挑战性的情况，对于这种情况，Girvan-Newman完全无法检测到任何聚类。N-ComBa K-means方法在这些情况下表现得非常好，我们应用它来检测具有这些特征的金属杂项制造商的国际贸易网络中的社区结构。最后还讨论了社区检测的一般原理。(C)2011年美国物理学会。[doi：10.1063/1.3552144]
We propose a new method for detecting communities based on the concept of communicability between nodes in a complex network. This method, designated as N-ComBa K-means, uses a normalized version of the adjacency matrix to build the communicability matrix and then applies K-means clustering to find the communities in a graph. We analyze how this method performs for some pathological cases found in the analysis of the detection limit of communities and propose some possible solutions on the basis of the analysis of the ratio of local to global densities in graphs. We use four different quality criteria for detecting the best clustering and compare the new approach with the Girvan-Newman algorithm for the analysis of two "classical" networks: karate club and bottlenose dolphins. Finally, we analyze the more challenging case of homogeneous networks with community structure, for which the Girvan-Newman completely fails in detecting any clustering. The N-ComBa K-means approach performs very well in these situations and we applied it to detect the community structure in an international trade network of miscellaneous manufactures of metal having these characteristics. Some final remarks about the general philosophy of community detection are also discussed. (C) 2011 American Institute of Physics. [doi: 10.1063/1.3552144]