网络中社团划分算法实现与对比研究∗

李新建 杨继红

（1.湖北中烟工业有限责任公司信息中心 武汉 430030）（2.中国人民大学附属中学朝阳学校 北京 100028）

1 引言

人类社会中人与人的熟知关系、计算机领域中的Internet 终端设备的互连、生物领域中分子的相互作用都可以用网络来抽象描述，网络中的节点对应系统中的个体，网络的边代表个体间的相互关系。这种抽象只保留了基本结构，过滤了复杂的背景信息，有助于对网络代表的系统内在共同特征和性质进行研究。研究发现这些网络并非随机网络［1］，它们的统计特性不同于传统的随机网络结构，是无尺度网络。网络中包含各种社团，社团是网络中内部比较致密，外部连接比较松散的子网络。网络中的社团结构是有现实意义的，例如：在人际关系网中，个体有相似爱好、职业的个体常具有社团结构特点［2～3］；在科学研究中，不同社团可代表不同的研究领域［4～5］；在Internet 中，新闻、音乐，论坛内容等可被划分为分别不同主题的社团［6～7］。合理有效地对网络进行社团划分有助于发现不同的主题分组，对了解整个网络的结构、功能和特点有重要的意义［8～9］。

一般认为，网络中社团结构是内部连接稠密而外部连接稀疏的子网络。“稠密”和“稀疏”是定性定义，在探索网络社团结构的过程中无法直接使用。因此，常用定量的强社团和弱社团定义。强社团的定义为［10～11］：子图v中任何一个顶点与v内部顶点连接的度大于其与v 外部顶点连接的度。弱社团的定义：子图v 中所有顶点与v 内部顶点的度之和大于v 中所有顶点与v 外部顶点连接的度之和。除此以外，还有派系［12］定义，是指由三个或三个以上顶点组成的全联通子图，即任何两点之间都直接相连。在此基础通过弱化连接条件可以进行拓展，形成n-派系。例如：2-派系意味着子图中任意两个顶点不必直接相连，但最多通过一个中介点就可以连通。3-派系是指子图中的任意两个顶点，最多通过两个中介点就能连通，以此类推，随着n 值增加，n-派系的要求越来越弱。这些定义允许社团间存在重叠：即单个顶点并非仅仅属于一个社团，还可以同时属于两个及两个以上的社团。本文关注完全相互独立的社团结构，因此采用较为常用的基于相对频数的社团结构定义。

在社团定义的基础上，在复杂网络中进行社团结构划分的方法大致可以分为3 类：层次聚类方法、搜索方法和其他方法。层次聚类方法又可以进一步分为凝聚过程和分裂过程，它们的主要区别在于是由底向上合并还是自顶向下分解。凝聚过程：即以顶点为基础，通过一定方法逐步凝聚，最终形成社团。主要步骤是：1）把网络中每个节点对象都看成一个单独的社团，网络中有多少节点就有多少社团；2）设定某种标准衡量社团与社团间的距离和相似度；3）逐步合并这些初始社团进而形成更大的社团，直至所有节点都聚集到一个社团中，或者满足某个终结条件停止。分裂过程采用的层次分解方法为自顶向下，与凝聚相反。搜索方法是建立逐步优化某个目标的探索过程，社团结构直接由最后的优化结果给出。代表性的方法有PageRank［13］和HIT［14］。不属于这两种方法的划为其他类，代表的方法有谱方法［15］。现有方法在复杂网络社团结构挖掘中取得一定的效果，但是在应用过程还是存在诸多问题：1）现在很多算法虽然有效，但是复杂度很高，限制了在大网络中进行社团结构划分的应用。2）己有方法大多需要设置一些特定的参数，这些参数需要大量的相关领域的经验，甚至需要专家提供指导。3）很多方法需要使用大型矩阵，需要大量计算或占用的大量存储空间。

因此本文讨论PCA、K-Means 和PSO 三种原理简单且实现高效的社团结构划分方法。

2 社团结构划分方法

本文讨论的PCA、K-Means 和PSO 三种划分方法均需要利用到Girvan 和Newman 定义的模块度［6］。模块度指网络中连接社团结构的内部顶点的边所占的比例与另外一个随机网络中连接社团结构内部顶点的边所占比例的期望值相减得到的差值。这个随机网络的构造方法是：保持每个顶点的社团属性不变，顶点间的边根据顶点的度随机连接。评判社团结构划分好坏的标准是看社团内部链接的稠密程度和随机连接网络的期望水平之间的关系。如果社团结构划分的好，则社团内部连接的稠密程度应该高于随机连接网络的期望水平。用Q函数定量描述社团划分的模块化水平：

其中Aij为网络中连接矩阵的元素，如果i，j两点有边相连，Aij=1，否则Aij=0。ci为顶点i所属的社团，若ci=cj则∂(ci，cj) =1，否则为零。m 为网络的边数，ki为顶点i 的度。如果社团内部顶点间的边没有随机连接得到的边多，则Q 为负值，如果Q 接近1时，表明相应的社团结构划分得很好。

2.1 PCA

PCA方法是一种从对象中提取主要信息，忽略相对次要信息的多元统计分析方法。利用该方法将一个网络划分为几个不同的社团，其本质是在最大化提取网络本身的主要信息。它是一种自底向上的方法。应用PCA 方法实现对网络多社团的划分可以通过对一次划分后所得到的社团不断重复进行二社团结构的划分来实现。在对一次划分所得的社团继续划分时，因为该社团始终是整个网络的一部分，这样就需要把它放到整个网络中去考虑，而不能把它作为一个独立的网络来处理。可以通过按网络的协方差矩阵中最大的特征值所对应的特征向量在各维取值的正负，将目标划分两个社团。划分结果的优劣可用模块度来衡量。在不断重复划分的过程中，模块度最大的社团结构划分状态一般认为是网络实际所具有的社区结构。

