经典的复杂网络社团划分算法研究与分析

庄城山

安徽工业职业技术学院信息工程系，安徽铜陵，244000



经典的复杂网络社团划分算法研究与分析

庄城山

安徽工业职业技术学院信息工程系，安徽铜陵，244000

以其中最具代表性的三种经典算法——GN算法、快速Newman算法、CNM算法为代表，研究了算法的设计思想、执行流程。通过横向对比，对三种算法的优缺点进行分析比较，明确了三种经典算法的各自适用情况和范围：GN算法精度较高，但时间复杂度也较高，适用于对结果要求比较精确的节点数较少的社团；Newman快速算法在时间复杂度上较GN算法占优势，但精确度略低于GN算法；CNM算法同Newman快速算法时间复杂度相同，适用于加权的复杂网络。最后以Zachary空手道俱乐部网络和上证50部分股票构建的股票网络为例进行了实证分析，得到了较为准确的社团划分结果。

复杂网络；社团划分；GN算法

1 复杂网络社团划分问题概述

20世纪末，两篇开创性的论文：一是在《Nature》杂志上发表的《小世界网络的群体动力行为》[1]，另一是在《Science》杂志上发表的《随机网络中标度的涌现》[2]，标志着复杂网络研究新纪元的到来。研究表明，社团结构是复杂网络的一种重要属性。社团内部的节点具有较强联系，而社团间节点之间联系则相对较少。社团划分技术是近年来复杂网络研究的重要方向之一，在分析研究复杂网络的拓扑结构、信息传递模式、节点重要性评估以及行为预测方面都具有重要的理论意义。

目前，较为成熟的社团划分算法通常有两大类：一类是计算机科学中的图形分割算法(Graph partitioning)，另一类是社会学中的分级聚类算法(Hierarchical Clustering)。图形分割算法主要包括Kernignan-Lin算法、谱平分法、派系过滤法，分级聚类算法又可以分为分裂算法和凝聚算法两类[3]。

对算法性能和有效性的分析研究离不开特定的数据对象，也称数据集。对同一数据集应用于不同的社团划分算法并分析实验结果，能够客观反映出算法自身的特点，以便进行算法之间社团划分精度和效率的横向比较研究。

2 实验数据集

2.1 测试数据1：Zachary空手道俱乐部网络

在社团划分研究中，最常用的一个经典网络数据集就是“Zachary空手道俱乐部网络”。该网络是社会学家Zachary于20世纪70年代初期，通过观察美国一所大学空手道俱乐部中 34名俱乐部成员间的社会关系而形成的。网络中每个节点表示俱乐部中的一位成员，联系节点间的边表示俱乐部成员之间的某种关系，如成员在俱乐部之外的地方有较多的社会活动[5]。

图1 Zachary空手道俱乐部成员关系网络

Zachary在调查过程中发现，图1中的34号节点俱乐部主管John与图1中1号节点俱乐部教练Hi因为收费问题发生争议，最终导致该俱乐部分裂成两个小俱乐部。因为两个俱乐部原来的渊源，分裂后的两个小俱乐部中部分成员之间仍然存在一些联系[5]。

2.2 测试数据2：“CSMAR数据库”查询股票数据

“国泰安数据服务中心”(CSMAR Solution)是由深圳市国泰安信息技术有限公司自主研发的网站系统。国泰安信息技术有限公司是国家科技部重点支持的高科技龙头企业，致力于为教育、科研和证券机构提供一流的中国财经数据库、金融工程等高端金融分析工具以及金融专业培训。

使用中国股票市场交易数据库，大大节约了研究过程中处理数据的宝贵时间，提高了研究效率。中国股票市场交易数据库是基础库，已广泛地应用于各种实证研究当中。

3 经典的GN社团划分算法

3.1 GN社团划分算法

3.1.1 GN社团划分算法概述

GN算法是Girvan和Newman在2002年提出的一种基于边的介数的社团划分算法。该算法是通过删除图中某些边，找出网络中最自然的分割[4]。

该算法的设计思想是：依据社团的定义，联系社团之间的边相对较少，这些较少的连接，也就是边，是社团之间的“瓶颈”，是联系不同社团的必经之路。因此，这些边比社团内部的流量高。将这样一些流量较高的边从网络中移除时，网络自然会被分割为若干社团。

