基于图着色的并行Louvain社区发现算法研究

发布时间：2016-08-20 06:16

第 1 章   绪     论 

1.1  课题研究背景和意义 
用网络的观点来描述现实世界，最早可以追溯到 1736 年瑞典数学家欧拉对著名的数学问题“哥尼斯堡七桥问题”的研究，并由此开创了数学研究领域中的一个重要分支—图论[1]（Graph Theory）的研究。随着图论研究的深入，随机图理论（Random Graph Theory）开创了复杂网络理论的系统性研究[2]。因此越来越多的研究人员开始关注网络结构复杂性及其与网络拓扑结构之间的关系，其中文献[3]揭示了复杂网络所具有的“小世界”和“无标度”等特殊性质。图(Graph)作为一种描述网络的统一工具，被广泛应用于研究复杂网络结构上的共性。通过图的表示形式，可以将任何一个网络看作是由若干个节点通过特定的方式连接在一起所构成的图，这种表述方法不仅有很好的体现节点间的连接关系，同时还能呈现出清晰的网络拓扑结构，因此图的表示形式已经广泛的应用于对复杂网络进行建模和分析的过程中。 近年来，复杂网络理论已经成为分析网络关系复杂性等相关问题的重要方法之一。复杂网络的一个重要的特性就是网络所呈现的社区结构，所谓的社区结构可以理解为关联个体的集合，而复杂网络则是由若干个社区组成。对于“社区”这个概念，，通常情况下认为[4][20]“社区内部的节点之间的连接相对比较紧密，各个社区之间的连接相对比较稀疏”。随着对复杂网络物理意义和数学特性的深入研究，研究人员发现复杂网络中蕴含着许多丰富的资源和潜在的信息，有效的利用这些信息具有很极高的商业价值和研究意义。然而，随着社交网络，生物信息网等新生应用网络规模的不断扩大，现有的社区发现算法已经不能满足网络规模达到数十亿个节点的处理需求，因此如何高效的对大规模复杂网络进行社区发现已经成为一个重要问题。由于现有算法普遍为串行算法，在对大规模复杂网络进行社区发现时，算法的处理效率较差，无法高效的处理大量的中间计算过程，同时社区发现的精确度也得不到很好的保障。 
........

1.2  国内外研究现状 
复杂网络社区发现技术已经广泛应用于社会学、生物医学、计算机科学等诸多领域。例如在生物医学研究中，识别癌症患者蛋白质功能组。在社会学研究中，通过社区发现分析人际交往的关系网络等等。 复杂网络社区发现算法的研究最早可以追溯到社会学中的研究工作[5]，大量的研究表明，实际网络中所蕴含的社区结构往往具有特殊的功能。社区发现实际上就是通过网络中不同节点的连接关系，将它们划分到不同的社区中，因此对复杂网络进行社区发现具有很高的应用价值。随着对复杂网络社区发现问题研究的不断深入，研究人员通过图论等相关成熟理论来解决社区发现问题，产生了大量不同类型的社区发现算法。根据处理网络方式的不同，复杂网络社区发现算法可以分为两类：基于全局信息的社区发现算法和基于局部信息的社区发现算法。全局社区发现算法主要采用了图论中图划分的思想，通过对整个网络的划分形成社区结构，代表算法有 GN 算法[4]，KL 算法[18]等经典算法，这类算法通常算法复杂度比较高，并且基于全局信息考虑的社区发现算法并不适合对大规模复杂网络进行社区发现。局部社区发现算法主要通过尽可能少的网络局部信息实现社区结构的划分。局部社区发现算法的基本思路是：首先选择初始节点的社区扩展集，然后根据局部的评判标准选择初始节点进行社区合并等操作。经典算法包括基于模块度优化的 LM[38]算法，基于拉普拉斯矩阵谱分析的社区发现算法和基于标签传播思想 RAK[14]算法，其中 LM 算法结合了模块度优化与层次聚类的思想，能够快速，准确的对不同规模的复杂网络进行社区发现，并且社区发现结果具有一定的层次结构特性，该算法是当前社区发现算法研究中重要的参考对象。
.........

第 2 章   相关工作和技术 

2.1  复杂网络社区发现理论
从图论的角度来说，复杂网络是一个由大量节点通过复杂的连接关系互相连接形成的图，因此复杂网络的研究核心主要是通过图的表示形式揭示复杂网络功能和结构之间的内在关系。通过图的表示形式可以反映出网络中不同类型的节点，例如在社交网络中，图中的节点代表不同的个体，而边表示不同人之间的熟悉程度。根据网络是否存在权值及节点间的指代关系，又将图分为有权或无权，无向或有向图。 社区发现技术的研究最早源于社会学的研究工作[5]，本文根据 Fortunato[6]的综述文献，对现有算法进行了详细的总结与比较，将现有研究方法分为以下几类：2002 年 Newman 和 Girvan 提出的模块度[7]  这个社区评价标准以后，才真正意义上的推动了复杂网络的社区发现的研究。在此之后产生了大量基于模块度优化的社区发现算法，这些算法的主要思想是将社区发现问题转化成优化问题，将模块度定义为评价社区划分好坏的质量函数，通过比较模块度数值获取最优的社区划分结构。根据层次聚类的思想，模块度优化算法主要分为两类，第一类算法采用凝聚法，算法自下而上执行，代表算法有 Fast-GN[7]算法、CNM[8]算法。Fast-GN 算法将网络中每个节点看作一个独立的社区，对产生最大模块度的两个节点进行聚类，算法是一个贪心迭代的过程，最终的社区结构可以表示成一个树状图，算法的时间复杂度为O m mn 。CNM 算法采用了更高效的堆数据结构对模块度值进行存储，提高算法的执行效率并减少对存储空间的需求。随后 Blondel[38]结合了模块度优化与层次聚类思想提出了 Louvain  method 算法，算法具有计算速度快，社区发现结果准确性高等特性，是目前基于优化模块度最好的算法。第二类算法采用分裂法，算法自上而下执行.代表算法为 Newman 最早提出的 GN[4]算法，算法通过删除网络中边介数最大的边，实现社区发现，但是算法的复杂度较高3O n ，并且只能处理无权网络。随着对模块度研究的深入，研究人员发现模块度优化方法不能发现小于一定粒度的社区结构[10][11]，Duan[12]应用不同相关性度量方法，改进了以模块度为标准的质量函数，有效的克服了社区发现过程中模块度分辨率问题。 
............

