average path length and finding all possible paths between 2 vertices

graph-tool
1

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

2

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

3

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

attachment.html (1.91 KB)

4

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

attachment.html (3.26 KB)

5

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