（电路与系统专业论文）基于进化计算的复杂网络社区检测.pdf

摘要 科技的高速发展使人类社会大步迈入了网络时代，很多现实世界的复杂系统 都可以表示为网络，如协作网，万维网，电力网，生物网和社会网络等。网络可 以模型化为图，其中节点表示对象，边表示节点之间的连接。近年来，复杂网络 逐渐受到了来自各个领域研究者们越来越多的关注，例如物理学，数学，生物学， 社会学等。除了小世界效应，无标度等网络属性外，社区结构是复杂网络中另外 一个重要的网络属性。社区可以定性的定义为网络中节点的子集，其内部节点之 间的链接比较紧密，而和网络中其它节点的链接相对稀疏。研究复杂网络社区结 构对于分析网络的拓扑结构、理解网络的功能、发现网络中的隐藏规律以及预测 网络的行为不仅具有十分重要的理论意义，而且具有广泛的应用前景。近年来， 越来越多的社区检测算法被提了出来，这些算法大致可以分为三类：基于图分割 的方法，基于层次聚类的方法和基于模块度( m o d u l a r i t y ) 优化的方法，其中基于模 块度优化的方法近年来得到了越来越多的关注。模块度函数是n e w m a n 和g i r v a n 提出的用来评价网络社区划分质量的指标函数。一般来说，模块度值越大，对应 的社区结构越明显。 密母算法( m e m e t i ca l g o r i t h m ) 是近年来进化计算领域的一个研究热点，它是一 种基于种群的全局搜索和基于个体的局部启发式搜索的结合体，这种结合机制使 其搜索效率在某些问题领域比传统遗传算法快几个数量级。本文所做的主要工作， 就是利用进化算法这些优点，将其应用于复杂网络社区检测问题。本文所做的主 要工作如下： ( 1 ) 研究了多目标优化和进化算法的基本理论，提出了一种基于分解多目标优 化进化算法( m o e a d ) 的复杂网络社区检测方法。在该方法中，我们把社区检测问 题模型化为了一个两个目标的多目标优化问题，并利用多目标进化算法m o e a ，d 来优化这两个目标。 ( 2 ) 研究了社区检测算法中传统模块度优化具有的分辨率限制问题，为了解决 这个问题，我们使用了一个新的目标函数：扩展模块度密度( g e n e r a lm o d u l a r i t y d e n s i t y ) ，该目标函数是r a t i oa s s o c i a t i o n 与r a t i oc u t 的凸组合，可以克服分辨率限 制问题，也就是说通过调节里面的参数，我们可以从不同分辨率分析网络，进而 发现网络社区的层次结构。研究了密母算法( m e m e t i ca l g o r i t h m ) 的基本理论，在此 基础上提出了一种复杂网络社区检测密母算法。该密母算法引入了局部搜索策略， 克服了传统遗传算法收敛速度慢，容易陷入局部最优的缺点。同时，该算法将扩 i i 摘要 展模块度密度作为目标函数，可以从不同分辨率分析网络，克服了传统模块度优 化算法的分辨率限制问题。 本论文得到国家8 6 3 项目( 批准号：2 0 0 9 a a l 2 2 2 1 0 ) 、教育部新世纪优秀人才 支持计划( 批准号：n c e t - 0 8 0 8 1 1 ) 、陕西省青年科技新星计划( 批准号： 2 0 1 0 1 c i x x - 0 3 ) 和中央高校基本科研业务费重点项目( 批准号：k 5 0 5 1 0 0 2 0 0 0 1 ) 资助。 关键词：复杂网络社区检测进化算法密母算法多目标优化 a b s t r a c t a b s t r a c t m a n yr e a l w o r l dc o m p l e xs y s t e m sc a nb er e p r e s e n t e da sn e t w o r k s c o l l a b o r a t i o n n e t w o r k s ，t h ew o r l d w i d e - w 曲，p o w e rg r i d s ，b i o l o g i c a ln e t w o r k s ，a n ds o c i a ln e t w o r k s a r es o m ee x a m p l e s n e t w o r k sc o u l db em o d e l e da sg r a p h s ，w h e r en o d e s ( o rv e r t i c e s ) r e p r e s e n tt h eo b j e c t sa n de d g e sr e p r e s e n tt h ei n t e r a c t i o n sa m o n gt h e s eo b j e c t s t h ea r e a o fc o m p l e xn e t w o r k sh a sa t r r a c t e dm a n yr e s e a r c h e r sf r o md i f f e r e n tf i e l d ss u c ha s p h y s i c s ，m a t h e m a t i c s ，b i o l o g y , a n ds o c i o l o g y b e s i d e st h ep r o p e r t i e ss u c ha ss m a l l w o r l de f f e c ta n dt h ef i g h t - s k e w e dd g r e ed i s t r i b u t i o n s ，c o m m u n i t ys t r u c t u r ei sa n o t h e r i m p o r t a n tp r o p e r t yi nac o m p l e xn e t w o r k q u a l i t a t i v e l y , ac o m m u n i t yi sd e f i n e da sa s u b s e to ft h eg r a p hn o d e sw h i c hh a v eap a t t e mo fi n t e r c o n n e c t i o n sw h i c hi sd e n s e rt h a n t h a to b s e r v e dw i t ht h er e s to ft h en e t w o r kn o d e sn o ti nt h a tc o m m u n i t y c o m m u n i t y d e t e c t i o ni nc o m p l e xn e t w o r k si sp o t e n t i a l l yv e r yu s e f u l n o d e sb e l o n g i n gt ot h es a m e c o m m u n i t ya r em o r el i k e l y t oh a v ep r o p e a i e si nc o m m o n i nr e c e n ty e a r s ，m a n y a l g o r i t h m sh a v eb e e nd e v e l o p e dt os o l v et h i sp r o b l e m t h e s ea l g o r i t h m sc a nb ed i v i d e d i n t o t h r e e m a j o rc a t e g o r i e s ：g r a p hp a r t i t i o n i n g ，h i e r a r c h i c a lc l u s t e r i n g ，a n d m o d u l a r i t y b a s e do p t i m i z a t i o nm e t h o d ，w h i c hi sb yf a rt h em o s tp o p u l a rc l a s so f m e t h o d st od e t e c tc o m m u n i t i e si ng r a p h s m o d u l a r i t y , o r i g i n a l l yi n t r o d u c e dt od e f i n ea s t o p p i n gc r i t e r i o nf o rt h ea l g o r i t h mo fg i r v a na n dn e w m a n , h a sr a p i d l yb e c o m ea n e s s e n t i a le l e m e n to fm a n yc o m m u n i t yd e t e c t i o nm e t h o d sa n db yf a rt h eb e s tk n o w n q u a l i t yf u n c t i o n b ya s s u m p t i o n , h i g hv a l u e so fm o d u l a r i t yi n d i c a t eg o o dp a r t i t i o n s s o ， t h ep a r t i t i o nc o r r e s p o n d i n gt oi t sm a x i m u mv a l u eo na g i v e n g r a p hs h o u l db et h eb e s t ， o ra tl e a s ta v e r yg o o do n e i na r t i f i c i a li n t e l l i g e n c e ，e v o l u t i o n a r ya l g o r i t h m si sp o p u l a t i o n b a s e dm e t a h e u r i s t i c o p t i m i z a t i o na l g o r i t h m si n s p i r e db yb i o l o g i c a le v o l u t i o n t h eu s eo fap o p u l a t i o no f s o l u t i o n sh e l p st h ee v o l u t i o n a r ya l g o r i t h m sa v o i db e c o m i n gt r a p p e da tal o c a lo p t i m u m ， w h i c hi sap r o m i n e n ta d v a n t a g e c o m p a r e d 、i i o t h e r o p t i m i z a t i o n m e t h o d s e v o l u t i o n a r ya l g o r i t h m st h a ti n t e r s p e r s e dt h er e c o m b i n a t i o no fh i g hq u a l i t ys o l u t i o n s w i t l lp e r i o d so fi n t e n s i v ei n d i v i d u a lo p t i m i z a t i o nw e r en a m e dm e m e t i ca l g o r i t h m s f r o ma no p t i m i z a t i o np o i n to fv i e w , m e m e t i ca l g o r i t h m sh a v eb e e ns h o w nt ob em o r e e f f i c i e n ta n dm o r ee f f e c t i v et h a nt r a d i t i o n a lg e n e t i ca l g o r i t h m sf o rs o m ep r o b l e m d o m a i n s t h i sp a p e ri sm a i n l ya b o u tt h ea p p l i c a t i o no fe v o l u t i o n a r ya l g o r i t h m st o c o m m u n i t yd e t e c t i o n t h em a i nw o r k s a r ea sf o l l o w s ： i va b s t r a c t ( 1 ) ac o m m u n i t yd e t e c t i o nm e t h o db yu s i n gm u l t i - o b j e c t i v ee v o l u t i o n a r y a l g o r i t h mb a s e do nd e c o m p o s i t i o ni sp r o p o s e d i nt h i sp r o p o s e dm e t h o d ，c o m m u n i t y d e t e c t i o ni sc o n s i d e r e da sam u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e ma n di sf o r m u l a t e d w i t h t w od i f f e r e n to b j e c t i v e s m u l t i - o b j e c t i v e e v o l u t i o n a r ya l g o r i t h mb a s e d o n d e c o m p o s i t i o n ( m o e a d ) i se m p l o y e dt oo p t i m i z et h et w oo b j e c t i v e s ( 2 ) t h er e s o l u t i o nl i m i to fm o d u l a r i t yo p t i m i z a t i o ni ss t u d i e d i no r d e rt oa v o i d r e s o l u t i o nl i m i tp r o b l e m ，w et e s t e da n o t h e rq u a l i t yf u n c t i o n ：t h eg e n e r a lm o d u l a r i t y d e n s i t y , w h i c hi sac o m b i n a t i o no ft h er a t i oa s s o c i a t i o na n dt h er a t i oc u t b yt u n i n gt h e p a r a m e t e r , w ec a nu s et h i sg e n e r a lf u n c t i o nt oa n a l y z et h et o p o l o g i c a ls t r u c t u r ea n d u n c o v e rm o r ed e t a i l e da n dh i e r a r c h i c a lo r g a n i z a t i o no fac o m p l e xn e t w o r kam e m e t i c a l g o r i t h mf o rc o m m u n i t yd e t e c t i o ni nn e t w o r k si sp r o p o s e d t h ep r o p o s e da l g o r i t h m c o m b i n e sg e n e t i ca l g o r i t h ma n dah i l l c l i m b i n gs t r a t e g ya st h el o c a ls e a r c hp r o c e d u r es o t h a ti ti sm o r ee f f i c i e n tt h a nt r a d i t i o n a lg e n e t i ca l g o r i t h m s m e a n w h i l e ，w ec h o o s et h e g e n e r a lm o d u l a r i t yd e n s i t ya st h eo b j e c t i v ef u n c t i o n , w h i c ha l l o w st h ep r o p o s e d m e m e t i ca l g o r i t h mt od i s c o v e rt h ec o m m u n i t ys n u c t u r ei nn e t w o r k sa td i f f e r e n t r e s o l u t i o n s t l l i sw o r kw a ss u p p o r t e db yt h en a t i o n a lh i g ht e c h n o l o g yr e s e a r c ha n d d e v e l o p m e n tp r o g r a m ( 8 6 3p r o g r a m ) o fc h i n a ( g r a n tn o 2 0 0 9 a a l 2 2 2 1 0 ) ，t h e p r o g r a mf o rn e wc e n t u r ye x c e l l e n tt a l e n t si nu n i v e r s i t y ( g r a n tn o n c e t - 0 8 0 8 1 1 ) ， t h ep r o g r a mf o rn e ws c i e n t i f i ca n dt e c h n o l o g i c a ls t a ro fs h a a n x ip r o v i n c e ( g r a n tn o 2 0lo k ，凇- 0 3 ) ，a n dt h ef u n d a m e n t a lr e s e a r c hf u n d sf o rt h ec e n t r a lu n i v e r s i t i e s ( g r a n tn o k 5 0 5 1 0 0 2 0 0 0 1 ) k 呵w o r d s ：c o m p l e xn e m o r kc o m m u n i t yd e t e c t i o ne v o l u t i o n a r ya l g o r i t h m m e m e t i e a l g o r i t h mm u l t i o b i e c t i v eo p t i m i z a t i o n 第一章绪论 第一章绪论 1 1 引言 科技的进步，特别是计算机网络信息技术的迅猛发展使人类社会大步迈入了 网络时代【l 】。现实世界中存在各式各样的复杂网络，例如大自然的生态网络，生物 体中的神经网络、新陈代谢网络，国家之间的政治、经济网络，与人类日常生活 密切相关的交通网络、电力网络，以及各种社会关系网络等。人类社会的网络化 既给社会生产和生活带来了极大的便利，提高了人类生产效率和生活质量，但也 给人类社会生活带来了一定的负面冲击，例如计算机病毒在互联网中的传播、传 染病在密集人群中的快速扩散、大面积停电事故等。因此，人类社会的日益网络 化需要人类对各种人工和自然的复杂网络的行为有更好的认识j 长期以来，通信 网络、电力网络、生物网络和社会网络等分别是通信科学、电力科学、生命科学 和社会科学等不同学科的研究对象，而复杂网络理论主要研究的是看上去不相同 的复杂网络之间的共性和处理它们的普遍方法。2 0 世纪末开始，复杂网络研究正 渗透到数理学科、生命学科和工程学科等众多不同的领域，对复杂网络定量与定 性特征的科学理解，已成为网络时代科学研究中一个极其重要的挑战性课题【2 3 】。 复杂网络之所以称之为复杂，主要体现在以下几个方面【4 j ： 结构复杂：表现在节点数巨大，网络结构呈现多种不同特征； 网络演化：表现在节点或边的增加与减少。例如万维网，网页或链接随时可 能出现或断开，导致网络结构的不断变化； 连接多样性：节点之间的连接权重存在差异，且有可能存在方向性； 动力学复杂性：每个节点本身可以是非线性系统，具有分岔和混沌等非线性 动力学行为而且在不停地变化； 节点多样性：复杂网络中的节点可以代表任何事物，例如人际关系构成的复 杂网络节点代表单独的个体，而万维网组成的复杂网络节点可以表示不同网页； 多重复杂性的融合：即以上多种复杂性相互影响，导致更加难以预知的结果。 网络在数学上以图来表示，因此图论是研究网络的重要工具。图的研究起源 于1 8 世纪著名数学家欧拉的哥尼斯堡七桥问题【5 】，但随后的相当长一段时间里， 图论并未获得足够的发展，研究者们认为复杂系统的各个实体之间可以用某种规 则的结构来表示，对图的研究停留在规则图阶段。对直到2 0 世纪6 0 年代，两位 匈牙利数学家e r d 6 s 和r 6 n y i 建立的随机图理论在数学上开创了复杂网络理论的系 2 基于进化计算的复杂网络社区检测 统性研究【6 】，随后，随机图理论在将近4 0 年的时间里一直是研究复杂网络结构的 基本理论。然而现实中网络并不完全是简单规则和随机的。到2 0 世纪末，对复杂 网络的科学探索发生了重要的转变，复杂网络理论的研究也不再局限于数学领域。 人们开始考虑节点数量众多、连接结构复杂的实际网络的整体特性，在从物理学 到生物学的众多学科中掀起了研究复杂网络的热潮。这一时期的两篇开创性的文 章开创了复杂网络研究的新纪元：1 9 9 8 年w a t t s 和s t r o g a t z 在n a t u r e 杂志上发表 的题为“小世界网络的集体动力学( c o l l e c t i v ed y n a m i c so f s m a l l w o r l d n e t w o r k s ) 懈t ；另一篇是1 9 9 9 年b a r a b 缸i 和a l b e r t 在s c i e n c e 杂志上发表的 题为随机网络中标度的涌现( e m e r g e n c eo fs c a l i n gi nr a n d o mn e t w o r k s ) 的文章 l 8 j 。这两篇文章分别揭示了复杂网络的小世界特征和无标度性质，并建立了相应的 模型以阐述这些特性的产生机理。近年来的研究表明，真实世界中许多网络都具 有另外一种普遍的性质，称之为社区( 社团) 结构特性。一个社区往往是由网络中可 能具有相同属性和( 或) 扮演相似作用的节点组成的，社区内部节点之间的连接相对 比较紧密，而各社区之间的连接相对比较稀疏。社区检测就是发现网络中的社区 结构，这是本文讨论的重点。 1 2 复杂网络的基本概念 1 2 1 复杂网络的图表示 一个具体的网络可抽象为一个由点集v 和边集e 组成的图g = ( 儿e ) 。节点数 记为n 爿vi ，边数记为m = ei 。e 中每条边都有v 中一对点与之相对应。如果任 意点对( f ，力与( ，0 对应同一条边，则该图称为无向图( u n d i r e c t e dg r a p h ) ，否则称为 有向图( d i r e c t e dg r a p h ) 。如果给每条边都赋予相应的权值，那么该图就称为加权图 ( w e i g h t e dg r a p h ) ，否则称为无权l 虱( u n w e i g h t e dg r a p h ) 。当然，无权图也可以看作是 每条边的权值都为l 的等权图。如果图g 中的节点不包含自己到自己的边，且两 个不同的节点之间最多只有一条边，则称图g 为简单图( s i m p l eg r a p h ) 。通常的研 究指的是简单图或简单网络的研究。如果图g 中任何两个节点之间都有通路可以 互相到达，则称g 是连通图，否则为不连通图。若g 不是连通图，则它的每一个 连通的子图称为连通分支。在无向图g 中，与节点f 相连的边的个数称为节点f 的 度，记为屯。在有向图中，一个节点的度分为入度( i n d e g r e e ) 和出度( o u t d e g r e e ) 。 节点的出度是指从该节点指向其它节点的边的数目，节点的入度是指从其它节点 指向该节点的边的数目。对于两个图g = ( 圪e ) 和g = ( 矿，e ) ，如果v cv 并且 e ce ，则称g 为g 的子图。如果一个图中任意两个节点之间都有边，则称这个 图为完全i 虱( c o m p l e t eg r a p h ) 。一个有刀个节点的完全图记为疋，它有n ( n 1 ) 2 条 第一章绪论 3 边。图g 的一个团( c l i q u e ) 是图g 的一个子图g 。，且g 是完全图。 矩阵是研究图的一个有力的工具，当利用计算机来研究有关图的算法时，通 常用邻接矩阵来表示和存储图。对于图g = ( y ，e ) ，构造邻接矩阵彳= ( 4 ) x ，其 中n 为图的节点数，如果节点f 和节点f 之间有边相连，则鸣= l ，否则4 = o 。 1 2 2 复杂网络的特性 1 2 2 1 小世界特性 要定义网络的小世界特性，需要先定义网络的聚类系数c 和特征路径长度三。 聚类系数( c l u s t e r i n gc o e f f i c i e n t ) ：一个节点的聚类系数指的是与该节点相连的 两个节点也存在连接的概率。假设网络中的一个节点i 有七条边将它和其他节点相 连，这置个节点就称为节点f 的邻居。显然，在这毛个节点之间最多可能有 毛( t 一1 ) 2 条边。而这屯个节点之间实际存在的边数e 和总的可能的边数 匆( 电一1 ) 2 之比就定义为节点f 的聚类系数c f ，即 c ：= 2 e , ( 乞( 毛一1 ) ) ( 1 1 ) 整个网络的聚类系数等于所有节点的聚类系数的平均值，即c = 寺：。e 。 特征路径长度( c h a r a c t e r i s t i cp a t hl e n g t h ) ：两个节点f 和歹之间的最短路径长度 指的是从节点f 到节点，所经过的最少边数，用4 ，表示，网络的特征路径长度三等 于网络中所有节点对之间的最短路径长度的平均值，即 1 一 三= 丁二略 ( 1 2 ) 二n ( n - i ) 巧 2 网络的特征路径长度衡量的是网络的传输性能与效率。 网络的聚类系数c 和特征路径长度三能够用来描述规则网络、随机网络和小世 界网络不同的数字特征。通常，规则网络具有大的聚类系数和长的特征路径长度； 随机网络具有小的聚类系数和短的特征路径长度；小世界网络则具有上述两种网 络的优点，即具有大的聚类系数和短的特征路径长度。物理学家把大的聚类系数 和短的特征路径长度两种统计特性合在一起称为小世界特性。研究表明，许多真 实网络都表现出上述的小世界特性。 1 2 2 2 无标度特性 要定义网络的无标度特性，首先需要定义网络节点的度分布。 节点度分布( d e g r e ed i s t r i b u t i o n ) ：即网络中节点的度的分布情况，可用分布函 4 基于进化计算的复杂网络社区检测 数尸( 七) 来描述，它表示的是一个随机选定的节点的度恰好为k 的概率。 规则的格子有着简单的度序列：因为所有的节点具有相同的度，所以其度分 布为d e l t a 分布，它是单个尖峰。网络中的任何随机化倾向都将使这个尖峰的形状 变宽。完全随机网络的度分布近似p o i s s o n 分布，如果用 表示网络所有节点 的平均度数，则当k 时，度为k 的节点在随机网络中是不存在的，故这种 网络也称为均匀网络。近几年的大量研究表明，很多真实的网络的度分布明显不 同于p o i s s o n 分布，而更接近于幂律分布p ( k ) o ck 一，即具有某一特定度数的节点 数目与这个特定的度之间的关系可以用一个幂函数近似的表示。幂函数曲线是一 条下降相对缓慢的曲线，这使得度很大的节点可以在网络中存在。对于随机网络 和规则网络，度分布区间非常狭窄，几乎找不到偏离平均度数较大的节点，故其 平均度可以看作是一个特征标度，在这个意义上，节点度服从幂律分布的网络既 有很多度很小的节点，又有少数度很大的节点，不存在一个明显的特征标度，因 此我们把节点度分布的幂律特性叫做无标度特性，具有无标度特性的网络叫做无 标度网络。 1 2 2 3 社区结构特性 社区结构是真实世界中许多复杂网络所具有的一种普遍性质，目前，社区结 构尚不存在统一的定义，它取决于特定的系统和应用。直观上来说，网络中的社 区指的是网络中存在的节点子集，该子集内部节点之间具有相对紧密的连接而与 外部节点具有相对稀疏的连接。图1 1 是社区结构的一个简单例子。另外，在很 多情况下，社区是由算法定义的，也就是说，它仅仅作为算法的最终输出结果， 而没有一个预先的精确定义。 、， 、， 、， _ ， 图1 1 社区结构示例。该网络包含三个社区，每个社区用虚线圆圈表示。 近年来，不同领域的专家学者们提出了很多社区结构的定量的定义，大体上 可以分为局部性的定义、全局性的定义和基于节点相似度的定义【9 】。 第一章绪论 5 局部性的定义：社区是网络中的一部分，但是和网络中的其它部分连接较少， 因此在某种意义上，可以认为它们相对独立存在，局部性的定义正是聚焦于要研 究的那一部分，可能包括它直接的邻居，而忽视网络中的其它部分。比如基于团 ( c l i q u e ) 的社区结构定义指的是网络中的每个社区都是一个团或者多个团的组合 【l o j 。网络中的团指的是网络中的全连接子图。最简单的团是三角形，在实际网络 中很常见，但规模较大的团却很少出现。团的定义非常严格，一个子图如果只缺 少所有可能存在的边当中的一条，那么按照团的定义，它依然不能被称之为一个 社区。另外一个问题是，团中所有节点都是对称的，它们之间没有任何差别，而 在很多实际网络中，社区内部往往同时存在核心和外围这样不同功能的节点。还 比如r a d i c c h i 等人提出的强弱社区的定义l i ，所谓的强社区指的是社区内的每一 个节点的内度大于它的外度，即矽 ，v i v 。这个定义同样比较严格，放松一 下条件，就是所谓的弱社区的定义：罗。，p 罗。，即社区节点总的内度大于 其总的外度。显然，一个满足强定义的社区一定是满足弱定义的社区，反之则不 然。 全局性的定义：从网络整体的角度同样也可以定义社区，特别是某些情况下， 网络中的某一部分对于整个系统的功能非常重要，单独分离这一部分可能会影响 整个系统。近年来研究者们提出了很多全局性的定义，大多数情况下都是间接定 义，这些定义在算法中利用了图的某些全局性特征，最终在算法结束时社区作为 结果输出。然而，有一类定义是基于这样一个思想：如果一个图具有社区结构， 那么它必然不同于随机图。一个随机图，比如e r d 6 s r 6 n y i 随机图是没有社区结构 的，因为任意两个节点都有相同的概率相连。因此，可以定义一个空模型( n u l l m o d e l ) ，即满足原图的某些结构属性的一个随机图。空模型可以用来比较，来判断 图中是否存在社区结构。2 0 0 4 年n e w m a n 和g i r v a n 提出了一个著名的空模型，即 原图的随机化版本，在保持每个节点的平均度不变的条件下，随机重连每一条边 i l 刀，这是模块度( m o d u l a r i t y ) 定义背后的基本概念。模块度是用来评价网络划分好 坏的函数，现在已经成了很多社区检测算法的核心部分，在下一章将会详细讨论 这个重要的概念。在标准模块度公式中，一个子图当其内部边数超过了空模型中 相同子图的期望内部边数，则该子图就被认为是一个社区，这个期望值是在所有 可能空模型实现上的平均值。 基于节点相似度的定义：这个定义设想社区是相似节点组成的点集，因此， 可以定义两个节点之间关于某种特性的相似度，不论这种特性是局部的还是全局 的，也不论它们之间是否有一条边相连。有了相似度定义，每个节点会出现在与 其相似节点相同的簇中，形成社区。相似度度量是很多传统社区检测方法的基础， 例如基于层次聚类，划分聚类，谱聚类的方法。 需要注意的是，很多现实世界网络中的社区都具有层次( h i e r a r c h i c a l ) 结构，即 6 基于进化计算的复杂网络社区检测 较大规模的社区通常会包含较小规模的社区，而较小规模的社区通常会包含更小 规模的社区，如图1 2 所示。这种层次结构对于网络的架构和演化具有重要意义。 图1 2 层次社区结构示例。该网络包含1 6 个3 2 个节点的小社区，每4 个小社区又组成一个 较大的社区，每个节点的度为6 4 。 1 2 3 社区检测研究意义与研究现状 1 2 3 1 研究意义 网络社区检测对于理解网络的结构和功能特性有深刻的理论和现实意义。对 于真实网络，同属于一个社区的节点更有可能具有相似的性质或相近的功能。比 如社会网络中的社区代表根据兴趣或背景而形成的真实的社会团体，引文网络中 的社区代表针对同一主题的相关论文，而生物化学网络或者电子电路网络中的社 区可以是某一类功能单元。发现网络社区结构有助于我们对网络中的节点进行分 类。处于社区中间位置的节点，也就是和社区内很多其它节点相连的节点，可能 对整个社区起到控制和维护稳定的功能，而在社区边缘的那些节点，则对社区间 的沟通与交流起到很大的作用。发现网络社区结构能够发现新的知识和现象，有 助于更深刻地理解和认识网络结构和功能之间的关系。 网络社区检测还具有巨大的商业价值，在w e b 数据挖掘、电子商务领域也有 重要的应用。比如在网上零售商( 比如亚马逊w w w a m a z o n e o m ) 的产品和客户组成 的购买关系网络中，发现具有相似购买行为的客户群可以帮助改进网站的购买推 荐系统，好的购买推荐系统可以让用户从众多的商品里发现更适合的产品，同时 第一章绪论 7 也帮助网上零售商提升销售业绩，获取更大的商业机会。 网络的社区检测对网络的分层可视化也有重要意义，网络的可视化是信息可 视化的一个重要分支，所谓可视化就是把一个网络的拓扑表示( 通常是矩阵表示) 投影到二维平面上，一个好的可视化模型或算法能够使节点的重叠和边的交叉越 少越好。对于一个节点数目庞大的复杂网络来说，将其投影到优先的二维平面上 会不可避免地使很多节点重叠在一起，如果我们能够检测出不同尺度下的社区结 构，把精细尺度下的社团抽象成粗尺度网络中的一个节点，经过层层社区检测及 抽象，就能得到一个节点数相对很少的网络，网络中的每一个节点对应着一个高 分辨率下的子网络。这样当进行网络的可视化时，就可以首先给出最粗尺度下的 清晰的可视化结果，然后再根据实际的需要对相关的节点所代表的子图进行可视 化，从而减少了节点和边的重叠，又增强了网络的分层可视化效果。 1 2 3 2 研究现状 作为网络社区检测的一个简化问题，图分割( g r a p h p a r t i t i o n i n g ) i h - j 题几十年来得 到了广泛和深入的研究。图分割问题的一个典型应用是并行计算中的任务分配问 题。有c 个处理器处理个任务，这些任务之间在处理过程中可能需要相互通信。 为简单起见，我们假设每个任务都需要相同的处理时间，并且任何有通信的两个 任务之间的通信量都是一样的。这样我们就得到了一个无权无向简单图，个节 点代表 r 个任务，边表示需要通信的任务。相对于同一处理器上的两个任务之间 的通信代价，不同处理器两个任务之间通信的代价是非常高的。因此，为了提高 处理的效率，应减少不同处理器上的任务之间的通信。从而，这样一个任务分配 问题就变成了一个典型的图分割问题，把图中的个节点划分成为c 个组，在平 衡各个处理器的负载的同时，使组问的通信尽可能的少。精确求解图分割问题是 n p h a r d 问题，因此多种启发式算法被提出，试图近似求解图分割问题。在很多情 况下，这些启发式算法能够得到可以接受的解，比如k e m i g h a n - l i n 算法1 1 3 j 和谱平 分算法( s p e c n 铂b i s e c t i o nm e t h o d ) 1 1 4 1 。 社区检测问题不同于图分割的是，事先我们并不知道一个网络中有多少个社 区存在，各个社区包含的节点个数也是未知的。这使得社区检测问题是一个比图 分割问题更加困难的问题。另外，网络的社区结构通常呈现出层次特征，一个社 区可以进一步划分为几个子社区；有些节点出现在不同的社区中，这使得社区之 间有重叠。这些现象也增加了社区检测的难度。 2 0 0 2 年，g i r v a n 和n e w m a n 发表了题为社会学和生物学网络中的社区结构 ( c o m m u n i t y s t r u c t u r ei ns o c i a la n db i o l o g i c a ln e t w o r k s ) 的文章1 1 5 j ，开启了复杂网络社 区检测的研究热潮。他们在这篇文章中提出的算法，也就是著名的g n 算法，通 8 基于进化计算的复杂网络社区检测 过计算网络中每条边的边介数( e d g eb e t w e e n n e s s ) ，试图找到位于不同社区之间的 边，并通过不断的移除这些边，以发现网络中的社区结构。近几年来社区检测得 到了各个领域的专家和学者们的广泛关注，包括物理、数学、生物学和计算机科 学等。在这些研究者们的努力下，很多算法被提了出来，主要分为两类：第一类 是基于层次聚类( h i e r a r c h i c a lc l u s t e r i n g ) 的方法，可以分为分裂方法和凝聚方法两种 策略，著名的g n 算、法【1 5 】就是分裂方法的代表；第二类是基于模块度( m o d u l a r i t y ) 优化的方法：模块度函数是n e w m a n 和g i r v a n 提出的用来评价网络社区划分质量 的指标函数i l2 。一般来说，模块度值越大，对应的社区结构越明显，一般认为如 果网络划分具有的最大模块度值大于0 3 ，则认为该网络存在明显的社区结构。因 此，网络社区检测问题就等价于找到网络的一个划分，使得模块度的值最大。在 下一章中我们将着重介绍几个代表性的算法。 1 3 本文的内容安排 本文主要研究基于进化算法的复杂网络社区检测，具体的来说就是利用进化 算法解决复杂网络社区检测问题。我们综述了复杂网络社区检测的已有知名算法， 并结合进化算法的优点，提出了基于分解多目标优化进化算法的复杂网络社区检 测，和基于密母算法的复杂网络社区检测两种新方法。本文的内容安排如下： 第一章介绍了复杂网络的基本概念和属性，阐述了复杂网络社区检测的研究 背景、研究意义和研究现状； 第二章概述了几种常见的复杂网络社区检测算法，包括基于图分割的方法， 基于层次聚类的方法，和基于模块度优化的算法，并介绍了这几种算法各自的优 缺点； 第三章介绍了本文提出的基于分解多目标优化进化算法的复杂网络社区检 测。通过从社区的定义入手，我们把社区检测问题模型化为了一个两个目标的多 目标优化问题，并利用多目标进化算法m o e a d 来优化这两个目标。实验证明， 所提出的算法m o e a d - n e t 能够正确的检测出网络的社区结构，并且该算法的主 要优点是，通过一次运行就能够得到该问题的一组p a r e t o 解，其中每一个解都是 两个目标函数的某种折中，对应着网络的一个不同划分，通过分析这些解对应的 划分，我们能够发现网络社区的层次结构。 第四章介绍了本文提出的基于密母算法的复杂网络社区检测。我们发现，如 果用传统的遗传算法来解决社区检测问题，可能会遇到收敛速度慢，容易陷入局 部最优的缺点。另外，常用的模块度( m o d u l a r i t y ) 函数还具有分辨率限制问题。因 此，基于这两点，我们提出了一种社区检测密母算法m e m e - n e t ，该算法将扩展模 块度密度函数( g e n e r a lm o d u l a r i t yd e n s i t y ) 作为目标函数，实验证明，通过调节目标 第一章绪论 9 函数里的参数，可以从不同分辨率分析网络，进而揭示网络社区的层次结构。另 外，我们将爬山法作为局部搜索策略引入到遗传算法中，加快了算法的收敛速度， 有效避免了算法陷入局部最优，能够取得更好的检测效果。 第五章对本工作进行了总结，指出了本文的主要特色和创新之处，并对以后 的工作进行了展望。 第二章复杂网络社区检测的几种常见算法 1 1 第二章复杂网络社区检测的几种常见算法 2 1 1 k e r n i g h a n l i n 算法 2 1 基于图分割的方法 k e r n i g h a n - l i n 算法是一种试探优化法。它是一种基于贪婪算法原理将网络划 分为两个大小已知的社区的二分法。其基本思想是为网络的划分引入一个增益函 数q ，定义为两个社区内部的边数减去连接两个社区之间的边数，然后寻找使q 值 最大的划分方法。整个算法可描述如下：首先，将网络中的节点随机地划分为已 知大小的两个社区。在此基础上，考虑所有可能的节点对，其中每个节点对的节 点分别来自两个社区。对每个节点对，如果交换这两个节点的话，计算可能得到q 的增益q = q 交换后一q 交换前，然后交换最大的q 对应的节点对，