# Label-Setting Algorithm for Multi-Destination \(K\) Simple Shortest Paths Problem and Application
## 5 Illustrative Practical Application  
This section demonstrates the usefulness and efficacy of the proposed algorithm for a practical application arising in a network science context. The problem attempts to quantify the significance of edges in a network and rank them based on their structural importance using a measure called Edge Gravity ([PERSON] and [PERSON], 2018). The edge gravity or the structural importance of an edge is the number of paths in the network comprising it. This concept is crucial in understanding various social, biological, and transportation networks. For instance, in transportation networks, identifying edges with high edge gravity can reveal critical links that enhance accessibility. Similarly, edge gravity can help find influential individuals in social networks or measure the overall resilience of a network. Through quantifying and ranking connections, it becomes a valuable tool for studying and manipulating social and other types of networks. The calculation of the metric requires the enumeration of all paths in the network, which can be performed using KSSP_LL_Heap, as finding the KSSP to all destinations (repeated from all origins) will provide all the paths in the network if a sufficiently large value of \(k\) is used. In networks where enumerating all paths is not practically feasible, the authors proposed the metric k-Gravity, which is the edge gravity computed using only the  
Figure 5: The tradeoff between the computational time and solution quality of KSSP_LL_Heap. (a) Anaheim network. (b) Barcelona network. (c) Rome network. (d) Hessen network. (e) Austin network. top \(k\) shortest paths between all OD pairs. The k-Gravity serves as a lower bound of the actual edge gravity. For the path enumeration, [14] adapted a KSP algorithm by running it for each OD pair in the network for an adequately large value of \(k\). They emphasized that the choice of the KSP algorithm is crucial for efficiently calculating edge gravity. Since path enumeration is the dominant step in this calculation, improvements in its computation time are necessary to handle larger networks. They state, \"Choice of a specific k-shortest path algorithm for enumerating the paths appears to be a factor and presents an interesting set of extension studies. Examination and improvement in computation time for Edge Gravity is necessary to address larger static and single-layer networks, which necessarily prefaces complexity that includes time-evolving and multi-layer networks\". The current study shows that the path enumeration for the edge gravity computation can be performed more efficiently with the proposed KSSP_LL_Heap, enhancing the scalability of the metric to larger networks. The computational performance is illustrated in Table 4 using [PERSON]'s example networks used by the authors in their experiments and two other road networks of Sioux Falls and Eastern Massachusetts [49]. The result shows that KSSP_LL_Heap is much faster on the same networks used by the authors. A 14-20 times speedup is achieved on the [PERSON] '73 example B network. Moreover, the scalability provided by KSSP_LL_Heap is evident from the other networks. On the larger Eastern Massachusetts network, KSSP_LL_Heap calculates the edge gravity using more than 10 million paths in 21.53 s, which is about 182 times faster than algorithm Y. It is clear that the computational benefits provided by KSSP_LL_Heap over existing methods grow with the problem size. Given that the number of paths present in the Eastern Massachusetts network is huge, the k-Gravity metric was computed considering the practical feasibility. To understand whether the importance of an edge remains stable as more paths are enumerated and get an idea of the quality of the ranking obtained with \(k\) values sufficiently large in practice, sensitivity analysis was performed as described below. First, the sensitivity of the absolute k-Gravity value of an edge for different values of \(k\) was investigated.