复杂网络的社区发现算法研究

第 1 章 绪论1.1 研究背景及意义自工业革命爆发以来，计算机互联网技术得到高速发展，我们也进入了日新月异的互联网时代。正是因为它的快速发展使得整个各个国家的距离无限缩小，就如同生活在一个村庄里一样，地球村的说法也就不足为奇。当然也渐渐的发现我们衣食住行各个方面的行为活动生活都处于复杂网络之中。 我们所生活的大千世界其实都可以看成一个由若干相互作用的子系统组成的复杂系统,如果我们把子系统抽象为节点，将各个子系统间的相互影响抽象成连接节点的边,复杂系统就会演变为一个复杂网络。例如,流行病传播网和科学家协作网络，社会系统中的人际关系网、生态系统中的神经元网、基因调控网和蛋白、生物新陈代谢网、科技系统中的电话网、因特网和万维网，等等都是典型的复杂网络。复杂网络根据评判标准的不同可以划分为结果也是不同的，如果参考边的权重值为标杆,复杂网络可以分为无权复杂网和有权复杂网。鉴于前网络中的边的方向性,复杂网络可以分为有向网络和无向网络。此外，假如以社区是否有重叠的标准,复杂网络则可以看成是重叠社区网和非重叠社区网组成的交叉混合的大型复杂网络。当然我们也可以综合网络拓扑机构、节点的归属度、边的全权重值等各个方面信息对复杂网络进行归类处理,从而产生了一类结构和内容更加复杂的异质型网络。例如，很多在线的社交门户网络新浪微博网络、知乎论坛、校内网、Faceboo 等都是典型的异质型网络,在这些网络中,节点的定义更抽象、内容也更广泛。与此同时，网络的边代表的内容也千差万别，甚至可能是通过综合分析各种指标后的计算参考值。总之,复杂网络的研究为我们探索生活中各个实体网络提供了新方法、新思路，对复杂网络进行学习与研究，不论在理论创新和项目科研上都有十分重要的意义。 在一般的复杂网络研究中会做出如下定义：用复杂网络中的每一个节点代表一个实体,例如在淘宝网络系统中，每一淘宝玩家都代表一个节点，自然网络中的边则代表制定网络系统中实体之间的相互关系,例如淘宝系统网络的边即代表购买玩家与售出玩家之间是否直接或间接存在交易关系。根据这样类似的复杂网络构建方式，我们可以把许多系统经过建模分析后抽象为网络，然而在构建了真实的网络系统之后,系统内部各元组之间也存在着一定的联系，可以将其进一步抽象为具有一定组织联系的小型划分，这类小型划分共同作用下体现了整个系统的功能，并且这些小型的划分的内部都会按照在一定的切合度组织起来，来维持内部划分内的紧密联系。我们把这样的小型划分称之为为复杂网络的社区。...........1.2 国内外研究现状随着科学技术的发展，复杂网络的研究价值逐渐凸显，研究者们更多的关注复杂网络社区发现中关键节点的探索与研究，到目前为止，对于复杂网络的社区发现已经提出了大量的科研成果，在这众多的成果之中也有一些较为实用的方法，为更好的研究复杂网络提供了便利条件。自 Newman 提出了 GN 算法以来，经过这些年的拓展和创新，复杂网络的社区结构发现算法已经有了较快的反战，很多新的想法不断的被提出，根据社区之间是否重合的特点大体上可以把这些被提出的算法划分为两类：非重叠社区发现结构的算法和识别重叠社区发现结构算法。 通过学习我们可以发现社区结构划分与计算机领域解决图分割的问题有许多雷同之处，因为图的划分问题的核心目的是指将一个网络中所有节点大致平均的划分到两个部分，使得划分后的两个部分子图之间的关联度最小。这种定义的方式与复杂网的社区结构的定义有较高的一致性，所以我们自然可以用雷同的方法对复杂网络进行划分处理进而得到相应的社区机构，在实际解决问题时，可以一般也通过迭代法进行迭代处理，把一个复杂网络先分割成两个部分，然后对划分后的两个部分分别使用图分割方法进行计算，一直迭代下去直到得到最优的划分结果为止。ernighan-Lin 算法最开始是受到一些电路问题的启发，此电路问题旨用最少的链接数量完成电路板的链接。通过使用模块函数Q，对模块内部及模块之间完成边的数量优化处理。初始结点既可以所及选取，又可以通过图的拓扑结构有针对性的选取，然后将候自选集平均分为两组，如果函数 Q 的值增加则交换节点，重新计算 Q 函数的值，依次选择最大的 Q 进行下一次计算。ernighan-Lin 算法执行效率较高算法复杂度并且算法的为 O(n2logn)，如果该图变为稀疏图则算法复杂度可以优化到 O(n2) 当然这种算法也存在一定的依赖性，如果初始化的节点选取不当就很难达到预期的预期的效率。...........第 2 章 复杂网络与社区发现相关理论2.1 复杂网络的简介自然界中普遍存在的一个有机的、完整的整体可以称之为一个系统，系统内各个元素相互结合、相互影响、相互依赖、使这个整体具有一定的功能特性，自然构成系统的各个元素是不能离开整体而孤立的存在。 在复杂网络可以参考计算机数据结构中图论的先关概念，它代表由节点和节点间的边所构成的图。网络中的图同样具有一定的物理意义，与通讯网络、运输网络一样，它是从大量同类型的具有实际意义的问题中提炼出来的。复杂网络与之前提到的系统之间存在紧密的联系，倘若用点来表示系统中的元素，节点之间的边的属性代表个元素之间的关联关系，此时我们就可以把网络看成是一个系统。 复杂网络从定义上来看，所表述的是具有很高复杂性的网络，同时具有网络和系统的双重含义。使用复杂网络这一概念模型的使用可以更好的描述系统之间的关联关系，既可以清晰的表述网络中图的拓扑结构，又能体现系统现实和功能等各方面指标。对于复杂网络概念的我国的著名科学家钱学森先生给出了这样一个定义[13]：具有自组织、自相似、吸引子、小世界、无标度中的部分或是全部性质的网络称为复杂网络。在这里做出几点解释，自组织是指复杂网络在不需要外力的条件下可以自行运转，各个部分乃至各个部分内元素之间能够按照某种特定的形成协调稳定的结构。而自相似则代表一种图形的每个部分在几何形状上与整体间具有一定的相似度。 综上所述,现实世界中的大多数系统都具有很高的复杂度,并可以用网络的相关概念按照一定的规则进行转换，可以把经过网络概念、图论基础抽象化后的复杂系统称之为复杂网络，网络的规模和其在结构与功能上的异构特征是复杂网络复杂度高的主要根源。.............2.2 复杂网络的特性2.2.1 复杂性复杂性是复杂网络最直接的属性，我们之所以称复杂网络具有复杂性主要体现在以下几个方面[8]： (1) 网络的规模巨大。对于规模不大的网络，我们能够直接观测其形态特征。而在显示世界的网络一般都具有成千上网个节点，在这样的条件，研究复杂网络结构、功能及特性就变得很复杂。 (2) 拓扑结构的复杂。每个复杂网络包含许多子网，每个子网内部的连接结构在某种程度上具有一定的规律性，并非都是随机的，有这些结构各异的子网相互结合，自然复杂网络的拓扑结构也变得异常复杂，而且网络内的连接可能每时每刻都发生变化，节点与节点之间的连接边也会存在权重、方向性等属性。 (3) 节点的复杂性。复杂网络中的节点具有高度的代表性，在实际网络科研课题研究中，即便是权重、方向属性具有一致性，但代表的具体意义也仍旧千差万别，例如在社交网络中，每个节点代表社区内的每个成员，而在商品交易网络模型中，则节点代表了具体的从属于某一类的商品，在此基础上，同一个复杂网络中的节点也可能代表完全不同的含义，出动力学复杂性，节点的现实也会受到时间、空间、环境等多方面因素所左右。

