Next: Modularity, motifs and other Up: Network models Previous: Network models
Small world and scale-free networks
Starting with a large set of elements, it is possible to connect them up in a number of different fashions. At one extreme, each element may be connected to its nearest spatial neighbours, leading to a network known as a regular lattice. At the other extreme, pairs of elements may be connected together at random, leading to the type of random networks investigated by Kauffman [67] (see Section 4). In the absence of any more detailed data on the architecture of biological networks, the random approach seemed reasonable. In addition, it allowed the use of a number of results from graph theory concerning the properties of random graphs. Real networks however, whether they be social networks, telecommunication networks or genetic networks, are not connected at random, and two recent models seem to offer a more representative model [64,139].
Two related models, small world networks and scale-free networks have recently been proposed to address this gap. Small world networks [141,140] are obtained when a small portion of the links in a random lattice are randomly rewired (see Figure 12). The resulting networks have two important properties. Firstly, the average distance between any two nodes in a network is very short, as it is in a randomly connected network. Secondly, the clustering coefficient, the number of nodes whose neighbours are also neighbours of each other, is high. It turns out that this model is a reasonable description of a number of naturally occurring networks [120,116].
![\begin{figure}
\begin{center}
\includegraphics[scale=0.7]{figures/sw}
\end{center}
\end{figure}](_img35.png) |
of the links. When all of the links are rewired, the result is a random network (right). For intermediate values of
The closely related scale-free network model [13] is characterised by a power law decay in the probability of a node interacting with k other nodes, according to
P(k) 
k-
. This structural property arises from a growth dynamic termed preferential attachment. Under this dynamic, a network is grown from an initially small number of nodes by successively adding new nodes. A new node has a probability of being connected to each existing node dependant on the number of connections that node already has. Thus networks with a large number of connections are likely to attract more, whereas minimally connected nodes are more likely to stay that way.
An interesting property of scale free networks is their robustness to the failure of individual nodes. Because many of the nodes have very low connectivity, the random removal of any individual node is unlikely to fundamentally affect the structure of the network, providing a degree of robustness to error. On the other hand, the fact that some nodes act as 'hubs' and are connected to many other nodes, such networks may be particularly vulnerable to attacks that target highly connected nodes [5].
One of the mechanisms by which the genome is hypothesized to have evolved is by gene duplication. Certain copying errors can result in a segment of the genome being duplicated and, because the duplicated segment encodes redundant information, it can subsequently diversify and possibly increase the functionality of the genome. The dynamics of this process have been modelled and demonstrated to show similar properties, such as response to failure and attack, to networks based on real data [117,135].
Next: Modularity, motifs and other Up: Network models Previous: Network models Nic Geard 2004-05-06