复杂网络聚类算法研究.ppt

1,复杂网络聚类方法研究,吉林大学知识工程教研室 吉林大学计算机学院,2,目 录,1.复杂网络聚类方法的研究背景及意义 2.复杂网络聚类方法的研究现状及分析 3.复杂网络聚类所面临的问题 4.我们的工作 5.复杂网络vs时空数据挖掘,3,1.复杂网络聚类方法的研究背景及意义,现实世界中的诸多系统都以网络形式存在，如社会系统中的人际关系网、科学家协作网和流行病传播网，生态系统中的神经元网、基因调控网和蛋白质交互网，科技系统中的因特网、万维网、通信网、交通网等。由于这些网络所对应的系统具有很高的复杂性，因此被统称为“复杂网络(complex network)”。,4,社会网络（Social Networks）,科学家协作网,移动电话网络,圣经对应的社会网络,5,生物网络（Biological Networks）,食物链网络,新陈代谢系统网络,蛋白质交互网络,6,科技网络（Technological Networks）,7,O(101),O(103),O(108),复杂网络分析具有重要研究意义,对于小规模网络，我们可以通过肉眼观测其形态、特征，但是对于(超)大规模复杂网络，我们将很难通过肉眼深入理解和预测网络的结构、行为和功能，需要借助各种复杂网络分析方法。,8,1.复杂网络聚类方法的研究背景及意义,复杂网络已成为当前最重要的多学科交叉研究领域之一。小世界性、无标度性、网络模体和网络簇结构是迄今为止发现的最普遍和最重要的复杂网络拓扑结构属性。,9,Small World (Nature 1998),小世界网络： 具有较小的平均路径长度，同时具有较大的聚类系数。,平均长度：网络中任意两点间最短路径长度的平均值。 聚类系数：节点的任意两个邻居节点仍互为邻居的平均概率,10,Scale-free network (Science 1999),无标度性：网络的度分布呈现出幂率分布（power law），而不是随机网络的泊松分布： P(K) K-a,11,Degree distribution,Poisson distribution,Power-law distribution,12,Network Motif (Science 1999),Network Motif：在统计意义上，网络中频繁出现的子图模式。（某些子图在现实网络中出现的概率明显高于这些子图在随机网络中出现的概率）。,13,Network Community Structure (Science 2002, Nature 2005, 2007),网络簇结构（network community structure）具有同簇节点相互连接密集、异簇节点相互连接稀疏的特点。,14,1.复杂网络聚类方法的研究背景及意义,复杂网络聚类方法的研究对分析复杂网络的拓扑结构、理解复杂网络的功能、发现复杂网络中的隐藏规律和预测复杂网络的行为不仅有十分重要的理论意义，而且有广泛的应用前景。 目前已被应用于：恐怖组织识别与组织结构管理等社会网络分析，围绕新陈代谢、蛋白质交互、未知蛋白质功能预测、基因调控和主控基因识别等问题的多种生物网络分析，Web社区挖掘与Web文档聚类，搜索引擎，空间数据聚类，图像分割 ，以及关系数据分析等众多领域。,Nature 2005,15,应用例子1 聚类分析,Gaussian similarity function（高斯相似度函数）:,16,应用例子2 社会网络、语义网络、生物网络分析,(Nature 2005),科学家合作网：每个节点表示一个科学家，连接表示科学家之间的合作紧密程度。,语义网络: 每个节点表示一个英文单词，连接表示词在某个语境下共同出现的频率。,17,聚类基因网络,Nature 2003,18,聚类新陈代谢网络,Nature 2005,19,聚类蛋白质网络,(Nature 2005),（芽殖酵母菌）的蛋白质交互网络,20,动态社会网络簇结构分析,(Nature 2007),该研究结果发现了维持社会结构稳定性的两个基本原则： 对于大规模社会机构，其成分的动态变化利于维护该机构的稳定性； 相反的，对于小规模机构，其成分的固定不变利于维护该机构的稳定性。,21,基于网络簇结构分析的链接预测,(Nature 2008),该研究提出了一种广义的随机网络模型（相对于经典的ER随机网络模型）： （1）具有更强的表达能力，既能刻画assortative网络又能刻画disassortative网络； （2）对于给定的网络，该模型能够精确的预测出网络中的未知链接或缺失链接，并能剔除网络中存在的噪音链接。,22,1.复杂网络聚类方法的研究背景及意义（续）,复杂网络聚类方法已成为图论、复杂网络、数据挖掘等理论的重要组成部分和相关课程的核心内容。如康奈尔大学计算机系开设了The Structure of Information Networks课程，麻省理工电子工程和计算机系开设了Networks and Dynamics课程。,由于复杂网络聚类研究具有重要的理论意义和应用价值，它不仅成为计算机领域中最具挑战性的基础性研究课题之一，也吸引了来自物理、数学、生物、社会学和复杂性科学等众多领域的研究者，掀起了一股研究热潮。从2002年至今，新的方法层出不穷，新的应用领域不断被拓展，不同领域的权威国际杂志和多个重要国际学术会议多次报道这方面的研究工作。,23,2.复杂网络聚类方法的研究现状及分析,2.1 复杂网络聚类方法的分类 2.2 基于优化的复杂网络聚类算法 2.3 启发式复杂网络聚类算法 2.4 其它网络聚类算法,24,2.1 复杂网络聚类方法的分类, 基于优化的方法将复杂网络聚类问题转化为优化问题，通过最优化预定义的目标函数来计算复杂网络的簇结构。 启发式方法将复杂网络聚类问题转化为预定义启发式规则的设计问题。 除以上两类方法之外，还存在其它类型的复杂网络聚类方法。,25,2.1 复杂网络聚类方法的分类,26,2.2 基于优化的复杂网络聚类方法,2.2.1 谱方法 2.2.2 基于局部搜索的复杂网络聚类方法 2.2.3 其它基于优化方法的复杂网络聚类方法,27,2.2.1 谱方法（Spectral Method）,谱方法采用二次型优化技术最小化预定义的“截函数”。当一个网络被划分成两个子网络时，“截”指子网间的连接密度。具有最小“截”的划分被认为是最优的网络划分。 谱方法具有严密的数学理论，已发展成数据聚类的一种重要方法(称为谱聚类法)，被广泛应用于图分割和空间点聚类等领域。 针对复杂网络聚类，谱方法的主要不足是： 1）需要借助先验知识定义递归终止条件，即谱方法不具备自动识别网络簇总数的能力； 2）现实世界中的复杂网络往往包含多个网络簇，而谱方法的递归二分策略不能保证得到网络划分是最优的多网络簇结构。,28,1970年，针对图分割问题克宁汉林(B.W. Kernighan和S. Lin)提出了 KL 算法 ，该算法也可用于复杂网络聚类。 KL算法简介 KL的优化目标是： 极小化簇间连接数目与簇内连接数目之差的绝对值 ； KL算法的不足： 找到的解往往是局部最优而不是全局最优解。 KL 对初始解非常敏感，它需要先验知识。 KL算法的时间复杂性: O(tn2)，t 表示算法终止时的迭代次数，n表示网络节点个数。,Kernighan-Lin算法(Bell System Technical Journal,1970),29,2004年，纽曼(M.E.J. Newman)提出了基于局部搜索的快速复杂网络聚类算法FN. 算法FN简介 FN的优化目标：极大化纽曼与格万(M.E.J. Newman和M. Girvan)于同年提出的网络模块性评价函数：Q函数. Q 函数定义为簇内的实际连接数目与随机连接下簇内的期望连接数目之差，用来定量地刻画网络簇结构的优劣. Q值越大则网络簇结构越好。 FN算法的时间复杂性: 是O (m n)，m和n分别表示网络的连接数和节点数,快速Newman算法(Physical Rev. E,2004),30,2005年， 吉莫热与阿麦拉尔(R. Guimera和L.A.N. Amaral)采用与算法FN相同的优化目标函数，提出了基于模拟退火算法(SA)的复杂网络聚类算法GA，并应用到新陈代谢网络分析中。Nature2005年2月刊报道了该项研究工作。 算法GA的优缺点 GA采用模拟退火控制策略，因此GA具有跳过局部最优解、找到全局最优解的能力，因而具有很好的聚类精度。 GA的效率取决于算法SA的效率，而后者通常收敛很缓慢。 GA对输入参数非常敏感，不同的参数设置往往导致不同的聚类结果。,Guimera - Amaral算法(Nature,2005),31,启发式复杂网络聚类算法的共同特点是： 基于某些直观假设来设计启发式算法，对大部分网络来说，它们能快速找到最优解或近似最优解，但无法从理论上严格保证它们对任何输入网络都能在令人满意的时间内找到令人满意的解。 本报告介绍几个典型的启发式复杂网络聚类算法： 算法 GN(Girvan-Newman) 算法 HITS(Hyperlink Induced Topic Search) 算法 CPM(Clique Percolation Method) 算法 FEC(Finding and Extracting Communities),2.3 启发式复杂网络聚类方法,32,2.3.2 GN算法(PNAS,2002),2002年，格万和纽曼(M. Girvan和M.E.J. Newman)提出了基于反复识别和删除簇间连接策略的复杂网络聚类算法GN. GN算法的缺点 GN的最大缺点是计算速度慢，边介数计算的开销过大O (m n)， GN具有很高的时间复杂性O(m2n)，只适合处理中小规模的网络(包含几百个节点的网络)。 GN算法的意义 在复杂网络聚类研究中，GN算法占有十分重要的地位（该文被引用超过1000次），格万和纽曼工作的重要意义在于：他们首次发现了复杂网络中普遍存在的网络簇结构，启发了其他研究者对这个问题的深入研究，掀起了复杂网络聚类的研究热潮。,33,2.3.4 HITS 算法 (Journal of ACM,1999 ),1999年，针对基于链接的网页排名问题，克莱因博格(Kleinberg)等人提出了著名的HITS算法，该算法也可用于基于内容的网页聚类。 HITS算法基于的基本假设 根据链接关系，WWW中存在权威(authority)和中心(hub)两种基本类型 的页面，权威页面倾向于被多个中心页面引用，而中心页面倾向于引用 多个权威页面。 基于权威中心页面间相互指向的链接关系，HITS算法通过计算 WWW子图（由查询得到的子图经过扩充而成）对应的某个特殊矩阵 的主特征向量来发现隐藏在WWW中的全部由权威中心页面构成 的网络簇结构。 该算法与Google的PageRank算法齐名，被包括Altavista在内的多个搜 索引擎所采用。,34,目前，绝大多数算法不考虑重叠网络簇结构。但在许多应用中，重叠网络簇结构更具有实际意义。如在语义网中，多义词允许同时出现在多个表示不同词义的网络簇 中. 2005年，帕拉(G.Palla)等在Nature上发表文章，首次提出了能识别重叠网络簇结构的CPM算法. CPM简介 CPM的基本假设 网络簇由多个相邻的k-团(k-clique)组成，两个相邻的k-团至少共享k-1个节点，每个k-团唯一的属于某个网络簇，但属于不同网络簇的k-团可能会共享某些节点。 CPM的缺点 1) 实际应用中参数k难以确定，选取不同的k值会得到不同的网络簇结构。 2) 计算网络中的全部k-团非常耗时，CPM非常慢，其时间复杂性近似为指数阶。,2.3.6 CPM 算法 (Nature, 2005),35,2.3.7 FEC算法 (TKDE, 2007),符号网络(signed network)是指包含正、负两种关系的二维复杂网络，是对一般复杂网络描述能力的一种推广。符号网络广泛存在于社会、生物等多种复杂系统中。符号网络簇结构具有簇内正关系稠密、同时簇间负关系稠密的特点. 2007年，我们针对符号网络聚类问题，提出了基于马尔科夫随机游走模型的启发式符号网络聚类算法FEC . FEC算法简介 FEC的基本假设 从任意给定的簇出发，网络中的Markov随机游走过程达到起始簇内节点的期望概率将大于达到起始簇外节点的期望概率。 网络簇识别 基于该启发规则，FEC先算出在给定时刻Markov随机游走过程到达所有节点的期望转移概率分布，进而根据该分布的局部一致性(同簇节点具有近似相同的期望转移概率分布)识别出所有的网络簇。 FEC算法之优缺点 1) 是第一个综合考虑两种分簇标准(连接密度和连接符号)的复杂网络聚类算法。 2) FEC在效率和识别精度都表现了更好的性能，尤其适于处理噪声高和网络簇结构不明显的复杂网络。 3）随机游走的步长会影响算法的聚类结果，尽管实验表明对某些网络，聚类结果对该参数并不敏感，但如何针对不同网络计算出最优步长仍是一个未被解决的理论问题。,36,3 复杂网络聚类所面临的问题,第一，我们还没有从客观上认清网络簇结构的本质含义。 1.网络簇结构是怎么形成的？ 2.它与网络的其它复杂现象有什么必然联系？ 3.它与网络自身的哪些内在属性有关？ 因此，现阶段我们不得不通过观察有簇网络所展示出的“外在”现象去理解网络簇概念，借助“主观”定义的目标函数或启发式规则去刻画和计算网络簇结构。 能否从网络的“内在”属性出发，给出一种“客观”的理论模型去理解、刻画和计算复杂网络簇结构。,37,3 复杂网络聚类所面临的问题,第二，不能同时满足计算速度快、聚类精度高（即抗噪声能力强）、免参数（即不依赖先验知识、对参数不敏感）等基本要求。 识别精度高的方法往往具有很高时间复杂性( O(n2) )，而快速的识别方法往往以牺牲精度为代价并且需要较多的参数和先验知识。 如何设计出快速、高精度和免参数的复杂网络聚类方法仍是当前最期待解决的问题之一。,38,3 复杂网络聚类所面临的问题,第三，除以上未解决的理论问题之外，随着应用领域的拓展、网络聚类问题的多样化，现有复杂网络聚类方法已难以胜任，需要针对特殊类型的复杂网络研究新型的复杂网络聚类方法。 （1）动态复杂网络聚类方法 （2）高维复杂网络聚类方法 （3）分布式复杂网络聚类方法 以上类型的复杂网络聚类方法具有广泛的应用领域，因此如何针对特殊类型的复杂网络设计出新型的复杂网络聚类方法也是当前面临的主要问题之一。,39,4. 前期的一些工作,Detect communities from decentralized networks B 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 communities B Yang, J Liu. Discovering Global Network Communities Based on Local Centralities. ACM Transactions on the Web (TWEB), 2008. Detect communities from signed networks B Yang, WK Cheung, J Liu. Community Mining from Signed Social Networks. IEEE Transactions on Knowledge and Data Engineering (TKDE), 2007. Detect communities from dynamic networks B Yang, D Liu. Force-based Incremental Algorithm for Mining Community Structure in Dynamic Network. Journal of Computer Science and Technology (JCST), 2006.,40,正在开展的一些工作,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 classification,41,时空数据挖掘,随着GPS、RS和GIS 等技术的应用和发展，使时空数据的膨胀速度远远超出了常规的事务型数据，“数据爆炸但知识贫乏”的现象在时空数据中尤为严重。,Geo-spatial data,Biomedical Data,Climate Data,Sensor Networks,42,特点和应用,除了具有海量、高维、高噪声和非线性等一般数据特征外，时空数据还包含了拓扑、距离、尺度、形状和时间等多种特殊信息，并按复杂的多维空间索引结构进行组织，在数据分析过程中还需借助空间推理、拓扑分析、几何计算和时空语义分析等方法。 时空数据挖掘方法对于有效处理海量时空数据、提高时空数据分析的自动化和智能化水平具有重要意义，在遥感、GIS、实时导航、决策支持、交通控制、环境监测、医疗图像处理、案件侦破、道路交通、机器人等许多涉及时空数据的领域中都有广泛应用。,43,应用成果,SKICAT系统已经发现了16 个新的极其遥远的类星体； POSS系统将天空图像中的星体对象分类准确性从75%提高到94%； MagellanStudy系统通过分析启明星表面的大约30000 幅高分辨率雷达图像，识别了火山； CONQUEST系统基于内容的空间和时间查询，发现了大气层中臭氧洞形成的样本知识。,44,时空数据挖掘vs复杂网络,1. 时空数据网 随着时空数据的日益积累，时空数据已经形成一个以时空数据实体为节点，时空数据实体与实体之间的关联关系为边的复杂网络，并以其自身的规律进行演化和发展。研究时空数据网络自身的演化规律，建立时空数据网络的预测模型，有利于时空数据挖掘。为了分析时空数据网络，可以将一些相关的复杂网络模型引入到时空数据网络当中。 2. 特征空间vs相似度空间 “高维”是基于特征空间数据挖掘方法所面临的主要困难。基于相似度空间的复杂网络分析是一个很有前景的“高维”数据分析方