Eigenspaces of networks reveal the overlapping and hierarchical community structure more precisely
Eigenspaces of networks reveal the overlapping and hierarchical community structure more precisely
复制标题
网络特征空间更准确地揭示重叠和分层的社区结构
DOI：
10.1088/1742-5468/2010/08/p08012
复制
发表时间：
2010-08-01
影响因子：
2.4
通讯作者：
Yong, Xuerong
中科院分区：
文献类型：
--
作者：
Ma, Xiaoke;Gao, Lin;Yong, Xuerong
识别社区结构是揭示复杂网络中结构-功能关系的基础，谱算法已被证明对于此目的非常强大。在传统的谱算法中，通过利用图的邻接矩阵或拉普拉斯矩阵的特征向量将网络的每个顶点嵌入到谱空间中。本文提出了一种新的谱方法，不仅使用特征值和特征向量，而且还使用所涉及网络的特征空间的性质，来揭示复杂网络的重叠和分层社区结构。这使我们能够更好地描述社区。我们首先证明一对顶点之间的可通信性可以用网络的特征空间来重写。然后提出了一种凝聚聚类算法，以使用可传播性矩阵来发现分层社区。最后，基于彼此连接更紧密的顶点更有可能通过短周期链接的事实，发现这些重叠的顶点具有相应的特征空间。与传统的谱算法相比，我们的算法可以识别重叠社区和分层社区，而不会增加时间复杂度 O(n(3))，其中 n 是网络的大小。此外，我们的算法还可以区分重叠顶点和桥。该方法通过将其应用于一些计算机生成的和现实世界的网络进行了测试。实验结果表明，我们的算法比传统的谱方法能够更准确地揭示社区结构。
Identifying community structure is fundamental for revealing the structure-functionality relationship in complex networks, and spectral algorithms have been shown to be powerful for this purpose. In a traditional spectral algorithm, each vertex of a network is embedded into a spectral space by making use of the eigenvectors of the adjacency matrix or Laplacian matrix of the graph. In this paper, a novel spectral approach for revealing the overlapping and hierarchical community structure of complex networks is proposed by not only using the eigenvalues and eigenvectors but also the properties of eigenspaces of the networks involved. This gives us a better characterization of community. We first show that the communicability between a pair of vertices can be rewritten in term of eigenspaces of a network. An agglomerative clustering algorithm is then presented to discover the hierarchical communities using the communicability matrix. Finally, these overlapping vertices are discovered with the corresponding eigenspaces, based on the fact that the vertices more densely connected amongst one another are more likely to be linked through short cycles. Compared with the traditional spectral algorithms, our algorithm can identify both the overlapping and hierarchical community without increasing the time complexity O(n(3)), where n is the size of the network. Furthermore, our algorithm can also distinguish the overlapping vertices from bridges. The method is tested by applying it to some computer-generated and real-world networks. The experimental results indicate that our algorithm can reveal community structure more precisely than the traditional spectral approaches.