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 <[email protected]> _______________________________________________ graph-tool mailing list [email protected] http://lists.skewed.de/mailman/listinfo/graph-tool
