Physics – Condensed Matter – Disordered Systems and Neural Networks
Scientific paper
2004-09-28
Physics
Condensed Matter
Disordered Systems and Neural Networks
14 pages. To be published in Physical Review E
Scientific paper
10.1103/PhysRevE.70.056127
We study the properties of random graphs where for each vertex a {\it neighbourhood} has been previously defined. The probability of an edge joining two vertices depends on whether the vertices are neighbours or not, as happens in Small World Graphs (SWGs). But we consider the case where the average degree of each node is of order of the size of the graph (unlike SWGs, which are sparse). This allows us to calculate the mean distance and clustering, that are qualitatively similar (although not in such a dramatic scale range) to the case of SWGs. 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.
No associations
LandOfFree
Properties of dense partially random graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Properties of dense partially random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Properties of dense partially random graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-530662