Indeed, none of the papers I mentioned are directly concerned with the average distance, but they allow approximating individual distances, which I can then use to estimate the average distance. However, right now I needed a quick solution, so I'll check these approximate methods later.
I've implemented your method and mine, and tested them by applying them several times to a few (smaller) networks. With reasonably large samples, it is possible to get close enough (to my opinion) to the actual values, in average, in a significantly smaller amount of time than when doing exact calculations. Also, your method is much faster, even if it seems to lead to a slightly higher variance. So, problem solved, thanks. Vincent On Mon, Jun 9, 2014 at 11:08 PM, Gábor Csárdi <[email protected]> wrote: > 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
