[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] Weighted graphs and the use of E(g)$weight as a distance me
From: |
Tamas Nepusz |
Subject: |
Re: [igraph] Weighted graphs and the use of E(g)$weight as a distance measure |
Date: |
Mon, 13 Jul 2015 21:26:57 +0200 |
User-agent: |
Mutt/1.5.23 (2014-03-12) |
> As I understand it, all of the igraph functions for measures of centrality
> and community detection treat the weights in a weighted graph as distance
> measures.
This is not true; it depends on the centrality measure. Closeness and
betweenness centrality treats the weights as distances, while PageRank and
eigenvector centrality treats them as similarities. As for community detection,
I think all but the edge betweenness method treats weights as similarities.
> It would be very convenient if for the graph functions for measures of
> centrality and community detection there were an argument "distance" for
> which a default value of distance=TRUE results in the function performing
> as it does now (for downward compatibility). A value of distance=FALSE
> would result in the function using 1/E(g)$weight rather than E(g)$weight as
> the distance measure and a value of distance="vector" would result in a
> user-defined distance, "vector".
The problem with this approach is that it is unclear how the transformation
would affect the underlying method; note that there are multiple ways of
converting a similarity score to a distance score and the suitability of
particular method usually depends on many factors. I can think of at least four
ways right now off the top of my head for such a conversion:
- similarity = 1/distance
- similarity = max(distance)-distance
- similarity = 1 - (distance-min(distance)) / (max(distance)-min(distance))
- similarity = some-logistic-function(distance)
where some-logistic-function in the last case means an appropriately tuned
logistic function that maps the median or the mean distance to 0.5 and some
pre-defined quantiles (say, the upper and lower quartile) to pre-defined values
(say, 0.1 and 0.9). Actually, I usually prefer the last option as it has the
added bonus of reducing the effect of outliers (especially when I use the
median weight as the midpoint), but that's just a matter of taste.
> Along the same vein, much of the existing documentation for the igraph
> package pretty much ignores how the package handles weighted graphs.
You are probably right as this is not the first time this question has popped
up on the mailing lists:
https://lists.nongnu.org/archive/html/igraph-help/2010-07/msg00052.html
https://lists.nongnu.org/archive/html/igraph-help/2013-07/msg00010.html
https://lists.nongnu.org/archive/html/igraph-help/2015-03/msg00037.html
The issue is already in our issue tracker (and sadly it has been there for more
than two years now):
https://github.com/igraph/igraph/issues/504
Anyway, thanks for the suggestion, we will try to clarify the documentation!
All the best,
T.