12 - Network Processes

Summary

Until now, we have considered “static” (in terms of the number of vertices) models of real-world networks only. However, more often, the networks are constructed by some random “dynamic” process of adding vertices, together with some new edges connecting those vertices with the already existing network. To model such networks is quite challenging and needs specific models of random graphs, possessing properties observed in a real-world network. One such property is that often the degree sequence exhibits a tail that decays polynomially, as opposed to classical random graphs, whose tails decay (super)exponentially. Grasping this property led to the development of, so-called, preferential attachment models. After the presentation of basic properties of the preferential attachment model, we conclude the first section with a brief discussion of its application to study the spread of infection through a network, called bootstrap percolation. The last section of this chapter is devoted to a generalization of the preferential attachment model, called spatial preferential attachment.