To analyze social networks, where social interactions change over time, special graphs and methods are needed. In this paper, social networks are represented as temporally detailed (TD) networks; the aim is to compute centrality metrics on them, betweenness in particular. At the basis of those metrics, there is the need to compute the shortest path between a pair of nodes, a problem that presents computational challenges in such dynamic and very large networks.

The authors propose a new algorithm, called EBETS, based on the novel idea of reducing the number of re-computations by defining epoch points, the time points where the metric of the shortest path changes. Those points are computed using a lazy approach and a new data structure, the TD priority queue, in conjunction with a path function that represents the total cost of the path as a function of time.

EBETS is demonstrated to be correct and complete. Space and time complexities are studied for a heap-based implementation; the advantages of EBETS with respect to other methods are in reducing the re-computations more than the asymptotical complexity. Experimental evaluations on three datasets analyze the effect of different parameters; taking Djikstra’s algorithm as the baseline, EBETS consistently performs better.

The proposed method is promising, and, besides computing betweenness, it can easily adapt to compute other extensions.

The paper is not always easy to follow, as it makes many lateral considerations and comparisons with other approaches. Unfortunately, the authors do not provide much of the implementation details. However, the reader is guided through many examples to understand how the algorithm works.

For readers interested in the application side, the three real datasets do not add much to a paper that substantially presents an algorithm.