基于模块性的簇结构检测图聚类算法研究

摘要

网络簇结构是复杂网络中重要的拓扑结构，通过检测簇结构可以分析复杂网络的拓扑性质，反映复杂网络的功能特性。从大规模的复杂网络中挖掘重要的簇结构(Community structure)已经成为当今研究的热点之一。近年来，图聚类算法在检测复杂网络簇结构中扮演着极其重要的角色，如在社会网络、生物网络、引文网络等领域都得到了非常好的实际应用。
　　本文对面向复杂网络检测簇结构问题进行分析，研究发现相较于密度性，模块性能够更好地体现簇结构的拓扑结构，并对聚类算法的效能和聚类结果具有决定性作用。因此本文针对复杂网络中基于模块性的图聚类算法，对算法过程中的边权重定义、种子选择与扩展等问题展开研究，提出一种检测复杂网络中稠密簇结构的局部模块性图聚类算法LMC。主要工作如下：
　　(1)基于端点的相似性，定义了边权重 w，在此基础上给出了簇结构的模块性定义以及顶点对簇结构的适应度函数。其中模块性度量了簇结构的抱团性，适应度函数体现了一个顶点对簇结构的影响程度。
　　(2)提出了基于“种子边-扩展”策略的复杂网络簇结构检测算法LMC。首先，根据所给出的边权重定义选取种子边，形成初始簇；计算当前簇的模块性，并计算当前簇的局部邻域内结点对簇的适应度函数，对其进行扩展，直到簇的模块性达到局部最大值；在此过程中，一个顶点可能同时属于多个簇结构。
　　(3)本文给出的 LMC算法是一个可以检测复杂网络中稠密簇结构的软聚类方法。最后，将聚类算法 LMC分别在人工模拟数据及真实蛋白质网络上进行实验比较，结果表明 LMC可以检测出网络中的重叠簇结构，真实地反应出蛋白质网络PPI中复合物的构成。

目录

封面

目录

中文摘要

英文摘要

第一章 绪论

1.1研究背景、目的及意义

1.2国内外研究现状

1.3本文工作

1.4本文组织结构

第二章 预备知识

2.1图相关概念

2.2点的相似性度量

2.3密度性及模块性相关概念

2.4本章小结

第三章 基于模块性的算法LMC

3.1边权重定义

3.2种子边选取

3.3基于局部模块性的聚类发现

3.4 LMC算法具体描述

3.5本章小结

第四章 实验结果与分析

4.1 One-vertex-union图G3(i, j, k)数据集实验

4.2 One-vertex-union图变型数据集实验

4.3蛋白质互作用网络PPI数据实验

4.4本章小结

第五章 总结与展望

5.1本文总结

5.2未来展望

参考文献

攻读学位期间取得的研究成果

致谢

个人简况及联系方式

承 诺 书

声明