算法复杂网络社区结构发现算法概述设计

摘要：分析了一些经典的复杂网络社区结构的发现算法，希望对社区发现问题的进一步研究及若干问题的早日解决起到一定的作业。
关键词：复杂网络 社区结构
1007-9416（2013）03-0145-01
1 引言
复杂网络是现实世界中复杂系统的一种抽象表现形式，网络中的节点是复杂系统中的个体，节点之间的边则是系统中个体之间按照某种规则而自然形成或人为构造的一种关系。网络节点被划分成若干组，使得组内节点之间的连接比较稠密，而不同组节点之间的连接则比较稀少，这样的划分结果被定义为复杂网络的社区结构。通过对复杂网络社区结构的研究，可以将复杂网络社区结构的研究理论成果应用到具体问题当中去，如可以通过社区结构发现资源分布、病毒的传播等。

2 基于Laplace图特征值的谱二分法[3]

令G是一个具有n个节点的无向图，G的Laplace矩阵L是一个n×n的对称矩阵，它的对角线元素Lij是节点i的度，表示节点i和节点j的连接情况，当i和j之间有边相连时，则Lij=-1，否则Lij=0。显然，L每一行的和以及每一列的和均为0，因而，向量l=（1，1，1，1）是L的相应于特征值0的特征向量。可以知道，此时L存在g个与特征值0对应的特征向量v（k），k=l，2，L，g，其中，v（k）的对应于分支Gk的分量为1，而其余分量为0。
因为对称矩阵的任意2个特征值所对应的特征向量相互正交，所以Laplace矩阵L的任意对应于非零特征值的特征向量均正交于向量L=（1，1，1，1），以此所有非零特征值的特征向量必须具有正分量和负分量。如果2个子图间连接很少，则将存在一个特征向量，它的特征值近似于0；它的特征向量的正分量对应一个子图，负分量对应另一个子图。
所以我们可以通过观察第二最小的特征值所对应的特征向量，依据特征值元素的正负将一个网络分解成2个社区，这就是谱二分法。

3 WH算法

在明确知道社团数目的情况下，Wu和Huberman提出了基于电阻网络电压谱的快速谱分割法。利用此算法不仅可以求出复杂网络的社团结构，还可以在不考虑整个复杂网络扩大社团结构的情况下，寻找一个已知节点所在的整个社团。
令图G=（V，E）可以分为两个社团G1和G2，且已知节点M和N分别属于这两个社团。令节点M为源节点，电压值为1，节点N为终节点，电压值为0。此时，网络中的每条边都视为一个阻值为l的电阻。复杂网络就可以看成一个电阻网络，可以利用基尔霍夫定理求各个几点的电压值。然后，选取一个电压阈值V（0V，认为它属于源节点M所在的社团，反之则为终结点N所在的社团。可以利用谱线图来记录电压值：在0～l的范围内，将电压值从大到小进行排列，然后用不同位置的谱线图来记录电压值。然后选取某个阈值，认为该阈值左边的线相应的节点属于一个社团，而右边的那些节点就属于另一个社团。

4 GN算法

GN算法[4]的思想是不断从网络中移除介数最大的边，边的介数是指通过该边的最短路径的数目。因为同一社区内的节点对介数较小，而不同社区的节点对介数较大，为此可以比较好的划分社区。
设网络矩阵中对角线上各元素之和为。该矩阵给出了网络中连接某一个社区内部各节点的边在所有边的数目中所占比例，定义每行（或者列）中各元素之和为，它表示与第i个社区中的节点相连的边在所有边中所占的比例，用下式来定义模块性的衡量标准：。上式的意义是：矩阵网络中连接两个同种类型的节点的边的比例减去在同样的社区结构下任意连接这两个节点的边的比例的期望值。如果社团内部边的比例不大于任意连接时的期望值，则有Q=0。Q的上限为Q=1，而Q越接近这个值，则说明社团结构越明显。
GN算法中，如果计算关于有m个节点和n条边的网络的所有边的介数则需O（mn）的时间。每一次删除边，都要重新计算一次边介数，所有整个算法的时间复杂度在最坏的情况是O（m2n）。

5 贪婪算法

贪婪算法与上面算法的共同之处在于都是以最大化Q函数值为目标，区别是最大化的途径不同。贪婪算法[5]的过程为：（1）初始时将网络中的每1个顶点都视为1个社团，每个社团内只有1个顶点。（2）两两合并社团，并计算社团合并所产生的Q值的变化量：Δ选择使得Q值增加最大的合并方式进行。计算Q值变化时，只需考虑存在连边的网络社团对。当网络中包含n条边时，这步算法的复杂度为O（n）。网络社团合并后一定会对e矩阵产生影响，所以将合并的两个社团所对应的行

摘自：硕士论文格式www.udooo.com

和列相加，对eij进行更新。（3）重复步骤（2）的操作，不断对社团进行合并，一直到所有顶点被凝聚到一个社团为止。上述的操作最多进行n-1次。这种方法将复杂网络中的社团用树状图的形式表现，使得Q函数值最大的社团划分方式就是网络的最优划分结果。
参考文献
WWZachary. An information flowJournal of Anthropological Research.model for conflict and fission in allgroups.1977，33（4）：452-473.
WWZachary. An information flow Journal of Anthropological Research.model for conflict and fission in all groups.1977，33（4）：452-473.
[3]汪小帆，李翔，陈关荣.复杂网络理论及其应用[M].北京：清华大学出版社，2006.
[4]Girvan M，Newman M E J.Community structure in social andbiological networks[J].Proc Natl Acad Sci USA，2002，99：782

1.7826.

[5]Newman M E].Fast algorithm for detecting community strut.ture in networks[J].Proc Natl Acad Sci，2001，99：7821.7826.