复杂网络重叠社团挖掘算法

吕晓军

(华南师范大学计算机学院，广东 广州 510631)

0 引言

复杂网络一般指节点众多、连接关系复杂的网络，包括社会网络、电力网络、生物网络、新陈代谢网络等。根据学者的研究，复杂网络一般都具有小世界现象和幂律分布等统计特性，具体表现为网络中具有社团结构。所谓社团结构是指整个网络可以由若干个社团组成，社团之间的连接相对稀疏，社团内部的连接相对稠密。本文研究的内容就是要从复杂网络中检测出社团结构，从而更深刻地理解复杂网络的拓扑特性。

社团结构可以分为非重叠社团结构和重叠社团结构。非重叠社团结构是指社团之间互不重叠，每个节点有且仅属于一个社团。非重叠社团结构把每个节点严格地划分到某个社团中，而真实世界中这种硬划分并不能真正反映节点和社团的实际关系，如社会网络中的人属于多个集体、网络中的网页属于多个主题等。把这种一个节点可以属于多个社团的节点叫“骑墙节点”，具有这种“骑墙节点”的社团结构就叫做重叠社团结构。重叠社团结构更符合真实网络的社团组织规律，成为近几年社团发现研究的新热点。

以前，人们往往从节点的角度出发来进行社团挖掘算法的研究，但是重叠社团结构中的“骑墙节点”可能会同时属于多个社团，所以从节点角度划分重叠社团结构效果不是很理想。最近，Evans等［5］和Ahn等［1］分别发表了以边为研究对象来划分社团，因为节点可能会属于多个社团，但边表示节点之间的关系，一般只能对应一种确定关系。这样以边为对象来划分社团能更真实地反映节点在复杂网络中的角色。但是Ahn等［1］提出的算法在小规模非高度重叠的网络，如Karate Club网络、Email网络中的划分效果并不是很好，因此本文提出一种改进算法，实验结果表明这种算法在小规模非高度重叠的网络中也能取得与实际基本相符的社团划分结果。

1 基本概念及相关算法

给定一个无向无权的网络G=(V，E)，V表示网络中节点的集合，E表示边的集合。本文的目的就是从给定网络中挖掘出以节点为元素的重叠社团结构。

由于是对Ahn等［1］提出的算法进行改进，所以先介绍Ahn等在文献［1］中提到的两个重要定义，然后介绍重叠社团中常用评价标准扩展模块度的概念［2］。

1.1 边相似度

对于给定网络G中有公共节点k的相邻边eik和ejk，节点i和它的邻居节点记为n+(i);同理，节点j和它的邻居节点记为n+(j)。

1.2 划分密度

划分密度分量:对应每个社团的划分密度。

(假定nc=2时，Dc=0)

对于一个给定网络G有M条边，N个节点，P={P1，P2，…，Pc}对应网络的一个社团结构划分，mc表示其中任意一个社团Pc的边数，nc表示社团Pc中有边相连的节点个数。

划分密度总量:对应整个社团结构的划分密度。

1.3 扩展模块度

为了描述重叠社团结构的模块度，引入扩展模块度定义［2］。

其中:C表示一个社团结构划分，c表示某个社团，V表示网络中节点集合;Auv是邻接矩阵，当u，v有边相连时为1，否则为 0;ku，kv表示节点 u，v 的度;kcu表示节点u在社团c中的内度;m表示网络中边的总数。

1.4 Ahn 算法思路

(1)计算所有相邻边对的相似度S;

(2)按从大到小的顺序对S排序;

(3)按S从大到小的顺序合并边对，如果S相同，则同时合并边对，直到合并成为一棵层次聚类树;

(4)根据划分密度总量D达到最大的标准来断开得到的层次聚类树，从而得到基于边划分的重叠社团结构。

2 改进算法

2.1 算法思想

原算法是先合并成树，然后根据划分密度D达到最大断开。本文的思路是同时考虑边相似度从大到小的顺序和扩展模块度Q0是否增大两个标准，最后得到一个边的森林结构，然后还原成节点，从而得到点聚类的重叠社团结构。

具体算法步骤如下:

(1)先计算所有相邻边对的相似度S;

(2)按从大到小的顺序对S排序;

