# Approximation Algorithm for Shortest Path in Large Social Networks
## 3 Algorithm Based on the Hierarchy of Networks  
After transforming the original network into a number of hierarchical networks, the distance of the shortest path between any two nodes in the lower network can be estimated by considering their corresponding central nodes in the higher-level network. Let \(\hat{d}_{i}(s,t)\) be the approximate distance between nodes \(s\) and \(t\) in the level \(i\) network. The distance of shortest path between nodes \(s\) and \(t\) in the original network is approximated by \(\hat{d}_{0}(s,t)\). In general, \(\hat{d}_{i}(s,t)\) is iteratively computed by  
\[\hat{d}_{i}(s,t)=\left\{ \begin{array}{ll}\hat{d}_{i}(s,c_{s})+\hat{d}_{i}(t,c_{t})&c_{s}=c_{t}\\ \hat{d}_{i}(s,c_{s})+\hat{d}_{i+1}(c_{s},c_{t})+\hat{d}_{i}(c_{t},t)&c_{s}\
eq c _{t}\end{array} \right.,i\geq 0, \tag{1}\]  
where \(c_{s}\) and \(c_{t}\) are the central nodes of nodes \(s\) and \(t\) respectively. Figure 2 shows an example of shortest path approximation using Equation (1). \(\hat{d}_{i}(s,c_{s})\) a nd \(\hat{d}_{i}(t,c_{t})\) are the approximate distances from nodes \(s_{i}\) and \(t_{i}\) to their respective central nodes \(c_{s_{i}}\) and \(c_{t_{i}}\) in the level \(i\) network. \(\hat{d}_{i+1}(s,c_{s})\) and \(\hat{d}_{i+1}(c,t_{s})\) are the distances from nodes \(s_{i+1}\) and \(t_{i+1}\) to their common central nodes in the level \(i+1\) network. Figure 1: Construction of hierarchical networks. (**a**) graph at level \(i\), (**b**) level \(i+1\) network. We define the longest distance from sub nodes to its corresponding central node as the radius \(r\) of the super node. For example, assuming normal nodes in the level \(i\) network in Figure 2 have the same radius \(r\), then the radiuses of their corresponding super nodes will range from \(r\) to \(3r+1\) (Note: the longest path to a central node is \(3r\)). However, computing for all radii of super nodes in the network hierarchy will consume so much memory and time. For this reason, we define an _appr radius_\(r_{i}\) for all super nodes in the level \(i\) network by approximating the distance between two adjacent normal nodes in the level \(i\) network. As shown in Figure 3, the _appr radiuses_ of super nodes in the level \(i+1\) network are the approximate distances between the centers of two adjacent normal nodes (represented as hollow circles). Normal nodes in the level \(i+1\) network were derived from super nodes in the level \(i\) network whose _appr radiuses_ were same. The _appr radius_ of normal nodes in level \(i\) network is defined by  
\[r_{i}=\left\{ \begin{array}{cc}0,&i=0\\ 2r_{i-1}&0<i<k\end{array} \right., \tag{2}\]  
where \(k\) is the number of hierarchical networks with different scales including the original network. Furthermore, Equation (2) can be written as \(r_{i}=2^{i}-1\) when \(0\leq i<k\). We approximate the distance from node \(s\) to its central node \(c\) in the level \(i\) network by  
\[\hat{d}_{i}(s,c)=2r_{i}+1 \tag{3}\]  
The approximate distance between adjacent nodes in level \(i\) network can also be written as \(2r_{i}+1\). Substituting Equations (2) and (3) into Equation (1), the upper bound of \(\hat{d}_{i}(s,t)\) can be calculated by  
\[\hat{d}_{i}(s,t)=\left\{ \begin{array}{ll}2&i=0,c_{s}=c_{t}\\ 2^{i+2}-2&0<i<k-1,c_{s}=c_{t}\\ 2^{i+2}-2+\hat{d}_{i+1}(c_{s},c_{t})&0<i<k-1,c_{s}\
eq c_{t}\\ d_{k-1}(s,t)&i=k-1\end{array} \right. \tag{4}\]  
The distance between any two adjacent nodes in the top-level network is approximated as \(2r_{k-1}+1\). \(d_{k-1}(s,t)\) in Equation (4) is the length of shortest path between nodes s and t in the top-level network computed by [PERSON]'s algorithm. Figure 2: Illustration of iterative approximation. The construction of each level of the hierarchical network is described in Algorithm 1. Algorithm 1 consumes \(O(n_{i}logn_{i})\) time to rank the \(n_{i}\) nodes in the level \(i\) network and \(O(n_{i}+e_{i})\) time to generate the level \(i+1\) network, where \(e_{i}\) is the number of edges in level \(i\) network. The space complexity of Algorithm 1 is \(O(n+e)\).