[igraph] arpack implementation in igraph is slow?

[Massimo Franceschet]

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