Efficient 2-Hop Labeling Maintenance in Dynamic Small-World Networks

Shortest path computation is a fundamental operation in small-world networks and index-based methods, especially 2-hop labeling, are commonly applied which have achieved high query efficiency. However, small-world networks keep evolving in real life, making it indispensable to study the maintenance of shortest path index. In this work, we adopt the state-of-the-art Parallel Shortest-distance Labeling (PSL) as the underlying 2-hop labeling construction method, and design algorithms to support efficient update of the index given edge weight change (increase and decrease) in the network. Specifically, we focus on weighted PSL (WPSL) and propose the update propagation mechanism for both synchronous propagation and asynchronous propagation. We then identify the curse of pruning power generated for the propagation under edge weight increase, and solve this problem with a balance between index size and effectiveness. Finally, we extend the proposed asynchronous propagation method to Pruned Landmark Labeling (PLL) for faster index maintenance and query processing with smaller index size. Our experimental results on real-life and synthetic networks demonstrate the superiority of our algorithms on index maintenance.