复杂网络社区提取综述

1、复杂网络论文汇报2013.10 网络 基本概念 复杂网络及其特性 社区提取及一些经典算法网络 传统的对网络的研究最早起源于著名的欧拉七桥问题。许多真实系统都可以用网络的形式加以描述，一个典型的网络是由许多结点与连接结点之间的边组成的。结点代表系统中的个体，边则表示结点之间的作用关系。通常是当两个节点之间具有某种特定的关系时连一条边,反之则不连边. 有边相连的两个节点在网络中被看作是相邻的. 我们把网络不依赖于节点的具体位置和边的具体形态就能表现出来的性质叫做网络的拓扑性质,相应的结构叫做网络的拓扑结构.基本概念 图 （网络） 由若干个不同顶点与连接其中某些顶点的边所组成的图形就称为图。（顶点的

2、位置以及边的曲直都是无关紧要的，而且也是没有假定这些顶点和边都要在一个平面内，只关心顶点的多少和这些边是连接哪些顶点的），通常用大写字母G表示图，记作G = (V, E)。其中顶点集合和边的集合分别用V(G)和E(G)表示。同时集合E(G)中的每一条边都与集合V(G)中的一对结点相对应，另外由一条边相互连接的两个结点称之为相邻节点。V(G)中的元素称为顶点（Vertex），顶点个数称为图的阶（Order）。E(G)中的元素称为边（Edge），边的个数称为图的边数（Size）（规模）。 有向图和无向图 如果任意的结点对(i,j)和(j,i)对应着同一条边,那么这种图就被称为无向图，即(i,j)=

3、(j,i)。若(i,j)(j,i)，则为有向图。对应有向网络和无向网络。路径、迹、路 在图G(V, E)中，若从顶点vi 出发，沿着一些边经过一些顶点vp1, vp2, , vpm，到达顶点vj，则称顶点序列(vi, vp1, vp2, vpm, vj)为从顶点vi 到顶点vj 的一条路径（Path，或称为通路），其中(vi, vp1), (vp1,vp2), , (vpm, vj)为图G 中的边。如果各边都不相同，则称该路径为图G 的一个迹。顶点互不相同的迹称为路。 图（网络）的存储表示 邻接矩阵 除了记录各个顶点信息的顶点数组外，还表示各个顶点之间关系的矩阵，称为邻接矩阵（Adjacenc

4、y Matrix）。 对于一个无权无向的网络来说,在它的邻接矩阵W的表示方法中,如果网络中的节点i和节点j之间存在连接的边,那么元素Wij=1,如果节点i和节点j之间没有边相连接则Wij=0,则由此可以知道该邻接矩阵是一个对称矩阵。 对于有向网络,邻接矩阵则代表着某个节点的出入度数目,其中第i行上非零的列数代表节点i的出度,第j列上非零的行数代表节点j的入度;对于加权网络中,如果结点i和结点j之间存在一条边,那么元素Wij的值等于节点i和节点j之间的相应的权重的值。 laplace矩阵（度矩阵减邻接矩阵） 路径的长度、距离、平均路径长度、直径、 路径中边的数目通常称为路径的长度。 单源最短路径

5、 就是固定一个顶点，将此顶点当作源点，求源点到其他各个顶点的最短路径。节点的度 结点i的度定义为与这个结点i相连接的其它结点的数目。换句话说,也就是与节点i相连接的边的数目。度有入度和出度之分，节点的度描述节点性质的一个特别重要的概念，在网络中,如果某个节点的度很大,说明这个结点对于整个网络来说非常重要。（核心节点算法就是先找出度数最大的点） 度分布 网络中的度分布则是描述网络性质的一个非常重要的统计量，无向网络中的节点的度的分布情况可以用分布函数P(k)来表示,它所代表的含义是随机地选择网络中的一个节点度为k的概率，换句话说就是在网络中度为k的节点数目总数占网络中所有节点总数的比例。对于有向

6、网络，其度分布还可细致地分为网络的入度分布(in-degree distribution)和出度分布(out-degree distribution)。随机网络和复杂网络有不同的度分布。介数（居间中心性）(betweenness) 网络中的介数分为节点介数和边介数。 通常在整个网络中,如果从某一个节点沿着最短路径到达另外一个节点时,一般会经过若干节点,但是这些节点的经过次数不一样,网络中的有些节点被经过的次数明显高于别的节点经过的次数，这种现象就有节点的介数来描述。节点介数定义为网络中所有最短路径中经过该节点的路径的数目占最短路径总数的比例.边介数定义为网络中所有最短路径中经过该边的路径的数目

