| 用于社团发现的Girvan-Newman改进算法 |
| |
| 引用本文： | 朱小虎,宋文军,王崇骏,谢俊元.用于社团发现的Girvan-Newman改进算法[J].计算机科学与探索,2010,4(12):1101-1108. |
| |
| 作者姓名： | 朱小虎 宋文军 王崇骏 谢俊元 |
| |
| 作者单位： | 南京大学,计算机软件新技术国家重点实验室,南京,210093;南京大学,计算机科学与技术系,南京,210093 |
| |
| 基金项目： | 国家自然科学基金，国家教育部重点项目，江苏省科技支撑计划 |
| |
| 摘 要： | 为了克服Girvan-Newman算法运行效率的不足,提出了一个基于modularity极值近似的社团发现算法MEA。该算法采用modularity增量作为社团结构的度量,使用贪心策略获得最优社团分划的近似解。通过理论分析,并在实际的数据集上进行实验验证,结果表明MEA算法是快速、有效的。
|
| 关 键 词： | 社会网络分析 社团结构发现 Girvan-Newman算法 贪心策略 |
| 修稿时间： | |
Improved Algorithm Based on Girvan-Newman Algorithm for Community Detection |
| |
| ZHU Xiaohu,SONG Wenjun,WANG Chongjun,XIE Junyuan.Improved Algorithm Based on Girvan-Newman Algorithm for Community Detection[J].Journal of Frontier of Computer Science and Technology,2010,4(12):1101-1108. |
| |
| Authors: | ZHU Xiaohu SONG Wenjun WANG Chongjun XIE Junyuan |
| |
| Affiliation: | 1. National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093, China2. Department of Computer Science and Technology, Nanjing University, Nanjing 210093, China |
| |
| 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. |
| |
| Keywords: | social networks analysis community structure detection Girvan-Newman algorithm greedy strategy |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《计算机科学与探索》浏览原始摘要信息 |
|
点击此处可从《计算机科学与探索》下载全文 |
|
