资源描述：
《局部搜索与遗传算法结合的大规模复杂网络社区探测》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第37卷第7期自动化学报Vol.37,No.72011年7月ACTAAUTOMATICASINICAJuly,2011局部搜索与遗传算法结合的大规模复杂网络社区探测金弟1;2刘杰1;2杨博1;2何东晓1;2刘大有1;2摘要基于遗传算法的复杂网络社区探测是当前的研究热点.针对该问题,本文在分析网络模块性函数Q的局部单调性的基础上,给出一种快速、有效的局部搜索变异策略,同时为兼顾初始种群的精度和多样性以达到进一步提高搜索效率的目的,采用了标签传播作为初始种群的产生方法;综上,提出了一个结合局部搜索的遗传算法(Geneticalgorithmwith
2、localsearch,LGA).在基准网络及大规模复杂网络上对LGA进行测试,并与当前具有代表性的社区探测算法进行比较,实验结果表明了文中算法的有效性与高效性.关键词复杂网络,社区探测,网络聚类,遗传算法,局部搜索DOI10.3724/SP.J.1004.2011.00873GeneticAlgorithmwithLocalSearchforCommunityDetectioninLarge-scaleComplexNetworks1;21;21;21;21;2JINDiLIUJieYANGBoHEDong-XiaoLIUDa-YouAbst
3、ractDetectingcommunitiesfromcomplexnetworksbygeneticalgorithmhastriggeredagreatcommoninterest.Forthisproblem,ageneticalgorithmwithlocalsearch(LGA)whichemploysnetworkmodularityQasobjectivefunctionisgiveninthiswork.Ane®ectiveaswellase±cientmutationmethodcombinedwithalocalsearc
4、hstrategyisproposedbasedonourprofoundanalysisonlocalmonotonicityoffunctionQ,meanwhile,alabelpropagationbasedmethodisadoptedtoproducetheaccurateanddiverseinitialpopulation,whichcanfurtherimprovethesearche±ciencyofLGA.TheproposedLGAhasbeentestedonbothbenchmarknetworksandsomela
5、rge-scalecomplexnetworks,andcomparedwithsomecompetitivecommunitydetectionalgorithms.ExperimentalresulthasshownthatLGAishighlye®ectiveande±cientfordiscoveringcommunitystructure.KeywordsComplexnetwork,communitydetection,networkclustering,geneticalgorithm,localsearch现实世界中的许多复杂系
6、统都以复杂网络的形标度特性"是指复杂网络中的结点的度服从幂率分式存在,或者能被转化为复杂网络进行处理,如社会布特征[2];而本文所涉及的聚类特性"(也称社区结网、生物网、Web网络、科技网络等.目前对复杂网构特性)是指复杂网络中普遍存在着同一社区内络基本统计特性的研究已吸引了不同领域的众多研之结点相互连接紧密、而不同社区间之结点相互连究者,复杂网络分析已成为当前最重要的多学科交接稀疏"的特点[3].叉研究领域之一[1¡4].其中,小世界效应"是指复随着应用领域的不同,社区结构具有不同的内杂网络具有短路径长度和高聚类系数的特点[1];无涵
7、,譬如:社会网中的社区代表了具有某些相近特征的人群,生物网络中的功能组揭示了具有相似功能收稿日期2010-07-19录用日期2011-01-12的生物组织模块,Web网络中的文档类簇包含了大ManuscriptreceivedJuly19,2010;acceptedJanuary12,2011量具有相关主题的Web文档,等等[5].复杂网络社国家高技术研究发展计划(863计划)(2006AA10Z245),国家自然科学基金(60773099,60703022,60873149,60973088),模式识别国家区探测(又称网络聚类)的目的就是要探
8、测并揭示出重点实验室开放课题(09-1-1),中央高校基本科研业务费专项资金(200903177),复旦大学智能信息处理上海市重点实验室开放课题(II
