ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn Journal of Software, Vol.20, No.1, January 2009, pp.54−66 http://www.jos.org.cn doi: 10.3724/SP.J.1001.2009.03464 Tel/Fax: +86-10-62562563 © by Institute of Software, the Chinese Academy of Sciences. All rights reserved.

复杂网络聚类方法∗ 杨 博1,2, 刘大有1,2+, LIU Jiming3, 金 弟1,2, 马海宾1,2 1(吉林大学 计算机科学与技术学院,吉林 长春 130012) 2(吉林大学 符号计算与知识工程教育部重点实验室,吉林 长春 130012) 3(香港浸会大学 计算机科学系, 香港) Complex Network Clustering Algorithms

YANG Bo1,2, LIU Da-You1,2+, LIU Jiming3, JIN Di1,2, MA Hai-Bin1,2 1(College of Computer Science and Technology, Jilin University, Changchun 130012, China) 2(Key Laboratory of Symbolic Computation and Knowledge Engineering for the Ministry of Education, Jilin University, Changchun 130012, China) 3(Department of Computer Science, Hong Kong Baptist University, Hong Kong, China) + Corresponding author: E-mail: dyliu@jlu.edu.cn Yang B, Liu DY, Liu J, Jin D, Ma HB. Complex network clustering algorithms. Journal of Software, 2009, 20(1):54−66. http://www.jos.org.cn/1000-9825/3464.htm Abstract: Network community structure is one of the most fundamental and important topological properties of complex networks, within which the links between nodes are very dense, but between which they are quite sparse. Network clustering algorithms which aim to discover all natural network communities from given complex networks are fundamentally important for both theoretical researches and practical applications, and can be used to analyze the topological structures, understand the functions, recognize the hidden patterns, and predict the behaviors of complex networks including social networks, biological networks, World Wide Webs and so on. This paper reviews the background, the motivation, the state of arts as well as the main issues of existing works related to discovering network communities, and tries to draw a comprehensive and clear outline for this new and active research area. This work is hopefully beneficial to the researchers from the communities of complex network analysis, data mining, intelligent Web and bioinformatics. Key words: complex network; network clustering; network community structure 摘 要: 网络簇结构是复杂网络最普遍和最重要的拓扑属性之一,具有同簇节点相互连接密集、异簇节点相互连接稀疏的特点.揭示网络簇结构的复杂网络聚类方法对分析复杂网络拓扑结构、理解其功能、发现其隐含模式、预测其行为都具有十分重要的理论意义,在社会网、生物网和万维网中具有广泛应用.综述了复杂网络聚类方法的研究背景、研究意义、国内外研究现状以及目前所面临的主要问题,试图为这个新兴的研究方向勾画出一个较为全面 ∗ Supported by the National Natural Science Foundation of China under Grant Nos.60496321, 60503016, 60573073, 60873149 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2006AA10Z245 (国家高技术研究发展计划(863))

Received 2008-06-17; Accepted 2008-08-28

杨博 等:复杂网络聚类方法 55

和清晰的概貌,为复杂网络分析、数据挖掘、智能Web、生物信息学等相关领域的研究者提供有益的参考. 关键词: 复杂网络;网络聚类;网络簇结构 中图法分类号: TP311 文献标识码: A

