第6卷第1期 智能系统学报 Vol.6 No.1 2011年2月 CAAI Transactions on Intelligent Systems Feb.2011 doi:10.3969/i.issn.1673-4785.2011.01.007 复杂网络社团的投影聚类划分 李伟，杨晓峰，张重阳，汤可宗，杨静宇 （南京理工大学计算机系，江苏南京210094) 摘要：社团结构划分对研究复杂网络有重要作用，由于该问题的复杂性，复杂网络中的社团划分问题成为近期的 一个研究热点.从经典数据分析的角度研究了复杂网络的社团结构，首先依据网络的拓扑信息，将网络节点投影成 高维空间的点，使得一个网络对应到高维空间中的一个点分布；接着使用主分量分析方法PCA对高维点分布降维， 保留点群分布的主要结构信息；再通过K-means聚类结果来推断网络的社团结构.基于2-mode数据和1-mode网络 数据实验表明，该方法可以快速、可靠地找出网络的社团将经典数据分析的聚类方法应用到网络分析中，验证了该 思路的有效性，为网络社团分析提供一个新视角. 关键词：复杂网络：社团划分：聚类：主分量分析 中图分类号：1P311;TP393;N94文献标识码：A文章编号：16734785(2011)010057-06 A clustering method for community detection on complex networks LI Wei,YANG Xiaofeng,ZHANG Chongyang,TANG Kezong,YANG Jingyu (Department of Computer Science,Nanjing University of Science and Technology,Nanjing 210094,China) Abstract:Community detection is important for understanding complex networks.Because of its high complexity, community detection in complex networks has recently attracted significant interest from research groups.In this work,a data analysis perspective was proposed for community detection on complex networks.First,based on the network topology,the nodes of the studied network were projected as data points in a high-dimensional space,and the network was associated with a data cloud.Second,principal component analysis (PCA)was used to reduce the high-dimensional data cloud into a low-dimensional one,which kept the main structural information.Third,K- means algorithms were used to find clusters of the data points in the reduced data cloud,which inferred the commu- nities of the studied network.Experiments on datasets DGG(2-mode)and Zachary (1-mode)indicated that the proposed method can reveal network communities effectively.The proposed method provided a novel perspective of the community detection of complex networks. Keywords:complex networks;community detection;cluster;PCA 近10年来，伴随着互联网的普及，计算技术的 样原来多样的复杂系统就可以从一个通用的网络视 发展，人们共享和处理大量数据的能力得到很大提 角来研究，称之为“复杂网络”研究[16 高，这使得需要大量现实数据支撑的复杂系统的实 复杂网络方法被广泛地应用到各个研究领域， 证研究成为可能.研究者采用整体研究模式，以探索 比如社会学中人际交互网络、合作网络、商业网的研 现实系统的宏观性质为目标，在多个学科领域取得 究，信息技术领域的文献索引网、互联网、万维网研 了重要进展3].特别地，通过忽略原系统中各个体 究，生物学中的蛋白质作用网络、神经网络、捕食网 自身细节，将组成系统的个体抽象为网络节点，即无 等的研究46].通过这样一个独特的研究视角，大量 论是细胞还是社会中的成员，一律看作是无属性的 实证研究证实了复杂网络模型在自然界和人类社会 节点，再将它们之间的相互关系抽象成网络的边，这 中的普遍性和有效性，而且来自于不同领域的复杂 系统惊奇地呈现出一些相同的性质，其中最具有代 收稿日期：2010-05-24 基金项目：国家自然科学基金资助项目(60632050,60873151). 表性的成果有Wats小世界效应]和Barabasi无标 通信作者：杨静宇.E-mai:yangiy@mail.just.edu.cm. 度特征[8
58 智能系统学报 第6卷 近来，复杂网络的另一个共同属性“社团结构” 分成各个小部分，见图1自上而下， 也引起了普遍的关注，人们发现在许多社会、生物网 络中都存在着社团结构9，即整个网络由多个社 团构成，这些社团的内部节点连接紧密，外部节点连 接稀疏.研究表明这些社团常常与系统的功能性质 有着很强的对应关系，如在人际交互网中，社团对应 着某些社群，这些社群的内部成员具有相似的职业、 政治倾向等社会属性91.同样，社团结构也反应在 图1层次聚类的凝聚、分裂方法 其他的社会网、信息网以及生态网中.社团结构的分 Fig.1 Agglomerative method and divisive method for 析有助于研究者进一步探索网络的内部结构，对认 hierarchical clustering 识原系统的属性有重要意义，对现实的社会分析、系 1.2图分割方法 统优化以及商业决策起着指导性作用， Kernighan和Lin在1970年提出了针对图分割 由于网络中社团结构分析的重要意义，近年来， 问题的Kernighan-Lin算法s].该方法首先将网络随 社团结构划分算法研究受到广泛的关注91.然而， 机地分成2个社团，然后通过重复交换来自这2个 由于社团划分问题自身的复杂性，现有的方法往往 社团的节点对，并在社团内部边数减去社团之间边 只在某个领域或某些条件下表现较优.因而，网络中 数达到最大时停止， 的社团划分问题仍然是研究人员面前的一个挑战. 谱平分法则是依据无向图G的Laplace矩阵 下面，首先介绍经典的社团划分方法；然后引人本文 (若G有n个节点，则其Laplace矩阵为n×n维对 方法：将网络社团划分看作一个数据挖掘问题，首先 称矩阵L.其对角元素等于点的节点度，若节点i与 将依据网络节点的影响力，将网络投影成高维空间 节点j连接，则L值为-1，否则为0)的第二小特征 的一个数据分布，再使用主分量降维，最后通过低维 值所对应的特征向量的元素的正、负符号将网络节 空间中的聚类结果来考察原网络的社团结构；文章 点分成2类14 最后讨论所提方法的优缺点及其改进， 考虑上述层次聚类和图分割算法，可以发现大 多数算法具有1个共同的不足之处，即在不知网络 网络社团划分经典算法 确切的社团数目时，很难确定算法何时终止.针对该 经典社团划分算法的思想很多来源于社会学中 问题，Girvan和Newman在2004年提出了网络社团 的层次聚类(hierarchical clustering)和计算机科学中 化评价函数Qo1.设网络被划分成n个社团，则Q 的图分割(graph partition)21.这些算法大致可以分 值计算如下： 成：凝聚方法(agglomerative method)、分裂方法(di- Q=∑(ew-a)=Te-‖e2. visive method)、搜索方法和其他方法.其中凝聚方法 式中：g表示社团i与社团j顶点之间的边占网络所 和分裂方法来源于社会学中寻找社团结构的层次聚 有边的比例；a:=∑e:表示与社团i中节点相连的边 类方法.Kernighan-Lin算法s]和谱平分算法[4]则 占网络所有边的比例；T。=∑e:则表示连接n个社 是图分割方法的代表。 团内部节点的边占网络所有边的比例；IeI为矩 1.1层次聚类算法 阵e2的模，即e2中元素的加总.物理意义上，Q函 凝聚方法和分裂方法是依据节点间的相似性， 数定义了社团内实际连接数目与随机连接情况下社 通过向网络中逐渐添加边或是从网络中移除边，把 团内连接数目之差，可以定量地刻画某种方法划分 网络自然地划分为各个社团.具体地，凝聚方法的思 结果的社团化程度.在具体算法迭代过程中，可以对 想是将初始的网络看成一个节点数为而边数为0 每一次社团划分结果计算Q值，当某次划分的Q值 的空网络，首先计算出两两节点之间的相似性，然后 达到峰值时，则可认为此时社团划分最优.基于该思 依次向相似性最高的节点对之间添加边，当该过程 想，一批基于传统的层次划分和图分割算法，并通过 停止时，这个网络的组成就认为是其原网络的社团 最优化目标函数Q来实现复杂网络的社团结构划 划分，见图1从下往上 分的方法涌现出来1 对应地，分裂算法是直接从原网络着手，首先计 然而，由于现实网络的规模巨大、结构复杂，使 算出两两节点之间的相似性，然后删除相似性最低 得网络社团划分问题通常需要搜索非常广阔的解空 的节点对之间的边，重复这个过程，网络就逐渐被细 间.在一般情况下，找到这类分割问题的精确解是一
第1期 李伟，等：复杂网络社团的投影聚类划分 ·59 个NP-hard问题).许多实际算法存在着需要预设 1,2,…,P5 参数，选择社团尺度，或者每次只能二分网络等限 2)当距离越大时，节点间的影响越小，计算距 制16，因而，网络中的社团划分问题仍然是一个挑 离的倒数1/d,作为节点间影响力度量； 战.本文从一个新的角度考虑网络划分问题：首先将 3)节点i对p个基准点的影响力向量为f:= 网络投影成高维空间的一个数据分布，接着使用主 （1/da,…,1/dn),当基准点选取的具有充分代表性 分量方法抽取主要分布结构，最后通过K-means算 时∫：可以表示节点i的网络影响力，向量∫将节点 法聚类低维空间中的数据，进而反推原网络的社团 i投影到高维度量空间. 结构. 2.2PCA降维 在得到所有n个网络节点的影响力向量后，构 2网络社团划分的投影聚类算法 建p×n影响矩阵F=[fif2…fn].再使用主分量分 近来，数据分析方法被有效地应用在网络分析 析PCA对矩阵F作降维，抽取主要结构信息， 领域719)，文献[19]首先将网络投影成高维空间的 1)首先在p维测量空间R”中计算F的标准化 点群分布，然后使用数据分析的主分量分析(PCA) 矩阵X,X的行均值为0，方差为1. 来抽取点群的主结构，并依据点群结构特征来反推 2)计算X的协方差矩阵C=Xx,对C作奇异 原网络的结构属性，结果表明，该方法可以重现复杂 值分解： 网络研究领域中mall-world网、scale-free网、nter C=Xx=(UV)(VΣU)=UAU net的层次结构等经典结果.在目前网络分析方法的 3)选择U的前q列记作U,计算R=U,X,R 研究尚未成熟时，通过将网络问题转化成一个传统 即为X的q维投影. 的数据分析问题，并有效地利用数据分析领域中经 接着用经典的K-means算法[2]对网络低维投 典方法来解决网络问题，具有广泛的实际意义， 影点R作聚类分析，将同一类的点所对应的原网络 本文沿用上述思路，首先将网络节点投影成高 顶点划分到个社团. 维空间点，接着使用P℃A对生成的点分布降维，最 3实验 后采用K-means方法聚类低维空间点，再根据聚类 结果来划分网络社团，方法原理见图2 3.1数据集 社横 我们使用了2个数据集作为实验数据，分别是 (a) 南方女士数据集DGC和空手道俱乐部数据集Za chary. 南方女士数据集是美国5位民族学者于20世 纪30年代在研究一个南部小镇阶层时收集的，根据 几位收集者的姓名首字母简称为DCG2I].DGC数 节点投影 据记录了9个月期间，18位女士(P1~P18)参加14 h 数据降维 件非正式的社会活动(E1~E14)的情况，是一个反 应行动者与事件之间关系的2-mode数据集.DCG 数据集的网络表示见图3，矩阵表示见表1，其中 ‘X’表示参加了该活动. 聚类 图2网络社团结构即聚类划分算法 Fig.2 Network community structure and illustra- tion of clustering algorithm 2.1节点投影 首先度量网络节点对网络的影响力，并依据节点 的影响力度量将其投影到度量空间，具体步骤如下， 图3南方女士数据集DGG的网络结构 1)随机选择p个网络节点作为度量基准点，计 Fig.3 Dllustration of DGG network 算当前度量节点到p个基准点的图论距离d;j=
·60 智能系统学报 第6卷 表1南方女士数据集DGG Table 1 Participants-events of DGG 参与事件 参与者 El E2 E3 E4 E5 E6 E7 E8 E9 E10 E11 E12 E13E14 PI X F F 下 子 P2 X X P3 X X X X X X X P4 X X P5 1 会 P10 P11 X P12 X P13 X X X P14 X P15 中 P16 P17 P18 X 空手道俱乐部数据集是Zachary在20世纪70 析的结果，见表2.表2中数字1(2)表示参与者被划 年代初，用了2年来观察美国某大学的空手道俱乐 分到第1(2)社团中；数字1/2表示算法判断某个参 部成员间的人际关系，并依据这些成员平时的交往， 与者分到第1或第2个社团均可；NA表示算法对某 建立的一个1-mode网络，它反应了成员之间的社交 个参与者的社团归属未能做出确切判断.本文结果 状况2]，见图2(a).空手道俱乐部网有34个点，代 在表2最后一行L&Y10给出. 表俱乐部成员；78条边，代表成员间的人际关系.在 考察表2，讨论以下3点. Zachary调查过程中，由于针对是否提高收费这一问 1)绝大多数算法将参与者P1~P7划到一个社 题，俱乐部管理者(1号顶点)与俱乐部教师(33号 团，本文方法得到相同结果。 顶点)之间产生了分歧并引发激烈的争论，最终导 2)在表2中，一个值得注意的地方是，部分算 致俱乐部网络分裂成2个部分：其中方形顶点代表 法认为P16、P17和P18的社团不可确定，理由是这 支持俱乐部管理者的成员，圆形顶点代表支持俱乐 3个参与者参加活动少，因而仅仅由可知的信息量 部教师的成员， 不能得到一个确定的判断.本文方法是一个强算法， 3.2实验结果及讨论 对每个参与者都会给出一个硬性划分.而且我们认 DCG和Zachary数据是具有代表性的社团结 为根据P16、P17、P18已有的活动信息，将她们划入 构，常常被使用作为示例来测试算法的效果，本文也 到社团二是合理的， 在这2个数据集上作算法测试： 3)DGG数据社团划分的难点在于判断参与者 1)计算各个网络节点的网络影响力，再根据节 P8的归属，各种方法给出了不同的结论.表1中，P8 点的影响力度量，将节点投影成高维空间点； 记录的社会活动有E6、E8和E9,其中E8是大多数 2)使用主分量分析PCA对生成的高维点降 人都会参与的大众活动，因而由活动E8不能推断 维，在具体实验中，保留前2维结构信息； 参与者P8的偏好，首先将E8排除不考虑.活动E6 3)计算点点间的距离（余弦），作K-means聚 和E9则是具有代表性的社团活动，其特征为绝大 类，根据聚类结果来决定网络的社团结构。 多数参与者是同一个社团内成员，很少有另一个社 3.2.1DGG数据实验结果 团成员参加.表2中部分算法认为P8具有更强的社 在Freeman的综述性文章23]中，列出了自1940 团一倾向，解释如下：比较E6和9，参与E6仅有一 年以来，超过20种方法在数据集DGG上作社团分 个社团外部成员P14,而参与E9的有3个非社团成
第1期 李伟，等：复杂网络社团的投影聚类划分 61… 员P1、P3和P9,因而，E6是比E9更典型的社团活 动是E5,而非6，P8参加了社团二最重要的活动 动，则P8的“社团一”性质更强.本文认为P8应归 E9,未参与社团一最重要活动E5,因而P8的“社团 入社团二，依据如下：比较E6和E9,E9的社团代表 二”性质更强.当然，关于P8的划分问题，关系到社 性高过E6;因为9是社团二中最具代表性的活动， 会学定量等复杂问题，在此仅作简要讨论，进一步结 社团二中几乎人人参加，而社团一的最具代表性活 论仍需进一步的研究， 表2DGG社团划分比较 Table 2 The comparison of community detection on DGG 算法 P1P2P3P4P5P6P7P8P9P10P11P12P13P14P15P16P17P18 DGG41 111 1111/2222222 222 HOM50 1 1 11/2 1 NA NA 2 2 2 2 NA 22 P&C72 1 1 2 2 2 2 2 BGR74 1 NA 2 2 2 2/32/3NA2/32/3 BBA75 1 1 2 2 2 2 2 2 2 2 2 BCH78 1 1 NA NA 2 2 2 2 2 2 NA D0R79 1 1 2 2 NA NA NA BCH91 1 1 2 2 2 2 FRE92 1 2 NA NA E&B93 nAnA Na FR193 1 2 2 2 FR293 1 2 2 2 2 FW193 1 2 2 1/2 2 FW293 1 1 NA 2 2 BE197 1 1 NA 2 NA NA NA BE297 1 1 2 BF397 2 2 2 2 2 S&F99 1 1 1 2 2 2 2 NA 2 2 ROBOO 1 1 1 2 2 2 2 2 2 2 2 OSBOO 1 1 2 2 NEWO1 1 1 1 1 1 2 1 2 2 2 2 2 2 2 2 2 L&Y10 1 1 1 1 2 1 2 2 2 2 2 2 2 3.2.2 Zachary数据实验结果 本文针对复杂网络中的社团划分问题，提出将 Zachary空手道俱乐部的实际社团结构见 网络的社团划分问题转化为数据聚类问题，给网络 图2(a),2个社团分别以方形和圆形顶点标出.本 中社团划分问题提供了一个新的解决视角.通过将 文方法得到2个社团，其中社团一中顶点为1、2、3、 经典的PCA、K-means等数据分析方法引入复杂网 4、5、6、7、8、11、12、13、14、17、18、20、22,社团二为9、 络分析领域，为社团划分提供新的理论方法，并在实 10、15、16、19、21、23、24、25、26、27、28、29、30、31、 验中验证了经典方法在复杂网络社团划分问题中的 32、33、34,可以看出，它能够将实际社团准确地划分 有效性.本文方法不仅可以用于1-mode网络的社团 出来[10-121 划分，而且可以直接处理2-mode网络，并且能得到 值得指出的是，DGG和Zachary均是小数据集， 优良的划分结果，不需要像传统方法那样，首先需要 实验中取所有网络顶点作为度量基准点；另外，K- 将2-mode网络转化成1-mode网络，再进行社团划 means方法作聚类时需要类别数作为预设参数，本 分，这使得所提方法在处理网络社团划分问题时具 文依据社团Q函数峰值设定类别数均为2. 有更高的通用性 目前，本文方法还只是应用在2个示例数据集 4结束语 上，而更多的现实网络往往要复杂的多，比如边是有 复杂网络的社团结构往往反应了系统的功能与 权值和方向的、网络规模又十分巨大等.如何将方法 性质，社团结构的分析有助于研究者进一步探索网 推广应用到更多的现实网络是下一步的工作：一是 络的关键结构，进而对认识原系统的性质有着指导 将算法泛化到有权有向网络；二是在大规模数据上 性意义 测试算法性能，进一步改进算法
智能系统学报 第6卷 本文提出的方法具有发展成通用方法的潜力、 Math Journal,1973,23(98),:298-305 通过将更多的经典数据方法引入到网络分析领域， [15]BRANDES U.DELING D.GAERTLER M.et al.Maxi- 可以为网络分析提供更多的理论工具，同时也为发 mizing modularity is hard[EB/OL]].(2006-08-30)[2010- 05-20].htp:://arxiv.org/abs/physics/0608255. 现和解释更多的网络特性提供了可能.我们希望通 16].FORTUNATO S.BARTHELEMY M.Resolution limit in 过与数据分析领域的科研人员以及网络科学工作者 community detection[J].Proceedings of the National A- 的进一步讨论，将本文方法进一步完善和发展。 cademy of Sciences of the United States of America,2007. 104(1):3641. 参考文献： 17].COSTA LD F,RODRIGUES F A,TRAVIESO G,et al. [1]JASNY B R,ZAHN L M,MARSHALL E.Special online Characterization of complex networks:a survey of measure- collection::complex systems and networks[EB/OL]. ments[J].Advances in Physics,2007,56(1)1:167-242 [2010-05-20].http://ww.sciencemag.org/complexity/.. [I8]]LI Wei,YANG Jingyu.Comparing networks from a data a- [2]DOROGOVISEV S N.GOLTSEV A V.MENDES J FF. nalysis perspective[J].Lecture Notes of the Institute for Critical phenomena in complex networks[J].Reviews of Computer Sciences,Social Informatics and Telecommuni- Moderm Physics,.2008,80(4):1275-1335 cations Engineering,2009,5:1907-1916. 圆汪秉宏，周涛，何大韧.统计物理与复杂系统研究最近发 [19]ILI Wei,YANG Jingyu,HADDEN W C.Analyzing com- 展趋势分析[].中国基础科学，2005,7(3)1：37-43. plex networks from a data analysis viewpoint[J].Euro- WANG Binghong,ZHOU Tao,HE Daren.The trend of re- physics Letters,2009,88(6):68007.. cent research on statistical physics and complex systems [20]]DUDA R O,HART P E,STORK D G.Patten classifica- [China Basic Science,2005,7(3):3743. tion[M]].New York,USA:John Wiley Sons,Inc., 4ALBERT R.BARABASI A L.Statistical mechanics of com- 2001::114-121. plex networks[J].Reviews of Modern Physics,2002,741 [21]]DAVIS A,GARDNER B B,GARDNER M R.Deep south ①.)：4797. [M].Chicago:The University of Chicago Press,1941: [5]NEWMAN M E J.The structure and function of complex 147. networks[J].SIAM Review,2003,45(2)::167-256. [22]ZACHARY WW.An information flow model for conflict 6BOCCALETTI S,LATORA V,MORENO Y.et al.Com-- and fission in small groups[J].Journal of Anthropological plex networks:structure and dynamics[J]].Physics Re- Research,1977,33:452473. ports,2006,424(4/5).:175-308. [23]FREEMAN L.Dynamic social network modeling and anal- [7]WATIS D J,STROGATZ S H.Colletive dynamics of ysis[M]Washington,DC,USA:"The National Academic 'small-world'networks[J]..Nature,1998,393(6638)': Press,2003::39-97. 40-442. 作者简介： 李伟，男，1978年生，博士.主要研究方 8BARABASI A L,ALBERT R.Emergence of scaling in ran- dom networks[J].Science,1999,286(5439)::509-512 向为复杂碰路、模式别、机器学习 9GIRVAN M.NEWMAN M E J.Community structure in so- cial and biological networks[J].Proceedings of the National Academy of Sciences of the United States of America,2001. 99(12):7821-7826 [10]]NEWMAN M E J,GIRVAN M.Finding and evaluating ommunity structure in networks[J].Physical Review E. 杨晓峰，男，1982年生，博士，主要 2004,69(2):026113. 研究方向为网络安全、人工智能 [11]FORTUNATO S.Community detection in graphs[J]. Physics Reports,2010,486(3/4/5):75-174 [12]解伯，汪小帆.复杂网络中的社团结构分析算法研究综 述0.复杂系统与复杂性科学，2005,2(3))：：-12 XIE Zhou,WANG Xiaofan.An overview of algorithms for analyzing community structure in complex networks[J].. 杨静宇，男，1941年生，教授，博士 Complex Systems and Complexity Science,2005,2(3): 生导师，教育部图像信息处理与智能 1-12. 控制重点实验室学术委员会委员，国际信 [13]KERNIGHAN B W,LIN S.A efficient heuristic procedure 息处理联合会(P)观察员.主要研究方 for partitioning graphs[J].Bel System Technical Journal,., 向为模式识别、智能机器人、智能系 1970,49(2))::291-307. 统.曾获奖14项，其中国家级2项，省部 [14]]FIEDILER M.Algebraic connectivity of graphs[J]].Czech 级12项.发表学术论文300余篇，出版论（译）著7部
第6卷 [4] ALBERT R,BARABASI A L. Statistical mechanics of complex networks[J] . Reviews of Modern Physics,2002,74 (1) :4797. [13] KERNIGHAN B W,LIN S. A efficient heuristic procedure for partitioning graphs[J]. Bel System Technical Journal, 1970,49(2) : 291-307. [9] GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[ J]. Proceedings of the National Academy of Sciences of the United States of America,2001, 99(12) : 7821-7826. [10] NEWMAN M E J,GIRVAN M. Finding and evaluating ommunity structure in networks[J]. Physical Review E, 2004,69(2) : 026113. 17] COSTA LD F,RODRIGUES F A,TRAVIES0 G,et al. Characterization of complex networks: a survey of measurements[J]. Advances in Physics,2007,56(1) : 167-242. [8] BARABASI A L,ALBERT R. Emergence of scaling in random networks[J] . Science,1999,286(5439) : 509-512. [12] 解伯,汪小帆.复杂网络中的社团结构分析算法研究综 述[J] .复杂系统与复杂性科学,2005,2(3) : 1-12. XIE Zhou,WANG Xiaofan. An overview of algorithms for analyzing community structure in complex networks[J] . Complex Systems and Complexity Science,2005,2(3) : 1-12. 62· [22] ZACHARY W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research,1977,33: 452473. 李伟,男,1978年生,博士.主要研究方 向为复杂网络、模式识别、机器学习. 智 能 系 统 学 报 [19] LI Wei,YANG Jingyu,HADDEN W C. Analyzing complex networks from a data analysis viewpoint[J] . Europhysics Letters,2009,88(6) :68007. 参考文献: [5] NEWMAN M E J. The structure and function of complex networks[J] . SIAM Review,2003,45(2) : 167-256. [2] DOROGOVISEV S N,GOLTSEV A V,MENDES J F F. Critical phenomena in complex networks[J] . Reviews of Moderm Physics,2008,80(4) : 1275-1335. 本文提出的方法具有发展成通用方法的潜力、 通过将更多的经典数据方法引入到网络分析领域, 可以为网络分析提供更多的理论工具,同时也为发 现和解释更多的网络特性提供了可能.我们希望通 过与数据分析领域的科研人员以及网络科学工作者 的进一步讨论,将本文方法进一步完善和发展. [15] BRANDES U,DELING D,GAERTLER M,et al. Maximizing modularity is hard[ EB/OL] .(2006-08-30) [2010- 05-20]. htp: //arxiv.org/abs/physics/0608255. [6] BOCCALETTI S,LATORA V,MORENO Y,et al. Complex networks: structure and dynamics[J] . Physics Reports,2006,424(4/5) : 175-308. [11] FORTUNATO S. Community detection in graphs[J]. Physics Reports,2010,486(3/4/5) : 75-174. [18] LI Wei,YANG Jingyu.Comparing networks from a data analysis perspective[J]. Lecture Notes of the Institute for Computer Sciences,Social Informatics and Telecommunications Engineering,2009,5: 1907-1916. [23] FREEMAN L. Dynamic social network modeling and analysis[ M] . Washington,DC,USA: The National Academic Press,2003: 39-97. [7] WATIS D J, STROGATZ S H. Colletive dynamics of 'small-world’networks[J] . Nature,1998,393(6638) : 40-442. [20] DUDA R O,HART P E,STORK D G. Patten classification[ M] . New York,USA: John Wiley & Sons,Inc., 2001: 114-121. [3] 汪秉宏,周涛,何大韧.统计物理与复杂系统研究最近发 展趋势分析[J].中国基础科学,2005,7(3) : 37-43. WANG Binghong,ZHOU Tao,HE Daren. The trend of recent research on statistical physics and complex systems [J]. China Basic Science,2005,7(3) : 3743. 作者简介: Math Journal,1973,23(98) : 298-305. [14] FIEDILER M. Algebraic connectivity of graphs[J] . Czech 16] FORTUNATO S,BARTHELEMY M. Resolution limit in community detection[ J]. Proceedings of the National Academy of Sciences of the United States of America,2007, 104(1) : 3641. [21] DAVIS A,GARDNER B B,GARDNER M R. Deep south [M] . Chicago: The University of Chicago Press,1941: 147. [1] JASNY B R,ZAHN L M,MARSHALL E. Special online collection: complex systems and networks[ EB/OL] . [2010-05-20]. http: //ww.sciencemag.org/complexity/. 杨晓峰,男,1982年生,博士,主要 研究方向为网络安全、人工智能. 杨静宇,男,1941年生,教授,博士 生导师,教育部图像信息处理与智能 控制重点实验室学术委员会委员,国际信 息处理联合会(IFP) 观察员.主要研究方 向为模式识别、智能机器人、智能系 ) : 统.曾获奖14项,其中国家级2项,省部 : ): : ) : r 。 级12 项.发表学术论文300余篇,出版论(译) 著7部