(3)按S从大到小的顺序合并边对，并同时计算Q0是否增加，如果增加或不变，则正式合并，否则放弃合并。直到一轮扫描完毕;

(4)再次考虑还没合并的边对，按S的相似度从大到小再次合并，并考虑Q0是否增加或不变;

(5)重复步骤(4)，直到所有边都用到或Q0开始减小。

2.2 算法主程序

3 实验结果及分析

本文算法是对文献［1］中算法的改进，故下面以5个经典的网络(Karate Club网络、Dolphins网络、A-merican-College-Football网络、Email网络、Jazz-musician网络)就这两个算法的社团划分结果做对比。

表1 实验结果对比

从表1实验结果可以看出，Ahn等［1］提出的边聚类算法对于小规模非高度重叠网络的效果可以说很差，而本文提出的改进算法对于小规模非高度重叠网络能取得较理想的划分结果，与实际情况基本相符。但是本文算法所取得的结果中重叠节点过多，是以后在进一步研究中需要解决的问题。

由于篇幅所限，本文仅列出空手道俱乐部(Karate Club)用改进算法得出的社团划分结果:

cluster 1(20):9，10，14，15，16，19，20，21，23，24，25，26，27，28，29，30，31，32，33，34，

cluster 2(6):1，5，6，7，11，17，

cluster 3(18):1，2，3，4，8，9，10，12，13，14，18，20，22，28，29，31，32，33，

4 结束语

尽管复杂网络的社团检测问题得到了大量的研究，但还存在一些尚未解决的基本问题，如社团概念虽然大量使用，但却缺少严格的数学定义;大多数社团检测算法虽然性能优越，但所需计算量却很大，尤其是重叠社团检测算法的研究，其与实际社团结构更相符，但也更复杂，尚存许多问题亟待解决。这说明复杂网络中社团检测的研究还需要付出大量的努力。

［1］Ahn Y Y，Bagrow J P，Lehmann S.Link communities reveal multiscale complexity in networks［J］.Nature，2010，466(7307):761-764.

［2］Chen D，Shang M，Lv Z，et al.Detecting overlapping communities of weighted networks via a local algorithm［J］.Physica A:Statistical Mechanics and its Applications，2010，389(19):4177-4187.

［3］骆志刚，丁凡，蒋晓舟，等.复杂网络社团发现算法研究新进展［J］.国防科技大学学报，2011，33(1):47-52.

［4］Shang M S，Chen D B，Zhou T.Detecting overlapping communities based on community cores in complex networks［J］.Chinese Physics Letters，2010，27(5):264-267.

［5］Evans T，Lambiotte R.Line graphs，link partitions，and overlapping communities［J］.Physical Review E，2009，80(1):16105.

［6］Girvan M，Newman M E J.Community structure in social and biological networks［J］.Proceedings of the National A-cademy of Sciences，2002，99(12):7821-7826.

［7］Newman M E J.Fast algorithm for detecting community structure in networks［J］.Phys.Rev.E，2004，69(6):066133.

［8］Newman M E J.Modularity and community structure in networks［J］.Proceedings of the National Academy of Sciences，2006，103(23):8577-8582.

［9］Palla G，Derenyi I，Farkas I，et al.Uncovering the overlapping community structure of complex networks in nature and society［J］.Nature，2005，435(7043):814-818.

［10］Lancichinetti A，Fortunato S，Kertesz J.Detecting the overlapping and hierarchical community structure in complex networks［J］.New Journal of Physics，2009，11(3):033015.

［11］Zarei M，Izadi D，Samani K A.Detecting overlapping community structure of networks based on vertex-vertex correlations［J］.Journal of Statistical Mechanics:Theory and Experiment，2009:P11013.

［12］Ding F，Luo Z，Shi J，et al.Overlapping community detection by kernel-based fuzzy affinity propagation［C］//Proceedings of the 2nd International Workshop on Intelligent Systems and Applications(ISA’2010).Wuhan，China，2010:1-4.

［13］Zhang S，Wang R S，Zhang X S.Identification of overlapping community structure in complex networks using fuzzy c-means clustering［J］.Physica A:Statistical Mechanics and its Applications，2007，374(1):483-490.

［14］Newman M E，Leicht E A.Mixture models and exploratory analysis in networks［J］.Proceedings of the National Academy of Sciences，2007，104(23):9564-9569.