5 - Growing network models: the Barabási–Albert model and its variants

Summary

Many properties of real-world networks have been considered so far: the degree distribution, clustering, diameter, etc. However, the treatment of these properties has been rather ad hoc, i.e., each new property found has been incorporated into a simple static model. This approach has several disadvantages.

1. • We cannot be sure that the ensemble we use is the correct one for the problem. Usually, we try to take the largest or simplest ensemble having the desired properties. However, this may not apply to real-world networks.

2. • Real-world networks are usually dynamical, whether over a short time span, such as the Internet and WWW, or over a long (evolutional) time span. The classes of networks discussed so far are static, and actually are distinct for each N. No dynamical evolution of the network is incorporated.

3. • The equilibrium models provide no indication as to why the network received its observed properties. So far, we have treated these properties as given.

In this chapter, we attempt to address these problems by presenting models for network creation and evolution. These growth models reproduce several observed properties of real-world networks using simple ideas. Most of these models are based on the simple Barabási–Albert model that is presented next.