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

Question

我已经实现了基于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

我将"彻底改变"算法.我发现这篇文章计数三角形.

一旦代码实现,我将在这里发布我的意见和更详细的代码(如果这种方法将成功).

---

UPDATE_2

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

Answer 1

在论文“MapReduce in MPI for Large Scale Graphic Algorithm”中，作者对三角形计数的 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 倍计数。这主要是效率较低，因为矩阵的大小如果你的图是稀疏的，那么与边列表的大小相比将会非常大。