复杂网络聚类算法的研究

1复杂网络聚类方法研究吉林大学知识工程教研室吉林大学计算机学院2目录1.复杂网络聚类方法的研究背景及意义2.复杂网络聚类方法的研究现状及分析3.复杂网络聚类所面临的问题4.我们的工作5.复杂网络vs时空数据挖掘31.复杂网络聚类方法的研究背景及意义现实世界中的诸多系统都以网络形式存在，如社会系统中的人际关系网、科学家协作网和流行病传播网，生态系统中的神经元网、基因调控网和蛋白质交互网，科技系统中的因特网、万维网、通信网、交通网等。由于这些网络所对应的系统具有很高的复杂性，因此被统称为“复杂网络(complexnetwork)”。4社会网络（SocialNetworks）科学家协作网移动电话网络《圣经》对应的社会网络5生物网络（BiologicalNetworks）食物链网络新陈代谢系统网络蛋白质交互网络6科技网络（TechnologicalNetworks）7O(101)O(103)O(108)复杂网络分析具有重要研究意义对于小规模网络，我们可以通过肉眼观测其形态、特征，但是对于(超)大规模复杂网络，我们将很难通过肉眼深入理解和预测网络的结构、行为和功能，需要借助各种复杂网络分析方法。81.复杂网络聚类方法的研究背景及意义复杂网络已成为当前最重要的多学科交叉研究领域之一。小世界性、无标度性、网络模体和网络簇结构是迄今为止发现的最普遍和最重要的复杂网络拓扑结构属性。9SmallWorld(Nature1998)小世界网络：具有较小的平均路径长度，同时具有较大的聚类系数。平均长度：网络中任意两点间最短路径长度的平均值。聚类系数：节点的任意两个邻居节点仍互为邻居的平均概率10Scale-freenetwork(Science1999)无标度性：网络的度分布呈现出幂率分布（powerlaw），而不是随机网络的泊松分布：P(K)~K-a11Degreedistribution()!kePXkk()aPXkkPoissondistributionPower-lawdistribution12NetworkMotif(Science1999)NetworkMotif：在统计意义上，网络中频繁出现的子图模式。（某些子图在现实网络中出现的概率明显高于这些子图在随机网络中出现的概率）。13NetworkCommunityStructure(Science2002,Nature2005,2007)网络簇结构（networkcommunitystructure）具有同簇节点相互连接密集、异簇节点相互连接稀疏的特点。141.复杂网络聚类方法的研究背景及意义复杂网络聚类方法的研究对分析复杂网络的拓扑结构、理解复杂网络的功能、发现复杂网络中的隐藏规律和预测复杂网络的行为不仅有十分重要的理论意义，而且有广泛的应用前景。目前已被应用于：恐怖组织识别与组织结构管理等社会网络分析，围绕新陈代谢、蛋白质交互、未知蛋白质功能预测、基因调控和主控基因识别等问题的多种生物网络分析，Web社区挖掘与Web文档聚类，搜索引擎，空间数据聚类，图像分割，以及关系数据分析等众多领域。Nature200515-100102030-10-5051015应用例子1–聚类分析Gaussiansimilarityfunction（高斯相似度函数）:16应用例子2社会网络、语义网络、生物网络分析(Nature2005)科学家合作网：每个节点表示一个科学家，连接表示科学家之间的合作紧密程度。语义网络:每个节点表示一个英文单词，连接表示词在某个语境下共同出现的频率。17聚类基因网络Nature200318聚类新陈代谢网络Nature200519聚类蛋白质网络(Nature2005)（芽殖酵母菌）的蛋白质交互网络20动态社会网络簇结构分析(Nature2007)该研究结果发现了维持社会结构稳定性的两个基本原则：对于大规模社会机构，其成分的动态变化利于维护该机构的稳定性；相反的，对于小规模机构，其成分的固定不变利于维护该机构的稳定性。21基于网络簇结构分析的链接预测(Nature2008)该研究提出了一种广义的随机网络模型（相对于经典的ER随机网络模型）：（1）具有更强的表达能力，既能刻画assortative网络又能刻画disassortative网络；（2）对于给定的网络，该模型能够精确的预测出网络中的未知链接或缺失链接，并能剔除网络中存在的噪音链接。221.复杂网络聚类方法的研究背景及意义（续）复杂网络聚类方法已成为图论、复杂网络、数据挖掘等理论的重要组成部分和相关课程的核心内容。如康奈尔大学计算机系开设了《TheStructureofInformationNetworks》课程，麻省理工电子工程和计算机系开设了《NetworksandDynamics》课程。由于复杂网络聚类研究具有重要的理论意义和应用价值，它不仅成为计算机领域中最具挑战性的基础性研究课题之一，也吸引了来自物理、数学、生物、社会学和复杂性科学等众多领域的研究者，掀起了一股研究热潮。从2002年至今，新的方法层出不穷，新的应用领域不断被拓展，不同领域的权威国际杂志和多个重要国际学术会议多次报道这方面的研究工作。232.复杂网络聚类方法的研究现状及分析2.1复杂网络聚类方法的分类2.2基于优化的复杂网络聚类算法2.3启发式复杂网络聚类算法2.4其它网络聚类算法242.1复杂网络聚类方法的分类基于优化的方法将复杂网络聚类问题转化为优化问题，通过最优化预定义的目标函数来计算复杂网络的簇结构。启发式方法将复杂网络聚类问题转化为预定义启发式规则的设计问题。除以上两类方法之外，还存在其它类型的复杂网络聚类方法。252.1复杂网络聚类方法的分类262.2基于优化的复杂网络聚类方法2.2.1谱方法2.2.2基于局部搜索的复杂网络聚类方法2.2.3其它基于优化方法的复杂网络聚类方法272.2.1谱方法（SpectralMethod）谱方法采用二次型优化技术最小化预定义的“截函数”。当一个网络被划分成两个子网络时，“截”指子网间的连接密度。具有最小“截”的划分被认为是最优的网络划分。谱方法具有严密的数学理论，已发展成数据聚类的一种重要方法(称为谱聚类法)，被广泛应用于图分割和空间点聚类等领域。针对复杂网络聚类，谱方法的主要不足是：1）需要借助先验知识定义递归终止条件，即谱方法不具备自动识别网络簇总数的能力；2）现实世界中的复杂网络往往包含多个网络簇，而谱方法的递归二分策略不能保证得到网络划分是最优的多网络簇结构。281.1970年，针对图分割问题克宁汉－林(B.W.Kernighan和S.Lin)提出了KL算法，该算法也可用于复杂网络聚类。2.KL算法简介KL的优化目标是：极小化簇间连接数目与簇内连接数目之差的绝对值；KL算法的不足：找到的解往往是局部最优而不是全局最优解。KL对初始解非常敏感，它需要先验知识。KL算法的时间复杂性:O(tn2)，t表示算法终止时的迭代次数，n表示网络节点个数。Kernighan-Lin算法(《BellSystemTechnicalJournal》,1970)291.2004年，纽曼(M.E.J.Newman)提出了基于局部搜索的快速复杂网络聚类算法FN.2.算法FN简介FN的优化目标：极大化纽曼与格万(M.E.J.Newman和M.Girvan)于同年提出的网络模块性评价函数：Q函数.Q函数定义为簇内的实际连接数目与随机连接下簇内的期望连接数目之差，用来定量地刻画网络簇结构的优劣.Q值越大则网络簇结构越好。FN算法的时间复杂性:是O(mn)，m和n分别表示网络的连接数和节点数快速Newman算法(《PhysicalRev.E》,2004)301.2005年，吉莫热与阿麦拉尔(R.Guimera和L.A.N.Amaral)采用与算法FN相同的优化目标函数，提出了基于模拟退火算法(SA)的复杂网络聚类算法GA，并应用到新陈代谢网络分析中。《Nature》2005年2月刊报道了该项研究工作。2.算法GA的优缺点GA采用模拟退火控制策略，因此GA具有跳过局部最优解、找到全局最优解的能力，因而具有很好的聚类精度。GA的效率取决于算法SA的效率，而后者通常收敛很缓慢。GA对输入参数非常敏感，不同的参数设置往往导致不同的聚类结果。Guimera-Amaral算法(《Nature》,2005)31启发式复杂网络聚类算法的共同特点是：基于某些直观假设来设计启发式算法，对大部分网络来说，它们能快速找到最优解或近似最优解，但无法从理论上严格保证它们对任何输入网络都能在令人满意的时间内找到令人满意的解。本报告介绍几个典型的启发式复杂网络聚类算法：算法GN(Girvan-Newman)算法HITS(HyperlinkInducedTopicSearch)算法CPM(CliquePercolationMethod)算法FEC(FindingandExtractingCommunities)2.3启发式复杂网络聚类方法322.3.2GN算法(PNAS,2002)2002年，格万和纽曼(M.Girvan和M.E.J.Newman)提出了基于反复识别和删除簇间连接策略的复杂网络聚类算法GN.GN算法的缺点GN的最大缺点是计算速度慢，边介数计算的开销过大O(mn)，GN具有很高的时间复杂性O(m2n)，只适合处理中小规模的网络(包含几百个节点的网络)。GN算法的意义在复杂网络聚类研究中，GN算法占有十分重要的地位（该文被引用超过1000次），格万和纽曼工作的重要意义在于：他们首次发现了复杂网络中普遍存在的网络簇结构，启发了其他研究者对这个问题的深入研究，掀起了复杂网络聚类的研究热潮。332.3.4HITS算法(JournalofACM,1999)1999年，针对基于链接的网页排名问题，克莱因博格(Kleinberg)等人提出了著名的HITS算法，该算法也可用于基于内容的网页聚类。HITS算法基于的基本假设根据链接关系，中存在权威(authority)和中心(hub)两种基本类型的页面，权威页面倾向于被多个中心页面引用，而中心页面倾向于引用多个权威页面。基于权威－－中心页面间相互指向的链接关系，HITS算法通过计算子图（由查询得到的子图经过扩充而成）对应的某个特殊矩阵的主特征向量来发现隐藏在中的全部由权威－－中心页面构成的网络簇结构。该算法与Google的PageRank算法齐名，被包括Altavista在内的多个搜索引擎所采用。341.目前，绝大多数算法不考虑重叠网络簇结构。但在许多应用中，重叠网络簇结构更具有实际意义。如在语义网中，多义词允许同时出现在多个表示不同词义的网络簇中.2005年，帕拉(G.Palla)等在《Nature》上发表文章，首次提出了能识别重叠网络簇结构的CPM算法.2.CPM简介CPM的基本假设网络簇由多个相邻的k-团(k-clique)组成，两个相邻的k-团至少共享k-1个节点，每个k-团唯一的属于某个网络簇，但属于不同网络簇的k-团可能会共享某些节点。CPM的缺点1)实际应用中参数k难以确定，选取不同的k值会得到不同的网络簇结构。2)计算网络中的全部k-团非常耗时，CPM非常慢，其时间复杂性近似为指数阶。2.3.6CPM算法(Nature,2005)352.3.7FEC算法(TKDE,2007)1.符号网络(signednetwork)是指包含正、负两种关系的二维复杂网络，是对一般复杂网络描述能力的一种推广。符号网络广泛存在于社会、生物等多种复杂系统中。符号网络簇结构具有簇内正关系稠密、同时簇间负关系稠密的特点.2007年，我们针对符号网络聚类问题，提出了基于马尔科夫随机游走模型的启发式符号网络聚类算法FEC.2.FEC算法简介FEC的基本假设从任意给定的簇出发，网络中的Markov随机游走过程达到起始簇内节点的期望概率将大于达到起始簇外节点的期望概率。网络簇识别基于该启发规则，FEC先算出在给定时刻Markov随机游