Re: [igraph] Estimation of the average distance

[Vincent Labatut]

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 <address@hidden> wrote:

On Mon, Jun 9, 2014 at 4:01 PM, Vincent Labatut <address@hidden> 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 <address@hidden> 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
>> <address@hidden> 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
>> > address@hidden
>> > https://lists.nongnu.org/mailman/listinfo/igraph-help
>> >
>
>