[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] directed, weighted leading.eigenvector* algorithms
From: |
Tamas Nepusz |
Subject: |
Re: [igraph] directed, weighted leading.eigenvector* algorithms |
Date: |
Sun, 7 Nov 2010 00:46:46 +0000 |
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