复杂网络的一种快速局部社团划分算法

为了快速准确地寻找大规模复杂网络的社团结构,文中基于节点度优先的思想,提出了一种新的寻找复杂网络中的局部社团结构的启发式算法.该算法的基本思想是从待求节点出发,基于节点的度有选择性的进行广度优先搜索,从而得到该节点所在的局部社团结构.由于该算法仅需要利用到节点的局部信息,因此时间复杂度很低,达到了线性的时间复杂度.将该算法应用于社会学中经典的Zachary网络,获得了满意的结果.最后,还分析了如何对该算法加以改进以进一步提高准确度.

A Fast Algorithm for Detecting Local Community Structure in Complex Networks

In order to detect community structure in large - scale complex networks fast and correctly, a new heuristic algorithm based on the idea of degree preference is proposed in this work. Started from the node under consideration, this new algorithm introduces a degree - based alternative breadth - first search to get the local community structure of a node. Since this algorithm only requires local information of the node, its time complexity is linear and thus is very low. This algorithm is applied to a classical social network, the Zachary network, with satisfactory result. Finally, an improved algorithm for further enhancing the accuracy is discussed.