7、占最短路径总数的比例.介数反映了相应的节点或者边在整个网络中的作用和影响力，是一个重要的全局几何量，具有很强的现实意义。GN算法中某条边的边介数是指网络中通过这条边的最短路径的数目。节点k的介数的计算公式为：公式 2.4中， Ck (i , j)表示节点 i和节点 j 之间的最短路径中经过节点 k的数目，C (i , j )表示节点 i 和节点 j 之间的最短路径的总数目。边介数的定义类似于节点介数的定义。 聚类系数（聚集系数）（簇系数） 网络的聚集系数表明复杂网络中的节点的聚集情况也就是网络的聚集性,换句话说,就是同一个节点的两个相邻节点仍然是相邻节点的几率有多大,网络的聚集系数反映了网络中

8、的局部特性例如在朋友关系网络中,你的两个朋友之间很有可能彼此也是朋友。聚类系数另一个图形化的等价定义局部集聚系数：蓝点有三个邻接点（白点）。如果三个白点都相互连接（上图），那么蓝点的集聚系数是33=1；如果只有两点之间相连（中图，只有一条边），那么集聚系数是1/3；如果没有两点是相连的接，那么集聚系数就是0。贪婪算法（贪心算法） 在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。比如k-l算法。一些网络演化模型（没仔细看） 规则网络简介右图是一种最简单的规则网络模型，在其中，N个节点排成环，每个节点与其邻近的m个节点连接（

