pathpyG icon indicating copy to clipboard operation
pathpyG copied to clipboard

New implementation of lift order temporal, temporal shortest paths and temporal closeness centrality

Open IngoScholtes opened this issue 2 months ago • 0 comments

This pull request contains the new memory-efficient implementation of the lift_order_temporal function that creates a temporal event DAG from a temporal graph with given delta.

I also added the new function to calculate temporal shortest paths based on the augmented temporal event DAG, as well as a function that computes temporal closeness centralitiues based on this new implementation.

I temporarily commented out functions to calculate (longest) time-respecting paths and temporal betweenness centeality.

This new implementation allows to calculate temporal closeness centralities of all nodes in the Sociopatterns Highschool data with delta = 3600 in less than 8 minutes.

TODO:

  • make creation of temporal event DAG Graph object more efficient (it currently eats up the majority of the time needed to calculate all pairs shortest paths) or skip the graph creation alltogether
  • add function to calculate all shortest paths between all pairs of nodes, not only a single shortest path
  • bring back function to calculate temporal betweenness centrality based on temporal event DAG

IngoScholtes avatar Apr 29 '24 20:04 IngoScholtes