复杂网络社团结构划分算法研究

论文摘要

社团结构是复杂网络普遍而又重要的拓扑属性之一，它具有团内连接紧密、团间连接稀疏的特点。揭示网络社团结构对分析复杂网络拓扑结构、理解其功能、发现其隐含模式以及预测网络行为都有十分重要的理论意义和广泛的应用前景。近年来，针对不同类型的大规模复杂网络，人们提出了许多划分社团结构的算法。本文在总结复杂网络的基本概念、社团结构定义的基础上，比较和分析了复杂网络领域一些具有代表性的社团结构划分算法，并展望了该领域的未来研究方向。然而，早期基于全局信息划分整个网络的社团结构的算法，很难适应于规模较大的复杂网络，而现实生活中有很多情况却只需要关注网络的局部社团结构，为此，需要寻找新的方法进行网络社团结构的划分。本文针对上述问题进行了深入研究。本论文所做的主要工作如下：首先，针对大型复杂网络信息不易获取、现有算法时间复杂度高的缺陷以及对划分节点局部社团的现实需求，我们提出了一种利用边连接强度改进局部模块度的局部社团划分算法——LCD-LinkS算法。该算法利用网络局部信息，以局部模块度作为标准贪婪地选择节点进行社团划分。该算法仅需要知道节点的局部信息，其时间复杂度为O （k2d4），而且划分的社团模块度高。其次，提出了节点和社团之间关系的度量方法，即节点贡献度。节点贡献度由两部分组成，节点和社团的连边数目和社团自身的稠密度。并在此基础上给出了一种比较型的社团结构定义。基于节点贡献度的社团定义和其他仅比较节点同社团连接频数的定义相比较，前者更符合无标度网络的特性。再次，针对基于社团吸引力的划分算法存在节点歧义性问题，提出了一种基于节点贡献度的快速社团划分算法——FCD-NodeC算法。该算法根据节点贡献度及社团的定义，通过网络社团自形成过程进行全局网络社团划分。该算法的复杂度为O （Lnd2/2），当d<<n时，算法具有线性复杂度。最后，针对LCD-LinkS和FCD-NodeC算法，在基准网络、经典的社会关系网络College Football network和Zachary karate club，以及未知社团结构的网络上进行了相关实验，实验结果表明，上述两个算法均能合理的划分网络中的社团结构。

论文目录

• 摘要
• Abstract
• 插图索引
• 附表索引
• 第1章 绪论
• 1.1 研究背景和意义
• 1.1.1 课题背景
• 1.1.2 问题描述
• 1.1.3 研究意义
• 1.2 本文主要工作和组织结构
• 1.2.1 本文所做工作
• 1.2.2 论文组织结构
• 第2章 相关工作基础
• 2.1 引言
• 2.2 复杂网络基本概念
• 2.2.1 网络的图表示
• 2.2.2 平均路径长度
• 2.2.3 聚类系数
• 2.2.4 度与度的分布
• 2.3 社团结构的定义和模块化函数
• 2.3.1 社团结构的定义
• 2.3.2 社团结构的定量化描述——模块化 Q 函数
• 2.4 社团发现算法
• 2.4.1 迭代法
• 2.4.2 层次聚类法
• 2.4.3 基于局部信息的算法
• 2.5 小结
• 第3章 一种改进局部模块度的社团划分算法
• 3.1 引言
• 3.2 边连接强度
• 3.3 改进局部模块度
• 3.4 基于改进局部模块度的社团划分算法
• 3.4.1 改进算法的基本思想
• 3.4.2 算法分析
• 3.4.3 算法举例
• 3.5 小结
• 第4章 一种基于节点贡献度的快速社团划分算法
• 4.1 引言
• 4.2 贡献度及社团定义
• 4.2.1 概念定义
• 4.2.2 示例分析
• 4.3 基于节点贡献度的快速社团划分算法
• 4.3.1 算法基本思想
• 4.3.2 算法分析
• 4.4 小结
• 第5章 实验及结果分析
• 5.1 实验数据集
• 5.1.1 人工数据集
• 5.1.2 经典网络数据集
• 5.1.3 常用的数据集
• 5.2 LCD-LinkS 算法实验及结果分析
• 5.2.1 人工网络分析
• 5.2.2 Football 网络分析
• 5.3 FCD-NodeC 算法实验及结果分析
• 5.3.1 人工网络分析
• 5.3.2 经典网络实验结果
• 5.3.3 算法性能比较
• 5.3.4 参数分析
• 5.4 LCD-LinkS 和 FCD-NodeC 算法的比较
• 5.5 小结
• 结论
• 参考文献
• 致谢
• 附录 A（攻读硕士学位期间所发表的学术论文目录）