performance - 分布式局部聚类系数算法(MapReduce/Hadoop)

Question

我已经实现了基于 MapReduce 范例的 local clustering coefficient algorithm .但是，对于更大的数据集或特定的数据集(节点的平均度数高)，我遇到了严重的麻烦。我试图调整我的 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 映射输出应该减少，以避免代价高昂的排序/合并过程，这会降低性能。

我也为 Giraph 平台实现了相同的算法(同样是 3 个作业，相同的“通信”模式，还有“Job2”问题)。然而，Giraph 是一个内存平台，针对相同“有问题”的数据集的算法会导致 OutOfMemoryException。

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

---

更新

我将“彻底”改变算法。我找到了这篇文章 Counting Triangles .

代码实现后，我将在这里发表我的意见和更详细的代码(如果这种方法会成功的话)。

---

UPDATE_2

最后，我根据自己的需要“修改”了 NodeIterator++ 算法(Yahoo 论文可通过文章中的链接获得)。不幸的是，虽然我可以看到性能有所提高，但最终结果并不像我希望的那样好。我得出的结论是，我可用的集群太小，无法使 LCC 计算对这些特定数据集可行。所以问题仍然存在，或者更确切地说，它在演变。有谁知道一种有效的分布式/顺序算法来计算可用资源有限的 LCC 或三角形？(我绝不是说 NodeIterator++ 算法不好，我只是说我可用的资源还不够)。

Answer 1

在论文“用于大规模图算法的 MPI 中的 MapReduce”中，作者很好地描述了三角计数的 MapReduce 实现。该论文可在此处获得:http://www.sciencedirect.com/science/article/pii/S0167819111000172但您可能需要一个帐户才能访问该论文。 (我使用的是付费订阅的大学系统，所以我永远不知道我只能访问什么，因为他们已经付费了。)作者可能会在个人网站上发布论文草稿。

还有另一种计算三角形的方法——除非您的图形相当密集，否则效率可能要低得多。首先，构建图形的邻接矩阵 A。然后计算 A^3(您可以很容易地并行执行矩阵乘法)。然后，将 A^3 的 (i,i) 个条目相加并将答案除以 6。这将为您提供三角形的数量，因为 A^k 的 i,j 条目计算从 i 走的长度 k 的数量到 j 并且因为我们只看长度为 3 的步行，任何从 i 开始并在 3 步后以 i 结束的步行都是三角形......多算了 6 倍。这主要是效率较低，因为矩阵的大小如果您的图形是稀疏的，则与边缘列表的大小相比将非常大。