9、这里m=4），很容易得到该网络的主要统计性质。度分布：p(k)=1(k=m)或0（km）各点聚类系数：3/(0.5*4*3)=1/2（邻接点之间的实际边数比上最大变数）网络的聚类系数：1/2(与N无关)平均路径长度：复杂系统与复杂网络p148（没看懂）与N成正比。 大聚类系数，大平均路径长度。ER随机网络模型（没仔细看）（1）给定网络节点总数为N。（2）在每一步，任意选择两点， 以概率p=(2n)/(N(N-1)把它们连边。其中n是给定的总边数（n0.5*N(N-1)）0.5*N(N-1)是最大可能连边数。（3）当边数达到n时停止演化。度分布是泊松分布，聚类系数与N成反比，平均路径长度与N成正

10、比。 小聚类系数，小平均路径长度。 网络理论研究先后经历了三个阶段，分别为规则网络（真实系统各因素之间的关系可以用一些规则的结构表示）、随机网络（两个节点之间连边与否不再是确定的事情,而是根据一个概率决定， 数学家把这样生成的网络叫做随机网络）、复杂网络（钱学森给出了复杂网络的一个较严格的定义：具有自组织（自我完善，不断提高）自相似（自己与自身的一小部分相似）、吸引子、小世界、无标度中部分或全部性质的网络称为复杂网络）。 大多数真实网络既不是规则的，也不是随机的，而是呈现一定规律的复杂网络。 复杂网络的研究大致可以描述为三个密切相关但又依次深入的方面：大量的真实网络的实证研究，分析真实网络的统

11、计特性；构建符合真实网络统计性质的网络演化模型，研究网络的形成机制和内在机理；研究网络上的动力学行为。复杂网络复杂网络的特性 大量的实证研究表明许多真实世界的网络具有三个基本性质：小世界特性(smal l world character)，无标度特性(scale-free character)和社区结构（community） 一、小世界（较小的平均最短距离，六度分隔） 小世界特性是指与相同规模（图的边数）的随机网络相比，该网络具有较小的平均最短距离和较大的簇系数。 把同时具有较大的族系数和较小的平均距离等两个统计特征的复杂网络,称为小世界网络。WS小世界网络模型（没仔细看）小世界网络模型的平均

12、路径长度类似于ER随机网络模型，聚类系数类似于规则网络。从规则网络开始，以概率p断开一个节点,随机地从网络中选取一个节点进行连接即保持边的一个端点不变,而另一个端点取为网络中随机选择的一个节点如果所选的节点已经与此节点相连,则再随机选择别的节点来重连。在构造过程中,如p=0则网络为规则网络,p=1时,则为随机网络；op1时 网络同时具有大的聚集系数和小的平均路径两个特征,而这样的网络我们称之为小世界网络。 大聚类系数，小平均路径长度。二、无标度（无尺度）（马太效应，富人穷人） 把网络的度分布符合幂律分布的网络,称为无标度网络。 幂律分布这一特性，正说明了无尺度网络的度分布与一般随机网络的不同。

13、随机网络的节点度分布属于正态分布，因此有一个特征度数，即大部分节点的度数都接近它。无尺度网络的度分布是呈集散分布：大部分的节点只有比较少的连接，而少数节点有大量的连接。由于不存在特征度数，因此得名“无尺度”。 无尺度网络的特性是：当节点意外失效或改变时，对网络的影响一般很小，只有很小的概率会发生大的影响，但当有集散节点受到影响时，网络受到的影响会比随机网络大得多。BA无标度网络模型 在双对数坐标系中幂律分布的图像呈直线。指数就是直线的斜率。 p(k)k-a等价于logp(k)-alog(k)（反比关系） 指数a是直线的斜率。（没研究a）()aP Xkk三、社区结构 整个网络是由若干个“社区或“

14、组构成的。每个社区内部的结点间的连接相对非常紧密，但是各个社区之间的连接相对来说却比较稀疏（网络中的顶点可以分成组,组内连接稠密而组间连接稀疏）。我们将复杂网络的这种结构特征称之为复杂网络的社团结构或社区结构。 社区结构是复杂网络的一个重要的特性，社区也被称为簇，大量研究表明网络是由各种不同类型的节点构成的，一般情况下，在不同类型的节点间存在较少的边，而在相同类型的节点间会有较多的边。位于一个子图内的节点和边组成一个社团。 复杂网络社区结构还有一个很重要的特性,即是它的层次特性现实中的网络是由一个个较小的社团组成,而这些社团又可以包括更小的社团。发现网络中的社团结构,对于了解网络结构，分析网络

15、特性都具有很重要的意义。具有社团结构性质的网络网络的社区社区结构的几种定义（没仔细看）派系社区分解算法及度量标准 社区分解算法的几种分类在复杂网络社区结构划分的研究中，社区结构划分算法所要划分的网络大致可分为两类，一类是比较常见的网络，即仅包含正联系的网络(网络中边的权值为正实数)；另一类是符号社会网络，即网络中既包含正向联系的边，也包含负向联系的边。因此划分网络中社区结构的算法相应分为两大类，而对于第一类网络又提出了许多不同的社区结 构划分算法，划分第一类网络社区的传统算法可分为两大类，第一类是基于图论的算法，比如KL算法（增益函数）、谱平分法、随机游走算法和派系过滤算法等；第二类是层次聚类

16、算法，比如基于相似度度量的凝聚算法和基于边介数度量的分裂算法（GN算法）等。早期分析社团结构的算法,包括基于计算机科学中的图形分割和社会学中的层次聚类两大类,前者主要包括Kernighan-Lin算法和谱平分算法两种;而后者则以GN算法为代表。之后,又有很多学者在GN算法的基础上提出了一系列算法按照复杂网络中社团形成的过程,网络中社团结构的划分思路大体可以分成4类:凝聚过程、分裂过程、搜索过程和其他过程。凝聚过程是以顶点为基础,通过逐步凝结形成社团。其主要步骤为: 1) 设定某种标准可以衡量社团与社团之间的距离或相似度; 2) 将网络中的每一个顶点视为一个社团,所以网络中有多少顶点就有多少初始

17、社团,并且每个社团只包含一个顶点; 3) 根据设定的衡量标准,计算社团与社团间的距离或相似度,并将距离最近的社团或相似度最高的社团合并在一起形成新的社团; 4) 重新计算每对社团间的距离或相似度; 5)不断重复合并及重新计算的步骤,直到所有顶点都聚集成一个社团。分裂过程则相反,它首先将网络中的所有顶点都视为一大社团,通过逐步分割这个大社团形成小社团。其主要步骤为: 1) 设定某种衡量顶点间密切程度或边对网络结构影响程度的指标; 2) 按照一定标准进行删边;3) 不断重复计算和断边的过程,网络将被划分成一个个越来越小的连通社团,这些连通社团就是对应某一阶段的社团; 4) 全部过程以每个顶点被独立

