文摘

事物的连接到互联网可以让聪明的事情来访问各种各样的Web服务。然而,智能能源有限公司,和合适的Web服务的选择将消耗更少的资源。在本文中,我们研究的问题选择一些Web服务从候选集。我们制定这个智能东西单一选择Web服务的许多目标最短路径问题。我们设计算法基于Dijkstra算法和广度优先搜索算法,提出一种有效的修剪广度优先搜索算法的迭代次数,并分析其性能 成本。实证评价真实图表明我们修剪算法比广度优先搜索算法更有效。

1。介绍

最近,发展RFID、传感器和网络技术使各种物理世界的东西连接到互联网,人们通常称之为物联网(物联网)。在物联网中,越来越多的设备连接到互联网,和下一步是使用万维网及其相关技术,如Web服务,作为智能平台的事情。

在网上,有很多Web服务。这些Web服务相互联系和构造图的拓扑结构。在物联网、智能都是连接到互联网,他们可以访问各种各样的Web服务。然而,聪明的事情通常是能源有限公司,所以选择合适的Web服务是极其重要的。Guinard et al。1]给出了Web服务的总体视图访问互联网的东西。他们提出一个过程和一个合适的系统架构,实现动态查询,开发人员和业务流程设计人员选择,并使用实际服务的运行实例。

在本文中,我们研究了物联网环境中的Web服务选择问题;即给定一个明智和Web服务的一个图表,如何选择几个合适的Web服务从候选集,同时提供令人满意的服务质量。如果所选择的Web服务是最近的,聪明的会少访问和等待时间,然后消耗更少的能量。在这里,我们制定的选择Web服务作为单一许多目标最短路径问题。

最短路径问题可分为SSSTSP(单源打最短路径),SSMTSP(单源许多目标最短路径),APSP(全对最短路径) 周效磺胺-乙胺嘧啶( 最短路径)。MSSTSP(许多来源打最短路径)是一样的SSMTSP如果我们反向图中所有边。

1.1。我们的贡献

在本文中,我们研究SSMT的问题 SP(单一许多目标 最短路径)MapReduce,发现 从一组候选人一个源节点最短路径MapReduce。在我们的工作中,我们不关心的 路径,而是 最近的邻居的源节点,所以SSMT SP问题也可以被视为单一许多目标 最近的邻居的问题。的SSMT SP可以用于推荐朋友或广告在社交网络上,和在公路网络搜索购物中心或酒店。

我们设计算法基于Dijkstra算法和广度优先搜索算法,提出一种有效的修剪广度优先搜索算法的迭代次数,并分析其性能 成本。实证评价现实生活中的图形和Hadoop平台显示,修剪算法比广度优先搜索最短路径算法更有效。

剩下的纸是组织如下。部分2最短路径的背景图,MapReduce,迪杰斯特拉算法,和广度优先搜索。的SSMT SP问题并提出了相应的算法3。我们在部分分析算法的性能4实验结果显示,在部分5和审查的相关工作部分6。最后,给出了结论和未来的工作部分7。

2。背景

在本节中,我们提供了一些背景为最短路径图,MapReduce,迪杰斯特拉算法,和广度优先搜索。

2.1。最短路径图

我们考虑一个加权有向图 ,在那里 是一组节点, 边的集合,节点和边的数目 和 ,分别。我们使用 代表的直径 。对于一个边缘 ,重量来标示 , 是 的父节点 是 的子节点。一个路径 在一个图 是一个序列的节点 ,在那里 和 。 和 被称为开始和目标的 和联系在一起 。的长度 之间的源和目标是边的权重的总和;也就是说, 和啤酒花的数量源来目标在 边的数量,也就是说, 。

定义1。一个路径 在图 从开始 为目标 是一个最短路径,如果不存在路径吗 之间的 和 ,这样 。
为了简化,我们假设在剩下的纸的重量在每边 = 1;也就是说, 。这缩短了 一个无关紧要的图,但不影响我们的算法的结果。

2.2。MapReduce

