Properties of dense partially random graphs

RISAU GUSMAN, SEBASTIAN

PHYSICAL REVIEW E - STATISTICAL PHYSICS, PLASMAS, FLUIDS AND RELATED INTERDISCIPLINARY TOPICS

American Physical Society

Año: 2004 vol. 70 p. 561271 - 5612712

1063-651X

We study the properties of random graphs where for each vertex a neighborhood has been previously defined. The probability of an edge joining two vertices depends on whether the vertices are neighbors or not, as happens in small-world graphs (SWG's). But we consider the case where the average degree of each node is of order of the size of the graph (unlike SWG's, which are sparse). This allows us to calculate the mean distance and clustering, which are qualitatively similar (although not in such a dramatic scale range) to the case of SWG's. We also obtain analytically the distribution of eigenvalues of the corresponding adjacency matrices. This distribution is discrete for large eigenvalues and continuous for small eigenvalues. The continuous part of the distribution follows a semicircle law, whose width is proportional to the "disorder" of the graph, whereas the discrete part is simply a rescaling of the spectrum of the substrate. We apply our results to the calculation of the mixing rate and the synchronizability threshold.