18、地分成一个社团为终点。整个过程可以用一个直立的树状图表示,过程方向与凝聚过程相反。搜索过程不拘泥于统一的凝结或分裂,而是建立一个逐步优化目标的探索过程,社团结构直接由最后的优化结果给出。以上提到的所有算法,其共同特点是致力于尽快且尽量准确地求得整个网络的社团构。因此,这些算法的前提是需要知道整个网络的拓扑结构。局部社区发现 在不知道整个网络拓扑结构的情况下，要求寻找一个起始节点所在社区，而无须找到网络中所有社区的算法叫做局部社区发现。局部社区发现特别适用于Web上的社区发现，因为Web上的网页规模极大，而且动态更新较快，想得到Web的全局拓扑结构几乎是不可能的，因此只能从局部出发，挖掘出与某个

19、起始网页主题相关的的其他网页，或者说挖掘出用户感兴趣主题的网页及信息。这样就可以节省开销而且具有针对性。全局社区发现 在知道整个网络拓扑结构的情况下，寻找该类网络中所有社区的算法叫做全局社区发现。全局社区发现算法更多的是针对在某一段时间内，拓扑结构相对稳定的网络，这也是目前研究得较多的一个方向，理论成果也很丰硕。比较经典的有基于模块度优化的方法、图分割法（大多数图分割方法均基于迭代二分法：首先将图按要求分割成2个子图，然后再分别对这2个子图进行分割，如此迭代下去直至获得所要求的子图个数。如KL算法，谱二分法）、层次聚类法（分为凝聚法和分裂法，GN算法为代表）、重叠社区发现方法和一些其他方法等。

20、存在的问题目前社区发现算法的研究主要存在以下一些问题：1 对大规模网络难以处理现有的社区发现算法大多不能处理大规模的网络，它们的时间复杂度较大。2 中心点个数难确定（凝聚算法中）（不明白） 有些社区发现算法是基于网络图的中心点，它们都是以度数最大的一些节点，称之为中心点，为起始节点进行扩展或者行走，中心点的选取很大程度上决定了最终社区划分。然而，这些算法对于网络中心点的数目一般难以确定，只能进行一定程度的尝试，通过重复设置中心点个数，多次重复运行算法，然后选取最好的结果作为社区划分。3 社区结构不稳定 目前很多社区发现算法都存在一定的随机性，都是因为种子节点选取的随机性而造成最终得到的社区结构

21、不稳定。不同种子节点的选取会造成得到不一样的社区结构。4 要求提前给定社区个数（GN算法） 有的社区发现算法需要提前指定该算法要找到的社区个数，也即把网络划分成指定个数的社区，一个具体网络的真实社区个数是很难预先知道的，而社区个数也正是算法需要找到的，这样的算法显得有些本末倒置。模块度（NG 模块度）（衡量分割后社区的好坏，网络分解的质量，GN算法）其基本假设是：随机网络没有社区结构。 Q=0时一个社区；Q=1时k个独立的社。GN算法是分裂法，可以用树状图来表示 算法过程。当沿着树状图逐步下移时，每移一步就对该截取位置对应的网络结构计算Q值，并找到局部峰值，既是对应着的比较好的截取位置。几种社

22、区提取算法及其优缺点 KL算法 Kernighan Lin 算法是一种试探优化算法，它基于贪婪算法原理的二分法该算法将网络划分为两个已知大小的社区 它的基本思想是引进一个增益函数Q，定义为两个社区内部的变数减去链接两个社团之间的变数，然后寻找最优方法使Q 值达到最大（Q定义为两个社区内部的边数减去连接两个社区之间的边数，然后寻找使Q值最大的划分方法。） 这种划分的方法的缺陷是只能用于划分存在两个社团结构的网络，并且必须事先知道该网络的两个社区的规模面临着如何事先知道网络中的社区数目，以及确定二分法要重复到哪一步停止的问题。这些局限使得该算法很难应用于实际问题 KL算法的不足： 找到的解往往是局

