一种基于Map Reduce的大型网络图中寻找公共联系人及其路径的计算方法

摘要

本发明涉及社交网络领域，具体涉及一种基于Map Reduce的大型网络图中寻找公共联系人及其路径的计算方法，所述计算方法通过Map Reduce运行机制，结合跳级原则(Mapper)和合并原则(Reducer)，建立在大型网络图或社交网络中寻找目标群体在若干跳数内的所有公共联系人及其最短联系路径的分布式计算框架，计算所述目标群体到所述公共联系人之间的最短路径，记录并存储于数据库中。本发明成功地将Map模型和Reduce模型结合在一起，实现了目标群体任意节点到该公共联系人之间的最短路径计算和记录；提出了一种效率较高的最短路径优化计算方法，为社交网络的进一步推进发展提供了一种新的算法推进思路。

主权项

一种基于Map Reduce的大型网络图中寻找公共联系人及其路径的计算方法，其特征在于：所述计算方法通过Map Reduce运行机制，结合跳级原则(Mapper)和合并原则(Reducer)，建立在大型网络图或社交网络中寻找目标群体在若干跳数内的所有公共联系人及其最短联系路径的分布式计算框架，计算所述目标群体到所述公共联系人之间的最短路径，记录并存储于数据库中；所述计算方法包括如下计算步骤：(1)初始状态：新建一个以“.txt”为后缀的任意命名文本文件，其内容包含三行数据，其中第一列数据为目标群体节点群体，后面各列数据为目标群体节点之间的最短距离，所述目标群体之间的直接相互关系被记录于所述文本文件中；(2)第一跳Mapper：从HBase中获取各目标群体节点的直接联系人，并计算这些所述直接联系人到所述目标群体节点之间的距离；若某节点是满足第K跳的公共联系人之一，则该节点的直接联系人均是满足第K+1跳的公共联系人；(3)第一跳Reducer：采用“合并原则”，若推导过程中对某个节点有多个不一样的距离记录，应该将其合并，取最小值；具体规律为：非负距离之间的比较，取距离最小的路径；如果非负距离的最小值有多个，则计算路径时保存所有最小距离上的不同路径；距离未知和距离已知之间的比较，取距离已知的路径；如果距离都是‑1，那么路径也是‑1；(4)第二跳Map Reduce：将第一次Map Reduce输出的距离矩阵文件作为第二次Map Reduce的输入，然后重复所述Mapper(跳级原则)和所述Reduce(合并原则)过程，获取两跳内的公共联系人及其联系路径；(5)第K跳Map Reduce：将第K‑1次Map Reduce输出的所述距离矩阵文件作为第K次Map Reduce的输入，然后重复Mapper(跳级原则)和Reducer(合并原则)过程，获取K跳内的公共联系人及其联系路径；(6)结果输出：根据“终止原则”，经过多次跳级动作之后，最终能成为目标节点群体在K跳内公共联系人的节点，一定满足一个条件，即到目标节点群体的距离均在0‑K之内，只有距离不大于K的节点满足条件，具体规则为：若寻找在K跳内的公共联系人，经过K次Map Reduce计算之后，距离矩阵中满足条件的节点为N_i(D₁,D₂,D₃,…,D_m)，其中0<D_j(0<j<＝m)<＝K；所有满足此规则的节点即为K跳内的公共联系人，距离向量中每个元素的路径即为公共联系人到目标节点的最短联系路径。