# Approximation Algorithm for Shortest Path in Large Social Networks
## 6 Experimental Results and Discussions  
Our algorithm was implemented by java programming language, running on a PC with intel core i5 4300M, CPU at 2.60 GHZ dual core and a 4 GB RAM. Performance of the algorithm was evaluated on four real undirected and weighted networks; Email-Enron [14], itdk0304_rlinks [15], DBLP [16] and roadNet. Email-Enron contains about half a million email communications among users whose nodes are the email addresses of senders or receivers and edges are the communication relationships. User's email addresses represents nodes on the dataset such that if a user \(i\) sent at least one email to another user \(j\), then there exists an undirected edge from \(i\) to \(j\). Tdk0304_rlinks is a CAIDA Skitter Router-Level Topology and Degree Distribution of an undirected internet router-level, which contains the relationships among nodes that access the router where the nodes are users or websites and the edges are the relationships between them. DBLP network contains information on computer science publications, in which each node corresponds to an author; two authors are connected by an edge if they have co-authored at least one publication. The roadNet is a California road traffic network composed of roads and sites network with the intersections and endpoints as nodes and the connecting roads as edges. Since most roads are unidirectional, the network graph is represented as an undirected graph. The number of nodes \(V\), edges \(E\), diameter of network \(D\), average degree \(<\)\(k\)\(>\), and the largest degree \(k_{max}\) of these four networks are shown in Table 1.  
We use _Path Ratio_\(p\) to assess the accuracy of the algorithm. \(p\) is defined as  
\[p=\ \frac{\sum_{i=1}^{pr}P_{f_{i}}}{\sum_{i=1}^{pr}P_{O_{i}}} \tag{5}\]  
where \(Pr\) is the total number of pairs of nodes, \(P_{f_{i}i}\) is the distance between pairs of nodes computed by the approximation algorithm, and \(P_{O_{i}}\) is the accurate distances computed by [PERSON]'s algorithm. The value of \(p\) is always greater than 1 since approximate distances are always longer than their corresponding accurate distances. Table 2 shows experimental results on preprocess time, average query time, and path ratio from our algorithm compared with that of CDZ. The threshold value is set at 100. \(T_{init}\) is the total time for preprocessing. \(T_{q}\) is the average runtime for 10,000 random queries. From table 2, it can be construed that our algorithm performed relatively better on four different networks. It ran 10 times faster than CDZ especially on DBLP and roadNet networks. Moreover, the approximation for the shortest path is more accurate on Email-Enron and itdk0304_rlinks, compared with CDZ on DBLP and roadNet. Table 3 shows results from LCA, LBFS, and our algorithm. It can be seen from Table 3 that our algorithm outperforms LBFS in terms of efficiency and accuracy. In DBLP and roadNet, our algorithm ran twice as fast as LBFS. Compared with LCA, our algorithm approximates more accurately but with a slightly higher runtime. Moreover, parallelization improved the runtime by about 15% compared with the latter which computed shortest paths sequentially. \begin{table}
\begin{tabular}{c c c c c} \hline \hline  & _Email-Enron_ & _itdk0304\_rlinks_ & _DBLP_ & _roadNet_ \\ \hline \(V\) & 36,692 & 190,914 & 511,163 & 1,405,790 \\ \hline \(E\) & 367,662 & 1,215,220 & 3,742,140 & 23,442,590 \\ \hline \(D\) & 12 & 24 & 25 & 30 \\ \hline \(<\)\(k\)\(>\) & 10.020 & 6.365 & 7.320 & 9.433 \\ \hline \(k_{max}\) & 1383 & 1071 & 976 & 1244 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Basic information of four networks.