Random and scale-free networks
Figure 1. (a) The ErdösRényi random-graph model is constructed by laying down N nodes and connecting each pair with probability p. This network has N = 10 and p = 0.2. Since 45 connecting pairs can be formed, we expect the network to contain approximately 9 links. (b) The scale-free model assumes that the network continually grows by the addition of new nodes. A new node (red) connects to two existing nodes in the network (black) at time t + 1. This new node is much more likely to connect to highly connected nodes, a phenomenon called preferential attachment. (c) The network connectivity can be characterized by the probability P(k) that a node has k links. For random graphs P(k) is strongly peaked at k = <k> and decays exponentially for large k. (d) A scale-free network does not have a peak in P(k), and decays as a power law P(k) ~ kg at large k. (e) A random network is rather homogeneous, i.e. most nodes have approximately the same number of links. (f) The majority of nodes in a scale-free network have one or two links, but a few nodes have a large number of links; this guarantees that the system is fully connected. More than 60% of nodes (green) can be reached from the five most connected nodes (red) compared with only 27% in the random network. This demonstrates the key role that hubs play in the scale-free network. Both networks contain the 130 nodes and 430 links.