Critical behavior in inhomogeneous random graphs

Mathematics – Probability

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

26 pages

Scientific paper

We study the critical behavior of inhomogeneous random graphs where edges are present independently but with unequal edge occupation probabilities. The edge probabilities are moderated by vertex weights, and are such that the degree of vertex i is close in distribution to a Poisson random variable with parameter w_i, where w_i denotes the weight of vertex i. We choose the weights such that the weight of a uniformly chosen vertex converges in distribution to a limiting random variable W, in which case the proportion of vertices with degree k is close to the probability that a Poisson random variable with random parameter W takes the value k. We pay special attention to the power-law case, in which P(W\geq k) is proportional to k^{-(\tau-1)} for some power-law exponent \tau>3, a property which is then inherited by the asymptotic degree distribution. We show that the critical behavior depends sensitively on the properties of the asymptotic degree distribution moderated by the asymptotic weight distribution W. Indeed, when P(W\geq k) \leq ck^{-(\tau-1)} for all k\geq 1 and some \tau>4 and c>0, the largest critical connected component in a graph of size n is of order n^{2/3}, as on the Erd\H{o}s-R\'enyi random graph. When, instead, P(W\geq k)=ck^{-(\tau-1)}(1+o(1)) for k large and some \tau\in (3,4) and c>0, the largest critical connected component is of the much smaller order n^{(\tau-2)/(\tau-1)}.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Critical behavior in inhomogeneous 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 Critical behavior in inhomogeneous random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Critical behavior in inhomogeneous random graphs will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-159414

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.