一种基于节点相似性的局部社团划分算法

王伟欣　刘发升

摘 要：提出一种基于节点相似性的社团挖掘算法，算法首先根据节点的相似度值找出最相似邻居节点，合并节点形成若干个社团，然后优化模块度函数进行社团的合并，当模块度值最大时算法终止。最后，通过Zachary网络和Dolphin网络进行实验仿真，验证了算法的可行性和精准性。

关键词：复杂网络；社团结构；节点相似性；模块度函数；聚类

中图分类号：TP301.6

现实世界中的诸多复杂系统可以抽象表示为复杂网络，如社会关系网络、生物网络、因特网等。研究发现这些网络具有共同的特征：网络内部存在社团结构，即网络是由若干“社团”构成，社团内部的节点之间连接稠密，社团之间的节点连接相对稀疏[1]。社团结构研究的科研价值和实用价值已经吸引了大量不同领域的研究工作者，并且其研究成果成功地应用在蛋白质功能检测、web社区挖掘、搜索引擎、恐怖组织识别等众多领域，社团结构已经成为信息时代网络研究的一个热点。

目前，社团划分方法主要分为两大类：图分割法和层次聚类法。图分割法的两个代表算法：Kernighan-Lin算法[2]是一种基于贪婪算法的原理通过优化增益函数从而将网络划分成两个大小已知社团的二分法；谱平分法[3，4]根据网络的Laplace矩阵的第二小特征值对网络进行平分。GN算法和FN算法是层次聚类法的两个代表算法。其中，GN算法[5]通过引入边介数的概念不断地对网络中的边进行删除来得到网络的层次结构；FN算法[6]通过不断合并节点的方式直接优化模块度值来获得网络的社团结构划分。CNM算法[7]通过使用堆和二叉树这两个新的数据结构进行节点信息的存储对FN算法进行改进，算法的计算效率提高，节省了节点的存储空间。文献[8]在CNM算法的基础上提出一种基于局部信息进行社团划分的算法。文献[9]根据节点类型提出一种社团划分算法。

本文提出一种局部社团划分的新算法。该算法在CNM的基础上，首先根据节点的相似性产生初始社团，即根据节点的相似度值找出最相似邻居节点，合并节点形成若干个小社团。然后采用CNM算法的思想根据模块度增量进行小社团之间的聚类，模块度取得最大值时算法终止。一方面，由于算法在形成初始社团的过程中只需要节点的局部信息，避免了全部节点和边信息的计算，加快了算法的计算速度；另一方面，社团合并时模块度增量的计算次数远远小于节点个数，与CNM算法相比，计算效率有很大的提高。

1 相关概念

一个无权无向的复杂网络可以用简单图G=（V，E）表示，其中V是网络的节点集，E是网络的边集。邻接矩阵 中的元素 表示网络中节点之间的连接关系，若节点 和 互相连接，则 ；若节点 和 互不连接，则 。

1.1 节点的相似度矩阵

假设网络中的一对节点 和 ， 是节点 的邻居集合， 是邻居集合中节点的数目，则 是节点 和 共同的邻居个数。节点的邻居节点越多，表明它作为其他节点的邻居节点的次数也就越多，为计算相应的节点之间的相似性贡献的力量就会越小。反之，如果一个节点仅有很少的几个邻居节点， 则为相应的节点对贡献的相似性的信息量就会越大。通过以上的分析，文中节点的相似度计算公式定义如下：

式中， 是节点 的度。度值越大的节点拥有的邻居节点数就会越多，式（1.1）中的分母正好消除了这种尺度效应，此时 。 表明节点 和 不相连。 有两种情况：一种是节点 和自身的相似度，即 ；另一种是 且 ，即节点 和 相连且两个节点均只能有一个邻居节点。

1.2 模块度函数

模块度函数是Newman和Girvan[10]在2004年提出的用来刻画社团结构强弱的参数，定义如下：

式中， 表示节点 所属的社团； 是节点 的度值； 是网络相应的邻接矩阵的元素，节点 ， 相连时 ，节点 ， 不相连时 ；节点 ， 在相同的社团时 ，节点 ， 在不同的社团时 ； 是网络中边的数目总和； 指随机网络中节点 ， 之间可能的边数。现实网络的模块度函数的值一般在0.3 ～0.7 之间。

2 算法实现

在复杂网络中，如果在两个节点的相连过程中，对某个节点进行相连的次数越多，说明这两个节点拥有共同的邻居节点数就较多，则认为这两个节点是相似的。两个节点的相似度是由他们的邻居节点决定的，而与图中其他节点无关。如果两个节点相似度足够大，它们应该被放到一起，这是基于相似网络的基本概念。

本文算法的基本思想：首先依据相似性函数计算节点之间的相似度，找出网络中每个节点的最近邻居节点，这里指在该节点的邻居节点中与该节点的相似度值最大的节点。然后把网络中的每个节点与其最近邻居节点一一合并，组成若干个局部社团。在节点合并的过程中应注意节点的归属，这里选取合并的节点中把含有最优相似性节点个数最多的节点作为社团的核心节点。节点合并之后形成若干个小社团，此时小社团形成了网络的初始社团。然后采用CNM算法的思想，把一个小社团全体看作一个节点，通过社团的合并进行模块度函数的优化，其中小社团是沿着模块度增量 升高的方向进行社团的整合。当模块度 的值最大时，终止算法。此时模块度 对应的划分即是待求解网络的最佳社团划分。

