search

uzhdag / pathpy

An OpenSource python package for the analysis of time series data on networks using higher-order and multi-order graphical models.
http://www.pathpy.net
GNU Affero General Public License v3.0
49 stars 17 forks source link

Performance of path calculation #17

Open IngoScholtes opened 6 years ago

IngoScholtes commented 6 years ago

From pathpy created by IngoScholtes : sg-dev/pathpy#9

The function HigherOrderNetwork.getShortestPaths is a bottleneck for the calculation of centralities.

I believe that we can make this more efficient, as it currently takes several minutes even for higher-order networks that only have a few hundred nodes and a few thousand links.

Moreover, for the calculation of betweenness centrality, we can adopt faster algorithms like the one by Brandes et al., see here: www.tandfonline.com/doi/abs/10.1080/0022250X.2001.9990249

IngoScholtes commented 6 years ago

Performance of distances, diameter, avg. path length has been largely improved in latest version by switching to shortest path implementation in scipy.sparse.csgraph.

Update for betweenness centralities and higher-order Networks still pending

PremWarde commented 4 years ago

I have a similar issue due to sheer size of the network. The multi order network output is resulting in what I expect. However, I was wondering if anyone knows how to speed up the processing itself as it takes 5 hours. Is multi-processing possible here?