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

Improved Algorithm Based on Girvan-Newman Algorithm for Community Detection

作　　者：朱小虎[1,2] 宋文军[1,2] 王崇骏[1,2] 谢俊元[1,2] 

机构地区：[1]南京大学计算机软件新技术国家重点实验室,南京210093 [2]南京大学计算机科学与技术系,南京210093

出　　处：《计算机科学与探索》2010年第12期1101-1108,共8页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金No.60503021;60721002;60875038;国家教育部重点项目No.108151;江苏省科技支撑计划No.BE2009142~~

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

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]