基于标签传播的社团检测算法研究.pdf

目录

摘要I

AbstractIII

1绪论1

1.1研究背景及意义1

1.2国内外研究现状3

1.2.1社团检测算法3

1.2.2标签传播算法5

1.3研究内容及创新点7

1.4论文组织结构8

2相关理论基础与实验数据集10

2.1社团检测概述10

2.1.1复杂网络的定义及表示10

2.1.2社团的定义11

2.1.3复杂网络的统计特性11

2.2标签传播算法13

2.2.1标签传播算法描述13

2.2.2标签传播算法数学模型16

2.3评价指标18

2.3.1标准化互信息(NMI)18

2.3.2模块度(Q)18

2.4实验数据集19

2.4.1真实网络数据集19

2.4.2人工合成网络数据集20

2.5本章小结21

3基于三节点模体挖掘的标签传播算法22

3.1网络模体相关理论22

3.2TNM-LPA算法描述23

3.2.1挖掘三节点模体23

3.2.2计算权重24

3.2.3标签传播26

3.2.4TNM-LPA算法实例28

3.3实验结果及分析30

3.3.1真实网络的实验结果及分析31

3.3.2人工合成网络的实验结果及分析35

3.4时间复杂度分析38

3.5本章小结38

4基于密度峰值和最短路径的标签传播算法40

4.1密度峰值聚类相关理论40

4.2DPD-LPA算法描述41

4.2.1计算局部密度和相对距离41

4.2.2选择社团中心44

4.2.3标签传播46

4.2.4DPD-LPA算法示例47

4.3实验结果及分析48

4.3.1真实网络的实验结果及分析48

4.3.2人工合成网络的实验结果及分析53

4.4时间复杂度分析56

4.5本章小结56

5总结与展望58

5.1本文总结58

5.2展望59

参考文献60

致谢67

攻读学位期间发表的学术论著68

摘要

复杂网络是对现实世界中复杂系统进行建模得到的一种网络结构，在城市交通网络、

社交网络、生物学网络等领域中广泛存在。随着数字化时代的到来，这些复杂网络已成为

研究信息传播和揭示网络结构的重要工具。通过识别网络中的社团结构，能够探知网络的

拓扑特征，从而帮助优化网络布局和资源分配，社团检测为深入理解复杂网络的功能结构

及动态行为提供了有力工具，成为当下研究的热点。

标签传播算法是一种简单高效的社团检测算法，无需先验知识且适用于大规模网络，

同时时间复杂度近似线性。但其在节点更新顺序的选择和标签选择上存在随机性，导致算

法划分的结果不稳定且准确性较低。针对以上问题，本文提出了两种改进算法，主要研究

内容如下：

(1)为了解决原始标签传播算法的随机性强这一问题，本文提出了一种基于三节点模

体挖掘的标签传播算法。通过挖掘三节点模体来获取网络的高阶拓扑结构，并为避免高阶

连接模式下出现孤立节点的情况，与原始低阶拓扑结构合并来重建网络。本文基于三节点

模