算法步骤如下：

步骤1 输入网络 ，找出网络中每个节点的邻居节点，根据相似性公式（1.1）计算每个节点与其邻居节点的相似度。

步骤2 从相似度矩阵中找出每个节点的最相似节点。节点 的最相似节点是指在节点 邻居节点中与该节点间的最大相似度值的节点。

步骤3 把具有相同的最相似节点的节点进行合并，并选取作为最相似节点次数最多的节点作为社团核心节点，并用核心节点表示该社团。

步骤4 重新构建网络。把每个初始社团看作是新的节点，对社团中的节点进行权值的合并，并更新邻接矩阵。

步骤5 根据式（2.1）计算模块度增量 。由于在该步骤时，每个节点对应的是一个社团，此时模块度的计算公式可表示如下：

步骤6 重复步骤5，直到模块度 不在增加为止，此时对应的社团结构就是待划分网络的最优社团结构。

3 实验结果及分析

为了测试本论文提出算法的可行性和准确性，针对两个经典的现实网络Zachary网络和Dolphins网络进行实验仿真。本文算法采用Matlab语言进行编译，实验结果证明该算法是可行的，并且准确性高，能够较好地完成网络社团的划分。

3.1 Zachary网络

Zachary网络是社会学家Zachary在1970至1972年间对其观察和研究的空手道俱乐部中成员的社会关系构建的一个社会网络，如图3.1所示。网络含有34个节点和78条边，它们分别代表俱乐部成员和成员之间的社会关系。在观察期间，俱乐部主管和校长对是否需要提高收费标准的问题意见不一致，俱乐部分成了两个小俱乐部，主管和校长分别是这两个小俱乐部的核心人物。在图3.1中，节点1表示俱乐部主管，节点34表示校长。Zachary网络是检验社团挖掘算法的三大基准网络之一，用来测试算法仅根据观察到的网络结构能否对网络做出准确的划分。

使用本文算法对Zachary网络进行分析，根据节点相似度进行节点聚类得到的初始社团如表3.1所示。从表中可以看出，经过节点聚类，网络中的节点被划分为8个小社团。

与CNM算法相比，本文算法由于先对节点进行了聚类，算法的迭代次数肯定会小于网络的节点数，考虑节点聚类时最糟糕的情况，即对于含有 节点的网络，网络中的每个节点只能够和一个节点相互成为最相似节点，则此时算法的迭代次数为 次，而CNM算法最多需要比网络的节点总数减少1的次数才能够完成网络社团的挖掘，此时迭代次数为 次。因此，该算法在时间上是由于CNM算法的。该算法Zachary网络划分结果如图4.2所示，可以看出，该算法把Zachary网络分成2个社团，与现实中的

结果相同，具有很高的准确性，此时网络的模块度 的值为0.381。

3.2 Dolphins网络

海豚关系网也是用于检验网络社团挖掘算法的一个常用的基准网络。Lusseau等人花费多年时间观察生活在新西兰的一个海豚群体，海豚群体中包含两个子群，其中较大的子群中包含42只海豚，而较小的子群中只有20只海豚。通过观察研究得出如图5.4所示的Dolphins网络图，网络中的每只海豚对应图中的一个节点，如果两个节点有边相连接，则表明节点对应的两只海豚之间有互动关系。Dolphins网络中共有62个节点、159条边。

4 结束语

本文提出一种基于节点相似性的局部划分的新算法，该算法是结合节点的局部信息和全局模块聚类的思想，在CNM算法的基础上改进的一种算法。算法充分利用了节点之间的关系——相似度，也采用了模块度函数作为社团凝聚时的判断标准，可以说既考虑了网络的局部结构，又考虑了网络的整体结构。从实验仿真分析，算法能够很好地完成网络的划分，具有较高的准确性和计算效率。

参考文献：

[1]Newman M E J. Detecting community structure in networks[J].The European Physical Journal B，2004，38（2）：321-330.

[2]Kernighan B W，Lin S.An efficient heuristic procedure for partitioning graphs[J].Bell System Technical Journal，1970，49（2）：291-307.

[3]Fiedler M.Algebraic connectivity of graphs[J]. Czechoslovak Mathematical Journal，1973，23（2）：298-305.

[4]Pothen A，Simon H，Liou K P.Partitioning sparse matrices with eigenvectors of graphs[J].SIAM J.Matrix Anal.Appl，1990，11：430.

[5]Girvan M，Newman M E J.Community structure in social and biological networks[J].Proc of the National Academy of Science，2002，99（12）：7821-7826.

[6]Newman M E J.Fast algorithm for detecting community structure in networks[J].Physical Review E，2004，69（6）：66-133.

[7]Clauset A，Newman M E J，Moore C.Finding community structure in very large networks[J].Physical Review E.2004，70：06611.

[8]任永功，孙宇奇，吕朕.一种基于局部信息的社区发现方法[J].计算机工程，2011，37（7）：12-23.

[9]史伟，赵政，薛桂香.基于节点类型的复杂网络模块探测算法[J].计算机应用，2008，28（10）：2590-2593.

[10]Newman M E J，Girvan M.Finding and evaluating community structure in networks[J].Physical Review E，2004，69：26-113.