Thread: Graph Algorithm

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.

Perhaps I'm totally wrong, but are you sure what they plot is not against , which would make sense? (and is in no way related to a degree) In other words, they plot the cumulative distribution function of the distribution of the random variable , on a log-log scale. Or not?

Hrm...looking at it, this is possible. I'm just confused because they're trying to show that the degree distribution of a sampled subgraph is different than its supergraph...and I'm not sure why they're calculating shortest paths to do this.