《三种经典复杂网络社区结构划分算法研究_GN算法》由会员分享，可在线阅读，更多相关《三种经典复杂网络社区结构划分算法研究_GN算法（4页珍藏版）》请在金锄头文库上搜索。
1、论文导读:：复杂网络是复杂系统的高度抽象。即社区结构特性3。算法是一种试探优化法4。算法。关键词：复杂网络，社区结构，Laplace 图谱，Kernighan-Lin 算法，GN 算法1引言现实生活中存在着各种各样的网络系统，如人际关系网、合作网、交通运输网、计算机网等。网络模型是描述这些复杂系统的最有效模型。通过对现实系统网络模型的研究，人们发现许多现实系统的网络模型是介于完全规则和完全随机之间的。由于这种网络是真实复杂系统的拓扑抽象因此它被称为复杂网络。复杂网络是复杂系统的高度抽象，除具备小世界1、无标度2等重要特性外，还拥有另外一个重要特征，即社区结构特性3。也就是说，整个网络是由若干个
2、“群（group） ”或“团（cluster） ”构成的。每个群内部的节点之间的连接相对非常紧密，但是各个群之间的连接相对来说却比较稀疏。如图1所示。图中的网络包含三个社团，分别对应图中三个圆圈包围的部分。在这些社团内部，节点之间的联系非常紧密，而社团之间的联系就稀疏的多。在大型复杂网络中进行社区搜寻或发现社区，具有重要的实用价值。如，社会网络中的社区代表根据兴趣或背景而形成的真实的社会团体；引文网络中的社区代表针对同一主题的相关论文；万维网中的社区就是讨论相关主题的若干网站而生物化学网络或者电子电路网络中的社区则可能是某一类功能单元。发现这些网络中的社区有助于研究人员更加有效地理解和开发这些
3、网络。图1 一个小型的具有社团结构性质的网络网络社团结构的研究起源于社团学，已经有很长的历史期刊网。它与计算机科学中的图形分割和社会学中的分级聚类有着密切的关系。目前 GN 算法，关于复杂网络中的社区发现算法已有很多，这些方法的核心思想、执行效率、使用范围等方面差别较大。本文着重叙述了三种典型的复杂网络社区识别算法，Kernighan-Lin 算法、Laplace 图特征值的谱二分法和 GN 算法，并对此三种方法进行了适当的分析和比较。2典型的网络社区识别算法(1) Kernighan-Lin 算法Kernighan-Lin 算法是一种试探优化法4。它是一种利用贪婪算法将复杂网络划分为两个社团
4、的二分法。该算法引入增益值 P，并将 P 定义两个社团内部的边数减去连接两个社团之间的边数，然后再寻找使 P 值最大的划分方法。整个算法可描述如下：首先，将网络中的节点随机地划分为已知大小的两个社团。在此基础上，考虑所有可能的节点对，其中每个节点对的节点分别来自两个社团。对每个节点对，计算如果交换这两个节点可能得到的 P 的增益 P=P 交换后 -P 交换前 ，然后交换最大的 P 对应的节点对，同时记录交换以后的 P 值。规定每个节点只能交换一次。重复这个交换过程，直到某个社团内所有的节点都被交换一次为止。需要注意的是，在节点对交换的过程中，P 值并不一定是单调增加的。不过，即使某一步的交换会
5、使 P 值有所下降，仍然可能在其后的步骤中出现一个更大的 P 值。当交换完毕后，便找到上述交换过程中所记录的最大的 P 值。这时对应的社团结构就认为是该网络实际的社团结构。(2)基于 Laplace 图特征值的谱二分法该算法利用网络结构的 Laplace 矩阵中不为零的特征值所对应的特征向量和同一个社区内的节点对应的元素近似值相等的原理对网络社区进行划分。该算法过程如下：设图 G 是一个具有 n 个节点的无向图，G 的 Laplace 矩阵 L 是一个 nn 的对称矩阵。L 的对角线元素 Lii 是节点 i 的度，非对角线元素 Lij 表示节点 i 和节点 j 的连接关系，当节点i 和节点 j
6、 之间有边连接时,则 Lij = -1,否则为 Lij = 0。容易验证，L 的每一行的和以及每一列的和均为0，因而，向量 I=(1,1,l1)是 L 相应于特征值 0的特征向量。如果图 G 可以被分解成 g 个互不重叠、互不相连的子图 Gk，则其 Laplace 矩阵 L 就是一个分成 g 块的对角矩阵块，每个对角矩阵块就是相应的分支子图的 Laplace 矩阵。显然，此时 L 存在 g 个与特征值0 对应的特征向量 v(k)，k=1,2, ,gGN 算法，当节点 i 属于该社团时，v i(k)=1，否则 vi(k)=0。如果图 G 可以被分解成 g 个子图，但子图之间存在少量连接时，其相应
7、的 Laplace 矩阵 L 就不再是一个分成 g 块的对角阵。此时，对应0这个特征值就只有一个特征向量 I。但是，在0的附近还有 g-1个比零稍大的特征值，并且这 g-1个特征值相应的特征向量可以近似地看成上述特征向量 v(k)的线性组合。因此，从理论上来说，只要找到 Laplace 矩阵中比零稍大的那些特征值，并且对其特征向量进行线性组合，就可以近似的得到这些子图5。考虑一个例子，即将图 G 分割成2个子图。由于对称矩阵的任意两个 2个特征值所对应的特征向量相互正交，因此 Laplace 矩阵 L 的任意对应于非零特征值的特征向量均正交于向量 I=(1,1,l1)，从而所有非零特征值的特征
8、向量必须具有正分量和负分量。如果图G 可以分解为2个子图使得这2个子图之间仅存在很少的连接，则必存在一个特征向量，其特征值近似于0；该特征向量的正分量对应于一个子图，负分量对应于另一个子图。因此，可以通过观察最小非零特征值所对应的特征向量，根据特征值元素的正负将一个网络分解成2个社区，该方法称为谱二分法6-7期刊网。(3) GN 算法GN 算法是一种分裂方法8。其基本思想是不断的从网络中移除介数最大的边。边介数定义为网络中经过每条边的最短路径的数目。具体算法如下：计算网络中所有边的介数。移除介数最高的边。重新计算所有受影响的边的介数。重复步骤 ，直到每个节点就是一个退化社团为止。3三种算法的对
9、比分析从上述三种算法的过程来看，Laplace 图特征值谱二分法， Kernighan-Lin 算法和 GN算法计算简洁，都易于程序实现。Kernighan-Lin 算法的时间复杂度相对于与其他两种算法较小些，但该算法对网络中社区划分的准确度不高，适用于小规模网络社区划分。而Laplace 图特征值谱二分法和 GN 算法则适合于较大网络的社区划分。其中，Laplace 图特征值谱二分法仅适用于由2个社团组成的大网络结构 GN 算法，其时间复杂度比 GN 算法要大些。而 GN 算法在对网络社区进行划分时必须事先知道网络中存在的社团个数，如表1所示。总之，三种社区划分算法各有优缺点，在实际应用时，
10、可根据所要划分的网络特点，选择单独一种算法或综合多种算法对网络进行划分，以使划分结果更接近于网络社区实际状况。 表1 三种社区划分算法比较算法名称时间复杂度优点 缺点Kernighan-Lin 算法O(n2) 计算简单，易于划分准确度不高，且必须事先知道网络中社团规模大小，适用于小规模网络Laplace图特征值谱二分法O(n3)计算简单，易于程序实现仅适用于由2个社团组成的网络结构，时间复杂度较大GN 算法 O(m2n)考虑网络全局，划分社区准确度较高对网络社团结构缺少量的定义，事先知道社团个数注：n ,m 分别为网络中的节点数和边数3 结论复杂网络中社区的划分具有重要的使用价值。本文给出了三
11、种经典的复杂网络社团划分算法，较为详细地描述了各种算法的核心思想和基本过程，并对各算法进行了适当的分析和比较，为用户针对不同的复杂网络选择合适的社区划分算法提供了一定的借鉴作用。参考文献：1Watts D J,Strogatz S H. Collective dynamics of small-world networks. Nature, 1998,393(66844): 440-4422Barabasi A L,Albert R. Emergence of scaling in random networks. Science, 1999,286(5493):509-5123Newman
12、M E J,Girvan M. Finding and Evaluating Community Structure in NetworksJ. PhysicalReview E ,2004,69(2):26-113.4Kernighan BW,Lin S. A efficent heuristic procedure for partitioning graphs. Bell SystemTechnical Journal. 1970, 49:291-3075Newman M E J. Detecting Community Structure inNetworksJ. Eur.Phys.J
13、.B., 2004, 38(2):321-330.6Fildler M. Algebraic Connectivity of GraphsJ. CzechMath J. 1973, 23 (98): 2 98-305.7Phothen A, SimonH. Partitioning Sparse Matrices with Eigenvectors of GraphsJ. SIAM J. Matrix Anal. Appl., 1990, 11 (3):430-452.8Girvan M, Newman MEJ. Community structure in socialand biological networks. Proc. Natl. Acad. Sci. 2001, 99:7821-7826
