Spark GraphX实现Bron–Kerbosch算法-极大团问题

首先，说明两个概念：团、极大团。

• 团（clique）是一个无向图（undirected graph ）的子图，该子图中任意两个顶点之间均存在一条边。又叫做完全子图。
• 极大团（maximal clique）是一个团，该团不能被更大的团所包含，换句话说，再也不存在一个点与该团中的任意顶点之间存在一条边。

研究极大团的问题对社区发现等场景有较高的理论价值和现实意义。求一个无向图中的极大团问题是一个经典的NP完全问题，1973年曾提出了一个Bron-Kerbosch算法用来解决该问题，其伪代码如下：

 BronKerbosch(R, P, X):if P and X are both empty:report R as a maximal cliquefor each vertex v in P:BronKerbosch(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))P := P \ {v}X := X ⋃ {v}

该算法中有四个集合：R,P,X,N(v)，其中：

R：目前已经在团中的顶点的集合

P：可能在团中的顶点的集合

X：不被考虑的顶点的集合

N（v）：顶点v的所有直接邻居

以一个6个顶点的图为例：

用Spark GraphX实现Bron Kerbosch算法，搜索该图的极大团，代码如下：

import org.apache.spark.graphx.{Edge, EdgeDirection, Graph, VertexId}
import org.apache.spark.{SparkConf, SparkContext}import scala.collection.mutable
import scala.collection.mutable.Setobject FindMaximalCliques {def main(args: Array[String]): Unit = {val conf = new SparkConf().setAppName("findMaximalCliques").setMaster("local")val sc: SparkContext = new SparkContext(conf)//定义顶点val vertexArray = Array((1L,null),(2L,null),(3L,null),(4L,null),(5L,null),(6L,null))//定义边val edgeArray = Array(Edge(6L, 4L,null),Edge(4L, 3L,null),Edge(4L, 5L,null),Edge(5L, 2L,null),Edge(3L, 2L,null),Edge(5L, 1L,null),Edge(2L, 1L,null))//顶点和边转化为RDDval vertexRDD = sc.parallelize(vertexArray)val edgeRDD  = sc.parallelize(edgeArray)//根据顶点和边创建图val graph= Graph(vertexRDD,edgeRDD)//创建一个Map集合。key是图中的所有顶点；value是一个Set集合，保存了该key的所有邻居顶点val map: Map[VertexId, Set[VertexId]] = graph.collectNeighborIds(EdgeDirection.Either).collect().map(t => {var set: mutable.Set[VertexId] = Set[VertexId]()t._2.foreach(t=>{set+=t})(t._1, set)}).toMap//R集合，初始值为空var R = Set[VertexId]()//P集合，初始值为所有的顶点var P = Set[VertexId]()//将所有的顶点添加到P集合中vertexRDD.collect().foreach(t=>{P+=t._1})//X集合，初始值为空var X = Set[VertexId]()//搜索极大团bronKerboschl(R,P,X,map)}/*** 搜索极大团的方法* @param R 目前已经在团中的顶点的集合* @param P 可能在团中的顶点的集合* @param X 不被考虑的顶点的集合* @param map Map集合，通过顶点获取该顶点的所有邻居顶点集合*/def bronKerboschl(R:Set[VertexId],P:Set[VertexId],X:Set[VertexId],map:Map[VertexId, Set[VertexId]]): Unit ={if(P.toList.length ==0 && X.toList.length ==0){println("find a maximal cilique:"+R)}else {for (v <- P) {var Nv: Set[VertexId] = map.get(v).getbronKerboschl(R+v, P.intersect(Nv), X.intersect(Nv), map)X += vP -= v}}}}

find a maximal cilique:Set(1, 5, 2)
find a maximal cilique:Set(5, 4)
find a maximal cilique:Set(2, 3)
find a maximal cilique:Set(6, 4)
find a maximal cilique:Set(3, 4)