SAP SE
RESOURCE-EFFICIENT CLOSENESS CENTRALITY COMPUTATION IN TIME-EVOLVING GRAPHS

Abstract:

Methods, systems, and computer-readable storage media for receiving data representative of time-based snapshots of a time-evolving graph, the data including vertices and edges for each time-based snapshot, for each source vertex in a time-based snapshot: executing a static single-source-shortest-path (SSSP) algorithm to provide a set of distance labels, each distance label including data representative of a distance between the source vertex and a reachable vertex within the time-based snapshot, and determining a total number of reachable vertices from the source vertex within the time-based snapshot and a total distance between the source vertex and the reachable vertices based on the set of distance labels within the time-based snapshot, and providing, for each source vertex, a set of closeness centrality values, each closeness centrality value corresponding to a respective time-based snapshot.