大规模社交网络中社区发现评估方法研究

摘要

复杂网络能够很好的描述许多复杂系统，人们期望通过对复杂网络的研究和分析，揭示并掌握其统计特征、功能特性、演化规律等，从而能够更深刻的理解复杂系统，指导解决实际问题。在研究中人们发现复杂网络中存在社区结构，并且社区结构对于理解复杂网络的结构和功能非常重要，许多研究者因此投入到了社区发现及其评估方法的研究。
　　本文首先介绍了CPM社区发现算法、CoDA社区发现算法和BLMPA社区发现算法，三个各具特色的社区发现算法。CPM算法是第一个能够识别重叠社区的社区发现算法，CoDA算法不仅能够识别传统社区而且能够识别二分社区，BLMPA算法具有速度快和稳定性好的优点。
　　其次，用F-measure评估方法对这三个社区发现算法在虚拟网络下的社区划分结果进行了详细的评估，用Qa评估方法对这三个社区发现算法在真实网络下的社区划分结果进行了详细的评估。
　　最后，文章提出了一种基于节点对序列的重叠社区发现评估方法EOCNS（Evaluation of overlapping communities based on node-pairs’sequence）。在该评估方法中，提出了杂类社区和节点对序列概念。杂类社区保障单节点社区在评估时不被忽略，节点对序列保障重复节点在评估时不被忽略，以此确保评估时社区的完整性。借鉴F-measure标准中平均值F1，提出基于节点对序列的调和均值评估指标（FS），用于描述预测社区和真实社区整体结构之间的差异；提出重叠度之差（DOD）评估指标，用于描述预测社区和真实社区在重叠结构方面的差异。并用EOCNS评估方法对CPM社区发现算法、CoDA社区发现算法和BLMPA社区发现算法在虚拟网络下的社区划分结果进行了详细的评估。实验表明该评估方法可以很好的应用于重叠社区发现算法的评估。

目录

声明

第1章 绪 论

1.1 研究背景和意义

1.2 国内外研究现状

1.3 本论文的研究内容

1.4 本论文的结构安排

第2章 CoDA、CPM和BLMPA算法概述

2.1 CoDA社区发现算法

2.2 CPM社区发现算法

2.3 BLMPA社区发现算法

2.4 本章小结

第3章 F-measure评估方法对社区发现算法的评估

3.1 F-measure评估方法的实现

3.2 实验所用数据集

3.3 F-measure评估方法对CoDA算法的评估

3.4 F-measure评估方法对CPM算法的评估

3.5 F-measure评估方法对BLMPA算法的评估

3.6 本章小结

第4章 Qa评估方法对社区发现算法的评估

4.1 Qa评估方法的实现

4.2 实验所用真实数据集

4.3 Qa评估方法对CoDA算法的评估

4.4 Qa评估方法对CPM算法的评估

4.5 Qa评估方法对BLMPA算法的评估

4.6 本章小结

第5章 基于节点对序列的重叠社区发现评估方法

5.1 三个约束条件

5.2 问题定义

5.3 EOCNS评估方法的实现

5.4 ENCOS评估方法对CoDA算法的评估

5.5 EOCNS评估方法对CPM算法的评估

5.6 EOCNS评估方法对BLMPA算法的评估

5.8 本章小结

结论

参考文献

攻读硕士学位期间所发表的论文

致谢