﻿An Analytical Model of the Power Law Distributions in the Complex Network

World Journal of Mechanics
Vol.2 No.4(2012), Article ID:21537,4 pages DOI:10.4236/wjm.2012.24027

An Analytical Model of the Power Law Distributions in the Complex Network

Kosuke Takagi

Email: coutakagi@mse.biglobe.ne.jp

Received May 25, 2012; revised June 30, 2012; accepted July 12, 2012

Keywords: Complex Networks; Scale Free; Power Law

ABSTRACT

It is known that complex networks in nature exhibit some significant statistical features. We notice power law distributions which frequently emerge with respect to network structures of various quantities. One example is the scale-freeness which is described by the degree distribution in the power law shape. In this paper, within an analytical approach, we investigate the analytical conditions under which the distribution is reduced to the power law. We show that power law distributions are obtained without introducing conditions specific to each system or variable. Conversely, if we demand no special condition to a distribution, it is imposed to follow the power law. This result explains the universality and the ubiquitous presence of the power law distributions in complex networks.

1. Introduction

Various social relations or natural phenomena can be modeled by the network, in which collections of individual components are connected via their interactions. It is known that complex networks exhibit some significant statistical features characterized by quantities such as the clustering coefficient or the degree distribution [1-24]. For example, the numerous studies in this decade have reported the emergence of the scale-freeness in biological, sociological, or technological networks [3-19]. The scalefreeness is defined as the power law shape of the degree distribution

(1)

with a constant, where the variable is the degree, the number of links each node has, and is its distribution function. It is contrasted with the Poisson distribution predicted by the random graph model proposed by the Erdős and Rényi (ER) [25-27].

One of the fundamental problems regarding statistics of complex networks would be the ubiquity of power laws. The power law distribution can frequently be observed in complex networks with respect to their topological quantities which characterize each network structure. Other than the degree, the betweenness centrality, a topological quantity which depends on the global network structure, gives another example. It has been reported that the cumulative distribution of the betweenness exhibits the power law in some complex networks [20-22].

The ubiquitous presence of the power law suggests that simple statistical laws underlie commonly in various types of complex networks. According to the model proposed by Barabási and Albert [3,5], scale free networks are generated through the process named preferential attachment, in which each network node prefers to make a connection to nodes with large degrees. However, taking into account the universality of the power law including the scale-freeness, we can expect that the conditions which allow the emergence of the power law would be given in more generalized forms which are independent to specific systems. In previous studies [23,24], we have introduced an analytical model in which the scale-free degree distribution is reconstructed. Indeed, it has been shown that the scale-free distribution can be obtained without introducing conditions other than general ones. In this paper, in order to extend this model to deal with various types of quantities, we discuss, in detail, required conditions which allow the emergence of the power law distribution. We find that under conditions such as the symmetry with respect to the variable, the power law shape of the distributions can not be obtained. However the distribution which has no such additional condition is naturally reduced to the simple functional form, the power law. Therefore, our result provides an explanation for the ubiquitous presence of the power law.

2. Analytical Framework for Scale-Free Distribution

According to recent studies [23,24] and the framework proposed in them, we show that distributions given in a general form can be reduced to the power law shape without introducing special conditions. We take an analytical approach in the sense that we deal with the degree distribution as a probability density function defined with a continuous variable.

2.1. Basic Notations

Let us take a variable, the degree of each node in the network. We normalize it as, where is defined in the interval. Then we take the distribution with and assume that the variable is a continuous variable defined in the finite interval. As a probability, we can demand that and

, (2)

where is taken in. can be expanded with respect to in the Taylor series and there exists a representation

(3)

with a sequence of coefficients.

In order to investigate the scaling behavior of, we introduce the scaling parameter defined as

(4)

in the interval. If we demand the normalizing condition to

, (5)

is given as

(6)

by comparing Equations (2) and (5). Furthermore, if we introduce the cumulative distribution

, (7)

then it is given by a positive function decreasing monotonically with increasing of. Then we can represent as

(8)

with a function given as an expansion of

, (9)

where the coefficients are derived from in Equation (3). With the expression (8), the distribution of, , is given as

. (10)

2.2. Scaling Property of P(x)

According to the result shown by the study [23], without introducing additional conditions for except for

, (11)

we can show that has a general property given by

. (12)

At first, taking given by

(13)

with the terms, we decompose into. If we take the average by introducing a parameter, it is given by

. (14)

Because Equation (8) defines as the scaling for the cumulative distribution, is given as a monotonically increasing function which satisfies the boundary conditions and. Then satisfies an identical relation given by

(15)

where due to the boundary conditions of. Also we can have another relation

(16)

with a function, because integrals on each side give functions of respectively. Combining these relations (15) and (16), we obtain the relation

. (17)

