用于社团发现的Girvan-Newman改进算法

doi:10.3778/j.issn.1673-9418.2010.12.004

计算机科学与探索 ›› 2010, Vol. 4 ›› Issue (12): 1101-1108.DOI: 10.3778/j.issn.1673-9418.2010.12.004

用于社团发现的Girvan-Newman改进算法

朱小虎^1,2, 宋文军^1,2, 王崇骏^1,2+, 谢俊元^1,2

1. 南京大学计算机软件新技术国家重点实验室, 南京 210093
2. 南京大学计算机科学与技术系, 南京 210093

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2010-12-01 发布日期:2010-12-01
通讯作者: 王崇骏

Improved Algorithm Based on Girvan-Newman Algorithm for Community Detection

ZHU Xiaohu^1,2, SONG Wenjun^1,2, WANG Chongjun^1,2+, XIE Junyuan^1,2

1. National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093, China
2. Department of Computer Science and Technology, Nanjing University, Nanjing 210093, China

Received:1900-01-01 Revised:1900-01-01 Online:2010-12-01 Published:2010-12-01
Contact: ZHU Xiaohu1,2, SONG Wenjun1,2, WANG Chongjun1,2+, XIE Junyuan1,2

摘要/Abstract

摘要： 为了克服Girvan-Newman算法运行效率的不足, 提出了一个基于modularity极值近似的社团发现算法MEA。该算法采用modularity增量作为社团结构的度量, 使用贪心策略获得最优社团分划的近似解。通过理论分析, 并在实际的数据集上进行实验验证, 结果表明MEA算法是快速、有效的。

关键词: 社会网络分析, 社团结构发现, Girvan-Newman算法, 贪心策略

Abstract: To improve the efficiency of Girvan-Newman(G-N) algorithm, a community detection algorithm named modularity extreme approximation (MEA) is given. MEA algorithm uses the increment of modularity as the meas-ure for community structure and finds the solution with a greedy strategy. The theoretical analysis and experimental results show the MEA algorithm is more effective and faster than the G-N algorithm.

Key words: social networks analysis, community structure detection, Girvan-Newman algorithm, greedy strategy

中图分类号:

TP311

朱小虎1,2 , 宋文军1,2 , 王崇骏1,2+ , 谢俊元1,2 . 用于社团发现的Girvan-Newman改进算法[J]. 计算机科学与探索, 2010, 4(12): 1101-1108.

ZHU Xiaohu^1,2, SONG Wenjun^1,2, WANG Chongjun^1,2+, XIE Junyuan^1,2. Improved Algorithm Based on Girvan-Newman Algorithm for Community Detection[J]. Journal of Frontiers of Computer Science and Technology, 2010, 4(12): 1101-1108.

[1]	刘文星, 范敏, 李金海. 网络形式背景下的社区划分方法研究[J]. 计算机科学与探索, 2021, 15(8): 1441-1449.
[2]	江淼淼，孙更新，宾晟. 多关系社交网络中社团结构发现算法[J]. 计算机科学与探索, 2019, 13(7): 1134-1144.
[3]	张云飞，李劲，岳昆，罗之皓，刘惟一. 关联影响力传播最大化方法[J]. 计算机科学与探索, 2018, 12(12): 1891-1902.
[4]	王虹旭，吴斌，刘旸. 基于Spark的并行图数据分析系统[J]. 计算机科学与探索, 2015, 9(9): 1066-1074.
[5]	徐彬，杨丹，张昱，李封，高克宁. 基于学习者行为特征的MOOCs学习伙伴推荐[J]. 计算机科学与探索, 2015, 9(1): 71-79.
[6]	徐彬，杨丹，张昱，李封，高克宁. 面向微博用户标签推荐的关系约束主题模型[J]. 计算机科学与探索, 2014, 8(3): 288-295.
[7]	何镝1 , 彭智勇2 , 梅晓茸2 . Web社区管理研究综述[J]. 计算机科学与探索, 2011, 5(2): 97-113.
[8]	钱铁云1+ ，李青1，2 ，许承瑜1 . 面向科技主题发展分段的社区核心圈技术[J]. 计算机科学与探索, 2010, 4(2): 170-179.
[9]	王翼+,吴斌,杨胜琦. CommTracker：一种基于核心的社区演化跟踪算法[J]. 计算机科学与探索, 2009, 3(3): 282-292.

用于社团发现的Girvan-Newman改进算法

Improved Algorithm Based on Girvan-Newman Algorithm for Community Detection

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 9

编辑推荐

Metrics