复杂网络中的社团结构特性研究

论文摘要

现代的复杂网络科学极大促进了人们对现实复杂系统的理解。社团结构是复杂网络的一个极其重要的特性,社团结构就是一组其内部节点间联系非常紧密而与网络中的其他部分联系相对比较稀疏的节点的子集。复杂网络中的社团结构研究在社会学、生物学和计算机科学等多个领域都具有很重要的意义。近年来,针对不同类型的大规模复杂网络,人们提出了很多寻找社团结构的算法。本文首先对最新的社团结构划分算法进行了综述,给出了该领域重要的研究进展。其次,网络的社团结构特性本质上是由网络的几阶度分布决定一直是网络科学领域悬而未决的问题之一。为此,本文采用高阶随机重连方法和社团检测算法进行仿真实验对该问题进行了研究。最后,有针对性地提出了一种基于Louvain的改进新算法,可以用于寻找加权网络中具有重叠性和层次性的社团结构,并利用该算法分析了在线社会网络Wealink的各种特性,重点分析了Wealink社团特性的发展和演化。本论文所作的主要贡献如下:1综述了该领域最新的比较有代表性的一些寻找社团结构的算法,重点分析了基于模块度指标的改进算法,能够体现社团层次性和重叠性的新算法,衡量社团划分算法好坏的基准图。最后展望了该领域的未来研究方向。2在保持网络一阶、二阶和三阶度相关特性不变的情形下,利用随机重连方法和社团检测算法研究了复杂网络的社团结构特性。仿真分析发现保持网络三阶度相关特性不变的随机重连方法所构造的网络则可以很高精度地呈现原有网络的社团特性,从而表明网络的社团结构可以由三阶度相关特性有效地刻画(不需要更高阶)。本文的研究提供了一种网络构造方法,即利用三阶随机重连方法可构造出能够体现真实网络社团结构这一特性的随机网络。3提出了一种可用于寻找加权网络中社团结构特性的算法,使得新算法能够同时体现出网络中社团的层次性和重叠性,并能够在较短时间内处理大规模的网络数据。其次提出了一种基于微调策略分析动态网络演化中社团特性的算法,能够在网络规模变化不大的前提下对网络高效地进行社团特性的分析。从而为动态网络的社团研究提供了一种较好的途径。最后利用基准图对三种经典算法的优劣性进行了比较。4利用新算法对在线社会网络Wealink(http://www.wealink.com)的结构特性和动态演化进行了实证分析,其中包含了网络规模、社团结构、重叠性节点、聚类系数和度分布等特性,重点研究了若邻网中社团结构的动态演化。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 引言
• 1.2 研究任务与论文内容安排
• 参考文献
• 第二章 复杂网络中的社团结构算法研究概述
• 2.1 引言
• 2.2 社团研究中的一些基本概念
• 2.2.1 社团的定义
• 2.2.2 模块度指标
• 2.2.3 层次性
• 2.2.4 重叠性
• 2.2.5 计算复杂度
• 2.3 基于模块度指标的改进新算法
• 2.3.1 分辨率问题
• 2.3.2 模块度指标的拓展
• 2.3.3 双重相关模型性检测方法（DAMM）
• 2.3.4 基于谱图形分割法的改进算法
• 2.3.5 基于修正型微调策略的改进算法
• 2.4 基于层次性和重叠性的算法
• 2.4.1 层次性
• 2.4.2 重叠性
• 2.4.2.1 基于派系过滤算法的改进算法
• 2.4.2.1.1 加权网络中的派系过滤算法CPMw
• 2.4.2.1.2 有向网络中的派系过滤算法CPMd
• 2.4.2.2 基于GN 算法的改进算法
• 2.4.3 层次性和重叠性同时体现的算法
• 2.4.3.1 一种基于适应度函数局部最优化的方法
• 2.4.3.2 一种基于凝聚算法的新算法EAGLE
• 2.4.3.3 一种从边的角度考虑同时体现重叠性和层次性的算法
• 2.5 其他算法
• 2.5.1 一种简单的标注传播算法
• 2.5.2 对模块度优化问题本身的改进算法
• 2.6 评判基准图
• 2.7 动态网络社团结构分析
• 2.7.1 社团结构的鲁棒性分析
• 2.7.2 社团结构的演化分析
• 2.8 本章小结
• 参考文献
• 第三章 基于随机重连方法的社团结构特性分析
• 3.1 引言
• 3.2 网络的高阶度相关特性
• 3.3 随机重连的算法
• 3.4 寻找网络中社团结构的算法
• 3.5 社团结构特性与网络的高阶度相关特性关系研究
• 3.6 本章小结
• 参考文献
• 第四章 一种用于寻找加权网络重叠性和层次性的社团算法
• 4.1 引言
• 4.2 一种可寻找层次性的社团算法（Louvain’s Method）
• 4.3 基于LOUVAIN 算法寻找重叠性社团的改进算法
• 4.4 基于LOUVAIN 处理动态网络演化的改进算法
• 4.5 几种主要算法比较
• 4.6 本章小结
• 参考文献
• 第五章 在线社会网络 Wealink 特性分析
• 5.1 引言
• 5.2 在线社会网络Wealink 特性分析
• 5.2.1 在线社会网络Wealink 拓扑特性分析
• 5.2.2 在线社会网络Wealink 社团特性分析
• 5.2.3 在线社会网络Wealink 社团中重叠节点特性分析
• 5.2.4 在线社会网络Wealink 聚类系数特性分析
• 5.2.5 在线社会网络Wealink 度分布特性分析
• 5.3 本章小结
• 参考文献
• 第六章 总结和展望
• 6.1 结论
• 6.2 展望
• 致谢
• 攻读硕士学位期间已录用或已发表的学术论文