[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## [igraph] arpack implementation in igraph is slow?

**From**: |
Massimo Franceschet |

**Subject**: |
[igraph] arpack implementation in igraph is slow? |

**Date**: |
Sat, 18 Feb 2012 10:42:19 +0100 |

Hi.
I am looking for an efficient implementation of the problem of finding the
second smallest eigenpair of a large sparse matrix (the Laplacian of an
undirected graph). I found the arpack function of igraph and tried it. However,
for some reason I cannot get, it is rather inefficient (it is more efficient to
compute *all* eigenpairs with eigen function than computing only a few of
them). In the following, I give the code I used. Any hint to get a faster
implementation is very welcome.
Thanks.
Massimo Franceschet
http://users.dimi.uniud.it/~massimo.franceschet/
# This function computes the product of the Laplacian of a graph (represented
as a sparse
# matrix using an adjacency list (adj)) and a vector (x).
# It takes linear time if the matrix is sparse
f = function(x, extra=adj) {
n = length(adj)
v = x
for (i in 0:(n-1)) {
# neighbors of node i
nei = adj[[i+1]]
# i-th component of matrix-vector product
v[i+1] = x[i+1] * length(nei) - sum(x[nei+1])
}
v
}
# This code generates a scale-free graph with 100 nodes and represent it
# using an adjacency list (I use the neighbors function of igraph)
g = simplify(barabasi.game(1000, directed=FALSE, m=2))
n = vcount(g)
adj = NULL
for (i in 0:(n-1)) {
adj[[i+1]] = neighbors(g, i)
}
# I compute the two smallest eigenpairs with arpack function (setting ncv=3 is
even worse)
tic = proc.time()
out = arpack(f, options=list(n=n, nev=2, ncv=n, which="SM"), sym=TRUE)
proc.time() - tic
# It takes this time
user system elapsed
11.403 0.044 11.448
# I compute *all* eigenpairs with eigen fuction
L = graph.laplacian(g)
tic = proc.time()
eig = eigen(L)
proc.time() - tic
# It takes this time (20 times faster!)
user system elapsed
1.135 0.064 0.664

**[igraph] arpack implementation in igraph is slow?**,
*Massimo Franceschet* **<=**