论文部分内容阅读
社交网络分析、网络舆情发现等应用发展迅速，这些应用所基于的图结构规模也越来越大，在对图结构的研究中，对亿万个顶点级别的大规模图的处理能力的需求愈加迫切。因为如今图的规模太大，使得最短路径查询问题变得更加具有挑战性，其中包括大规模图结构的存储以及查询的效率等挑战性问题。传统的串行算法在处理大规模图结构时面临着巨大的问题。众所周知，云计算的发展与大规模数据的处理关系紧密。所以运用云计算环境，在大规模图上进行数据处理是一个十分有潜力的研究方向。最近几年，Hadoop是一个十分典型的云计算平台代表。于是，我们可以基于Hadoop来对我们的问题进行研究。本文主要结合云计算相关知识以及社交网络、交通网络实际应用，对大规模图上的距离查询经典问题进行研究。本文首先针对实际应用提出并行化的经典Floyd类矩阵乘法算法D-Floyd，并将该算法在Hadoop平台上进行实现。D-Floyd算法主要采用Hadoop中的MapReduce和HDFS两部分来将经典Floyd算法在分布式环境下进行实现。接着，我们对D-Floyd进行优化扩展，优化方案主要从D-Floyd算法本身和Hadoop平台两个方面入手进行考虑。然后我们研究了支持增量计算的D-Floyd算法，根据研究，我们定义“有界”和“无界”，提出部分增量的D-Floyd和完全增量的D-Floyd。我们将算法与已有的OptHCL-2方法、NaiveHCL方法、BSC2Hop方法进行多角度的分析比较，阐述分布式方案的必要性及优点。接下来，我们提出BFS计算无权图中最短路径的分布式解决方案并将其在Hadoop平台上进行实现，并与D-Floyd进行分析比较。通过试验分析，我们提出的D-Floyd算法显然要比已有的单机串行算法高效，而且优化后的D-Floyd算法和增量式D-Floyd算法的相关研究提出的方法都在一定程度上提高了D-Floyd算法的性能。此外，在无权图中D-BFS比D-Floyd性能要好很多，于是在实际的应用中，当要处理的图为无向图时，可以采用D-BFS方案进行计算，当要处理的图为有向图时，则只能采用D-Floyd方案进行计算。最后我们结合现有的一些经典算法如A*寻路算法、B*算法等在分布式架构上实现的思路，提出展望并实现相关应用。比如，我们可以将解决方案运用到社交网络人物关系图谱分析、网络舆情传播控制模型发现等应用中。