正在加载图片...
D0I:10.13374/1.issnl00103.2009.0L.013 第31卷第1期 北京科技大学学报 Vol.31 No.1 2009年1月 Journal of University of Science and Technology Beijing Jan.2009 基于最小社团链接度增量的社团结构挖掘算法 王立敏2)高学东)武森) 1)北京科技大学经济管理学院，北京1000832)北京科技大学中国教育经济信息网管理中心，北京100083 摘要针对复杂网络社团结构挖掘算法复杂度高的问题，定义了一个衡量局部社团结构的指标，提出了一种基于最小社团 链接度增量的社团结构挖掘算法·本算法的时间复杂度为O(k),其中d为网络的平均节点度数，k为搜索的节点数.为了 验证本算法的性能和计算的准确性，把本算法与一种经典的挖掘局部社团结构方法一Clauset算法，进行了比较.实验结果 表明：本算法抽取的社团结构与Clauset算法相比基本一致，但在性能上有了显著提高 关键词复杂网络；链接度：社团结构：挖掘算法 分类号TP393 Mining algorithm of community structure based on the minimal increment of link degree of a community WANG Li-min2.GAO Xue-dong),WU Sen) 1)School of Economics and Management.University of Science and Technology Beijing Beijing 100083.China 2)Management Center of China Education Economy Information Net,University of Science and Technology Beijing Beijing 100083.China ABSTRACI A measure of local community structure was defined,and an mining algorithm of local community structure based on the minimal increment of link degree of a community was presented for resolving the time complexity problems of finding local com- munity structure in complex networks.The algorithm ran in time 0(kd)for general graphs,where d is the mean degree and k is the number of vertices to be explored.In order to determine its performance and calculation precision,the algorithm was compared with the classical local community identification approach,Clauset algorithm.Experimental results show that mining results of the al- gorithm are as effective as those of Clauset algorithm on the whole,and the algorithm is much faster than Clauset algorithm. KEY WORDS complex network:link degree:community structure:mining algorithm 复杂网络的结构描述已经成为物理学家关注的 近几年，研究者提出许多用于挖掘网络社团结 一个热点，目前，研究者除了研究网络的统计特征 构的技术，其中比较著名的是由Newman和Girvan 和动力学特征外，越来越重视社团的结构]，试图 提出基于边介数的算法[2，刃，此算法已经被用于各 揭示看上去错综复杂的网络是怎样由相对独立又相 种网络中，但算法运行的时间复杂度为O(nm), 互交错的社团组成的.这对于理解网络的结构和功 其中n和m分别为网络中的节点数和边数，此后， 能特性有着深刻的理论意义和现实意义， 一些学者们又提出了许多不同的算法[山，但是这 2002年，首次由Girvan和Newman提出了复 些算法的前提条件是需要知道所研究网络的整体结 杂网络的社团结构概念[]，社团就是网络中的节点 构，对于许多规模比较大而且具有动态特征的网络 集合·社团内节点之间具有比较紧密的链接，而社 来说，如万维网，要完全了解网络的整体结构不太可 团之间节点的链接相对比较松散，目前，尽管社团 能，因此这个要求就使得许多算法的应用受到了限 还没有一个统一的、量化的定义，但这种定义已经被 制，更重要的是，在实际应用中，有时并不需要了解 广大学者所接受 整个网络的社团结构，只是需要知道某个局部的社 收稿日期：2008-01-08 基金项目：教育部新世纪优秀人才支持计划资助项目(N。·NCET一05O097) 作者简介：王立敏(l971一)，女，博士研究生，E-mail:wanglimin@cee~ustb.ed:cn:高学东(1964一)，男，教授，博士生导师基于最小社团链接度增量的社团结构挖掘算法 王立敏12） 高学东1） 武 森1） 1） 北京科技大学经济管理学院北京100083 2） 北京科技大学中国教育经济信息网管理中心北京100083 摘 要 针对复杂网络社团结构挖掘算法复杂度高的问题定义了一个衡量局部社团结构的指标提出了一种基于最小社团 链接度增量的社团结构挖掘算法．本算法的时间复杂度为 O（ kd）其中 d 为网络的平均节点度数k 为搜索的节点数．为了 验证本算法的性能和计算的准确性把本算法与一种经典的挖掘局部社团结构方法———Clauset 算法进行了比较．实验结果 表明：本算法抽取的社团结构与 Clauset 算法相比基本一致但在性能上有了显著提高． 关键词 复杂网络；链接度；社团结构；挖掘算法 分类号 TP393 Mining algorithm of community structure based on the minimal increment of link degree of a community W A NG L-i min 12）GA O Xue-dong 1）W U Sen 1） 1） School of Economics and ManagementUniversity of Science and Technology BeijingBeijing100083China 2） Management Center of China Education Economy Information NetUniversity of Science and Technology BeijingBeijing100083China ABSTRACT A measure of local community structure was definedand an mining algorithm of local community structure based on the minimal increment of link degree of a community was presented for resolving the time complexity problems of finding local community structure in complex networks．T he algorithm ran in time O（ kd） for general graphswhere d is the mean degree and k is the number of vertices to be explored．In order to determine its performance and calculation precisionthe algorithm was compared with the classical local community identification approachClauset algorithm．Experimental results show that mining results of the algorithm are as effective as those of Clauset algorithm on the wholeand the algorithm is much faster than Clauset algorithm． KEY WORDS complex network；link degree；community structure；mining algorithm 收稿日期：2008-01-08 基金项目：教育部新世纪优秀人才支持计划资助项目（No．NCET—05—0097） 作者简介：王立敏（1971—）女博士研究生E-mail：wanglimin＠cee．ustb．edu．cn；高学东（1964—）男教授博士生导师 复杂网络的结构描述已经成为物理学家关注的 一个热点．目前研究者除了研究网络的统计特征 和动力学特征外越来越重视社团的结构［1—5］试图 揭示看上去错综复杂的网络是怎样由相对独立又相 互交错的社团组成的．这对于理解网络的结构和功 能特性有着深刻的理论意义和现实意义． 2002年首次由 Girvan 和 Newman 提出了复 杂网络的社团结构概念［6］社团就是网络中的节点 集合．社团内节点之间具有比较紧密的链接而社 团之间节点的链接相对比较松散．目前尽管社团 还没有一个统一的、量化的定义但这种定义已经被 广大学者所接受． 近几年研究者提出许多用于挖掘网络社团结 构的技术其中比较著名的是由 Newman 和 Girvan 提出基于边介数的算法［27］．此算法已经被用于各 种网络中但算法运行的时间复杂度为 O（ n 2m） 其中 n 和 m 分别为网络中的节点数和边数．此后 一些学者们又提出了许多不同的算法［8—11］但是这 些算法的前提条件是需要知道所研究网络的整体结 构．对于许多规模比较大而且具有动态特征的网络 来说如万维网要完全了解网络的整体结构不太可 能．因此这个要求就使得许多算法的应用受到了限 制．更重要的是在实际应用中有时并不需要了解 整个网络的社团结构只是需要知道某个局部的社 第31卷 第1期 2009年 1月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol．31No．1 Jan．2009 DOI:10．13374／j．issn1001－053x．2009．01．013