基于社团强弱度的加权网络局部与重叠社团检测研究

摘要

复杂网络普遍存在于现实世界中，对复杂网络的研究已经渗透到各个学科领域。社团结构是复杂网络最重要的特征之一，通过研究社团结构可以获取现实网络的大量有用信息。目前，对于复杂网络的社团检测，研究者们提出了大量的算法，主要有图分割法、分级聚类法、基于模块度的方法和基于统计推断的方法等。这些现有的算法大多针对无权网络，然而很多现实网络本质上是加权网络，边的权重对网络的功能和特性有着重要影响，忽略权重信息会丢掉很多有用的信息。一方面，随着现实网络的规模不断扩大，拓扑结构日趋复杂，使得我们难以掌握整个网络的信息和结构，因此需要提出有效的局部社团检测方法来解决该问题。另一方面，实际网络中存在一些节点可以同时在多个社团中，研究者将这些节点称为重叠节点，对应的社团称为重叠社团，目前已有一些重叠社团检测方法，但大多属于全局算法且主要用于无权网络的检测，无法适用于检测规模巨大、结构复杂、全局信息不可知的加权网络的重叠社团结构。
　　因此，本文针对加权网络，进行了局部社团检测和重叠社团检测的研究。在局部社团检测方面，提出了一种简单快速的有效方法，在该方法中定义了节点划分到社团中的社团强弱度系数，扩展了p强度评价指标用于加权网络，通过计算机生成网络和现实网络进行了验证，并和现有的一些方法进行比较，结果表明该算法具有较低的时间复杂度，能准确检测网络的社团结构。在重叠社团检测方面，以加权网络的局部社团检测方法为基础，通过改进模块度函数，基于社团强弱度及模块度优化的思想，准确检测重叠节点，并且利用归一化社团属于度的计算方法得出重叠节点的模糊系数，最后对计算机仿真网络和现实网络进行实验分析，验证了算法的有效性和准确性，克服了已有重叠社团检测方法大多是针对无权网络全局信息的不足。
　　本文第一章研究了复杂网络社团检测的研究背景、意义和现状，介绍了本文的研究内容、创新点及全文的结构。第二章研究了复杂网络的拓扑特性和常用模型，社团的定义及社团检测算法的衡量指标。第三章针对加杈网络进行分析，提出了基于社团强弱度系数的局部社团检测方法。第四章结合本文局部算法的特性，定义了重叠节点的模糊系数，提出了一种加权网络的局部的重叠社团检测方法，并且对仿真网络和真实网络进行实验分析，与已有算法进行比较，验证本文算法的快速有效性。最后总结本文的研究成果，并进行了展望。

目录

声明

摘要

第一章 绪论

1．1 研究背景及意义

1．2 研究现状

1．2．1 无权网络的社团检测全局方法

1．2．2 无权网络的社团检测局部方法

1．2．3 无权网络的重叠社团检测全局方法

1．2．4 加权网络的社团检测方法

1．3 研究内容及创新点

1．3．1 研究内容

1．3．2 创新之处

1．3．3 技术路线

1．4 本文组织结构

第二章 复杂网络社团结构

2．1 复杂网络的基本概念

2．1．1 网络的图表示法

2．1．2 节点度、度分布及度相关性

2．1．3 最短路径、节点介数及聚类系数

2．2 复杂网络的结构模型

2．2．1 随机网络

2．2．2 小世界网络

2．2．3 无标度网络

2．2．4 加权网络建模

2．3 社团检测的要素

2．3．1 社团的定义

2．3．2 社团检测的评价指标

2．4 本草小结

第三章 加权网络的局部社团检测

3．1 代表性的相关研究工作

3．1．1 Clauset算法

3．1．2 Bagrow算法

3．1．3 LPA算法

3．2 基于社团强弱度的加权网络局部社团检测

3．2．1 社团强弱度系数

3．2．2 社团评价指标

3．2．3 算法步骤

3．3 实验检测与分析

3．3．1 仿真网络

3．3．2 现实网络

3．4 本章小结

第四章 加权网络的重叠社团检测

4．1 代表性的相关研究工作

4．1．1 CPM算法

4．1．2 FCM算法

4．1．3 COPRA算法

4．2 基于局部信息的加权网络重叠社团检测

4．2．1 模糊系数

4．2．2 模糊重叠模块度

4．2．3 算法步骤

4．3 实验检测与分析

4．3．1 仿真网络

4．3．2 现实网络

4．5 本章小结

第五章 总结和展望

5．1 总结

5．2 展望

参考文献

致谢

在学研究成果