  The widespread use of graph data in various applications and the highly
dynamic nature of today's networks have made it imperative to analyze
structural trends in dynamic graphs on a continual basis. The shortest path is
a fundamental concept in graph analysis and recent research shows that counting
the number of shortest paths between two vertices is crucial in applications
like potential friend recommendation and betweenness analysis. However, current
studies that use hub labeling techniques for real-time shortest path counting
are limited by their reliance on a pre-computed index, which cannot tackle
frequent updates over dynamic graphs. To address this, we propose a novel
approach for maintaining the index in response to changes in the graph
structure and develop incremental (IncSPC) and decremental (DecSPC) update
algorithms for inserting and deleting vertices/edges, respectively. The main
idea of these two algorithms is that we only locate the affected vertices to
update the index. Our experiments demonstrate that our dynamic algorithms are
up to four orders of magnitude faster processing for incremental updates and up
to three orders of magnitude faster processing for hybrid updates than
reconstruction.