Because the left-hand side can be regarded as the Laplace transform with a parameter, is uniquely determined as the inverse transform of the right-hand side. Then we obtain

. (18)

However, because the coefficient for in expansion is taken to be 0 and the expansion is free from, it is required that

(19)

and Equation (12) is given.

2.3. A Class of Distributions and the Power Law

The degree distribution is derived from with embedding from the degree to the continuous variable Substituting the representation (12), is given in the power law shape,

, (20)

with a constant and substituting straightforwardly gives the expression of in the power law shape.

However, the relation between and is not determined uniquely. Indeed, besides a trivial relation such as with the maximum value of, , we can take arbitrary transforms from to. Then we show that distributions which satisfy the condition (11) comprise a class of distributions. Within this class, the basic property (12) is conserved under the transforms between distributions.

Let us take normalized variables and and consider transforms. Generally these transforms are given by the polynomial

(21)

of with coefficients. At first, if we apply our calculating procedure to, then is given in the power law functional form such as Equation (20). However substituting Equation (21) gives form by

(22)

with another constant. Comparing this Equation (22) to Equation (20), we find that transforms from to are represented by the single term expansions such as

(23)

with a constant. Under these transforms, distributions comprise a class that preserves the power law.

3. Conditions for the Power Law Distribution

In the previous section, we have shown that the distribution is imposed to follow the power law shape if satisfies the general condition given by Equation (11). In this section, we investigate this condition in more detail.

As we have shown in the previous section, under the condition (11), distributions comprise a general class of distributions which follow the power law. As an example of exceptional cases, we construct different types of distributions which are excluded from this class. Introducing a different condition to the distribution, we show the existence of a distribution class which includes the Gaussian distribution.

As well known, the Gaussian distribution follows a profile different from the power law. As an example of a different class of distribution, we consider the following case to which we can not apply our framework. Let us take a variable with a distribution and assume that it satisfies the condition

. (24)

If we represent as

(25)

with an expanded expression

, (26)

then has the coefficients

(27)

due to the condition (24).

In this case we can not apply our framework given in the previous section and the probability density function is not included in the class of distributions which follow the power law. Within the distribution class we defined in the previous section, each element is related by the transform represented by Equation (23) and the power law feature is conserved under these transforms. However, the functional form (26) with coefficients (27) can not be reduced to the power law due to the condition (11). On the other hand, the Gaussian distribution, for example, explicitly has the symmetry such as given by Equation (24). Then there exists no transform which relates the Gaussian distribution and the power law distribution.

In this example, the symmetry of the distribution, Equation (24), breaks the condition for the power law, Equation (11). According to our result, the power law emerges as a primitive common feature of distributions. However characteristics of each system such as the symmetry of the variable work as additional conditions to the distribution and break this law.

4. Concluding Remarks

As we have discussed, our framework predicts the emergence of the power law distribution when the variable satisfies the general analytical conditions. Our model does not depend on specific systems and therefore we can apply our framework to describe the statistical behavior of various variables other than the degree. Our result suggests that the power law distribution is a ubiquitous functional form in real world networks. Then we can expect that our model provides one description which allows us to deal with various types of complex networks and their statistical quantities in a unified framework.

REFERENCES

