Distance distribution in random graphs and application to networks exploration

Details Distance distribution in random graphs and application to networks exploration Distance distribution in random graphs and application to networks exploration

2007-06-22

arxiv.org/abs/0706.3322v2

Physics

Condensed Matter

Statistical Mechanics

12 pages, 8 figures (18 .eps files)

Scientific paper

10.1103/PhysRevE.76.066101

We consider the problem of determining the proportion of edges that are discovered in an Erdos-Renyi graph when one constructs all shortest paths from a given source node to all other nodes. This problem is equivalent to the one of determining the proportion of edges connecting nodes that are at identical distance from the source node. The evolution of this quantity with the probability of existence of the edges exhibits intriguing oscillatory behavior. In order to perform our analysis, we introduce a new way of computing the distribution of distances between nodes. Our method outperforms previous similar analyses and leads to estimates that coincide remarkably well with numerical simulations. It allows us to characterize the phase transitions appearing when the connectivity probability varies.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-187831