Random Graphs and Complex Networks
Random Graphs and Complex Networks
复制标题
DOI：
10.1017/9781316779422
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
R. Hofstad
中科院分区：
文献类型：
--
作者：
R. Hofstad
随着计算机时代的到来，人们对现实世界网络的基本性质越来越感兴趣。由于计算能力的提高，现在可以很容易地存储和研究大型数据集，这对大型网络的实证研究产生了深远的影响。正如我们在本章中详细解释的那样，许多现实世界的网络都是小世界，它们的度都有很大的波动。这些认识对网络科学研究具有根本性的影响。网络研究旨在理解为什么许多网络都具有这些迷人的特征，并研究这些网络在疾病传播，路由信息和顶点排名方面的属性。复杂网络的研究在科学中起着越来越重要的作用。这样的网络的例子是电力网和电信网络，社会关系，万维网和互联网，科学家的合作和引用网络，等等。例如，社交网络的拓扑影响信息或疾病的传播（参见，例如，Strogatz（2001））。互联网的快速发展和成功促进了对网络拓扑结构的基础研究。Barabási（2002）和Watts（2003）对Barabási、Watts及其合著者发现网络性质的简要描述。在纽曼等人（2006）的文章中，你可以找到一些原始论文，详细描述了现实世界网络的经验发现以及为它们发明的网络模型。纽曼（Newman，2010）的介绍性著作列出了网络的许多经验性质和科学方法。复杂网络的一个共同特征是它们都很大。因此，一个全局的描述是完全不可能的，研究人员，无论是在应用程序和数学，已经转向他们的本地描述：有多少顶点，通过哪些本地规则顶点连接到另一个，等等。概率论提供了一种非常有效的方法来处理网络的复杂性，并引导我们考虑随机图。最简单的随机图是Erdens-Rényi随机图
The advent of the computer age has incited an increasing interest in the fundamental properties of real-world networks. Due to the increased computational power, large data sets can now easily be stored and investigated, and this has had a profound impact on the empirical studies of large networks. As we explain in detail in this chapter, many real-world networks are small worlds and have large fluctuations in their degrees. These realizations have had fundamental implications for scientific research on networks. Network research is aimed to both to understand why many networks share these fascinating features, and also to investigate what the properties of these networks are in terms of the spread of diseases, routing information and ranking of the vertices present. The study of complex networks plays an increasingly important role in science. Examples of such networks are electrical power grids and telecommunication networks, social relations, the World-Wide Web and Internet, collaboration and citation networks of scientists, etc. The structure of such networks affects their performance. For instance, the topology of social networks affects the spread of information or disease (see, e.g., Strogatz (2001)). The rapid evolution and success of the Internet have spurred fundamental research on the topology of networks. See Barabási (2002) and Watts (2003) for expository accounts of the discovery of network properties by Barabási, Watts and co-authors. In Newman et al. (2006), you can find some of the original papers detailing the empirical findings of real-world networks and the network models invented for them. The introductory book by Newman (2010) lists many of the empirical properties of, and scientific methods for, networks. One common feature of complex networks is that they are large. As a result, a global description is utterly impossible, and researchers, both in the applications and in mathematics, have turned to their local description: how many vertices they have, by which local rules vertices connect to one another, etc. These local rules are probabilistic, reflecting the fact that there is a large amount of variability in how connections can be formed. Probability theory offers a highly effective way to deal with the complexity of networks, and leads us to consider random graphs. The simplest imaginable random graph is the Erdős-Rényi random