复杂网络中节点重要度评估算法的研究

摘要

近年来，复杂网络系统已经融入到人们生产生活的方方面面。作为一个新兴且活跃的科学研究领域，复杂网络早已引入到在现实世界网络的实证研究。目前，在计算机科学、社会科学、生物科学、管理科学等众多领域得到了越来越多的人的重视。一方面，伴随着复杂网络的不断发展，人类的生产生活质量有了大幅度的提高和升华，并且为之带来了极大的便利。但是另一方面，复杂网络系统的运行也对人类的生产生活带来了一定的负面冲击，比如疾病的快速传播、大面积的停电事故、以及交通运输的瘫痪等等。因此，我们需要对各种复杂网络系统有着更为深刻的认识和分析，以便对可能造成的负面影响进行预测、避免、控制等等。在众多复杂网络研究方向中，节点重要度评估已经成为其研究发展中一个较为深远的方向。
　　虽然目前已经许多的中心性方法被提出来度量节点的重要度，但不同的中心性在各个方面或多或少都存在着一定的不足和局限性。由于不同的中心性的机制不同，而且有着不同的不足，因此，当对同一个网络使用不同的中心性进行节点重要度评估时，往往会得到不同的结果。为此，我们有必要对现有的中心性进行改进，从而能全面有效的对复杂网络节点重要度进行评估。
　　本文主要提出了三种不同的中心性算法对节点进行重要度评估。首先将有效距离引入节点最短路径的应用中，用其代替传统的测地线和地理距离来衡量网络节点的距离，并利用改进后接近中心性对节点进行重要度评估。然后提出了一种基于TOPSIS算法的多属性决策模型的中心性算法，该算法将多个中心性作为多属性进行融合来评估节点重要度。最后，我们基于失效模式及影响分析模型，将复杂网络的节点信息进行建模来刻画发生频度、严重程度、检测难易程度，并通过风险顺序数来对节点进行重要度评估。为了体现出本文提出的算法的有效性和实用性，我们都将这些算法应用到真实的网络中进行对比实验。
　　本文的工作主要包括以下几个方面:
　　(1)提出基于有效距离的接近中心性算法
　　在真实的网络中，往往会有孤立节点和单向边，这会导致部分节点对的距离是无穷大，在此情况下则利用传统接近中心性来评估节点重要度是无效的。针对此问题，我们引入有效距离，来代替传统的测地线和地理距离来度量网络节点的距离。该模型不但解决了传统接近中心性失效的问题，还能广泛应用于加权网络中，而且更加合理的表示了网络节点信息流的传输过程。
　　(2)提出基于TOPSIS模型的中心性算法
　　TOPSIS算法是一种被广泛应用的多属性决策算法，它能有效地融合多个有差异的属性，并得出一组接近理想最优解的排序。由于各种中心性算法都存在着种种缺点，并且不同中心性会产生不同的评估结果，因此我们认为有必要提出一种折衷的算法来融合这些差异以及克服单一中心性所存在的缺点。我们将度中心性、接近中心性和介数中心性这三个最为基础的中心性作为多个属性引入到TOPSIS多属性决策模型中，将融合后的中心性作为网络节点的重要度评估算法。该算法不仅解决了这三个中心性各自存在的缺陷，还有效地将它们的差异进行折衷融合。并且首次将工程评估中的TOPSIS算法引入到复杂网络系统中，对跨学科领域研究有着积极的影响。
　　(3)提出基于失效模式及影响分析模型的中心性算法
　　失效模式及影响分析是一种可靠性设计的重要方法，它通过由发生频度、严重程度、检测难易程度得出的风险顺序数来对模式进行评估。我们利用网络的结构和节点的信息进行建模来刻画发生频度、严重程度、检测难易程度。我们认为如果一个节点的入度越大，则表明其他节点发生故障时影响到该节点的机会就越大，那么这个节点发生“失效”的概率就越高。同时，倘若一个节点到其他所有节点的有效距离越短，则表明该节点失效后影响的传播就越广，那么这个节点失效的严重程度就越大。在此模型中，我们定义了网络节点的熵的概念。因为信息熵表示的是系统或者个体的不确定性，因此我们认为如果一个节点的熵值越大，则这个节点在网络中所处的结构也就越复杂，那么对这个节点进行失效探测的难易程度也就越难。最后，我们根据新的模型得出的风险顺序数对节点进行重要度评估。风险顺序数值越大，则节点越重要。

目录

声明

摘要

第一章 绪论

1．1 研究背景和意义

1．2 国内外研究现状

1．2．1 复杂网络研究现状

1．2．2 失效模式及影响分析技术研究现状

1．3 本文的研究方法和内容

1．4 论文组织结构

第二章 相关理论与技术基础

2．1 复杂网络基本静态几何特征

2．1．1 网络的图表示

2．1．2 网络直径与平均距离

2．1．3 集聚系数

2．1．4 真实网络统计性质实例

2．2 复杂网络节点中心性理论

2．2．1 度中心性

2．2．2 介数中心性

2．2．3 接近中心性

2．2．4 特征向量中心性

2．2．5 流介数中心性

2．3 失效模式及影响分析理论

第三章 基于有效距离的接近中心性研究

3．1 有效距离理论

3．2 基于有效距离的接近中心性

3．2．1 算例

3．3 数值实验与分析

3．3．1 实验数据

3．3．2 Susceptible-Infected疾病传播模型

3．3．3 实验与分析

3．4 本章小结

第四章 基于TOPSIS模型的节点重要度识别算法研究

4．1 TOPSIS算法

4．2 基于TOPSIS模型的节点重要度识别算法

4．2．1 传统中心性问题描述

4．2．2 TOPSIS中心性评估算法

4．2．3 算例

4．3 数值实验与分析

4．4 本章小结

第五章 基于FMEA的节点重要度识别算法研究

5．1 网络节点的失效模式及影响分析模型

5．2 数值实验与分析

5．3 本章小结

第六章 总结与展望

6．1 本文工作总结

6．2 未来工作展望

参考文献

发表文章目录

简历

致谢