基于社区性质的社区发现和基于局部视图的社区演变追踪研究

摘要

网络是对许多现实系统的一种既简单又形象的表达方式，对网络进行研究有助于人们理解真实世界。许多现实网络，比如社交网、作者合作网、蛋白质交互网、万维网等，都具有一种重要的中观结构——社区结构。一个网络中的社区结构是网络中的社区划分，即将节点划分到不同的社区，社区内节点连接更加紧密，而社区之间的连接相对稀疏。社区发现能够探知网络的隐藏结构，发现网络的潜在信息，对认识和理解网络的拓扑结构起着重要的作用；社区演变追踪能够探知社区的改变情况，揭示网络的内在动向，对捕捉和掌握网络的发展趋势起着不可忽略的作用。因此，对社区发现和社区演变追踪开展研究具有重要的意义。
　　在社区发现方面，本文研究了个人社交网络中的社交圈发现和现实大规模网络中的社区发现，提出了相关的社区发现算法。在社区演变追踪方面，本文研究了动态网络在每个时刻的社区发现和相邻时刻的社区结构匹配，提出了相关的社区演变追踪算法。本文的主要工作如下：
　　1.针对个人社交网络中的社交圈发现问题，提出了基于加强链聚类的社交圈发现算法。社交圈发现属于社区发现，本文在对真实社交圈分析的基础上，将节点属性信息和网络结构信息整合到边上，提出了一种加强链聚类算法。实验结果表明，与目前的社交圈发现算法相比，所提出的算法可以更快速更准确地完成个人社交网络中的社交圈发现。
　　2.为了能更加准确地发现现实大规模网络中的社区，提出了两种基于加权策略的社区发现算法。首先研究了大规模网络中的真实社区结构，发现了社区结构具有的一种性质；然后基于此设计了一种加权策略，并在此加权策略的基础上提出了两种社区发现算法。在现实网络上的实验结果表明，所提出的基于加权策略的算法可以更准确地发现真实社区。
　　3.提出一种基于加权局部视图的社区发现算法。该算法结合分析到的社区性质探索节点对社区结构的局部视图，然后整合节点的局部视图得到社区结构。在现实网络上的实验结果表明，所提出的基于加权局部视图的算法在发现大规模网络中的社区时存在效率优势，且能更准确地发现真实社区。
　　4.在社区演变追踪方面，提出了一种增量式的局部动态社区演变追踪算法。该算法分两个步骤：1）为了快速发现动态网络在每个时刻的社区结构，该算法在每个时刻只关注网络中发生变化的节点，通过探索变化节点的局部视图对社区结构进行更新；2）为了快速地匹配相邻时刻的社区结构以追踪社区的演变行为，该算法基于变化节点在变化前后的社区归属关系，构建一个部分社区演变图，并通过搜索部分社区演变图对社区的演变行为进行追踪。实验结果表明，当网络变化平滑时，所提出的局部动态社区演变追踪算法能更快速地完成社区演变追踪；当网络变化剧烈时，所提出的算法也具有一定的优势。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪 论

1.1 研究工作的背景与意义

1.2 国内外研究历史与现状

1.3 本文的主要研究内容

1.4 本论文的结构安排

第二章 相关理论基础

2.1 网络及其性质

2.2 社区发现算法概述

2.3 社区演变追踪算法概述

2.4 网络数据

2.5 评价指标

2.6 本章小结

第三章 基于加强链聚类的社交圈发现

3.1 社交圈发现

3.2 社交圈模型的建立

3.3 相似性度量

3.4 加强链聚类算法

3.5 实验与分析

3.6本章小结

第四章 基于加权策略的社区发现

4.1 数据集

4.2 社区性质的分析

4.3 加权策略

4.4 加权的标签传播算法

4.5 加权的Louvain算法

4.6 实验与分析

4.7 本章小结

第五章 基于加权局部视图的社区发现

5.1 基于个性化PageRank向量的局部社区发现算法

5.2 基于加权个性化PageRank向量的局部社区发现算法

5.3 种子选取

5.4 基于加权局部视图的社区发现算法

5.5 时间复杂度分析

5.6 实验与分析

5.7 本章小结

第六章 基于局部视图的社区演变追踪

6.1 动态网络表示

6.2 局部动态社区演变追踪算法

6.3 实验与分析

6.4 本章小结

第七章 总结与展望

7.1 研究内容总结

7.2 未来工作展望

致谢

参考文献

攻读博士学位期间取得的成果