电气工程及其自动化专业毕业设计（论文）外文翻译.doc

英 文 翻 译 2010 届 电气工程及其自动化 专业 1006972 班级姓 名 学号 指导教师 职称 二一 二 年 二 月 十 日2.3. Networks modelsThe observations described in the examples of Section 2.2 have clearly motivated the introduc tion of new concepts and models. In this section, we focus on the mathematical modelling of netw -orks, discussing some simple and genericmodels from the point of view of their motivation, const- ruction procedure and signicant properties. Further details on models can be found in Refs. 24,7.2.3.1. Random graphsThe systematic study of random graphs was initiated by Erdös and Rényi in 1959 with the orig- inal purpose of studying, by means of probabilistic methods, the properties of graphs as a function of the increasing number of random connections. The term random graph refers to the disordered nature of the arrangement of links between different nodes. In their rst article, Erdös and Rényi proposed a model to generate random graphs with N nodes and K links, that we will henceforth call Erdös and Rényi (ER) random graphs and denote as GERN,K . Starting with N disconnected nodes, ER random graphs are generated by connecting couples of randomly selected nodes, prohibiting multiple conne- ctions, until the number of edges equals K 115. We emphasize that a given graph is only one out come of the many possible realizations, an element of the statistical ensemble of all possible combin- ations of connections. For the complete description of K,None would need to describe the ensembleof possible realizations, that is, in the matricial representation, the ensemble of adjacency matrices 116. An alternative model for ER random graphsconsists in connecting each couple of nodes with a probability 0 < p < 1. This procedure denes a different ensemble, denoted as G N,pand containing graphs with different of links:graphs with K links will appear in the ensemble with a probability pK(1 p)N (N 1)/2K 14,115,117. The two models have a strong analogy, respectively, with the canonical and grand canonical ensembles in statistical mechanics 118, and coincide in the limit of large N16. Notice that the limit N is taken at xed k, which corresponds to xing 2K/N in the rst model and p(N 1) in the second one. Although the rst model seems to be more pertinent to applications, analytical calculations are easier and usually are performed in the second model. ER random graphs are the best studied among graph models, although they do not reproduce most of the properties ofreal networks discussed in Section 2.2. The structural properties of ER random graphs vary as a function of p showing, in particular, a dramatic change at a critical probability pc=N1 , corresponding to a critical average degreekc= 1.Erdös and Rényi proved that 14,16:if p < pc, then almost surely, i.e. with probability tending to one as N tends to innity, the graph has no componentof size greater than O(ln N ), and no component has more than one cycle;if p = pc, then almost surely the largest component has size O(N2/3);if p > pc, the graph has a component of O(N ) with a number O(N ) of cycles, and no other comp- onent has more than O(ln N ) nodes and more than one cycle.The transition at pc has the typical features of a second order phase transition. In particular, if one considers as order parameter the size of the largest component, the transition falls in the same universality class as that of the mean eld percolation transitions. Erdös and Rényi studied the distribution of the minimum and maximum degree in a randomgraph 115, while the full degree distribution was derived later by Bollobás 119. The probability that a node i has k =kiedges is the binomial distribution P (ki=k)=CNk 1pk(1 p)N1k , where pkis the probability for the existence of k edges, (1 p)N1kis the probability for the absence of the remaining N 1 k edges, and CNk 1=Nk1 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 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)= 2.15For this reason, ER graphs are sometimes called Poisson random graphs. ER random graphs are, by denition, uncor-related 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 coefcient 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 2.16This is in agreement with the prediction of the Wigners semicircle law for symmetric uncorrelat- ed random matrices78. The largest eigenvalue (N) is isolated from the bulk of the spectrum, and it increases with the network 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.2.3.2. Generalized random graphsThe ER models can be extended in a variety of ways to make random graphs a better represent tation of real networks. In particular, one of the simplest properties to include is a non-Poisson degree distribution. Random graphs with an arbitrary degree distribution P (k) have been discussed a number of times in the literature.The conguration model introduced by Bender and Caneld 121allows to sample graphs with a given degreesequence 122,123. A degree sequence is any sequence of N integer numbers D=k1, k2, . . . , kNsuch thatiki=2K, where K is the number of links in the graph. In the conguration 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 asGconfN,D ) of all graphs with N nodes and a given degree sequence D, each graph being considered with equal probability. Random congurations on the xed degree sequence by assigning toeach nodei a number of half-edges equal to its expected degree ki, and by forming edges by pairing at random, with uniformprobability, two half-edges together. This procedure generates, with equal prob- ability, each possible graph compatible with D 6,122. In fact, each conguration can be obtained ini(ki!) different ways, since ki! are the permutations of the kiindistinguishable half-edges of node i. Notice that GERN,Kcan 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 conguration model makes it a good playground for analytical approaches. Molloy and Reed proved that a giant component emerges almost surely in random graphs with a given P (k) when 2.17 and the maximum degree kmaxin the graph is not too large. Conversely, when Q < 0, and kmaxis not too large, then almost surely the size of the largest component is O(kmax2lnN ) 122. We shall discuss the derivation of this condition in Section 3.1.2, and the application to the case in which P (k) is a power law in Section 2.3.4. For ER random graphs, formula (2.17) yields the critical average degreekc= 1 discussed in Section 2.3.1. The same au-thors have studied in Ref. 123 the size of the giant component and the structure of the graph formed by deletingsuch component. Newman et al. have proposed a slightly different method to generate graphs with a given degree distribution, in which the degree of nodes are independent identically distributed random integers drawn from a given P (k). In thisway, not a single degree sequence, but an ensemble of degree sequences is consid -ered, and the statistical properties of the ensemble, as component sizes and number of nodes at a distance m from a given node, can be calculated by the use of a powerful formalism based on prob -ability generating functions 4,124. Newman et al. have found an approximateformula for the average shortest path length that, when N >z1 and z2>z1, reads as 2.18 where zm is the average number of neighbors at distance m. This formula reduces to the expre ssion discussed in Section 2.3.1, in the special case of ER random graphs, for which z1= k , and z2= k2. More recently, Chung and Luproposed a model for random graphs with given expected degree sequ -ence and provided a more rigorous proof that Lis almost surely of the order of ln N/ ln d, with deq- ual to the weighted average of the sum of squares of degrees 125. The clustering coefcient in the conguration model is given by 4,6,126 2,19 That is the value for the ER random graphs times an extra factor that can be quite large since its leading term goes as the fourth power ofk/k. Consequently, C vanishes for N , although it can be not negligible for highly skewed degree distributions and nite graph sizes as those observed empiri -cally (see Section 2.3.4). Generalization to include clustering properties in random graphs have been less ex -plored in the literature 6,59. 2.3.3. Small-world networksThe Watts and Strogatz (WS) model is a method to construct graphs, denoted as GWSN,K having both the small-world property and a high clustering coefcient 28. The model is based on a rew -iring procedure of the edges implemented with a probability p. The starting point is a Nnodes ring, in which each node is symmetrically connected to its 2m nearest neighbors for a total of K = mN edges. Then, for every node, each link connected to a clockwise neighbor is rewired to a randomly chosen node with a probability p, and preserved with a probability 1 p. Notice that for p = 0we have a regular lattice, while for p = 1 the model produces a random graph with the constraint that each node hasa minimum connectivity kmin= m. For intermediate values of p the procedure generates graphs with the small-worldproperty and a non-trivial clustering coefcient. Alternative procedures for constructing small-world networks, based on adding edges instead of rewiring, have also been proposed 126128.The richness of the WS model has stimulated an intense activity aimed at understanding the networks properties as a function of the rewiring probability p and the network size N53,128130. As observed in 28, the small-world property results from the immediate drop in L(p) as soon as p is slightly larger than zero. This is because the rewiring of links creates long-range edges (shortcuts) that connects otherwise distant nodes. The effect of the rewiring procedure is highly nonlinear on L, and not only affects the nearest neighbors structure, but it also opens new shortest paths to the next-nearest neighbors and so on. Conversely, an edge redirected from a clustered neighborhood to another node has,at most, a linear effect on C . That is, the transition from a linear to a logarithmic behavior in L(p) is faster than the one associated with the clustering coefcient C(p). This leads to the appearance of a region of small (but non-zero) values of p, where one has both small path lengths and high clustering. The change in L(p) soon stimulated numerical and analytical work 53,128,129, aimed at inspecting whether the transition to the small-world regime takes place at a nite value of p, or if there is a crossover phenomenon at any nite value of N with the transition occurring at p = 0. This latter scenario turned out to be the case. To see this, we follow the arguments by Barrat and Weigt 53, and Newman and Watts 128. We assume that p is kept xed and we inspect the dependency of L(N, p). For small system sizes, the number of shortcuts is less than 1 on average, and the scaling of L(N, p) is linear with the system size. However, for larger values of N , the average number of shortcutseventually becomes greater than one and L(N, p) starts scaling as log(N ). Similar to the correlation length behavior in conventional statistical physics, at some intermediate system value N= L, where the transition occurs, we expectL p. Additionally, close to the transition point, L(N, p) should obey the nite-size scaling relation 53,128: 2.20 where f (x) is a universal scaling function that obeys to: f (x) x if x >1 and f (x) ln x if x?1. Let us suppose now that< 1 and assume<< 1. From Eq. (2.20) it follows that 2.21 On the other hand, the average number of rewired connections is mN11/, which vanishes as N gro -ws. From here, Barrat and Weigt deduced that 1, a result also supported by their numerical simu- lations. Newman and Watts corroborated this result by a renormalization group analysis and showed that in fact = 1 128. In summary, the model undergoes a continuous phase transition as the density of shortcuts tends to zero with a characteristic length diverging as p1. The exact form of the scaling function f (x) has been obtained in Refs. 129,131. Barrat and Weigt have obtained a simple form- ula that ts well the dependency of C(p) observed in the numerical simulations of the WS model53. The formula is based on the fact that for p = 0, C(0) = 3(m 1)/2(2m 1). Then, because of the fact that with probability (1 p) edges are not rewired, two neighbors that were linked together at p = 0 will remain connected with probability (1 p)3up to corrections of order 1/N . From here, we get: 2.22 where C(p)is redened as the ratio between the average number of edges between the neighbors of a vertex and theaverage number of possible links between the neighbors of a vertex. As for the degree distribution, when p = 0 it is a delta function positioned at 2m, while for p = 1 it is sim