大规模网络的社团发现与多层次可视化分析

论文摘要

大量的复杂系统可以被抽象地描述为复杂网络,如朋友关系网络、在线社会网络、交通运输网络、蛋白质交互网络、新陈代谢网络等等。随着对复杂网络研究的逐步深入,研究者们的注意力也逐渐从网络的宏观特征转向网络的中观特征。社团结构作为理解网络中观特征的一个关键因素,也因此成为了复杂网络研究的一个关键领域。尽管当前学者们已经提出了大量的网络分析算法,然而这些网络分析算法较高的时间复杂度与空间复杂度往往严重地制约了他们的应用。本文致力于研究低时间复杂度与空间复杂度的适合于分析海量数据的网络分析算法,特别是复杂网络研究的核心内容——社团发现算法。本文提出了两个近似线性的社团发现算法及一个快速平均最短路径估计算法,并分析了大量大规模真实网络中社团规模与社团质量的分布情况。此外,作者还开发出了一个通用网络分析平台用以分析实际复杂网络中的各类模式。本文的创新点主要体现在如下5个方面：1.提出了一个基于多解析度的模块度函数优化社团发现算法—MMO算法。MMO算法的时间复杂度是近似线性的,空间复杂度是线性的。在大量人工网络与真实网络中验证了MMO算法的效率与可靠性,并给出了该分布式算法在云计算平台上的运行结果。在本文的绝大部分试验中,MMO算法很好地平衡了运行效率与准确性两方面的问题,非常适合挖掘大规模网络中的社团结构。2.提出了一个时间复杂度近似线性,空间复杂度为线性的多解析度链接社团发现算法——MLP算法。通过调节MLP算法中社团质量的解析度参数,人们可以在不同粒度上探索社团可能存在的层次结构。在本文的绝大部分试验中,MLP算法的精确性优于当前使用最为广泛的链接划分算法(ABL算法),同时其精确性与运行速度也优于当前绝大多数社团发现算法。3.进行了大量大规模真实网络中社团质量分布的实证研究。发现社团的质量与社团的大小并不存在明显的相关性,并且在社团平均质量的分布图中并不存在以往研究所说的“V”型分布。本文还发现许多社团质量函数,如导通函数、膨胀函数与归一化分割函数等均存在著名的解析度问题。最后,本文提出了“平均网络社团描述’’(MNCP)这一社团质量分布函数,用以替代“网络社团描述”(NCP),从而更加合理地反映网络中社团的质量分布情况。4.在对真实网络进行大量实证研究后,本文首次发现这些网络中的节点与节点间距离分布非常符合具有不同均值与方差的正态分布。基于以上发现,本文提出一个快速的节点抽样算法用以精确估计网络的平均最短路径长度。实验表明该抽样算法效率极高,且在各类型大规模真实网络与人工网络均具有极高的准确性。5.开发了一个网络可视化分析平台NeSVA用以分析发现实际复杂网络中的各类模式。NeSVA的设计理念是实证研究驱动的,该框架包括了以下的分析策略：网络生成、统计分析、社团发现与网络可视化。基于以上策略,NeSVA融入了网络建模、链接预测、中介度分析、社团发现与网络绘制等技术。NeSVA不但是一个通用网络分析平台,同时也是一个能够较为系统地对比现有算法与新算法效果的验证平台。总体而言,本论文特点在于针对大规模复杂网络的社团发现与多层次可视化分析方面的诸多关键技术的研究。以上创新工作为人们提供了针对大规模网络的、从宏观到中观的、快速准确的分析方法。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1. 相关研究内容
• 1.2. 研究动机
• 1.3. 主要研究工作
• 1.4. 论文内容与结构
• 第二章 网络科学综述
• 2.1. 研究内容
• 2.2. 宏观分析方法
• 2.3. 中观分析方法
• 2.3.1. 密集子图发现
• 2.3.2. 非重叠社团发现算法
• 2.3.3. 重叠社团发现算法
• 2.3.4. 社团发现准确度测试
• 2.3.5. 基于社团的实证研究
• 2.4. 可视化分析
• 2.4.1. 大规模网络可视化算法
• 2.4.2. 网络可视化工具
• 2.5. 小结
• 第三章 基于节点划分的社团发现算法
• 3.1. MMO社团发现算法
• 3.1.1. 符号与相关定义
• 3.1.2. MMO社团发现算法
• 3.1.3. 算法复杂度分析
• 3.2. 算法对比与实验
• 3.2.1. 运行环境
• 3.2.2. 人工标准测试网络
• 3.2.3. 小规模的社会网络
• 3.2.4. 大规模网络
• 3.2.5. 分布环境中的社团发现
• 3.3. 大规模网络探索
• 3.3.1. 电话网络数据集
• 3.3.2. 大规模网络的中观可视化
• 3.4. 小结
• 第四章 基于链接划分的社团发现算法
• 4.1. MLP链接划分算法
• 4.1.1. 符号与相关定义
• 4.1.2. MLP链接社团发现算法描述
• 4.1.3. 算法复杂度分析
• 4.2. 算法对比与实验
• 4.2.1. 度量函数
• 4.2.2. 人工标准测试网络
• 4.2.3. 具有典型结构的人工网络
• 4.2.4. 小规模社会网络
• 4.2.5. 大规模实际网络
• 4.2.6. 实际应用
• 4.3. 进一步讨论
• 4.4. 小结
• 第五章 社团大小与质量分布
• 5.1. 社团质量函数
• 5.1.1. 符号与相关定义
• 5.1.2. 社团大小与质量分布
• 5.1.3. 质量函数的解析度极限
• 5.2. 社团质量分布与MNCP
• 5.2.1. 数据集与社团发现算法
• 5.2.2. 社团质量分布函数MNCP
• 5.2.3. 强社团节点比例（SCNF）分布
• 5.3. 小结
• 第六章 最短路径分布与平均最短路径估计算法
• 6.1. 节点间距离分布
• 6.1.1. 平均距离函数
• 6.1.2. 数据集
• 6.1.3. 节点-节点距离分布
• 6.2. 随机节点抽样算法
• 6.2.1. 随机节点抽样算法（RV）描述
• 6.2.2. 随机节点抽样算法（RV）的均值和方差
• 6.2.3. 抽样算法的效果对比
• 6.2.4. 模型生成的网络
• 6.3. 小结
• 第七章 网络可视化分析框架NeSVA
• 7.1. NeSVA的设计与架构
• 7.1.1. 数据模型与数据存储
• 7.1.2. 网络模型
• 7.1.3. 大规模网络的统计分析
• 7.1.4. 社团发现
• 7.1.5. 大规模网络可视化
• 7.1.6. 用户层相关功能
• 7.2. 网络可视化分析工具
• 7.2.1. 预处理与统计分析
• 7.2.2. 社团发现
• 7.2.3. 网络可视化
• 7.3. 小结
• 第八章 实际网络的实证研究
• 8.1. 北邮合作网络分析
• 8.1.1. 网络统计特征
• 8.1.2. 社团发现
• 8.2. 电信呼叫网络的Group CRM
• 8.2.1. Group CRM的框架
• 8.2.2. 用户群演化
• 8.3. VAST2008竞赛
• 8.3.1. 数据集
• 8.3.2. 带时序的链接关系
• 8.3.3. 结构等效的节点
• 8.4. 生命科学研究领域分析
• 8.4.1. 数据集与同被引关系网络
• 8.4.2. 研究领域发现
• 8.5. 小结
• 第九章 结束语
• 9.1. 论文总结
• 9.2. 未来的机遇与挑战
• 9.3. 下一步工作
• 参考文献
• 致谢
• 攻读博士学位期间发表论文