Mathematics – Probability
Scientific paper
2005-02-28
Mathematics
Probability
30 pages, 2 figures
Scientific paper
In this paper we derive results concerning the connected components and the diameter of random graphs with an arbitrary i.i.d. degree sequence. We study these properties primarily, but not exclusively, when the tail of the degree distribution is regularly varying with exponent $1-\tau$. There are three distinct cases: (i) $\tau>3$, where the degrees have finite variance, (ii) $\tau\in (2,3)$, where the degrees have infinite variance, but finite mean, and (iii) $\tau\in (1,2)$, where the degrees have infinite mean. These random graphs can serve as models for complex networks where degree power laws are observed. Our results are twofold. First, we give a criterion when there exists a unique largest connected component of size proportional to the size of the graph, and study sizes of the other connected components. Secondly, we establish a phase transition for the diameter when $\tau \in (2,3)$. Indeed, we show that for $\tau>2$ and when nodes with degree 2 are present with positive probability, the diameter of the random graph is, with high probability, bounded below by a constant times the logarithm of the size of the graph. On the other hand, assuming that all degrees are at least 3 or more, we show that, for $\tau \in (2,3)$, the diameter of the graph is with high probability bounded from above by a constant times the $\log \log$ of the size of the graph.
der Hofstad Remco van
Hooghiemstra Gerard
Znamenski Dmitri
No associations
LandOfFree
Random graphs with arbitrary i.i.d. degrees 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 Random graphs with arbitrary i.i.d. degrees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random graphs with arbitrary i.i.d. degrees will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-142588