复杂网络聚类算法研究

《复杂网络聚类算法研究》由会员分享，可在线阅读，更多相关《复杂网络聚类算法研究（46页珍藏版）》请在金锄头文库上搜索。

1、复杂网络聚类方法研究复杂网络聚类方法研究吉林大学知识工程教研室吉林大学知识工程教研室 吉林大学计算机学院吉林大学计算机学院 1 1目 录1.复杂网络聚类方法的研究背景及意义 2.复杂网络聚类方法的研究现状及分析 3.复杂网络聚类所面临的问题 4.我们的工作 5.复杂网络vs时空数据挖掘 2 21.复杂网络聚类方法的研究背景及意义 现实世界中的诸多系统都以网络形式存在，如 社会系统中的人际关系网、科学家协作网和流 行病传播网，生态系统中的神经元网、基因调 控网和蛋白质交互网，科技系统中的因特网、 万维网、通信网、交通网等。由于这些网络所 对应的系统具有很高的复杂性，因此被统称为 “复杂网络(co

2、mplex network)”。3 3社会网络（Social Networks）科学家协作网移动电话网络圣经对应的社会网络4 4生物网络（Biological Networks）食物链网络新陈代谢系统网络蛋白质交互网络5 5科技网络（Technological Networks）6 6O(101)O(103)O(108)复杂网络分析具有重要研究意义对于小规模网络，我们可以 通过肉眼观测其形态、特征 ，但是对于(超)大规模复杂 网络，我们将很难通过肉眼 深入理解和预测网络的结构 、行为和功能，需要借助各 种复杂网络分析方法。7 71.复杂网络聚类方法的研究背景及意义 复杂网络已成为当 前最重要的

3、多学科 交叉研究领域之一 。小世界性、无标 度性、网络模体和 网络簇结构是迄今 为止发现的最普遍 和最重要的复杂网 络拓扑结构属性。8 8Small World (Nature 1998)小世界网络： 具有较小的平均路 径长度，同时具有 较大的聚类系数。平均长度：网络中任意两点间最短路径长度的平均值。 聚类系数：节点的任意两个邻居节点仍互为邻居的平均概率9 9Scale-free network (Science 1999)无标度性：网络的度分布呈现出幂率分布（power law），而 不是随机网络的泊松分布： P(K) K-a1010 Degree distributionPoisson d

4、istributionPower-law distribution1111Network Motif (Science 1999)Network Motif：在统计意义上，网络中频繁出现的 子图模式。（某些子图在现实网络中出现的概率明显高 于这些子图在随机网络中出现的概率）。1212Network Community Structure (Science 2002, Nature 2005, 2007)网络簇结构（network community structure）具有同簇节点相互连接 密集、异簇节点相互连接稀疏的特点。13131.复杂网络聚类方法的研究背景及意义复杂网络聚类方法的研究对复

5、杂网络聚类方法的研究对分析复杂网络的拓扑结构、理解复分析复杂网络的拓扑结构、理解复杂网络的功能、发现复杂网络中的隐藏规律和预测复杂网络的杂网络的功能、发现复杂网络中的隐藏规律和预测复杂网络的行为行为不仅不仅有十分重要的理论意义，而且有广泛的应用前景。有十分重要的理论意义，而且有广泛的应用前景。目前已被应用于：恐怖组织识别与组织结构管理等目前已被应用于：恐怖组织识别与组织结构管理等社会网络分社会网络分析析，围绕新陈代谢、蛋白质交互、未知蛋白质功能预测、基因，围绕新陈代谢、蛋白质交互、未知蛋白质功能预测、基因调控和主控基因识别等问题的多种调控和主控基因识别等问题的多种生物网络分析生物网络分析，We

6、bWeb社区挖社区挖掘与掘与WebWeb文档聚类，文档聚类，搜索引擎搜索引擎，空间数据聚类空间数据聚类，图像分割图像分割 ，以及以及关系数据分析关系数据分析等众多领域。等众多领域。Nature 20051414应用例子1 聚类分析Gaussian similarity function （高斯相似度函数）:1515应用例子应用例子2 2 社会网络、语义网络、生物网络分析社会网络、语义网络、生物网络分析(Nature 2005) 科学家合作网 ：每个节点表 示一个科学家 ，连接表示科 学家之间的合 作紧密程度。语义网络: 每个节点 表示一个英文单词， 连接表示词在某个语 境下共同出现的频率 。1

7、616聚类基因网络Nature 2003 1717聚类新陈代谢网络 Nature 20051818聚类蛋白质网络(Nature 2005) （芽殖酵母菌） 的蛋白质交互网 络1919动态社会网络簇结构分析(Nature 2007) 该研究结果发现了维持社会结构稳定性的两个基本原则： 对于大规模社会机构，其成分的动态变化利于维护该机构的稳定性； 相反的，对于小规模机构，其成分的固定不变利于维护该机构的稳定性。2020基于网络簇结构分析的链接预测(Nature 2008) 该研究提出了一种广义的随机网络模型 （相对于经典的ER随机网络模型）： （1）具有更强的表达能力，既能刻画 assortati

8、ve网络又能刻画disassortative 网络； （2）对于给定的网络，该模型能够精 确的预测出网络中的未知链接或缺失链 接，并能剔除网络中存在的噪音链接。21211.复杂网络聚类方法的研究背景及意义（续）复杂网络聚类方法已成为图论、复杂网络、数据挖掘等理论的重要组成部分复杂网络聚类方法已成为图论、复杂网络、数据挖掘等理论的重要组成部分 和相关课程的核心内容和相关课程的核心内容。如康奈尔大学计算机系开设了如康奈尔大学计算机系开设了The The Structure Structure of of Information Information NetworksNetworks课程，麻省理工

