【新书】随机图与复杂网络，508页pdf

目标。在这本书中，这是两本书中的第二卷，我们研究了复杂网络中随机图模型的局部极限、连接组件和小世界属性。第一卷描述了自1999年以来作为现实世界网络模型的随机图的初步研究。这些网络在元素连接数量等方面与经典随机图模型有很大的不同。结果，发明了许多新的模型来捕捉这些属性。第一卷研究了这些模型及其度结构。第二卷总结了这一激动人心时期关于所提出的随机图模型的局部结构、连通性和小世界结构的发展见解。第一卷旨在用于硕士课程，学生对概率论的特殊主题只有有限的先验知识，而第二卷描述了过去二十年来研究社区关注的更复杂的概念。第二卷旨在用于博士课程、阅读研讨会，或希望获得该科学领域结果和方法的全面概述的研究人员。第一卷包括许多基础知识，例如随机变量的收敛性、概率界限、耦合、鞅和分支过程，我们经常依赖这些结果。这一系列的第一卷和第二卷旨在自成体系。在第二卷中，我们简要重复了第一卷中讨论的随机图的某些基础知识，包括关键模型及其度分布的介绍。在第二卷中，我们力求提供详细而完整的证明。在我们不提供证明的地方，我们提供启发式方法以及大量的文献参考。我们还讨论了几种更新的随机图模型，旨在更现实地模拟现实世界的网络，因为它们包含了网络的有向性质、社区结构和/或空间嵌入。发展。随机图领域由Erdos和Rényi在1959-1960年开创于概率方法的背景下。Erdos和Rényi的初步工作引发了该领域的大量后续研究，最初主要在组合数学社区内进行。有关该主题的标准参考文献见Bollobás（2001）和Janson、Łuczak、Rucinski（2000）。Erdos和Rényi（1960）提供了Erdos-Rényi随机图中发生的各种相变的相当完整的图景。这一初步工作并没有旨在现实地模拟现实世界的网络。在1999年之后，由于大量现实世界网络数据集变得丰富可用，其结构在数学及各种应用领域中引起了极大的关注。这一点可以从该领域最早的文章之一——Barabási和Albert（1999）——获得超过40,000次引用中得到体现。从这一压倒性研究工作得出的主要结论之一是，许多现实世界的网络共享两个基本特性。首先，它们高度不均匀，不同的顶点在网络中扮演的角色非常不同。这一特性通过现实世界网络的度结构服从幂律来体现：这些网络是无标度的。这一现实世界网络的无标度性质促使社区提出了许多新颖的随机图模型，这些模型与Erdos-Rényi随机图不同，具有幂律度序列。这是第一卷的主要焦点。内容。在本书中，我们继续第一卷中的轨迹，现在我们关注顶点之间的连接结构。连通性可以总结为现实世界网络的两个关键方面：它们高度连通，通常具有一个包含大部分顶点（如果不是全部的话）的巨型组件；它们是小世界的，大多数顶点对通过短路径分隔。我们讨论了这些证明的可用方法，包括路径计数技术、分支过程近似、可交换随机变量和de Finetti定理。我们特别关注一种称为局部收敛的最近技术，它精确地说明了随机图“局部看起来像树”的说法。这本书由四部分组成。第一部分包括第1章和第2章，我们在第1章中重复了一些第一卷的定义，包括本书研究的随机图模型，即不均匀随机图、配置模型和优先附着模型。我们还讨论了随机图理论中的一些重要主题，例如幂律分布及其性质。在第2章中，我们继续讨论局部收敛，这是一种在随机图理论和本书中起关键作用的极其强大的技术。第二部分包括第3-5章，我们讨论了随机图模型中的局部极限和大型连通组件。在第3章中，我们进一步扩展了广义随机图的定义，以包括一般不均匀随机图。在第4章中，我们讨论了配置模型中的局部极限和大型连通组件，在第5章中，我们讨论了优先附着模型中的局部结构和连通性。第三部分包括第6-8章，我们研究了随机图的小世界性质，从不均匀随机图开始，继续讨论配置模型，最后讨论优先附着模型。第四部分包括第9章，我们研究了相关的随机图模型及其结构。在此过程中，我们给出了许多练习，应该有助于读者通过解决问题来更深入地理解材料。这些练习出现在每章的最后一节，在适用的情况下，我们在正文中适当位置引用它们。我们还在每章的倒数第二节提供了广泛的注释，讨论了与文献的联系和一些扩展。