spark graphx:如何遍历图形以创建二度邻居的图形

Question

我是初学者,有火花/ 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的解决方案.它生成一个包含所有原始顶点但只包含所需边缘的图形.我将空字符串作为数据放在所有顶点和边上.

假设您通常在Spark shell中使用SparkContext sc,并且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编程指南中找到.