Girvan和Newman用边的介数来定义这种流量。这是Freeman节点的介数在边上的推广。图1中一条边的介数定义是：网络中任何结点对之间的最短路径中含有这条边的最短路径的个数。Girvan和Newman提出的GN算法就是反复计算图中介数最高的边，并从网络中移除这条边，不断重复这个过程。当两条或多条边的介数同时具有最高值时，就随机地选择一条边将其移除。在一个具有n个节点、m条边的网络中计算各条边的介数的算法时间复杂度为O(mn)[6]。

3.1.2 GN社团划分算法优缺点与适用情况分析

优点：由于GN算法从整个网络的全局出发进行社团划分，是每次通过移除介数最大的边，避免了以往算法的很多缺点。因此，该算法精确度非常高。某种程度上GN算法已成为对后续社团划分算法评价的标准，被广泛地应用到社团划分及算法分析等诸多方面(图2)。

缺点：(1)该算法无法事先判断网络最终应该被划分为多少个社团。(2)该算法通过不断地计算网络中各条边的介数，并从中找出介数最大的边。当网络中的一条边被删除后，一般要重新计算网络每条边的介数。因此，该算法的时间复杂度较高，最差的时间复杂度为O(m2n)(m为边数，n为节点数)。因效率较低，该算法只适合节点数较少的网络。如果网络节点数较大时，则该算法运算耗时较长。

算法适用：GN社团划分算法比较实用于节点数较少，对社团划分结果要求较为精准的网络。

图2 GN算法对网球俱乐部Zachary数据集的划分

3.2 Newman快速社团划分算法3.2.1 Newman快速社团划分算法概述

根据去边还是加边的判断标准，算法执行过程中不断去边的算法为分裂算法，反之则是凝聚算法。传统的GN算法属于分裂算法，而Newman快速算法属于凝聚算法。GN算法虽然有较高的精度，但时间复杂度也较高，只适用于中小规模的网络。为分析大规模复杂网络，以凝聚思想为核心，Newman于2004年创造性地提出了一种新的高效的社团划分算法，称为Newman快速社团划分算法[7]。

该算法采用基于婪算法的思想，将n个节点独立为n个社团。首先通过计算得出各节点对之间的相似性，从相似性最高的节点对开始，将其添加到n个节点、m条边的空网络中。以社团模块性增加或者减小为目标不断合并社团，从而得到规模最大的网络社团，获得社团划分的结果。算法的执行流程也可以用树状图来表示。这几个联通子图也就对应着一种社团结构的划分。

3.2.2 对经典网球俱乐部Zachary数据集划分的结果与分析

图3 Newman算法在Zachary网络的划分层次树

利用Newman快速算法对Zachary网络进行社团划分，当模块度系数Q取得最大值(0.381)时，原始网络被划分为17个大小近似的小社团。由图3可知，只有节点V10划分错误。而在GN算法的分析中，V3也未被正确划分。因此，该算法在精确度上与GN算法大体相当。

3.2.3 Newman快速算法优缺点与适用情况分析

优点：对于大规模网络，可以视为稀疏网络，其算法时间复杂度可以简化为O(N2),因此，对于大规模网络的分析，该算法具有优良的性能。

缺点：该算法同GN算法相比，划分的准确度比GN算法略低，如Zarchary网络中V10节点被划分到了错误的社团中。

适用：该算法在时间复杂度上具有明显的优势，可适用于几百万个节点的复杂网络。因此，该算法适用于节点数量百万级，而且不要求划分结果100%准确的复杂系统。

3.3 CNM加权网络社团划分算法

3.3.1 CNM算法概述

2004年，Clauset、Newman和Moore三人在Newman快速算法基础上，联名提出了一种全新的贪婪算法，称为CNM算法[5]。Newman快速算法和CNM算法的相同之处是两者都用到了增量矩阵ΔQ，然后通过对它的元素进行更新来得到一种规模性更大的社团结构。在算法执行过程中，当两个不相连的社团被合并时，社团的模块度不会增加。CNM算法只存储那些相邻社团及合并后模块度的增加值，达到了节约存储空间的目的。该算法的一个突出优点是时间复杂度为O(Nlog2N),已经十分接近线性。

即使对同一种算法采用不同的数据结构，算法的时间复杂度也会差别很大。CNM算法采用数据结构中的“堆”进行计算。

3.3.2 实验数据

3.3.2.1 数据来源和构造方法

输入数据：

50 47

2 9 0.077 8

2 38 0.102 0

2 42 0.060 0

…………

48 39 0.047 4

49 11 0.082 1

49 32 0.061 7

50 24 0.062 8

(1)数据的构造方法：使用的数据由上海上证50收盘价,通过处理建立的无标度网络。

(2)数据建立的方法：日对数收益率Si(t)可以用以下方法求得。

