一种面向大型网络的快速随机化社区挖掘算法

寻找网络的社区结构对于理解真实网络的自组织机制、可视化大网络有重要的作用.然而,现有的社区挖掘算法由于性能较低,还难以处理大型网络,特别是有着百万顶点的网络.然而,百万规模的大网络却在越来越多的真实应用中大量涌现,这对于高效的有效社区识别算法提出新的需求.为此,一种新颖的随机算法被提出,能够在接近线性时间内,从大型网络上高效地挖掘质量较高的网络社区:新算法的核心思路是在每一随机步骤中对网络中的顶点进行基于深度优先顺序的编码,这样的编码有助于有效地识别社区之间的边.最后,通过针对模拟网络和真实网络的一系列实验验证了新算法的高效性和有效性.

Fast Randomized Algorithm for Community Detection in Large Networks

Detecting community structure is fundamental for uncovering the organization principle of real networks.Existing community detection algorithms are not tractable for large graphs,in particular the graphs with millions of nodes.However,proliferation of large-scale real network data demands new methods to identify communities efficiently and effectively.For this purpose,a randomized algorithm is proposed to efficiently mine community structure with high quality from large networks.Each randomized step of the new algorithm is to renumber the vertices by a DFS order.Such DFS renumbering is helpful to identify the edges between communities.Finally,the effectiveness and efficiency of the new algorithm are shown by experimental results on both synthetic and real networks.