G-N算法解读

1Girvan-Newman算法（G-N算法）陕西西安201304202１G-N算法概要２G-N算法的思想３边界数的计算4G-N算法存在的问题5社区划分质量衡量标准6G-N算法的缺点7G-N算法的改进8意义３3一、G-N算法概要•GN算法是一个经典的社区发现算法，它属于分裂的层次聚类算法，最初，由MichelleGirvan和MarkNewman提出。其基本思想是不断的删除网络中具有相对于所有源节点的最大的边介数(egebetweenness)的边，然后，再重新计算网络中剩余的边的相对于所有源节点的边介数，重复这个过程，直到网络中，所有边都被删除。4二、G-N算法的思想•流程如下：1、计算网络中所有边的边介数。2、找到边介数最高的边并将它从网络中移除。3、重复步骤1,2，直到每个节点就是一个退化的社区为止。5三、边介数定义和计算•最短路径边介数方法是一种最简单的边介数度量方法，一条边的边介数(betweenness)是指从某个源节点S出发通过该边的最短路径的数目，对所有可能的源节点，重复做同样的计算，并将得到的相对于各个不同的源节点的边介数(betweenness)相加，所得的累加和为该边相对于所有源节点的边介数。6•假设有一个具有m条边和n个节点的图，考虑一种比较简单的情况，假设从任何一个源节点出发，对该图进行搜索，该源节点与其它节点之间都只存在一条最短路径，图中的所有最短路径构成一个最短路径树。利用这颗最短路径树来计算每条边的边介数。71，找到这棵树的叶子节点，并为每条与叶子节点相连的边赋值为1；2，按照自下而上的方向为该搜索树中的每条边赋值，从与源节点S之间距离最远的边开始，其值等于位于该边之下的所有邻边的值之和再加上1；3，按照这种赋值方式，对搜索树中的所有边进行遍历，那么每条边的相对于某个源节点S的边介数就是该边的值，对于所有可能的源节点，我们都重复上述过程；4，将每条边的相对于各个源节点的边介数相加，最终结果就是每条边的相对于各个源节点的边介数，即所有节点对间的最短路径的边介数。1112428•但是，在大多数的实际网络中，每个源节点与其它节点之间并不只是存在一条最短路径，一些节点对之间存在若干条长度相等的最短路径。9从源节点S出发，为每个节点i赋值，该值为从一个源节点S出发到达其它节点i的最路径的数目用wi表示。具体步骤如下:1.定义源节点S的距离为ds=0，并赋予一个权值为ws=1。2.对于每一个与源节点S相邻的节点i，定义它到源节点的距离为di=ds+1，以及该节点的权值为wi=ws=1。3.对于每一个与任意节点i相邻的节点j，我们根据具体情况，采取以下三个步骤之一：如果节点j没有被指定距离，那么，指定其距离为dj=di+1，权值为wj=wi；如果已经指定了节点j的距离，并且节点j的距离值为dj=di+1，那么就要在原来的基础上将节点j的权值再增加wi，使其权值为wj，即wj←wj+wi；如果已经指定了节点j的距离，并且距离为djdi+1，那么，直接执行步骤4。4.重复执行第3个步骤，一直到网络中不存在满足以下条件的节点，即其本身已经被指定了距离，但是其邻接点却没有被指定距离。(1,1)(0,1)(1,1)(2,1)(2,1)(2,2)(3,2)(3,1)(3,3)10(1,1)(0,1)(1,1)(2,1)(2,2)(3,1)(3,3)从节点j经过节点i到达源节点的最短路径的数目与节点j到达源节点的最短路径的数目之比为wi/wj，对于源节点S，应该采取以下步骤计算边界数：1.找到所有的叶子节点f，该叶子节点f不被任何从源节点出发到达其它任何节点的最短路径所经过。2.假设叶子节点f与节点i相邻，那么就将权值wi/wf赋给从节点f到节点i的的边。3.从距离源节点S最远的边开始，从下至上直到源节点S为从节点i到节点j的边赋值为位于该边之下的所有邻边的权值之和再加上1，然后，再将其和乘以wi/wj，最后的结果就是该边的边介数。4.重复步骤3，直到遍历图中的所有节点。11/3(1+1/3+1)*12/3(1+2/3)*1/2(1+2/3)*1/225/611/61112移除具有最高边界数的边13四、GN算法存在的问题•从上面的算法流程中我们可以看到：在不知道社区数目的情况下，G-N算法也不知道这种分解要进行到哪一步为止。•为解决这个问题，Newman等人引进了一个衡量网络划分质量的标准——模块度。模块度函数Q：)(2iiiaeQ14•在此基础上，用模块度函数来确定社区划分质量：•该式的物理意义是：网络中连接两个同种类型的节点的边的比例，减去在同样的社区结构下任意连接这两个节点的边的比例的期望值。•在实际的网络中，Q的值通常在0.3-0.7之间，Q的值越大，网络分裂的结果状态越好，Q值大于0.7的几率很小，Q值的上限是1，当越接近于1时，越能说明网络具有较强的聚类性质，即具有明显的社区结构。五、社区划分质量衡量标准)(2iiiaeQ15•它将网络划分为k个社区。定义一个kxk维的对称矩阵E=(eij)。•元素eij表示网络中连接两个不同社区的节点的边在所有边中所占的比例，这两个节点分别位于的第i个社区和第j个社区。•设矩阵中对角线的各元素之和为∑eii.它给出了网络中连接某一个社区内部各节点的边在所有边的数目中所占的比例。•每行（或列）中各元素之和为ai＝∑eij.它表示与第i个社区中的节点相连的边在所有边中所占的比例。16•GN算法是分裂法，可以用树状图来表示算法过程。•当沿着树状图逐步下移时，每移一步就对应着该截取位置的网络结构的Q值，并找到局部峰值，既是对应着的比较好的截取位置。17此图为美国一所大学中的空手道俱乐部成员间的相互社会关系。1819加入模块度函数后G-N算法的基本流程•1)计算网络中各条边的相对于所有可能的源节点的边介数。•2)移除相对于所有可能的源节点的边介数较大的边，每当分裂出新的社区的时候，需要计算一次网络的模块度Q，并且记录与该Q值对应的网络结构。•3)重新计算网络中所有剩余的边的相对于所有可能的源节点的边介数。•4)重复上述过程，直到网络中没有边为止，然后选择具有最大模块度Q值时的网络结构作为该网络的最终分裂状态。20•GN算法的缺点计算速度慢，边介数计算的开销过大，时间复杂性高，只适合处理中小规模的网络(包含几百个节点的网络)。六、GN算法的缺点21七、改进的GN算法GN算法虽然准确度比较高，分析社区结构的效果比原有的一些算法好，但是它的算法复杂度比较大，因此仅仅局限于研究中等规模的复杂网络。现在，对于Internet、、电子邮件网络等网络的研究越来越多，而这些网络通常都包含几百万个以上的结点。在这种情况下，传统的GN算法就不能满足要求。基于这个原因，Newman在GN算法的基础上提出了一种快速算法(NewmanFastAlgorithm，以下简称NF算法)，它实际上是基于贪婪算法思想的一种凝聚算法，可以用于分析结点数达100万的复杂网络。22•NF算法如下：•步骤1:初始化网络为n个社区，即每个结点就是一个独立社区。则在GN算法中讨论过的矩阵E=(eij)中，初始的eij，和口ai满足：其中ki为结点i的度，m为网络中总的边数。元素eij表示网络中连接第i个社区和第j个社区节点的边在所有边中所占的比例。ai它表示与第i个社区中的节点相连的边在所有边中所占的比例。23•步骤2:依次合并有边相连的社区对，并计算合并后的模块度增量∆Q=eij+eji-2aij=2(eij-aiaj)。根据贪婪算法的原理，每次合并应该沿着Q增大最多或者减小最少的方向进行。每次合并以后，对相应的元素eij更新，并将与i、j社区相关的行和列相加。•步骤3重复执行步骤2，不断合并社区，直到整个网络都合并成为一个社区。最多要执行n-1次合并。整个算法完成后可以得到一个社区结构分解的树状图。再通过选择在不同位置断开可以得到不同的网络社区结构。在这些社区结构中，选择一个对应着局部最大Q值的，就得到最好的网络社区结构。24加权网络中的社区结构划分算法•以上算法所适用的网络大多数是无权网络，然而现实世界中却存在许多加权网络。网络中边的权重大小具有实际意义，比如在社会网络中边的权重可能表示人与人之间关系亲密程度的大小，因此如果忽略权重去分析加权网络将会丢失大量包含在权重中的有用信息。25•把GN算法推广到加权网络中，一个很简单的想法是在把加权网络转换的多重图中计算边的介数，然后移除拥有最大边介数的边。边的权重越大，通过该边的最短路径数目越多，被移除的概率也越大，然而边的权重代表该边所连接的结点对的亲密程度，权重越大，结点对之间的亲密程度越高，从社区结构划分的角度上来说，该边被移除的概率应该越小，所以上述算法的推广是不可行的。26•正确的求解加权网络中边的介数的方法应该是在忽略边的权重的情形下，计算网络中各边的介数，然后定义加权网络中边的介数为以上无权情形下求得的边的介数除以该边的权重，这样权重越大的边得到的边的介数越小，因而被移除的概率越小，符合社区结构划分的定义。27•因此把GN算法推广到加权网络的描述为：首先不计网络中边的权重，计算各边的介数，然后用以上所求边的介数除以该边的权重得到加权网络中边的介数，移除具有最大边介数的边，重复以上步骤，直到每个结点就是一个退化的社区为止。),(]2[21jiijjiijccmkkAmQ28八、GN算法的意义在复杂网络聚类研究中，GN算法占有十分重要的地位，其重要意义在于：首次发现了复杂网络中普遍存在的网络簇结构，启发了其他研究者对这个问题的深入研究，掀起了复杂网络聚类的研究热潮。29