基于聚集系数的聚类算法在复杂网络中的应用研究

摘要

社团发现是复杂网络分析中一个重要的研究领域，其本质上属于数据挖掘技术中的聚类。聚类的目的是将较为相似的数据点聚集成簇，而在现实生活中存在的复杂网络也是因为相似性而被划分为若干个社团。在众多衡量网络中各节点之间相似性的方法中，聚集系数是最为常用的一种方法。本课题提出两个聚类算法用于发现复杂网络中的社团，这两个算法都是依据聚集系数衡量网络中节点的相似度。这两个算法是：
　　1)一个新的动态聚类算法用于一般复杂网络中的社团发现。该算法采用两种网络拓扑特性，聚类特性与中心特性，对网络进行分析。聚类特性用于衡量网络中各有边相连节点之间在拓扑结构上的相似性，而中心特性用于确定各个簇的中心点。通过对每个节点进行迭代重定位，将相似的节点组合成簇。各个节点的归属主要是依据其对于各个簇中关键节点的相似性。实验证明，本课题提出的算法能够精确地发现现实网络中存在的社团，而且具有较低的时间复杂度。
　　2)一个基于密度的聚类算法用于从蛋白质相互作用网络中识别出复合物。首先，采用一种基于基因本体的相似度计算方法来衡量网络中各相互作用的强度，并作为对应边的权重；之后，采用一个新的基于密度的图划分算法从带权重的网络中发现较为稠密的子图，这些子图将作为算法输出的簇。实验结果证明该方法可以成功地从两类蛋白质相互作用网络中识别出潜在的复合物。
　　该论文得到国家自然科学基金（No.61402363）的资助。

目录

封面

声明

中文摘要

英文摘要

目录

1绪论

1.1研究背景及目的

1.2论文内容及组织结构

2复杂网络社团发现算法

2.1社团的定义

2.2层次聚类算法

2.3 RANKCLUS算法

2.4经典算法概述

2.5本章小结

3复杂网络中的聚集系数

3.1节点的聚集系数

3.2边的聚集系数

3.3本章小结

4 DCM-Net算法

4.1算法概述

4.2算法聚类过程

4.3基于聚集系数的社团归属度衡量方法

4.4伪代码和时间复杂度

4.5实验及分析

4.6本章小结

5 DBGPWN算法

5.1算法概述

5.2基于聚集系数的密度可达关系

5.3伪代码和时间复杂度

5.4蛋白质网络相互作用权重评估方法

5.5对比实验

5.6本章小结

6总结

致谢

参考文献

在校期间学术成果