Re: [igraph] directed, weighted leading.eigenvector* algorithms

[Tamas Nepusz]

Dear Carson,

> I see from the list archives that there has been some talk of weighted and/or 
> directed implementations of the leading.eigenvector* graph partitioning 
> algorithms (in the R package). Looking at the code of the latest version 
> however, I don't see any indication that this has been added (I'm not much of 
> a C programmer, so I may have missed something there).
I've just checked community.c in the development version and it's not there 
either -- so I guess it has not been implemented yet and no one is working on 
it (as far as I know).

> Does anyone have a working implementation of either/both a weighted and/or 
> directed variant of the algorithms (as suggested in [1] and [2])?
I am not aware of such implementations yet.

> Alternatively, does anyone know of another package that *does* have this 
> algorithm implemented?
Unfortunately not :(

> I'm not against compiling the source myself, so even a patched version, or 
> some suggestions to get me started on modifying it myself would be great!
The algorithm itself is in community.c, look for the functions called 
igraph_community_leading_eigenvector. (Ignore the _naive ones, they are not 
important). This function uses ARPACK to find the leading eigenvector of the 
modularity matrix. ARPACK requires the user to implement the matrix-vector 
multiplication operation corresponding to the matrix whose eigenvectors are 
being searched for; the actual multiplication is in 
igraph_i_community_leading_eigenvector (_i_ standing for "internal"). The data 
structure being used to pass all the necessary data to 
igraph_i_community_leading_eigenvector is defined in 
igraph_i_community_leading_eigenvector_data_t.

Adding support for weights is probably not a big deal; first, you would have to 
modify igraph_i_community_leading_eigenvector_data_t to contain an 
igraph_vector_t* corresponding to the edge weights, and to use an 
igraph_adjedgelist_t (which will be renamed to igraph_inclist_t in igraph 0.6) 
as you will need the *weights* of the edges in the matrix-vector multiplication 
(you cannot simply assume that every weight is equal to 1), and you can fetch 
the weights from the weight vector only if you need the IDs of the edges 
incident on a given vertex.

-- 
Tamas