# Label-Setting Algorithm for Multi-Destination \(K\) Simple Shortest Paths Problem and Application
## 5 Illustrative Practical Application
For this, the normalized k-Gravity value of an edge is defined as the ratio of its k-Gravity to the total number of paths found between all OD pairs. The variation in the normalized k-Gravity averaged over all the edges in the network is shown in Figure 6. From Figure 6, it is observed that the average normalized k-Gravity value starts to stabilize in the range of \(k\) = 10,000 to 20,000 as the rate of increase (slope) in the average normalized edge gravity drops sharply at \(k\) = 10,000 and starts converging to a constant value. \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline
**Network** & \(n\) & \(m\) & \(k\) & \begin{tabular}{c} **Total Paths** \\ **Found** \\ \end{tabular} & \begin{tabular}{c} **Maximum** \\ **Path Length** \\ \end{tabular} & \begin{tabular}{c} **CPU Time** \\ **Reported by** \\ **[PERSON] and** \\ **[PERSON] (s)** \\ \end{tabular} & \
\begin{tabular}{c} **CPU Time** \\ **for Y** \\ **(s)** \\ \end{tabular} &
\begin{tabular}{c} **CPU Time for** \\ **KSSP\_LL_Heap** \\ **(s)** \\ \end{tabular} \\ \hline Granovetter ’73 & 10 & 42 & 416 & 14,796 & 9 & \(3.17\times 10^{-2}\) & \(1.33\times 10^{-1}\) & \(2.39\times 10^{-2}\) \\ [PERSON] ’73 & 25 & 82 & 17,480 & 2,130,510 & 24 & 124.31 & 94.67 & 6.51 \\ Sioux Falls & 24 & 76 & 4787 & 1,717,464 & 23 & \(\times\) & 56.55 & 4.87 \\ Eastern & 74 & 258 & 5000 * & 5,316,354 & 18 & \(\times\) & 1417.08 & 10.15 \\ Eastern & 74 & 258 & 10,000 * & 10,633,368 & 20 & \(\times\) & 3912.52 & 21.53 \\ Massachusetts & & & & & & & \\ \hline \hline \end{tabular}  
* Paths enumerated for the k-Gravity computation. \(\times\) These networks were not used by [14].  
\end{table} 
Table 4: Computational performance for obtaining the edge gravity metric. Next, the sensitivity of the rank ordering of the edges based on their k-Gravity was analyzed by studying the differences in the rank order of edges obtained with a value of \(k\) against that obtained with \(k\) = 50,000. With \(k\) = 50,000, a large set of paths (approximately 27 million) is obtained, and the corresponding k-Gravity is assumed to provide the actual order of edge importances for the purpose of this analysis. The distribution of the absolute difference in the rank of an edge obtained with a given value of \(k\) against the actual order is shown in Figure 7. It is observed that the range of the rank differences continuously reduces from 82 at \(k\) = 1000 to 7 at \(k\) = 40,000, indicating that the distribution of the rank differences (i.e., the error in ordering) tends to converge towards zero (mean and variance of differences shrink) with increasing \(k\). The plot also corroborates that a \(k\) value between 10,000 and 20,000 seems to provide a sufficiently good choice for the lower bound of edge gravity since the average absolute rank difference is around 10 for \(k\) = 20,000 (0.05% error), which is practically acceptable. Further, the rank correlation between the edge ranks obtained for \(k\) = 10,000 was compared against the upper bound of \(k\) = 50,000. Since the relationship between two sets of ranked (ordinal) data is analyzed, appropriate statistical measures of [PERSON]'s rank correlation coefficient [52] and [PERSON]'s \(\tau\)[53] are used. [PERSON]'s rank correlation coefficient turned out to be close to 1 (0.98), and [PERSON]'s \(\tau\) was 0.9, and both were statistically significant (\(p\) < 1 \(\times\) 10\({}^{-100}\)), suggesting the adequacy of using 10,000 paths per OD to estimate edge gravity. This procedure can be adopted for other networks to determine convergence and find the smallest \(k\) needed to estimate edge gravity. However, the thresholds for convergence may depend on network topology and connectivity. Figure 6: Sensitivity of k-Gravity to k on the Eastern Massachusetts network. Figure 7: Distribution of the difference in edge ranking for different values of k compared against \(k\) = 50,000.