基于贪婪优化技术的网络社区发现算法研究-论文.pdf

《基于贪婪优化技术的网络社区发现算法研究-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第4期电子学报V01．42No．42014年4月ACTAEII：TRONICASINICAApr．2014基于贪婪优化技术的网络社区发现算法研究冷作福(烟台市电化教育馆，山东烟台264003)摘要：社区发现问题是复杂网络研究的热点问题．基于优化模块度Q函数的方法例如CNM，BGLL等是一类经典的应用广泛的网络社区发现方法．但是已有研究发现，该类方法存在分辨率的问题，即当大规模网络中存在较小社区的情况下这类方法的效果不佳．近来，针对Q函数存在的问题，有研究者证明了另一个有效的目标函数surprise不存在分辨率的问题．但是目前没有直接优化该函数的有效算法，因此，提出一种基于贪婪思想的局部优

2、化surprise函数的社区发现算法，该方法同样不存在分辨率的问题，而且算法不需要指定社区的个数．实验结果表明该方法鲁棒性好，精度优于其它经典的方法例如CNM，BGIL和Ⅱ，A．关键词：复杂网络；礼区发现；模块度函数；surprise中图分类号：N94；TP393文献标识码：A文章编号：0372-2112(2014)04—0723—07电子学报Ul也：http：／／www．ejou~．org．caIX)I：10．3969／j．issn．0372—2112．2014．04．016CommunityDetectioninComplexNetworksBasedonGreedyOptimiza

3、tionIENGZuo．fu(YantaiCenterforEducationalTechnology，Yantai，Shanabng264003，China)Abstract：Insocialnetwork，theimportantandcrucialproblemiscommunitydetection．Classicalmodularityfunctionopti-mizafionapproachessuchasCNMandBGLLalewidelyusedmethodsforidentifyingcommunitieswhichalequiteefficient．Aswehave

4、known，modularityfunction(Q)sufersfromitsresolutionlimit．Recently，surprisefunction(S)Wasproposedandexperimen—tallyprovedtobebetterthanQfunction．However，uptoFlOW，thereisnotanymethodwhichisbasedondirectsu~senlatd／~za—don．Inthispaper，anefficientcommunitydetectionalgorithmwhichisbasedongreedysurpriseo

5、ptimizationisproposedanddoesnotsuferfromaresolutionlimit．TheFlewmethoddoesnotneedcommunitynumberK．Testresultsonexperimentalnetworksshowthatourmethodisrobust，notsensitivetonoisesandhasbetterperformances．Kaywords：complexnetwork；communitystructure；modularityfunction；surprise表了不同的意义，例如在生物学系统中，一个社区可以1

6、引言代表一个组织的功能单位；在生态学系统中，一个社区近年来，复杂网络社区发现问题逐渐成为人们研究可以代表一个生态子系统；在社会学系统中，一个社区的热点问题．复杂网络社区的多样性以及其结构和特征可以代表受到社会各种因素影响的一类个体或者一个的复杂性使得研究者对于社区发现的研究成为一项具团体，该类个体或者团体具备共有的属性和特征等等．有挑战性的基础性研究课题之一．大量的研究发现，复网络社区发现任务旨在挖掘出网络中的这种社区结构．杂网络具有复杂的内部结构和结构特征多样性，比如小复杂网络社区发现的研究对于分析复杂网络的拓扑结世界特性⋯1、无尺度特性_2]以及模块性_3J等等．其中，网构、理解复杂

7、网络的功能、发现复杂网络中的隐藏规律络的模块性是指网络中的节点具有聚类的特性，表现为以及预测复杂网络的行为不仅具有十分重要的理论意网络中的节点呈现出“模块”结构，即“社区结构”．社区义，而且具有广泛的应用前景，目前已被应用于生物蛋结构具有社区内部节点之间连接紧密、社区之间的节点白质网络分析和功能预测、人类疾病网络分析和预测、连接稀疏的特点．在实际的社会网络中，不同的社区代社会网络链接分析和预测、生物新陈代谢网络分析、基收稿日期：20