On the proportion of edges that belong to shortest paths in random graphs
(2007) Proceedings of Dynamo’s first meeting on Dynamic Networks — Location: Salerno, Italy
Files
07BHJ_Salerno.pdf
Restricted Access - Adobe PDF
- 26.77 KB
Details
- Authors
- Abstract
- We consider the problem of determining the proportion of edges that are discovered in a random 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. In order to perform our analysis, we introduce a new way of characteriz- ing the distribution of distances between nodes. Our method outperforms previous similar analysis and leads to estimates that coincide remarkably well with numerical simulations.
- Affiliations
Citations
Blondel, V., Hendrickx, J., & Jungers, R. (2007). On the proportion of edges that belong to shortest paths in random graphs. Proceedings of Dynamo’s first meeting on Dynamic Networks, Salerno, Italy. https://hdl.handle.net/2078.5/254658