数学执来与表用
复杂网络社区结构发现算法概述
杨泽俊1.2何柳3
(1.三峡大学湖北宜昌443000；2.湖北三峡职业技术学院湖北宜昌443000;
3.三峡旅游职业技术学院湖北宜昌443000)
算法分析
摘要：分析了一要经典的复杂网络社区结构的发现算法，希望对社区发现同题的进一步研究及若干问题的早日解决越到一定的作业，关键调：复杂网络社区结构
中图分类号:TP3 1引言
文献标识码：A
文章编号:1007-9416(2013)03-0145-01
较小，而不同社区的节点对介数较大，为此可以比较好的划分社区。
复杂网络！是现实世界中复杂系统的一种抽象表现形式，网络中的节点是复杂系统中的个体，节点之间的边则是系统中个体之间按照某种规则而自然形成或人为构造的一种关系，网络节点被划分成著干组，使得组内节点之间的连接比较密，而不同组节点之间的连接则比较稀少，这样的划分结果被定义为复杂网络的社区结构。通过对复杂网络社区结构的研究，可以将复杂网络社区结构的研究理论成果应用到具体问题当中去，如可以通过社区结构发现资源分布、病毒的传插等。
2基于Laplace图特征值的谱二分法s)
令G是一个具有n个节点的无向图，G的Laplace矩阵L是一个n ×的对称矩阵，它的对角线元素LI是节点的度，表示节点和节点 j的连接情况，当和之间有边相连时，则Lj=-1，否则Lij=0。显然， L每一行的和以及每一列的和均为0,因面，向量1=(1,1,1,1)是L的相应于特征值0的特征向量。可以知道，此时L存在g个与特征值0对应的特征向量vk,k=1,2,L,g,其中,v的对应于分支Gk的分量为 1.而其余分量为0。
因为对称矩阵的任意2个特征值所对应的特征间量相互正交，所以Laplace矩阵L的任意对应于非零特征值的特征向量均正交于向量L一(1.1,1,1)，以此所有非零特征值的特征向量必须具有正分量和负分量。如果2个子图间连接很少，则将存在一个特征间量，它的特征值近似于0，它的特征间量的正分量对应一个子图，负分量对应另一个子图。
所以我们可以通过观案第二最小的特征值所对应的特征向量，依据特征值元素的正负将一个网络分解成2个社区，这就是谱二分法。 3WH算法
在明确知道社团数目的情况下，Wu和Huberman提出了基于电阻网络电压谱的快速谱分割法。利用此算法不仅可以求出复杂网络的社团结构，还可以在不考虑整个复杂网络扩大社团结构的情况下，寻找一个已知节点所在的整个社团。
令图G=(VE)可以分为两个社团G1和G2,且已知节点M和N分别属于这两个社团。令节点M为源节点，电压值为1，节点N为终节点，电压值为0，此时，网络中的每条边都视为一个阻值为的电阻。复杂网络就可以看成一个电阻网络，可以利用基尔霍夫定理求各个儿点的电压值。然后，选取一个电压阔值V(0V，认为它属于源节点M所在的社团，反之则为终结点N所在的社团。可以利用谱线图来记录电压值：在0～1的范围内，将电压值从大到小进行排列，然后用不同位置的谱线图来记录电压值。然后选取某个阔值，认为该阅值左边的线相应的节点属于一个社团，而
右边的那些节点就属于另一个社团。 4GN算法
GN算法的思想是不断从网络中移除介数最大的边，边的介数是指通过该边的最短路径的数目。因为同一社区内的节点对介数
设网络矩阵中对角线上各元素之和为Tre=Ze。该矩阵给出了网络中连接某一个社区内部各节点的边在所有边的数目中所占比例，定义每行(或者列)中各元素之和为,=之，它表示与第i个社区中的节点相连的边在所有边中所占的比例，用下式来定义模块性的衡量标准：Q=Z(es-a,)=Tre-e=l。上式的意义是：矩阵网络中连接两个同种类型的节点的边的比例减去在同样的社区结构下任意连接这两个节点的边的比例的期望值。如果社团内部边的比例不大于任意连接时的期望值，则有Q=0。Q的上限为Q=1，而Q越接近这个值，则说明社团结构越明显。
GN算法中，如果计算关于有m个节点和n条边的网络的所有边的介数则需O(m)的时闻。每一次除边，都要重新计算一次边介
数，所有整个算法的时间复杂度在最坏的情况是O(mn)。 5贪婪算法
贪婪算法与上面算法的共同之处在于都是以最大化Q函数值为目标，区别是最大化的途径不同。贪婪算法的过程为：(1)初始时将网络中的每1个顶点都视为1个社团，每个社团内只有1个顶点。(2)两两合并社团，并计算社团合并所产生的Q值的变化量：Q=e,+e。2a,a,=2(ea,a,选择使得Q值增加最大的合并方式进行。计算Q值变化时，只需考患存在连边的网络社团对。当网络中包含n条边时，这步算法的复杂度为 O(n)。网络社团合并后一定会对e矩阵产生影响,所以将合并的两个社团所对应的行和列相加，对ej进行更新。(3)重复步骤(2)的操作，不断对社团进行合并，一直到所有项点被赢聚到一个社团为止。上述的操作最多进行n一1次。这种方法将复杂网络中的社团用树状图的形式表现，使得Q函数值最大的社团划分方式就是网络的最优划
分结果。参考文献
[1 JWZachary. An information flowJournal of Anthropologica] Research.mode1 for conflict and fission in smallgroups.1977,33(4):452473.
[2JwwZachary. An information flow Journa1 of Anthropo logical1 Research.mode1 for conflict and fission in sma11 groups.1 977,33(4):452473
[3]汪小机.李翔.陈关荣.复杂网络理论及其应用[M].北京：清华大学出版社2006
[4]Girvan M,Newman M E J. Community structure in social andbiological networks[J]. Proc Nat1 Acad Sci USA,2002,99:7821 . 7826
[5JNewman M E]. Fast algorithm for detecting community strut. ture in networks[JJ.Proc Nat1 Acad Sc1,2001,99:7821.7826
145