2.2  图的着色理论

图着色问题[34]作为图论中的经典问题，具有广泛的实际应用背景，许多实际问题，例如任务调度问题[36]，存储问题[37]等都可以抽象成图着色问题，同时图着色问题也是一种组合优化问题，由于图的着色问题具有广泛的应用性，因此对图的着色问题进行深入的研究具有重要意义[22]。图着色问题可以分为两种问题，一是求图的着色数问题，另一种是给定着色数 k，要求对图中的节点或边进行着色。图着色主要优化的目标是使用最少的着色数，而着色数与图的规模，节点度，最大节点度以及孤点个数有着紧密的关系 在图着色算法中，对图的节点着色算法是目前解决图着色问题最主要的方法之一。对于无向图来说，用 n 种颜色为图中所有节点进行着色，要求相邻节点之间着色情况不同，并且尽可能少的使用不同颜色为所有节点着色，这个过程成为图的节点着色过程。节点着色算法主要利用了极大独立集的思想，规定每个同色集合中两两节点不相邻，同色节点集实际上是一个独立集，当我们用一种颜色上色时，为了尽可能扩大颜色 1 的顶点数，到达颜色数使用最少的目的，实际上就是找到图的一个极大独立集并为他上颜色1，用第 2 种颜色上色时，同样选择另一个极大独立集着色，当所有节点着色完毕，所用的着色数即所选的极大独立集的个数。 

..............

第 3 章   基于模块度的社区发现并行化方法研究 ........... 11 
3.1  模块度优化函数 ....... 11 
3.2 LM 算法社区发现算法 ....... 13 
3.2.1  算法思想 ............ 13 
3.2.2  算法执行流程 .... 13 
3.3  并行作业划分 ........... 15
3.4  基于模块度的节点状态更新机制 ......... 17 
3.5  动态负载划分 ........... 19 
3.6  本章小结 ......... 19 
第 4 章   基于 OPENMP 的并行社区发现算法设计 ........ 20 
4.1  并行 LM 社区发现算法 ..... 20 
4.1.1  算法思想和执行流程 ............ 20 
4.2  数据结构 ......... 21 
4.2.1  传统的图数据结构 ...... 21 
4.2.2  改进的图数据结构 ...... 22 
4.3  算法设计 ......... 23
4.4  算法复杂度分析 ....... 29 
4.5  本章小结 ......... 30 
第 5 章   实验和测试分析 ........... 31
5.1  实验平台 ......... 31 
5.2  算法实现 ......... 31 
5.3  实验数据集 ..... 33 
5.4  对比算法 ......... 33 
5.5  实验结果和分析 ....... 34 

第 5 章   实验和测试分析 

5.1  实验平台 
本文将实验平台建立在吉林大学高性能中心计算的刀片服务器的计算节点上。具体的实验环境如下： 操作系统：Redhat Linux version 2.6.32-358.el6. x86_64； CPU：Intel(R) Xeon(R) E5-2670，16 核，主频为 2.60GHz，内存：32G。 网络环境：实验室与计算节点之间通过千兆以太网互相连接，通过 SSH 与 VNC 远程登录计算节点。本文提出的并行社区发现算法 P-LM 是基于 Open MP 共享内存编程方式实现的，算法通过 GCC 编译器编译后，可以通过 Linux 命令行的方式控制算法不同阶段的执行方式，实现了一个可以对不同类型的大规模网络数据集进行计算与分析的工具。 如图 5.1 所示，通过输入控制选项—f，输出输入数据的基本信息。例如输入数据的节点数，边数，最大节点度，平均节点度，特殊节点个数等基本信息。 如图 5.2 所示，通过输入控制选项—cp，对输入数据进行粗粒度预处理过程，也就是将网络中孤点以及节点度为 1 的特殊节点进行优先，并且对网络中的节点进行重新编号。这样做记录了下一阶段算法进行着色过程时网络中节点数与边数，并且我们发现由于部分节点进行了社区合并，使得网络的平均节点度发生了变化。 
.........

总结 

随着信息技术的迅猛发展，现实世界中充满着各种各样的复杂网络。由于复杂网络中存在较强的社区结构，因此对复杂网络社区发现算法的研究室人们可以更好地理解复杂网络的数学意义与物理特征。 本文详实的介绍了复杂网络的相关知识以及并行社区发现算法的相关研究，在现有基于模块度优化的 LM 社区发现算法的基础上，提出了一个面向大规模复杂网络的并行社区发现算法（PLM），算法主要通过 Open MP 共享内存思想实现并行的。不同于 LM串行算法顺序选取节点计算模块度增量，本文提出基于图着色的并行作业划分方法，对节点进行着色处理，对不直接相邻的节点并行计算它们的模块度最大增量。还对根据模块度进行社区合并与信息更新的过程进行了优化，提出了节点状态更新机制以及粗粒度的预处理过程。最后为了优化并行算法的计算效率，提出了基于节点度的动态负载划分方法。
.........
参考文献(略)  

本文编号：98625