复杂网络中社区发现方法研究

第 1 章 绪 论1.1 课题背景及意义随着人类的科学技术不断发展前行，人与人、人与物、物与物之间的关系变得越来越复杂多变。这些个人及个体之间的关系在一定的范围内形成了一个个复合而非纷繁的、非简易随机的、具有相互依赖的、有组织的复杂系统。复杂系统具有一定的智能性和自适应性，系统中的个体不是被中央控制而是根据局部信息进行处理行动。研究复杂系统的各种特征和性能成为近一段时间科学领域发展的一个重要方向。为了便于研究复杂系统，人们将复杂系统抽象表现成为复杂网络。复杂网络中节点表示复杂系统的个体，边表示复杂系统中个体之间按照某种规则自然形成或人为构成的各种关系。复杂网络的结构复杂，节点可表述各种不同事物且数量巨大，链接存在多样性，网络结构各不相同且可随时间变化。如图1-1所示为蛋白质关系网络。节点可以有各种属性用来表示个体的特征，边可以赋予不同的权重和方向用来反映个体之间多种多样的关系。复杂网络离人们生活并不遥远，从Inter到万维网、从宏观生态环境中的食物链网到微观的生物个体中的新陈代谢网、从科研合作网络到各种政治、经济、文化网络、从大型电力网络到全球交通网络，可以说，人们生活在一个充斥着着各种各样的复杂网络的世界中。早期受制于信息数据采集能力和方式的限制，复杂网络的规模往往很小。在复杂网络规模较小的时候，人们利用图论和概率统计相关理论挖掘复杂网络的本质和模式。随着计算机科学、互联网技术的发展，人与人沟通方式爆炸式增加，各种关系变得多且复杂，同时，收集保存信息数据变得越来越容易，复杂网络的规模越来越庞大，构建包含成千上万个节点的复杂网络成为越来越普遍的情况。如何在纷繁庞杂的网络中高效地挖掘有意义的信息，成为了当前多学科交叉领域之一[1]。.........1.2 复杂网络相关概念Guimera和Amaral提出了基于模拟退火算法的复杂网络社区发现方法（简称GA算法）[8]。GA算法首先确定网络中的功能模块（社区），模块类似于地图中的国家或地区，粗粒度地对网络进行划分描述。然后，将在网络中的节点分类到这些模块当中。GA算法通过使用模拟退火算法[48]来确定网络中的模块，以便最大限度地提高网络的模块化程度。模拟退火算法是一种通用概率算法，用来在一个大的搜寻空间内找寻命题的最优解。模拟退火算法是源于对热力学中退火过程的模拟，在某一给定初温下，通过缓慢下降温度参数，使算法能够在多项式时间内给出一个近似最优解。退火与冶金学上的退火;相似，而与冶金学的淬火有很大区别，前者是温度缓慢下降，后者是温度迅速下降。模拟退火算法可以分解为解空间、目标函数和初始解三部分。层级聚类社区发现是根据某种规则计算复杂网络中节点之间相似度，相似度高的节点进行合并，相似度低的节点进行分割。分裂方法和凝聚方法是层级聚类社区发现两种主要方法。分裂方法的基本思想是，整个网络初始时看作是一个社区，根据节点间相似度，通过切断相似度较低的节点之间的联系，使其划分为不同社区，重复这一过程直到每一个节点是一个独立的社区；与分裂方法相反，凝聚方法最初将每个节点作为一个单独社区，通过计算节点间的相似度，将相似度高的节点不断合并，直到所有节点都成为一个大的社区。如图1-5所示，层级聚类过程可以用树状图的形式来展示。.........第 2 章 基于稳定标签传播的社区发现方法2.1 引言随着社会计算研究的深入发展，社会网络的重要基本特征之一聚簇结构成为广大学者研究的热点之一。从社会网络中挖掘出聚簇结构的过程，称为社区发现。很多专家学者根据不同角度提出了众多的社区发现方法，如基于谱平分的社区发现方法、基于全局或局部划分的社区发现方法、基于随机游走的社区发现方法、基于模块度的社区发现方法、基于边图思想的社区发现方法等。这些传统社区发现方法在规模较小的社会网络中具有较好的社区发现结果。随着科技的进步，人们沟通方式的变化，扮演的角色多元丰富化，社会网络的规模也在不断扩大。传统的社区发现方法由于算法复杂度高、需要大量先验知识等缺点，无法适应新的需求。快速、有效地对社会网络进行社区发现具有更加重要的意义。标签传播社区发现方法具有近似线性的时间复杂度，能够快速地对社会网络进行社区发现。同时，标签传播社区发现方法不需要事先知道社区数量、社区规模、相关参数等先验知识，仅利用社会网络自身的结构特征挖掘得到社区，对社会网络具有很强的适应性。然而，由于标签传播社区发现方法在标签传播节点队列设置上采取了随机排序方式，在标签传播过程中遇到最多数量的相同标签不唯一时采用了随机选择的方法，这使得在相同网络结构中社区发现结果相差较大，降低了社区发现结果的质量。针对标签传播社区发现方法的随机性问题，本文提出了一种稳定标签传播的社区发现方法。本文对标签传播社区发现方法的标签初始设定、传播节点队列形成和标签传播选择过程这三个步骤分别进行了改进，提高了标签传播社区发现方法的稳定性。首先通过网络中不重叠三角形进行标签初始化，即每个不重叠三角形三个节点赋予相同的初始标签，使得网络中社区结构更加稳定；然后根据节点标签计算得到的熵的大小对节点队列进行排序，相比以往方法队列随机排序方式，降低了随机性；在标签传播过程中，当遇到数量最多的标签不唯一的情况时，采用当前被传播节点的邻接点及其邻接点的标签分布情况确定选择的传播标签，使得标签传播选择过程更加确定。.........2.2 基于标签传播的社区发现本节首先介绍标签传播算法，然后介绍标签传播算法在社区发现方法中的应用及相关改进方法。2002 年，Zhu 等人[132]提出了一种基于图的半监督学习方法标签传播算法（Label Propagation Algorithm，简称 LPA 方法），主要用来解决有监督学习中大量无标记数据的标记问题。LPA 方法把每个数据看作一个节点，数据标记称为节点标签，数据之间的相关性作为节点之间边的权重。LPA 方法首先赋予一部分节点初始标签，这些初始标签信息就像源头，通过节点之间的相似度将已标记节点的标签传播至所有其他没有标签的节点，被传播节点根据其与关于的已标记节点之间的相似度大小，对标记自身的标签进行选择，节点间相似度越高，标签影响力越大，选择对应的标签可能性越大。当所有节点都标记标签且满足一定的稳定现实，则标签传播过程结束。为了解决传统社区发现方法的参数难以确定、算法时间复杂度高等问题，Raghavan 等[58]将 LPA 方法应用到复杂网络中的社区发现，提出了近似线性时间复杂度的 RA 方法。RA 方法首先对网络中每个节点都赋予初始化标签，初始化标签各不相同，然后将节点随机排序形成传播节点队列，根据传播节点队列顺序，依次分析当前被传播节点的邻接点标签分布情况，选择标签数量最多的标签作为当前被传播节点的新标签，重复进行标签传播过程，直到网络中每个节点的标签与其邻接点标签最多的那个标签相同。........第 3 章 基于半监督局部聚类的社区发现方法.......503.1 引言.....503.2 局部聚类社区发现方法.......513.2.1 局部聚类社区发现概述.......513.2.2 局部聚类社区扩张节点选择方法....523.2.3 局部聚类社区扩张终止条件..... 543.3 半监督局部聚类的社区发现......553.4 实验与分析.......613.5 本章小结....69第 4 章 基于半同步标签传播和局部聚类的重叠社区发现方法......714.1 引言.....714.2 重叠社区发现方法........714.3 基于半同步标签传播和局部聚类的重叠社区发现方法.........764.4 实验及分析.......804.5 本章小结....86第 5 章 融合内容主题和链接关系的社区发现方法......885.1 引言.....885.2 基于内容主题的社区发现方法.........895.3 融合内容主题和链接关系的社区发现..........905.4 实验与分析.......955.5 本章小结....99第 5 章 融合内容主题和链接关系的社区发现方法5.1 引言前面三章社区发现方法都是基于网络结构本身进行社区发现，仅仅考虑了节点间的链接关系，而没有考虑节点自身的内容信息层面的属性。本章将对融合内容主题和链接关系的社区发现方法进行研究。节点自身的内容属性和节点间的连接关系一样，都可以用来衡量节点之间的相似度，从而作为社区发现的依据。这种情况在真实的复杂网络经常出现。例如，在博客网站上，每个博主看做一个节点，博主之间的好友或关注关系作为节点之间的连边，博主及其之间关系构成了一个博客网络。每个博主所撰写的博客内容大多是博主所感兴趣的，具有相同兴趣的博主往往会撰写相同主题的博客；博客内容主题相似的博主，也往往对同一个主题都抱有浓厚的兴趣。因此，博客内容可以作为博主节点的内容属性，用来衡量用户之间的相似程度，从而用于社区发现。本章研究融合内容主题和链接关系的社区发现方法的动机是，内容主题和链接关系能够分别从两个不同层面表述节点之间紧密程度，单独利用内容属性或链接关系，都难以取得令人满意的结果。单独利用内容进行社区发现，忽略节点链接关系的疏密，且无关内容信息容易误导错误的社区结构；单独利用链接关系进行社区发现，往往受制于网络稀疏和噪音的影响。因此，将内容主题和链接关系两者融合起来，充分利用两者在不同层面的优势，减弱两者各自的劣势，从而挖掘出更加符合真实情况的社区结果。研究人员提出了多种结合方法。但这些方法大多将基于内容和基于链接关系分成两个独立的部分，将两个独立部分通过标准化后简易相加，而且往往需要预先设定社区数量，以获取节点与所有社区之间的从属度。本文采用 LDA 模型获取内容主题向量，内容主题向量之间的相似度融合到全局的标签传播社区发现方法和局部聚类的社区发现方法。在标签传播社区发现中，考虑传播标签时，标签根据节点之间的内容主题相似度赋予权值。在局部聚类社区发现方法中，社区扩张时，不仅仅考虑与当前社区相邻的节点，而是考虑社区外所有节点，综合节点与社区在内容主题和链接关系的相似度，选择使得社区综合密度增加最多的节点加入社区。

