Random graphs

PalE85 Palmer, E. M. Graphical Evolution. An introduction to the theory of random graphs. Wiley-Iiherscience Series in Discrete Mathematics, John Wiley and Sons, 1985. 

In the numerical simulation, we take a random graph of n = 1000 vertices with edge density varied accordingly to sparse graphs (p = 0.1), normal graphs... 

The appearance of a giant component in the evolution of random graphs, which corresponds to gelation in polymer science, was discovered to their surprise by Erdos P, Renyi A. ([34] below) more than a decade after Flory... 

Sequences folding into the same structure form neutral networks in sequence space. A mathematical model based on random graph theory was designed [16] in order to allow for the derivation of analytical expressions. Neutral networks are represented by graphs in sequence space that show an interesting percolation phenomenon depending on the... 

To discover new fitness peaks, the neutral network must be sufficiently extended, allowing neutral drift to effectively sample sequence space. A neutral network can be characterized by a mean fraction of neutral neighbors A (Reidys et al., 1997). If A exceeds a threshold A,., then the network is connected and dense, making it more likely the network percolates through sequence space. If A < Ac, the networks are partitioned into components. Using random graph theory, the threshold is derived analytically as... 

P. Erdos and A. Renyi. On random graphs. Publicationes Mathematicae, Debrecen (Hungary), 6, 290 (1959) for a discussion see N.Alon and J. H. Spencer. The Probabilistic Method. New York Wiley (1992). 

Balinska, K.T, Gargano, M.L. and Quintas, L.V. (2001) Two models for random graphs with bounded degree. Croat. Chem. Acta, 74, 207-223. 

Erdos, P. Renyi, A., On random graphs Publ. Math. Debrecen 1959, 6, 290-297. 

Random Graphs with Given Expected Degrees. 

The random graph models are one of the oldest network models, introduced in (Solomonoff Rapoport, 1951) and further studied in (Erdos Renyi, 1959) and (Erdos Renyi, 1960). These works identify two different classes of random graphs, called Gn,u and Gn,p and defined by the following connection rules ... 

The degree distribution is one of the important characteristics of this kind of networks because it affects their properties and behavior (R ka Barabasi, 2000). The random graph Gn,p has a binomial degree distribution. The probability pk that a randomly chosen vertex is cormected to exactly k others is (Newman et al., 2001) ... 

To determine if a network is a small-world, one can use the measures described below and compare them to the corresponding measures of a random graph. 

Since the mean and the median are practically identical for any reasonably symmetric distribution, the characteristic path length of a random graph is the mean value of the shortest path lengths between any two vertices. The characteristic path length of a random... 

The clustering coefficient of a random graph with mean degree 2 is... 

Newman, M. E. J. Strogatz, S. H. Watts, D. J. (2001). Random graphs with arbitrary degree distributions and their applications. Physical Reoiew E, Vol. 64 Orengo, C. A. Michie, A. D. Jones, S. Jones, D. T. Swindells, M. B. Thornton, J. M. (1997). CATH - a hierarchic classification of protein domain structures. Structure,... 

Supposing that the sample of the random graph to be constructed has n vertices in the observation window. Then, we generate an iid sample d, . .., d > 0 of candidates for vertex degrees according to the distribution shown in Figure 24.15a. 

Random graph models have been considered in the literature for a long time, starting in the middle of the last century see, for example, [37-39]. 

The model type for random geometric graphs described in the previous sections is rather different from random graphs considered in the literature see, for example, [40-45] for an overview. 

---