MapReduce (2),谷歌提出的,是一种编程模型并行处理大量的数据使用大量商品的机器,和它的开源实现Hadoop (http://hadoop.apache.org/docs/current/hadoop-project-dist/hadoop-hdfs/Federation.html)。通过自动处理低水平的问题,比如工作分配、数据存储、容错,它允许程序员没有任何经验,并行和分布式系统很容易利用的资源一个大型分布式系统。

MapReduce-like系统,程序迭代完成的三个阶段:地图,洗牌,和减少。在地图阶段,他们读值或键/值对的集合从并行输入源和排放零个或多个键/值对,每个输入元素通过调用一个用户定义的映射器函数。在洗牌阶段,他们一起Mapper-emitted键/值对共享同一密钥和输出所有组到下一个阶段。在减少阶段,它们调用用户定义的减速机函数为每一个不同的组独立和并行和排放零个或多个键/值对将写在磁盘上或下一个的输入地图在接下来的迭代阶段。在我们的工作中,我们将使用两个基本元素:地图和减少。

2.3。迪杰斯特拉算法

迪杰斯特拉算法(3)是单源最短路径问题的经典算法图与积极的权重。计算源之间的最短路径 和任何其他节点图。主要的思想是,从 ,扩大一个节点的最短路径 ;重复这个过程,直到所有的节点都达到了从扩张 。在每个扩张过程中,展开一个最近邻算法,它要求每条边的重量是正的。

例2。考虑到图 在图1如果我们选择 源之间的距离 和其他节点 ,可以做6扩张过程。


图1
图 当我们运行的例子。
2.4。广度优先搜索

找到源之间的最短路径 和其他节点图 ,我们可以进行广度优先搜索(BFS)从 并获得一个BFS-tree (4]。为了构建BFS-tree ,我们首先初始化 作为一个树只有根节点 然后添加的孩子 在 来 。也就是说,如果 中,我们添加了 来 作为一个孩子的 。然后迭代,每个叶节点 在当前 ,我们搜索所有的孩子 ,这样 和 还没有添加到吗 然而,添加 来 作为一个孩子的 。

例3。也考虑到图 在图1的BFS-tree 可以看到图吗2。如果我们选择 源之间的距离 也和其他节点 , ,但只有3中的BFS能完成扩张过程。

(一)
(一)
(b)
(b)
(c)
(c)
(d)
(d)
(e)
(e)
(f)
(f)
(g)
(g)
图2
BFS-tree的图 。

3所示。SSMT SP

3.1。问题陈述

定义4。给定一个有向图(加权) 和一个候选节点集 这是选择从 ,SSMT SP问题是,源节点 ,找 最近的邻居与最短路径,这样那些最近的邻居 。

在我们的工作中,我们不关心 具体路径,而是 目标节点,或称最近的邻居,所以SSMT SP问题也可以被视为单一许多目标 最近的邻居的问题。候选集 可以选择从 根据节点的图上的重要性,如网页排名分数(5]。

3.2。DijkstraKNN MapReduce算法

MapReduce,我们保持一个根集 为源 。在一开始, 只包含( ,0),在每个迭代中,我们添加一个最近邻 之间最短的距离 和 来 。只要 包含 节点来自 ,或者没有与外部 ,扩大进程终止。然后我们可以得到 最近的邻居通过另一个地图阶段。DijkstraKNN算法的细节中可以看到算法1和2。

输入:(加权)图 ,候选人 , 最近的邻居,源节点 ;
输出:一个列表 的 从 ,在那里 ;
(1)让 ;
(2)让 ;
(3)/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
(4)这里我们定义” ”如下:
(5) 和
(6)* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /
(7)而 做
(8)DijkstraMapper ;
(9)/ /找到最近的邻居
(10) ∪DijkstraReducer ();
(11)结束时
(12) ;
(13)返回
算法1
DijkstraKNN ( )。

DijkstraMapper :
(1)对所有 在 做
(2)如果 然后
(3)发出 ;
(4)如果
(5)结束了;
DijkstraReducer(输出DijkstraMapper):
(6)让 ;
(7)对所有 做
(8)/ /找到最近的邻居不是 ;
(9)如果 然后
(10) ;
(11)如果
(12)结束了;
(13)返回
算法2
扩大最近邻。

3.3。BFSKNN MapReduce和PruningBFSKNN算法

DijkstraKNN算法每次迭代扩展一个最近邻的来源 。然而,我们可以扩大其所有邻国的啤酒花同时,也就是说,BFSKNN算法。在BFSKNN算法,迭代我们扩大相同的啤酒花的所有邻居 和更新之间最短的距离 这些节点。尽管所有的距离不会改变,我们获得之间最短的距离 和其他节点图。BFSKNN算法的细节中可以看到算法3。

输入:(加权)图 ,候选人 , 最近的邻居,源节点 ;
输出:一个列表 的 从 ,在那里 ;
(1)让 ;
(2)让 ;
(3)而 做
(4) ;
(5)BFSMapper ;
(6) = BFSReducer ();
(7)结束时;
(8)/ /” ”意思是一样的算法1
(9) ;
(10)返回
算法3
BFSKNN ( )。

不同的迪杰斯特拉算法,扩展了最近邻在每个迭代中,BFSKNN算法扩展的所有节点具有相同的啤酒花 (参见算法4详情)。终止的条件也不同。迪杰斯特拉算法,如果我们发现 最近的邻居或 没有任何与该算法终止。然而,在BFSKNN算法终止条件之间的距离 和其他节点 不改变。

BFSMapper( ):
(1)对所有 在 做
(2)发出 ;
(3)结束了;
(4)对所有 在 做
(5)发出 ;
(6)结束了;
BFSReducer(输出BFSMapper):
(7)对所有 做
(8)让 ;
(9)对所有 做
(10)如果 然后
(11) ;
(12)如果
(13)结束了;
(14)排放( );
(15)结束了
算法4
扩大与同样的啤酒花BFSKNN的邻居。

定理5。BFSKNN算法终止在有限数量的迭代,和输出SSMT是一个有效的解决方案 SP的问题。

证明。考虑到图 ,构造一个BFS-tree 扎根在源头 在接下来的步骤:(1)让 的根 ;(2)找到每个叶节点的所有外部链接 在 并将它们添加到 作为叶子节点的孩子;(3)重复步骤2,直到从根到叶子的路径节点形成一个循环 。
所以,我们有一个简单的路径 来 在 当且仅当存在一条从根到叶节点 在 。上述步骤完成数量有限 ( )的迭代,因此BFSKNN算法在有限的迭代终止。后 迭代,我们都可以找到之间的最短路径 和其他节点 ,所以自 th迭代之间的最短路径 和其他节点将不再改变 最近的邻居的 SSMT构造一个有效的解决方案 SP的问题。

在每个BFSKNN的扩张过程,然而,所有节点及其与外部扩张,这导致扩张路径的问题,因为所有边缘都要访问。为了修剪边缘不一定是访问,我们有一个清单cList对于每个节点,记录从候选节点设置为当前路径。在cList,如果一个路径包含 节点从 ,然后删除路径来自这条道路,因为他们不包含任何有用的信息 最近的邻居。在算法的细节中可以看到5和6。

输入:(加权)图 ,候选人 , 最近的邻居,源节点 ;
输出:一个列表 的 从 ,在那里 ;
(1)让 ;
(2)让 ;
(3)而 做
(4) ;
(5)PruningBFSMapper ;
(6) = PruningBFSReducer ();
(7)结束时;
(8)/ * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
(9)这里我们定义” ”如下:
(10) 和
(11)* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /
(12) ;
(13)返回
算法5
PruningBFSKNN ( )。

PruningBFSKNNMapper( ):
(1)对所有 在 做
(2)发出 ;
(3)结束了;
(4)对所有 在 做
(5)如果 然后
(6)返回;
(7)其他的如果 然后
(8)
(9)如果;
(10)发出 ;
(11)结束了;
PruningBFSKNNReducer(输出PruningBFSKNNMapper):
(12)对所有 做
(13) ;
(14)对所有 做
(15)如果 然后
(16) ;
(17)其他的如果 然后
(18) ;
(19)如果;
(20)结束了;
(21)排放( );
(22)结束了
算法6
扩大与同样的啤酒花PruningBFSKNN的邻居。

例6。考虑到图 在图1,候选人 和 我们可以删除的BFStree 在图2,结果在图3。

(一)
(一)
(b)
(b)
(c)
(c)
(d)
(d)
(e)
(e)
(f)
(f)
(g)
(g)
图3
修剪BFS-tree的图 ,候选人 和 。

定理7。PruningBFSKNN算法终止在有限数量的迭代,和输出SSMT是一个有效的解决方案 SP的问题。

证明。构建一个BFS-tree 一样的定理的证明5,我们有一个简单的路径从源 为目标 在 当且仅当存在一个路径的根 叶子节点 在 。删除路径有 候选节点从 后 候选节点。有两种修剪节点、普通节点(不属于 )和候选节点。如果一个节点是一个候选节点,它不能之一 最近的邻居修剪的路径,因为我们已经找到了 最近的邻居的路径。否则,如果一个节点是一个正常的节点,那么是否出现在修剪路径不影响算法的终止,不影响算法的正确性。所以我们有PruningBFSKNN算法终止在一个有限的时间,和输出SSMT是一个有效的解决方案 SP的问题。

4所示。性能分析

在本节中,我们分析和比较迭代和的数量 DijkstraKNN成本、BFSKNN PruningBFSKNN算法。现实的MapReduce算法效率的分析并不简单,因为算法的效率实际上取决于其他很多因素,比如分布的数据,调度工作,和近距离的交流的机器。然而,这些因素都是由系统控制,且仅迭代和的数量 成本可以控制用户的MapReduce程序。

4.1。迭代的次数

定理8。迪杰斯特拉算法与参数 和 完成在 MapReduce迭代。

证明。自 选择从 ,所以当我们扩展一个节点,它属于的概率 是 。为了获得 最近的邻居,我们所需要的 扩张的过程,所以Dijkstra算法完成 MapReduce迭代。

定理9。BFSKNN PruningBFSKNN算法和参数 和 完成在 ( MapReduce的迭代。

证明。构造一个BFS-tree 一样的定理的证明5,所以的深度 等于直径 的 ,BFSKNN PruningBFSKNN算法终止 扩张的过程,所以BFSKNN和PruningBFSKNN算法完成 MapReduce迭代。

4.2。 成本分析

我们现在开始通过分析 成本DijkstraKNN算法。DijkstraKNN算法终止 扩大的过程。在每个扩张过程中,输入 和 ,所以总 成本是 接下来,我们分析 成本BFSKNN算法。BFSKNN算法终止 扩大的过程。在每个扩张过程中,输入 和 ,所以总 成本是 最后,我们分析了 成本PruningBFSKNN算法。PruningBFSKNN算法也终止 扩大的过程。在 th ( )扩大过程中,输入BFSKNN是一样的,但在 th ( )扩大的过程,我们修剪 不必要的路径,所以总 我们节省成本

5。实验

在本节中,我们提出我们做的实验测试的结果我们算法的性能。

5.1。实验装置

数据集。为了证明我们的方法的鲁棒性和展示他们在现实的表现数据,我们提出的两个真实数据集的实验,Epinions这样的社交网络(6和LiveJournal上的社交网络7,8]。总结这些数据集的统计信息展示在表1。

表1
总结数据集的特征。

实验平台。我们实现Dijkstra算法、BFSKNN PruningBFSKNN Hadoop之上的算法在Java平台。我们的实验是一个集群上执行20节点,每个节点是一个商品机2.16 GHz的英特尔酷睿2双核CPU和1 GB内存,运行CentOS v6.0。

5.2。实验结果

选择候选集,我们计算网页排名分数(5每个使用飞马(图)9),并选择5000年的候选集。我们可以看到从图4PageRank分数的两个图表符合幂律,这意味着只有少数的节点是重要的。在广告中,候选集通常包含的实体,我们从业务中获利。

(一)Epinions这样
(一)Epinions这样
(b) LiveJournal上
(b) LiveJournal上
图4
图的PageRank。

我们选择前50名,500年和5000年PageRank分节点从Epinions这样的社交网络和网页排名5000强分节点从LiveJournal社交网络并比较上述算法的性能。我们随机选择20从每个源节点图和计算的平均执行时间。

可以看到从图5DijkstraKNN算法的执行时间变化极大地改变候选集的大小,和更大的候选集规模较小的执行时间。此外,BFSKNN和PruningBFSKNN算法有更稳定的执行时间。我们也打印所有候选人的结果集500年和5000年的数据的大小6(一)和6 (b),这表明,执行时间增长线性迭代的增长。这是由于输入 和 在每个迭代中,处理时间约为37秒。然而,执行时间也变得几乎线性的增长 ,这是对我们的直觉,它应该会随着节点数量的增加而按指数指数增长。原因在于,当我们搜索一个图,我们通常发现高PageRank得分节点,而不是那些边缘节点。


图5
Epinions这样的执行时间。
(一)
(一)
(b)
(b)
图6
迪杰斯特拉算法。

我们也比较上述算法的稳定性;细节图7。DijkstraKNN算法的执行时间变化很大,我们选择不同的来源,因为某些节点拥有更多有影响力的邻居需要较少的迭代。BFSKNN和PruningBFSKNN算法更稳定的执行时间,因为他们执行时间取决于源图的半径,和图的半径在实践中更加稳定。


图7
比较稳定。

LiveJournal上的社交网络,我们选择网页排名得分5000强节点作为候选集和上述算法的性能进行比较。结果是图8。小的DijkstraKNN算法是有效的 ,但如果候选集和小 较大,PruningBFS算法是一个更好的选择。


图8
LiveJournal上的执行时间。

在本节中,我们回顾一些关于MapReduce的相关工作,图的最短路径和实体的推荐。

MapReduce。MapReduce算法设计或提出在文献中广泛应用,如机器学习(10),文本处理(11),和生物信息学12,13]。MapReduce大型图像处理提供了一个极好的工具;许多图像处理系统设计在文献中,比如飞马(9)和Giraph (http://incubator.apache.org/giraph/)。在本文中,我们研究的一个最著名的图形计算问题,即计算最短路径或最近的邻居。

最短的路径。计算最短路径是一个基本的和重要的原始图相关的核心问题。最短路径问题可以分为SSSTSP SSMTSP APSP, SP和经典算法如迪杰斯特拉算法(3)和Floyd-Warshall算法(14]只能处理小图形串行计算模型。随着图表变得越来越大,为了及时回答问题,近似处理这个问题的研究人员(15- - - - - -17],预处理[18,19),或并行。当前并行算法的最短路径问题主要是基于图的搜索BFS-tree [18,20.,21),但他们要么研究的问题 SP或关注APSP。在本文中,我们研究SSMT的问题 SP,是上述两种的组合,设计BFS-based MapReduce并行算法,并提出相应的剪枝策略。

实体的推荐。复杂网络,如社交网络和网页图形、越来越受欢迎,实体的推荐图成为一个热点研究之一。目前的实体的推荐方法主要是基于内容的性质。实体基于内容的推荐算法只考虑实体的内容,推荐最相似的实体(参见[22,23]详情)。Rank-based实体推荐算法考虑的结构图形和建议对一些最有影响力的实体。实体的影响可以被定义为网页排名(5],点击[24],SimRank [25),或一些来自他们的方法。本文从影响的角度来看,我们认为最近的邻居是最具影响力的实体和推荐最近的邻居一些选定的候选集的实体。

7所示。结论和未来的工作

在本文中,我们研究单源许多目标的问题 图的最短路径,是发现 最近的邻居从一组候选人一个源。我们所知,这是第一个研究的建议 最近的邻居从选定的候选集。MapReduce编程模型在数据密集型计算变得越来越流行,在其开源implementation-Hadoop我们评估算法。我们设计算法基于Dijkstra算法和广度优先搜索算法,提出一种有效的剪枝算法广度优先搜索,并评估他们的表现。

随着图形变得越来越大,精确算法需要大量的时间来计算几个最近的邻居和一些边缘节点甚至可能浪费更多的计算资源。在未来,我们打算寻求近似算法,可以处理这个问题。

利益冲突

作者宣称没有利益冲突有关的出版。