Scale-free networks

Keywords Scale-free networks Internet structure quantum key... 

One of the key discoveries was the realization that very many real networks in nature, technology (e.g., the Internet and WWW) and human relations have similar structure and growth patterns, and can be described by the same mathematical formulas. All of them share similar properties and behavior. This discovery and the new theory have created an unprecedented opportunity for investigating resilience and vulnerabilities of the Internet and the WWW. For this reason we consider the scale-free network theory and related empirical results as being a significant development in the Cyberspace Security and Defense. 

Random networks were a significant contribution to the future theory of large real networks but the most dramatic and useful development took place about forty years later when A-L Barabasi and his collaborators made empirical mapping of the Internet and using different growth principles created the theory of nets called scale-free networks. 

The scale-free networks investigated by A-L Barabasi and his collaborators follow a different growth rule than the rules for creating random networks. All scale-free networks are characterized by distribution functions P(k) which are powers of k. 

The pattern of growth for scale-free networks follows the rule of preferential attachment [7]. According to this rule a new node prefers attaching itself to the highly connected nodes. For example a simple linear version of this rule can be expressed formally as... 

The most dramatic result of the preferential attachment growth rule is the appearance of highly connected nodes called hubs. The scale-free networks do not have typical nodes with average number of edges. The concept of average connectivity does not have meaning for these nets. 

Scale-free networks have few very highly connected hubs and most of the nodes have only few edges. This difference in the structure between the... 

Scale free networks are common in nature, human relations, economy and technology. The Internet and WWW are important examples of scale-free networks. A possible reason for popularity of scale-free nets in nature may be their robustness in the presence of random node failures. Computer experiments have shown that Internet would not fall apart even if 80% of all routers fail [7]. 

This structural robustness could be attributed to the existence of hubs in scale-free networks. Similar experiments indicate that by removing a few hubs the Internet would disintegrate into disjoint components. 

Both developments, scale-free network theory and quantum key distribution offer new opportunities for Cyberspace Security and Defense. In... 

Dezso, Zoltan and A-L. Barabasi, Halting viruses in scale- free networks, Phys Rev. E, 65, 055103(R)... 

Following the considerable recent interest in scale-free networks, Jeong et al. [145] have shown that the metabolic networks of extant living systems are scale-free networks sharing the same metabolite hubs over evolutionary time. Wagner and Fell [146] suggest that there are three reasons why metabolic networks may be scale free. 

Metabolism may be scale-free because of chemical constraints of the underlying chemical network. They dismiss this possibility, claiming as evidence the fact that in different organisms the metabolic network takes many different forms. However, this does not rule out the existence of more general chemical constraints that may produce the scale-free network. For example, it is generally the case that small molecules have more possible synthesis routes than large molecules and so we expect connectivity to scale as a function of size. 

Nacher JC, Ueda N, Kanehisa M, Akutsu T Flexible construction of hierarchical scale-free networks with general exponent. Phys. Rev. 2005 E 71, 036132... 

Large systems. If two oscillators can adjust their rhythms due to an interaction, then one can expect similar behavior in large populations of units. Among different models under investigation we outline regular oscillator lattices (which in the limit case provide a description of extended systems) [9], ensembles of globally (all-to-all) coupled elements, the main topic of the present contribution, random oscillator networks (small world networks, scale-free networks, etc), and spatially-extended systems [10, 44, 55]. 

Albert, R. Scale-free networks in cell biology. J. Cell. Sci. 2005,118(Pt 21), 4947-57. 

Husi, H., Choudhaiy, J., Yu, L., Cumiskey, M., Blackstock, W., O Dell, T.J., Visscher, P.M., Armstrong, J.D. Grant, S.G.N., 2003, Synapse proteomes show scale-free network properties underlying plasticity, cognition and mental illness. Submitted. 

