igraph-help
[Top][All Lists]

## [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) {
v = x
for (i in 0:(n-1)) {
# neighbors of node i
# 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)
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

```

reply via email to