Figure 4. Network of physical interactions between nuclear proteins in yeast. Here we show the subset of protein-protein physical interactions reported in the full set of reference 8 consisting of 318 interactions between proteins that are known to be localized in the yeast nucleus.5 The resulting network involves 329 proteins. Note that most neighbors of highly connected proteins have rather low connectivity. This feature will be later quantified in the correlation profile of this network (Figs. 6, 8).

forces of biological evolution shape them from raw material provided by random events such as mutations within individual genes, and gene duplications. As a result their connections are characterized by a large degree of randomness. One may wonder which connectivity patterns are indeed random, and which arose due to the network growth, evolution, ans/or its fundamental design principles and limitations?

To this end we first construct a proper randomized version (null model) of a given network. As was pointed out in the general context of complex scale-free networks,9 a broad distribution of degrees indicates that the degree itself is an important individual characteristic of a node and as such it should be preserved in the randomized null-model network.10 In addition to degrees one may choose to preserve some other low-level topological properties of the network in question.11 Any measurable topological quantity, such as e.g., the total number of edges connecting pairs of nodes with given degrees, the number of loops of a certain type, the number and sizes of

Figure 5. One step of the random local rewiring algorithm. A pair of edges A—>B and C—>D is randomly selected. The two edges are then rewired in such a way that A becomes connected to D, while C to B, provided that none of these new edges already exist in the network, in which case the rewiring step is aborted and a new pair of edges is selected. An independent random network is obtained when the above local switch move is performed a large number of times, say several times in excess of the total number of edges in the system. Note that for directed networks this rewiring algorithm separately conserves both the in- and out-degrees of each individual node.

components, the diameter of the network, can then be measured in the real complex network and separately in its randomized version. One then concentrates only on those topological properties of the real network that significantly deviate from its null model counterpart.1 13

An algorithm giving rise to a random network with the same set of individual node degrees as in a given complex network was proposed in references 10, 14 and 15. It consists of multiple repetitions of the following simple switch move (elementary rewiring step) illustrated in Figure 5:

Randomly select a pair ofedges A—>B and C—>D and rewire them in such a way that A becomes connected to D, while C to B.

To prevents the appearance of multiple edges connecting the same pair of nodes, the rewiring step is aborted and a new pair of edges is selected if one or two of the new edges already exist in the network. A repeated application of the above rewiring step leads to a randomized version of the original network. The set of MATLAB programs generating such a randomized version of any complex network can be downloaded from.16

Sometimes it is desirable that the null-model random network in addition to nodes' degrees conserves some other topological quantity of the real network. In this case one could supplement11 the random rewiring algorithm described above with the Metropolis acceptance/ rejection criterion17 of a switch move.

For the sake of concreteness let's assume that one wants to generate a random network with the same set of nodes' degrees and the same number N of triangles as the real undirected network.11 Indeed, the number of triangles in a network is related to its "clustering coefficient" routinely used as a measure of its modularity.18 Hence, by conserving N one generates a null-model with the same average level of modularity as the original complex network.

The Metropolis version11 of the random rewiring algorithm uses an artificial energy function H that favors the number of triangles in a random network 7V*r) to be as close as possible to its value N in the real network:

0 0

Post a comment