《电气工程及其自动化专业毕业设计外文翻译》由会员分享，可在线阅读，更多相关《电气工程及其自动化专业毕业设计外文翻译（35页珍藏版）》请在金锄头文库上搜索。
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 ensemble10of possible realizations,
6、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:gr
7、aphs 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 a
8、t 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, althou
9、gh 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 pr
10、oved 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 paramete
11、r 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
13、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
14、 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
