I have a graph data structure that represents a rail network. The nodes of the network are the train stations and the edges are the connections between stations.

Running PageRank on this graph gives me a way to rank the stations by importance. But I want to rank the connections between stations, the edges of the graph, by importance.

Is there an appropriate algorithm to do this? Is there a way to reformat the graph so that I can run PageRank for edges?

  • 1
    $\begingroup$ What have you tried and where did you get stuck? There's a rather standard transformation from one graph to another so that edges in one correspond to nodes in the other, and vice versa. $\endgroup$ – Raphael Apr 5 '16 at 12:01
  • 1
    $\begingroup$ Are you positive that page rank is a suitable measure of importance in this application? $\endgroup$ – Raphael Apr 5 '16 at 12:02
  • 1
    $\begingroup$ PageRank on nodes would mean how much they're connected to the rest of the network. What would PageRank mean on edges? $\endgroup$ – Auberon Apr 5 '16 at 14:35
  • 1
    $\begingroup$ You need to define what you mean by importance before you can decide whether any particular algorithm can calculate it correctly. $\endgroup$ – reinierpost Apr 5 '16 at 14:56
  • $\begingroup$ Also, are you sure your data structure is appropriate? Railway lines very often have junctions that aren't at stations. The true structure is often not that there are lines from city A to cities B and C but, rather, there's a line from A to some point X, where there is no station, and from X to B and C. This seems relevant to your notion of importance since, if the line from A to X is blocked, you can't get to B or C. $\endgroup$ – David Richerby Apr 5 '16 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.