An Estimation of the Shortest and Largest Average Path Length in Graphs of Given Density

Details An Estimation of the Shortest and Largest Average Path Length in Graphs of Given Density An Estimation of the Shortest and Largest Average Path Length in Graphs of Given Density

2011-01-13

arxiv.org/abs/1101.2549v1

Physics

Physics and Society

Scientific paper

Many real world networks (graphs) are observed to be 'small worlds', i.e., the average path length among nodes is small. On the other hand, it is somewhat unclear what other average path length values networks can produce. In particular, it is not known what the maximum and the minimum average path length values are. In this paper we provide a lower estimation for the shortest average path length (l) values in connected networks, and the largest possible average path length values in networks with given size and density. To the latter end, we construct a special family of graphs and calculate their average path lengths. We also demonstrate the correctness of our estimation by simulations.

Affiliated with

Also associated with

No associations

Rating

An Estimation of the Shortest and Largest Average Path Length in Graphs of Given Density 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 An Estimation of the Shortest and Largest Average Path Length in Graphs of Given Density, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Estimation of the Shortest and Largest Average Path Length in Graphs of Given Density will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-66487