1. D. J. Watts and S. H. Strogatz, “Collective Dynamics of ‘Small-World’ Networks,” Nature, Vol. 393, No. 6684, 1998, pp. 440-442. doi:10.1038/30918
2. S. H. Strogatz, “Exploring Complex Networks,” Nature, Vol. 410, No. 6825, 2001, pp. 268-276. doi:10.1038/35065725
3. A.-L. Barabási and R. Albert, “Emergence of Scaling in Random Networks,” Science, Vol. 286, No. 5439, 1999, pp. 509-512. doi:10.1126/science.286.5439.509
4. A.-L. Barabási, R. Albert, and H. Jeong, “Mean-Field Theory for Scale-Free Random Networks,” Physica A, Vol. 272, No. 1-2, 1999, pp. 173-187. doi:10.1016/S0378-4371(99)00291-5
5. P. L. Krapivsky, S. Redner and F. Leyvraz, “Connectivity of Growing Random Networks,” Physical Review Letters, Vol. 85, No. 21, 2000, pp. 4629-4632. doi:10.1103/PhysRevLett.85.4629
6. S. N. Dorogovtsev, J. F. F. Mendes and A. N. Samukhin, “Structure of Growing Networks with Preferential Linking,” Physical Review Letters, Vol. 85, No. 21, 2000, pp. 4633-4636. doi:10.1103/PhysRevLett.85.4633
7. A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins and J. Wiener, “Graph Structure in the Web,” Computer Networks, Vol. 33, No. 1-6, 2000, pp. 309-320. doi:10.1016/S1389-1286(00)00083-9
8. M. Faloutsos, P. Faloutsos and C. Faloutsos, “On PowerLaw Relationships of the Internet Topology,” ACM SIGCOMM—Computer Communication Review, Vol. 29, No. 4, 1999, pp. 251-262. doi:10.1145/316194.316229
9. S. N. Dorogovtsev and J. F. F. Mendes, “Evolution of Networks,” Advances in Physics, Vol. 51, No. 4, 2002, pp. 1079-1187. doi:10.1080/00018730110112519
10. R. Albert and A.-L. Barab’asi, “Statistical Mechanics of Complex Networks,” Reviews of Modern Physics, Vol. 74, No. 1, 2002, pp. 47-97. doi:10.1103/RevModPhys.74.47
11. M. E. J. Newman, “The Structure and Function of Complex Networks,” SIAM Review, Vol. 45, No. 2, 2003, pp. 167-256. doi:10.1137/S003614450342480
12. R. Albert, H. Jeong and A.-L. Barabási, “Internet: Diameter of the World-Wide Web,” Nature, Vol. 401, No. 6749, 1999, pp. 130-131. doi:10.1038/43601
13. M. E. J. Newman, “Scientific Collaboration Networks. I. Network Construction and Fundamental Results,” Physical Review E, Vol. 64, No. 1, 2001, Article ID: 016131. doi:10.1103/PhysRevE.64.016131
14. H. Jeong, B. Tombor, R. Albert, Z. N. Oltvai and A.-L. Barabási, “The Large-Scale Organization of Metabolic Networks,” Nature, Vol. 407, No. 6804, 2000, pp. 651- 654. doi:10.1038/35036627
15. H. Jeong, S. Mason, A.-L. Barabási and Z. N. Oltvai, “Lethality and Centrality in Protein Networks,” Nature, Vol. 411, No. 6833, 2001, pp. 41-42. doi:10.1038/35075138
16. O. Sporns, D. R. Chialvo, M. Kaiser and C. C. Hilgetag, “Organization, Development and Function of Complex Brain Networks,” Trends in Cognitive Sciences, Vol. 8, No. 9, 2004, pp. 418-425. doi:10.1016/j.tics.2004.07.008
17. E. Bullmore and O. Sporns, “Complex Brain Networks: Graph Theoretical Analysis of Structural and Functional Systems,” Nature Reviews Neuroscience, Vol. 10, No. 3, 2009, pp. 186-198. doi:10.1038/nrn2575
18. J. A. Dunne, R. J. Williams and N. D. Martinez, “FoodWeb Structure and Network Theory: The Role of Connectance and Size,” Proceedings of the National Academy of Sciences, Vol. 99, No. 20, 2002, pp. 12917-12922. doi:10.1073/pnas.192407699
19. M. C. Gonz’alez, C. A. Hidalgo and A.-L. Barabási, “Understanding Individual Human Mobility Patterns,” Nature, Vol. 453, No. 7196, 2008, pp. 779-782. doi:10.1038/nature06958
20. A. Vazquez, R. Pastor-Satorras and A. Vespignani, “LargeScale Topological and Dynamical Properties of the INTERNET,” Physical Review E, Vol. 65, No. 6, 2002, Article ID: 066130. doi:10.1103/PhysRevE.65.066130
21. R. Albert, I. Albert and G. L. Nakarado, “Structural Vulnerability of the North American Power Grid,” Physical Review E, Vol. 69, No. 2, 2004, Article ID: 025103(R). doi:10.1103/PhysRevE.69.025103
22. R. Guimer’a, S. Mossa, A. Turtschi and L. A. N. Amaral, “The Worldwide Air Transportation Network: Anomalous Centrality, Community Structure, and Cities’ Global Roles,” Proceedings of the National Academy of Sciences of the United States of America, Vol. 102, No. 22, 2005, pp. 7794-7799. doi:10.1073/pnas.0407994102
23. K. Takagi, “Scale Free Distribution in an Analytical Approach,” Physica A: Statistical Mechanics and Its Applications, Vol. 389, No. 10, 2010, pp. 2143-2146. doi:10.1016/j.physa.2010.01.034
24. K. Takagi, “An Analytical Approach for Degree Correlations in Complex Network,” World Journal of Mechanics, Vol. 2, No. 2, 2012, pp. 171-174. doi:10.4236/wjm.2012.23020
25. P. Erdős and A. Rényi, “On Random Graphs,” Publicationes Mathematicae, Vol. 6, 1959, pp. 290-297.
26. P. Erdős and A. Rényi, “On the Evolution of Random Graphs,” Publications of the Mathematical Institute of the Hungarian Academy of Sciences, Vol. 5, 1960, pp. 17-61.
27. P. Erdős and A. Rényi, “On the Strength of Connectedness of a Randomgraph,” Acta Mathematica Scientia Hungary, Vol. 12, No. 1-2, 1961, pp. 261-267. doi:10.1007/BF02066689