（计算机科学与技术专业论文）复杂网络中的层次重叠社区发现及可视化.pdf

l 一， i 勺 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅同 意学校向国家有关部门或机构送交论文的复印件和磁盘 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：z 殴 签字日期：2 ，f | 年；月z f 日 导师签名： 签字日期：lt , l o 年多月吖日 硕士学位论文 复杂网络中的层次重叠社区发现及可视化 d e t e c t i o na n dv i s u a l i z a t i o no fh i e r a r c h i c a lo v e r l a p p i n g c o m m u n i t i e si nc o m p l e xn e t w o r k s 作者姓名：王熙 导师姓名：林友芳 学号：0 8 1 2 0 5 2 1 职称：副教授 学位类别：工学学位级别：硕士 学科专业：计算机科学与技术研究方向：数据与知识工程 北京交通大学 2 0 1 0 年6 月 致谢 芳副教授的悉心指导下完成的，林友芳副教 给了我极大的帮助和学习的榜样在此衷心 成了实验室的科研工作，在学习上和生活上 向魏老师和韩老师表示衷心的谢意 研工作和论文都提出了许多的宝贵意见，在 在实验室工作及撰写论文期间，黎雷、商源纯等同学对我论文中可视化相关 研究工作给予了热情帮助，在此向他们表达我的感激之情 另外也感谢我的父母，他们的理解和支持使我能够在学校专心完成我的学业 北京交通大学硕士学位论文 中文摘要 中文摘要 随着复杂性科学的发展，复杂网络的研究逐渐受到各个学科学者的关注为 了通过网络结构来发现复杂网络的行为规律、演化方向和功能结构，学者们通过 对其拓扑进行研究，发现了复杂网络具有社区结构的基本特征有效的发现网络 的真实社区结构并进行展现，对相关数据及网络的分析和利用有重大的现实意 义本文提出了一种发现层次重叠社区的算法，并基于层次遗传算法实现了对重 叠社区发现结果的可视化 首先通过优化模块性函数对网络进行社区发现再利用局部优化社区结构性 的方法，在网络社区发现结果的基础上找到重叠节点，从而实现重叠社区发现最 后将社区抽象为社区节点并构造社区关系图进行迭代，来发现网络的层次结构， 并最终实现了对网络的层次重叠社区发现层次重叠社区发现能够更好的揭示复 杂网络中的社区结构、重叠结构和层次结构，有利于对复杂网络的理解，更好的 进行网络控制、功能发现等应用 根据分而治之的思想，自顶向下的对网络层次结构中的各个子社区独立的利 用遗传算法进行布局，并采用旋转、合并、翻转等方法，促使局部最优化逼近全 局最优化，从而得到整个网络的近似最优布局布局过程充分利用了数据关系， 既能够直观的看出网络的社区结构以及社区间的关系，又能够清楚的发现网络中 的重叠社区和重叠节点，兼顾了节点、社区布局的美观性同时支持对层次结构 进行布局，并能够进行并行计算，有较好的时间效率适合对网络进行直观的观 察和分析，充分发挥了可视化的作用 通过对复杂网络研究中常用数据集进行实验表明，层次重叠社区发现算法在 发现效果上和时间效率上都有令人满意的表现，同时采用层次遗传算法进行可视 化的结果也很好的展现了发现的结果，满足预定的布局目的，同时克服了传统算 法效率低下的问题 关键字：复杂网络；社区结构；重叠社区发现；层次化；模块性；可视化；图布 局；遗传算法 分类号：t p l 8 2 ；n 9 4 1 4 r e s e a r c h e r st r y t od e t e c tt h ec o m m u n i t i e si nt h en e t w o r k s f i n d i n go u tt h er e a l i z ec o m m u n i t i e si s s i g n i f i c a n ti na n a l y z i n ga n du s i n gt h en e t w o r k s t h i sp a p e rp r o p o s e sa na l g o r i t h mf o r d e t e c t i n gh i e r a r c h i c a lo v e r l a p p i n gc o m m u n i t i e s ，a n dv i s u a l i z i n gt h ed e t e c t i n gr e s u l t s 、析mah i e r a r c h i c a lg e n e t i ca l g o r i t h m f i r s t l y , t h ed e t e c t i n ga l g o r i t h mi s u s e dt oo p t i m i z et h ec o m m u n i t ys t r u c t u r e l o c a l l yi no r d e r t of i n do u tt h eo v e r l a p p i n gn o d e sf r o mt h ep a r t i t i o nw h i c hi st h er e s u l t o f m a x i m i z i n gt h em o d u l a r i t yo f a c o m p l e xn e t w o r k t h e nag r a p hw h i c hi n d i c a t e st h e r e l a t i o n s h i p sb e t w e e nc o m m u n i t i e si sb u i l tu p o nt h ec o v e ro fan e t w o r k b yb u i l d i n g t h ec o m m u n i t yg r a p ha n dd e t e c t i n gt h e c o m m u n i t yi t e r a t i v e l y , t h eh i e r a r c h i c a l o v e r l a p p i n gc o m m u n i t i e so ft h en e t w o r kw h i c hr e p r e s e n t st h ef e a t u r e so far e a ls y s t e m i sd e t e c t e d a l lo ft h ec o m m u n i t ys t r u c t u r e s ，o v e r l a p p i n gs t r u c t u r e sa n dh i e r a r c h i c a l s t r u c t u r e sa r eb e n e f i c i a lf o ru n d e r s t a n d i n ga n du s i n gt h ec o m p l e xn e t w o r k s ( e g ，t o c o n t r o lt h en e t w o r k sa n dd i s c o v e rt h en e wf u n c t i o n s ) a c c o r d i n gt ot h ei d e ao fd i v i d i n ga n dc o i l q u 耐n g ，at o p d o w nh i e r a r c h i c a lg e n e t i c a l g o r i t h mi sp r o p o s e dt ov i s u a l i z et h er e s u l t so ft h ed e t e c t i n ga l g o r i t h m b yl a y o u t i n g e a c h c o m m u n i t ya n dr e p l a c i n g t h ec o m m u n i t yn o d e sw i t h s u b - l a y o u t s ，t h e a p p r o x i m a t eb e s tl a y o u to ft h en e t w o r ki s a c h i e v e d t og a i ng l o b a lo p t i m i z a t i o n t h r o u g ha c c e l e r a t i n gl o c a lo p t i m i z a t i o np r o c e s s ，t h er o t a t i n g ，m e r g i n ga n do v e r t u r n i n g p r o c e s s e sa r ei n t r o d u c e d t h ev i s u a l i z a t i o nw h i c ht a k e st h ea d v a n t a g eo ft h es t r u c t u r e i n f o r m a t i o no fan e t w o r ki s v e r yu s e f u lf o ro b s e r v i n ga n da n a l y z i n gt h en e t w o r k s t r u c t u r ec l e a r l ya n dd i r e c t l y t h ec o m p u t a t i o n a le f f i c i e n c yi ss a t i s f y i n ge s p e c i a l l yi na p a r a l l e ls e t t i n g t h ee x p e r i m e n t a lr e s u l t sp r o v et h a t , t h eh i e r a r c h i c a l o v e r l a p p i n gc o m m u n i t y d e t e c t i n ga l g o r i t h mi sf e a s i b l ea n dp r o m i s i n g a n dg i v e ns o m er u l e s ，t h eh i e r a r c h i c a l g e n e t i ca l g o r i t h mc a l la c h i e v eah i ：g he f f i c i e n c ya n da c c u r a t e l yv i s u a l i z et h en e t w o r k s t r u c t u r e k e y w o r d s ：c o m p l e xn e t w o r k s ；c o m m u n i t ys 仃u c t u r e ；o v e r l a p p i n gc o m m u n i t i e s d e t e c t i o n ；h i e r a r c h i c a l ；m o d u l a r i t y ；v i s u a l i z a t i o n ；g r a p hl a y o u t ；g e n e t i ca l g o r i t h m c l a s s n o ：t p l8 2 ；n 9 4 1 4 目录 1 1 4 网络可视化3 1 2 相关工作3 1 2 1 传统图论及聚类方法3 1 2 2 经典社区发现算法4 1 2 3 重叠社区发现算法。4 1 2 4 层次结构发现5 1 2 5 模块性函数5 1 2 6 扩展模块性函数6 1 2 7 网络可视化8 1 3 论文结构8 2 层次重叠社区发现1 0 2 1 社区发现一l o 2 1 1 模块性函数。1 0 2 1 2 模块性优化算法1o 2 2 重叠社区发现1 3 2 2 1 社区结构性度量1 3 2 2 2 重叠节点识别算法1 4 2 3 层次结构发现1 7 2 3 1 社区关系图1 7 2 3 2 层次结构发现算法。18 2 4 小结2 0 3 重叠社区可视化。2 2 3 1 遗传算法2 2 3 2 布局准则2 3 3 3 层次遗传算法2 3 v v 1 1 1 1 2 i r 一 r 目录 2 4 3 3 - 2 评价函数2 5 3 3 3 选择算子2 9 3 3 4 交叉算子3 0 3 3 5 变异算子3 0 3 3 6 保存最优3l 3 4 小结3 2 4 实验部分3 3 4 1 常见数据集测试。3 3 4 1 1k a r a t e 数据集3 3 4 1 2d o l p h i n 数据集：3 4 4 1 3f o o t b a l l 数据集。3 5 4 2 算法时间复杂度3 6 4 2 - l 模块性优化算法3 6 4 2 2 重叠节点识别算法3 6 4 2 3 层次结构发现算法3 6 4 2 4 层次遗传算法3 7 4 3 可视化算法效果比较3 7 4 3 1 可视化效果3 7 4 3 2 适应值及时间开销比较3 8 5 总结与展望3 9 5 1 工作总结。3 9 5 2 工作展望。3 9 参考文献4 2 独创性声明4 5 学位论文数据集。4 6 引言 发展到着眼于 显规律关系的 科学的兴起和 发展，人们在实验中发现：大量的真实网络，如社会关系网络、生物神经网络、 语义联系网络等，既不是规则网络，也不是随机网络，而是具有许多不同统计特 征的更为复杂的网络，称之为“复杂网络” 复杂网络作为真实复杂系统的一种拓扑抽象，反映了真实系统的内在结构、 演化方向和行为规律，是研究真实复杂系统的重要工具然而，复杂网络由于其 结构复杂、网络演化、连接多样、动态变化、节点异构，并且多种复杂性并发的 特征，导致其结构和功能都非常难以理解【l j 为了研究复杂网络，学者们通过大量实验发现了复杂网络具有小世界和无标 度两个重要的统计特性小世界指网络有较小的平均距离和较大的簇系数，这意 味着网络中的边集中在少数节点上，且相邻节点相对集d p 2 1 无标度是指网络中 的节点度数服从幂率分布，这意味着网络中可能存在度数非常大的节点【3 】这些 统计特征表明了复杂网络的网络结构遵循特定的规律，意味着对复杂网络进行研 究成为可能 1 1 2 社区结构 1 9 8 6 年m c m i l l a n 等人在h i l l e r y 提出的“社区 1 4 定义基础上，完善了社区 的定义和相关理论【5 j 2 0 0 2 年，g i l v a l l 和n e w m a n 提出，复杂网络除了小世界和 无标度外，还具有社区结构的特征【6 】，引起了学术界的广泛关注社区是由网络 中带有相似属性的一组节点的集合，它具有社区内节点关系紧密，社区间节点关 系松散的特点f o r t u n a t o 总结了三种常见的社区结构定义，是分别从节点相似度、 局部、全局三个角度进行的【丌 北京交通大学硕士学位论文引言 节点相似度定义：社区结构是网络中相似节点的集合由于社区结构中节点 在异构的复杂网络中体现出相似特征，类似于社会学中“组织或者“群体 的 概念这是根据社区内部节点的相似度进行定义，而不考虑这些相似节点之间的 具体关系通常采用层次聚类的方法来度量节点相似度和发现社区结构【引 局部定义：社区结构是与网络申其他部分只有少量联系的部分局部定义是 从单个社区结构对外关系的角度进行的非全局性的宽松定义区别于节点相似度 的定义，认为社区结构必须满足社区内的个体间彼此“友好”的要求，即社区内 联系相对紧密例如p a l l a 等人提出的“派系”的概念1 9 1 ，就是一种局部定义方式 全局定义：社区结构是对系统的一种划分，这种划分结果使特征函数得到最 优解这是结合系统中所有社区结构进行的全局性定义，这里的特征函数可以根 据具体的应用需求来设计，从而对社区结构给出一种量化定义最常见的特征函 数是n e w m a n 等人提出的模块性函数【l 们 从三种定义可以看出，节点相似度更多的利用节点属性对网络进行划分，在 社会网络分析领域经常采用但是在复杂网络中，由于节点的复杂性往往无法获 得足够的信息，因此更多的采用后两种定义，利用网络的拓扑信息来进行社区发 现 社区结构在一定程度上反映了真实系统拓扑关系，指示了网络中的功能实体， 对网络理解有重要意义例如，在社会关系网络中，一个社区可能代表一群拥有 相同兴趣爱好的人；在生物神经网络中，一个社区可能代表具有特定功能的组织 结构；在语义联系网络中，一个社区可能代表一组用于同一场景的词汇可见， 社区发现有助于理解网络的拓扑结构及功能结构，从而为利用和改造网络提供指 导，如控制病毒传播、发掘网络未知功能、寻找相似节点等而且在一些特定应 用中，社区发现本身也有现实意义，如在社会网络中发现犯罪团体，寻找潜在客 户等 1 1 3 重叠社区与层次结构 真实网络中，并非每个节点都只属于一个社区结构，而是存在一些属于多个 社区结构的“重叠节点 ，与其它社区之间存在重叠节点的社区结构称为“重叠社 区以社会关系网络为例，网络中的一个个体往往属于多个组织，如一个人可能 既参加了足球俱乐部又参加了围棋俱乐部重叠社区可以视为是对网络的一种覆 盖，反映了更加真实的网络结构 重叠节点与各个社区内部的关系都相对紧密，可以很直观的观察到然而， 重叠社区之间很可能因为重叠节点而发生联系，却不易被察觉因此，重叠节点 2 北京交通大学硕士学位论文 引言 经常作为网络中的关键“桥梁 而受到重视另一方面，重叠社区更加真实的反 映了现实系统，发现重叠社区对研究真实网络的拓扑结构有更重要的指导意义 无论是发现社区对网络进行划分，或者是发现重叠社区对网络进行覆盖，都 可以按照层次顺序进行，使网络在不同的尺度下展现出不同的结构，即一个社区 中可能包含着更小的社区结构在社会网络及生物网络中，层次结构普遍存在如 足球和篮球俱乐部同属于球类俱乐部，围棋、桥牌俱乐部同属于棋牌俱乐部，而 球类和棋牌俱乐部又同属于体育俱乐部发现网络的层次结构，能够了解不同尺 度下的网络结构以及网络结构之间的关系，从而更为充分的反映真实系统的情况， 有利于进行系统分析 1 1 4 网络可视化 随着大规模数据的处理、分析技术的发展，为了方便科研人员或相关领域非 计算机专业人员对数据进行分析，数据可视化也成为一个重要课题将数据中的 实体视为节点，实体间的关系视为节点间的边，可以构成一个数据关系图，即真 实网络的拓扑结构通过一定的算法使网络中的节点分布n - 维空间中的不同位 置，然后用直线连接有关系的节点，可以得到网络的一个平面图像将网络可视 化为平面图像，可以让分析人员更加直观的了解网络的拓扑结构、内在关系等信 息因此，对图的布局算法的研究，是可视化课题的一个重要分支 在早期的研究中，人们更多的注重布局的美学效果但随着数据处理及分析 的深入，人们逐渐意识到应该以数据关系来指导布局，使得到的可视化结果更有 利于分析人员直观的观察数据的特性社区结构和重叠社区，能够对网络进行划 分或覆盖，有利于区分网络中不同节点集合及功能结构同时，由于它们更好的 反映了真实系统的结构特征，如果可视化结果能直观的表现出网络中的社区结构 和重叠节点，对网络分析工作将有巨大的促进意义 1 2 相关工作 1 2 1 传统图论及聚类方法 复杂网络理论始于图论中对e r 随机网络的研究，与社会网络分析相似但更 注重拓扑信息的挖掘且具有动态特征在复杂网络理论建立以前，一般通过图论 中图分割方法【1 1 。1 3 】和社会学中的划分聚类【1 舢16 】方法进行社区发现但是这两类方 3 北京交通大学硕士学位论文 引言 法的限制性在于，算法需要输入社区的数量甚至社区的规模，而这在研究复杂网 络时，可能往往并不能预先知道反而更加期望通过社区发现来了解复杂网络中 社区的数量和规模因此，图分割和划分聚类的方法并不适合于复杂网络的社区 发现 1 2 2 经典社区发现算法 依据社区的局部定义，通过找到连接各个社区的边并删除来将网络划分成不 同社区是一种朴素的社区发现思想g i r v a n 和n e w m a n 基于这种思想提出了最受 关注的社区发现算法刈算法g n 算法通过不断的移除边介数最高的边将网 络划分为各个社区【6 】这里的边介数的定义为经过某条边的最短路径数由于计 算边介数的时间复杂度较高o ( m n ) ，使得g n 算法时间复杂度为o ( m 2 ，z ) 对于稀 疏图，g n 算法时间复杂度近似o ( n 3 ) ，不太适合大规模复杂网络的应用，许多学 者在此基础上提出了改进算法 t y l e r 等人认为没有必要计算所有节点对边介数的贡献，提出只对一些对边介 数贡献度高的中心节点进行计算【1 7 】例如，通过随机抽样，利用较少的样本节点 计算出边介数的蒙特卡洛估计值，从而降低计算强度来提高速度，但也相对降低 了准确性 r a d i c c h i 等人基于g n 算法的思想，按照边聚集系数的大小来作为移除边的 度量准则【1 8 】边聚集系数定义为包含该边的长度为n 的环的数量之和( 一般取 n - 3 或n = 4 ) 由于边聚集系数是一个局部度量，计算速度很快，算法时间复杂 度为o ( m 4 n 2 ) 对于稀疏图，该算法时间复杂度近似o ( n 2 ) ，比g n 算法快了一 个数量级 1 2 3 重叠社区发现算法 2 0 0 5 年，p a l l a 等人提出了用于发现重叠社区的派系过滤方法，认为社区内部 的边密度高，容易形成派系，从而可以通过找出网络中的派系来发现社斟川p a l l a 等人定义k 派系表示网络中含有k 个节点的完全子图，两个k 派系如果有k 1 个公共点则相邻，两个k 派系如果可以通过相邻派系互通则连通，由连通的k 派 系构成的最大子图就是一个k 派系社区同时，一个节点所在的派系可能属于不 同的社区，因此派系过滤方法可以发现重叠社区 派系过滤方法能够发现重叠社区，对理解复杂网络起到非常好的效果，引起 了各学科的高度关注a d a m c s e k 等人开发了利用派系过滤方法发现重叠社区的软 4 北京交通大学硕士学位论文 引言 件包c f i n d e r t l 9 1 ，很快有学者将派系过滤方法扩展到有向带权图【2 0 】和二分图【2 1 】中， k u m p u l a 等人给出了派系过滤的一种快速实现算法【2 2 】 由于派系过滤方法假设网络中存在大量派系，因此对于派系稀疏的网络，派 系过滤难以给出有效的社区发现结果另一方面，如果网络中的派系非常密集， 算法将把整个网络认为是一个社区而且算法依赖于参数k 的选择，存在一定的 缺陷近年来，许多学者提出了一些新的发现重叠社区的思路 b a u m e s 等人基于边密度给出了一些评价社区结构的局部优化函数，按照一定 策略对所有社区进行对立的局部优化，将最终的优化结果作为社区发现结果【2 3 ， 2 4 1 由于一个节点可能在不同社区的优化过程中加入社区，从而达到发现重叠社 区的目的 e v a n s 等人利用边图分割的思想，将原始网络转为边图后进行社区发现，然 后再将社区发现的结果还原成原始网络【2 5 1 其中，边图是将原图中的边作为节点， 边图中的边表示节点对应的边在原图中相邻1 2 6 1 由于边图中不同社区的节点还原 成原图中的边后，可能联系着相同的节点，这些节点可以视为重叠节点，因此边 图分割法有天然发现重叠社区的特性，为重叠社区发现提供了一个新思路 g r e g o r y 利用将高分介数的节点分裂成多个副本，然后可以采用传统的社区 发现方法进行社区发现，最后再合并分裂的节点【27 。由于分裂节点可能被分到不 同的社区中，从而可以发现重叠社区这种思路的好处在于，可以利用所有传统 的社区发现算法来发现重叠社区 1 2 4 层次结构发现 传统的层次聚类方法，一般都是设计一个函数来度量节点对之间的相似度， 而后利用凝聚算法自底向上或者利用分裂算法自顶向下的对网络进行聚类，从而 发现层次结构【2 8 1 s a l e s p a r d o 等人根据模块性函数设计了节点亲和度来作为度量 进行层次聚类，从而实现带层次的社区发现【2 9 1 b l o n d e l 等人采用贪心策略优化模块型函数，然后将结果中的社区抽象为社区 节点，建立社区关系图后进一步优化，从而得到层次结果【3 0 1 a i m 等人利用边图 聚类的思想，实现了带层次重叠社区发现【3 1 2 5 模块性函数 在最原始的g n 算法中，由于缺乏一个量化标准来判定社区发现结果的优劣， 使得难以决定何时停止分裂以得到最佳的结果n e w m a n 和g i r v a n 针对此问题， 北京交通大学硕士学位论文引言 在2 0 0 4 年提出了评价社区发现效果的模块性函数1 0 1 他们假定随机网络是没有 社区结构的，那么一个社区内部的边密度应该大于一个随机子图因此，将模块 性函数q 定义为： q = 去莩( 呜一弓，勺( ) - 1 , c f = c j ， 公式1 中，m 为网络的边数，么为邻接矩阵，尸为期望邻接矩阵，根据不同的随 机模型而有所不同例如，如果认为所有子图的边密度与原图相同，则有 弓= 2 m ( n ( n 一1 ) ) ，刀为网络的节点数但是这种简单的均匀分布模型不适于复杂 网络一种更适合的模型是使边的期望与原图的节点度数分布相一致，即 b = k i k j 2 m ，其中t 表示节点f 的度数从而，模块性函数重定义为： q = 去莩( 鸣一等州 ( 2 ) 由此模块性函数可以看出，当所有的节点都属于同一个社区，或者所有的节点都 属于不同社区的时候，网络的模块性最差q = 0 而q 越接近1 时，网络模块性越 好，即认为社区发现结果更好n e w m a n 等人认为，一般社区发现结果在( o 3 ，0 7 ) 之间都是可以接受的 由于模块性函数很容易扩展到带权和有向图的情况【3 2 , 3 3 1 ，因此成为最受关注 的社区发现评价函数通过优化模块性函数也成为社区发现的一种思路但是 b r a n d e s 等人证明了优化模块性函数是一个n p 完全问题【3 4 】因此需要采用一定的 策略利用模块性函数进行启发式搜索，如贪心优化 3 0 , 3 5 - 3 7 1 、模拟退火【3 8 捌、极值 优化1 4 0 1 、频谱优化【4 14 2 】等等 1 2 6 扩展模块性函数 由于n e w m a n 提出的模块性函数并不能用于评价重叠社区发现结果，一些学 者对其进行了扩展 s h e n 等人给出了一个相对简单的扩展模块性函数四【4 3 1 ，定义为： 6 北京交通大学硕士学位论文 引言 明= 去莩奇鸣一等剐 公式3 中，q 表示包含节点f 的社区结构数可见，一条边对模块性的贡献度， 将随着包含其端点的社区数量的增加而降低e q 的时间复杂度为o ( n 2 ) n i c o s i a 等人考虑更一般的情况，认为网络中的边和随机模型中的边对模块性 有不同的贡献度，同时考虑了有向图的情况，给出了新的模块性函数瓯m 】，原 始模型为： 瓯= 去喜渺鸣一学， ( 4 ) 公式4 中，为社区数，磙，磋分别表示节点f 连接到社区c 内部和外部的度 数和分别表示实际边和随机模型中的边对不同社区的贡献系数，并在没有 重叠的情况下两者相等而在有重叠时，两者依赖于节点与社区之间的关系最 终将模块性函数瓯定义为： 鼯翌掣以。：婆掣 瓯= 去羔c = l i , j f ( q 吩，) 呜一 公式5 中，。为f 对c 的隶属度因子，表示f c 的程度，要求：。= 1 而 f ( a l c ，吩，。) 函数可以有不同的选择，如简单的取两个输入参数的平均值n i c o s i a 等人通过实验给出了一个效果较好的f ，。，嘭，。) 函数： ) 2 雨巧杀硒以加2 乃鸭p 猷 并给出了经验值p = 3 0 在实验中， 劬，。= 磁妇：c e c 磔，否则取，。= o o ( n 。n 2 ) 7 对于隶属度因子有：如果i c 取 计算绋的时间复杂度相对较高，为 北京交通大学硕士学位论文 引言 e q 和瓯作为模块性函数的扩展，适合于对重叠社区发现结果进行评价，同 样很容易扩展到带权网络虽然它们基于模块性函数而存在分辨率极限，有时候 并不能准确的评价重叠社区发现的结果【4 5 】，但是对重叠社区发现还是具有重大的 指导意义，受到广泛的认可在第4 章的实验中也会通过这两个扩展模块型函数 来验证重叠社区发现的结果 1 2 7 网络可视化 1 9 8 4 年，e a d e s 基于q u i n n 等人在v l s i 技术中提出的“力导向布局 4 6 1 ， 给出了一种模拟弹簧模型的启发式力导向绘图算法【47 1 算法将图中的节点视为钢 圈，将节点间的边视为一根弹簧，通过计算节点间的引力和斥力并对布局进行相 应调整，当图中所有节点受力平衡时完成布局i t o h 等人在最近的研究中，利用 混合空间填充技术将力导向算法扩展到多类图的布局上【4 引然而，力导向算法采 用的是基于节点关系的模型，虽然在一定程度体现出社区结构，但并不适用于重 叠社区的可视化 1 9 9 1 年，k o s a k 等人将h o l l a n d 提出的遗传算法1 4 9 j 应用于图布局【5 0 1 遗传算 法以一定的美观准则作为评价函数，通过布局间的交叉和变异，不断在二维空间 搜索更加符合准则的布局，最终演绎出近似最优布局由于“美观”因不同的观 察目的而有所不同，遗传算法针对不同的应用，可以通过修正评价函数来达到目 的，展现了非常灵活的适应性然而昂贵的时间开销，使得遗传算法难以应用于 大规模数据的可视化【5 1 1 在前期的研究中，曾经利用分而治之的思想，提出层次 遗传算法对大规模聚类数据进行可视化，取得了较好的效果【5 2 1 1 3 论文结构 本文共五章第1 章主要介绍了本文研究背景及近年来相关研究工作；第2 章提出了一种发现层次重叠社区的算法；第3 章提出了一种基于层次遗传算法的 重叠社区可视化方法；第4 章展示了本文实验结果；第5 章总结了本文工作成果 及展望 第1 章分四节第l 节介绍了复杂网络研究领域中，社区结构、重叠社区与 层次结构等网络结构提出的背景及研究意义，同时介绍了网络可视化的基本方法 和作用，引出了本文研究相关的一些重要概念及理论基础第2 节介绍了社区发 现、重叠社区发现、层次结构发现、网络模块性评价、网络可视化几个方面的重 8 北京交通大学硕士学位论文引言 要研究成果，对相关经典算法及其思想进行了总结和讨论本节是第l 章最后一 节，解析论文结构及各部分内容 第2 章分四节第l 节提出了一种基于优化模块性函数的社区发现方法第 2 节介绍了一些常见的社区结构性度量方法，并结合社区发现的结果提出重叠节 点识别算法用来发现重叠社区第3 节介绍了如何通过构造社区关系图进行网络 的层次结构发现，从而得到带层次的重叠社区发现结果第4 节对层次重叠社区 发现算法进行小结 第3 章分四节第l 节介绍了遗传算法及其在可视化中的应用第2 节针对 重叠社区的特点，设计了有利于网络分析的布局准则，用于指导可视化实验第 3 节介绍了层次遗传算法的思想及各个步骤的实现第4 节对层次遗传布局算法 进行小结 第4 章为实验部分，分三节第1 节对社会网络及复杂网络领域常用的数据 集进行实验，通过可视化的方法展现网络的层次重叠社区发现结果，并对结果进 行讨论第2 节讨论了各个算法的时间复杂度第3 节将层次遗传算法与传统遗 传算法及力导向算法进行可视化效果和时间开销的比较，体现可视化算法的有效 性 第5 章分两节第l 节对论文工作成果进行了总结第2 节对论文工作提出 展望 9 重叠社区发现 q = 瓣一c 知 实际上只计 公式6 的形 公式7 中，乞为两个端点都在社区c 内部边的数量和，吃为社区c 中所有节点的度 数和这种等价形式的好处在于，公式中所有的子项都可以从社区内部的边中得 到，在合适的数据结构下有更快的计算效率同样可以很容易的将上式扩展到带 权情况： q = 喜t 鲁一岛) 2 】 公式8 中，w 为网络中所有边的权和，形为所有两个端点都在社区c 内部的边的 权和，疋为社区c 中所有节点的强度和，一个节点的强度即连接到该节点的所有 边的权和 2 1 2 模块性优化算法 这里介绍一种以局部最优化模块性函数为思想的社区发现算法，本文将以此 算法为基础进行后续实验算法首先将网络中所有的节点都初始化为一个社区， 即每个社区都只包含一个节点然后遍历所有节点及其邻点，计算将节点从原来 所在社区移动到其各个邻点所在的社区后带来的局部模块性增益然后将节点加 1 0 北京交通大学硕士学位论文 层次重叠社区发现 入到模块性增益最高的相邻社区之中如果没有能够带来正增益的相邻社区则将 节点留在原来社区重复以上过程，直至全图移动任何节点都不再能提高模块性 函数时，得到网络的一个划分，以此作为社区发现结果上述模块性的局部增益 定义为： q，=wcj+weight(i,k)一兰兰-=：掣2一軎一(参2 + ! 掣一, s o , - 2 x z t , w e i g h t ( i , k 1 2 一 等一( 嘉 2 ( 9 ) 公式9 中，w e i g h t ( i ，j ) 表示节点f ，之间边的权值公式前两项为节点f 加入邻点 所在社区勺后模块性函数的变化，后两项为节点i 移出原来所在社区q 后模块性 函数的变化即模块性局部增益等价于将节点i 从原来社区c 。移动到邻点_ ，所在社 区勺带来的模块性变化对公式9 进行化简，得到模块性局部增益定义为： w e i g h t ( i ，七) 一w e i g h t ( i ，七) q 一，勺2 旦面生一 一三二薹! 竺竺! ! ! 三：薹! 竺竺! ! 二兰二兰1 2 w 2 ( 1 0 ) 从公式1 0 可以看到，如果在构造网络时提前统计节点的强度只需要对qc j 两 个社区进行局部的边权计算，即可很快的计算出模块性的局部增益，这使算法有 很高的效率 模块性优化社区发现算法流程如图2 1 所示： 图2 1 模块性优化社区发现算法流程图 f i g u r e2 1t h ef l o w c h a r to fc o m m u n i t yd e t e c t i n g a l g o r i t h m d e g r e e r a t i o =吃+ i e cf e c 即认为社区结构中的任意节点，如果它对于社区内部的边所占的比例较高，就对 社区结构的有更高的贡献 b a u m e s 等人给出了更多的社区结构性度量【2 3 】定义社区内外边强度分别为： 砌纪删砌纪嘶= 鼎 胁砌纪珊砂= 面m 丽- e 丽( c ) 两 ( 1 2 ) ( 1 3 ) 公式1 2 和1 3 中，五( c ) ，n ( c ) 分别表示社区c 中的边数和节点数由此可以定义社 区边强度比为： 掀n s i t y r a t i o ( c ) 2 瓦磊赢磊i n t e 而r n a l 污i n t e 赢n s i t 赢y ( c ) 赢磊而 1 4 ) 。i n t e r 船l i n t e h s i 砷( c 、+ l 泌t e r n a l i m e 孔s i 如ic 、 。 社区内边强度和社区边强度比都在一定程度上反映了社区特性，可以作为社 区结构性度量但是相比之下，节点度数比与原网络的分布更加吻合，在实验中 性度量 2 2 2 重叠节点识别算法 以上述节点度数比或节点强度比作社区结构性度量，通过局部优化社区结构 性，可以实现一种在社区发现的结果的基础上识别重叠节点的算法，进而达到发 现重叠社区的目的 假设将一个节点加入某个社区后，社区的结构性没有下降，那么就认为这个 节点属于这个社区是合理的，即便这个节点已经属于另一个社区另一方面，一 个节点如果作为属于多个社区的重叠节点，假设它必然会与每一个重叠社区中的 至少一个节点有联系，即为重叠节点必须是社区的边缘节点 基于上述两个合理假设，对于本章第1 节中提出的社区发现结果，可以通过 找出所有边缘节点作为重叠节点的可能集合s ，然后尝试遍历所有的节点f s ， 进行加入测试来判断其是否重叠节点具体做法是将f 加入其所有相邻社区中， 并计算相应社区的结构性，判断社区的结构性是否提高如果节点功日入c 后，新 社区c + f ) 的结构性相比c 没有下降，则将f 标记为c 的重叠节点( 同时也属于原 社区) ，并将f 的所有邻点加入s 计算完f 的所有相邻社区后，将f 移出s 算法 执行到s = a 时停止 迭代的将重叠节点的邻点加入s 中，可以避免由于遍历顺序而导致一些较弱 的又先进行识别的重叠节点没有被发现在追求时间而容忍降低一定精确度的应 用中，可以不用迭代的扩展s ，从而降低计算开销更严格的，可以要求节点对 于某个社区必须满足强定义才认为它是该社区的重叠节点，但是这样严格的定义 只能发现重叠性非常强的社区，为了后续实验更好的进行层次结构发现，本文实 验只要求重叠节点满足弱定义 1 4 北京交通大学硕士学位论文 层次重叠社区发现 事实上，可以在任何社区发现算法的结果上，通过本算法进行重叠社区发现， 算法的效果也取决于社区发现算法的准确度因此，对于一些通过降低准确性来 提高计算效率的社区