动态网络的结构相似性度量方法与应用研究

论文摘要

近年来,复杂网络成为了多学科交叉的热点研究领域之一,己有研究学者进行了大量深入地研究。复杂网络的结构相似性度量问题作为复杂网络领域一个重要的研究方向,在网络聚类、层次约简以及状态划分等实际应用中起着至关重要的作用。目前,大多数的网络结构相似性度量方法仅针对静态网络。但在实际场景中,网络的结构往往会随着时间的推移不断演化,网络的规模也会逐渐增大,如何快速且准确地衡量动态网络各时间片网络的结构相似性面临巨大的挑战。尽管,将动态网络的各时间片网络简单地视为静态网络也可以使用目前大多数的网络结构相似性度量方法。但是这样做不仅计算耗时,而且也没有考虑到动态网络各时间片沿着时间线彼此相关的结构特性。动态网络具有规模庞大和动态演化的显著特性,如何有效地利用各网络层的信息快速且准确地衡量动态网络各时间片网络间的结构相似性,是本研究的主要难点。本文在充分考虑动态网络结构特性的基础上,提出了两种快速且准确地衡量动态网络结构相似性的方法。首先,图的特征值可以从图的结构中提取重要的属性信息,因此利用谱特征表征图的结构特性是一个重要的研究思路。但是在规模庞大的动态网络中图谱特征的计算成本很高。为了解决这一问题,本文提出了一种基于矩阵扰动的动态网络结构相似性度量方法(PNSD)。该方法引入矩阵扰动理论结合网络扰动思想,通过初始时间片网络的谱特征快速更新得到各时间片网络的特征值,而无需在每个时间片网络中重新计算特征值,计算的复杂度与节点数量和变化的边数量呈线性相关。然后,通过分析动态网络的结构特性发现,在动态网络的演化过程中存在重要的拓扑结构信息,如骨干拓扑结构信息等。基于这一发现,本文在矩阵扰动理论的基础上引入包含动态网络重要拓扑结构信息的骨干拓扑信息网络作为基准网络,经过理论推导提出了一种基于骨干结构扰动的动态网络结构相似性度量方法(BPNSD),该方法有利于区分各时间片网络中不同结构变化的重要性程度。最后,在多个真实数据集和人工数据集上的实验结果表明,两种方法不但在规模庞大的动态网络中具有明显的速度优势,而且在实际分析应用中的实验效果优于现有基准方法。

论文目录

致谢

摘要

ABSTRACT

1 引言

1.1 研究背景

1.2 研究目的与意义

1.3 研究现状

1.4 主要研究内容

1.5 论文组织结构

2 相关理论基础

2.1 复杂网络

2.1.1 复杂网络的基本概念

2.1.2 复杂网络的表示形式

2.1.3 复杂网络的拓扑属性

2.1.4 复杂网络的基本模型

2.2 网络结构的相似性度量

2.2.1 网络比较基本概念

2.2.2 谱距离

2.3 扰动理论

2.3.1 矩阵扰动

2.3.2 网络扰动

2.4 本章小结

3 基于矩阵扰动的动态网络结构相似性度量方法

3.1 问题定义

3.2 总体研究思路

3.3 算法介绍

3.3.1 算法描述

3.3.2 算法流程

3.4 算法复杂度分析

3.5 状态划分实验及结果分析

3.5.1 任务介绍

3.5.2 实验平台介绍

3.5.3 基准方法介绍

3.5.4 数据集介绍

3.5.5 评价指标

3.5.6 实验设置

3.5.7 实验结果及分析

3.6 算法性能验证

3.6.1 人工数据集

3.6.2 实验结果及分析

3.7 本章小结

4 基于骨干结构扰动的动态网络结构相似性度量方法

4.1 问题定义

4.2 总体研究思路

4.3 基于连边重要性抽取骨干结构

4.4 算法介绍

4.4.1 算法描述

4.4.2 算法流程

4.5 算法复杂度分析

4.6 状态划分实验及结果分析

4.6.1 实验设置

4.6.2 实验结果及分析

4.6.3 参数敏感性分析

4.7 算法性能验证

4.8 本章小结

5 总结与展望

5.1 总结

5.2 展望

参考文献

作者简历及攻读硕士学位期间取得的研究成果

学位论文数据集

文章来源

类型: 硕士论文

作者: 王佳

导师: 武志昊

关键词: 动态网络,网络结构相似性,矩阵扰动,特征分解,状态划分

来源: 北京交通大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 北京交通大学

分类号: O157.5

DOI: 10.26944/d.cnki.gbfju.2019.000616

总页数: 66

文件大小: 4976K

下载量: 59

动态网络的结构相似性度量方法与应用研究

论文摘要

论文目录

文章来源

相关论文文献

猜你喜欢