# Shortest Paths Based Web Service Selection in Internet of Things

Authors: Xiangdong Yin; Jie Yang
Journal: Journal of Sensors
 (2014)

---

## Abstract

The connecting of things to the Internet makes it possible for smart things to access all kinds of Web services. However, smart things are energy-limited, and suitable selection of Web services will consume less resources. In this paper, we study the problem of selecting some Web service from the candidate set. We formulate this selection of Web services for smart things as single-source many-target shortest path problem. We design algorithms based on the Dijkstra and breadth-first search algorithms, propose an efficient pruning algorithm for breadth-first search, and analyze their performance of number of iterations andI/O cost. Our empirical evaluation on real-life graphs shows that our pruning algorithm is more efficient than the breadth-first search algorithm.


---

## Body

## 1. Introduction

Recently, development of RFID, sensor, and networking technologies make it possible for various physical world things connecting to the internet, and people usually call it Internet of Things (IoT). In IoT, more and more devices are getting connected to the Internet, and the next step is to use the World Wide Web and its associated technologies, such as Web services, as a platform for smart things.In Internet, there are a lot of Web services. These Web services connect with each other and construct a topology of graph. In IoT, all smart things are connecting to the Internet, so they can access all kinds of Web services. However, smart things are usually energy-limited, so the selection of suitable Web service is extremely important. Guinard et al. [1] give an overall view of Web service access in Internet of Things. They propose a process and a suitable system architecture that enables developers and business process designers to dynamically query, select, and use running instances of real-world services.In this paper, we study the problem of Web services selection in IoT setting; that is, given a smart thing and a graph of Web services, how to select several suitable Web services from the candidate set while providing satisfactory quality of service. If the selected Web services are nearest, the smart thing would take less accessing and waiting time and then consume less power. Here, we formulate the selection of Web services as single-source many-target shortest path problem.The shortest path problem can be classified as SSSTSP (single-source single-target shortest path), SSMTSP (single-source many-target shortest paths), APSP (all-pairs shortest paths), andkSP (k shortest paths). The MSSTSP (many-sources single-target shortest paths) is the same as SSMTSP if we reverse all edges in the graph.


### 1.1. Our Contribution

In this paper, we study the problem of SSMTkSP (single-source many-target k shortest paths) on MapReduce, which is finding k shortest paths from a candidate set for one source node on MapReduce. In our work, we do not care about the exact k paths, but rather the k nearest neighbors of the source node, so the SSMTkSP problem can also be considered as single-source many-target k nearest neighbors problem. The SSMTkSP can be used in recommending friends or ads in social networks, and in searching malls or hotels in road networks.We design algorithms based on the Dijkstra and breadth-first search algorithms, propose an efficient pruning algorithm for breadth-first search, and analyze their performance of number of iterations andI/O cost. Our empirical evaluation on real-life graphs and Hadoop platform shows that the pruning algorithm is more efficient than the breadth-first search shortest path algorithm.The rest of the paper is organized as follows. Section2 gives the background for shortest path for graphs, MapReduce, Dijkstra algorithm, and breadth-first search. The SSMTkSP problem and its corresponding algorithms are presented in Section 3. We analyze the performance of our algorithms in Section 4, show experimental results in Section 5, and review the related work in Section 6. Finally, conclusion and future work is given in Section 7.


## 1.1. Our Contribution

In this paper, we study the problem of SSMTkSP (single-source many-target k shortest paths) on MapReduce, which is finding k shortest paths from a candidate set for one source node on MapReduce. In our work, we do not care about the exact k paths, but rather the k nearest neighbors of the source node, so the SSMTkSP problem can also be considered as single-source many-target k nearest neighbors problem. The SSMTkSP can be used in recommending friends or ads in social networks, and in searching malls or hotels in road networks.We design algorithms based on the Dijkstra and breadth-first search algorithms, propose an efficient pruning algorithm for breadth-first search, and analyze their performance of number of iterations andI/O cost. Our empirical evaluation on real-life graphs and Hadoop platform shows that the pruning algorithm is more efficient than the breadth-first search shortest path algorithm.The rest of the paper is organized as follows. Section2 gives the background for shortest path for graphs, MapReduce, Dijkstra algorithm, and breadth-first search. The SSMTkSP problem and its corresponding algorithms are presented in Section 3. We analyze the performance of our algorithms in Section 4, show experimental results in Section 5, and review the related work in Section 6. Finally, conclusion and future work is given in Section 7.


## 2. Background

In this section, we provide some background for shortest path for graphs, MapReduce, Dijkstra algorithm, and breadth-first search.


### 2.1. Shortest Path for Graphs

We consider a Weighted Directed GraphG=(V,E), where V is the set of nodes, E is the set of edges, and the number of nodes and edges is |V| and |E|, respectively. We use D to represent the diameter of G. For an edge (u,v)∈E, the weight is denoted with wu,v, and u is v’s parent node and v is u’s child node. A path P in a graph G is a sequence of nodes 〈v1,v2,…,vj〉, where vi∈V(1≤i≤j) and (vi,vi+1)∈E(1≤i<j). v1 and vj are calledstart andtarget of P and linked by P. The length of P betweensource andtarget is the sum of weights of edges in it; that is, len(P)=∑i=1j-1‍wi,i+1, and the number of hops fromsource totarget in P is the number of edges, that is, h(p)=j-1.Definition 1.
A pathP in graph G from start s to target t(s,t∈V) is a shortest path, if there does not exist any path P′ between s and t, such that len(P′)<len(P).
For the sake of simplifying the presentation, we assume for the rest of the paper that the weight on each edge ofG equals 1; that is, len(P)=h(P). This degrades G to an unweighted graph but does not affect the result of our algorithms.


