  Finding the shortest path distance between an arbitrary pair of vertices is a
fundamental problem in graph theory. A tremendous amount of research has been
successfully attempted on this problem, most of which is limited to static
graphs. Due to the dynamic nature of real-world networks, there is a pressing
need to address this problem for dynamic networks undergoing changes. In this
paper, we propose an \emph{online incremental} method to efficiently answer
distance queries over very large dynamic graphs. Our proposed method
incorporates incremental update operations, i.e. edge and vertex additions,
into a highly scalable framework of answering distance queries. We
theoretically prove the correctness of our method and the preservation of
labelling minimality. We have also conducted extensive experiments on 12 large
real-world networks to empirically verify the efficiency, scalability, and
robustness of our method.
