igraph-help
[Top][All Lists]

## Re: [igraph] Question on igraph_community_fastgreedy

 From: Tamas Nepusz Subject: Re: [igraph] Question on igraph_community_fastgreedy Date: Wed, 27 Feb 2008 23:21:23 +0100

*** I assume that this means the current iGraph version still represents the
```original CNM algorithm?
```
Almost. The original source by Clauset has been rewritten from scratch in C and the data structures were built according to the Wakita paper, so we were able to gain some speed improvement this way. However, the heuristic variations have not been implemented yet. It is somewhere in our bug tracker as a feature request.
```
```
*** Just to clarify, since the input network/graph in CNM (Fast Greedy) is assumed to be the individual link pairs, then the "weights" are really any
```"arbitrary" >0 (possibly >=0) value for each specific link node pair?
```
Yes, the weights (any positive value is allowed) are assigned to the individual edges of the original network. (or, if you omit the weights argument, every link will have an equal weight).
```
```
*** So, I'm a little confused by the "sum of the weights of their adjacent edges" since the input weights are on a link pair by link pair basis. Isn't
```their only one weight possible per link pair?
```
Yes, each pair has only one weight. However, when one builds the initial dq matrix, its elements are defined as follows: A_ij - (d_i d_j)/2m where A_ij is the corresponding element in the adjacency matrix, d_i is the degree of the ith vertex and d_j is the degree of the jth vertex. m is the number of edges. When weights are assigned to the individual edges, the degree of the vertex (d_i) is defined as the total weight of the edges adjacent to this particular vertex. Similarly, m is the total sum of the edge weights. Note that this definition is equivalent to the unweighted case when all weights are equal to 1.
```
--
Tamas

```