
From:  Vincent Labatut 
Subject:  Re: [igraph] Estimation of the average distance 
Date:  Wed, 11 Jun 2014 17:36:43 +0300 
On Mon, Jun 9, 2014 at 4:01 PM, Vincent Labatut <address@hidden> wrote:That's what I suggested. With the difference that it is most probably
> 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?
not worth calculating the distances _between_ the selected nodes, as
opposed to calculating the distances _from_ the selected nodes to all
other nodes.
None of these papers are about the _average_ distance imho. They are
> The link you propose is interesting, but not all my networks are clearly
> scalefree. 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/orionwosn10.pdf
> source code : http://current.cs.ucsb.edu/rigel/
>  "Fast Fully Dynamic Landmarkbased 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
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/16741056/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
>> >
>> >
>> > _______________________________________________
>> > igraphhelp mailing list
>> > address@hidden
>> > https://lists.nongnu.org/mailman/listinfo/igraphhelp
>> >
>
>
[Prev in Thread]  Current Thread  [Next in Thread] 