复杂网络聚类算法研究

《复杂网络聚类算法研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、网络聚类方法的研究背景及意义复杂网络已成为当前最重要的多学科交叉研究领域之一。小世界性、无标度性、网络模体和网络簇结构是迄今为止发现的最普遍和最重要的复杂网络拓扑结构属性。8SmallWorld(Nature1998)小世界网络：具有较小的平均路径长度，同时具有较大的聚类系数。平均长度：网络中任意两点间最短路径长度的平均值。聚类系数：节点的任意两个邻居节点仍互为邻居的平均概率9Scale-freenetwork(Science1999)无标度性：网络的度分布呈现出幂率分布（powerlaw），而不是随

4、机网络的泊松分布：P(K)~K-a10DegreedistributionPoissondistributionPower-lawdistribution11NetworkMotif(Science1999)NetworkMotif：在统计意义上，网络中频繁出现的子图模式。（某些子图在现实网络中出现的概率明显高于这些子图在随机网络中出现的概率）。12NetworkCommunityStructure(Science2002,Nature2005,2007)网络簇结构（networkcommunitys

5、tructure）具有同簇节点相互连接密集、异簇节点相互连接稀疏的特点。131.复杂网络聚类方法的研究背景及意义复杂网络聚类方法的研究对分析复杂网络的拓扑结构、理解复杂网络的功能、发现复杂网络中的隐藏规律和预测复杂网络的行为不仅有十分重要的理论意义，而且有广泛的应用前景。目前已被应用于：恐怖组织识别与组织结构管理等社会网络分析，围绕新陈代谢、蛋白质交互、未知蛋白质功能预测、基因调控和主控基因识别等问题的多种生物网络分析，Web社区挖掘与Web文档聚类，搜索引擎，空间数据聚类，图像分割，以及关系数据分析

6、等众多领域。Nature200514应用例子1–聚类分析Gaussiansimilarityfunction（高斯相似度函数）:15应用例子2社会网络、语义网络、生物网络分析(Nature2005)科学家合作网：每个节点表示一个科学家，连接表示科学家之间的合作紧密程度。语义网络:每个节点表示一个英文单词，连接表示词在某个语境下共同出现的频率。16聚类基因网络Nature200317聚类新陈代谢网络Nature200518聚类蛋白质网络(Nature2005)（芽殖酵母菌）的蛋白质交互网络19动态社会网

7、络簇结构分析(Nature2007)该研究结果发现了维持社会结构稳定性的两个基本原则：对于大规模社会机构，其成分的动态变化利于维护该机构的稳定性；相反的，对于小规模机构，其成分的固定不变利于维护该机构的稳定性。20基于网络簇结构分析的链接预测(Nature2008)该研究提出了一种广义的随机网络模型（相对于经典的ER随机网络模型）：（1）具有更强的表达能力，既能刻画assortative网络又能刻画disassortative网络；（2）对于给定的网络，该模型能够精确的预测出网络中的未知链接或缺失链接

8、，并能剔除网络中存在的噪音链接。211.复杂网络聚类方法的研究背景及意义（续）复杂网络聚类方法已成为图论、复杂网络、数据挖掘等理论的重要组成部分和相关课程的核心内容。如康奈尔大学计算机系开设了《TheStructureofInformationNetworks》课程，麻省理工电子工程和计算机系开设了《NetworksandDynamics》课程。由于复杂网络聚类研究具有重要的理论意义和应用价值，它不仅成为计算机领域中最具挑战性的基础性研究课题之一，也吸引