[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [igraph] Alpha Centrality Function Crashes

From: Judd Antin
Subject: Re: [igraph] Alpha Centrality Function Crashes
Date: Mon, 28 Apr 2008 10:09:24 -0700
User-agent: Thunderbird (Windows/20080213)

Thanks so much for the help. This worked, but after all the equation turned out not to be solvable!

This will be incredibly useful for a variety of large data-set projects, though, so thanks again for your time and effort!


Gabor Csardi wrote:
Judd, it is not difficult, here is some example code:


## 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, 
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.


On Thu, Apr 24, 2008 at 04:15:05PM -0700, Judd Antin wrote:

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!


Gabor Csardi wrote:
I get

g <- erdos.renyi.game(40000, 90000, type="gnm")
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.


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.



Judd Antin
School of Information
University of California Berkeley
web: http://technotaste.com
blog: http://technotaste.com/blog

igraph-help mailing list

igraph-help mailing list

reply via email to

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