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

ISSN 1673-9418 CODENJKYTA8
E-mail:fcstvip.163.com
Journal of Frontiers of Computer Science and Technology
http://www.ceaj.org
1673-9418/2010/(04(12)-1101-08
Tel:+86-10-51616056
DOl:10.3778jiss,1673-9418.2010.12.004
用于社团发现的 Girvan-newman改进算法
朱小虎2,宋文军2,王崇骏2,谢俊元2
1.南京大学计算机軟件新技术国家重点实验室,南京210093
2.南京大学计算机科学与技术系,南京210093
Improved Algorithm Based on Girvan-newman Algorithm for Community Detection
ZHU Xiaohu 2, SONG Wenjun"=, WANG Chongjun?", XIE Junyuan 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
Correspondingauthor:E-mail:chjwang(@nju.edu.cn
ZHU Xiaohu, SONG wenjun, WANG Chongjun, et al. Improved algorithm based on Girvan-newman algo
rithm for community detection. Journal of Frontiers of Computer Science and Technology, 2010, 4(12)
1101-1108
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
摘要:为了克服( Girvan- Newman算法运行效率的不足,提出了一个基于 modularityⅳ极值近似的社团发现
算法MEA。该算法采用 modularity增量作为社团结构的度量,使用贪心策略获得最优社团分划的近似解。
通过理论分析,并在实际的数据集上进行实验验证,结果表明MEA算法是快速、有效的。
The National Natural Science Foundation of China under Grant No.60503021,60721002,60875038(国家自然科学基金); the Key
Research Projects of the Ministry of Education of China under Grant No.108151(国家教育部重点项目); the Science and Tech
nology Support Foundation of Jiangsu Province under Grant No.BF2009142(江苏省科技支撑计划
Received 2010-04, Accepted 2010-06
1102
Journal of Frontiers of Computer Science and7 echnology计算机科学与探索
2010,4(12)
关键词:社会网络分析;社团结发现; Girvan- Newman算法;贪心策略
文献标识码:A中图分类号:TP311
1引言
社会网络这个概念强调其中每个点都与其他点
在社会网络巾,兴趣爱好的共同点会导致社有或多或少的关系。社会网络分析者建立这些关
会网络中的某些个体形成一个团体,网络也随之系的模型,力图描述群体关系的结构,研究这种
划分成一系列社闭。社团结构作为社会网络拓扑结构对群体功能或者群体内部个体的影响。
结构的重要方面,对其研究有着重要的应用价
社会网络中的点可以是一个学院、学校,也
值。社团发现既可以使人们从社团结构的整体功可以是一个城市、国家等,当然也包括互联网
能得到其中个体在网络中的作用,又可以从整体每一个虚找社区成员或康找社区本身。社会网络
上把握整个网络的结构和木米走向。
可以是单一实体作为元素的集合,也可以是多实
目前,比较有效的社团发现方法是由 Girvan
体集合作为元素的集合。点是通过各种关系联系
和 Newman提出来的边删除算法,简称为G-N算
在一起的。在社会网络分析中,一些得到广泛研
法。他们通过移除网络中的边来将整个网络划分究的关系有:隶属关系,如属于某一个组织;行
为上的互动关系,如行动者之间的自然交往,如
成为合适的社团结构,运用此算法可以将原来的
谈话、拜访等。
网络分割成为任意数日的社团。但是它有两个不
近年来,越来越多的人开始从数学或是物理
足之处:首先它没有给出明确的标准来说明何时
学的角度来研究社会?络,通过数学中的方法找
停止循环过程;另一方面其时间复杂性过高。而
到一些度量来反映当前社会?络的统计特征,如
这里的工作就是通过引进一种终止循环的标准。小世界效应、度服从特定的分布等。这些统计特
及贪心策略来尝试解决这两个不足,进而提出一征是社会网络区别于随机网络的主要标志,并且
种发现近似最优社团结构的 modularity extreme可以反映网络中所隐藏的信息,甚至影响网络的
approximate(MEA)算法。
形成。
本文结构如下:第2章介绍社会网络和社团22社团结构
结构的相关内容,并简要讨论了GN社团发现算
社会网络中社团结构的精确定义有多种,早
法和社团结构的度量;第3章对G-N算法进行改在1994年,文献]就提出了基于图的准团的局部
进;第4章是实验结果及分析;第5章总结全文。定义;近期有文献3]提出的基于空模型( null model
的全局定义,此定义直接给出了日前常用的社团
2社闭结构发现
结构评价标准;还有目前不太常用的基于顶点相
2.1社会网络
似性(的社团结构的定义等。以下所给出的是其
社会网络的研究起源于20世纪二三十年代中最易