scala - 使用 Graphx 在 Apache Spark 中查找团或强连接组件

Question

无向图 G = (V, E) 中的团 C 是顶点 C ⊆ V 的子集，因此每两个不同的顶点都是相邻的。这相当于由 C 导出的 G 的子图是完备的条件。在某些情况下，术语 clique 也可以直接指代子图。

因此，我将 GraphX 与 Apache-Spark 结合使用。我阅读了它的文档指南，它们提供了一种方法来找出图中的连通分量，但不是派系/强连通分量。我怎样才能使用 Scala 做到这一点？谢谢!

编辑:正如评论中所建议的，我在 R 中为完成相同任务而编写的一段代码如下:(将这段代码与 Spark 一起使用的问题是最近发布的 SparkR，通过它我可以将 R 与Spark 在库(例如 igraph)方面的支持有限。因此，我开始使用 GraphX 和 Scala)，我现在需要算法。

library(igraph)
files <- paste0("NP",1:10,".txt") // Files which represent graphs
func.clique <- function(file)
{
    w <- read.table(file)
    g <- graph.edgelist(cbind(as.character(w$V1),as.character(w$V2)))
    plot(g)
    cli <- cliques(g)
    return (cli)
}
cliquevalues <- sapply(files,func.clique)

Answer 1

我们最近使用了 jgrapht，与上面@marios 在评论中提到的相同。有关如何使用它的示例代码，这里的 Vertex 是自定义 Vertex 类，cliques 为您提供图中存在的所有 cliques 的列表:

import org.jgrapht._
import org.jgrapht.graph._
import org.jgrapht.alg._
import scala.collection.JavaConverters._
import Util._
import Constants._
import Implicits._

class CliqueGraph(vertices:List[Vertex],xyEdges:List[(Vertex,Vertex)]){
    val graph = new SimpleGraph[Vertex, DefaultEdge](classOf[DefaultEdge])
    vertices.foreach(v=>graph.addVertex(v))
    xyEdges.foreach{ case(v1,v2) =>
            graphg.addEdge(v1,v2)
    }
    lazy val cliques= {
        val c =  new BronKerboschCliqueFinder(graph)
        val setVertices = c.getAllMaximalCliques().asScala
        setVertices.toList
    }
}

在您的 build.sbt 文件中，您需要导入库:

libraryDependencies += "org.jgrapht" % "jgrapht-dist" % "0.9.0"