复杂网络聚类算法研究课件

复杂网络聚类方法研究复杂网络聚类方法研究吉林大学知吉林大学知吉林大学知吉林大学知识识工程教研室工程教研室工程教研室工程教研室吉林大学吉林大学吉林大学吉林大学计计算机学院算机学院算机学院算机学院 1 1复杂网络聚类方法研究吉林大学知识工程教研室1目目 录录1.复杂网络聚类方法的研究背景及意义复杂网络聚类方法的研究背景及意义 2.复杂网络聚类方法的研究现状及分析复杂网络聚类方法的研究现状及分析 3.复杂网络聚类所面临的问题复杂网络聚类所面临的问题 4.我们的工作我们的工作 5.复杂网络复杂网络vs时空数据挖掘时空数据挖掘 2 2目 录1.复杂网络聚类方法的研究背景及意义 21.复杂网络聚类方法的研究背景及意义复杂网络聚类方法的研究背景及意义 现现实实世世界界中中的的诸诸多多系系统统都都以以网网络络形形式式存存在在，如如社社会会系系统统中中的的人人际际关关系系网网、科科学学家家协协作作网网和和流流行行病病传传播播网网，生生态态系系统统中中的的神神经经元元网网、基基因因调调控控网网和和蛋蛋白白质质交交互互网网，科科技技系系统统中中的的因因特特网网、万万维维网网、通通信信网网、交交通通网网等等。由由于于这这些些网网络络所所对对应应的的系系统统具具有有很很高高的的复复杂杂性性，因因此此被被统统称称为为“复杂网络复杂网络(complex network)”。3 31.复杂网络聚类方法的研究背景及意义 现实世界中的诸多系统都社会网络（社会网络（Social Networks）科学家协作网移动电话网络圣经对应的社会网络4 4社会网络（Social Networks）科学家协作网移动电生物网络（生物网络（Biological Networks）食物链网络新陈代谢系统网络新陈代谢系统网络蛋白质交互网络蛋白质交互网络5 5生物网络（Biological Networks）食物链网络科技网络（科技网络（Technological Networks）6 6科技网络（Technological Networks）6O(10O(101 1)O(10O(103 3)O(10O(108 8)复杂网络分析具有重要研究意义复杂网络分析具有重要研究意义复杂网络分析具有重要研究意义复杂网络分析具有重要研究意义对于小规模网络，我们可以对于小规模网络，我们可以通过肉眼观测其形态、特征，通过肉眼观测其形态、特征，但是对于但是对于(超超)大规模复杂网大规模复杂网络，我们将很难通过肉眼深络，我们将很难通过肉眼深入理解和预测网络的结构、入理解和预测网络的结构、行为和功能，需要借助各种行为和功能，需要借助各种复杂网络分析方法。复杂网络分析方法。7 7O(101)O(103)O(108)复杂1.复杂网络聚类方法的研究背景及意义复杂网络聚类方法的研究背景及意义 复复杂杂网网络络已已成成为为当当前前最最重重要要的的多多学学科科交交叉叉研研究究领领域域之之一一。小小世世界界性性、无无标标度度性性、网网络络模模体体和和网网络络簇簇结结构构是是迄迄今今为为止止发发现现的的最最普普遍遍和和最最重重要要的的复复杂杂网网络络拓扑结构属性。拓扑结构属性。8 81.复杂网络聚类方法的研究背景及意义 复杂网络已成为当前最重Small World(Nature 1998)小世界网络：小世界网络：具有具有较小较小的平均路的平均路径长度，同时具有径长度，同时具有较大较大的聚类系数。的聚类系数。平均长度：网络中任意两点间最短路径长度的平均值。平均长度：网络中任意两点间最短路径长度的平均值。聚类系数：节点的任意两个邻居节点仍互为邻居的平均概率聚类系数：节点的任意两个邻居节点仍互为邻居的平均概率9 9Small World(Nature 1998)小世界网络Scale-free network(Science 1999)无标度性：网络的度分布呈现出幂率分布（无标度性：网络的度分布呈现出幂率分布（power law），而），而不是随机网络的泊松分布：不是随机网络的泊松分布：P(K)K-a1010Scale-free network(Science 19Degree distributionPoisson distributionPower-law distribution1111Degree distributionPoisson disNetwork Motif(Science 1999)Network Motif：在统计意义上，网络中频繁出现的：在统计意义上，网络中频繁出现的子图模式。（某些子图在现实网络中出现的概率明显高子图模式。（某些子图在现实网络中出现的概率明显高于这些子图在随机网络中出现的概率）。于这些子图在随机网络中出现的概率）。1212Network Motif(Science 1999)NeNetwork Community Structure(Science 2002,Nature 2005,2007)网络簇结构网络簇结构（network community structure）具有具有同簇节点相互连接同簇节点相互连接密集密集、异簇节点相互连接、异簇节点相互连接稀疏稀疏的特点。的特点。1313Network Community Structure(S1.复杂网络聚类方法的研究背景及意义复杂网络聚类方法的研究背景及意义复复复复杂杂杂杂网网网网络络络络聚聚聚聚类类类类方方方方法法法法的的的的研研研研究究究究对对对对分分分分析析析析复复复复杂杂杂杂网网网网络络络络的的的的拓拓拓拓扑扑扑扑结结结结构构构构、理理理理解解解解复复复复杂杂杂杂网网网网络络络络的的的的功功功功能能能能、发发发发现现现现复复复复杂杂杂杂网网网网络络络络中中中中的的的的隐隐隐隐藏藏藏藏规规规规律律律律和和和和预预预预测测测测复复复复杂杂杂杂网网网网络络络络的的的的行为行为行为行为不仅有十分重要的理论意义，而且有广泛的应用前景。不仅有十分重要的理论意义，而且有广泛的应用前景。不仅有十分重要的理论意义，而且有广泛的应用前景。不仅有十分重要的理论意义，而且有广泛的应用前景。目目目目前前前前已已已已被被被被应应应应用用用用于于于于：恐恐恐恐怖怖怖怖组组组组织织织织识识识识别别别别与与与与组组组组织织织织结结结结构构构构管管管管理理理理等等等等社社社社会会会会网网网网络络络络分分分分析析析析，围围围围绕绕绕绕新新新新陈陈陈陈代代代代谢谢谢谢、蛋蛋蛋蛋白白白白质质质质交交交交互互互互、未未未未知知知知蛋蛋蛋蛋白白白白质质质质功功功功能能能能预预预预测测测测、基基基基因因因因调调调调控控控控和和和和主主主主控控控控基基基基因因因因识识识识别别别别等等等等问问问问题题题题的的的的多多多多种种种种生生生生物物物物网网网网络络络络分分分分析析析析，WebWeb社社社社区区区区挖挖挖挖掘掘掘掘与与与与WebWeb文文文文档档档档聚聚聚聚类类类类，搜搜搜搜索索索索引引引引擎擎擎擎，空空空空间间间间数数数数据据据据聚聚聚聚类类类类，图图图图像像像像分分分分割割割割 ，以及以及以及以及关系数据分析关系数据分析关系数据分析关系数据分析等众多领域。等众多领域。等众多领域。等众多领域。Nature 200514141.复杂网络聚类方法的研究背景及意义复杂网络聚类方法的研究对应用例子应用例子1 聚类分析聚类分析Gaussian similarity function（高斯相似度函数）:1515应用例子1 聚类分析Gaussian similarity应用例子应用例子应用例子应用例子2 2 社会网络、语义网络、生物网络分析社会网络、语义网络、生物网络分析社会网络、语义网络、生物网络分析社会网络、语义网络、生物网络分析(Nature 2005)科学家合作网：每个节点表示一个科学家，连接表示科学家之间的合作紧密程度。语义网络:每个节点表示一个英文单词，连接表示词在某个语境下共同出现的频率。1616应用例子2 社会网络、语义网络、生物网络分析(Natur聚类基因网络Nature 20031717聚类基因网络Nature 200317聚类新陈代谢网络 Nature 20051818聚类新陈代谢网络 Nature 200518聚类蛋白质网络(Nature 2005)（芽芽殖殖酵酵母母菌菌）的的蛋蛋白白质质交交互互网网络络1919聚类蛋白质网络(Nature 2005)（芽殖酵母菌）的蛋动态社会网络簇结构分析(Nature 2007)该研究结果发现了维持社会结构稳定性的两个基本原则：该研究结果发现了维持社会结构稳定性的两个基本原则：对于大规模社会机构，其成分的对于大规模社会机构，其成分的动态变化动态变化利于维护该机构的稳定性；利于维护该机构的稳定性；相反的，对于小规模机构，其成分的相反的，对于小规模机构，其成分的固定不变固定不变利于维护该机构的稳定性。利于维护该机构的稳定性。2020动态社会网络簇结构分析(Nature 2007)该研究结果基于网络簇结构分析的链接预测(Nature 2008)该研究提出了一种广义的随机网络模型该研究提出了一种广义的随机网络模型（相对于经典的（相对于经典的ER随机网络模型）：随机网络模型）：（1）具有更强的表达能力，既能刻画）具有更强的表达能力，既能刻画assortative网络又能刻画网络又能刻画disassortative网络；网络；（2）对于给定的网络，该模型能够精）对于给定的网络，该模型能够精确的预测出网络中的未知链接或缺失链确的预测出网络中的未知链接或缺失链接，并能剔除网络中存在的噪音链接。接，并能剔除网络中存在的噪音链接。2121基于网络簇结构分析的链接预测(Nature 2008)该研1.复杂网络聚类方法的研究背景及意义（续）复杂网络聚类方法的研究背景及意义（续）复复复复杂杂杂杂网网网网络络络络聚聚聚聚类类类类方方方方法法法法已已已已成成成成为为为为图图图图论论论论、复复复复杂杂杂杂网网网网络络络络、数数数数据据据据挖挖挖挖掘掘掘掘等等等等理理理理论论论论的的的的重重重重要要要要组组组组成成成成部部部部分分分分和和和和相相相相关关关关课课课课程程程程的的的的核核核核心心心心内内内内容容容容。如如如如康康康康奈奈奈奈尔尔尔尔大大大大学学学学计计计计算算算算机机机机系系系系开开开开设设设设了了了了The The Structure Structure of of Information Information NetworksNetworks 课课课课 程程程程，麻麻麻麻 省省省省 理理理理 工工工工 电电电电 子子子子 工工工工 程程程程 和和和和 计计计计 算算算算 机机机机 系系系系 开开开开 设设设设 了了了了Networks and DynamicsNetworks and Dynamics课程。课程。课程。课程。由由由由于于于于复复复复杂杂杂杂网网网网络络络络聚聚聚聚类类类类研研研研究究究究具具具具有有有有重重重重要要要要的的的的理理理理论论论论意意意意义义义义和和和和应应应应用用用用价价价价值值值值，它它它它不不不不仅仅仅仅成成成成为为为为计计计计算算算算机机机机领领领领域域域域中中中中最最最最具具具具挑挑挑挑战战战战性性性性的的的的基基基基础础础础性性性性研研研研究究究究课课课课题题题题之之之之一一一一，也也也也吸吸吸吸引引引引了了了了来来来来自自自自物物物物理理理理、数数数数学学学学、生生生生物物物物、社社社社会会会会学学学学和和和和复复复复杂杂杂杂性性性性科科科科学学学学等等等等众众众众多多多多领领领领域域域域的的的的研研研研究究究究者者者者，掀掀掀掀起起起起了了了了一一一一股股股股研研研研究究究究热热热热潮潮潮潮。从从从从20022002年年年年至至至至今今今今，新新新新的的的的方方方方法法法法层层层层出出出出不不不不穷穷穷穷，新新新新的的的的应应应应用用用用领领领领域域域域不不不不断断断断被被被被拓拓拓拓展展展展，不不同同领领域域的的权权威威国国际际杂杂志志和和多多个个重重要要国国际际学学术术会会议议多多次次报报道道这这方面的研究工作。方面的研究工作。22221.复杂网络聚类方法的研究背景及意义（续）复杂网络聚类方法已2.复杂网络聚类方法的研究现状及分析复杂网络聚类方法的研究现状及分析 n n2.1 2.1 复杂网络聚类方法的分类复杂网络聚类方法的分类复杂网络聚类方法的分类复杂网络聚类方法的分类n n2.2 2.2 基于优化的复杂网络聚类算法基于优化的复杂网络聚类算法基于优化的复杂网络聚类算法基于优化的复杂网络聚类算法n n2.3 2.3 启发式复杂网络聚类算法启发式复杂网络聚类算法启发式复杂网络聚类算法启发式复杂网络聚类算法n n2.4 2.4 其它网络聚类算法其它网络聚类算法其它网络聚类算法其它网络聚类算法 23232.复杂网络聚类方法的研究现状及分析 2.1 复杂网络聚类方2.1 复杂网络聚类方法的分类复杂网络聚类方法的分类 基基于于优优化化的的方方法法将复杂网络聚类问题转化为优化问题，通通过过最最优优化化预预定定义义的的目目标标函函数来计算复杂网络的簇结构。数来计算复杂网络的簇结构。启启发发式式方方法法将复杂网络聚类问题转化为预定义启发式规则的设计问题。除除以以上上两两类类方方法法之之外外，还还存存在在其其它它类类型型的复杂网络聚类方法的复杂网络聚类方法。24242.1 复杂网络聚类方法的分类242.1 复杂网络聚类方法的分类复杂网络聚类方法的分类25252.1 复杂网络聚类方法的分类252.2 基于优化的复杂网络聚类方法基于优化的复杂网络聚类方法2.2.1 2.2.1 谱方法谱方法 2.2.2 2.2.2 基于局部搜索的复杂网络聚类方法基于局部搜索的复杂网络聚类方法2.2.3 2.2.3 其其它它基基于于优优化化方方法法的的复复杂杂网网络络聚聚类类方法方法26262.2 基于优化的复杂网络聚类方法2.2.1 谱方法 262.2.1 2.2.1 谱方法（谱方法（Spectral MethodSpectral Method）n n谱谱谱谱方方方方法法法法采采采采用用用用二二二二次次次次型型型型优优优优化化化化技技技技术术术术最最最最小小小小化化化化预预预预定定定定义义义义的的的的“截截截截函函函函数数数数”。当当当当一一一一个个个个网网网网络络络络被被被被划划划划分分分分成成成成两两两两个个个个子子子子网网网网络络络络时时时时，“截截截截”指指指指子子子子网网网网间间间间的的的的连连连连接密度。具有最小接密度。具有最小接密度。具有最小接密度。具有最小“截截截截”的划分被认为是最优的网络划分。的划分被认为是最优的网络划分。的划分被认为是最优的网络划分。的划分被认为是最优的网络划分。n n谱谱谱谱方方方方法法法法具具具具有有有有严严严严密密密密的的的的数数数数学学学学理理理理论论论论，已已已已发发发发展展展展成成成成数数数数据据据据聚聚聚聚类类类类的的的的一一一一种种种种重重重重要要要要方方方方法法法法(称称称称为为为为谱谱谱谱聚聚聚聚类类类类法法法法)，被被被被广广广广泛泛泛泛应应应应用用用用于于于于图图图图分分分分割割割割和和和和空空空空间间间间点点点点聚聚聚聚类等领域。类等领域。类等领域。类等领域。n n针对复杂网络聚类，谱方法的针对复杂网络聚类，谱方法的针对复杂网络聚类，谱方法的针对复杂网络聚类，谱方法的主要不足主要不足主要不足主要不足是：是：是：是：1 1）需要借助先验知识定义递归终止条件，即谱方法不具）需要借助先验知识定义递归终止条件，即谱方法不具）需要借助先验知识定义递归终止条件，即谱方法不具）需要借助先验知识定义递归终止条件，即谱方法不具备自动识别网络簇总数的能力；备自动识别网络簇总数的能力；备自动识别网络簇总数的能力；备自动识别网络簇总数的能力；2 2）现实世界中的复杂网络往往包含多个网络簇，而谱方）现实世界中的复杂网络往往包含多个网络簇，而谱方）现实世界中的复杂网络往往包含多个网络簇，而谱方）现实世界中的复杂网络往往包含多个网络簇，而谱方法的递归二分策略不能保证得到网络划分是最优的多网络法的递归二分策略不能保证得到网络划分是最优的多网络法的递归二分策略不能保证得到网络划分是最优的多网络法的递归二分策略不能保证得到网络划分是最优的多网络簇结构。簇结构。簇结构。簇结构。27272.2.1 谱方法（Spectral Method）谱方法1.19701970年年年年，针针针针 对对对对 图图图图 分分分分 割割割割 问问问问 题题题题 克克克克 宁宁宁宁 汉汉汉汉 林林林林(B.W.B.W.KernighanKernighan和和和和S.S.LinLin)提提提提出出出出了了了了 KL KL 算算算算法法法法 ，该该该该算算算算法法法法也也也也可可可可用于复杂网络聚类。用于复杂网络聚类。用于复杂网络聚类。用于复杂网络聚类。2.KLKL算法简介算法简介算法简介算法简介KLKL的优化目标是的优化目标是的优化目标是的优化目标是：极小化簇间连接数目与簇内连接数目之差的极小化簇间连接数目与簇内连接数目之差的极小化簇间连接数目与簇内连接数目之差的极小化簇间连接数目与簇内连接数目之差的绝对值绝对值绝对值绝对值 ；KL KL算法的不足：算法的不足：算法的不足：算法的不足：找到的解往往是找到的解往往是找到的解往往是找到的解往往是局部最优局部最优局部最优局部最优而不是全局最优解。而不是全局最优解。而不是全局最优解。而不是全局最优解。KL KL 对初始解非常敏感对初始解非常敏感对初始解非常敏感对初始解非常敏感，它，它，它，它需要先验知识。需要先验知识。需要先验知识。需要先验知识。KLKL算法的时间复杂性算法的时间复杂性算法的时间复杂性算法的时间复杂性:O(O(tntn2 2)，t t 表示算法终止时的迭代次数，表示算法终止时的迭代次数，表示算法终止时的迭代次数，表示算法终止时的迭代次数，n n表示网络表示网络表示网络表示网络节点个数节点个数节点个数节点个数。Kernighan-LinKernighan-Lin算法算法算法算法(Bell System Technical Journal,1970)28281970年，针对图分割问题克宁汉林(B.W.Kernig1.20042004年年年年，纽纽纽纽曼曼曼曼(M.E.J.M.E.J.NewmanNewman)提提提提出出出出了了了了基基基基于于于于局局局局部部部部搜索的快速复杂网络聚类算法搜索的快速复杂网络聚类算法搜索的快速复杂网络聚类算法搜索的快速复杂网络聚类算法FN.FN.2.算法算法FNFN简介简介 FNFN的优化目标：的优化目标：极大化纽曼与格万极大化纽曼与格万极大化纽曼与格万极大化纽曼与格万(M.E.J.M.E.J.NewmanNewman和和和和M.GirvanM.Girvan)于同年提出的网络模块性于同年提出的网络模块性于同年提出的网络模块性于同年提出的网络模块性评价函数评价函数评价函数评价函数：Q Q函数函数函数函数.Q Q 函数函数函数函数定义为簇内的实际连定义为簇内的实际连定义为簇内的实际连定义为簇内的实际连接数目与随机连接下簇内的期望连接数目之差，接数目与随机连接下簇内的期望连接数目之差，接数目与随机连接下簇内的期望连接数目之差，接数目与随机连接下簇内的期望连接数目之差，用来定量地刻画网络簇结构的优劣用来定量地刻画网络簇结构的优劣用来定量地刻画网络簇结构的优劣用来定量地刻画网络簇结构的优劣.Q Q值越大则网值越大则网值越大则网值越大则网络簇结构越好。络簇结构越好。络簇结构越好。络簇结构越好。FNFN算法的时间复杂性算法的时间复杂性:是是是是O(O(mm n n)，mm和和和和n n分别表示网络的连接数和节点分别表示网络的连接数和节点分别表示网络的连接数和节点分别表示网络的连接数和节点数数数数 快速快速快速快速NewmanNewman算法算法算法算法(Physical Rev.EPhysical Rev.E,2004,2004)29292004年，纽曼(M.E.J.Newman)提出了基于局部1.20052005年年，吉吉莫莫热热与与阿阿麦麦拉拉尔尔(R.(R.GuimeraGuimera和和L.A.N.L.A.N.Amaral)Amaral)采采用用与与算算法法FNFN相相同同的的优优化化目目标标函函数数，提提出出了了基基于于模模拟拟退退火火算算法法(SA)(SA)的的复复杂杂网网络络聚聚类类算算法法GAGA，并并应应用用到到新新陈陈代代谢谢网网络络分分析析中中。NatureNature20052005年年2 2月刊报道了该项研究工作。月刊报道了该项研究工作。2.算法算法GAGA的优缺点的优缺点 GA GA采用模拟退火控制策略，因此采用模拟退火控制策略，因此GAGA具有跳过局具有跳过局部部最优最优解、找到全局最优解的能力，因而具有很好解、找到全局最优解的能力，因而具有很好的聚类精度。的聚类精度。GAGA的的效效率率取取决决于于算算法法SASA的的效效率率，而而后后者者通通常常收敛很缓慢。收敛很缓慢。GAGA对对输输入入参参数数非非常常敏敏感感，不不同同的的参参数数设设置置往往往往导致不同的聚类结果。导致不同的聚类结果。Guimera-AmaralGuimera-Amaral算法算法(NatureNature,2005),2005)30302005年，吉莫热与阿麦拉尔(R.Guimera和L.An n启发式复杂网络聚类算法的启发式复杂网络聚类算法的启发式复杂网络聚类算法的启发式复杂网络聚类算法的共同特点共同特点共同特点共同特点是：是：是：是：基于某些基于某些基于某些基于某些直观假设直观假设直观假设直观假设来设计启发式算法，对来设计启发式算法，对来设计启发式算法，对来设计启发式算法，对大部分网络来大部分网络来大部分网络来大部分网络来说说说说，它们能快速找到最优解或近似最优解，但，它们能快速找到最优解或近似最优解，但，它们能快速找到最优解或近似最优解，但，它们能快速找到最优解或近似最优解，但无法从理无法从理无法从理无法从理论上严格保证论上严格保证论上严格保证论上严格保证它们对任何输入网络都能在令人满意的时它们对任何输入网络都能在令人满意的时它们对任何输入网络都能在令人满意的时它们对任何输入网络都能在令人满意的时间内找到令人满意的解。间内找到令人满意的解。间内找到令人满意的解。间内找到令人满意的解。n n本报告介绍几个典型的启发式复杂网络聚类算法：本报告介绍几个典型的启发式复杂网络聚类算法：本报告介绍几个典型的启发式复杂网络聚类算法：本报告介绍几个典型的启发式复杂网络聚类算法：算法算法算法算法 GN GN(Girvan-NewmanGirvan-Newman)算法算法算法算法 HITS HITS(Hyperlink Induced Topic SearchHyperlink Induced Topic Search)算法算法算法算法 CPM(Clique Percolation Method)CPM(Clique Percolation Method)算法算法算法算法 FEC(Finding and Extracting Communities)FEC(Finding and Extracting Communities)2.3 启发式复杂网络聚类方法启发式复杂网络聚类方法3131启发式复杂网络聚类算法的共同特点是：基于某些直观假设来设计2.3.2 GN2.3.2 GN算法算法(PNAS,2002)(PNAS,2002)2002年年，格格万万和和纽纽曼曼(M.Girvan和和M.E.J.Newman)提提出出了了基基于于反反复识别和删除簇间连接策略的复杂网络聚类复识别和删除簇间连接策略的复杂网络聚类算法算法GN.n GN算法算法的缺点的缺点 GN的最大缺点是计算速度慢，边介数计算的开销过大的最大缺点是计算速度慢，边介数计算的开销过大O(m n)，GN具有很高的时间复杂性具有很高的时间复杂性O(m2n)，只适合处理中小，只适合处理中小规模的网络规模的网络(包含几百个节点的网络包含几百个节点的网络)。n GN算法算法的意义的意义 在复杂网络聚类研究中，在复杂网络聚类研究中，GN算法占有十分重要的地位（该算法占有十分重要的地位（该文被引用超过文被引用超过1000次），格万和纽曼工作的重要意义在于：他次），格万和纽曼工作的重要意义在于：他们首次发现了复杂网络中普遍存在的们首次发现了复杂网络中普遍存在的网络簇结构网络簇结构，启发了其他，启发了其他研究者对这个问题的深入研究，掀起了复杂网络聚类的研究热研究者对这个问题的深入研究，掀起了复杂网络聚类的研究热潮潮。32322.3.2 GN算法(PNAS,2002)20022.3.4 HITS 2.3.4 HITS 算法算法算法算法(Journal of ACM,1999Journal of ACM,1999)1999 1999年，针对年，针对年，针对年，针对基于链接的网页排名问题基于链接的网页排名问题基于链接的网页排名问题基于链接的网页排名问题，克莱因博格，克莱因博格，克莱因博格，克莱因博格(KleinbergKleinberg)等人等人等人等人提出了著名的提出了著名的提出了著名的提出了著名的HITSHITS算法算法算法算法，该算法也可用于基于内容的网页聚类。，该算法也可用于基于内容的网页聚类。，该算法也可用于基于内容的网页聚类。，该算法也可用于基于内容的网页聚类。n n HITS HITS算法基于的算法基于的算法基于的算法基于的基本假设基本假设基本假设基本假设 根据链接关系，根据链接关系，根据链接关系，根据链接关系，WWWWWW中存在中存在中存在中存在权威权威权威权威(authority)(authority)和中心和中心和中心和中心(hub)(hub)两种基本类两种基本类两种基本类两种基本类型型型型 的页面，的页面，的页面，的页面，权威页面权威页面权威页面权威页面倾向于被多个倾向于被多个倾向于被多个倾向于被多个中心页面中心页面中心页面中心页面引用，而引用，而引用，而引用，而中心页面中心页面中心页面中心页面倾向于引用倾向于引用倾向于引用倾向于引用 多个多个多个多个权威页面权威页面权威页面权威页面。n n 基于权威中心页面间基于权威中心页面间基于权威中心页面间基于权威中心页面间相互指向相互指向相互指向相互指向的链接关系，的链接关系，的链接关系，的链接关系，HITSHITS算法通过计算算法通过计算算法通过计算算法通过计算 WWW WWW子图（由查询得到的子图经过扩充而成）对应的某个特殊矩阵子图（由查询得到的子图经过扩充而成）对应的某个特殊矩阵子图（由查询得到的子图经过扩充而成）对应的某个特殊矩阵子图（由查询得到的子图经过扩充而成）对应的某个特殊矩阵 的的的的主特征向量主特征向量主特征向量主特征向量来发现隐藏在来发现隐藏在来发现隐藏在来发现隐藏在WWWWWW中的全部由权威中心页面构成中的全部由权威中心页面构成中的全部由权威中心页面构成中的全部由权威中心页面构成 的网络簇结构。的网络簇结构。的网络簇结构。的网络簇结构。n n 该算法与该算法与该算法与该算法与GoogleGoogle的的的的PageRankPageRank算法齐名，被包括算法齐名，被包括算法齐名，被包括算法齐名，被包括AltavistaAltavista在内的多个在内的多个在内的多个在内的多个搜搜搜搜 索引擎索引擎索引擎索引擎所采用。所采用。所采用。所采用。33332.3.4 HITS 算法(Journal of AC1.目前，绝大多数算法不考虑目前，绝大多数算法不考虑重叠网络簇结构重叠网络簇结构。但在许多应用中，。但在许多应用中，重叠网络簇结构更具有实际意义。如在语义网中，多义词允许同时重叠网络簇结构更具有实际意义。如在语义网中，多义词允许同时出现在多个表示不同词义的网络簇出现在多个表示不同词义的网络簇 中中.2005年，帕拉年，帕拉(G.Palla)等等在在Nature上发表文章，首次提出了能上发表文章，首次提出了能识别重叠网络簇结构的识别重叠网络簇结构的CPM算法算法.2.CPM简介简介n CPM的的基本假设基本假设 网络簇由网络簇由多个多个相邻的相邻的k-团团(k-clique)组成，两个组成，两个相邻的相邻的k-团团至少至少共享共享k-1个节点个节点，每个，每个k-团团唯一的唯一的属于某个网络簇，但属于某个网络簇，但属于不同网属于不同网络簇的络簇的k-团团可能会共享某些节点。可能会共享某些节点。nCPM的的缺点缺点 1)实际应用中实际应用中参数参数k难以确定难以确定，选取不同的，选取不同的k值会得到不同的网络值会得到不同的网络簇结构。簇结构。2)计算网络中的全部计算网络中的全部k-团团非常耗时非常耗时，CPM非常慢，其时间复杂非常慢，其时间复杂性近似为性近似为指数阶指数阶。2.3.6 CPM 2.3.6 CPM 算法算法算法算法(Nature,2005)(Nature,2005)3434 目前，绝大多数算法不考虑重叠网络簇结构。但在许多应用中，重2.3.7 FEC2.3.7 FEC算法算法(TKDE,2007)(TKDE,2007)1.1.符符符符号号号号网网网网络络络络(signed(signed network)network)是是是是指指指指包包包包含含含含正正正正、负负负负两两两两种种种种关关关关系系系系的的的的二二二二维维维维复复复复杂杂杂杂网网网网络络络络，是是是是对对对对一一一一般般般般复复复复杂杂杂杂网网网网络络络络描描描描述述述述能能能能力力力力的的的的一一一一种种种种推推推推广广广广。符符符符号号号号网网网网络络络络广广广广泛泛泛泛存存存存在在在在于于于于社社社社会会会会、生生生生物物物物等等等等多多多多种种种种复复复复杂杂杂杂系系系系统统统统中中中中。符符符符号号号号网网网网络络络络簇簇簇簇结结结结构构构构具具具具有有有有簇簇簇簇内内内内正正正正关关关关系系系系稠稠稠稠密密密密、同同同同时时时时簇簇簇簇间间间间负负负负关关关关系系系系稠稠稠稠密密密密的的的的特特特特点点点点.20072007年年年年，我我我我们们们们针针针针对对对对符符符符号号号号网网网网络络络络聚聚聚聚类类类类问问问问题题题题，提提提提出出出出了了了了基基基基于于于于马马马马尔尔尔尔科科科科夫夫夫夫随随随随机机机机游游游游走走走走模模模模型型型型的的的的启启启启发发发发式式式式符符符符号号号号网网网网络络络络聚聚聚聚类类类类算算算算法法法法FEC FEC.2.2.FECFEC算法简介算法简介算法简介算法简介n nFECFEC的的的的基本假设基本假设基本假设基本假设从任意给定的簇出发，网络中的从任意给定的簇出发，网络中的从任意给定的簇出发，网络中的从任意给定的簇出发，网络中的MarkovMarkov随机游走过程达到起始簇内节点的期望概率将随机游走过程达到起始簇内节点的期望概率将随机游走过程达到起始簇内节点的期望概率将随机游走过程达到起始簇内节点的期望概率将大于大于大于大于达到起始簇外节点的期望概率。达到起始簇外节点的期望概率。达到起始簇外节点的期望概率。达到起始簇外节点的期望概率。n n网络簇识别网络簇识别网络簇识别网络簇识别基于该启发规则，基于该启发规则，基于该启发规则，基于该启发规则，FECFEC先算出在给定时刻先算出在给定时刻先算出在给定时刻先算出在给定时刻MarkovMarkov随机游走过程到达所有节点的随机游走过程到达所有节点的随机游走过程到达所有节点的随机游走过程到达所有节点的期望转期望转期望转期望转移概率分布移概率分布移概率分布移概率分布，进而根据该分布的，进而根据该分布的，进而根据该分布的，进而根据该分布的局部一致性局部一致性局部一致性局部一致性(同簇节点具有近似相同的期望转移概率分同簇节点具有近似相同的期望转移概率分同簇节点具有近似相同的期望转移概率分同簇节点具有近似相同的期望转移概率分布布布布)识别出所有的网络簇。识别出所有的网络簇。识别出所有的网络簇。识别出所有的网络簇。n nFECFEC算法之优缺点算法之优缺点算法之优缺点算法之优缺点1)1)是第一个是第一个是第一个是第一个综合考虑两种分簇标准综合考虑两种分簇标准综合考虑两种分簇标准综合考虑两种分簇标准(连接密度和连接符号连接密度和连接符号连接密度和连接符号连接密度和连接符号)的复杂网络聚类算法。的复杂网络聚类算法。的复杂网络聚类算法。的复杂网络聚类算法。2)FEC 2)FEC在在在在效率和识别精度都效率和识别精度都效率和识别精度都效率和识别精度都表现了更好的性能，尤其适于处理噪声高和网络簇结构不表现了更好的性能，尤其适于处理噪声高和网络簇结构不表现了更好的性能，尤其适于处理噪声高和网络簇结构不表现了更好的性能，尤其适于处理噪声高和网络簇结构不明显的复杂网络。明显的复杂网络。明显的复杂网络。明显的复杂网络。3 3）随随随随机机机机游游游游走走走走的的的的步步步步长长长长会会会会影影影影响响响响算算算算法法法法的的的的聚聚聚聚类类类类结结结结果果果果，尽尽尽尽管管管管实实实实验验验验表表表表明明明明对对对对某某某某些些些些网网网网络络络络，聚聚聚聚类类类类结结结结果果果果对对对对该该该该参数并不敏感，但如何针对不同网络计算出最优步长仍是一个未被解决的理论问题。参数并不敏感，但如何针对不同网络计算出最优步长仍是一个未被解决的理论问题。参数并不敏感，但如何针对不同网络计算出最优步长仍是一个未被解决的理论问题。参数并不敏感，但如何针对不同网络计算出最优步长仍是一个未被解决的理论问题。35352.3.7 FEC算法(TKDE,2007)符号网络(3 复杂网络聚类所面临的问题复杂网络聚类所面临的问题 第第一一，我我们们还还没没有有从从客客观观上上认认清清网网络络簇簇结结构构的的本本质质含义含义。1.1.网络簇结构是网络簇结构是怎么形成的怎么形成的？2.2.它与网络的其它复杂现象它与网络的其它复杂现象有什么必然联系有什么必然联系？3.3.它与网络自身的它与网络自身的哪些内在属性有关哪些内在属性有关？因此，现阶段我们不得不通过观察有簇网络所展示因此，现阶段我们不得不通过观察有簇网络所展示出的出的“外在外在”现象现象去理解网络簇概念，借助去理解网络簇概念，借助“主观主观”定义的目标函数定义的目标函数或或启发式规则启发式规则去去刻画和计算刻画和计算网络网络簇结构。簇结构。能否从网络的能否从网络的“内在内在”属性属性出发，给出一种出发，给出一种“客观客观”的理论模型去理解、刻画和计算复杂网络簇结构。的理论模型去理解、刻画和计算复杂网络簇结构。36363 复杂网络聚类所面临的问题 第一，我们还没有从客观上认清网3 复杂网络聚类所面临的问题第第二二，不不能能同同时时满满足足计计算算速速度度快快、聚聚类类精精度度高高（即即抗抗噪噪声声能能力力强强）、免免参参数数（即即不不依依赖赖先先验验知知识、对参数不敏感）等基本要求。识、对参数不敏感）等基本要求。识识别别精精度度高高的的方方法法往往往往具具有有很很高高时时间间复复杂杂性性(O(n2)，而而快快速速的的识识别别方方法法往往往往以以牺牺牲牲精精度度为为代代价价并且需要较多的并且需要较多的参数和先验知识参数和先验知识。如如何何设设计计出出快快速速、高高精精度度和和免免参参数数的的复复杂杂网网络络聚聚类方法仍是当前最期待解决的问题之一。类方法仍是当前最期待解决的问题之一。37373 复杂网络聚类所面临的问题第二，不能同时满足计算速度快、聚3 复杂网络聚类所面临的问题第第第第三三三三，除除除除以以以以上上上上未未未未解解解解决决决决的的的的理理理理论论论论问问问问题题题题之之之之外外外外，随随随随着着着着应应应应用用用用领领领领域域域域的的的的拓拓拓拓展展展展、网网网网络络络络聚聚聚聚类类类类问问问问题题题题的的的的多多多多样样样样化化化化，现现现现有有有有复复复复杂杂杂杂网网网网络络络络聚聚聚聚类类类类方方方方法法法法已已已已难难难难以以以以胜胜胜胜任任任任，需需需需要要要要针针针针对对对对特特特特殊殊殊殊类类类类型型型型的的的的复复复复杂杂杂杂网网网网络络络络研研研研究究究究新新新新型型型型的的的的复复复复杂杂杂杂网网网网络聚类方法。络聚类方法。络聚类方法。络聚类方法。（1 1）动态复杂网络聚类方法）动态复杂网络聚类方法）动态复杂网络聚类方法）动态复杂网络聚类方法 （2 2）高维复杂网络聚类方法）高维复杂网络聚类方法）高维复杂网络聚类方法）高维复杂网络聚类方法 （3 3）分布式复杂网络聚类方法）分布式复杂网络聚类方法）分布式复杂网络聚类方法）分布式复杂网络聚类方法以以以以上上上上类类类类型型型型的的的的复复复复杂杂杂杂网网网网络络络络聚聚聚聚类类类类方方方方法法法法具具具具有有有有广广广广泛泛泛泛的的的的应应应应用用用用领领领领域域域域，因因因因此此此此如如如如何何何何针针针针对对对对特特特特殊殊殊殊类类类类型型型型的的的的复复复复杂杂杂杂网网网网络络络络设设设设计计计计出出出出新新新新型型型型的的的的复复复复杂杂杂杂网网网网络络络络聚聚聚聚类类类类方法也是当前面临的主要问题之一。方法也是当前面临的主要问题之一。方法也是当前面临的主要问题之一。方法也是当前面临的主要问题之一。38383 复杂网络聚类所面临的问题第三，除以上未解决的理论问题之外4.4.前期的一些工作前期的一些工作前期的一些工作前期的一些工作 Detect communities from decentralized networksB Yang,J Liu,D Liu.An autonomy-oriented computing approach to community mining in distributed and dynamic networks.Autonomous Agents and Multi-Agent Systems(JAAMAS),2010.Detect web communitiesB Yang,J Liu.Discovering Global Network Communities Based on Local Centralities.ACM Transactions on the Web(TWEB),2008.Detect communities from signed networksB Yang,WK Cheung,J Liu.Community Mining from Signed Social Networks.IEEE Transactions on Knowledge and Data Engineering(TKDE),2007.Detect communities from dynamic networksB Yang,D Liu.Force-based Incremental Algorithm for Mining Community Structure in Dynamic Network.Journal of Computer Science and Technology(JCST),2006.39394.前期的一些工作 Detect communities 正在开展的一些工作正在开展的一些工作正在开展的一些工作正在开展的一些工作 Spectral analysis for community structures NSFC project(2009-2011)&NLPR Open Project(2009-2010)Novel spectral model and method Spectral analysis for directed networks Spectral analysis for assortative/disassortative networks Statistical relational learning for graph mining NSFC project(2010-2012)Combine inference and learning for networked data Link prediction Collective classification4040 正在开展的一些工作 Spectral analysis f时空数据挖掘n n随着随着GPS、RS和和GIS 等技术的应用和发展，等技术的应用和发展，使时空数据的膨胀速度远远超出了常规的事使时空数据的膨胀速度远远超出了常规的事务型数据，务型数据，“数据爆炸但知识贫乏数据爆炸但知识贫乏”的现象的现象在时空数据中尤为严重。在时空数据中尤为严重。Geo-spatial dataBiomedical DataClimate DataSensor Networks 4141时空数据挖掘随着GPS、RS和GIS 等技术的应用和发展，使特点和应用n n除了具有海量、高维、高噪声和非线性等一般数除了具有海量、高维、高噪声和非线性等一般数除了具有海量、高维、高噪声和非线性等一般数除了具有海量、高维、高噪声和非线性等一般数据特征外，时空数据还包含了拓扑、距离、尺度、据特征外，时空数据还包含了拓扑、距离、尺度、据特征外，时空数据还包含了拓扑、距离、尺度、据特征外，时空数据还包含了拓扑、距离、尺度、形状和时间等多种特殊信息，并按复杂的多维空形状和时间等多种特殊信息，并按复杂的多维空形状和时间等多种特殊信息，并按复杂的多维空形状和时间等多种特殊信息，并按复杂的多维空间索引结构进行组织，在数据分析过程中还需借间索引结构进行组织，在数据分析过程中还需借间索引结构进行组织，在数据分析过程中还需借间索引结构进行组织，在数据分析过程中还需借助助助助空间推理、拓扑分析、几何计算和时空语义分空间推理、拓扑分析、几何计算和时空语义分空间推理、拓扑分析、几何计算和时空语义分空间推理、拓扑分析、几何计算和时空语义分析析析析等方法。等方法。等方法。等方法。n n时空数据挖掘方法对于有效处理海量时空数据、时空数据挖掘方法对于有效处理海量时空数据、时空数据挖掘方法对于有效处理海量时空数据、时空数据挖掘方法对于有效处理海量时空数据、提高时空数据分析的自动化和智能化水平具有重提高时空数据分析的自动化和智能化水平具有重提高时空数据分析的自动化和智能化水平具有重提高时空数据分析的自动化和智能化水平具有重要意义，在要意义，在要意义，在要意义，在遥感、遥感、遥感、遥感、GISGIS、实时导航、决策支持、实时导航、决策支持、实时导航、决策支持、实时导航、决策支持、交通控制、环境监测、医疗图像处理、案件侦破、交通控制、环境监测、医疗图像处理、案件侦破、交通控制、环境监测、医疗图像处理、案件侦破、交通控制、环境监测、医疗图像处理、案件侦破、道路交通、机器人等道路交通、机器人等道路交通、机器人等道路交通、机器人等许多涉及时空数据的领域中许多涉及时空数据的领域中许多涉及时空数据的领域中许多涉及时空数据的领域中都有广泛应用。都有广泛应用。都有广泛应用。都有广泛应用。4242特点和应用除了具有海量、高维、高噪声和非线性等一般数据特征外应用成果n nSKICATSKICAT系统已经发现了系统已经发现了系统已经发现了系统已经发现了16 16 个新的极其遥远的个新的极其遥远的个新的极其遥远的个新的极其遥远的类星体；类星体；类星体；类星体；n nPOSSPOSS系统将天空图像中的星体对象分类准确性系统将天空图像中的星体对象分类准确性系统将天空图像中的星体对象分类准确性系统将天空图像中的星体对象分类准确性从从从从75%75%提高到提高到提高到提高到94%94%；n nMagellanStudyMagellanStudy系统通过分析启明星表面的大系统通过分析启明星表面的大系统通过分析启明星表面的大系统通过分析启明星表面的大约约约约30000 30000 幅高分辨率雷达图像，识别了火山；幅高分辨率雷达图像，识别了火山；幅高分辨率雷达图像，识别了火山；幅高分辨率雷达图像，识别了火山；n nCONQUESTCONQUEST系统基于内容的空间和时间查询，系统基于内容的空间和时间查询，系统基于内容的空间和时间查询，系统基于内容的空间和时间查询，发现了大气层中臭氧洞形成的样本知识。发现了大气层中臭氧洞形成的样本知识。发现了大气层中臭氧洞形成的样本知识。发现了大气层中臭氧洞形成的样本知识。4343应用成果SKICAT系统已经发现了16 个新的极其遥远的类星时空数据挖掘vs复杂网络n n 1.1.时空数据网时空数据网时空数据网时空数据网 随着时空数据的日益积累，时空数据已经形成一个以时空随着时空数据的日益积累，时空数据已经形成一个以时空随着时空数据的日益积累，时空数据已经形成一个以时空随着时空数据的日益积累，时空数据已经形成一个以时空数据实体为节点，时空数据实体与实体之间的关联关系为数据实体为节点，时空数据实体与实体之间的关联关系为数据实体为节点，时空数据实体与实体之间的关联关系为数据实体为节点，时空数据实体与实体之间的关联关系为边的边的边的边的复杂网络复杂网络复杂网络复杂网络，并以其自身的规律进行演化和发展。研究，并以其自身的规律进行演化和发展。研究，并以其自身的规律进行演化和发展。研究，并以其自身的规律进行演化和发展。研究时空数据网络自身的演化规律，建立时空数据网络的预测时空数据网络自身的演化规律，建立时空数据网络的预测时空数据网络自身的演化规律，建立时空数据网络的预测时空数据网络自身的演化规律，建立时空数据网络的预测模型，有利于时空数据挖掘。为了分析时空数据网络，可模型，有利于时空数据挖掘。为了分析时空数据网络，可模型，有利于时空数据挖掘。为了分析时空数据网络，可模型，有利于时空数据挖掘。为了分析时空数据网络，可以将一些相关的以将一些相关的以将一些相关的以将一些相关的复杂网络模型复杂网络模型复杂网络模型复杂网络模型引入到时空数据网络当中。引入到时空数据网络当中。引入到时空数据网络当中。引入到时空数据网络当中。n n2.2.特征空间特征空间特征空间特征空间vsvs相似度空间相似度空间相似度空间相似度空间 “高维高维高维高维”是基于特征空间数据挖掘方法所面临的主要困难。是基于特征空间数据挖掘方法所面临的主要困难。是基于特征空间数据挖掘方法所面临的主要困难。是基于特征空间数据挖掘方法所面临的主要困难。基于相似度空间的复杂网络分析是一个很有前景的基于相似度空间的复杂网络分析是一个很有前景的基于相似度空间的复杂网络分析是一个很有前景的基于相似度空间的复杂网络分析是一个很有前景的“高维高维高维高维”数据分析方法。将数据分析方法。将数据分析方法。将数据分析方法。将特征空间变换为等价的相似度空间特征空间变换为等价的相似度空间特征空间变换为等价的相似度空间特征空间变换为等价的相似度空间后，后，后，后，高维时空数据挖掘问题就转换为复杂网络分析问题。复杂高维时空数据挖掘问题就转换为复杂网络分析问题。复杂高维时空数据挖掘问题就转换为复杂网络分析问题。复杂高维时空数据挖掘问题就转换为复杂网络分析问题。复杂网络聚类是最主要的复杂网络分析方法之一，可用于网络聚类是最主要的复杂网络分析方法之一，可用于网络聚类是最主要的复杂网络分析方法之一，可用于网络聚类是最主要的复杂网络分析方法之一，可用于空间空间空间空间数据聚类和空间模式识别数据聚类和空间模式识别数据聚类和空间模式识别数据聚类和空间模式识别等多种空间数据分析。等多种空间数据分析。等多种空间数据分析。等多种空间数据分析。n n3.3.探索其它结合点探索其它结合点探索其它结合点探索其它结合点?4444时空数据挖掘vs复杂网络44n nShiShi等提出等提出等提出等提出规范谱方法规范谱方法规范谱方法规范谱方法，有效地解决了图像分割和多维空间模式识，有效地解决了图像分割和多维空间模式识，有效地解决了图像分割和多维空间模式识，有效地解决了图像分割和多维空间模式识别问题，该方法成为谱图分析的主要方法，并被广泛引用别问题，该方法成为谱图分析的主要方法，并