Поиск кликов или сильно связанных компонентов в Apache Spark с использованием Graphx

Question

Клика C в неориентированном графе G = (V, E) является подмножеством вершин C ⊆ V, так что каждые две различные вершины смежны. Это эквивалентно условию, что подграф G, индуцированный C, является полным. В некоторых случаях термин клика может также относиться к подграфу напрямую.

Итак, я использую 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, а клики дают вам список всех клик, присутствующих на графике:

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"