基于连接度的图聚类方法研究

论文摘要

图是实体及其关系建模的一种常见方法并广泛地运用于Internet，Web结构，社会网络，代谢网络，蛋白质作用网络，文献共引关系网络，以及通讯网络等的结构描述。随着通讯技术、计算机及网络技术的飞速发展和社会信息化进程的持续推进，用于描述真实世界网络结构的图的规模普遍呈现出指数增长趋势。这一现象，一方面确定了大型复杂网络结构特征研究的必要性和挑战性；另一方面激发了很多研究者试图探索以聚类方法分析、理解和表示它们的浓厚兴趣。图聚类是按照结点具有的关联特性对结点进行分类或标识。其目标是分组图的结点，使其组内紧密关联，组间稀疏关联。不同于一般的数值聚类，图聚类具有其自身的特殊性。主要是因为图的许多特性，如结点间的距离，关联关系等，对图中的边具有高度敏感性；另外，图的距离往往是整数，结点到多个聚类中心等距的情况十分常见。因此，一般很难简单复制数值聚类的现有方法达到图聚类的目标。本文以连通的无向非加权图为研究对象，在系统地分析和比较几种典型的图聚类方法的基础上，主要完成如下研究工作：（1）提出了结点连接度和图的连接度矩阵的概念，并给出了它们的定义及计算方法，该方法的效率主要依赖于计算过程中所用的最短路径算法。（2）将最大最小距离聚类方法的基本思想与连接度矩阵相结合，提出了最大最小连接度图聚类方法，该聚类方法的时间复杂度为O（（k+3）k/2 n），其中，k是期望的聚类数目，n是图的结点数。（3）引入结点相异度和图的相异度矩阵的概念，给出其具体定义和计算模型，该模型的算法复杂度均为O（n2）。（4）给出了已知图的相异度矩阵的前提下，子聚类间的一种相异度度量方法，允许以之为依据实现对图结点的凝聚层次聚类。（5）通过实例检验了上述度量标准及聚类算法的正确性和有效性。

论文目录

• 中文摘要
• ABSTRACT
• 第一章 引言
• 1.1 聚类分析概述
• 1.2 聚类分析技术
• 1.3 图聚类分析
• 1.3.1 图聚类分析概述
• 1.3.2 国内外研究现状
• 1.3.3 图聚类分析面临的问题和挑战
• 1.4 论文的主要工作
• 1.5 论文的组织结构
• 第二章 图聚类方法的分析比较
• 2.1 图的基本概念和术语
• 2.2 Kernighan-Lin算法
• 2.3 谱聚类方法
• 2.3.1 基于Laplace矩阵的传统谱平分法
• 2.3.2 其它谱平分法
• 2.4 层次聚类方法
• 2.4.1 GN算法
• 2.4.2 Newman快速算法
• 第三章 最大最小关联度聚类方法
• 3.1 结点相似性
• 3.2 关联度矩阵
• 3.3 聚类算法描述
• 3.4 算法例证
• 3.5 算法分析
• 3.6 小结
• 第四章 基于相异度度量的凝聚聚类方法
• 4.1 相异度定义
• 4.2 聚类算法描述
• 4.3 算法例证
• 4.4 分析比较
• 4.5 聚类结果评测
• 4.6 小结
• 结论与展望
• 参考文献
• 发表文章目录
• 致谢
• 个人简况及联系方式