一个基于中心度的社团结构发现新算法

• 作者: 戴爱明 王立敏 高学东
• 来源期刊: 计算机应用研究
• 关键词: 社团结构 节点中心度 GN算法 DCGN算法
• 年，卷（期）: 2011,（8）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 2909-2911
• 分类号: TP393
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2011.08.030

摘要

针对GN算法在社团结构发现中时间复杂度高等问题,提出一种基于中心度的GN改进算法(DCGN).该算法根据节点中心度以及节点之间的最短路径首先确定社团结构中心节点集,然后逐步删除社团结构中心节点之间的最大边介数连边,完成社团结构划分.DCGN算法避免了GN算法边介数计算开销大的问题,算法的时间复杂度约为D(cmn),其中c为常数,n为网络成员数,m为网络连边数.将DCGN和GN算法同时应用到Za-chary网络及计算机随机生成网络中并进行了比较.实验结果表明,所提出的DCGN算法在运行效率和效果方面较之GN算法均具有一定的优势.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	高学东	北京科技大学经济管理学院	143	1129	18.0	24.0
2	戴爱明	北京科技大学经济管理学院	14	62	5.0	7.0
6	王立敏	北京科技大学中国教育经济信息网管理中心	7	68	5.0	7.0