基于图能量的节点重要性的度量方法研究

论文摘要

在网络分析中,度量节点中心性早已成为一个关键问题,它决定了网络中节点的重要性。复杂网络中的重要节点往往在网络的结构和功能上起着举足轻重的作用。因此,识别网络中的重要节点是至关重要的,并且有广泛的实际应用价值,如控制流行病的爆发、宣传电子商务产品、预测流行科学出版物、防止电网或网络的灾难性故障等。对于无权网络,已经存在很多度量节点重要性的经典算法,例如度中心性、接近中心性、介数中心性、PageRank算法和Coreness等。图能量是测定图中所包含的结构信息的一种度量方法,它已经广泛应用于许多领域,包括生物学、化学和社会学。图能量也可以用来衡量节点重要性,即一个节点重要性等价于移除这一节点前后图能量的变化量。本文中,将基于图能量这一概念,引入两种新的节点重要性度量算法。第一种方法称之为Quasi-Laplacian中心性。我们将会根据quasi-Laplacian矩阵引进一种新的图能量——Quasi-Laplacian能量,并基于这一能量构造一种新的节点中心性度量方法——Quasi-laplacian中心性。该算法的中心思想是利用网络G删去某个节点v后,Quasi-Laplacian能量的变化量来反映这一节点的重要性。首先,我们证明移除任何一个节点后Quasi-Laplacian能量的变化量都为正值。其次,证明网络G的Quasi-Laplacian能量不仅与原网络G的边数有关,而且与它对应线图L（G）的边数有关。因此,节点v的Quasi-Laplacian中心性不仅考虑了节点在原图G中的位置,而且考虑了它在线图L（G）中的位置。我们进一步研究了新节点中心性方法的有效性和鲁棒性,把这一方法应用于3个经典的社会网络和14个来自其他领域的网络,并将实验结果与常用的SIR评价模型比较,有力地证实了新中心性方法的效用。第二种方法称为hyper-Zagreb中心性。因为hyper-Zagreb指标常常用于刻画分子间的能量关系,因此我们把这一指标推广到图能量领域,提出一种新的节点中心性度量方法—hyper-Zagreb中心性,并将其应用于衡量节点重要性。我们发现节点v的hyper-Zagreb中心性不仅与它自身的度和邻点的度有关,而且与它邻点的邻点有关。同样将该中心性在实际网络上进行实验,验证了其效用。特别指出的是,Quasi-Laplacian、hyper-Zagreb中心性都与图的参数直接相关,因此运算比较便捷。尤其是Quasi-Laplacian中心性与其他方法（除度中心性）相比有更低的时间复杂度,因此可以应用于大型网络。

论文目录

• 中文摘要
• 英文摘要
• 符号说明
• 第一章 绪论
•   1.1 研究背景和研究意义
•   1.2 基础知识
•     1.2.1 邻接矩阵和度矩阵
•     1.2.2 Quasi-Laplacian能量
•     1.2.3 线图
•   1.3 度量节点重要性的经典算法
•   1.4 评价模型:SIR模型
•   1.5 论文的主要工作及结构
•     1.5.1 论文的主要工作
•     1.5.2 论文的结构
• 第二章 Quasi-Laplacian中心性
•   2.1 基于图论的Quasi-Laplacian能量
•   2.2 Quasi-Laplacian中心性
•   2.3 实验
•     2.3.1 两个简单的实验
•     2.3.2 经典数据集
•     2.3.3 更多数据集
• 第三章 Hyper-Zagreb中心性
•   3.1 Hyper-Zagreb指标
•   3.2 Hyper-Zagreb中心性
•   3.3 实验
•     3.3.1 经典数据集
•     3.3.2 更多数据集
• 第四章 时间复杂度分析
• 第五章 结论与展望
•   5.1 结论
•   5.2 展望
• 参考文献
• 致谢
• 个人简历
• 学位论文评阅及答辩情况表

文章来源

类型: 硕士论文

作者: 马悦

导师: 亓兴勤

关键词: 节点中心性,图能量,能量,指标,时间复杂度

来源: 山东大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 山东大学

分类号: O157.5

总页数: 57

文件大小: 3984K

下载量: 51