### 2.2.  MapReduce

MapReduce [2], proposed by Google, is a programming model for processing huge amounts of data in parallel using a large number of commodity machines, and its open-source implementation is Hadoop (http://hadoop.apache.org/docs/current/hadoop-project-dist/hadoop-hdfs/Federation.html). By automatically handling the lower level issues, such as job distribution, data storage, and fault tolerance, it allows programmers without any experience with parallel and distributed systems to easily utilize the resources of a large distributed system.In the MapReduce-like systems, programs are done iteratively in three phases:Map,Shuffle, andReduce. In theMap phase, they read a collection of values or key/value pairs from input sources in parallel and emit zero or more key/value pairs for each input element by invoking a user definedMapper function. In theShuffle phase, they group together all the Mapper-emitted key/value pairs sharing the same key and output all groups to the next phase. In theReduce phase, they invoke a user definedReducer function for each distinct group independently and in parallel and emit zero or more key/value pairs that will be written on disks or be the input of the nextMap phase in the following iteration. In our work, we will use two basic primitives:Map andReduce.


### 2.3. Dijkstra Algorithm

Dijkstra algorithm [3] is a classical algorithm for single-source shortest path problem for graphs with positive weights. It computes the shortest paths between the source s and any other node in a graph. The main idea is that starting from s, expand one node that has the shortest path to s; repeat the expanding process until all nodes are reached from s. In each expanding process, the algorithm expands a nearest neighbor, and it requires that the weight of each edge is positive.Example 2.
Given the graphG in Figure 1, if we choose v0 as the source, the distances between v0 and other nodes will be {[v1,1],[v2,1],[v3,2],[v4,2],[v6,2],[v5,3]}, which can be done in 6 expanding processes.Figure 1
GraphG as our Running Example.


### 2.4. Breadth-First Search

To find the shortest paths between the sources and other nodes in graph G, we can conduct a breadth-first search (BFS for short) starting from s and obtain a BFS-tree Ts [4]. In order to construct BFS-tree of G, we first initialize Ts as a tree having only the root node s and then add children of s in G to Ts. That is, if (s,x)∈G, we add x to Ts as a child of s. Then iteratively, for each leaf node x in current Ts, we search all its children y, such that (x,y)∈E and y has not been added to Ts yet and add y to Ts as a child of x.Example 3.
Also considering the graphG in Figure 1, the BFS-tree of G can be seen in Figure 2. If we choose v0 as the source, the distances between v0 and other nodes are also {[v1,1],[v2,1],[v3,2],[v4,2],[v6,2], and [v5,3]}, but the BFS can finish in only 3 expanding processes.BFS-tree of GraphG.
(a)
T
v
0
(b)
T
v
1
(c)
T
v
2
(d)
T
v
3
(e)
T
v
4
(f)
T
v
5
(g)
T
v
6


## 2.1. Shortest Path for Graphs

We consider a Weighted Directed GraphG=(V,E), where V is the set of nodes, E is the set of edges, and the number of nodes and edges is |V| and |E|, respectively. We use D to represent the diameter of G. For an edge (u,v)∈E, the weight is denoted with wu,v, and u is v’s parent node and v is u’s child node. A path P in a graph G is a sequence of nodes 〈v1,v2,…,vj〉, where vi∈V(1≤i≤j) and (vi,vi+1)∈E(1≤i<j). v1 and vj are calledstart andtarget of P and linked by P. The length of P betweensource andtarget is the sum of weights of edges in it; that is, len(P)=∑i=1j-1‍wi,i+1, and the number of hops fromsource totarget in P is the number of edges, that is, h(p)=j-1.Definition 1.
A pathP in graph G from start s to target t(s,t∈V) is a shortest path, if there does not exist any path P′ between s and t, such that len(P′)<len(P).
For the sake of simplifying the presentation, we assume for the rest of the paper that the weight on each edge ofG equals 1; that is, len(P)=h(P). This degrades G to an unweighted graph but does not affect the result of our algorithms.


## 2.2.  MapReduce

MapReduce [2], proposed by Google, is a programming model for processing huge amounts of data in parallel using a large number of commodity machines, and its open-source implementation is Hadoop (http://hadoop.apache.org/docs/current/hadoop-project-dist/hadoop-hdfs/Federation.html). By automatically handling the lower level issues, such as job distribution, data storage, and fault tolerance, it allows programmers without any experience with parallel and distributed systems to easily utilize the resources of a large distributed system.In the MapReduce-like systems, programs are done iteratively in three phases:Map,Shuffle, andReduce. In theMap phase, they read a collection of values or key/value pairs from input sources in parallel and emit zero or more key/value pairs for each input element by invoking a user definedMapper function. In theShuffle phase, they group together all the Mapper-emitted key/value pairs sharing the same key and output all groups to the next phase. In theReduce phase, they invoke a user definedReducer function for each distinct group independently and in parallel and emit zero or more key/value pairs that will be written on disks or be the input of the nextMap phase in the following iteration. In our work, we will use two basic primitives:Map andReduce.


## 2.3. Dijkstra Algorithm

Dijkstra algorithm [3] is a classical algorithm for single-source shortest path problem for graphs with positive weights. It computes the shortest paths between the source s and any other node in a graph. The main idea is that starting from s, expand one node that has the shortest path to s; repeat the expanding process until all nodes are reached from s. In each expanding process, the algorithm expands a nearest neighbor, and it requires that the weight of each edge is positive.Example 2.
Given the graphG in Figure 1, if we choose v0 as the source, the distances between v0 and other nodes will be {[v1,1],[v2,1],[v3,2],[v4,2],[v6,2],[v5,3]}, which can be done in 6 expanding processes.Figure 1
GraphG as our Running Example.


## 2.4. Breadth-First Search

To find the shortest paths between the sources and other nodes in graph G, we can conduct a breadth-first search (BFS for short) starting from s and obtain a BFS-tree Ts [4]. In order to construct BFS-tree of G, we first initialize Ts as a tree having only the root node s and then add children of s in G to Ts. That is, if (s,x)∈G, we add x to Ts as a child of s. Then iteratively, for each leaf node x in current Ts, we search all its children y, such that (x,y)∈E and y has not been added to Ts yet and add y to Ts as a child of x.Example 3.
Also considering the graphG in Figure 1, the BFS-tree of G can be seen in Figure 2. If we choose v0 as the source, the distances between v0 and other nodes are also {[v1,1],[v2,1],[v3,2],[v4,2],[v6,2], and [v5,3]}, but the BFS can finish in only 3 expanding processes.BFS-tree of GraphG.
(a)
T
v
0
(b)
T
v
1
(c)
T
v
2
(d)
T
v
3
(e)
T
v
4
(f)
T
v
5
(g)
T
v
6


## 3. SSMTkSP

### 3.1. Problem Statement

Definition 4.
Given a (weighted) directed graphG=(V,E) and a candidate node set C which is chosen from V, the SSMTkSP problem is that, for a source node u∈V, find k nearest neighbors with shortest paths, such that those nearest neighbors are in C.In our work, we do not care about thek exact paths, but rather the k target nodes, or called nearest neighbors, so the SSMTkSP problem can also be considered as single-source many-target k nearest neighbors problem. The candidate set C could be chosen from V according to nodes’ importance on the graph, such as PageRank scores [5].


### 3.2.  DijkstraKNN Algorithm on MapReduce

On MapReduce, we keep a root setR for source s. At the beginning, R contains only (s, 0), and at each iteration, we add a nearest neighbor u and the shortest distance between s and u to R. As long as R contains k nodes coming from C, or there is no out-link from R, the expanding process terminates. Then we can get the k nearest neighbors through anotherMap phase. Details of the DijkstraKNN algorithm can be seen in Algorithms 1 and 2.Algorithm 1:DijkstraKNN(G,C,k,s).
Input: A (weighted) graph G=(V,E), candidate set C, k nearest neighbors, and source node s;
Output: A list l of (node,distance) from s, where |l|≤k;
(1)let R={(s,0)};
(2)let R.NODE={r.node∣r∈R};
(3)/*******************************************
(4)Here we redefine “∩” as follows:
(5)R∩C={(vi,di)∣(vi,di)∈R and vi∈C}
(6)*******************************************/
(7)while |R∩C|<k∧∃(u,v)(u∈R.NODE∧v∈(V(G)-R.NODE)∧(u,v)∈E(G))  do
(8) DijkstraMapper(R,G);
(9) //find a nearest neighbour
(10)R=R  ∪ DijkstraReducer();
(11)end while
(12)l=C∩R;
(13)return  lAlgorithm 2:Expanding a nearest neighbor.
DijkstraMapper  (R,G):
(1)for all  (from,to) in G  do
(2) if  from∈R.NODE∧to∉R.NODE  then
(3)  emit(from,to);
(4) end if
(5)end for;
DijkstraReducer  (output of DijkstraMapper):
(6)let result(key,value)=(0,+∞);
(7)for all  (key,value)  do
(8) //find a nearest neighbour not in R;
(9) if  key∉R.NODE∧value<result.value  then
(10)result=(key,value);
(11)end if
(12)end for;
(13)return  result


### 3.3. BFSKNN and PruningBFSKNN Algorithms on MapReduce

The DijkstraKNN algorithm expands one nearest neighbor in each iteration for the sources. However, we can expand all its neighbors of the same hops at the same time, that is, BFSKNN algorithm. In BFSKNN algorithm, iteratively we expand all neighbors of the same hops from s and update the shortest distances between s and these nodes. While all distances do not change any more, we obtain the shortest distances between s and other nodes in a graph. Details of the BFSKNN algorithm can be seen in Algorithm 3.Algorithm 3:BFSKNN(G,C,k,s).
Input: A (weighted) graph G=(V,E), candidate set C, k nearest neighbors, and source node s;
Output:A list l of (node,distance) from s, where |l|≤k;
(1)let R=null;
(2)let R′={(vi,di)∣vi==s?0:+∞,0≤i≤|G|};
(3)while  R′≠R  do
(4) R=R′;
(5) BFSMapper(R,G);
(6) R′ = BFSReducer();
(7)end while;
(8)//“∩” means the same as Algorithm 1
(9)l=C∩R;
(10)return  lDifferent from the Dijkstra algorithm, which expands the nearest neighbor in each iteration, the BFSKNN algorithm expands all nodes that have the same hops froms (see Algorithm 4 for details). The conditions that terminate them are also different. In the Dijkstra algorithm, if we have found k nearest neighbors or R has not any out-link, the algorithm terminates. However, in the BFSKNN algorithm, the termination condition is that all distances between s and other nodes in G do not change.Algorithm 4:Expanding neighbors with the same hops in BFSKNN.
BFSMapper (R,G):
(1)for all  (node,distance) in R  do
(2) emit(node,distance);
(3)end for;
(4)for all  (from,to) in G  do
(5) emit(to,from.distance+wfrom,to);
(6)end for;
BFSReducer  (output of BFSMapper):
(7)for all  key  do
(8) let result(key,value)=(0,+∞);
(9) for all  value  do
(10)if  value<result.value  then
(11)result=(key,value);
(12)end if
(13)end for;
(14)  emit(result);
(15)end forTheorem 5.
The BFSKNN Algorithm terminates in a limited number of iterations, and the output is a valid solution to the SSMTkSP problem.Proof.
Given the graphG, construct a BFS-tree T rooted at source s in the following steps: (1)
lets be the root of T;(2)
find all out-links for each leaf node ofT in G and add them to T as children of that leaf node;(3)
repeat Step  2 until that the path from root to leaf node forms a loop inG.
So, we have that there is a simple path froms to v in G if and only if there is a path from root to leaf node v in T. The above steps finish in a limited number i (i≤|V|) of iterations, so the BFSKNN algorithm terminates in a limited number of iterations. After i iterations, we can find all the shortest paths between s and other nodes in G, so since the (i+1)-th iteration, all the shortest paths between s and other nodes will not change any more, and the k nearest neighbors from C construct a valid solution to the SSMTkSP problem.However, in each expanding process of BFSKNN, all nodes expand along with their out-links, and this causes the problem of path expansion because all edges have to be accessed. In order to prune edges that are not necessarily accessed, we keep a listcList for each node, which records nodes from the candidate set for the current path. IncList, if a path contains k nodes from C, then we prune paths derived from that path, because they do not contain any useful information about k nearest neighbors. Details can be seen in in Algorithms 5 and 6.Algorithm 5:PruningBFSKNN(G,C,k,s).
Input: A (weighted) graph G=(V,E), candidate set C, k nearest neighbors, and source node s;
Output: A list l of (node,distance) from s, where |l|≤k;
(1)let R=null;
(2)let R′={(vi,cListi,di)∣vi==s?0:+∞,cListi=0,0≤i≤|G|};
(3)while  R′≠R  do
(4) R=R′;
(5) PruningBFSMapper(R,G);
(6) R′ = PruningBFSReducer();
(7)end while;
(8)/*******************************************
(9)Here we redefine “∩” as follows:
(10)R∩C={(vi,di)∣(vi,cListi,di)∈R and vi∈C}
(11) *******************************************/
(12)l=C∩R;
(13)return  lAlgorithm 6:Expanding neighbors with the same hops in PruningBFSKNN.
PruningBFSKNNMapper (R,G):
(1)for all  (node,cList,distance) in R  do
(2) emit(node,cList,distance);
(3)end for;
(4)for all  (from,to) in G  do
(5) if  from.cList∩C≥k  then
(6)  return;
(7) else if  from∈C  then
(8)  cList=cList∪{from}
(9) end if;
(10)  emit(to,cList,from.distance+wfrom,to);
(11)end for;
PruningBFSKNNReducer (output of PruningBFSKNNMapper):
(12)for all  key  do
(13)  Letresult(key,cList,value)=(0,0,+∞);
(14)for all  value  do
(15)if  value<result.value  then
(16)result=(key,cList,value);
(17)else if  value==result.value∧|key.cList|>|result.cList|  then
(18)result=(key,cList,value);
(19)end if;
(20)end for;
(21)  emit(result);
(22)end forExample 6.
Given the graphG in Figure 1, candidate set C={v0,v2,v5,v6} and k=2, we can prune the BFStree of G in Figure 2, and the results are in Figure 3.Pruned BFS-tree of graphG, candidate set C={v0,v2,v5,v6} and k=2.
(a)
T
v
0
(b)
T
v
1
(c)
T
v
2
(d)
T
v
3
(e)
T
v
4
(f)
T
v
5
(g)
T
v
6Theorem 7.
The PruningBFSKNN algorithm terminates in a limited number of iterations, and the output is a valid solution to the SSMTkSP problem.Proof.
Constructing a BFS-treeT the same as Proof of Theorem 5, we have that there is a simple path from source s to target v in G if and only if there is a path from root s to leaf node v in T. Prune paths have k candidate nodes from C after the kth candidate node. There are two kinds of pruned nodes, normal nodes (not belonging to C) and candidate nodes. If a node is a candidate node, it cannot be one of the k nearest neighbors in the pruned paths, because we have found k nearest neighbors in those paths. Otherwise, if a node is a normal node, then whether it appears in pruned paths or not does not affect the termination of the algorithm and does not affect the correctness of the algorithm either. So we have that the PruningBFSKNN algorithm terminates in a limited number of time, and the output is a valid solution to the SSMTkSP problem.


## 3.1. Problem Statement

Definition 4.
Given a (weighted) directed graphG=(V,E) and a candidate node set C which is chosen from V, the SSMTkSP problem is that, for a source node u∈V, find k nearest neighbors with shortest paths, such that those nearest neighbors are in C.In our work, we do not care about thek exact paths, but rather the k target nodes, or called nearest neighbors, so the SSMTkSP problem can also be considered as single-source many-target k nearest neighbors problem. The candidate set C could be chosen from V according to nodes’ importance on the graph, such as PageRank scores [5].


## 3.2.  DijkstraKNN Algorithm on MapReduce

On MapReduce, we keep a root setR for source s. At the beginning, R contains only (s, 0), and at each iteration, we add a nearest neighbor u and the shortest distance between s and u to R. As long as R contains k nodes coming from C, or there is no out-link from R, the expanding process terminates. Then we can get the k nearest neighbors through anotherMap phase. Details of the DijkstraKNN algorithm can be seen in Algorithms 1 and 2.Algorithm 1:DijkstraKNN(G,C,k,s).
Input: A (weighted) graph G=(V,E), candidate set C, k nearest neighbors, and source node s;
Output: A list l of (node,distance) from s, where |l|≤k;
(1)let R={(s,0)};
(2)let R.NODE={r.node∣r∈R};
(3)/*******************************************
(4)Here we redefine “∩” as follows:
(5)R∩C={(vi,di)∣(vi,di)∈R and vi∈C}
(6)*******************************************/
(7)while |R∩C|<k∧∃(u,v)(u∈R.NODE∧v∈(V(G)-R.NODE)∧(u,v)∈E(G))  do
(8) DijkstraMapper(R,G);
(9) //find a nearest neighbour
(10)R=R  ∪ DijkstraReducer();
(11)end while
(12)l=C∩R;
(13)return  lAlgorithm 2:Expanding a nearest neighbor.
DijkstraMapper  (R,G):
(1)for all  (from,to) in G  do
(2) if  from∈R.NODE∧to∉R.NODE  then
(3)  emit(from,to);
(4) end if
(5)end for;
DijkstraReducer  (output of DijkstraMapper):
(6)let result(key,value)=(0,+∞);
(7)for all  (key,value)  do
(8) //find a nearest neighbour not in R;
(9) if  key∉R.NODE∧value<result.value  then
(10)result=(key,value);
(11)end if
(12)end for;
(13)return  result


## 3.3. BFSKNN and PruningBFSKNN Algorithms on MapReduce

The DijkstraKNN algorithm expands one nearest neighbor in each iteration for the sources. However, we can expand all its neighbors of the same hops at the same time, that is, BFSKNN algorithm. In BFSKNN algorithm, iteratively we expand all neighbors of the same hops from s and update the shortest distances between s and these nodes. While all distances do not change any more, we obtain the shortest distances between s and other nodes in a graph. Details of the BFSKNN algorithm can be seen in Algorithm 3.Algorithm 3:BFSKNN(G,C,k,s).
Input: A (weighted) graph G=(V,E), candidate set C, k nearest neighbors, and source node s;
Output:A list l of (node,distance) from s, where |l|≤k;
(1)let R=null;
(2)let R′={(vi,di)∣vi==s?0:+∞,0≤i≤|G|};
(3)while  R′≠R  do
(4) R=R′;
(5) BFSMapper(R,G);
(6) R′ = BFSReducer();
(7)end while;
(8)//“∩” means the same as Algorithm 1
(9)l=C∩R;
(10)return  lDifferent from the Dijkstra algorithm, which expands the nearest neighbor in each iteration, the BFSKNN algorithm expands all nodes that have the same hops froms (see Algorithm 4 for details). The conditions that terminate them are also different. In the Dijkstra algorithm, if we have found k nearest neighbors or R has not any out-link, the algorithm terminates. However, in the BFSKNN algorithm, the termination condition is that all distances between s and other nodes in G do not change.Algorithm 4:Expanding neighbors with the same hops in BFSKNN.
BFSMapper (R,G):
(1)for all  (node,distance) in R  do
(2) emit(node,distance);
(3)end for;
(4)for all  (from,to) in G  do
(5) emit(to,from.distance+wfrom,to);
(6)end for;
BFSReducer  (output of BFSMapper):
(7)for all  key  do
(8) let result(key,value)=(0,+∞);
(9) for all  value  do
(10)if  value<result.value  then
(11)result=(key,value);
(12)end if
(13)end for;
(14)  emit(result);
(15)end forTheorem 5.
The BFSKNN Algorithm terminates in a limited number of iterations, and the output is a valid solution to the SSMTkSP problem.Proof.
Given the graphG, construct a BFS-tree T rooted at source s in the following steps: (1)
lets be the root of T;(2)
find all out-links for each leaf node ofT in G and add them to T as children of that leaf node;(3)
repeat Step  2 until that the path from root to leaf node forms a loop inG.
So, we have that there is a simple path froms to v in G if and only if there is a path from root to leaf node v in T. The above steps finish in a limited number i (i≤|V|) of iterations, so the BFSKNN algorithm terminates in a limited number of iterations. After i iterations, we can find all the shortest paths between s and other nodes in G, so since the (i+1)-th iteration, all the shortest paths between s and other nodes will not change any more, and the k nearest neighbors from C construct a valid solution to the SSMTkSP problem.However, in each expanding process of BFSKNN, all nodes expand along with their out-links, and this causes the problem of path expansion because all edges have to be accessed. In order to prune edges that are not necessarily accessed, we keep a listcList for each node, which records nodes from the candidate set for the current path. IncList, if a path contains k nodes from C, then we prune paths derived from that path, because they do not contain any useful information about k nearest neighbors. Details can be seen in in Algorithms 5 and 6.Algorithm 5:PruningBFSKNN(G,C,k,s).
Input: A (weighted) graph G=(V,E), candidate set C, k nearest neighbors, and source node s;
Output: A list l of (node,distance) from s, where |l|≤k;
(1)let R=null;
(2)let R′={(vi,cListi,di)∣vi==s?0:+∞,cListi=0,0≤i≤|G|};
(3)while  R′≠R  do
(4) R=R′;
(5) PruningBFSMapper(R,G);
(6) R′ = PruningBFSReducer();
(7)end while;
(8)/*******************************************
(9)Here we redefine “∩” as follows:
(10)R∩C={(vi,di)∣(vi,cListi,di)∈R and vi∈C}
(11) *******************************************/
(12)l=C∩R;
(13)return  lAlgorithm 6:Expanding neighbors with the same hops in PruningBFSKNN.
PruningBFSKNNMapper (R,G):
(1)for all  (node,cList,distance) in R  do
(2) emit(node,cList,distance);
(3)end for;
(4)for all  (from,to) in G  do
(5) if  from.cList∩C≥k  then
(6)  return;
(7) else if  from∈C  then
(8)  cList=cList∪{from}
(9) end if;
(10)  emit(to,cList,from.distance+wfrom,to);
(11)end for;
PruningBFSKNNReducer (output of PruningBFSKNNMapper):
(12)for all  key  do
(13)  Letresult(key,cList,value)=(0,0,+∞);
(14)for all  value  do
(15)if  value<result.value  then
(16)result=(key,cList,value);
(17)else if  value==result.value∧|key.cList|>|result.cList|  then
(18)result=(key,cList,value);
(19)end if;
(20)end for;
(21)  emit(result);
(22)end forExample 6.
Given the graphG in Figure 1, candidate set C={v0,v2,v5,v6} and k=2, we can prune the BFStree of G in Figure 2, and the results are in Figure 3.Pruned BFS-tree of graphG, candidate set C={v0,v2,v5,v6} and k=2.
(a)
T
v
0
(b)
T
v
1
(c)
T
v
2
(d)
T
v
3
(e)
T
v
4
(f)
T
v
5
(g)
T
v
6Theorem 7.
The PruningBFSKNN algorithm terminates in a limited number of iterations, and the output is a valid solution to the SSMTkSP problem.Proof.
Constructing a BFS-treeT the same as Proof of Theorem 5, we have that there is a simple path from source s to target v in G if and only if there is a path from root s to leaf node v in T. Prune paths have k candidate nodes from C after the kth candidate node. There are two kinds of pruned nodes, normal nodes (not belonging to C) and candidate nodes. If a node is a candidate node, it cannot be one of the k nearest neighbors in the pruned paths, because we have found k nearest neighbors in those paths. Otherwise, if a node is a normal node, then whether it appears in pruned paths or not does not affect the termination of the algorithm and does not affect the correctness of the algorithm either. So we have that the PruningBFSKNN algorithm terminates in a limited number of time, and the output is a valid solution to the SSMTkSP problem.


## 4. Performance Analysis

In this section, we analyze and compare the number of iterations andI/O cost of the DijkstraKNN, BFSKNN, and PruningBFSKNN algorithms. Realistic analysis of the efficiency of MapReduce algorithms is not straightforward, because the algorithms’ efficiency in practice depends on many other factors, such as distribution of data, scheduling of jobs, and proximity of the communicating machines. However, these factors are all controlled by the system, and only the number of iterations and I/O cost can be controlled by users’ MapReduce programs.


### 4.1. The Number of Iterations

Theorem 8.
The Dijkstra algorithm with parametersG(V,E),C,k and s finishes in O(k×(|V|/|C|)) MapReduce iterations.Proof.
SinceC is chosen from V, so when we expand a node, the probability that it belongs to C is (|C|/|V|). In order to obtain k nearest neighbors, we need O(k×(|V|/|C|)) expanding processes, so the Dijkstra algorithm finished in O(k×(|V|/|C|)) MapReduce iterations.Theorem 9.
The BFSKNN and PruningBFSKNN algorithms with parametersG(V,E),C,k and s finish in k (k≤D) MapReduce iterations.Proof.
Construct a BFS-treeT the same as Proof of Theorem 5, so the depth of T equals the diameter D of G, and the BFSKNN and PruningBFSKNN algorithms terminate in at most D expanding processes, so the BFSKNN and PruningBFSKNN algorithms finish in at most D MapReduce iterations.


### 4.2.I/O Cost Analysis

We now start by analyzing theI/O cost of the DijkstraKNN algorithm. The DijkstraKNN algorithm terminates in O(k×(|V|/|C|)) expanding processes. In each expanding process, the input is R and G, so the total I/O cost is
(1)O(k·|V||C|(|V|+|E|)).
Next, we analyze the I/O cost of the BFSKNN algorithm. The BFSKNN algorithm terminates in at most D expanding processes. In each expanding process, the input is R and G, so the total I/O cost is
(2)O(D(|V|+|E|)).
At last, we analyze the I/O cost of the PruningBFSKNN algorithm. The PruningBFSKNN algorithm also terminates in at most D expanding processes. In the ith (1≤i<k) expanding process, the input is the same as BFSKNN, but in the ith (k≤i≤D) expanding process, we prune 2i(1-∏j=0i-k‍(1-Ck-1+jk-1(|C|/|V|)k(1-(|C|/|V|))j)) unnecessary paths, so the total I/O cost that we save is
(3)O(∑i=kD‍2i(1-∏j=0i-k‍(1-Ck-1+jk-1(|C||V|)k(1-|C||V|)j))).


## 4.1. The Number of Iterations

Theorem 8.
The Dijkstra algorithm with parametersG(V,E),C,k and s finishes in O(k×(|V|/|C|)) MapReduce iterations.Proof.
SinceC is chosen from V, so when we expand a node, the probability that it belongs to C is (|C|/|V|). In order to obtain k nearest neighbors, we need O(k×(|V|/|C|)) expanding processes, so the Dijkstra algorithm finished in O(k×(|V|/|C|)) MapReduce iterations.Theorem 9.
The BFSKNN and PruningBFSKNN algorithms with parametersG(V,E),C,k and s finish in k (k≤D) MapReduce iterations.Proof.
Construct a BFS-treeT the same as Proof of Theorem 5, so the depth of T equals the diameter D of G, and the BFSKNN and PruningBFSKNN algorithms terminate in at most D expanding processes, so the BFSKNN and PruningBFSKNN algorithms finish in at most D MapReduce iterations.


## 4.2.I/O Cost Analysis

We now start by analyzing theI/O cost of the DijkstraKNN algorithm. The DijkstraKNN algorithm terminates in O(k×(|V|/|C|)) expanding processes. In each expanding process, the input is R and G, so the total I/O cost is
(1)O(k·|V||C|(|V|+|E|)).
Next, we analyze the I/O cost of the BFSKNN algorithm. The BFSKNN algorithm terminates in at most D expanding processes. In each expanding process, the input is R and G, so the total I/O cost is
(2)O(D(|V|+|E|)).
At last, we analyze the I/O cost of the PruningBFSKNN algorithm. The PruningBFSKNN algorithm also terminates in at most D expanding processes. In the ith (1≤i<k) expanding process, the input is the same as BFSKNN, but in the ith (k≤i≤D) expanding process, we prune 2i(1-∏j=0i-k‍(1-Ck-1+jk-1(|C|/|V|)k(1-(|C|/|V|))j)) unnecessary paths, so the total I/O cost that we save is
(3)O(∑i=kD‍2i(1-∏j=0i-k‍(1-Ck-1+jk-1(|C||V|)k(1-|C||V|)j))).


## 5. Experiments

In this section, we present the results of the experiments that we did to test the performance of our algorithms.


### 5.1. Experimental Setup

Dataset. In order to demonstrate the robustness of our methods and to show their performance on realistic data, we present experiments with two real-world datasets, Epinions social network [6] and LiveJournal social network [7, 8]. Summary statistics about these datasets are presented in Table 1.Table 1
Summary characteristics of datasets.
Dataset
|
V
|
|
E
|
D
Epinions
196,591
950,327
13
LiveJournal
4,847,571
68,993,773
18
Here|V|,|E|, and D represent the number of nodes, the number of edges and the diameter of a graph respectively.Experimental Platform. We implement the Dijkstra, BFSKNN, and PruningBFSKNN algorithms in Java on top of Hadoop platform. Our experiments are executed on a cluster of 20 nodes, where each node is a commodity machine with a 2.16 GHz Intel Core 2 Duo CPU and 1 GB of RAM, running CentOS v6.0.


### 5.2. Experimental Results

For choosing the candidate sets, we compute the PageRank scores [5] of each graph using Pegasus [9] and select 5,000 top ones as the candidate set. As can be seen from Figure 4 that PageRank scores of the two graphs all conform to the power law, that means only a small number of nodes are important. In the ads, the candidate sets usually contain the entities in which we gain profit from business.PageRank for graphs.
(a)
Epinions
(b)
LiveJournalWe choose top 50, 500, and 5000 PageRank score nodes from Epinions social network and top 5000 PageRank score nodes from LiveJournal social network and compare the performance of the above algorithms. We select randomly 20 source nodes from each graph and compute the average execution time.As you can see from Figure5, the execution time of the DijkstraKNN algorithm changes greatly as we change the size of the candidate set, and bigger candidate set has smaller execution time. Moreover, the BFSKNN and PruningBFSKNN algorithms have more stable execution time. We also print all results for candidate sets size of 500 and 5000 in Figures 6(a) and 6(b), which show that the execution time grows linearly as the growth of iterations. This is because the inputs are R and G in each iteration, and the processing time is about 37 seconds. However, the execution time also grows nearly linearly as the growth of k, which is against our intuition that it should grow exponentially as the number of nodes grows exponentially. The reason is that when we search in a graph, we usually find high PageRank score nodes instead of those fringe nodes.Figure 5
Execution time of Epinions.Dijkstra algorithm.
(a)
C
=
500
(b)
C
=
5000We also compare the stability of the above algorithms; details are in Figure7. The execution time of the DijkstraKNN algorithm changes greatly as we choose different sources because some nodes having more influential neighbors need less iterations. The BFSKNN and PruningBFSKNN algorithms have more stable execution time because their execution time depends on the radius of a graph for the source, and the radius of a graph is more stable in practice.Figure 7
Stability comparison.For LiveJournal social network, we choose the top 5000 PageRank score nodes as the candidate set and compare the performance of the above algorithms. The result is in Figure8. The DijkstraKNN algorithm is efficient for small k, but if the candidate set is smaller and k is bigger, the PruningBFS algorithm is a better choice.Figure 8
Execution time of LiveJournal.


## 5.1. Experimental Setup

Dataset. In order to demonstrate the robustness of our methods and to show their performance on realistic data, we present experiments with two real-world datasets, Epinions social network [6] and LiveJournal social network [7, 8]. Summary statistics about these datasets are presented in Table 1.Table 1
Summary characteristics of datasets.
Dataset
|
V
|
|
E
|
D
Epinions
196,591
950,327
13
LiveJournal
4,847,571
68,993,773
18
Here|V|,|E|, and D represent the number of nodes, the number of edges and the diameter of a graph respectively.Experimental Platform. We implement the Dijkstra, BFSKNN, and PruningBFSKNN algorithms in Java on top of Hadoop platform. Our experiments are executed on a cluster of 20 nodes, where each node is a commodity machine with a 2.16 GHz Intel Core 2 Duo CPU and 1 GB of RAM, running CentOS v6.0.


## 5.2. Experimental Results

For choosing the candidate sets, we compute the PageRank scores [5] of each graph using Pegasus [9] and select 5,000 top ones as the candidate set. As can be seen from Figure 4 that PageRank scores of the two graphs all conform to the power law, that means only a small number of nodes are important. In the ads, the candidate sets usually contain the entities in which we gain profit from business.PageRank for graphs.
(a)
Epinions
(b)
LiveJournalWe choose top 50, 500, and 5000 PageRank score nodes from Epinions social network and top 5000 PageRank score nodes from LiveJournal social network and compare the performance of the above algorithms. We select randomly 20 source nodes from each graph and compute the average execution time.As you can see from Figure5, the execution time of the DijkstraKNN algorithm changes greatly as we change the size of the candidate set, and bigger candidate set has smaller execution time. Moreover, the BFSKNN and PruningBFSKNN algorithms have more stable execution time. We also print all results for candidate sets size of 500 and 5000 in Figures 6(a) and 6(b), which show that the execution time grows linearly as the growth of iterations. This is because the inputs are R and G in each iteration, and the processing time is about 37 seconds. However, the execution time also grows nearly linearly as the growth of k, which is against our intuition that it should grow exponentially as the number of nodes grows exponentially. The reason is that when we search in a graph, we usually find high PageRank score nodes instead of those fringe nodes.Figure 5
Execution time of Epinions.Dijkstra algorithm.
(a)
C
=
500
(b)
C
=
5000We also compare the stability of the above algorithms; details are in Figure7. The execution time of the DijkstraKNN algorithm changes greatly as we choose different sources because some nodes having more influential neighbors need less iterations. The BFSKNN and PruningBFSKNN algorithms have more stable execution time because their execution time depends on the radius of a graph for the source, and the radius of a graph is more stable in practice.Figure 7
Stability comparison.For LiveJournal social network, we choose the top 5000 PageRank score nodes as the candidate set and compare the performance of the above algorithms. The result is in Figure8. The DijkstraKNN algorithm is efficient for small k, but if the candidate set is smaller and k is bigger, the PruningBFS algorithm is a better choice.Figure 8
Execution time of LiveJournal.


## 6.  Related Work

In this section, we review some related work about MapReduce, the shortest paths and entity recommendation for graphs.MapReduce. MapReduce algorithms have been designed or proposed in the literature for a wide range of applications, such as machine learning [10], text processing [11], and bioinformatics [12, 13]. MapReduce provides an excellent tool for large graph processing as well; a number of graph processing systems have been designed on it in the literature, such as Pegasus [9] and Giraph (http://incubator.apache.org/giraph/). In this paper, we study one of the most well-known graph computation problems, that is, computing the shortest paths or the nearest neighbors.The Shortest Paths. Computing the shortest paths is a basic and important primitive that lies at the core of graph related problems. The shortest path problem can be classified as SSSTSP, SSMTSP, APSP, and kSP and classical algorithms such as Dijkstra algorithm [3] and Floyd-Warshall algorithm [14] can only handle small graphs in serial computation model. As the graphs become larger and larger, in order to answer questions timely, researchers deal with this problem by approximation [15–17], preprocessing [18, 19], or parallelization. Current parallel algorithms for the shortest path problem are mainly based on searching the BFS-tree of the graph [18, 20, 21], but they either study the problem of kSP or focus on APSP. In this paper, we study the problem of SSMTkSP, which is a composition of the above two, design BFS-based parallel algorithm on MapReduce, and propose corresponding pruning strategy.Entity Recommendation. As complex networks, such as social networks and web-page graphs, become more and more popular, entity recommendation on graphs becomes a hotspot among researchers. Current entity recommendation methods are mainly content-based or link-based. Content-based entity recommendation algorithms consider only the content of entities and recommend the most similar ones for some entity (refer to [22, 23] for details). Rank-based entity recommendation algorithms consider the structure of the graphs and recommend the most influential ones for some entity. The influence of entities can be defined as PageRank [5], HITS [24], SimRank [25], or some methods that derive from them. In this paper, from the perspective of influence, we consider the nearest neighbors as the most influential entities and recommend the nearest neighbors from the selected candidate set for some entity.


## 7. Conclusion and Future Work

In this paper, we study the problem of single-source many-targetk shortest paths for graphs, which is finding k nearest neighbors from a candidate set for one source. To the best of our knowledge, this is the first study of recommending k nearest neighbors from selected candidate set. As MapReduce programming model becomes more and more popular in data intensive computing, we evaluate algorithms on its open-source implementation-Hadoop. We design algorithms based on the Dijkstra and breadth-first search algorithms, propose an efficient pruning algorithm for breadth-first search, and evaluate their performance.As graphs become bigger and bigger, precise algorithms need much time to compute several nearest neighbors and some fringe nodes may even waste more computing sources. In the future, we plan to seek approximation algorithms that can handle this problem.



---

*Source: 958350-2014-06-26.xml*