社会网络中基于社区引力的社区结构发现算法

摘要

随着互联网和移动通信技术的进步，在线社交网络的兴起和飞速发展，大数据时代已经到来。人们的生活、工作与在线社交网络间的关系变得密不可分，这些在线社会网络其实是实际社会网络的缩影。因此，对社会网络进行研究，发现其网络结构特征，有助于深入了解社会网络系统，极具现实指导意义。近年来，社会网络中社区结构发现算法的研究已成为国内外研究的热点，如何对社区结构进行快速准确的划分一直是困扰各国专家学者的难题。随着研究的深入，研究发现社会网络更应该呈现出一种重叠性的结构，也就是说网络的节点可能同时属于多个社区。本文的最大创新来自提出社会网络中节点与节点之间存在引力关系以对应于真实世界里物体间的万有引力，并给出了其引力大小的计算方法。本文分别对社会网络中的非重叠社区发现算法和重叠社区发现算法做了相关研究，主要工作如下：
　　(1)在非重叠社区发现方面，鉴于谱聚类中相似函数的选取仍是一个亟待于解决的难题，我们对现有的边介数定义进行了拓展，提出了虚边介数来衡量网络中没有直接边相连的两点的关系，从而构造新的边介数相异度矩阵，然后应用于谱聚类算法中。为了对网络中的争议节点进行正确划分，我们提供了一个比较节点社区引力的修正步骤。然后，在计算机生成随机网络和三个真实世界网络模型中进行实验，我们的算法均取了满意的效果。
　　(2)在重叠社区发现方面，研究工作主要在于利用局部社区引力的概念从非重叠社区结构中发现重叠节点。我们采用了现有的两种能应用于大规模网络的算法Infomap和Louvain划分的非重叠社区。在人工网络和不同规模的真实世界网络中进行实验，大量的实验结果都充分说明了本章算法的有效性，并且该算法仅含有一个随着网络规模增大而呈线性增长的低计算复杂度。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪论

1.1 研究背景

1.2 国内外研究现状

1.3 研究意义

1.4文章结构和研究内容

第2章 社会网络相关理论与社区结构发现算法

2.1 社区网络基本理论

2.2 社区结构评价指标

2.3社区发现算法

第3章 基于边介数相异度矩阵的谱聚类算法

3.1 算法储备知识

3.2 基于边介数相异度矩阵的谱聚类算法描述

3.3 方法论

3.4计算机生成网络实验仿真

3.5真实网络实验仿真

3.6 小结

第4章 基于局部社区引力的重叠社区发现算法

4.1 基于LCG的重叠社区发现算法提出的背景

4.2算法相关定义

4.3 基于LCG的重叠社区发现算法描述

4.4 方法论

4.5 LFR人工合成网络实验

4.6 真实世界网络实验

4.7 小结

第5章 总结与展望

5.1 论文总结

5.2 研究展望

参考文献

致谢

个人简历、在学期间发表的学术论文及研究成果