average path length and finding all possible paths between 2 vertices
Dear all, I am new to graph tools. I am trying to calculate the average path length (not the shortest) between any 2 given vertices. Which function should I use for that? Also, I would like to create a list of all possible paths between any 2 given vertices. Here I assume the edges are directed in both cases. So far I haven't found proper functions in the documentation for these calculations. I would appreciate any suggestions. Thanks in advance! Hu -- View this message in context: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/... Sent from the Main discussion list for the graph-tool project mailing list archive at Nabble.com.
On 11/02/2013 02:27 AM, hux wrote:
Dear all,
I am new to graph tools. I am trying to calculate the average path length (not the shortest) between any 2 given vertices. Which function should I use for that? Also, I would like to create a list of all possible paths between any 2 given vertices.
Here I assume the edges are directed in both cases.
So far I haven't found proper functions in the documentation for these calculations. I would appreciate any suggestions.
There is no function in the library which computes this. The reason for this is that typically the number of distinct paths grows very fast (super-polynomially) with the size of the network. Hence even if you write a fast algorithm for this (which can't be done), the result would not even fit in memory. Cheers, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
OK I see. However, the networks I am dealing with are relatively small, on average ~25 vertices and ~60 edges. I think l could try to write some code of my own to find the paths. Could you maybe show me some references for any available path finding algorithm? Thanks a lot! Hu On Nov 2, 2013 5:45 AM, "Tiago de Paula Peixoto" <tiago@skewed.de> wrote:
On 11/02/2013 02:27 AM, hux wrote:
Dear all,
I am new to graph tools. I am trying to calculate the average path length (not the shortest) between any 2 given vertices. Which function should I use for that? Also, I would like to create a list of all possible paths between any 2 given vertices.
Here I assume the edges are directed in both cases.
So far I haven't found proper functions in the documentation for these calculations. I would appreciate any suggestions.
There is no function in the library which computes this. The reason for this is that typically the number of distinct paths grows very fast (super-polynomially) with the size of the network. Hence even if you write a fast algorithm for this (which can't be done), the result would not even fit in memory.
Cheers, Tiago
-- Tiago de Paula Peixoto <tiago@skewed.de>
_______________________________________________ graph-tool mailing list graph-tool@skewed.de http://lists.skewed.de/mailman/listinfo/graph-tool
Dear Tiago, You have mentioned in the previous an email that "the number of distinct paths [between 2 arbitrary verices] grows very fast (super-polynomially) with the size of the network". Could please point me any reference on that(papers/books)? Thanks! Best, Hu On 11/2/2013 1:28 PM, Xiaohu Hu wrote:
OK I see. However, the networks I am dealing with are relatively small, on average ~25 vertices and ~60 edges. I think l could try to write some code of my own to find the paths. Could you maybe show me some references for any available path finding algorithm?
Thanks a lot!
Hu
On Nov 2, 2013 5:45 AM, "Tiago de Paula Peixoto" <tiago@skewed.de <mailto:tiago@skewed.de>> wrote:
On 11/02/2013 02:27 AM, hux wrote: > Dear all, > > I am new to graph tools. I am trying to calculate the average path length > (not the shortest) between any 2 given vertices. Which function should I use > for that? Also, I would like to create a list of all possible paths between > any 2 given vertices. > > Here I assume the edges are directed in both cases. > > So far I haven't found proper functions in the documentation for these > calculations. I would appreciate any suggestions.
There is no function in the library which computes this. The reason for this is that typically the number of distinct paths grows very fast (super-polynomially) with the size of the network. Hence even if you write a fast algorithm for this (which can't be done), the result would not even fit in memory.
Cheers, Tiago
-- Tiago de Paula Peixoto <tiago@skewed.de <mailto:tiago@skewed.de>>
_______________________________________________ graph-tool mailing list graph-tool@skewed.de <mailto:graph-tool@skewed.de> http://lists.skewed.de/mailman/listinfo/graph-tool
On 11/22/2013 04:24 AM, Xiaohu Hu wrote:
Dear Tiago,
You have mentioned in the previous an email that "the number of distinct paths [between 2 arbitrary verices] grows very fast (super-polynomially) with the size of the network". Could please point me any reference on that(papers/books)? Thanks!
I don't have a reference now on the top of my head, but it is easy to see that in some examples this number increases very fast. Consider for instance the complete graph, where all vertices are directly connected. The shortest paths are trivial, but the number of distinct (not shortest) paths is very large. For instance, one could visit every other vertex once before reaching the target. There are (N-2)! such paths, so the number of shortest paths is at least this large, which is super-polynomial. Note that in this case the average path length will approach N which is quite different from the shortest path of length 1... In general something similar will happen for random graphs as well. Usually obtaining average properties of _all_ paths is not very meaningful... Cheers, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
participants (3)
-
hux -
Tiago de Paula Peixoto -
Xiaohu Hu