RE: [igraph] Question on igraph_community_fastgreedy

[Thomas F. Brantle]

Thanks Tamas...Any estimate on how much faster based on nodes/edges?

Also, do the input IDs have to be contiguous, e.g., 0,1,2,3,4,5,6,7,8,9 or
can it be 0,1,2,3,4,15,16,17,28,29 with ID gaps but still be a fully
connected component. 

My guess is that I would need to remap Node IDs? Thanks again.

-----Original Message-----
From: address@hidden
[mailto:address@hidden On Behalf
Of Tamas Nepusz
Sent: Wednesday, February 27, 2008 5:21 PM
To: Help for igraph users
Subject: Re: [igraph] Question on igraph_community_fastgreedy

> *** 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



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