# Approximation Algorithm for Shortest Path in Large Social Networks
## 4 Parallelization  
In order to reduce the overall computational runtime for computing the shortest path from \(s\) to \(t\), we parallel to jobs to each processor on the computing hardware. Parallelization is simultaneously employing multiple compute resources by sharing tasks among these resources to solve a computational  
Figure 3: Illustration of approximate distance \(r_{i}\). problem. Two common approaches to run our algorithm are via either threads or multiple processes. Threads treat each job as sub tasks of a single process and therefore would have to access the same memory location. If synchronization is not done properly, there could be conflicts for example when there is access to the same memory location at the same time. A safer approach is to submit each task to a completely separate memory location. We distribute networks evenly on to multiple cores thus passing level \(i\) networks to a cpu core for computation. [PERSON]'s algorithm can only compute the shortest path from s to t after it has completed computation of shortest path \(d(s,w)\) where w is any vertex that satisfies \(\big{\|}d(s,w)\big{\|}~{}<\big{\|}d(s,t)\). It is evident that this process will increase the idleness on processors that leads to a reduction in resource utilization and efficiency [13] where efficiency \(p\) was about \(\sqrt{p}\). Figure 4 shows the architecture of the various stages of our proposed algorithm. The given network is the input data to the hierarchical graph construction process at the pre-processing stage. The graph in partitioned into k number of hierarchies and distributed across the processor cores of the computing machine. Algorithm 2 describes the subsequent construction hierarchies. Algorithm 1 is repeatedly executed until the top-level network is achieved which is essentially equal to the partitioning value (\(p\)) nodes given a threshold (\(t\)). The time complexity for constructing hierarchical networks is given as \(O\big{(}\sum_{i=0}^{k-1}(n_{i}\log n_{i}+n_{i}+e_{i})\big{)}\) and space complexity as \(O(kn+e)\). In the top level network, [PERSON]'s algorithm require \(O\big{(}m^{2}\big{)}\) time to compute the shortest paths between each pair of nodes and \(O\big{(}m^{2}\big{)}\) space to store the distances, where \(m\) is the number of nodes in the top level network. Incorporating time and space complexity into [PERSON]'s algorithm requires \(O\big{(}kn+e+m^{2}\big{)}\) space to store hierarchical networks and corresponding distances in the top level network. Figure 4: Architecture of the algorithm for computing shortest path. ```
1:Network = original
2:k = Network/number_of_processors
3:function HierarchyCluster
4:Network _current = original_;
5:while current.size > threshold
6:If len(current) <= k
7:\(next\) = SingleCluster(current);//Algorithm 1 else
8:\(current\) = next;
9:endif
10:endwhile//hierarchy networks
11:Employ [PERSON]'s algorithm to find shortest path between any pair of nodes on the top level network. Save the results to \(d[i][j]\). 12:return\(d[i][j]\)
13:endfunction
```  
**Algorithm 2**Hierarchy Networks  
After the construction of a number of networks from Algorithm 2, Algorithm 3 distributes the networks across each processor core of the computing hardware for computation. ```
1:level \(i\) networks computed by Algorithm 2. 2:Function Create Pool_Object(\(p\)) = processes
3:part_generator = 4*len(\(p\_pool\))
4:max_number_of_clusteres = int(len(original)/part_generator/lotal number of hierachies
5:\(k\) = len(max_number_of_clusters)
6:return\(k\)
7:Distribute hierarchy networks evenly to each processor
8:Parallel_mapping = p.map (btwn_pool, zip([original] *number of clusters, hierarchies))
9:Return parallel_mapping
```  
**Algorithm 3**Parallelization of Hierarchies  
Finally, the approximate distances of the shortest paths in the original network can be calculated by Algorithm 4. Algorithm 4 requires at most \(O\left(kn^{2}\right)/p\) time to compute the shortest paths for all pairs of nodes, where \(p\) is the number of processor cores.