24
Average cut Ratio cut Normalized cut Kernighan-Lin Local Search Fast Newman Guimera-Amaral Potts Model with multi-spin state es MFC Girvan-Newman Tyler Radicchi HITS Wu-Huberman FEC CPM Correlation coefficient Random walk based similarity Clustering centrality Hall
对于小规模网络， 对于小规模网络，我们可以 通过肉眼观测其形态、特征， 通过肉眼观测其形态、特征， 但是对于(超 大规模复杂网 但是对于 超)大规模复杂网 络，我们将很难通过肉眼深 入理解和预测网络的结构、 入理解和预测网络的结构、 行为和功能， 行为和功能，需要借助各种 复杂网络分析方法。 复杂网络分析方法。
复杂网络聚类方法研究
吉林大学知识工程教研室 吉林大学计算机学院
1
目
录
1.复杂网络聚类方法的研究背景及意义 2.复杂网络聚类方法的研究现状及分析 3.复杂网络聚类所面临的问题 4.我们的工作 5.复杂网络vs时空数据挖掘 复杂网络vs时空数据挖掘
2
1.复杂网络聚类方法的研究背景及意义 1.复杂网络聚类方法的研究背景及意义
8
Small World (Nature 1998)
小世界网络： 小世界网络： 具有较小 较小的平均路 具有较小的平均路 径长度， 径长度，同时具有 较大的聚类系数 的聚类系数。 较大的聚类系数。
平均长度：网络中任意两点间最短路径长度的平均值。 平均长度：网络中任意两点间最短路径长度的平均值。 聚类系数： 聚类系数：节点的任意两个邻居节点仍互为邻居的平均概率
3
社会网络（ 社会网络（Social Networks） ）
科学家协作网
移动电话网络
《圣经》对应的社会网络
4
生物网络（ 生物网络（Biological Networks） ）
新陈代谢系统网络 蛋白质交互网络
食物链网络
5
科技网络（ 科技网络（Technological Networks） ）
6
复杂网络分析具有重要研究意义
14
Nature 2005
应用例子1 应用例子1– 聚类分析
15 10 5 0 -5 -10 -10 0 10 20 30
Gaussian similarity function （高斯相似度函数）:
aij = exp(− || xi − x j || 2 / ε)
15
应用例子2 应用例子2
社会网络、语义网络、生物网络分析 社会网络、语义网络、
基于网络簇结构分析的链接预测
(Nature 2008)
该研究提出了一种广义的随机网络模型 相对于经典的ER随机网络模型 随机网络模型）： （相对于经典的 随机网络模型）： （1）具有更强的表达能力，既能刻画 ）具有更强的表达能力， assortative网络又能刻画 网络又能刻画disassortative 网络又能刻画 网络； 网络； （2）对于给定的网络，该模型能够精 ）对于给定的网络， 确的预测出网络中的未知链接或缺失链 并能剔除网络中存在的噪音链接。 接，并能剔除网络中存在的噪音链接。
2.1 复杂网络聚类方法的分类
Donetti-Munoz
2.2 基于优化的复杂网络聚类方法
2.2.1 谱方法 2.2.2 基于局部搜索的复杂网络聚类方法 2.2.3 其它基于优化方法的复杂网络聚类 方法
Hale Waihona Puke 262.2.1 谱方法（Spectral Method） 谱方法（ Method）
谱方法采用二次型优化技术最小化预定义的 截函数” 谱方法采用 二次型优化技术最小化预定义的 “ 截函数 ” 。 二次型优化技术最小化预定义的“ 当一个网络被划分成两个子网络时， 当一个网络被划分成两个子网络时 ， “ 截 ” 指子网间的 连接密度。 具有最小“ 连接密度 。 具有最小 “ 截 ” 的划分被认为是最优的网络 划分。 划分。 谱方法具有严密的数学理论， 谱方法具有严密的数学理论 ， 已发展成数据聚类的一种 重要方法(称为谱聚类法)， 称为谱聚类法 重要方法 称为谱聚类法 ，被广泛应用于图分割和空间点 聚类等领域。 聚类等领域。 针对复杂网络聚类，谱方法的主要不足 主要不足是 针对复杂网络聚类，谱方法的主要不足是： 1）需要借助先验知识定义递归终止条件，即谱方法不具 ）需要借助先验知识定义递归终止条件， 备自动识别网络簇总数的能力； 备自动识别网络簇总数的能力； 2）现实世界中的复杂网络往往包含多个网络簇，而谱方 ）现实世界中的复杂网络往往包含多个网络簇， 法的递归二分策略不能保证得到网络划分是最优的多网 络簇结构。 络簇结构。
12
Network Community Structure (Science 2002, Nature 2005, 2007)
网络簇结构（network community structure）具有同簇节点相互连接 网络簇结构（ ）具有同簇节点相互连接 密集、异簇节点相互连接稀疏的特点。 稀疏的特点 密集、异簇节点相互连接稀疏的特点。
现实世界中的诸多系统都以网络形式存在， 现实世界中的诸多系统都以网络形式存在 ， 如社会系统中的人际关系网 人际关系网、 如社会系统中的 人际关系网 、 科学家协作网 流行病传播网， 生态系统中的神经元网 神经元网、 和 流行病传播网 ， 生态系统中的 神经元网 、 基因调控网和 蛋白质交互网， 基因调控网 和 蛋白质交互网 ， 科技系统中的 因特网、 万维网、 通信网、 交通网等 因特网 、 万维网 、 通信网 、 交通网 等 。 由于 这些网络所对应的系统具有很高的复杂性， 这些网络所对应的系统具有很高的复杂性 ， 因 此 被 统 称 为 “ 复 杂 网 络 (complex network)”。 )
13
1.复杂网络聚类方法的研究背景及意义 1.复杂网络聚类方法的研究背景及意义
复杂网络聚类方法的研究对分析复杂网络的拓扑结构 复杂网络聚类方法的研究对分析复杂网络的拓扑结构、理解复 分析复杂网络的拓扑结构、 杂网络的功能、 杂网络的功能、发现复杂网络中的隐藏规律和预测复杂网络的 行为不仅有十分重要的理论意义 而且有广泛的应用前景。 行为不仅有十分重要的理论意义，而且有广泛的应用前景。 不仅有十分重要的理论意义， 目前已被应用于：恐怖组织识别与组织结构管理等社会网络分 目前已被应用于：恐怖组织识别与组织结构管理等社会网络分 析，围绕新陈代谢、蛋白质交互、未知蛋白质功能预测、基因 围绕新陈代谢、蛋白质交互、未知蛋白质功能预测、 生物网络分析， 调控和主控基因识别等问题的多种生物网络分析 Web社区挖 调控和主控基因识别等问题的多种生物网络分析，Web社区挖 掘与Web文档聚类 搜索引擎，空间数据聚类， 掘与Web文档聚类，搜索引擎，空间数据聚类，图像分割 ， 文档聚类， 以及关系数据分析等众多领域。 以及关系数据分析等众多领域。 关系数据分析等众多领域
21
1.复杂网络聚类方法的研究背景及意义（续） 1.复杂网络聚类方法的研究背景及意义 复杂网络聚类方法的研究背景及意义（
由于复杂网络聚类研究具有重要的 理论意义和应用价值， 理论意义和应用价值 ， 它不仅成为 计算机领域中最具挑战性的基础性 研究课题之一， 也吸引了来自物理、 研究课题之一 ， 也吸引了来自物理 、 数学、 生物、 数学 、 生物 、 社会学和复杂性科学 等众多领域的研究者， 等众多领域的研究者 ， 掀起了一股 研究热潮。 2002年 至今， 研究热潮 。 从 2002 年 至今 ， 新的方 法层出不穷， 法层出不穷 ， 新的应用领域不断被 拓展， 拓展 ， 不同领域的权威国际杂志和 多个重要国际学术会议多次报道这 方面的研究工作。 方面的研究工作。 复杂网络聚类方法已成为图论、复杂网络、 复杂网络聚类方法已成为图论、复杂网络、数据挖掘等理论的重要组成部分 和相关课程的核心内容。 如康奈尔大学计算机系开设了《 和相关课程的核心内容 。 如康奈尔大学计算机系开设了 《The Structure of Information Networks》 课 程 ， 麻 省 理 工 电 子 工 程 和 计 算 机 系 开 设 了 Networks》 Dynamics》课程。 《Networks and Dynamics》课程。
芽殖酵母菌） （芽殖酵母菌） 的蛋白质交互网 络
19
动态社会网络簇结构分析
(Nature 2007)
该研究结果发现了维持社会结构稳定性的两个基本原则： 该研究结果发现了维持社会结构稳定性的两个基本原则： 对于大规模社会机构，其成分的动态变化利于维护该机构的稳定性； 动态变化利于维护该机构的稳定性 对于大规模社会机构，其成分的动态变化利于维护该机构的稳定性； 相反的，对于小规模机构，其成分的固定不变利于维护该机构的稳定性。 固定不变利于维护该机构的稳定性 20 相反的，对于小规模机构，其成分的固定不变利于维护该机构的稳定性。
(Nature 2005)
科学家合作网： 每个节点表示 一个科学家， 连接表示科学 家之间的合作 紧密程度。
语义网络: 每个节点 表示一个英文单词， 连接表示词在某个语 境下共同出现的频率。
16
聚类基因网络
Nature 2003
17
聚类新陈代谢网络
Nature 2005
18
聚类蛋白质网络
(Nature 2005)
22
2.复杂网络聚类方法的研究现状及分析 2.复杂网络聚类方法的研究现状及分析
2.1 复杂网络聚类方法的分类
2.2 基于优化的复杂网络聚类算法
2.3 启发式复杂网络聚类算法 2.4 其它网络聚类算法
23
2.1 复杂网络聚类方法的分类 • 基于优化的方法 基于优化的方法将复杂网络聚类问题转 化为优化问题，通过最优化预定义的目标函 通过最优化预定义的目标函 数来计算复杂网络的簇结构。 数来计算复杂网络的簇结构。 • 启发式方法 启发式方法将复杂网络聚类问题转化为 预定义启发式规则的设计问题。 • 除以上两类方法之外，还存在其它类型 除以上两类方法之外，还存在其它类型 的复杂网络聚类方法。 的复杂网络聚类方法。