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

英 文 翻 译 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 Erds and Rnyi 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, Erds and Rnyi proposed a model to generate 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 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 ensemble31of 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.Erds and Rnyi proved 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 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. 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 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 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 similar to thatof an ER-network. For intermediate p, the degree distribution is given by 53: for km, and is equal to zero for k smaller than m.Finally, Farkas et al. have studied numerically the properties of the spectra in the SW model, showing that the distribution continuously approaches that of a random graph, aspincreases 72, and Monasson has studied the spectral properties of the Laplacian operator both numerically and analytically 127.2.3.4. Static scale-free networks,The large amount of works on the characterization of the topological properties of real networks has motivated the need to construct graphs with power law degree distributions. Graphs with a power-law degree distribution can besimply obtained as a special case of the random graphs with a given degree distribution discussed in Section 2.3.2. We denote such graphs as static scale-free to distinguish them from models of evolving graphs that will be discussed in Section 2.3.5. Aiello et al. have studied a model that involves only two parameters,and, and that assigns uniform probability egree k given by N (k) = ek132. We denote this model as G, since both the total number of nodes N and edges K are fully determined, onceandare given. Notice that is the logarithm of the number of nodes with k = 1, while e/is the maximum degree of the graph. Aiello et al. have shown that the Molloy and Reed criterium predicts that G ,has a giant component whenc= 3.47875 . . . , and have proved that the second largest components are of size O(log N ) for 2 cand O(1) for 1 2, while the graph is almost surely connected for 0 7/3, while for 3. Conversely, if 2 3, L is O(log log N ), while the diameter is O(log N ) 125. Similar results were obtained by Cohen and Havlin 133. More recently, Chung et al. have shown that the spectrum of the adjacency matrix of random power law graphs follows a power law distribution, while the eigenvalues of the normalized Laplacian follow the semicircle law 134. Several other recipes to construct static scale-free networks, based on assuming that a node has some intrinsic properties, have been proposed in the physics community. In the model by Goh et al. 42, each node i is assigned a weight (or tness) wi=i, where i =1, 2 , . . . , N is the node index andis a tunable parameter in 0, 1). Two different nodes, i and j , are selected with probabilities equal to the normalized weights wi /lwland wj /lwl, respectively, and are connected if there is not already a link between them. The process is repeated until mN links are made in the system, so thatk = 2m. When= 0 one obtains a ER random graph. When= 0, the graph obtained has a power law degree distribution P (k) kwith an exponen=1 + 1/. Thus, by varyingin 0, 1) one obtains an exponentin the range 2 . The betweenness distribution follows a power law with an exponent= 2.2 for any value of in the range 2 3 42,45. A similar tness model was studied by Caldarelli et al. 135. The model starts with N isolated nodes, and associatesat every node i a tnessi, which is a real number taken from a tness distribution(). For every couple of nodes, i and j , a link is drawn with a probability f (i,j), with fbeing a symmetric function of its arguments. The model generates power-law P (k)for various tness distributions and attaching rules, while it gives ER random graph if f (i,j) = pi, j. Recently, Masuda et al. focused on the threshold graph model which is a subclass of the previousmodel particularly suited to the analytical treatment. The connectivity betw -een a pair of nodes in the model is determined by whether the sum of the tness of the pair exceeds a given threshold, namely f (i,j) = 1 ifi+j, and f (i,j) = 0 otherwise 136. We nally mention gradient networks, i.e. directed graphs induced by local gradients of a scalar eld distributed on the nodes 137139. In the simplest model, Toroczkai and Bassler consider a given substrate network, S, and a non-degenerate scalar, hi, associated with each node i and describing the potential of the node. Then, the gradient network is constructed as the collection of directed links pointing from each node to whichever of its neighbors on has the highest potential 137. It can be shown that gradient networks consist only of trees. Furthermore, if the substrate network S is scale-free, and the scalars hiare ind -ependent identically distributed random variables, then the associated gradient network is scale-free