Finding clicks or tightly coupled components in Apache Spark using Graphx
The clique, C, in an undirected graph G = (V, E) is a subset of vertices C ⊆ V, so that every two distinct vertices are adjacent. This is equivalent to the termination condition for the subgraph G induced by C. In some cases, the term clique can also directly refer to a subgraph.
So, I am using GraphX with Apache-Spark. I read his documentation guide and they provide the ability to find connected components in the graph, but not clicks / tightly connected components. How can I do this using Scala? Thank!
Edit: As suggested in the comments, the piece of code I wrote in R to accomplish the same task looks like this: (The problem with using this code with Spark is that the recently released SparkR through which I can use R with Spark has limited support in libraries (eg igraph), so I started using GraphX and Scala), for which I now need an algorithm.
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)
source to share
We recently used jgrapht, the same as @marios mentioned in the comment above. Sample code on how to use it, here Vertex is its own Vertex class and Clicks gives you a list of all the clicks present in the graph:
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
}
}
In your build.sbt file, you need to import the library:
libraryDependencies += "org.jgrapht" % "jgrapht-dist" % "0.9.0"
source to share