...........第 3 章 局部相似性聚类预处理的社区发现算法 .......... 203.1 研究背景 ............. 203.2 局部相似性聚类预处理算法相关概念 ..... 213.3 局部相似性聚类预处理算法 ........... 273.3.1 算法思想 .... 273.3.2 算法过程 .... 293.3.3 算法总结 .... 303.4 本章小结 ............. 30第 4 章 局部相似聚类预处理算法实验 ...... 314.1 模块度与纯净度 ........... 314.2 海豚数据集 ......... 324.3 空手道俱乐部数据集 ............. 344.4 美国大学橄榄球数据集 ......... 354.5 本章小结 ............. 38第 5 章 总结与展望 ........ 395.1 本文总结 ............. 395.2 研究展望 ............. 39第 4 章 局部相似聚类预处理算法实验4.1 模块度与纯净度在处理复杂网络社区发现问题的研究中，一般会引入模块度以及纯净度等基本参考指标用来验证算法的准确，与此同时对算法的效率进行评价。Newman 在提出了 GN 算法之后，模块度这一概念就被广泛的运用，渐渐的已经成为参考社区划分质量优劣的重要指标，对衡量社区发现结构稳定性与算法可靠性方面做出了卓越的贡献，然而我们不由得思考的是这样一个问题，此项参考指标既然能够评价社区发现的处理结果的好会坏那么也应该可以参考这个指标完成社区发现算法的改进与优化，正式由于这样的思考，基于模块度优化的社区发现的方法被提出。 模块度方法的主要思路是在复杂网络中针对节点度的分布情况进行分析，规定当前网络标记为 G，G 由 m 条边与 n 个节点共同组成。设定节点 ni与 nj为当前复杂网络中的两个随机的节点，其节点的度数分别用，di与 dj表示,则此时随机节点 ni与 nj之间的边的期望表述式为 didj/2m，在实际节点对之间连接可能会与预期连接数量有差别，可以使用 Aij-didj/2m 计算。...........总结本文提出了基于局部相似度聚类算法预处理的社区发现算法，鉴于利用社区发现算法在构建相似度后可以转换为聚类算法的基本思路，使用局部相似指标构建相似矩阵，使用谱聚类算法，参考特征间隙标准对当前网络进行预处理划分(如果先验信息中已经给出聚类中心参数则可以直接跳过特征间隙处理阶段)，再使用考量网络全局拓扑特性 Page Ran 算法作为核心节点的选择的参考指标，在预处理的每个社区结构内选择重要节点，计算每个非中心节点对每个重要节点所形成的社区结构的贡献值即节点适应度，选取适应度更大的节点依次加入相应社区，进而完成网络社区划分，最后融合 -means 算法优秀思想，对得到的划分结果进行迭代计算直至社区结构达到稳定现实。 需要特别指出的是，一部分复杂网络社区发现算法大多针对网络中重要节点为核心，进而进行社区拓展，当处理核心节点不明晰的网络时，划分的结构很难得到保证，本文提出的方法考首先运用谱聚类算法对当前网络社区结果进行预处理，克服了上述情况，使网络结构初始划分得到保证，同时由于在谱聚类算法过程中使用特征间隙求出初始聚类个数，社区结构有一定的效率做保证，因此，可根据初始划分社区数目作为一个合理的预选择参考值，同样避免 -means 算法在不知晓社区划分个数参数 的情况下带来的效率问题，并在此基础上运用Page Ran、节点适应度等参考指标对重要节点的选择及社区合并算法进一步优化，进而完善社区结构。 在实验阶段，分别使用了空手道俱乐部数据集、海豚数据集、美国大学橄榄球俱乐部数据集，实验结果证明了基于聚类预处理划分的社区发现算法正确性，并且保证了一定的效率。.........参考文献(略)