同步操作将从 张尉东/GraphMapReduce 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
#GraphMapReduce: 基于MapReduce编程模型的图计算框架
(名词约束: 顶点Vertex-图中顶点;节点Process-计算单元节点),目录说明:
代码主要包含四个文件: gmr.cpp gmr.h algorithms.h graph.h
|__graph/---------#此目录包含测试用的图例数据
|__include/-------#此目录包含所使用到的第三方库的头文件(目前只用到了ParMetis,去掉了GKlib)
|__lib/------------#包含了使用到的第三方库
|__gmr.cpp------#程序的main函数入口和迭代循环
|__gmr.h---------#包含主要的计算过程函数computing()和计算结果更新函数updateGraph()
|__algorithm.h---#常用图算法的MapReduce实现
|__graph.h-------#定义了图数据结果和常用的集中图操作函数
make clean && make
./startgmr.sh (或者mpirun -np 3(注:进程数) ./gmr)
注: 目前正在移植Parmetis(MPI-based)分图部分代码, 所以暂时只能运行graph/已经分好的例图。因为例图都被分为了三个子图,所以目前只能运行三个MPI进程。
目前正在整合并行切图工具Parmetis, 现阶段只能先通过改写的metis进行切图(需要重新编译metis代码,然后运行"gpmetis graphfilename partsnumber"), 或者直接采用切好的示例图库(graph/)中的图进行测试(small.subgraph.* 4elt.graph.* mdual.graph.*分别为不同规模的图例). 目前切图工具采用了metis库,其源码和说明位于include/metis中,其编译使用可参考include/metis/README.md。
结算进程之间通信通过MPI实现;
为了将全图的不同部分放到不同的计算节点进行并行计算,需要将整划分为若干子图。划分工具采用开源的Parmetis进行(为方便使用,正在进行整合)。Parmetis是基于MPI进行大规模的子图划分,为了方便和适应我们的算法,我们对Parmetis的输出结果进行了重写,每个输出的节点的格式如下:
#节点id 节点权重 邻居1的id 邻居1所在进程 邻居1所在边权重 ...邻居N的id 邻居N所在进程 邻居N所在边权重
vertex_id vertex_weight neighbor1 neighbor1.location edge1.weight ... neighborN neighborN.location edgeN.weight
第一步,先遍历自己计算的子图graph与其他子图的邻居情况,并收集需要向其他节点发送的字节数,并申请发送缓冲区;
第二步,通过MPI_Alltoall()与其他节点交换其他节点需要接受的字节数,每个节点收到信息后,各自计算和申请接受数据需要的空间。
第三步,再次遍历自己计算的子图graph,并将需要发往其他节点的顶点信心拷贝到发送缓存char *sb;
第四部,调用MPI_Alltoallv(),将发送缓存中的数据发往各节点.
将子图graph和接受缓冲区中的数据实例化为顶点Vertex,再调用业务逻辑函数map将Vertex生成key/value list。
将排序好的key/value list按照业务逻辑函数reduce进行规约.
void map(Vertex &v, std::list<KV> &kvs){
int neighbor_count = 0;
while(v.neighbors[neighbor_count] != 0)neighbor_count++;
float value = v.value / neighbor_count;
for (int i = 0; i < neighbor_count; i++)
kvs.push_back({v.neighbors[i], value});
}
KV reduce(std::list<KV> &kvs) {
float sum = 0.0;
for (auto kv : kvs) {
sum += kv.value;
}
/*Pagerank=a*(p1+p2+…Pm)+(1-a)*1/n,其中m是指向网页j的网页j数,n所有网页数*/
sum = 0.5 * sum + (1 - 0.5) / (sizeof(vs) / sizeof(Vertex) - 1);
return {kvs.front().key, sum};
}
上述上网者的行为是一个马尔科夫过程的实例,要满足收敛性,需要具备一个条件: 图是强连通的,即从任意网页可以到达其他任意网页: 互联网上的网页不满足强连通的特性,因为有一些网页不指向任何网页,如果按照上面的计算,上网者到达这样的网页后便走投无路、四顾茫然,导致前面累 计得到的转移概率被清零,这样下去,最终的得到的概率分布向量所有元素几乎都为0。假设我们把上面图中C到A的链接丢掉,C变成了一个终止点,得到下面这个图:
另外一个问题就是陷阱问题,即有些网页不存在指向其他网页的链接,但存在指向自己的链接。比如下面这个图:
上网者跑到C网页后,就像跳进了陷阱,陷入了漩涡,再也不能从C中出来,将最终导致概率分布值全部转移到C上来,这使得其他网页的概率分布值为0,从而整个网页排名就失去了意义。
Processor\Platform | GMR | Spark | GraphX | GraphLab | Pregel |
1 | | | | | |
3 | | | | | |
8 | | | | | |
16 | | | | | |
64 | | | | | |
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。