search

snap-stanford / snap

Stanford Network Analysis Platform (SNAP) is a general purpose network analysis and graph mining library.
Other
2.16k stars 795 forks source link

TSnap::GetBetweennessCentr on 100.000 nodes takes days #214

Closed giorgiobovenzi closed 3 years ago

giorgiobovenzi commented 3 years ago

I'm just trying to use the library. We have seen that the TSnap::GetBetweennessCentr() on a graph with "only" 100.000 nodes takes literally DAYS to complete. Our target is to work with graphs with a few millions nodes. We have compiled a short/simple cpp console app in in VS2019. Compiled to x64 release.

The process stops acquiring memory at around 75MB, and uses about 10% of the CPU until completion, days later! For comparison with 10.000 nodes it used about 8MB and the same 10% of the CPU for about a minute. We have used 3 different PC with different combinations of CPU and RAM to test the performances. Same results.

Are these the expected performances? Should we try to set some compile options we may have overlooked? What could possible be wrong?

Thanks.

roks commented 3 years ago

Try to compute the values for a subset of nodes, which you can then scale up. This will allow you to better assess the expected performance on large graphs. You will probably need to approximate the values for large graphs in any case.