基于半监督学习的复杂网络社区模型及改进算法

摘要

现代网络科学的发展进一步提高了人们对复杂网络的认识，而深层次的研究成为国际热点问题之一。社区识别作为复杂网络的一个典型事例，已经得到来自不同领域广大研究学者的关注，其中包括社会学、生物学、计算机科学、信息科学、数学统计学以及系统可以用图表示的相关学科。复杂网络最突出的特点是，社区结构作为其基本的功能单元能够很好地反映网络的性质和功能，这些性质功能使得社区识别具有重要的理论意义和应用价值。本文主要研究一类基于先验信息的半监督社区识别算法，具体工作为： 首先，在己知网络少量先验信息的条件下，提出一种改进的半监督标签传播社区识别算法。该算法兼顾了原始标签传播算法运算速度快的优点，并结合网络少量的先验信息来指导社区的识别过程；在标签传播过程中，提出一种顶点吸收邻居顶点标签的策略，大幅度提高了社区识别精度；在真实网络与人工生成网络上的实验均表明了该算法的有效性和近线性时间复杂度。 其次，通过预先标记少量顶点的标签并引入空模型修正拉普拉斯矩阵，提出一种基于离散电势理论和空模型修正的半监督社区识别算法。该算法将整个网络模拟成几个不同的静电场，并将其中的电势传递过程转化为组合荻利克雷问题，通过比较那些未标记顶点的电势得到网络的社区结构。真实网络与LFR人工生成网络上的实验结果均表明该算法能够准确地识别出网络的社区结构，特别是对于社区结构比较模糊的网络，该算法具有明显的优势。

目录

声明

第一章 绪论

1.1 研究背景及意义

1.2 研究现状

1.2.1 非重叠社区识别算法的研究现状

1.2.2 重叠社区识别算法的研究现状

1.3 研究动机

1.4 论文的主要贡献和结构安排

第二章 预备知识

2.1.1 图论知识

2.1.2 共轭梯度算法

2.2 常用符号及意义

2.3 实验数据集

2.3.2 真实网络

2.4 评价指标

第三章 基于先验信息的标签传播社区识别算法研究

3.1 问题描述

3.2 改进半监督标签传播社区识别算法

3.2.1 算法描述

3.2.2 时间复杂性分析

3.3.1 真实网络

3.3.2 人工生成网络

3.4 小结

第四章 基于离散电势理论和空模型修正的半监督社区识别算法研究

4.2 基于离散电势理论和空模型修正的半监督社区识别算法

4.2.1 算法描述

4.2.2 复杂性分析

4.3 实验结果

4.3.2 LFR网络

4.4 小结

第五章 总结与展望

5.2 展望

参考文献

攻读学位期间完成的论文

致谢