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

　　摘要:社区发现是复杂网络挖掘中的重要任务之一,在恐怖组织识别、蛋白质功能预测、舆情分析等方面具有重要的理论和应用价值.但是,现有的社区质量评判指标具有数据依赖性与耦合关联性,而且基于单一评判指标优化的网络社区发现算法有很大的局限性.针对这些问题,将网络社区发现问题形式化为多目标优化问题,提出了一种基于多目标粒子群优化的网络社区发现算法MOCD-PSO,它选取模块度Q、最小最大割MinMaxCut与轮廓(silhouette)这3个指标进行综合寻优.实验结果表明,MOCD-PSO算法具有较好的收敛性,能够发现分布均匀且分散度较高的Pareto最优网络社区结构集,并且无论与单目标优化方法(GN与GA-Net)相比较,还是与多目标优化算法(MOGANet与SCAH-MOHSA)相比较,MOCD-PSO算法都能在无先验信息的条件下挖掘出更高质量的网络社区.

　　关键词:复杂网络;社区挖掘;多目标粒子群优化

　　现实世界中的许多复杂系统都可以用复杂网络加以表示,例如社会网络、生物网络、电力网络、Web网络等.通过两个简单的映射,即对象到网络节点的映射与对象间关系到边的映射,可将复杂网络表示成图模型.复杂网络研究正在吸引着来自物理学、生物学、社会学与计算机科学等不同领域学者的关注.除了广为人知的小世界与无标度等特性外,复杂网络还具有极为重要的模块性,即复杂网络中隐含着丰富的社区结构模式.按照文献中对网络社区的描述,可以松散地将其定义为具有某种共同特征的相互连接的信息载体集合,例如,隶属于某个特定主题的Web页面集合,由具有某种共同兴趣爱好的微博者组成的微群,等等.从网络拓扑结构来看,一个网络社区就是一个网络图的稠密连通子图,在这个子图内的节点之间,连接密度高于子图内部节点与外部节点的连接密度.复杂网络社区发现的研究成果已被成功应用于诸如恐怖组织识别、蛋白质功能预测、舆情分析与处理等众多领域当中.

　　网络社区发现研究正在吸引着复杂网络研究者的广泛关注,近年来涌现出大量的方法,文献对这些方法进行了系统分析并给出了初步的分类.从数据挖掘层面上看,网络社区发现的本质是基于网络链接的聚类学习,其目标是将网络节点集划分为多个内部链接紧密而外部链接稀疏的簇.从聚类学习的角度上讲,网络社区发现算法的质量很大程度上取决于网络社区结构质量评判指标的设计思路与优化策略.目前,网络社区发现算法中目标函数(网络社区结构质量评判指标)的优化求解策略大致可归纳为两类:基本启发式方法和超启发式方法.

　　前者将复杂网络社区发现问题转化为预定义启发式规则的设计问题,根据各种社区质量评判指标的特征设计优化策略;后者利用各种超启发式算子在网络社区发现问题空间中对社区质量评判指标进行寻优.

　　社区质量评判指标的基本启发式方法可分为直接贪心法与间接贪心法.直接贪心法的思想非常简单,就是初始化网络为|V|个社区,反复迭代如下过程直到算法终止条件满足:计算各边相对于模块度的信息增益度,选取使社区质量评判指标值增量最大的边加入,从而实现社区合并.直接贪心法的代表算法就是模块度指标值Q的优化算法,原始的Q优化算法的时间复杂度为O((m+n)n)或O(n2).为了提高算法的效率与效果,提出了一系列的改进方法:Clauset等人设计了数据结构max-heaps将算法时间复杂度降低到O(mdlogn);Danon等人提出对Q值增量进行规范化处理以发现与社区大小具有较大差异的社区结构;Wakita等人提出利用合并比(consolidationratio)对Q值增量进行加权来提高算法的扩展性;Blondel等人提出在迭代合并的过程中允许多个社区合并而不仅仅是两个社区的合并.间接贪心法的基本思想是:将整个网络视为一个社区,然后循环如下过程直到社区质量评判指标值Q满足给定条件:选择具有某种特性的边并删除来实现网络社区的发现.该方法的选择策略主要包括:边介中性(betweenness)大者优先、边聚集系数(clusteringcoefficient)小者优先、边信息中心度(informationcentrality)大者优先与边稳定系数(stabilitycoefficient)大者优先.除了对边进行贪心的方法外,淦文燕等人提出了一种基于拓扑势的社区发现算法,将每个社区视为拓扑势场的局部高势区,通过对局部极大势值节点进行贪心寻优来实现网络的社区划分.

　　基本启发式方法的思想简单直观,容易实现,但是,该类方法需要借助先验知识定义递归终止条件,不具备自动识别网络社区总数的能力,这在很大程度上限制了此类优化方法在现实复杂网络社区发现中的应用.

