On Mon, Jun 9, 2014 at 4:01 PM, Vincent Labatut <[email protected]> wrote: > Hi Gábor, > > thanks for your answer. I was actually asking if such a method was already > implemented in igraph (because I'm lazy and didn't want to use a different > tool if it was the case). I was considering sampling a limited number of > pairs of nodes, using shortest.paths() to process the distance between them, > and averaging them, as an estimation. What do you thing of this approach?
That's what I suggested. With the difference that it is most probably not worth calculating the distances _between_ the selected nodes, as opposed to calculating the distances _from_ the selected nodes to all other nodes. > The link you propose is interesting, but not all my networks are clearly > scale-free. I had found other related works, too. I haven't checked the > associated tools yet, but I list them here anyway, since they might interest > other igraph users: > - "Fast Shortest Path Distance Estimation in Large Networks", Potamias et > al. 2009. > article: http://chato.cl/papers/potamias_2009_fast_shortest_path.pdf > source code: http://sourceforge.net/projects/landmarksel/ > - "Orion: Shortest Path Estimation for Large Social Graphs", Zhao et al. > 2010. > article: > http://www.cs.ucsb.edu/~ravenben/publications/pdf/orion-wosn10.pdf > source code : http://current.cs.ucsb.edu/rigel/ > - "Fast Fully Dynamic Landmark-based Estimation of Shortest Path Distances > in Very Large Graphs", Tretyakov et al. 2011. > article: http://vvv.cs.ut.ee/~dumas/pubs/cikm2011.pdf > source code: couldn't find any None of these papers are about the _average_ distance imho. They are about estimating distances of _individual_ node pairs. Gabor > > Best, > Vincent > > > On Mon, Jun 9, 2014 at 9:51 PM, Gábor Csárdi <[email protected]> wrote: >> >> Hi Vincent, >> >> you can sample some source vertices and calculate distances from them >> to all other vertices. This be unbiased for uncorrelated graphs, but >> not for correlated ones (like real graphs). >> >> There are also more sophisticated ways, e.g. a quick search got me this: >> http://iopscience.iop.org/1674-1056/17/7/001 >> >> Best, >> Gabor >> >> On Mon, Jun 9, 2014 at 11:37 AM, Vincent Labatut >> <[email protected]> wrote: >> > Hello, >> > >> > I want to process the average distance of some large graphs. I do not >> > need >> > the paths themselves, or the individual lengths of all possible shortest >> > paths, but just the average value over the whole graph. >> > >> > However, when using the function average.path.length() (R version of >> > igraph), it takes too long (weeks) due to the size of the graphs. I >> > could do >> > with only an estimation of the average distance, so I was wondering if >> > there >> > was any way of processing such an approximation (I noticed some >> > functions >> > such as betweenness() have an 'estimate' version). >> > >> > Best regards, >> > Vincent >> > >> > >> > _______________________________________________ >> > igraph-help mailing list >> > [email protected] >> > https://lists.nongnu.org/mailman/listinfo/igraph-help >> > > > _______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
