复杂网络中的社团结构发现方法

Community Structure Detection in Complex Networks

社团结构是真实复杂网络异质性与模块化特性的反映。深入研究网络的社团结构有助于揭示错综复杂的真实网络是怎样由许多相对独立而又互相关联的社区形成的,使人们更好地理解系统不同层次的结构和功能,具有广泛的实用价值。总结了目前常用的社区发现方法,包括经典的GN算法、模块度优化算法、基于网络动力学的方法以及统计推断方法;用社区划分基准测试网络Zachary对上述算法进行了实验,对这几类算法的时间复杂度和优缺点进行了比较分析。最后,对复杂网络的社区结构发现算法的研究进行了展望。

Many networks of interest in the sciences,including social networks, computer networks, are found to divide naturally into communities or modules. Community structure can reflect the heterogeneity and modularity of the real- world networks. Finding the communities within a network is a powerful tool for understanding the structure and the functioning of the network. We reviewed some most popular methods for detecting community, including GN algorithm, modularity-based methods,dynamic algorithms, and the methods based on statistical inference. We used the standard testing network Zachary to test the above-mentioned methods, and analysed the time complexity and conclude the advantages and disadvantages of this methods. Finally, prospected of study on community detection methods.