Re: [igraph] Alpha Centrality Function Crashes

[Gabor Csardi]

Judd, it is not difficult, here is some example code:

library(igraph)
library(Matrix)

## Random graph of the same "size" as yours 
g <- erdos.renyi.game(58000, 87000, type="gnm", dir=TRUE)

## Convert it to a sparse matrix. 
el <- get.edgelist(g) + 1
M <- spMatrix(vcount(g), vcount(g), i=el[,2], j=el[,1], x=rep(1,nrow(el)))
M <- as(M, "dgCMatrix")

## This does not work with Matrix, so if you want to
## exclude loop edges, call 'simplify()' on your graph
### diag(M) <- 0

## Create an identity matrix
M2 <- spMatrix(vcount(g), vcount(g), i=1:vcount(g), j=1:vcount(g),
               x=rep(1, vcount(g)))
M2 <- as(M2, "dgCMatrix")

## This is the 'exo' vector, replace rep() with your values,
e <- spMatrix(vcount(g), 1, i=1:vcount(g), j=rep(1,vcount(g)), x=rep(1.0, 
vcount(g)))
e <- as(e, "dgCMatrix")

## Solve the equation and convert the result to an ordiniry
## matrix with a single column
alpha <- 1
M3 <- M2- alpha*M
system.time(r <- solve(M3, e))
r <- as.matrix(r)

I could run this in 6-7 minutes on a fairly fast machine 
(ADM Opteron 248) with 6Gb memory.

It might happen that the equation cannot be solved, then you'll get
an error message that the matrix is singular.

G.

On Thu, Apr 24, 2008 at 04:15:05PM -0700, Judd Antin wrote:
> Gabor,
> 
> Thanks for the suggestion. That may be a little beyond my abilities. 
> It's easy enough for me to get an edgelist, and I can see roughly which 
> equation I'll need to solve. However, I'm not sure of how to coerce the 
> edgelist into a sparse matrix, nor how exactly to use the sparse matrix 
> solver.
> 
> Any help is greatly appreciated!
> 
> --Judd
> 
> 
> 
> Gabor Csardi wrote:
> >Judd, 
> >
> >I get
> >
> >>g <- erdos.renyi.game(40000, 90000, type="gnm")
> >>alpha.centrality(g)
> >Error in get.adjacency(graph) : 
> >  At vector.pmt:408 : cannot reserve space for vector, Out of memory
> >
> >Yes, this function uses an adjacency matrix, so you cannot use it
> >on such a big graph. You can try the 'Matrix' package. 
> >See the code of 'alpha.centrality', get the edge list of 
> >the graph with 'get.edgelist', convert it to a (sparse) Matrix,
> >and solve the equation with the sparse matrix solver.
> >It should not be too difficult, i can help you if you need help.
> >
> >Gabor
> >
> >On Thu, Apr 24, 2008 at 08:37:10AM -0700, Judd Antin wrote:
> >>Hi all,
> >>
> >>I've been using igraph in R to look at a a very large, sparse directed 
> >>network of about 58,000 nodes and 87,000 edges. I am interested in 
> >>calculating alpha centrality scores, but the alpha.centrality function 
> >>crashes R for me instantaneously. I've tried this on both Windows and 
> >>Mac builds of the library (in case of a platform dependent issue), with 
> >>the same results.
> >>
> >>Does anyone have any insight on how I could get this to work? Is the 
> >>size of the network simply too large? I also noticed in the manual that 
> >>'singular adjacency matrices' can cause problems for the algorithm, but 
> >>I'm not sure what a 'singular adjacency matrix' is.
> >>
> >>Any advice appreciated.
> >>
> >>Thanks!
> >>
> >>--Judd
> >>
> >>--
> >>Judd Antin
> >>School of Information
> >>University of California Berkeley
> >>address@hidden
> >>web: http://technotaste.com
> >>blog: http://technotaste.com/blog
> >>
> >>
> >>_______________________________________________
> >>igraph-help mailing list
> >>address@hidden
> >>http://lists.nongnu.org/mailman/listinfo/igraph-help
> >
> 
> 
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help

-- 
Csardi Gabor <address@hidden>    UNIL DGM