关键词:
图论
复杂网络
图不变量
特征值
节点中心性
倒距离矩阵
最大度矩阵
摘要:
近年来,随着科学技术的迅猛发展,人类社会进入了网络时代。今天,世界上充满了各类复杂网络,人们的生活与生产已离不开这些种类繁多的网络。网络时代使人与人之间的联系更加紧密,更紧密的连接意味着局部影响更容易扩散,从另一个角度讲,这表示了网络瘫痪、流行病等负面事件将更具破坏性。因此,日益网络化的人类社会需要对复杂网络的行为与特征有更深入的了解。随着复杂网络研究的不断深入,越来越多的学者关注到少数重要节点对网络整体功能的重大影响。网络的规模和结构在不断变化,快速有效地挖掘网络中的重要节点对各个领域都具有重要的现实意义。研究复杂网络,离不开图论中的相关理论。图论已广泛应用于各种复杂网络:交通网、社会经济网、通讯网、物流网络、传感器网络、因特网等领域。具体的网络可以抽象为由节点集和边集组成的图:节点集中的每个点可以表示为抽象的城市、交通枢纽和人;边集中的每条边可以抽象表示两个城市或交通枢纽之间的距离、两个人之间的关系等。这可以将网络问题转化为图形进行研究。
图不变量可以反映复杂网络的局部特征,它能有效地反映图的结构性质。在复杂网络中,拓扑指数与网络的整体特性密切相关,如抗毁性和鲁棒性。通过计算网络中节点的拓扑指数,并根据其数值重新排序其重要性,可以有效地评估复杂网络的可靠性,并保护重要节点。这些特征可用于对节点的重要性进行排序,从而识别复杂网络中的重要节点并对其进行保护。在图论中,它主要依赖于图的各种矩阵(邻接矩阵、距离矩阵、倒距离矩阵、倒距离(无符号)拉普拉斯矩阵等)特征值、特征向量、色数等来研究图的拓扑结构和代数性质。
本文利用图的倒距离矩阵、倒距离(无符号)拉普拉斯矩阵和广义倒距离矩阵对其拓扑性质进行研究,并在此基础上研究复杂网络拓扑结构的性质。本文主要研究结论如下:
(1)证明了倒距离拉普拉斯谱的一些性质,并导出几类图的倒距离拉普拉斯特征多项式。最后得出了给定色数下第二小和第三小的倒距离拉普拉斯特征值上界,并刻画了极值图。
(2)得到了倒距离无符号拉普拉斯矩阵谱展在各种图参数方面的一些界。还建立了图G的倒距离无符号拉普拉斯矩阵谱展和倒距离矩阵谱展之间的关系,并且获得了二部图的倒距离无符号拉普拉斯矩阵谱展的下界。
(3)本文由倒距离拉普拉斯矩阵和倒距离无符号拉普拉斯矩阵引出了广义倒距离矩阵,通过使用倒距离度和第二倒距离度给出了广义倒距离矩阵谱半径的上界和下界。并且给出了线图的广义倒距离矩阵的谱半径的界。
(4)介绍了几种经典的研究节点中心性的方法,针对现有节点重要性评估方法中节点移除可能导致网络拓扑结构发生变化的问题,提出了一种基于节点间相关性特征的网络节点重要性评估法。该方法提出利用倒距离能量、倒距离拉普拉斯能量和倒距离无符号拉普拉斯能量对节点中心性进行研究,并且定义的最大度矩阵变化法考虑了网络中不同节点之间的连接关系对其重要性的影响。针对已有的节点重要性评价方法,基于节点的移除可能导致网络拓扑结构发生变化,提出了一种利用节点间关联特性的通信网络节点重要性评价方法。该方法定义的最大度矩阵变化值法考虑了网络中不同节点间的联接关系对节点重要性的影响,利用删除节点后其对应的最大度矩阵的变化情况来度量所删节点的重要性。研究发现这种方法判断节点重要性优于传统的度中心性。