It appears that protein conformations are also like that, they can be viewed as nodes of a scale-free network. What plays the role of bonds in this network, or handshakes between conformations The answer would appear natural if the reader remembers the protein conformation contact matrix — we discussed it around formula (10.1) in Section 10.5. Indeed, the distance between two conformations can be characterized by the number of permutations by which the contact matrix of one conformation is transformed into the other. Then, two conformations are declared neighbors , and are connected by a bond ( handshake ), if the distance between them is smaller than a certain threshold (and the results appear rather insensitive to the specific value of this threshold, within reasonable limits). With such definition, the network of protein conformations turns out to be scale-free. Obviously, this fact must be somehow the result of evolution. But how did it happen in evolution And what does it lead to Those are all topics of active current research. 

Eugene V. Koonin, Yuri I. Wolf and Georgy P. Karev, Power Laws, Scale-Free Networks and Genome Biology , Springer, 2006. 

Nakao and Mikhailov [316] performed numerical simulations of an activator-inhibitor model, namely the Mimura-Murray model, on a large array, namely a Barabasi-Albert scale-free network with 1000 nodes and mean degree of 20 ... 

The degree distribution P(k) is the probability that a node is linked to k other nodes. The P(k) of random networks exhibits a Poisson distribution, whereas that of scale-free networks approximates a power law of the form m An interesting suggestion is that most cellular networks approximate a scale-free topology" " with an exponent y between 2 and The... 

The path length distribution of a network tells us how far nodes are from each other. Scale-free networks are ultra-small because they have an average path length of the order log(log N), where N is the number of nodes. Random networks are small because their mean path length is of the order logN. ... 

R. Cohen and S. Havlin, Phys. Rev. Lett., 90, 058701 (2003). Scale-Free Networks are Ultra... 

Pastor-Satorras, R. and A. Vespignani 2001. Epidemic Spreading in Scale-Free Networks. Physical Review Letters 86(14) 3200. 

Zheng, J.-F., Z.-Y. Gao, et al. 2007. Clustering and congestion effects on cascading failures of scale-free networks. EPL (Europhysics Letters) (5) 58002. 

The most important property of scale-free systems is their invariance to changes in scale. The term "scale-free" refers to a system defined by a fxmctional form fix) that remains unchanged within a multiplicative factor under rescaling of the independent variable x. Indeed, this means power-law forms, since these are the only solutions to fian) = b fin), where n is the number of vertices (Newman, 2002). The scale-invariance property means that any part of the scale-free network is stochastically similar to the whole network and parameters are assumed to be independent of the system size (Jeong et al., 2000). 

Amaral and al (Amaral et al., 2000) have studied networks whose cumulative degree distribution shape lets appear three kinds of networks. First, scale-free networks whose distribution decays as a power law with an exposant a satisfying bounds seen above. Second, see Fig. 4, broad-scale or truncated scale-free networks whose the degree distribution has a power law regime followed by a sharp cutoff. Third, single-scale networks whose degree distribution decays fast like an exponential. 

Fig. 4. Degree distribution described in (Amaral et al., 2000). The red line follows a power law, as for scale-free networks. The green line corresponds to truncated scale-free networks. The black curve corresponds to single-scale networks.

Consequently, we find a way to approximate all proteins SSE-IN cumulative degree distribution by the function Pjt which can be adjusted. This function describes a power law regime followed by a sharp cut-off which arises for degree values exceeding the mean degree. Proteins SSE-IN are so tnmcated scale-free networks. 

Such graphs are also called scale-free networks, see, for example, [47]. 

Keywords power, scale-free networks, new institutional economics... 

Scale-Free Networks The vertex degree distributions of scale-free networks differ from those of large random networks and many small worid networks, which are Poisson distributed (vide supra). By contrast, scale-free networks described by Barabasi and Albert [182] are nonhomogeneously distributed and follow power laws, such that the probability that a random vertex has degree k is inversely related to a power of vertex degree, i.e.,... 

---