# Faster Algorithms for Mining Shortest-Path Distances from Massive Time-Evolving Graphs
## 1 Introduction
Indeed, it is known that finding a minimum size set of hubs is NP-hard [18; 28] but both heuristics and approximation algorithms, for computing fairly compact labelings, providing excellent practical performance in terms of query times at the price of a reasonable preprocessing effort, are known [3; 7; 18]. Specifically, the two approaches of [3; 7] currently are considered the best options in this direction. A further level of complexity arises when the network to be handled is _time-evolving_, i.e., is when the underlying graph can evolve over time. In fact, in this which is universally considered the most realistic scenario, every time the network is subject to an update, i.e., when the corresponding graph undergoes some topological change (e.g., an arc removal or an arc weight decrease), the preprocessed data can become obsolete and hence must be updated to preserve query correctness (i.e., that exact distances are returned). A naive way to produce updated preprocessed data is to recompute everything from scratch. Nonetheless, this is not a practical strategy when inputs are massive, as it requires unsustainable computational overheads [8; 27; 29]. Observe that this issue is common to many preprocessing-based approaches for mining properties from big graphs (e.g., mining betweenness centralities [30]). For these reasons, in the last few years, researchers have worked to adapt known methods, for mining (generic) properties from static graphs, to function in such time-evolving scenarios through the design of specific _dynamic algorithms_, i.e., algorithms that are able to update the preprocessed data to reflect graph changes without performing any full recomputation from scratch [8; 14; 17; 24; 25; 26; 27; 30; 31]. Such algorithms are typically divided in two broad categories, namely _incremental_ and _decremental algorithms_, depending on whether they able to handle _incremental updates_ only (i.e., insertion of vertices/arcs and arc weight decreases) or _decremental updates_ only (deletion of vertices/arcs and arc weight increases). Both types of algorithms find several prominent applications in the real-world, as well documented in the literature [8; 17; 26]. On the one hand, incremental algorithms are essential to handle scenarios where the graph to be managed tends to be subject to sequences of changes that correspond to a growth of the size of the underlying network. Examples include _citation networks_, where new references or new authors can be added dynamically, or _email/messaging networks_, where one can observe only new emails being sent and new addresses being added. On the other hand, decremental algorithms are useful in all those cases where the graph to be managed tends to be subject to sequences of changes that correspond to a reduction of the size/functionality of the underlying network. Examples include: _communication networks_ where links can become unavailable, and arc weights representing latencies typically can deviate by increasing from the initial value; _railway/bus networks_ where delays due to disruptions can occur, while no train is allowed to leave before the scheduled time; _data mining for linked data_ (web link analysis, social network analysis, biological networks analysis, databases processing) where one's purpose is to determine which nodes/links are the most important by observing the effect of removals/congestions on the structure of the shortest paths (and/or diameter or components) of the corresponding graphs. Finally, it is well known that both kinds of solutions are necessary to build effective fully dynamic algorithms that are of fundamental importance for all those applications where the structure of the sequences of modifications, affecting the graph, is unpredictable [26; 32; 33]. A typical example is _social network analysis_ where users can join or leave, and connections between users can be established or removed.