【正文】 mit t → ∞, the model produces a degree distribution P (k) ～ k?,with an exponent= 3. The case of a growing work with a constant attach ment probabilityj→i =1/(m0+t ? 1) produces, instead, a degree distribution P (k) = e/m exp(?k/m). This implies that the preferential attachment is an essential ingredient of the model. Krapivsky and Redner have considered a directed version of the BA model. They have studied the relation between the age a of a node i, de?ned as the number of nodes added after node i, and its degree, and the correlations in thedegree of adjacent nodes [147]. They found that the number of nodes of age a with k links, Na(k), is equal to ( ) 1 1 1 ka aaNk NN??? ? ? ????? 4 Thus, the degree distribution for nodes of ?xed age decays exponentially with the degree, with a characteristic degree scale which diverges as (1 ? a/N )?1/2fora → N . The same authors have also shown that there are correlations in the degrees of neighboring nodes, so that nodes of similar degree are more likely to be connected [147] in sharp contrast to the standard BA model where degreedegree correlations are absent. An alternative method to generate degree correlations in a BA scalefree work (or in a generic undirected uncorrelated work) has been proposed in Ref. [148]. The method is based on the following iterative algorithm: at each step two links of the work are chosen at random, and the four endnodes are ordered with respect to their degrees。s [119]. The probability that a node i has k =kiedges is the binomial distribution P (ki=k)=CNk ?1pk(1 ?p)N?1?k , where pkis the probability for the existence of k edges, (1 ? p)N?1?k is the probability for the absence of the remaining N ? 1 ? k edges, and CNk ?1=Nk?1 is the number of different ways of selecting the end points of the kedges. Since all the nodes in a random graphare statistically equivalent, each of them has the same distribution, and 2 the probability that a node chosen uniformlyat random has degree k has the same form as P (ki= k). For large N, and ?xed k, the degree distribution is well approximated by a Poisson distribution: P(k)= ()ke? ()!kkk For this reason, ER graphs are sometimes called Poisson random graphs. ER random graphs are, by de?nition, uncorrelated graphs, since the edges are connected to nodes regardless of their degree. Consequently, P (k |k) and knn(k) are independent of k. Concerning the properties of connectedness,when plan N/N, almost any graph in the ensemble GER N,pis totally connected [115], and the diameter varies in a small range of values around Diam = ln N/ ln(pN ) = ln N/ ln k [14,120]. The average shortest path length L has the same behavior as a function of N as the diameter, L ～ ln N/ ln k [5,14,28,53]. The clustering coef?cient of GERis equal to C = p = k /N, since p is the probability of having a link between any two nodes in the graph and, consequently, there will be pk(k ? 1)/2 edges among the neighbors of a node with degree k, out of a maximum possible number of k(k ? 1)/2 [28]. Hence, ER random graphs have a vanishing C in the limit of large system size. For large N and p pc, the bulk of the spectral density of ER random graphs converges to the distribution [2,72] ? ? 241 2 ( 1 )() 2 ( 1 )0Np p if u Np pu Np po th e rwise?? ?? ??? ??? ? ??? This is in agreement with the prediction of the Wigner’s semicircle law for symmetric uncorrelat ed random matrices[78]. The largest eigenvalue (N) is isolated from the bulk of the spectrum, and it increases with the work size aspN . For p pc, the spectral density deviates from the semicircle law, and its odd moments M2k+1are equal to zero, indicating that the only way to return back to the original node is traversing each edge an even number of times. . Generalized random graphs The ER models can be extended in a variety of ways to make random graphs a better represent tation of real works. In particular, one of the simplest properties to include is a nonPoisson degree distribution. Random graphs with an arbitrary degree distribution P (k) have been discussed a number of times in the con?guration model introduced by Bender and Can?eld [121] allows to sample graphs with a given degreesequence [122,123]. A degree sequence is any sequence of N integer numbers D={k1, k2, . . . , kN}such thatiki=2K, where K is the number of links in the graph. In the con?guration model D is chosen in such a way that the fraction of vertices with degree k will tend, for large N , to the desired degree distribution P (k). The model considers the ensemble (denoted asGconf N,D ) of all graphs with N nodes and a given degree sequence D, each graph being considered with equal probability. Random con?gurations on the ?xed degree sequence by assigning toeach nodei a number of halfedges equal to its expected degree ki, and by forming edges by pairing at random, with uniformprobability, two halfedges together. This procedure generates, with equal prob ability, each possible graph patible with D [6,122]. In fact, each con?guration can be obtained ini(ki!) different ways, since ki! are the permutations of the ki indistinguishable halfedges of node i. Notice that GERN,K can be obtained as a particular case of GconfN,D. A different method, that produces multigraphs, possibly with loops, can be found in Refs. [122,123]. The simplicity of the con?guration model makes it a good playground for analytical approaches. Molloy and Reed proved that a giant ponent emerges almost surely in random graphs with a given P (k) when ( 2 ) ( ) 0kQ k k p k? ? ?? 3 and the maximum degree kmaxin the graph is not too large. Conversely, when Q 0, and kmaxis not too large, th