复杂网络基于局部模块度的社团划分方法  

Algorithm for detecting community structures in complex networks

作　　者：刘绍海[1,2] 刘青昆[1] 谢福鼎[1] 安娜[1] 

机构地区：[1]辽宁师范大学计算机与信息技术学院,辽宁大连116029 [2]武警沈阳指挥学院教研部,辽宁沈阳110113

出　　处：《计算机工程与设计》2009年第20期4708-4710,4714,共4页Computer Engineering and Design

基　　金：国家自然科学基金项目(10771092);国家973重点基础研究发展计划基金项目(2004CB318000)

摘　　要：提出了一种基于局部模块度的社团划分算法,该算法的基本思想是将具有最大综合特征值的节点作为初始节点,然后从候选集中找到使局部模块度Q达到最大值时所对应的候选节点,将此节点合并到该社团中,更新候选集合直至Q值不再增加,此时该社团形成。由于算法仅需要利用节点的局部信息,因此时间复杂度很低,并且通过综合特征值,找到聚类中心,从而使得聚类效果大大提高。通过社会学中经典的Zachary网络表明了该算法的可行性,并得到满意的结果。A new method is presented which can detect community structure based on the idea of local modularity measure. The algorithm ftrstly starts from the node which has the max multifesture of nodes, and finds the candidate node from the candidate set which can reach the maximum of the local modularity measure, Q. Secondly, the algorithm merge the node into the community and update the candidate set. At last, clustering results is received. Since this algorithm only requires local information of the complex networks, its time complexity is very low. It can find clustering centers better based on the multifesture value of nodes. Finally, this algorithm is applied to a classical social network, the Zachary network, with satisfactory result, the experiment shows the validity of this method.

关 键 词：社团结构 聚类系数 综合特征值 局部模块度 复杂网络 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]