.........结 论随着对复杂网络研究的不断深入，复杂网络中社区发现方法成为多领域研究的关键技术之一，在社会组织网络结构分析、个性化信息服务与强烈推荐等方面具有重要意义。然而，在实际研究情况中，同一网络社区发现结果不一致、网络信息的部分缺失、网络节点角色多元化没有对应到多个其从属社区、网络节点的内容属性被忽略等问题，使得社区发现结果不能满足人们期望。本文针对上述问题，分别从全局社区发现角度和局部社区发现角度，就如何提高社区发现结果稳定性、利用已知背景信息克服网络信息缺失、挖掘重叠社区结构、融合节点内容属性等四个问题开展了深入的研究，与传统方法相比，本文提出的方法取得了稳定性更好、质量更优、更符合实际情况的社区发现结果。具体来说，本文的主要创新点包括以下四个方面：第一，提出了一种稳定的标签传播社区发现方法。为了提高社区发现初始现实的稳定性，本文提出了采用不重叠三角形对节点标签进行初始化方法，避免了大幅度提升算法时间复杂度。针对传统标签传播社区发现方法传播队列随机设置导致社区发现结果不稳定问题，本文提出了基于节点标签熵的随机队列设置方法。针对传统标签传播社区发现方法标签传播过程中标签随机选择问题，本文提出了基于当前被传播节点的邻接点及其邻接点的标签分布情况进行标签选择的方法。分析结果表明，本文提出的方法在保持了传统标签传播社区发现方法的无需先验知识等优点同时，降低了传统标签传播社区发现方法的随机性，提高了社区发现结果的质量和稳定性。第二，提出了基于半监督的局部聚类社区发现方法。为了区分传统局部聚类社区发现方法待加入节点不同的边对当前社区结构的影响，本文提出了一种改进的节点加入社区衡量方法，使得社区发现过程更符合社区结构定义。针对真实情况中网络部分信息缺失所导致的社区发现结果偏差的问题，本文提出了基于奖励惩罚机制的局部社区发现方法，实现了利用已知社区背景信息克服网络部分信息缺失所导致的社区发现结果偏差的影响。分析结果表明，本文提出的方法在部分链接信息缺失的网络中获得符合完整网络结构的社区发现结果。第三，提出了基于半同步标签传播和局部聚类的重叠社区发现方法。针对节点个体角色多元化与社区结构硬划分的问题，本文提出了结合异步传播策略和同步传播的半同步重叠社区发现方法，避免了标签传播震荡问题的同时，在计算效率和社区发现结果质量之间取得了较好的平衡。为了提高种子节点选择质量，本文提出了基于改进 Pageran 算法的种子节点选择方法，利用 Spin-glass模型作为社区扩张节点选择的标准。分析结果表明，本文提出的方法提高了复杂网络中重叠社区结构发现质量。第四，提出了融合内容主题和链接关系的社区发现方法。针对传统社区发现方法仅依靠网络链接关系而忽略了节点内容信息层面属性的问题，本文提出了利用 LDA 模型获得节点内容主题向量及其相似度，并分别融合到标签传播和局部聚类的社区发现方法。分析结果表明，相对于单独基于内容主题或单独基于链接关系的社区发现方法，融合内容主题和链接关系的社区发现方法提升了社区发现结果的准确度，获得了更加符合实际情况的社区发现结果。..........参考文献（略）