现实世界中的诸多系统都以网络形式存在,如社会系统中的人际关系网、科学家协作网和流行病传播网,生态系统中的神经元网、基因调控网和蛋白质交互网,科技系统中的电话网、因特网和万维网等.由于这些网络具有很高的复杂性,因此被称为“复杂网络(complex network)”.复杂网络已成为当前最重要的多学科交叉研究领域之一[1−3].与小世界性[1]、无标度性[2−4]等基本统计特性相并列,网络簇结构(network cluster structure或network community structure)是复杂网络最普遍和最重要的拓扑结构属性之一,具有同簇节点相互连接密集、异簇节点相互连接稀疏的特点[5−9].复杂网络聚类方法旨在揭示出复杂网络中真实存在的网络簇结构. 复杂网络聚类方法的研究对分析复杂网络的拓扑结构、理解复杂网络的功能、发现复杂网络中的隐藏规律以及预测复杂网络的行为不仅具有十分重要的理论意义,而且具有广泛的应用前景,目前已被应用于恐怖组织识别、组织结构管理等社会网络分析[5,7,10−12]、新陈代谢网络分析[7,13]、蛋白质交互网络分析和未知蛋白质功能预测[14−16]、基因调控网络分析和主控基因识别[8]等各种生物网络分析以及Web社区挖掘和基于主题词的Web文档聚类[17−19]和搜索引擎[20−22]等众多领域. 由于复杂网络聚类研究具有重要的理论意义和应用价值,它不仅成为计算机领域中最具挑战性的基础性研究课题之一,也吸引了来自物理、数学、生物、社会学和复杂性科学等众多领域的研究者,掀起了一股研究热潮.从2002年至今,新的方法层出不穷,新的应用领域不断被拓展,《Nature》[6,7,10],《Science》[13],《Proc. of National Academy of Sciences (PNAS)》[5,8,9,23−25],《Physics Review Letter》[26,27],《IEEE Trans. on Knowledge and Data Engineering(TKDE)》[28,29],《PLOS Computational Biology》[14,30]等不同领域的权威国际杂志和多个重要的国际学术会议(如数据挖掘领域权威国际会议ACM SIGKDD[31]和IEEE ICDM[32],万维网领域权威国际会议WWW[19,21]等)多次报道这方面的研究工作.复杂网络聚类方法已成为图论、复杂网络、数据挖掘等基础理论的重要组成部分和相关课程的核心内容,如康奈尔大学计算机系开设的“The Structure of Information Networks”课程和麻省理工大学电子工程和计算机系开设的“Networks and Dynamics”课程. 在以上研究背景下,本文综述了复杂网络聚类方法的研究现状以及目前面临的主要问题,试图为该研究方向勾画出一个较为全面和清晰的概貌,为复杂网络分析、数据挖掘等相关领域的研究者提供有益的参考.本文第1节分析复杂网络聚类问题的研究现状,重点分析15个具有代表性的复杂网络聚类算法.第2节通过实验定量分析和比较7种典型算法的性能.第3节总结全文并给出本文的一些结论. 1 复杂网络聚类方法分类与分析 复杂网络可以建模为一个图G=(V,E),V表示网络的节点集合,E表示连接的结合.复杂网络可以是无向图、有向图、加权图或者超图.网络簇定义为网络的稠密连通分支,具有簇内连接稠密、簇间连接相对稀疏的特点.例如,可以把人类社会抽象成一个称为“社会网络”的加权有向图.图中节点表示人,有向边表示人与人之间的社会关系,权值表示关系的强弱,路径表示由社会关系组成的“关系链”,网络簇表示由多个具有共同属性的人组成的“社团”.除社会网络之外,常见的复杂网络还有生物网络和科技网络.研究发现,尽管客观世界中的复杂系统功能各样,但它们对应的复杂网络在结构上却具有十分惊人的相似性.根据网络结构的特点,科学家把绝大多数的复杂网络归纳为3类:随机网络、小世界网络和无标度网络.复杂网络的核心研究内容是揭示复杂网络功能和结构之间的内在联系.目前,用于刻画复杂网络结构的重要属性是平均路长、聚类系数、度分布、网络Motif和网络簇结构.借助复杂网络簇结构分析方法,科学家取得了一些有关网络功能和结构的初步研究结果,如:揭示出蛋白质功能和交互关系的内在联系、网页主题和超连接的内在联系、社会组织如何随时间演化等.然而,已有的研究结果还远未揭示复杂网络功能与结构的内在联系,在理论和应用上都还存在许多亟待解决的问题.本文主要从计算方法的角度,围绕复杂网络簇结构的发现算法进行讨论,

