python-graphblas / graphblas-algorithms

Graph algorithms written in GraphBLAS
Apache License 2.0
73 stars 4 forks source link

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

Open eriknw opened 1 year ago

eriknw commented 1 year ago

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).

szhorvat commented 1 year ago

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