Results 1 to 3 of 3

Math Help - Graph Algorithm

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    2

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Perhaps I'm totally wrong, but are you sure what they plot is not \log_{10} P(X>d) against \log_{10} d, which would make sense? (and d is in no way related to a degree) In other words, they plot the cumulative distribution function of the distribution of the random variable X, on a log-log scale. Or not?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2008
    Posts
    2
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Algorithm for determining if a graph is possible?
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 4th 2010, 01:12 PM
  2. algorithm for a graph theory problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: August 29th 2008, 04:18 AM
  3. Triangle-free graph algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 12th 2008, 01:38 AM
  4. Need a graph algorithm
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 6th 2008, 02:27 PM
  5. Replies: 0
    Last Post: November 6th 2007, 02:05 PM

Search Tags


/mathhelpforum @mathhelpforum