基于k-shell分解的复杂网络节点重要度研究

摘要

随着科技的进步，人们对复杂网络的研究也日渐深入。复杂网络作为一个新兴学科已经融入到我们的日常生活，从具体的交通网、河流网到抽象的社交网、互联网等都属于复杂网络的研究范畴。复杂网络是一门交叉学科，涉及的领域包括物理学、生物学、社会学、管理学等。复杂网络的研究包括复杂网络结构、复杂网络特性、复杂网络节点重要度等。其中，复杂网络节点重要度的研究是这篇文章主要研究方向。复杂网络节点重要度的研究可以为人们生活带来很大的便利，比如人们对交通网络的研究可以帮助人们预防交通拥堵、交通事故等情况，人们对于社交网络的研究可以帮助人们切断重要传染源、预防流行疾病的爆发等。目前，复杂网络节点重要度的研究已有很多成果，比如度中心性、介数中心性、特征向量中心性、k-shell分解等多种评估节点重要度的算法。虽然人们提出了很多评估节点重要度的方法，但是这些方法在某些情况下都有很大的局限性，人们一直试图寻找更有效、更快捷、更精确的评估重要度的方法。本文首先介绍了复杂网络发展史和复杂网络的相关统计特性。然后介绍了多种节点重要度评估方法，主要包括度中心性评估方法、基于路径的评估方法、基于特征向量的评估方法、基于随机游走的评估方法和基于节点位置的评估方法。随后，提出了两种节点重要度评估方法：第一种，改进的加权k-shell分解方法；第二种，基于有效距离的k-shell分解方法。
　　本研究主要内容包括：⑴原有的加权k-shell分解方法在计算加权度方面还存在不足。于是，本文通过改进节点加权度的计算提出了一种改进的加权k-shell分解方法，且在六个真实的网络Blogs、Email、Net-science、Roget、USAir、Yeast分别进行了k-shell分解实验、SIR传染病实验和脆弱性实验来验证改进方法的性能。在SIR传染病实验中，模型达到平衡状态后，改进的k-shell分解算法比原有的的方法所得到的传染节点要多。由此可以看出，改进的k-shell分解算法排序得到的前30个节点的传播能力比原有的的方法要强。在脆弱性实验中，大多数网络的实验中改进方法排序得到的前30个节点的网络脆弱性之和比原有的方法排序得到的前30个节点网络脆弱性之和要大，这说明改进方法的排序得到的前30个节点对网络的影响力从总体上来说比原有的方法排序得到的前30个节点对网络的影响力要大，这进一步证实了使用改进算法排序所得到的节点的重要度要比原有的方法有一定的优越性。⑵传统的k-shell分解算法考虑的都是无权、加权的情况，但是没有考虑有效距离的因素。因此本文提出了基于有效距离的k-shell分解方法。为了验证提出方法的有效性和可行性，又在四个真实网络C.elegans、etscience、polblogs、USairport上分别进行了kendall相关性实验和SI疾病传播实验。celegans网络中，基于有效距离的k-shell分解实验结果明显优于其它两种方法。在netscience网络中经典k-shell分解比基于有效距离k-shell分解结果要好一些。在polblogs网络中基于有效距离的k-shell分解实验结果比其它两种方法优秀。在USAirport网络中，基于有效距离k-shell分解明显优于其它两种方法。综上所述，本文提出的基于有效距离的k-shell分解方法在大多数情况性比原有的加权k-shell分解方法和经典k-shell分解方法要优越。

目录

封面

声明

目录

中文摘要

英文摘要

第一章 绪论

1.1 引言

1.2 复杂网络概述

1.3 复杂网络节点重要度

1.4 本文组织结构

第二章 复杂网络节点重要度

2.1 基于节点度中心性的评估方法

2.2 基于路径的评估方法

2.3 基于特征向量的评估方法

2.4 基于随机游走的评估方法

2.5 基于节点位置的评估方法

2.6 本章小结

第三章 改进的加权k-shell分解算法

3.1 k-shell分解算法

3.2 加权k-shell分解

3.3 改进的加权k-shell分解

3.4 实验与分析

3.5 本章小结

第四章 基于有效距离的k-shell分解算法

4.1 有效距离理论

4.2 基于有效距离的k-shell分解方法

4.3 仿真实验与分析

4.4 本章小结

第五章 总结与展望

5.1 本文总结

5.2 未来工作展望

参考文献

发表文章目录

简历

致谢