《电气工程及其自动化专业毕业设计（论文）外文翻译.doc》由会员分享，可在线阅读，更多相关《电气工程及其自动化专业毕业设计（论文）外文翻译.doc（34页珍藏版）》请在三一办公上搜索。
1、英 文 翻 译 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
2、 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 Erds and Rnyi in 1959 with the orig- inal purpose o
3、f 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, Erds and Rnyi proposed a model to gen
4、erate random graphs with N nodes and K links, that we will henceforth call Erds and Rnyi (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
5、 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, th
6、at 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:grap
7、hs 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
8、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
9、 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.Erds and Rnyi prov
10、ed that 14,16: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
11、the size of the largest component, the transition falls in the same universality class as that of the mean eld percolation transitions. Erds and Rnyi studied the distribution of the minimum and maximum degree in a randomgraph 115, while the full degree distribution was derived later by Bollobs 119.
12、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 po
13、ints 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 b
14、y 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 th
15、e 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 diamet
16、er, 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
17、)/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
18、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 origi
19、nal 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.
20、 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, .
21、. . , 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
22、 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 ha
23、lf-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
24、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 rando
25、m graphs with a given P (k) when 2.17 and the maximum degree kmaxin the graph is not too large. Conversely, when Q z1 and z2z1, 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 rando
26、m 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
27、. 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 s
28、kewed 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 construc
29、t 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 neighb
30、ors 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 t
31、he 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, ha
32、ve 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)
33、 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 sho
34、rtest 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 coefcien
35、t 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 pla
36、ce 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 ins
37、pect 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
38、(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 unive
39、rsal 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 re
40、sult 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 di
41、verging 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
42、)/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
