基于多目标优化的网络社区发现方法

软件学报ISSN1000-9825,CODENRUXUEWE-mail:[e-mail],2013,24(9):2062−2077[doi:10.3724/SP.J.1001.2013.04400]©中国科学院软件研究所版权所有.Tel/Fax:[phone]基于多目标优化的网络社区发现方法∗黄发良1,张师超2,朱晓峰2,31(福建师范大学软件学院,福建福州350007)2(广西师范大学计算机科学与信息工程学院,广西桂林541000)3(SchoolofInformationTechnologyandElectricalEngineering,UniversityofSouthernQueensland,Australia)通讯作者:黄发良,E-mail:[e-mail]摘要:社区发现是复杂网络挖掘中的重要任务之一,在恐怖组织识别、蛋白质功能预测、舆情分析等方面具有重要的理论和应用价值.但是,现有的社区质量评判指标具有数据依赖性与耦合关联性,而且基于单一评判指标优化的网络社区发现算法有很大的局限性.针对这些问题,将网络社区发现问题形式化为多目标优化问题,提出了一种基于多目标粒子群优化的网络社区发现算法MOCD-PSO,它选取模块度Q、最小最大割MinMaxCut与轮廓(silhouette)这3个指标进行综合寻优.实验结果表明,MOCD-PSO算法具有较好的收敛性,能够发现分布均匀且分散度较高的Pareto最优网络社区结构集,并且无论与单目标优化方法(GN与GA-Net)相比较,还是与多目标优化算法(MOGA-Net与SCAH-MOHSA)相比较,MOCD-PSO算法都能在无先验信息的条件下挖掘出更高质量的网络社区.关键词:复杂网络;社区挖掘;多目标粒子群优化中图法分类号:TP181文献标识码:A中文引用格式:黄发良,张师超,朱晓峰.基于多目标优化的网络社区发现方法.软件学报,2013,24(9):2062−2077.英文引用格式:HuangFL,ZhangSC,ZhuXF.Discoveringnetworkcommunitybasedonmulti-objectiveoptimization.RuanJianXueBao/JournalofSoftware,2013,24(9):2062−2077(inChinese).(FacultyofSoftware,FujianNormalUniversity,Fuzhou350007,China)2(CollegeofComputerScienceandInformationTechnology,GuangxiNormalUniversity,Guilin541000,China)3(SchoolofInformationTechnologyandElectricalEngineering,UniversityofSouthernQueensland,Australia)Correspondingauthor:HUANGFa-Liang,E-mail:[e-mail]:Communitydiscoveryisanimportanttaskinminingcomplexnetworks,andhasimportanttheoreticalandapplicationvalueintheterroristorganizationidentification,proteinfunctionprediction,publicopinionanalysis,etc.However,existingmetricsusedtomeasurequalityofnetworkcommunitiesaredatadependentandhavecouplingrelations,andthecommunitydiscoveryalgorithmsbasedonoptimizingjustonemetrichavealotoflimitations.Toaddresstheissues,thetasktodiscovernetworkcommunitiesisformalizedasamulti-objectiveoptimizationproblem.Analgorithm,MOCD-PSO,isusedtodiscovernetworkcommunitiesbasedonmulti-objectiveparticleswarmoptimization,whichconstructsobjectivefunctionwithmodularityQ,MinMaxCutandsilhouette.TheexperimentalresultsshowthattheproposedalgorithmhasgoodconvergenceandcanfindParetooptimalnetworkcommunitieswithrelativelywelluniform∗基金项目:国家自然科学基金(61170131,61263035);澳大利亚ARC(DP0985456);国家高技术研究发展计划(863)(2012AA011005);国家重点基础研究发展计划(973)(2013CB329404);教育部人文社会科学研究青年基金(12YJCZH074);福建师范大学优秀青年骨干教师培养基金(fjsdjk2012082);科学计算与智能信息处理广西高校重点实验室开放基金(GXSCIIP201212)收稿时间:2012-10-19;修改时间:2013-01-21;定稿时间:2013-03-22;jos在线出版时间:2013-04-27CNKI网络优先出版:2013-04-2715:35,黄发良等:基于多目标优化的网络社区发现方法2063anddispersivedistribution.Inaddition,comparedwiththeclassicalalgorithmsbasedonsingleobjectiveoptimization(GN,GA-Net)andmulti-objectiveoptimization(MOGA-Net,SCAH-MOHSA),theproposedalgorithmrequiresnoinputparametersandcandiscoverthehigher-qualitycommunitystructureinnetworks.Keywords:complexnetwork;communitiesmining;multi-objectiveparticleswarmoptimization现实世界中的许多复杂系统都可以用复杂网络加以表示,例如社会网络、生物网络、电力网络、Web网络等.通过两个简单的映射,即对象到网络节点的映射与对象间关系到边的映射,可将复杂网络表示成图模型.复杂网络研究正在吸引着来自物理学、生物学、社会学与计算机科学等不同领域学者的关注.除了广为人知的小世界与无标度等特性外,复杂网络还具有极为重要的模块性,即复杂网络中隐含着丰富的社区结构模式.按照文献中对网络社区的描述,可以松散地将其定义为具有某种共同特征的相互连接的信息载体集合,例如,隶属于某个特定主题的Web页面集合,由具有某种共同兴趣爱好的微博者组成的微群,等等.从网络拓扑结构来看,一个网络社区就是一个网络图的稠密连通子图,在这个子图内的节点之间,连接密度高于子图内部节点与外部节点的连接密度.复杂网络社区发现的研究成果已被成功应用于诸如恐怖组织识别、蛋白质功能预测、舆情分析与处理等众多领域当中[1].网络社区发现研究正在吸引着复杂网络研究者的广泛关注,近年来涌现出大量的方法,文献[2]对这些方法进行了系统分析并给出了初步的分类.从数据挖掘层面上看,网络社区发现的本质是基于网络链接的聚类学习,其目标是将网络节点集划分为多个内部链接紧密而外部链接稀疏的簇.从聚类学习的角度上讲,网络社区发现算法的质量很大程度上取决于网络社区结构质量评判指标的设计思路与优化策略.目前,网络社区发现算法中目标函数(网络社区结构质量评判指标)的优化求解策略大致可归纳为两类:基本启发式方法和超启发式方法.前者将复杂网络社区发现问题转化为预定义启发式规则的设计问题,根据各种社区质量评判指标的特征设计优化策略;后者利用各种超启发式算子在网络社区发现问题空间中对社区质量评判指标进行寻优.社区质量评判指标的基本启发式方法可分为直接贪心法与间接贪心法.直接贪心法的思想非常简单,就是初始化网络为|V|个社区,反复迭代如下过程直到算法终止条件满足:计算各边相对于模块度的信息增益度,选取使社区质量评判指标值增量昀大的边加入,从而实现社区合并.直接贪心法的代表算法就是模块度指标值Q的优化算法,原始的Q优化算法的时间复杂度为O((m+n)n)或O(n2)[3].为了提高算法的效率与效果,提出了一系列的改进方法:Clauset等人设计了数据结构max-heaps将算法时间复杂度降低到O(mdlogn);Danon等人提出对Q值增量进行规范化处理以发现与社区大小具有较大差异的社区结构[4];Wakita等人提出利用合并比(consolidationratio)对Q值增量进行加权来提高算法的扩展性[5];Blondel等人提出在迭代合并的过程中允许多个社区合并而不仅仅是两个社区的合并[6].间接贪心法的基本思想是:将整个网络视为一个社区,然后循环如下过程直到社区质量评判指标值Q满足给定条件:选择具有某种特性的边并删除来实现网络社区的发现.该方法的选择策略主要包括:边介中性(betweenness)大者优先[7]、边聚集系数(clusteringcoefficient)小者优先[8]、边信息中心度(informationcentrality)大者优先[3]与边稳定系数(stabilitycoefficient)大者优先[9].除了对边进行贪心的方法外,淦文燕等人提出了一种基于拓扑势的社区发现算法,将每个社区视为拓扑势场的局部高势区,通过对局部极大势值节点进行贪心寻优来实现网络的社区划分[10].基本启发式方法的思想简单直观,容易实现,但是,该类方法需要借助先验知识定义递归终止条件,不具备自动识别网络社区总数的能力,这在很大程度上限制了此类优化方法在现实复杂网络社区发现中的应用.为了克服基本启发式方法的不足,研究者们提出了一类用于优化社区质量评判指标的超启发式方法,主要包括基于单一目标的优化算法与基于多目标的优化算法.Tasgin等人通过利用GA(geneticalgorithm)算法优化社区模块度Q函数来实现网络昀优划分的近似[11].Pizzutiz首先给出用于评判网络划分质量的社区分数(communityscore)的定义,然后运用GA-Net进行优化网络划分[12].考虑到社会网络的海量性,Lipczak等人[13]提出一种基于社区足够小且社区数有限假设的ACGA算法:将一个社区编码为一个个体,根据社区质量潜在提高量来选择个体进行遗传操作.段晓东等人引入粒子群算法对网络进行迭代二分实现Web社区的发现[14].CDPSO算法[15]采用基于节点邻居有序表的粒子编