基于Peer pressure算法的社区发现方法

摘要：社区有助于揭示复杂网络结构和个体间的关系。研究人员从不同视角提出很多社区发现方法，用来识别团内紧密、团间稀疏的网络结构。该文将Peer pressure 算法应用于社区发现的研究当中，介绍了Peer pressure 算法的步骤和社区发现的过程，最后进行了聚类模型的演示。

关键词：Peer pressure算法；社区发现；网络图

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2014）22-5301-02

在现实世界中，多种系统都通过网络结构的形式展现出来，如社会系统中的人际关系网、电话网、蛋白质交互网、文献引用网络等。这些网络具有很高的复杂性又被称为复杂网络（Complex Network） 。复杂网络已经在多个领域广泛应用，是重要的多学科交叉研究领域之一。复杂网络以节点抽象为实体，边抽象为实体间各种联系。社区结构是复杂网络的一个特例，其特性已经引起广泛的关注。其网络结构由若干个社区组成，各个社区之间具有明显的联系稀疏度，相同社区联系紧密而不同社区联系相对稀疏。社区发现的研究对于深入了解网络结构与分析网络特征具有有重要意义。

在过去几年中，已经产生了大量的社区发现算法。如Kernighan-Lin 算法极小化簇间连接数目与簇内连接数目之差，GN 算法的规则则是簇间连接的边介数大于簇内连接的边介数。

但以这上些方法均需要预先估计社区数目，进行参数的设定，如K（社区个数）等。该文提出一种基于Peer pressure算法的社区结构发现的聚类方法。该算法不需要任何的参数设定。

1 基于Peer pressure的社区发现

由于社区结构一般都表示成复杂网络图，故对社区结构聚类就是对一个网络图进行聚类。图聚类是图结构分类的无监督学习过程，简单地说，对图进行聚类就是要把图中相对连接紧密的结点及其相关的边分组形成一个子图，子图内各结点具有较高的连接度，而子图之间各结点的连接度则相对较低。

1.1 Peer pressure 聚类

Peer pressure聚类利用一个给定的事实：于一个近似的图的任何一个合适的聚类，顶点的聚类任务和它主要的相邻顶点聚类是相似的。如图1所示，除了顶点4以外，所有的顶点都在合适的聚类中。

如果图1中每个顶点的入度边被验证是这个图起源的聚类，那么这个聚类能被认为是次优的。除了顶点4外，在各自类别中所有的顶点都有最大的入度边。另外，如果顶点4调整到红色聚类里面，那么这个聚类可以被看成是最优的。每个顶点都有从自身所在聚类中的主要入度边。如图2所示。

传统上，peer pressure聚类是通过图的近似迭代产生。通过给定一个近似聚类， 在这个聚类中，每个顶点对它所有的邻接点进行第一次投票。统计这些投票，通过他们获得的最多的投票来移动顶点，从而产生一个新的近似聚类。通过这样的不断迭代从确定每个顶点所在的类，通常是连续的产生两个相同的近似聚类。

如下所示算法表示了pressure clustering 的迭代定义。同样的，这个算法也能用循环表示通过保存当前的和前一次近似聚类，如果相等则跳出循环。

1.2 社区发现建模

基于Peer pressure 算法的社区发现模型从网络图出发，使用引文关系作为子图分割的依据。Peer pressure 算法的思想如下：

1） 文章引用图抽象为邻接矩阵V输入matlab中，并初始化向量C为一到顶点个数即n的向量。

2） 计算出每个顶点对其邻接顶点出度所占比例，记为T矩阵。

3） 求出每个顶点中对其出度贡献最大的顶点，并赋值为当前顶点，改变后的近似聚类记为C1。

4） 重复2、3步，看C1是否发生变化。不变则迭代结束，输出C1，否则继续进行迭代。

2 试验与分析

为了演示该社区发现模型，从新浪微博中抓取、筛选和过滤若干用户，这些用户分别关注了以下四个种类的话题：体育类、财经类、军事类、饮食类，根据他们的关注关系构建了图3 所示的复杂图，尝试通过Peer pressure 算法进行聚类。

如图4所示，该算法经过三次迭代算出计算结果，最终的结果为节点1、节点3、节点5、节点7聚为一类，节点2、节点4、节点6、节点8聚为一类，节点10、节点12、节点16聚为一类，节点9、节点14聚为一类，节点11、节点13、节点15聚为一类，一共聚出5类。

真实的社区结构是节点9、节点11、节点13、节点14和节点15在一个社区，其余的社区结构都分析对了。由此可见该算法基本上可以正确地划分社区网络。

这种基于过Peer pressure 算法的社区发现方法，不需要任何参数的设置，可以自动识别社区数目。实验结果表明，该算法能够比较准确的识别网络中的社区，具有一定的研究及使用价值。

参考文献：

[1] 杨楠.Web社区发现技术综述[J].计算机研究与发展，2005（4）.

[2] 杨柳.基于无偏Q值反馈的社区划分算法[J].东南大学学报：自然科学版，2011（1）.

[3] 胡健，邓志娟.一种新型简单图社区结构发现算法[J].计算机工程与应用，2009（5）.

[4] 谢锋.基于GN算法的文献聚类研究[J].信息科技，2013（1）.