Classification of Scale Free Networks

While the emergence of the scale-free behavior in complex networks is intriguing and has a number of important consequences in its own right, there may exist other hidden orders in the scale-free networks. In this section, we introduce a candidate for this, the load distribution, and show that we can classify a range of real-world and model-generated scale-free networks into two distinct classes. We argue that such classification is rooted from the distinct topological features of the shortest pathways in the network.

Load Distribution

Let us suppose that a signal is sent from a vertex i to j (i —>_/), along the shortest pathway between them.35 In the information network such as the Internet, data packet is normally transmitted along the shortest pathways, however, for biological networks, it is not, even though the shortest pathways are the major flux canal. Nevertheless, here we consider the signal transport along the shortest pathways for simplicity. If there exist more than one shortest pathways, the signal would encounter one or more branching points. In this case, the signal is presumed to take one of them with equal probability, and the signal is effectively divided evenly over the branches at each branching point as it travels. Then the load 1 at a vertex k is defined as the amount of signals passing through that vertex k. Note that 1 = 0 for vertices which do not fall on the shortest pathway (i—>j). Also note that the contribution from the pathway (i—>j), may be different from that of (/—>/), ' , even for undirected networks. Then we define the load Ik of a vertex k as the accumulated sum of 1 over all pairs of senders and receivers: »'■j

Here, we do not take into account the time delay of signal transfer at each vertex or edge, so that all signals are delivered in a unit time, regardless of the distance between any two vertices. So the load is a static variable for a given number of vertices N. The definition of the load is illustrated in Figure 2. Since the packets are conserved, the total load contributed by one pair is simply related to the shortest pathway length d.t] between them, by

Figure 2. Illustration of the definition of load: The load at each vertex due to a unit packet transfer from the vertex ¿to the vertex/ In this diagram, only the vertices along the shortest paths between (i,j) are shown. The quantity in parenthesis is the load due to the one from j to i.

Thus we have the sum rule for :

k i,j where D is called the diameter. The quantity we defined as load is closely related to the one used in sociology called "betweenness centrality" (BC) which quantifies how much power is centralized to a person in social networks.36,37

We focus our interest on the manner how Ik are distributed. Once a SF network is generated artificially or adopted from the real world, we select an ordered pair of vertices (/,_/) on the network, and identify the shortest pathway(s) between them and measure the load on each vertex along the shortest pathway using the modified version of the breath-first search algorithm introduced by Newman37 and independently by Brandes.38

We have measured load (.k of each vertex k for SF networks with various y. It is found numerically that the load distribution Pl(0 follows the power law,35

When the indices of the vertices are ordered according to the rank of the load, we have i\> ... > I'm. Then, the power-law behavior of the load distribution implies that

Jitj Nl-aia' j with

The relation, Eq. (8), is valid in the region,39 < ('< /mM> where ND if a< 1

Based on numerical measurements of load exponents for a variety of SF networks, we find that the load exponent is likely to be robust, independent of the details of network structure such as the degree exponent y as long as y is in the range 2 < y < 3 and other details such as the mean degree, the directionality of edge, and so on.35 Thus we may categorize the SF networks according to the load distributions of them. We found two classes, say, class I and II.40 For the class I, the load exponent is 8 ~ 2.2(1) and for the class II, it is 6 = 2.0(1). We conjecture the load exponent for the class II to be exacdy 5 = 2 since it can be derived analytically for simple models. We will show that such different universal behaviors in the load distribution originate from different generic topological features of networks.

Real- World and Artificial Networks Investigated

A few network examples that we find to belong to the class I with 8 = 2.2(1) include:

i. The protein interaction network of the yeast 5. cerevisiae compiled by Jeonget al31 (PINi), where vertices represent proteins and the two proteins are connected if they interact.

ii. The core ofprotein interaction network ofthe yeast S. cerevtsiae obtained by Ito et al (PIN2) .27

iii. The metabolic networks for 5 species of eukaryotes and 32 species of bacteria in reference 21, where vertices represent substrates and they are connected if a reaction occurs between two substrates via enzymes. The reaction normally occurs in one direction, so that the network is directed.

iv. The Barabisi-Albert (BA) model41 when the number of incident edges of an incoming vertex m> 2.

v. The stochastic model for the protein interaction networks introduced by Sold et al.42 For both (i) and (v), the degree distribution is likely to follow a generalized power-law with a cut-off. Despite this abnormal behavior in the degree distribution for finite system, the load distribution follows a pure power law with the exponent 8 = 2.2(1) . The representative load distributions for real world networks (ii) and (iii) are shown in Figure 3A.

0 0

Post a comment