[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


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.


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])

# 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 

reply via email to

[Prev in Thread] Current Thread [Next in Thread]