apache-spark - Spark 图x : how to travers a graph to create a graph of second degree neighbors

Question

我是 Spark/hadoop/图形计算的初学者，所以请请原谅我的初学者问题。

我使用 graphx 创建了一个图表。现在，对于每个顶点，我想要得到它的所有二级邻居。所以如果我的图表是:

v1 --> v2
v1 --> v4
v1 --> v6

我想要得到类似的东西:

v2 --> v4
v2 --> v6
v4 --> v2
v4 --> v6
v6 --> v2
v6 --> v4

我的图表非常大，所以我希望尽可能优雅且高效地完成它。

我有一种感觉，这应该不会太难，但作为这个庞大框架的新手，我发现自己在文档/源代码中试图解决这个问题。

有人对什么是最好的方法有建议吗？图形实例？

谢谢!

Answer 1

从你的例子来看，我认为你的问题是你想要构造一个具有边 a -> b 的图，前提是原始图中有一个顶点 v 和边 v -> a 和 v -> b. (这可能是也可能不是有向图中“二级邻居”的标准定义，但无论如何都很有趣。)

这是 Scala 中的解决方案。它生成一个包含所有原始顶点但仅包含所需边的图。我将空字符串作为所有顶点和边上的数据。

假设 SparkContext sc 与您通常在 Spark shell 中获得的一样，并且 GraphX 可用，请设置示例图:

val vertices: RDD[(VertexId, String)] =
    sc.parallelize(Array((1L,""), (2L,""), (4L,""), (6L,"")))

val edges: RDD[Edge[String]] =
    sc.parallelize(Array(Edge(1L, 2L, ""), Edge(1L, 4L, ""), Edge(1L, 6L, "")))

val inputGraph = Graph(vertices, edges)

创建一组备用顶点，每个顶点都用其后继集合进行注释，因此，在您的示例中，v1 将用 {v2, v4, v6} 进行注释。

val verticesWithSuccessors: VertexRDD[Array[VertexId]] = 
    inputGraph.ops.collectNeighborIds(EdgeDirection.Out)

使用这些顶点和原始边创建一个新图。

val successorSetGraph = Graph(verticesWithSuccessors, edges)

现在我们需要沿着每条边插入这些集合，创建另一组顶点，这次所有顶点都用它们的邻居进行注释。我们需要组合目标顶点处的集合，因此使用 Scala Set 可以删除重复项。我们还需要从其邻居集合中删除每个顶点，因此在末尾添加了额外的map。

val ngVertices: VertexRDD[Set[VertexId]] =  
    successorSetGraph.mapReduceTriplets[Set[VertexId]] (
        triplet => {
            Iterator((triplet.dstId, triplet.srcAttr.toSet))
        },
        (s1, s2) => s1 ++ s2
    ).mapValues[Set[VertexId]](
        (id: VertexId, neighbors: Set[VertexId]) => neighbors - id
    )

现在我们几乎准备好创建最终的图，但我们需要每个邻居关系的边:

val ngEdges = ngVertices.flatMap[Edge[String]](
  {
    case (source: VertexId, allDests: Set[VertexId]) => {
      allDests.map((dest: VertexId) => Edge(source, dest, ""))
    }
  }
)

现在我们可以把它们放在一起:

val neighborGraph = Graph(vertices, ngEdges)

我确信专家可以做得更好，尤其是在性能方面，但是它所依赖的大多数想法都可以在 GraphX Programming Guide 中找到。 。