[Top][All Lists]

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

Re: [igraph] iGraph benchmarks

From: Tamás Nepusz
Subject: Re: [igraph] iGraph benchmarks
Date: Fri, 26 Aug 2011 15:19:17 +0200

Hi Victor,

> is there any iGraph benchmark that shows the upper bounds of the tool?
The tool is bounded by 1) the amount of memory available on your machine (as it 
has to keep the entire graph in memory all the time) and 2) the amount of time 
you have ;) I know it doesn't say much, but that's the case.

As a rough guideline, I can say that I successfully managed to calculate the 
*diameter* of a graph with 15 million edges and 2 million vertices, but it took 
12 days. The time complexity of diameter calculation is O(|V|*|E|), i.e. the 
same as edge betweenness calculation, so it gives you an idea.

As for your graph, edge betweenness calculation on a graph with 2K nodes and 
32K edges should not take 10 hours. I have just generated a random Erdos-Renyi 
graph with 2K nodes and 32K edges and it terminated in a few seconds. Same for 
a Barabasi-Albert graph with 2K nodes and 32K edges. If you can send me your 
network, I'll try to run it on my own computer and check how much time it 
should take.


reply via email to

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