19

我已经实现了基于 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 映射输出，以避免代价高昂的排序/合并过程，这会降低性能。

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

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

更新

我将“彻底”改变算法。我发现这篇文章Counting Triangles。

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

更新_2

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

4

1 回答 1

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 倍。这主要是效率较低，因为矩阵的大小如果您的图是稀疏的，那么与边缘列表的大小相比将会非常大。

于 2014-11-04T21:44:54.960 回答