On a growth model for complex networks capable of producing power-law out-degree distributions with wide range exponents

The out-degree distribution is one of the most reported topological properties to characterize real complex networks. This property describes the probability that a node in the network has a particular number of outgoing links. It has been found that in many real complex networks the out-degree has a behavior similar to a power-law distribution, therefore some network growth models have been proposed to approximate this behavior. This paper introduces a new growth model that allows to produce out-degree distributions that decay as a power-law with an exponent in the range from 1 to ∞.

A mong the topological properties of real complex networks (CN), one of the most studied is the out-degree distribution. This property describes the probability that a node in the network has a particular number of outgoing links. It has been found that in many real CN the out-degree behaves as a power-law distribution (P(k) / k 2c ) [1][2][3][4][5][6][7] . In order to approximate this type of out-degree distribution, some growth models for CN have been proposed. For example, Dorogovtsev et.al. 8 and Bollobás et.al. 9 have each developed a model capable of producing out-degree distributions that decay as a power-law with exponent c~2z n r znzB m and c~1z 1zd out azb ð Þ bzc , respectively. Hence in both models the c exponent is greater than 2. Esquivel et.al. 10 proposed a model that produces out-degree distributions that decay as a power-law where the c exponent value is in the range between 0 and 1. The previous models are not able to produce out-degree distributions with c exponents in the range between 1 and 2. However, there are real CN where the c exponent value is within this interval. For example, the social network of Flickr users 6 , the Any Beat network 7 , the online social network Epinions 6 and the network of flights between airports of the world (OpenFlights) 6 where the c exponent for the out-degree distribution of these CN is close to 1.74, 1.71, 1.69 and 1.74 respectively. This paper introduces a new model for growth of directed CN that allows to obtain out-degree distributions that decay as a power-law with exponents in the range 1 , c , '. That is, the proposed model is able to generate all exponent values found in documented real CN [1][2][3][4][5][6][7] .
It has been demonstrated that the growth and evolution of CN is influenced by local processes that shape its topological and dynamical properties 11 . The model proposed in here incorporates two local processes for adding new nodes to the network: a random out-degree selection and a copy of an already present out-degree value. In many large networks the maximum degree of a node (the degree of a node is the sum of its incoming and outgoing links) is much smaller than the number of nodes 6 . Thus, the proposed model assumes that the probability that a new node n new selects a random out-degree decreases as the network grows. This probability is expressed as N 2a where N is the total number of nodes in the network (including n new ) and a is a constant greater than 0. In other words, the probability that new nodes have an out-degree close to N tends to zero as N ? 1.

