Re: [igraph] pagerank implementation questions

[Tamas Nepusz]

> I just wonder what's the largest graph that igraph
> developers have used with igraph
As for me, I hardly ever used igraph with graphs larger than a few  
thousand nodes, but as far as I know, Gabor used it with graphs with  
millions of nodes and edges. Maybe he'll post some representative  
figures soon... Gabor? :)

> and what's the performance of pagerank convergence speed (in
> particular)?
I just tested it with some randomly generated Barabasi-Albert graphs  
(n=number of nodes, m=number of outgoing edges for each node). The  
first number is the wall clock time in seconds needed to actually  
generate the graph, the second is the wall clock time in seconds  
needed to calculate the pagerank. The benchmark was run on a MacBook  
with an Intel Core Duo 1.83GHz processor and 512MB of RAM, using the  
Python interface of igraph (this means a small overhead compared to  
using the C interface directly).

n=  10000, m= 10:   0.03 /   0.02
n=  10000, m=100:   0.29 /   0.10
n= 100000, m= 10:   0.41 /   0.31
n= 100000, m=100: 103.79 /  36.16
n=1000000, m= 10:  73.37 /  70.81

I also tried it with n=1000000 and m=100, but after a while it  
started swapping heavily - which is no surprise: this graph has 10^8  
edges, and since igraph uses an indexed edge list representation at  
present, both endpoints of an edge are stored in 4 bytes. That means  
that at least 8 bytes are needed per edge (not counting the index  
tables to make lookups faster), so I'd need 8*10^8 bytes (approx. 762  
Mbytes) of memory to store the graph itself, without index tables.  
Maybe I'll try it once on a computer with more memory.

--
Tamas Nepusz <address@hidden>             MTA RMKI, BME MIT