Search Results

This chapter considers networks with an arbitrary degree distribution, in which the degrees of nodes are uncorrelated, including the degrees of the nearest-neighbour nodes. The two kinds of these networks are considered in detail. The first is the configuration model (a random graph with a given degree sequence) and the second is the static model (a random graph with a given sequence of desired degrees). The basic properties of these locally tree-like networks are discussed. The chapter also considers bipartite uncorrelated networks.

A discussion of the most fundamental of network models, the configuration model, which is a random graph model of a network with a specified degree sequence. Following a definition of the model a number of basic properties are derived, including the probability of an edge, the expected number of multiedges, the excess degree distribution, the friendship paradox, and the clustering coefficient. This is followed by derivations of some more advanced properties including the condition for the existence of a giant component, the size of the giant component, the average size of a small component, and the expected diameter. Generating function methods for network models are also introduced and used to perform some more advanced calculations, such as the calculation of the distribution of the number of second neighbors of a node and the complete distribution of sizes of small components. The chapter ends with a brief discussion of extensions of the configuration model to directed networks, bipartite networks, networks with degree correlations, networks with high clustering, and networks with community structure, among other possibilities.

A discussion of the site percolation process on networks and its application as a model of network resilience. The chapter starts with a description of the percolation process, in which nodes are randomly removed from a network, and of the percolation phase transition at which a giant percolating cluster forms. The properties of percolation on configuration model networks are studied, including networks with power-law degree distributions, and including both uniform and non-uniform removal of nodes. Computer algorithms for simulating percolation on real-world networks are also discussed, and numerical results are given for several example networks, including the internet and a social network.

Growth processes are a fundamentally different approach compared to probability-driven exponential models covered in earlier chapters. This chapter studies how growth rules can be designed to mimic processes observed in the real world, and how the process can be mathematically analyzed in order to obtain information about the likely topological properties of the resulting networks. The configuration (stub joining) model is described, including a careful discussion of how bias can be introduced if backtracking is used instead of restarting if stubs join to form a self or double link. The second class of models looked at is preferential attachment. The simplest variants of this are analyzed with a master equation approach, in order to introduce this technique as a way of obtaining analytical information about the expected properties of the generated graphs. Extensive references are provided to the numerous variants and extensions of both of these models.

Once network structures are established it is important to be able to reproduce in a computer the system we are studying. We can use models to predict the outcome of an experiment, or to understand the basic principles shaping the evolution of a given phenomenon; and in the case of networks we need procedures to generate them and to study the dynamics in relation to their topology. The aim of this chapter is to present the most used models in the field of complex networks, to illustrate the basic principles on which they are based (sometimes inspired by similar situations in different fields), and to provide the code for them. It deals with random graph generation, configuration models, gravity models, fitness model and the Barabási–Albert model.