Re: [igraph] question about average.path.length(graph, directed=TRUE, unconnected=TRUE)

[Tamas Nepusz]

Thanks. And you think the possible "real" path length within the graph is the number of nodes in the network (minus 1).

Well, let's say that it's a worst-case estimate :) But anyway, my standpoint is that the question of "what is the average path length in this graph" is ill-posed if the graph is disconnected, and basically all the solutions that people have come up with so far to solve this problem are not theoretically well-grounded. You could:

- say that the average path length is infinite

- ignore all the disconnected vertex pairs and calculate the average for the rest

- pick any number between d+1 and |V|-1 (or even above) and use that for disconnected vertex pairs

- calculate average path lengths for the components and take the average

- calculate average path lengths for the components and take the average weighted by the component size

Two of these solutions were added to igraph but I consider both of them 'wrong' in some sense. I think that the real solution is to report the average path length of the individual connected components *separately*. You can do this easily with igraph, and then you are free to do whatever magic you want to do with the per-component average path lengths and the component sizes to compress all that data into a single number (and lose some of the information that the full per-component average path length vector conveys in the process).

T.

 

I just thought that may be it is too stringent. One unconnected node may contribute much to the average length of shortest path (consider one case, only a few nodes are not connected to the connected component). If the diameter of the connected component is d, how about to define the distance between unconnected nodes as d+1 or 2d?

Thanks again

Best

Quanwei

From: Tamas Nepusz <address@hidden>
Reply-To: Help for igraph users <address@hidden>
Date: Sunday, September 6, 2015 9:40 AM
To: Help for igraph users <address@hidden>
Subject: Re: [igraph] question about average.path.length(graph, directed=TRUE, unconnected=TRUE)

Hello,

What else would you do with them? :) Obviously we cannot count them with an infinite distance because that would make the average distance infinite as well. We cannot ignore them either, because a disconnected graph with 1 million vertices and a single edge would have an average path length of 1 if we did that. So, the best we can do is to take them into account with a distance that is larger than any possible "real" path length within the graph.

T.

T.

On Sun, Sep 6, 2015 at 2:37 PM, Qunawei Zhang <address@hidden> wrote:

Hello:

Would you please explain more how you calculate the distance among unconnected nodes? Why the length of the missing paths are counted having length vcount(graph). Thanks

unconnected

What to do if the graph is unconnected (not strongly connected if directed paths are considered). If TRUE only the lengths of the existing paths are considered and averaged; if FALSE the length of the missing paths are counted having length vcount(graph), one longer than the longest possible geodesic in the network. Best Quanwei

_______________________________________________
igraph-help mailing list
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraph-help

_______________________________________________ igraph-help mailing list address@hidden https://lists.nongnu.org/mailman/listinfo/igraph-help

_______________________________________________
igraph-help mailing list
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraph-help