动态网络社团检测与演变分析方法的研究与实现

摘要

复杂网络能够刻画现实世界中的大量现象，对复杂网络的研究受到了人们越来越多的关注。在现实世界中，复杂网络的结构并不是一成不变的，而是随着时间的变化而不断改变，从而形成了动态网络。动态网络对于刻画随时间变化的自然和社会现象具有极大的潜力，对动态网络的研究具有很强的现实意义。
　　传统的动态网络社团发现算法往往分别对每一个时刻的网络快照进行聚类，然后分析相邻时刻社团之间的演化关系。这种方法的缺点之一就是没有考虑动态网络的时序特点，聚类仅仅基于单一时刻网络的结构，难以刻画社团的演化特性。基于这一观察，本文提出了一种局部优先的演化聚类方法LEOD以及一种基于标签传播的演化聚类算法DLPAE。对于LEOD，它针对某个时间点的快照网络，以网络中的每个结点为中心，首先在该节点的邻居网络上通过标签传播算法检测得到Ego社团。然后将这些局部Ego社团不断合并，从而得到网络的全局社团结构。在执行社团合并的过程中，通过引入社团相似度和关联度两个概念，并利用演化聚类框架，实现了局部优先的动态网络社团检测与演化分析。在DLPAE中，节点的社团标签由其邻居节点投票决定，且每个邻居节点对该结点都具有各自的影响力，我们称之为置信度。在聚类的过程中，节点的置信度的计算不仅要考虑当前时刻的网络结构，同时需要考虑前一时刻网络的结构，从而保证了聚类的时序特性。同时，对于每一个节点，DLPAE计算其节点的置信度方差，并按照节点置信度方差从大到小的顺序更新节点的标签，从而提高社团检测结果的稳定性与准确率。在DLPAE中，每个节点可以持有一个或者多个社团标签，该属性使得DLPAE能够同时发现动态网络中的重叠社团与非重叠社团。
　　本文在真实和人工数据集上进行了大量的实验来评估本文提出算法的性能。实验结果表明，LEOD能够有效地检测出动态网络中的重叠社团结构，发现网络中潜在的信息；而DLPAE能够同时检测网络中的重叠社团和非重叠社团；和同类算法相比，本文提出的算法表现出了较好的性能。

目录

封面

声明

中文摘要

英文摘要

插图索引

表格索引

符号对照表

目录

第一章 绪论

1.1 研究背景和意义

1.2 静态网络社团检测的研究现状

1.3 动态网络社团检测的研究现状

1.4 本文主要的工作和创新点

1.5 论文章节安排

第二章 问题描述

2.1 问题的描述

2.2 本章小结

第三章 局部优先的演化聚类算法

3.1 局部Ego社团检测

3.2 局部优先的演化聚类

3.3 本章小结

第四章 基于标签传播的演化聚类算法

4.1 静态网络社团发现算法DLPA

4.2 基于标签传播的演化聚类算法DLPAE

4.3 本章小结

第五章 实验结果与分析

5.1 实验数据集

5.2 评估指标

5.3 DLPA+性能评估

5.4 演化聚类算法性能评价

5.5 本章小结

第六章 总结与展望

6.1 总结

6.2 展望

参考文献

致谢

作者简介