[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.
Cheers,
Tamas