可导航网络模型的研究

摘要

近些年来，复杂网络研究方兴未艾，已成为一个跨学科的领域，覆盖范围包括了数学、计算机科学、社会科学和生物科学等。在这个领域中，近来大量的工作主要集中在复杂网络模型的发展上。这些复杂网络模型，能抓住现实网络中观察到的数据的一些定性的性质，并且可以帮助我们大致地推测出现实网络的组织方式。复杂网络具有三种重要的结构特性：小世界性、scale-free性和可导航性。反映这些性质的经典模型分别是：Watts-Strogatz模型、Barabási-Albert模型和Kleinberg模型。 本文从现实社会中的小世界现象出发，以网络的可导航性为视角展开对复杂网络的研究，内容涉及可导航网络的形成以及分散搜索算法等。 第一章，简要介绍了可导航网络的基本内容和研究背景，描述了一个著名的实验，该实验给出了社会网络“六度分隔”现象的首个实证性根据。第二章，讨论了由该实验产生的可导航网络模型，描述了经典的网络模型及其所引发的新颖的算法问题和图论问题。第三章，深入研究了网络可导航性的要素，并提出一个可导航的网络模型。第四章，从理论推理和分散搜索算法方面进一步研究新的增长的可导航网络模型。第五章，对本文所做工作进行了概括，并对下一步的研究指明了方向。 本文主要做了三方面的工作：第一，通过对网络可导航性的研究，在经典网络模型的基础上提出了一个新的增长的可导航网络模型，这个模型同时具有三种重要特征；并且在这个网络模型上使用贪婪算法时，它与Kleinberg模型具有相同的导航效果，有时甚至更加优越。第二，通过计算机模拟和理论推导证明我们所提出的新的网络模型是可导航的scale-free网络。第三，对各种分散搜索算法进行比较后得出，对于不同的网络拓扑结构分别有相应匹配的分散搜索算法，相对于最大结点度算法，增长的可导航网络模型更适合贪婪算法。 总之，本文成功建立了一个增长的可导航网络模型。然而，将其应用于通讯和信息产业还有很长的路要走。

目录

文摘

英文文摘

声明

第一章 绪论

1.1 小世界现象

1.2 复杂网络

1.3 网络的可导航性研究

1.3.1 国内外研究近况

1.3.2 可导航网络研究的重要性

1.4 本文研究的问题及成果

1.4.1 增长的可导航网络模型

1.4.2 理论证明与算法研究

第二章可导航网络

2.1 可导航网络的概念

2.2 Kleinberg模型

2.3 其他结构模型

2.3.1 分层模型

2.3.2 基于集合系统的模型

第三章增长的可导航网络模型

3.1 网络可导航性分析

3.1.1 可导航网络的特性

3.1.2 网络可导航的原因

3.2 增长的可导航网络模型

3.3 本章小结

第四章理论证明与分散搜索算法研究

4.1 理论证明

4.2 分散搜索算法的研究

4.3 本章小结

第五章结论与展望

5.1 结论

5.2 展望

附录

参考文献

作者在攻读硕士学位期间公开发表的论文

致谢