2.2 K-Means

假设网络G有n个节点和m条边。为了衡量节点传输信息的有效性，引入网络效率NE 的概念。假设网络中两个节点之间的信息总是沿着最短路径传播的，则节点i和j之间的信息传输效率εij为它们之间最短路径长度dij的倒数（如果节点i和j之间不存在路径，则最短路径长度为∞，εij=0）。

整个网络G 的信息有效率定义为各节点对的信息传输有效率的平均值NE［G］，即

边eij的信息中心度Ceij，定义为移除该边后整个网络的信息有效率减少的相对量，即

社团间的边的信息中心度比社团内部边的信息中心度大。节点i 与j 之间的边的信息中心度越小，它们的关联度就越大，属于同一个团的概率就越大，两个相邻节点的关联度：

非相邻节点间的关联度可用最短路径上所有节点对的关联度乘积表示。

应用K-Means方法进行社团划分的主要思想：以最小关联度原则选取新的聚类中心，以最大关联度原则进行模式归类，直到所有的节点都划分完为止，最后根据模块度来确定理想的社团数，即k值。

2.3 PSO

PSO 算法具有进化计算和群智能的特点，和其他进化算法相似，PSO 也是通过个体间的协作与竞争，实现复杂空间中最优解的搜索。PSO 先产生一个初始种群，种群中每个粒子都是优化问题的一个可行解，并由目标函数确定一个适应度值，种群中的粒子将追随当前的最优粒子运动，并经过不断进化得到最优解：在每一次进化中，粒子将追踪两个极值，一个是粒子本身迄今找到的最优解pbest，一个是整个种群迄今找到的最优解gbest。在划分问题中，PSO 中每个粒子包含一个适应值f，速度和位置更新定义为粒子的移动方向v。v 是由当前网络节点所属社团的情况决定。初始时，网络中的每个节点独立为一个社团。在算法迭代过程中，粒子的移动方向v 选择为向任意一个与该粒子所在节点有边，且不属于同一个社团的下一个节点移动。当粒子到达新节点后，计算新的适应值f'，若新适应值f'大于原有值f，则把新节点的社团标号标为原有节点的社团标号，否则保持不变。直到粒子运动前后模块Q不变或者达到进化迭代数。

3 实验

本文实验所用的硬件环境是：CPU Intel I5-4440（3.1GHz），内存为8GB，三种方法在Windows 7 下用C#实现。

为了比较三种方法，本文设计了两组实验。实验一采用的数据集是Zachary Club 数据集。20 世纪70 年代初，Wayne Zachary 观察了美国大学空手道俱乐部成员间的人际关系，并依据俱乐部成员间平时的交往状况建立了一个网络。这个网络包含34 个顶点，代表了俱乐部成员；包含了78 条边，代表他们之间的人际关系。由于突发的原因，俱乐部管理者与俱乐部主要教师之间针对是否提高收费这一问题产生了激烈的争论，并最终导致俱乐部分裂成两部分。该网络己知网络结构，便于比较得到划分方法的准确性。实验二采用计算机随机生成网络图，可以通过扩大社团成员规模，比较几种算法对不同规模网络的运行时间和正确率。

图1 Zachary Karate Club的社团图。圆形节点代表管理者社团，方形节点代表教师社团。

实验结果为PCA方法的准确率为97%，错分了第6号节点。图2是该网络协方差矩阵的最大特征值所对应的单位特征向量q 在各维上的数值。特征向量q 各维的数值大小一定程度反映了其所对应的网络中节点所属于社团的力度。

图2 Zachary Karate Club网络协方差矩阵最大特征值对应的单位向量在各维上的值。三角形节点代表管理者社团，圆形节点代表教师社团

K-Means 方法的结果随k 取值的不同，划分的社团个数与隶属情况也不一样。由图3 可知，当k取2 时，Q 值最大，表明划分为2 个社团时是最合适的。

图3 K-Means 对Zachary Karate Club网络中不同社团划分数对应的Q值

PSO 在多次计算中，还存在极少数进化搜索失败的可能，对Zachary Karate Club进行划分时，节点10被错误划分，其余的均正确。

图4 随机扩展网络规模，三种方法的时间消耗与正确率。圆形代表PSO，三角代表K-Means，十字代表PCA，实线是相应方法的时间消耗，虚线是正确率。

实验2 通过不断扩大社团成员规模，比较三种算法对不同规模网络的运行时间和正确率。从图4 可以看出，PCA、K-Means 和PSO 都保持着较低的运行时间、不低于0.8的较高的正确率。其中，PCA在运行时间上表现最为突出，K-Means 次之，基于PSO 消耗时间较长。但是，PSO 在时间上的消耗可以获得更好的正确率，在正确率方面，PSO 表现的最好，K-Means次之，PCA 最差。因此，三种方法应用场景侧重点不同有关。可根据不同社团规模进行选择。当社团规模较小，对正确率要求较高时候选择PSO；当社团规模较大的时候，选择PCA 会有优势。K-Means是折中的方法。

4 结语

本文介绍了网络中社团划分的方法，特别针对PCA、K-Means 和PSO 三种简洁实用的方法进行了讨论，并在Chary Karate Club 网络和人工变尺度网络上进行社团结构探测的性能比较，证明了三种方法划分有效性和性能特点。