Spark内置算法：Connected Components算法解析及案例和Triangle Counting算法解析及案例
发布时间
阅读量：
阅读量
1.Connected Components
含义：连通分量算法用图的最低编号顶点的ID标记图的每个连通分量。例如，在社交网络中，连接的组件可以近似于群集。
案例：
package sparkGraphX
import org.apache.spark.graphx.{GraphLoader, VertexId, VertexRDD}
import org.apache.spark.{SparkConf, SparkContext}
object connectionTest {
def main(args: Array[String]): Unit = {
val conf = new SparkConf().setAppName("SimpleGraphX").setMaster("local")
val sc = new SparkContext(conf)
sc.setLogLevel("WARN")
// Load the graph as in the PageRank example
val graph = GraphLoader.edgeListFile(sc, "D:/testData/vertices.txt")
// Find the connected components
val cc: VertexRDD[VertexId] = graph.connectedComponents().vertices
cc.collect.foreach(println(_))
//下面的代码就是将顶点的名称与编号建立对应关系，最后将顶点名称与值打印出来。
val users = sc.textFile("D:/testData/user.txt").map { line =>
val fields = line.split(",")
(fields(0).toLong, fields(1))
}
val ccByUsername = users.join(cc).map {
case (id, (username, cc)) => (username, cc)
}
// Print the result
println(ccByUsername.collect().mkString("\n"))
}
}结果： 顶点图：
解析：Connected Components算法可以找出孤立的点。从结果可知，图分为两部分。1,4,8,2一组。6,3,7一组。
2.Triangle Counting
含义：当一个顶点有两个相邻的顶点之间有一条边时，它就是三角形的一部分。GraphX在TriangleCount对象中实现了一个三角形计数算法，该算法确定通过每个顶点的三角形数，从而提供了聚类的度量。注意，三角形计数要求边处于规范方向（srcId<dstId），并使用graph.partitionBy对图形进行分区。
案例：
package sparkGraphX
import org.apache.spark.graphx.{GraphLoader, PartitionStrategy}
import org.apache.spark.{SparkConf, SparkContext}
object TriangleCounting {
def main(args: Array[String]): Unit = {
val conf = new SparkConf().setAppName("SimpleGraphX").setMaster("local")
val sc = new SparkContext(conf)
sc.setLogLevel("WARN")
// Load the edges in canonical order and partition the graph for triangle count
val graph = GraphLoader.edgeListFile(sc, "D:/testData/vertices.txt", true)
.partitionBy(PartitionStrategy.RandomVertexCut)
// Find the triangle count for each vertex
val triCounts = graph.triangleCount().vertices
triCounts.collect.foreach(println(_))
//下面的代码就是将顶点的名称与编号建立对应关系，最后将顶点名称与值打印出来。
val users = sc.textFile("D:/testData/user.txt").map { line =>
val fields = line.split(",")
(fields(0).toLong, fields(1))
}
val triCountByUsername = users.join(triCounts).map { case (id, (username, tc)) =>
(username, tc)
}
// Print the result
println(triCountByUsername.collect().mkString("\n"))
}
}结果： 顶点图：
结果解析：Triangle Counting算法找出图中的三角形，如图点4，不与其他点构成三角形所以为0，而1,2,8与6,3,7都构成三角形所以值为1 。
全部评论 (0)
还没有任何评论哟~