23、部最优而不是全局最优解。 KL 对初始解非常敏感，它需要先验知识。 KL算法的时间复杂性: O(tn2)，t 表示算法终止时的迭代次数，n表示网络节点个数。 KL算法可描述如下1将网络中的结点随机地划分为已知大小（阶数或规模，阶数是顶点数，规模是边数）的两个社区。在此基础上，考虑所有可能的结点对，其中每个结点对的结点分别来自两个社区。2引进增益函数Q，Q表示两个社区内部的边数减去连接两个社区之间的边数。3计算每对节点的Q（交换前）值和没对节点交换后的Q（交换后）值，求=Q（交换后）Q（交换前），（负值怎么办，是安正负比较大小吗？）找出最大的 ，并将其对应的节点交换。并记录交换后的Q值。注意节点

24、对的点必须位于两个社区。4重复这个交换过程，规定每个结点只能交换一次，直到某个社区内所有的结点都被交换一次为止。5当交换完毕后，便找到上述交换过程中所记录的最大的Q值。这时对应的社区结构就认为是该网络实际的社区结构。注：贪婪算法：贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。规模:边的数目。GN算法层次聚类是寻找社会网络中社团结构的一类传统算法。它基于各个节点之间连接的相似性或者强度,把网络自然地划分为各个子群。根据加边或去边,该类算法又可以分为两类:凝聚方法和分裂方法。，层次聚类方法通常

25、采用谱系图或树状图来记录算法的结果，从而描述整个网络从单个独立的子群逐步凝聚为整个网络或者从整个网络逐步分解为若干个越来越小的子群的连续过程，其中底部的各个圆代表了网络中的各个结点。当水平虚线从树的底端逐步上移，各结点也逐步聚合成为更大的社区。当虚线移至顶部，即表示整个网络就成为一个社区。在该树状图的任何一个位置用虚线断开，就对应着一种社区结构。分裂方法中最典型的算法是GN方法。它的基本思想是通过不断地从网络中移除介数(Betweenness)最大的边将整个网络分解为各个社区。其中，边介数定义为网络中经过该边的最短路径的数目。它为区分一个社区的内部边和连接社区之间的边提供了一种有效的度量标准。

26、GN算法的基本流程如下1计算网络中所有边的介数（网络中经过该边的最短路径的数目）； 2找到介数最高的边并将它从网络中移除； 重复步骤1和2，直到每个结点就是一个退化的社区为止。GN算法弥补了一些传统算法的不足，GN算法有两个缺陷,首先对于网络的社团结构并没有一个量的定义，因此不能直接从网络的拓扑结构来判断它所求的社团是否是实际网络中的社团结构。其次在不知道社团数目的情况下,GN算法也不知道这种分解要进行到哪一步终止。为解决这些问题,Newman等人引进了一个衡量网络划分质量的标准-模块度。GN算法考虑网络全局，划分社区准确度较高，但是对网络社团结构缺少量的定义，需要事先知道社团个数GN算法的缺

27、点GN的最大缺点是计算速度慢，边介数计算的开销过大O (m n)， GN具有很高的时间复杂性O(m2n)，只适合处理中小规模的网络(包含几百个节点的网络)。core-vertices算法（核心顶点算法）基于一些节点拥有最高的度数（从一个顶点V引出的边的条数，称为V的度数），它们可能属于某一社区的核心，我们提出了核心节点算法。首先找到核心节点并将其看成最初的社团，然后计算各社团和其邻接点的亲密度（intimate degree），根据亲密度来吸收新节点到该社区。该算法可以在社区提取的过程中精确地找到公共节点。算法步骤如下1、找出度数最大的节点作为核心节点（初始社区），分成几个社区就找几个节点。2

28、、计算各核心节点和其邻接点的亲密度，亲密度定义为 NCCN是社区和其邻居共同连接节点的个数（如果核心节点与邻接点有连接就加1否则不加），分母kj是邻居（邻接点）的度，n是节点的个数（阶数），C代表不同的社区。3、比较亲密度大小，将邻接点归于亲密度大的社区内，找出公共节点。4、计算公共节点与各社区内节点的亲密度，根据亲密度的最大值来决定把公共节点归于哪一个社区。5、计算模块度衡量网络分解的质量。6、计算时间复杂度。（没看）Dijkstra 算法（单源最短路径算法）（介数）用于解决最短路径问题的算法被称做“最短路径算法”， 有时被简称作“路径算法”。所谓单源最短路径问题是指：已知图G=（V，E），我们希望找出从某给定的源结点SV到V中的每个结点的最短路径。Dijkstra算法是典型的最短路径算法。它的关键思想是以起始点为