第11期2012年11月电子学报Vol.40No.11Nov.2012ACTAELECTRONICASINICA社会网络中基于局部信息的边社区挖掘磊1,2,金杰1,2,王崇骏1,2,谢俊元1,2潘(1.南京大学计算机软件新技术国家重点实验室,江苏南京210093;2.南京大学计算机科学与技术系,江苏南京210093)摘要:近年来,随着社交网络的发展,许多重叠社区挖掘算法被提出来.传统的方法都是将节点作为研究对象,而最近的一些研究表明,以边为研究对象的边社区挖掘方法相对于点社区挖掘方法来说具有更加明显的优势.因此,我们提出了基于局部边社区的挖掘算法(LLCM),利用网络中的局部信息去挖掘边社区结构.给定一条初始的边,通过不断最大化一个适应度函数来获取该边所在的局部社区,而这条初始的边可以预先通过一些排序算法进行选择.算法经过在计算机生成网络和真实网络上测试,并且同其他边社区挖掘算法进行了比较,实验结果表明LLCM算法关键词:社区挖掘;边社区;局部社区:文献标识码::TP391A037222112(2012)1122255209电子学报URL:://wwejournal.org.cnDOI:10.3969/j.issn.037222112.2012.11.018DetectingLinkCommunitiesBasedonLocalInformationinSocialNetworksPANLei1,2,JINJie1,2,WANGChong2jun1,2,XIEJun2yuan1,2(1.StateKeyLaboratoryforNovelSoftwareTechnology,Nan激ngUniversity,Nan激ng,激angsu210093,Abstract:Recentyearshaveseenthedevelopmentofonlinesocialnetworks.Manyalgorithmshavebeenproposedthatareabletoassigneachnodetomorethanasinglecommunity.Thetraditionalapproacheswerealwaysfocusingonthenodecommunity,whilesomerecentstudieshaveshowngreatadvantageoflinkcommunityapproachwhichpartitionslinksinsteadofnodesintocom2munities.Inthispaper,wepresentanovelalgorithmLLCM(locallinkcommunityminingalgorithm)fordiscoveringlinkcommuni2tiesinnetworks.Alocallinkcommunitycanbedetectedbymaximizingalocallinkfitnessfunctionfromaseedlink,whichwasrankedpreviously.TheproposedLLCMalgorithmhasbeentestedonbothsyntheticandrealworldnetworks,andithasbeencom2paredwithotherlinkcommunitydetectingalgorithms.TheexperimentalresultsshowedLLCMachievessignificantimprovementonlinkcommunitystructure.Keywords:communitydetection;linkcommunity;localcommunity5,67法,基于电阻器网络的Wu2Huberman算法,基于RandomWalk相似度的算法8,9.而近年来随着Face2book、Twitter等社交网站的崛起,这一领域的关注度已大大提升,经过许多学者的不断研究,现在已经有了一些代表性的研究成果:GN算法10,11,FastNewman算法12,Radicchi快速分裂算法13,Duch的极值优化算法14,Guimera的基于模拟退火的GA算法15,以及许多基于模块度的优化算法,这种方法将社区挖掘问题转化为1引言挖掘社区结构已经成为一个具有普遍意义的问题,在计算机科学、数学、物理、生物以及社会学等领域都有着广泛的应用,例如:web社区挖掘、社交网络分析、犯罪网络分析、蛋白质交互网络分析、新陈代谢网络分析、基因生物网络分析,还有客户关系挖掘和在线行为分析等,因而在国内外引起学者们的不断关注1～3.从上世纪70年代开始,子图分割和社区挖掘问题逐渐成为图挖掘和社会网络分析领域关注的重点,如Kernighan2Lin的二分算法4,基于Laplace图特征值的谱平分算收稿日期:2011212206;修回日期:2012204212基金项目:国家自然基金(No.60503021,No.60721002,No.60875038,No.61105069);江苏省科技支撑计划(No.RE2010180,No.BE2011171);南京大学研究生创新基金(No.2011CL07)---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---theory):Palla的CPM算法18,TSEvans的CliqueGraph19,基于极大子团合并的EAGLE算法20.另一类是基于局部信息的方法,其中代表性的算法有:Blondel示边集合.社区发现的目的就是找出网络中符合一定条件的一些集合,这是一个NP2hard问题.本文将社区看作是网络中一些边组成的集合,我们的分析对象是网络中的边,那么将相似的边聚集在一个社区中就是边社区挖掘的目的.211社区的基本定义至今为止还没有一个被公认的社区定义,一个比较...