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?
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 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
