graphblas-algorithms icon indicating copy to clipboard operation
graphblas-algorithms copied to clipboard

Add `igraph` backend to `scripts/bench.py`

Open eriknw opened this issue 2 years ago • 1 comments

We would like to be able to compare performance to igraph: https://github.com/igraph/python-igraph

Some algorithms may be different, which can make direct comparisons difficult to do well (for example, stopping criteria for e.g. PageRank could be different).

eriknw avatar Mar 10 '23 17:03 eriknw

for example, stopping criteria for e.g. PageRank could be different

Currently, igraph does not use power iteration at all for PageRank. Older versions did, but that code was removed, as it was slow, and did not support all features (such as personalization).

Mathematically, PageRank can be formulated either as a linear equation (assuming a damping factor less than 1), or as an eigenvector problem. At the moment, igraph has two methods: it can use the PRPACK library, which uses the linear equation picture, or it can use ARPACK to compute PageRank as an eigenvector.

See also https://igraph.discourse.group/t/implementing-the-ldbc-graphalytics-benchmark/417

szhorvat avatar Mar 10 '23 23:03 szhorvat