基于距离动力学半监督社区检测方法及抗噪性研究

摘要

社区检测是理解、分析和掌控复杂网络系统要解决的重要问题。近年来学者们提出了诸多复杂网络社区检测方法，这些方法大多依赖于网路拓扑结构对节点进行无监督聚类，而忽略了客观存在的先验信息，如已知节点社区隶属关系或节点之间的社区关系等。
　　完全基于网络拓扑结构的无监督社区检测方法并不总是能获得较高的精度，特别是在社区结构模糊或者存在噪声信息的场景下。最近，诸多学者提出了一些半监督社区检测方法，这些方法试图融合先验信息来提高社区检测的性能和精度，但这些方法大多具有较高的时间复杂度，不适宜处理大规模的复杂网络。针对上述问题，本文提出了一种快速的半监督社区检测方法—SemiAttractor，通过把先验信息与网络拓扑结构融入到距离动力学中，在网络拓扑与先验信息的驱动下加速社区检测过程，降低噪声对社区检测过程的负面影响，能够较为准确的识别出社区结构。所取得的创新性成果主要如下:
　　(1)提出了基于距离动力学半监督社区检测方法。该方法的基本思想是:模拟质点间的动力学距离模型，复杂网络中的实体相当于质点，在动力学中各质点受力发生运动而改变之间的距离，最终各质点达到平衡的过程相当于复杂网络社区检测的过程。复杂网络中每条边的两个节点之间的距离受到它们直接连接、共同的邻居、各节点的独自邻居三方面的影响。本文的方法能够发现任意大小的社区，可以很好的识别在真实世界的网络中通常存在的小型社区或异常情况，在网络社区结构不明显的情况下，同样的先验信息较其他半监督社区检测方法具有更高的划分精度。分别在人工基准网络和真实世界网络中进行对比实验，验证了本文的方法有效性。
　　(2)提出了基于边的噪声扰动网络模型，通过删除真实链路和添加错误的链路方式构成基于边的噪声扰动网络模型。不改变网络节点平均度，符合真实网络中的噪声存在。在上述噪声扰动网络模型中尝试用本文提出的半监督社区检测方法和目前经典的半监督社区检测算法进行社区结构划分，从实验的角度分析了噪声规模对半监督社区检测方法的影响，并验证了本文中提出的半监督社区结构检测方法具有较高的抗噪性。

目录

摘要

第一章 绪论

1．1 研究背景及意义

1．1．1 复杂网络

1．1．2 网络社区结构

1．1．3 半监督社区检测

1．2 本文研究的主要内容

1．3 本文中用到的数学符号

1．4 本文的结构安排

第二章 相关研究

2．1 社区检测概述

2．2 无监督社区检测方法

2．3 半监督社区发现方法相关研究

2．2．1 基于成对约束的半监督社区检测

2．2．2 基于个体标签的半监督社区检测

2．4 本文用到的网络数据集

2．4．1 人工合成网络

2．4．2 真实世界网络

2．5 本文用社区发现评价标准

第三章 基于距离动力学半监督社区检测方法

3．1 引言

3．2 基于距离动力学半监督社区检测方法

3．2．1 预定义

3．2．2 半监督局部交互模式

3．2．3 SemiAttractor算法

3．3 实验与分析

3．3．1 实验所有网路详细信息

3．3．2 对比算法

3．3．3 如何使用先验信息

3．3．4 SemiAttractor与Attractor在时间步数t的对比

3．3．5 SemiAttractor与Attractor在精度上的对比

3．3．6 SemiAttractor算法与其它半监督社区检测算法在NMI值对比

3．4 本章小结

第四章 基于距离动力学半监督社区检测抗噪性分析

4．1 引言

4．2 噪声模型设计

4．3 半监督社区检测抗噪性仿真实验及分析

4．3．1 本章所用的网络数据集详细参数

4．3．2 实验数据对比分析

4．4 本章小结

第五章 总结与展望

5．1 本文工作总结

5．2 未来研究方向与展望

参考文献

致谢

攻读硕士学位期间的科研成果

声明