基于FCM的复杂网络重叠社团结构发现算法  

Fast Partitioning Algorithm for Detecting Communities in Complex Networks

作　　者：潘惠勇[1] 王鹏[2] 张慧乐 

机构地区：[1]中原工学院计算机学院,河南郑州450007 [2]复旦大学信息科学与工程学院,上海200433 [3]河南联通漯河分公司,河南漯河462000

出　　处：《微电子学与计算机》2011年第12期111-114,共4页Microelectronics & Computer

基　　金：国家自然科学基金项目(91024121)

摘　　要：复杂网络中的社团结构发现是对网络数据集进行数据挖掘的普遍性问题.针对网络中大量存在的重叠社团现象,提出了基于FCM的发现重叠社团结构算法,并进一步在NG模块度的基础上,给出了评价重叠社团结构的模块度函数.算法首先将网络的节点映射成欧氏空间的节点,再以此做模糊聚类得到各重叠社团结构,根据模块度函数选择最佳重叠社团结构.最后,在经典网络上的实验结果表明,算法能够得到满意度高的重叠社团结构,而且时间复杂度较低.Detection of overlapping communities in a complex network is a general problem in data mining of network data sets.In view of the phenomenon of a lot of overlapping communities in real networks,we devise the novel algorithm of detection of overlapping community based on Fuzzy c-means clustering.Further more,we propose the improved modularity to evaluate the overlapping community structure based on NG modularity.Firstly,network nodes were mapped into the nodes in Euclidean space.Secondly,the nodes were clustered by Fuzzy c-means algorithm.Thirdly,the best overlapping community was selected by computing the function of improved modularity.Finally,the developed algorithm has been tested on two common real-world networks.Computational results demonstrate that the improved modularity and the algorithm have better partitioning ability and lower time complexity.

关 键 词：复杂网络 社团发现 FCM聚类 模块度 

分 类 号：N94[自然科学总论—系统科学]