假设某支股票i(i=1,2,…,N)，该股票在第t个交易日的收盘价格为Yi(t)，则可以用公式Si(t)=lnYi(t)-lnYi(t-1)表示这只股票的日对数收益率。

(3)求相关系数rij。可用rij表示两只股票(股票i和股票j)的相关系数，股票的同步时间进化可以用相关系数表示。相关系数rij定义如下：

(1)

(4)求上证50股票价格相关性无标度加权网络：相关性较小的股票不是本文主要研究的对象，本文关注的是股票之间的强影响关系。根据相关性系数正态分布的规律，设定关系阈值为0.4，并利用相关性系数进行相关性连接。以股票为节点，相关性系数为加权边，当rij≥0.4时，节点i和j连边。当|rij|≥0.4时，节点i和j不连边，从而建立起上证50的股票价格相关性无标度加权网络模型[8]。

3.3.2.2 输出结果

41->49ΔQ=0.012 961

8->26ΔQ=0.012 485

4->50ΔQ=0.012 345

14->49ΔQ=0.011 506

26->49ΔQ=0.010 974

6->49ΔQ=0.010 582

社团1中的节点有：48,44,18,39,13,5。

社团2中的节点有：49,11,34,47,27,35,32,1,23,45,7,38,2,9,42,16,40,313,20,30,43,33,46,37,36,17,29,28,21,22,15,19,41,14,26,8,6。

社团3中的节点有：50,24,10,25,12,4。

其中节点数较多的社团中的节点大多数为金融业方面的股票，而节点数较少的社团中的节点多为农、林、牧、渔及文化产业方面的股票。因此，可以得出，保持好中心位置社团就显得十分重要。这样，便可避免它给其他社团带来的风险和不良影响，从容地对国民经济进行宏观调控。该算法不仅揭示了哪些股票所在的社团更具影响力，而且显示了不同节点在社团中的影响力。

3.3.4 算法性能分析

优点：CNM算法同Newman快速算法一样具有极高的运行效率。因为它是通过对Newman快速算法中模块度进行加权，从而选出在加权网络中最相似的两个节点合并为一个社团。因为采用堆结构更新网络的模块度，该算法的时间复杂度只有O(Nlog2N),这样的时间复杂度已经十分接近线性。

4 结束语

社团划分技术是当前复杂网络研究中的重要课题之一，它在各个领域的应用有重要的理论价值和现实意义。三种经典社团划分算法中，GN算法精度较高，但时间复杂度也较高，适用于对结果要求比较精确的节点数较少的社团。Newman快速算法在时间复杂度上较GN算法占优势，但精确度略低于GN算法。CNM算法同Newman快速算法时间复杂度相同，适用于加权的复杂网络。

因为对社团概念本身还缺乏严格的数学定义，各种社团划分算法还缺乏统一严格的衡量标准。多数算法虽然具有较高的社团识别精度，但执行效率往往不高。进一步提高社团识别精度和较高的执行效率是以后社团划分算法的一个重要研究方向。

[1]Watts DJ,Strogatz SH.Collective dynamics of small-world networks[J].Nature，1998，393(4):440-442

[2]Bráabasi A L,Albert R.Emergence of scaling in random networks[J]. Science，1999，286(15):509-512

[3]郭世泽，陆哲明.复杂网络基础理论[M].北京：科学出版社，2012:265-289

[4]丁连红，时鹏.网络社区发现[M].北京：化学工业出版社，2008:18-33

[5]汪小帆，李翔，陈关荣.网络科学导论[M].北京：高等教育出版社，2013:119-153

[6]薄辉.社区发现技术的研究与实现[D].北京：北京交通大学计算机与信息技术学院，2009:13-25

[7]钟芬芬.复杂网络社区发现算法研究[D].西安：西安电子科技大学计算机学院，2012:5-17

[8]王浩，李国欢，姚洪亮，等.基于影响力计算模型的股票网络社团划分算法[J].计算机研究与发展，2014，51(10):2137-2147

[9]罗明伟，姚洪亮，李俊照，等.一种基于节点相异度的社团层次划分算法[J].计算机工程，2014，40(1):275-279

(责任编辑：汪材印)

10.3969/j.issn.1673-2006.2015.06.024

2015-03-20

安徽省教育厅质量工程项目“《网络互联技术》精品资源共享课程”(2013gxk159)。

庄城山(1975-)，江苏南京人，硕士，高级工程师，主要研究方向：计算机网络与虚拟化技术。

O157.5

A

1673-2006(2015)06-0090-04