Re: [igraph] Edge weights and community detection

[Tamas Nepusz]

Hi,

> I have a weighted graph where the edge weights have only two values:
> either w1 or
> w2. I noticed that some algorithms are sensitive to the actual values
> of w1, w2, while
> others seem to be not.
This is indeed very likely for some of the algorithms.

> Do the community detection algorithms do any normalization,
> scaling of the edge weights or smth before the actual detection, or
> just use the supplied weigths?
As far as I know, none of the algorithms do any preprocessing on the weights
in igraph.

> 1) Are the CD algorithms supposed to be sensitive to the actual
> weights w1, w2, or to their
> ratio w2/w1?
I'd say they are not guaranteed to be sensitive only to the actual ratio. It
depends on the community detection method of course, and the easiest is to
try it yourself on some benchmark graphs. But I also think that the
community detection methods based on the modularity score (e.g., the "fast
greedy" method or the multilevel method) should not be sensitive on the
absolute values of the weights as the modularity measure itself does not
change if you multiply all the weights by a constant. Similarly, the edge
betweenness method should not be affected by a constant multiplicative
factor either because such a multiplication cannot change the shortest paths
in the network on which the algorithm is based (unless the multiplication
factor is zero of course).

> 2) How are the edges with weight=0 treated -- no connection between
> the respective vertices
> at all, or some (weak) connection is still assumed?
No connection is assumed for such vertices.

> 3) If there are many possible values of edge weights in a graph, would
> some scaling (i.e., multiplying
> all edge weights by a constant factor) affect the community detection results?
As mentioned above for point 1), the modularity-based methods and the edge
betweenness method should not be affected by the absolute values of the
weights as long as the ratios stay the same.

-- 
Tamas