复杂网络社区发现及其动态演化研究

论文摘要

复杂网络社区发现及其动态演化研究对于现实生活具有非常重要的研究价值,它引起了许多领域研究者的关注。本文提出了三个复杂网络社区研究的算法,第一个算法是改进后的多社区谱分解法,后两个算法引入“线图”来进行社区研究。针对传统的谱分解存在网络平分或者递归平分问题,提出一种基于点的分步骤的复杂网络谱分解的多社区算法(NSDA)。首先,该算法利用先验信息对复杂网络中的特殊结点和局部特殊结构进行预处理;接着,建立Laplace矩阵,对该矩阵进行谱分解,从而得到三个特定的特征值及其对应的特征向量,以三个特征向量的元素为坐标形成直角坐标系下的结点分布图;最后,通过坐标系中的结点分布图确定阈值,根据阈值来确定相应社区成员,从而构造出多个社区。本文用“线图”来改进NSDA算法,运用线图优势,提出了一种基于边的有覆盖的多社区的探测方法(ESDA)进行多社区发现。该算法有三个步骤:第一,复杂网络原始图转换成线图;第二,用一种基于点的分步骤的复杂网络谱分解的多社区算法(NSDA)来划分社区,近而得到线图的社区划分;第三,再把线图的社区划分转换为原始网络结构,得到有覆盖的社区划分,从而确定社区成员。本文再次把线图应用到社区动态演化研究,提出了一种基于线图的启发式的分层聚合的社区动态演化方法。该方法主要分为四步:首先,对一定比例的、低语义相似度的结点进行预处理;其次,对复杂网络的历史权值和瞬间权值按比例进行计算得到综合带权网络图;把综合的带权网络图转换成线图。再者,以一定比例的语义相似度高的节点为中心进行聚合,再把处理后的结点进行分层,确定社区成员。最后,依据模块度公式进行计算,合并能提高模块度的社区,寻找相对较佳的社区划分。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 社区研究的背景及意义
• 1.2 社区研究现状和热点
• 1.3 社区结构及其特点
• 1.4 本文要完成的工作
• 第二章 社区相关研究
• 2.1 社区研究的相关概念
• 2.2 复杂网络的典型模型
• 2.3 社区划分的常用算法
• 2.3.1 传统的社区划分方法
• 2.3.2 社会学方面的网络划分算法
• 2.4 常用聚类算法
• 2.5 相关研究工作
• 第三章 社区的划分算法
• 3.1 社区划分算法应该满足的基本条件
• 3.2 传统的谱分解二分法
• 3.3 复杂网络的概化算法
• 3.4 一种基于点的多社区谱分解方法
• 3.4.1 复杂网络的预处理
• 3.4.2 改进后的谱分解的多社区发现方法（NSDA）
• 3.4.3 据阈值确定社区成员或运用聚类算法
• 3.5 基于边的有覆盖的多社区的探测算法
• 3.5.1 线图在社区划分中的应用
• 3.5.2 点图到线图的转换规则
• 3.5.3 运用线图改造后的传统谱二分法
• 3.5.4 一种谱分解的有覆盖多社区探测方法
• 3.6 社区划分结果的评价---模块度
• 3.7 本章小结
• 第四章 社区研究算法的仿真实验
• 4.1 社区研究的实验数据标准化
• 4.2 实验工具
• 4.3 实验的设计方案与条件分析
• 4.4 实验结果与分析
• 4.5 本章小结
• 第五章 社区的动态演化
• 5.1 社区的动态演化常用算法
• 5.1.1 社区动态演化的存在两种观点
• 5.1.2 动态演化的常用算法
• 5.2 社区演化应用中线图的转化及其实验数据标准化
• 5.2.1 社区动态演化的线图转化及其评价
• 5.2.2 社区动态演化实验数据的标准化
• 5.3 语义相似度
• 5.4 一种基于线图的启发式分层聚合的社区动态演化方法
• 5.5 社区动态演化的仿真实验
• 5.5.1 实验设计方案
• 5.5.2 实验结果与分析
• 5.6 本章小结
• 第六章 总结与展望
• 6.1 本文的主要研究工作与贡献
• 6.2 本文存在的问题
• 6.3 展望
• 6.4 本章小结
• 参考文献
• 附录1 GML 数据集的操作代码
• 致谢
• 攻读学位期间发表的学术论文目录