Proposed model
In this model, the growth of the network is performed by adding nodes one at a time. At the beginning, only node n 0 is present in the network and its out-degree is 0. Then, the out-degree of any new node n new added to this network is determined as follows: . With probability N 2a , n new randomly selects an out-degree uniformly distributed from 0 to N 2 1. That is, n new may have outdegree 0, 1, 2, …, N 2 1. It is important to notice that it is possible that n new has an out-degree of the order of N 2 1. In this situation n new would connect to all the other nodes in the network. This scenario may not be realistic for large values of N, because in many real networks, the maximum degree for a node is much smaller than the total number of nodes N 6 . However, the probability N 2a decreases when N increases for a . 0. . With complementary probability 1 2 N 2a , n new copies the outdegree of a randomly selected node from the network. It is important to notice that as the number Q s of nodes with outdegree s increases, the probability that n new has out-degree s also increases to Q s N{1 .
It is possible to employ the continuum method 12 to obtain the analytical solution for the proposed model. This method is implemented using the following differential equation: The previous equation describes the variation of the number Q s of nodes with out-degree s with respect to the total number N of nodes in the network. The term g 1 describes the situation that a new node randomly selects an out-degree value and the term g 2 the situation that a new node copies this value from a randomly selected node in the network.
Eq. 1 may be written in the standard form for a linear differential equation: From Eq. 2, it is possible to deduce the integrating factor I N ð Þẽ Ð N {a {1 N{1 dN . Solving for I(N) produces non elementary functions, which complicate the solution of Eq. 2. In order to obtain an integrating factor in terms of elementary functions, it is best to simplify Eq. 2 as follows: This simplification has little implications for large values of N, because N 2 1 < N, as N ? 1. This allows to employ the following integrating factor: . Multiplying Eq. 3 by Solving for Q s (N) where k is a constant and C(?) is the incomplete Gamma function. In order to obtain the out-degree distribution Q s (N), it is necessary to solve Eq. 6 for s 5 1, s 5 2, and so on as follows: . for Q 1 (N), consider the initial condition this initial condition is due to the fact that, at the beginning the network only has one node, n 0 , with no outgoing links (N 5 1). When the next node, n 1 , is added (N 5 2), the probability that node n 1 has out-degree s 5 1 is 2 {a 2 .
. Then, solving Eq. 6 for the initial condition Q 1 2 ð Þ~2 {a 2 produces: . for Q 2 (N), consider the initial condition this initial condition is due to the fact that, before adding node n 2 only n 0 and n 1 exist in the network (N 5 2) and both have s , 2, therefore Q 2 (2) 5 0. When n 2 is added (N 5 3), the probability that node n 2 has out-degree s 5 2 is 3 {a 3 .
. Then, solving Eq. 6 with the initial condition Q 2 3 ð Þ~3 {a 3 , one obtains: From the results in Eqs. 7 and 8, it is possible to deduce that: Normalizing Eq. 9, yields: Eq. 10 describes the out-degree distribution P s (N) obtained with the proposed model for 1 , s , N. It can also be noted that, as s R N, Eq. 10 predicts that P s N ð Þ< 1 N az2 . That is P s (N) decays to 0 rapidly as s R N and N ? 1, therefore the power-law behavior exhibits a cutoff (Figure 1a).
In order to obtain the scaling exponent of the out-degree distribution, terms C(?) into Eq. 10 are simplified using: it is possible to write: Using Eq. 11 it is possible rewrite the C(?) terms of Eq. 10 as follows: Substituting Eqs. 12 and 13 into Eq. 10 and considering that s 1 1 < s as s ? 1, Eq. 10 can be expressed as: Furthermore, in the limit when N R ', Eq. 17 takes the form Eq. 18 shows that the out-degree distribution obtained with the proposed model decays as a power-law P s , s 2c for 1 , s , N with scaling exponent c 5 a 1 1.
To validate the analytical solution of the model as described by Eq. 10, four experiments were executed using a 5 0.5, 1, 1.5 and 2. Each of these experiments simulated the growth of a directed network from N 5 1 to 10 4 nodes. Figure 1b shows that the out-degree distribution produced by these experiments and the analytical predictions by Eq. 10 fit appropriately.

Comparison with real networks
To verify that the proposed model is able to reproduce the out-degree distribution of real CN, the social network of Flickr users 6 was selected.
In this network, the users correspond to the nodes and their friendship connections to the links. This network has 2, 302, 925 nodes and 33, 140, 017 links. Figure 2a shows that the out-degree distribution of the nodes in the Flickr network decay as a power-law distribution with c < 1.74. Figure 2b shows that the model proposed by Eq. 10 with a 5 0.74 and N 5 2, 302, 925 reproduces appropriately the out-degree distribution of the Flickr network for s . 1.

Discussion
The model proposed in this article has been able to reproduce the out-degree distribution of the Flickr social network for values of s . 1. Although this model produces a good fit with the out-degree distribution of a real network, we cannot guarantee that the local processes incorporated in this model are the only ones involved in the behavior of the out-degree distribution of the nodes in this network. Unknown processes may help to explain why for s 5 1, this model does not fit. However, the proposed model provides a simplification of these processes and therefore, reproduces the out-degree distribution of the network. to obtain out-degree distributions P s that decay as a power-law. Also, it may be noted that for values of s close to N the P s decays rapidly (vertical arrow) and the power-law behavior is cut-off. (b) Comparison of the out-degree distribution produced by the experiments (symbols^, [, g, h) and by Eq. 10 (solid line) for N 5 10 4 and several values of a.
www.nature.com/scientificreports Conclusions Local processes participate in the growth and evolution of real CN which, in turn, shape the out-degree of its nodes. The model proposed here incorporates two local processes: a random out-degree selection and a copy of an out-degree for the nodes added to the network. This model is able to produce out-degree distributions that decay as a power-law with the c exponent in the range from 1 to '. That is, the proposed model reproduces all exponent values found in distributions of documented real complex networks.