复杂网络聚类算法综述

龙源期刊网复杂网络聚类算法综述作者：李建郑晓艳来源：《电脑知识与技术》2015年第05期摘要：随着复杂网络应用的日益广泛，发现复杂网络簇结构的复杂网络聚类算法越来越多。这导致在实际应用中根据实际的复杂网络结构选择合适的聚类算法成为一大难题。针对这种情况，根据复杂网络聚类算法的求解策略，通过介绍各个经典的复杂网络聚类算法的基本原理、实现步骤以及优缺点，对这些算法进行归类和比较，得出了它们对应的更好的适用范围，有助于在复杂网络聚类分析中选取合适的算法解决问题，为相关领域的研究者提供了参考。关键词：复杂网络；簇结构；聚类中图分类号：TP311文献标识码：A文章编号：1009-3044（2015）05-0037-05SurveyofComplexNetworkClusteringAlgorithmsLIJian，ZHENGXiao-yan（CollegeofInformationTechnologyEngineering，TianjinUniversityofTechnologyandEducation，Tianjin300222，China）Abstract：Complexnetworkclusteringalgorithmswhichaimtodiscovernetworkcommunitiesareincreasingalongwiththewideapplicationofcomplexnetworks，soitishardtoselecttheappropriateclusteringalgorithmbasedontheactualstructureofcomplexnetworksinapplication.Inviewofthissituation，itclassifiesandcomparestheclassicalcomplexnetworkclusteringalgorithmsthroughintroducingthebasicprinciple，theimplementsteps，theadvantagesanddisadvantagesaswellasthesolvingstrategyofthecomplexnetworkclusteringalgorithms.Finally，itgetsthebetterscopeofapplication，whichisbeneficialtoselectingtheappropriatealgorithmsforthecomplexnetworkclusteringanalysisandprovidingareferenceforresearchers.Keywords：complexnetwork；communitystructure；clustering近几年随着复杂网络的发展，现实世界中的各种网络大量涌现，许多复杂系统直接或间接地以复杂网络的形式存在，如社会关系网、新陈代谢网等。网络簇结构（networkcommunitystructure）是复杂网络最普遍和最重要的拓扑结构属性之一，具有同簇节点相互连接密集、异簇节点相互连接稀疏的特点，复杂网络聚类是为了找到复杂网络中真实存在的全部簇[1]。研究复杂网络聚类算法有助于挖掘出复杂网络的内在规律、拓扑结构、各类功能以及发展趋势，具有重要的理论意义和广阔的应用前景。在此背景下，本文概述了各复杂网络聚类算法的基本思想、实现步骤和优缺点。龙源期刊网目前，复杂网络聚类算法有两种求解方法，第一种是启发式方法，将复杂网络聚类问题转化成预定义启发式规则的设计问题；第二种是基于优化的方法，通过最优化预定义的目标函数来计算复杂网络的簇结构从而将复杂网络聚类问题转化成优化问题[2]。1启发式方法典型的启发式复杂网络聚类算法有hyperlinkinducedtopicsearch（HITS）算法[3]、maximumflowcommunity（MFC）算法[4]、Girvan-Newman（GN）算法[5]及其改进、Wu-Huberman（WH）算法[6]、cliquepercolationmethod（CPM）算法[7]、findingandextract-ingcommunities（FEC）算法[8]、基于标签传播的网络聚类算法和基于仿生计算的网络聚类算法。以上算法都是利用某种直观假设，可快速找到大多数复杂网络的最优解或近似最优解，但是却不能保证对于任意网络都可以得出很好的解。1.1HITS算法1999年，Kleinberg等人提出了HITS算法[3]，认为web页面有权威性（Authority）和枢纽性（Hub），取值依次用和表示。HITS算法利用页面之间的引用链来发现隐含在中的网络簇结构，计算简单且效率高，已被广泛应用。HITS算法的实现步骤简述如下：（1）选取根集；（2）构造基集；（3）构造邻接图；（4）迭代得出结果。HITS算法虽然能很好地描述Web的组织特点，但易出现主题漂移现象，导致不同的查询算法要重新运行，开销过大，因此HITS算法不能用于实时系统。1.2MFC算法2002年，GW.Flake等人提出了MFC算法[4]，它的提出思想是簇内边的密度远远大于簇间边的密度。簇间连接构成网络“瓶颈”，其容量决定最大流量，可由最小截集计算得出，反复识别、删除簇间连接，可以逐渐分离网络簇，当前计算最小截集最快需要。Flake等人把MFC算法应用于基于链接的Web网页聚类研究，为基于主题词的Web网页/文本聚类研究开阔了思路。1.3GN算法及其改进2002年，Girvan和Newman提出了著名的GN算法[5]。GN算法以簇间连接的边介数应大于簇内连接的边介数为启发式规则，不断删除边介数最大的边，最终把整个网络划分成若干个网络簇[1]。边介数定义成，表示为起点，作终点的路径中经过的最短路径的数量，是网络中经过的所有最短路径的数量。GN算法的实现步骤简述如下：（1）计算全部边的介数；（2）删除介数最大的边；（3）更新剩余边的介数；（4）重复（2）、（3），直到删除所有的边。龙源期刊网算法，该算法最大的缺点是计算速度慢、开销大，时间复杂度很高，所以其不适合处理大规模的网络。针对该问题，学者们对GN算法进行改进，而后提出了采用节点集的GN算法和自包含GN算法等。1.4WH算法2004年，Wu和Huberman结合物理学知识，提出了WH算法[6]，在该算法中，整个网络被看作一个电阻网络，每条边被看作一个电阻，位置不同的节点电位势不同。选取位于不同簇中的两个节点作为正负极，根据簇内电阻远远小于簇间电阻得出异簇节点位势不同而同簇节点位势近似相同[6]。WH算法利用最大位势差来识别网络簇，该过程可在线性时间内完成，但是WH算法往往需要大量难以获取的先验知识。1.5CPM算法复杂网络的快速发展使更多的研究者投入到重叠网络的研究。2005年，Palla等人提出了CPM算法[7]，他们认为网络簇可以看作由若干重叠的团组成，通过搜索相邻的团可检测网络的簇结构。CPM算法的实现步骤简述如下：（1）确定参数，找到复杂网络中所有的-团；（2）把每个团看作一个顶点，若两个-团共享个节点，则对应的顶点有边相连，否则无边相连；（3）构建重叠矩阵，计算网络簇结构。虽然CPM算法是首个可以识别重叠网络簇结构的算法，但是参数不同则聚类结果不同，且参数不易确定[1]。除此之外，CPM算法的时间复杂度近似指数阶。1.6FEC算法2007年，Yang等人针对符号网络聚类问题，在Markov随机游走理论的基础上提出了FEC算法[8]，符号网络包含正、负两种关系，在复杂系统中普遍存在。FEC算法的基本假设是：如果从网络中任意一个簇出发进行随机游走，结果到达起始簇内节点的概率应大于到达剩余簇中节点的概率[9]。在此基础上，FEC算法的实现步骤简述如下：（1）任选目的节点，计算其步转移概率分布；（2）将与所有节点相对应值按降序排序，寻找使截函数（CutCriterion）最大的二分分裂点；（3）若算法已满足基于截函数的终止条件，递归结束；否则，按分裂点把当前网络分成两个子网络，递归执行上述步骤。随机游走步长是FEC算法唯一的参数，其取值影响聚类，经验取值区间是[6，20]。FEC算法较好的精度和时间性能使其适用于簇结构模糊和噪声高的复杂网络，但该算法没有从理论上给出设置[l]的通用方法。1.7基于标签传播的网络聚类算法2002年，Zhu等人提出了LPA算法[10]，其使用已被标记的节点标签信息来预测未被标记的节点标签信息。LPA算法的实现步骤简述如下[11]：（1）构造边权重矩阵，得出数据之间龙源期刊网的相似度；（2）计算节点之间的传播概率；（3）定义标注矩阵；（4）根据（2）、（3）更新概率分布；（5）更新初始矩阵，重复（4），直到收敛。2007年，Raghavan等人提出RAK算法[12]，第一次把LPA的思想应用到复杂网络聚类中。2009年，Leung等人[13]通过研究发现LPA算法有很大潜力处理大规模网络的聚类问题。2009年，Barber对LPA算法的目标函数进行修正，提出了带约束的LPAm算法[14]，改善了LPA算法的聚类性能。2010年，Liu等人考虑到LPAm算法易陷入局部最优解，在层次贪婪算法MSG和LPAm算法的基础上，提出了LPAm+算法[15]，进一步改善了标签传播类算法的聚类性能。1.8基于仿生计算的网络聚类算法2007年，Liu等人在研究蚂蚁行为的基础上提出了蚁群聚类算法[16]，该算法应用于邮件社会网络。2010年，刘大有等人在Markov随机游走的基础上提出了RWACO算法[17]，之后对RWACO算法进行了改进。2011年，公茂果等人提出了密母算法[18]，该算法可以有效探测网络中的层次簇结构。2012年，何东晓等人提出多层蚁群算法（MABA算法）[19]，该算法可发现网络中的层次簇结构，其实现步骤简述如下：（1）运行其子算法，发现网络簇结构；（2）把簇看作节点，簇间链接看作加权边，构建上层网络，并将子算法用于此网络；（3）重复以上步骤，直到模块度函数不再增加。2基于优化的算法在基于优化的复杂网络聚类算法中，两种经典的代表算法是谱聚类算法和局部搜索算法。2.1谱聚类算法谱聚类算法基于谱图理论，把各个样本数据视为顶点，通过利用数据之间的相似度给点之间的边赋权值得到一个无向加权图，如此把聚类的问题转化成对图的划分问题。其划分准则是使子图内部的相似度最大、子图之间的相似度最小[20]。常见的划分准则有Minicut、Averagecut、Normalizedcut、Min-maxcut、Ratiocut和MNcut等。根据不同的准则函数及谱映射方法，谱聚类算法可以分为二路谱聚类算法和多路谱聚类算法。龙源期刊网算法[21]、Shi和Malik提出的SM算法[20]、Scott和LanguetHiggins提出的SLH算法[22]、KannanR和VempalaS提出的KVV算法[23]以及Ding提出的Mcut算法[24]。经典的多路谱聚类算法有Ng，Jordan等人提出的NJW算法[25]以及Meila提出的MS算法[26]。上述典型算法的比较，如表1所示。这些算法的实现步骤都可用以下三个重要步骤表示：（1）构建表示样本集的矩阵[Z]；（2）计算[Z]的前个特征值与特征向量，构建特征向量空间；（3）利用经典的聚类算法对特征向量进行聚类。谱聚类算法可发现不规则形状的网络簇，应用于各种形状的样本空间，且结果收敛于全局最优解。近几年谱聚类算法的研究虽有了一定的成果，但仍有以下需要解决的问题：（1）如何构造相似矩阵[