首页 文章

分布式局部聚类系数算法（MapReduce / Hadoop）

提问于
浏览 次
19

我已经实现了基于local clustering coefficient algorithm的MapReduce范例 . 但是，我遇到了更大的数据集或特定数据集（节点的高平均程度）的严重问题 . 我试图调整我的hadoop平台和代码，但结果不令人满意（至少可以说） . 不，我已经把注意力转向实际改变/改进算法 . 下面是我目前的算法（伪代码）

foreach(Node in Graph) {
  //Job1
  /* Transform edge-based input dataset to node-based dataset */

  //Job2
  map() {
   emit(this.Node, this.Node.neighbours) //emit myself data to all my neighbours
   emit(this.Node, this.Node) //emit myself to myself
  }

  reduce() {
    NodeNeighbourhood nodeNeighbourhood;
    while(values.hasNext) {
      if(myself)
        this.nodeNeighbourhood.setCentralNode(values.next) //store myself data
      else
        this.nodeNeighbourhood.addNeighbour(values.next)  //store neighbour data
    }

    emit(null, this.nodeNeighbourhood)
  }

  //Job3
  map() {
    float lcc = calculateLocalCC(this.nodeNeighbourhood)
    emit(0, lcc) //emit all lcc to specific key, combiners are used
  }

  reduce() {
    float combinedLCC;
    int numberOfNodes;
    while(values.hasNext) {
      combinedLCC += values.next;
    }

    emit(null, combinedLCC/numberOfNodes); // store graph average local clustering coefficient
  }
}

关于代码的更多细节 . 对于有向图，邻居数据被限制为节点ID和OUT边缘目的地ID（以减小数据大小），对于未定向的节点ID和边缘目的地ID . 排序和合并缓冲区增加到1.5 Gb，合并流80 .

可以清楚地看到Job2是整个算法的实际问题 . 它会生成大量必须进行排序/复制/合并的数据 . 这基本上会破坏某些数据集的算法性能 . 有人可以指导我如何改进算法（我正在考虑创建迭代Job2 [“过程”在每次迭代中只有N个M节点，直到每个节点都被“处理”]，但我现在已经放弃了这个想法） . 在我看来，应该减少Job2 map-output，以避免代价高昂的排序/合并过程，这会破坏性能 .

我也为Giraph平台实现了相同的算法（3个作业，相同的“通信”模式，也称“Job2”问题） . 然而，Giraph是一个内存平台，同一个“有问题的”数据集的算法会导致OutOfMemoryException .

对于任何评论，评论，指南，我将不胜感激 .

UPDATE

我'm going to change the algorithm 788442 . I'已经找到了这篇文章Counting Triangles .

一旦代码实现，我将在这里发表我的意见和更详细的代码（如果这种方法将成功） .

UPDATE_2

最后，我结束了“修改”NodeIterator算法以满足我的需求（雅虎论文可以通过文章中的链接获得） . 不幸的是，尽管我可以看到性能有所改善，但最终结果还不如我所希望的那么好 . 我得出的结论是，我可用的集群太小，无法使LCC计算对这些特定数据集可行 . 所以问题仍然存在，或者说它会发展 . 有没有人知道有效的分布式/顺序算法用于计算可用资源有限的LCC或三角形？ （我决不是说NodeIterator算法不好，我简单地说我可用的资源是不够的） .

performance algorithm graph hadoop mapreduce

1 回答

  • 0

    在论文"MapReduce in MPI for large scale graph algorithms"中，作者对三角计数的MapReduce实现给出了很好的描述 . 该文件可在此处获取：http://www.sciencedirect.com/science/article/pii/S0167819111000172但您可能需要一个帐户才能访问该论文 . （我'm on a University system that'已支付订阅费用，所以我永远不知道我只能访问，因为他们已经付费 . ）作者可能会在个人网站上发布该论文的草稿 .

    还有另一种方法可以计算三角形 - 除非图形相当密集，否则效率可能会低得多 . 首先，构建图形的邻接矩阵A.然后计算A ^ 3（你可以很容易地并行地进行矩阵乘法） . 然后，总结A ^ 3的（i，i）条目并将答案除以6.这将给出三角形的数量，因为A ^ k的i，j条目计算从i开始的长度k步数因为我们只看3个步行，所以任何从i开始并在3步后结束的步行都是一个三角形...超过6倍 . 这主要是因为矩阵的大小效率较低如果图表稀疏，则与边缘列表的大小相比将非常大 .

    回复于

相关问题