分析和比较现有算法的基本原理、特

56 Journal of Software 软件学报 Vol.20, No.1, January 2009

点、不足和需要解决的问题. 目前已存在多种复杂网络聚类算法,按照所采用的基本求解策略,本文将它们中的大多数归纳为两大类:基于优化的方法(optimization based method)和启发式方法(heuristic method).前者将复杂网络聚类问题转化为优化问题,通过最优化预定义的目标函数来计算复杂网络的簇结构.例如,谱方法(spectral method)将网络聚类问题转化为二次型优化问题,通过计算特殊矩阵的特征向量来优化预定义的“截(cut)”函数.后者将复杂网络聚类问题转化为预定义启发式规则的设计问题.例如,被广泛引用的Girvan-Newman算法[5]的启发式规则是:簇间连接的边介数(edge betweenness)应大于簇内连接的边介数.除了以上两类方法之外,还存在其他类型的复杂网络聚类方法.按照本文的分类方法,现有复杂网络聚类方法的分类如图1所示,本节将具体分析各类方法的典型代表.

Fig.1 Classification chart of complex network clustering algorithms 图1 复杂网络聚类算法分类图 1.1 基于优化的复杂网络聚类方法 谱方法和局部搜索方法是两类主要的基于优化的复杂聚类方法. 1.1.1 谱方法 谱方法最早用于解决图分割(graph partition)问题,近年来被应用到复杂网络聚类[23,31,33,34].谱方法采用二次型优化技术最小化预定义的“截”函数.当一个网络被划分为两个子网络时,“截”即指子网间的连接密度.具有最小“截”的划分被认为是最优的网络划分.针对不同问题,提出了不同的“截”函数.例如,针对分布式系统负载平衡提出的“平均截(average cut)”[35,36]、针对大规模集成电路(VLSI)设计提出的“比率截(ratio cut)”[37,38]以及针对图像分割提出的“规范截(normalized cut)”[39]等.已经证明,最小化以上的“截”函数是NP完全问题[39,40].采用矩阵分析技术,谱方法将求解最小“截”问题转化为求解带约束的二次型优化问题:min{(XTMX)/(XTX)},其中,向量X表示网络划分,M表示对称半正定矩阵.对于“平均截”,M=D−A表示网络的拉普拉斯矩阵(Laplacian matrix),其中D表示由节点度构成的对角矩阵,A为网络的邻接矩阵;对于“规范截”,M=D−1/2(D−A)D−1/2表示网络的规范化拉普拉斯矩阵;对于其他截函数,M是拉普拉斯矩阵的不同变体.由拉格朗日方法,以上约束二次型的近似最优解(即网络的近似最优划分)可以通过计算M的第2小特征向量求得.一般地,n维矩阵特征向量的计算时间为O(n3).对于稀疏网络,采用Lanczos算法[41],M的第2小特征向量的计算时间为32(/())Omλλ−,其中m表示网络连接数目,λ2和λ3分别表示M的第二、第三小特征值.谱方法本质上是一种二分法,在每次二分过程中,网络被分割成两个近似平衡的子网络.当网络中含有多个簇时,谱方法递归地分割现存的子网络,直到满足预先定义的停止条件为止. 谱方法具有严密的数学理论,已发展成数据聚类的一种重要方法(称为谱聚类法),被广泛应用于图分割和Complex networks clustering algorithms

Optimization based algorithmsHeuristic algorithmsOthers

Spectral methods

Average cut Ratio cut

Normalized cut Local search

Kernighan-Lin

Fast Newman

Guimera-Amaral

Potts model with multi-spin states

MFCGirvan-NewmanHITSWu-HubermanCPMTyler RadicchiSimilarity based methodsHybrid methods

Correlation coefficient

Random walk based

similarity

Clustering centrality

HallDonetti-MunozFEC