一种基于节点重要度的社团划分算法
2016-04-22吴卫江李国和
吴卫江,周 静,李国和
(中国石油大学(北京) 地球物理与信息工程学院,北京 102200)
一种基于节点重要度的社团划分算法
吴卫江,周静*,李国和
(中国石油大学(北京) 地球物理与信息工程学院,北京 102200)
摘要指出了通过挖掘复杂网络中存在的社团结构,可以分析整个复杂网络的拓扑结构和功能,还可以发现网络中隐藏的规律.为了得到最佳社团划分结构,定义了网络的节点重要度矩阵和聚类矩阵,结合图的特征谱平分法和模块度函数,提出了一种基于节点重要度的社团划分算法(CDNIM).通过在空手道俱乐部、海豚关系网络等多个经典数据集上应用,结果表明:该算法能够有效提高发现社团结构的准确率.
关键词复杂网络; 社团结构; 谱平分; 聚类算法; 模块度
Community Partition Algorithm Based on Node Importance
WuWeijiang,ZhouJing,LiGuohe
(China University of Petroleum-Beijing,College of Geophysics and Information Engineering,Beijing 102200,China)
AbstractThis paper points out that through mining the society existed in complex networks, the topological structure and function of complex networks can be analyzed, and the hidden rules can be found either. In order to get the optimal community structure, node importance matrix and clustering matrix are defined, combined the spectral bisection method based on graph and modularity function, an community partition algorithm (CDNIM) based on node importance is proposed. This algorithm is applied in karate club, dolphin networks, and other classical data sets, the result of experiment shows that this algorithm can effectively improve the accuracy of discovering community structure.
Keywordscomplex networks;society structure;spectral bisection method;clustering algorithm;modularity
在现实世界中,存在着各式各样的网络,如科技网、社会网络、生物网等,它们都可以抽象成复杂网络.小世界[1]和无标度[2]特性是研究复杂网络理论的开创性标志,随着人们对复杂网络的研究不断深入,发现复杂网络的另外一个特性,即社团结构[3]特性.复杂网络中的社团结构表征为:存在于单个社团内部的各个节点之间的边较多,分布比较有地域密集性,而社团之间相互连接的边比较少.这种社团结构暗示着同一社团内的节点具有相同的属性或者是有其他相似的方面.对复杂网络进行社团划分,可以更好地了解现实网络中的内部组织结构:依据复杂网络中划分的各个社团的功能,可以推测出整个网络的实际功能;……