基于稠密子图的社区发现算法研究

摘要

复杂网络分析在生物网络、社会组织结构、搜索引擎及推荐系统中被广泛应用。社区结构是复杂网络中的一个重要特征，一个复杂网络通常包含若干个社区，社区内部对象连接相对紧密，社区间对象连接相对稀疏。在从大规模的复杂网络中进行社区发现已经成为众多领域研究的热点之一。发现复杂网络中的社区结构有助于分析和理解复杂网络的拓扑结构，以便人们更好地对其表示的复杂系统进行研究。
　　基于密度的图聚类算法通过搜索网络中局部稠密子图来识别社区，在社区发现中得到了广泛应用。然而，此类算法会产生大量无法划入社区的未聚类节点。针对此问题，本文对基于稠密子图的重叠聚类算法进行研究，主要包括以下两方面工作：
　　（1）针对无权无向网络，给出了一种基于稠密子图的软聚类算法(BDSG)。算法首先根据密度阈值搜索网络中的稠密子图得到中心社区；对无法加入中心社区的未聚类节点，定义了一种结点对社区的归属度，并以此为主要依据给出中心社区扩展策略，将未聚类节点分配至某些中心社区，得到最终的社区发现结果。该中心社区扩展策略确保算法可以发现网络中的重叠社区结构。与经典的基于密度的图聚类方法CPM、k-dense算法在5个真实网络数据集上的比较结果表明BDSG算法在模块性指标与时间效率方面体现了良好性能，同时中心社区扩展策略能在一定程度上提高CPM、k-dense等基于密度算法的聚类有效性。
　　（2）针对带权无向网络，给出了基于加权稠密子图的重叠社区发现算法（OCDW）。算法首先综合考虑网络拓扑结构及网络本身边权重信息，给出了一种网络中边权重的定义方法，进而给出点权重定义方式，选择权重最大的节点作为种子节点；定义了子图的社区适应度函数，将种子节点逐步扩展成为稠密子图作为中心社区；最终将未聚类节点按照归属度进行中心社区分配，通过合并优化过程得到最终社区发现结果。与k-dense、CPM、MCODE、HC-PIN、MDOS及BGLL算法在6个无权网络和3个带权网络的比较结果表明算法 OCDW在F度量、准确度、分离度、标准互信息、调整兰德系数、模块性及运行时间等方面均表现出较好的性能。

目录

第一章 绪论

1.1研究背景、目的和意义

1.2 国内外研究现状

1.3 主要研究内容

1.4 论文框架

第二章 理论基础

2.1图论基础知识

2.2相似性度量

2.2模块性

2.3本章小结

第三章 基于稠密子图的社区发现算法

3.1确定聚类个数

3.2节点对社区的归属度定义

3.3中心社区扩展策略

3.4实验结果与分析

3.5本章小结

第四章 基于加权稠密子图的社区发现算法

4.1 边权重定义

4.2种子结点选取

4.3种子结点扩展策略

4.4合并优化社区与未聚类结点处理

4.5算法描述

4.6实验结果与分析

4.7本章小结

第五章 结论与展望

5.1 结论

5.2 展望

参考文献

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

致谢

个人简况及联系方式

声明