首页 | 官方网站   微博 | 高级检索  
     

一个基于中心度的社团结构发现新算法*
引用本文:戴爱明,高学东,王立敏b.一个基于中心度的社团结构发现新算法*[J].计算机应用研究,2011,28(8):2929-2911.
作者姓名:戴爱明  高学东  王立敏b
作者单位:1. 北京科技大学 经济管理学院,北京100083;南昌航空大学制造业发展研究所,南昌330063
2. 北京科技大学 经济管理学院,北京,100083
3. 北京科技大学 中国教育经济信息网管理中心,北京,100083
基金项目:国家自然科学基金资助项目(70962008);国家航空科学基金资助项目(2009ZG56022)
摘    要:针对GN算法在社团结构发现中时间复杂度高等问题,提出一种基于中心度的GN改进算法(DCGN)。该算法根据节点中心度以及节点之间的最短路径首先确定社团结构中心节点集,然后逐步删除社团结构中心节点之间的最大边介数连边,完成社团结构划分。DCGN算法避免了GN算法边介数计算开销大的问题,算法的时间复杂度约为O(cmn),其中c为常数,n为网络成员数,m为网络连边数。将DCGN和GN算法同时应用到Zachary网络及计算机随机生成网络中并进行了比较。实验结果表明,所提出的DCGN算法在运行效率和效果方面较之GN算

关 键 词:社团结构    节点中心度    GN算法    DCGN算法

New algorithm of detecting community structure based on degree centrality
DAI Ai-ming,GAO Xue-dong,WANG Li-minb.New algorithm of detecting community structure based on degree centrality[J].Application Research of Computers,2011,28(8):2929-2911.
Authors:DAI Ai-ming  GAO Xue-dong  WANG Li-minb
Affiliation:(1.a.School of Economics & Management, b.Management Center of China Education Economy Information Net, University of Science & Technology Beijing, Beijing 100083, China; 2.Institute of Manufacture Industry Development, Nanchang Hangkong University, Nancha
Abstract:Using GN algorithm to detect the community structure,there will be high time complexity.This paper proposed a new GN algorithm based on degree centrality(DCGN).According to node degree centrality and the shortest path among them,the algorithm first confirmed the community structure central nodes,then deleted edges with the biggest betweenness among the community structure central nodes by step,to finish the community structure dividing.This algorithm got rid of high cost of parameter calculating when using ...
Keywords:community structure  degree centrality  GN algorithm  DCGN algorithm
本文献已被 CNKI 万方数据 等数据库收录!
点击此处可从《计算机应用研究》浏览原始摘要信息
点击此处可从《计算机应用研究》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司    京ICP备09084417号-23

京公网安备 11010802026262号