Hi,

I'm trying to replicate some results from a paper, but having a little bit of trouble with the final step of their algorithm.

It's based on a random graph structure, so given a random graph with 50,000 nodes, and an average degree (it's an undirected graph) of 15 (so a probability of connection between two nodes of 0.0003), pick a random source node and 500 random destination nodes, and calculate the shortest paths between those source-destination pairs (using Dijkstra's algorithm).

This is all fine, up and working. However, what they've done is plot log10(degree) (this is a chosen degree, say 10^0.8 or so) again log10(P(X>d)). I'd assumed this X was our shortest paths, but this doesn't make any sense to me...shortest paths are shortest paths, how are they related back to the degree exactly?

I guess this long ramble of a question reduces to how are the shortest paths and the degrees related exactly?

Thanks for any help in advance.