基于传播动力学的复杂网络社团检测方法研究

摘要

网络科学为解决现实生活中各种各样的复杂问题带来了新的视角。真实网络系统通常具有一些非平凡的拓扑特性，如重尾度分布、高聚集系数、同配异配性、社团结构和层级组织等。其中，社团结构是复杂网络最突出的特性之一，即网络中存在一些内部连接紧密的群组，而群组与群组之间的连接较为稀疏。社团结构的检测在物理学、生物学、社会学和计算机科学等领域具有重要的理论意义和广阔的应用前景，近年来吸引了很多不同领域研究者的关注。
　　本文介绍了社团检测的基本概念和方法，探讨了聚类意义以及如何测试和比较各种方法，讨论了社团检测在真实网络中的应用，并深入研究了三种基于传播动力学的社团检测方法。具有创新性的研究成果有以下三个方面:
　　1.基于网络随机游走动力学特征和信息熵最小化，提出了一种新的社团检测方法-LPAf。它基于以下思想:如果按照网络的社团结构对其节点进行二级编码，则网络上随机游走的平均描述长度（加权信息熵）将会显著减小。平均描述长度是网络划分的函数，对于同一个网络，较好的划分对应较短的平均描述长度。通过改进原始标签算法的多数投票规则，使平均描述长度在标签扩散过程中逐渐减小，可以精确且有效地检测社团结构。在合成网络和真实网络上的测试结果表明，LPAf具有较强的鲁棒性、较高的精确度，以及较低的时间复杂度。
　　2.基于社团内节点互相相似且连接紧密的特征，提出了一种高效的多分辨率社团检测方法MLPA。在MLPA中，相似的节点首先聚集到一起形成许多元社团。然后，这些元社团通过比较其内部凝聚力与外部吸引力，决定是否与其它元社团进行合并，这个过程一直进行直到所有元社团都满足定义。MLPA既不需要知道社团结构的任何先验信息，也不需要优化任何目标函数。在合成网络和真实网络上的测试结果表明，与其它几种流行的算法相比，MLPA具有较高的准确度和极低的时间复杂度。通过调节分辨率参数，可以观察不同尺度的社团，进而揭示网络的层级结构。为了进一步验证MLPA的有效性，利用它对大肠杆菌的转录调控网络进行了详细的分析，结果表明检测到的模块具有很强的结构和功能的一致性。
　　3.基于局域标签传播过程，提出了一种高效的动态社团检测方法-ALPA。许多真实网络是随时间演化的，而传统方法将它们视为静态的，即通过聚合一段时间内的数据而构建的，这种处理方式会丢失网络及社团的演化信息。如果希望实时跟踪网络的社团，静态方法通常非常耗时，因为即使网络的结构发生极小的改变，它们也必须重新计算整个社团结构。网络演化愈快，静态方法的耗时缺陷愈发明显。与传统方法不同，ALPA通过一个局域的标签传播过程来更新当前的社团结构。局域的标签传播过程有效利用了社团结构的历史信息，因此通常只会影响网络中很小一部分节点，这使得ALPA能够快速地响应网络结构的变化。在合成网络和真实网络上的测试结果表明，ALPA能够成功地识别并且追踪动态网络中的社团。此外，和其它常用方法相比，ALPA拥有更高的准确度和更低的时间复杂度。

目录

声明

摘要

第一章 绪论

第二章 理论基础与相关工作

2．1 网络基本概念

2．2 社团定义

2．2．1 自治定义

2．2．2 对比定义

2．3 社团检测方法概述

2．3．1 层次聚类

2．3．2 模块度优化

2．3．3 谱聚类

2．3．4 非负矩阵分解

2．3．5 统计推断

2．3．6 动力学方法

2．3．7 其它方法

2．3．8 局域社团检测

2．3．9 重叠社团检测

2．3．10 动态社团检测

2．4 社团检测评价

2．4．1 基准网络

2．4．2 划分比较

2．4．3 社团优度

第三章 基于随机游走路径压缩的社团检测算法

3．1 相关工作

3．2 算法介绍

3．3 结果分析

3．3．1 社团结构评价指标

3．3．2 合成网络测试结果

3．3．3 真实网络测试结果

3．3．4 时间复杂度分析

3．4 本章小结

第四章 基于多级标签传播的多分辨率社团检测算法

4．1 引言

4．2 方法

4．2．1 结构相似度

4．2．2 推广的社团定义

4．2．3 算法描述

4．2．4 时间复杂度分析

4．3 结果

4．3．1 合成网络

4．3．2 真实网络

4．3．3 分辨率参数分析

4．3．4 时间复杂度

4．4 小结与讨论

第五章 基于局域标签传播的自适应动态社团检测算法

5．1 引言

5．2 算法介绍

5．2．1 局域标签传播

5．2．2 网络拓扑结构改变对其社团结构的影响

5．2．3 自适应标签传播算法

5．2．4 时间复杂度分析

5．3 测试结果与分析

5．3．1 合成网络

5．3．2 真实网络

5．4 小结与讨论

6．1 工作总结

6．2 工作展望

附录

参考文献

在校期间发表的论文、科研成果等

致谢