基于极大度数节点的复杂网络社区层次结构发现研究

论文摘要

社会网络分析（Social Network Analysis,SNA）是使用量化方法对社会网络进行分析,研究其中个体和网络特性的学科。从最初的规则网络,随机网络,再到现在的复杂网络,越来越多的来自不同领域的事物通过复杂网络的形式进行描述,由此产生的海量数据及其动态变化的网络结构已使得人们无法实时获知全局数据信息。对此,利用局部信息进行的社区发现技术已成为近年来社会网络分析的研究热点。与过去研究者仅注重从复杂网络中研究社区的平面拓扑特性不同,局部社区层次结构研究是对给定节点所属社区位于的社会层次的深入分析。通过分析社区空间结构,我们可以更好地确定节点的网络地位、了解复杂网络的结构和演变、以及社区在网络中的阶层。此外,社区层次研究还在用户行为分析、反恐追踪、病毒传播等方面有着广泛应用。但现时大多数社区层次结构发现思想都是在已有社区发现方法上的延伸,具有一定的局限性,且缺乏对社区层次结构合理性的有效评估,也无法发现同一层次上的子社区结构。为了解决上述问题,本文在深入探索局部社区发现方法的基础上,提出了反映节点在网络中聚集特性的极大度数节点的定义和基于极大度数节点的社会网络局部社区层次发现算法——基于极大度数节点的复杂网络社区层次结构研究算法（HCSD-MN算法）。本算法首先对社区层次进行横向发现:考虑了节点在网络中的作用,根据起始节点最近关联的的极大度数点数量划分出相应的主题社区;然后对社区层次结构进行纵向研究:构造出节点间相似度较高的起始节点集,并通过调整社区-分辨率变化级别,快速划分社区层次,进而发现社区的演变途径,特别是社区层次的跃变,以及对应的社区结构饱和状态。本文还提出使用NMI标准来评估HCSD-MN算法的有效性,并与其他算法进行比较,其中,NMI是目前被广泛用于社区层次发现方法检测的标准。实验证明,该算法不仅能获得正确的社区结构,而且能有效发现社区层次跃变,以及社区各层次中存在的小社区结构。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景和现状
• 1.1.1 概述
• 1.1.2 国内外研究现状
• 1.1.3 存在的问题
• 1.2 本课题的研究内容
• 1.3 本课题研究意义
• 1.4 本文组织结构
• 第二章 社区网络分析
• 2.1 复杂网络特征
• 2.1.1 小世界特性
• 2.1.2 无标度特性
• 2.2 社会网络分析
• 2.2.1 社会网络分析中的基本概念
• 2.2.2 社会网络的形式化表示
• 2.2.3 社会网络的分析方法
• 2.4 本章小结
• 第三章 社区结构研究
• 3.1 社区的相关认识
• 3.1.1 社区的概述
• 3.1.2 基于社区的用户模型
• 3.1.3 社区层次结构的相关概念
• 3.1.4 层次结构研究在社会网络分析中的应用
• 3.2 社区发现
• 3.2.1 全局社区发现算法
• 3.2.2 局部社区发现算法
• 3.3 社区层次结构发现
• 3.3.1 基于全局模块度的多分辨率方法
• 3.3.2 基于局部模块度的多分辨率方法
• 3.3.3 基于分辨率的MONC方法
• 3.3.4 现有算法的缺点
• 3.5 本章小结
• 第四章 基于极大度数节点的复杂网络社区层次结构算法
• 4.1 算法思想
• 4.2 相关定义
• 4.2.1 局部社区的形式化表示
• 4.2.2 极大度数点
• 4.2.3 起始节点集的构成
• 4.2.4 社区-分辨率变化公式
• 4.2.5 社区链接密度比
• 4.2.6 社区层次与社区内部链接密度比的关系
• 4.2.7 社区间的相似度
• 4.3 HCSD-MN算法描述
• 4.4 HCSD-MN算法的优点
• 4.5 本章小结
• 第五章 算法实现与实验
• 5.1 JUNG简介
• 5.2 算法实现
• 5.2.1 DataExtraction类
• 5.2.2 FindMDN类
• 5.2.3 HierarchyCommunityDetection类
• 5.2.4 CommunityOptimization类
• 5.2.5 GraphVisualization类
• 5.3 算法有效性评估方法
• 5.4 ZACHARY数据集实验
• 5.4.1 Zachary数据集介绍
• 5.4.2 实验结果与分析
• 5.5 DOLPHINS数据集实验
• 5.5.1 Dolphins数据集介绍
• 5.5.2 实验结果与分析
• 5.6 人工合成数据集实验
• 5.6.1 人工合成数据集介绍
• 5.6.2 数据预处理
• 5.6.3 实验结果与分析
• 5.7 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间取得的研究成果
• 致谢