9、电子工程和计算机系开设了课程，麻省理工电子工程和计算机系开设了 Networks and DynamicsNetworks and Dynamics课程。课程。由于复杂网络聚类研究具有重要的由于复杂网络聚类研究具有重要的 理论意义和应用价值理论意义和应用价值，它不仅成为，它不仅成为 计算机领域中最具挑战性的基础性计算机领域中最具挑战性的基础性 研究课题之一，也吸引了来自物理研究课题之一，也吸引了来自物理 、数学、生物、社会学和复杂性科、数学、生物、社会学和复杂性科 学等众多领域的研究者，掀起了一学等众多领域的研究者，掀起了一 股研究热潮。从股研究热潮。从20022002年年至今，新的至今，新的

10、 方法层出不穷，新的应用领域不断方法层出不穷，新的应用领域不断 被拓展，被拓展，不同领域的权威国际杂志 和多个重要国际学术会议多次报道 这方面的研究工作。 22222.复杂网络聚类方法的研究现状及分析 n2.1 复杂网络聚类方法的分类n2.2 基于优化的复杂网络聚类算法n2.3 启发式复杂网络聚类算法n2.4 其它网络聚类算法 23232.1 复杂网络聚类方法的分类 基于优化的方法将复杂网络聚类问题转 化为优化问题，通过最优化预定义的目标 函数来计算复杂网络的簇结构。 启发式方法将复杂网络聚类问题转化为 预定义启发式规则的设计问题。 除以上两类方法之外，还存在其它类 型的复杂网络聚类方法。24

11、242.1 复杂网络聚类方法的分类25252.2 基于优化的复杂网络聚类方法2.2.1 谱方法 2.2.2 基于局部搜索的复杂网络聚类方 法 2.2.3 其它基于优化方法的复杂网络聚 类方法26262.2.1 谱方法（Spectral Method）n谱方法采用二次型优化技术最小化预定义的“截函数” 。当一个网络被划分成两个子网络时，“截”指子网间 的连接密度。具有最小“截”的划分被认为是最优的网 络划分。 n谱方法具有严密的数学理论，已发展成数据聚类的一种 重要方法(称为谱聚类法)，被广泛应用于图分割和空间 点聚类等领域。 n针对复杂网络聚类，谱方法的主要不足是：1）需要借助先验知识定义递归

12、终止条件，即谱方法不 具备自动识别网络簇总数的能力；2）现实世界中的复杂网络往往包含多个网络簇，而谱 方法的递归二分策略不能保证得到网络划分是最优的多 网络簇结构。2727n 1970年，针对图分割问题克宁汉林(B.W. Kernighan和S. Lin)提出了 KL 算法 ，该算法也 可用于复杂网络聚类。 n KL算法简介 KL的优化目标是： 极小化簇间连接数目与簇内连接数目之差的绝对 值 ；KL算法的不足： 找到的解往往是局部最优而不是全局最优解。 KL 对初始解非常敏感，它需要先验知识。KL算法的时间复杂性:O(tn2)，t 表示算法终止时的迭代次数，n表示网 络节点个数。 Kernig

13、han-LinKernighan-Lin算法算法(Bell System Technical Journal,1970)2828n 2004年，纽曼(M.E.J. Newman)提出了基于局部 搜索的快速复杂网络聚类算法FN. n 算法FN简介 FN的优化目标：极大化纽曼与格万(M.E.J. Newman和M. Girvan)于同年提出的网络模块性 评价函数：Q函数. Q 函数定义为簇内的实际连 接数目与随机连接下簇内的期望连接数目之差 ，用来定量地刻画网络簇结构的优劣. Q值越大 则网络簇结构越好。 FN算法的时间复杂性: 是O (m n)，m和n分别表示网络的连接数和节 点数 快速Newm

14、an算法(Physical Rev. E,2004)2929n 2005年， 吉莫热与阿麦拉尔(R. Guimera和L.A.N. Amaral)采用与算法FN相同的优化目标函数，提 出了基于模拟退火算法(SA)的复杂网络聚类算法 GA，并应用到新陈代谢网络分析中。Nature 2005年2月刊报道了该项研究工作。 n 算法GA的优缺点GA采用模拟退火控制策略，因此GA具有跳过 局部最优解、找到全局最优解的能力，因而具有 很好的聚类精度。GA的效率取决于算法SA的效率，而后者通常 收敛很缓慢。 GA对输入参数非常敏感，不同的参数设置往 往导致不同的聚类结果。Guimera - Amaral算法

15、(Nature,2005)3030n启发式复杂网络聚类算法的共同特点是： 基于某些直观假设来设计启发式算法，对大部分网络 来说，它们能快速找到最优解或近似最优解，但无法 从理论上严格保证它们对任何输入网络都能在令人满 意的时间内找到令人满意的解。n本报告介绍几个典型的启发式复杂网络聚类算法：算法 GN(Girvan-Newman)算法 HITS(Hyperlink Induced Topic Search)算法 CPM(Clique Percolation Method)算法 FEC(Finding and Extracting Communities)2.3 2.3 启发式复杂网络聚类方法启发式复杂网络聚类方法31312.3.2 GN算法 (PNAS,2002)2002年，格万和纽曼(M. Girvan和M.E.J. Newman)提出了基于反 复识别和删除簇间连接策略的复杂网络聚类算法GN. n GN算法的缺点GN的最大缺点是计算速度慢，边介数计算的开销过大O (m n)， GN具有很高的时间复杂性O(m2n)，只适合处理中小 规模的网络(包含几百个节点的网络)。 n GN算法的意义在复杂网络聚类研究中，GN算法占有十分重要的地位（该 文被引