　　为了克服基本启发式方法的不足,研究者们提出了一类用于优化社区质量评判指标的超启发式方法,主要包括基于单一目标的优化算法与基于多目标的优化算法.Tasgin等人通过利用GA(geneticalgorithm)算法优化社区模块度Q函数来实现网络最优划分的近似.Pizzutiz首先给出用于评判网络划分质量的社区分数(communityscore)的定义,然后运用GA-Net进行优化网络划分.考虑到社会网络的海量性,Lipczak等人提出一种基于社区足够小且社区数有限假设的ACGA算法:将一个社区编码为一个个体,根据社区质量潜在提高量来选择个体进行遗传操作.段晓东等人引入粒子群算法对网络进行迭代二分实现Web社区的发现.CDPSO算法采用基于节点邻居有序表的粒子编码方式,通过PSO全局搜索来挖掘社区.Gog等人提出一种基于个体2064JournalofSoftware软件学报Vol.24,No.9,September2013信息共享机制的协同进化算法对网络社区结构进行寻优,结合局部搜索的GA变体算法CCGA与LGA通过优化社区质量评判指标Q来实现大规模复杂网络的社区发现.Zhu与Wang提出挖掘网络社区的并行遗传算法PGA.

　　尽管上述这些基于单一目标优化算法具有较好的时间效率且能够挖掘出满足某种特定目标的网络社区结构,但是,实际应用中的网络社区发现问题常需要兼顾多个目标,且这些目标可能是相互冲突的.显然,基于单一目标优化的社区发现方法无法满足这样的应用需求.因此,基于多目标优化的社区发现开始受到关注.公茂果等人提出一种用于网络社区发现的基于数学规划方法与进化算法相结合的多目标优化算法,同时对内部链接密度与外部链接密度进行优化.多目标优化算法(NNIA-Net,MOGA-Net,MOHSA与SCAHMOHSA)都是选取社区评分(communityscore)与社区适应度(communityfitness)作为优化目标来实现网络社区的挖掘,不同的是所采用的超启发式方法:NNIA-Net运用免疫算法,MOGA-Net运用GA算法,MOHSA自适应混合多目标和谐搜索算法,SCAH-MOHSA在MOHSA基础上添加一个谱聚类的预处理算子.

　　与单一目标优化算法相比较,这些多目标优化算法能够对各种社区质量评判指标进行综合考量,可以发现更多更高质量的网络社区结构.由于基于多目标优化的社区发现研究刚刚起步,还存在着一些不足,比如,当前的算法都是假设网络社区质量评判指标之间是可能不相一致的,而没有对假设是否成立给出理论证明或者实验验证,也没有研究网络社区质量评判指标之间的关系性质.另外,现有的基于多目标优化的社区发现方法几乎都是基于遗传算法,将多目标粒子群优化算法用于社区发现的研究报告尚未见到,而相关研究表明多目标粒子群优化算法具有优良的全局寻优能力.

　　本文首先从实验的角度验证了网络社区质量评判指标耦合关联性与数据依赖性的存在性,由此推导出进行多目标优化的社区发现的必要性,接着对多目标优化网络社区的问题进行形式化描述,然后提出了一种基于多目标粒子群优化的网络社区发现算法MOCD-PSO,该方法通过同时优化多个网络社区质量评判指标产生Pareto最优社区划分集合,用户可以根据特定需要从中选择最满意的社区结构.实验结果表明,无论与单目标优化方法(GN与GA-Net)比较,还是与多目标优化算法(MOGA-Net与SCAH-MOHSA)相比较,MOCD-PSO算法总能在无先验信息的条件下挖掘出更高质量的网络社区.

　　1、相关工作

　　由于“关于什么是社区”缺乏严格统一的定义,研究者们就从不同的应用场景与理论角度入手,定义出各种不同形式的社区,而根据社区的松散定义,可以把这些形形色色的社区归为3大类:具有最大内部链接密度的连通子图,具有最小外部链接密度的连通子图,同时具有最大内部链接密度与最小外部链接密度的连通子图.研究人员为了从网络中挖掘出各自定义的不同社区,提出了多种用于测度网络社区质量的量化指标.本节在给出网络社区结构形式定义(定义1)的基础上,列出了常用的社区质量评判指标,更多的社区质量评判指标见文献.

　　当前,使用最广泛的社区质量评判指标就是Newman与Girvan提出的Q值函数,它是通过比较网络子图与其对应随机图零模型的连接密度来定义的,Q值越大,则网络社区质量越高.然而该指标存在着粒度有限的缺点,Li等人将其改进为模块度密度指标QLi.评判指标MinMaxCut试图在最大化社区内节点相似度的同时最小化社区间节点相似度,MinMaxCut值越小,则网络社区质量越高.评判指标silhouette是借鉴于图形显示中的同一簇内的像素点值相似的观点来度量网络社区质量.

　　2、社区质量评判指标的性质

　　社区质量评判指标值有最大化最优,亦有最小化最优,二者可相互转化.不失一般性,本文仅讨论最大化最优的情形.下面,我们首先通过实验法来探讨网络社区质量评判指标耦合关联性与数据依赖性的存在性,然后给出对应的形式定义.理论上,可以根据先验的权系数将不同的评判指标合成一个评判指标,进而采用单目标优化策略.但由于性质1的存在,即各评判指标之间的耦合关联性,使得这种做法很难保证得到最优解.从实验可以看出,对于某个具体的网络而言,的确存在着某个最优的评判指标,但这个最优评判指标是因网络而异,而且无法事先得知.因此,性质2的存在说明了只选取某种质量评判指标进行网络社区发现是具有局限性的.