LPA

run API

• API

  run[VD, ED: ClassTag](graph: Graph[VD, ED], maxSteps: Int): Graph[VertexId, ED]

• 功能描述

  计算图网络中每个节点所属社区。该算法接口与开源GraphX中LabelPropagation算法保持一致。

• API描述
  1. 包名：package org.apache.spark.graphx.lib.LabelPropagation
  2. 类名：LabelPropagation
  3. 方法名：run
  4. 输入：
     1. graph: Graph[VD,ED]
     2. maxSteps: Int
  5. 参数详情：

     参数名称	参数含义	取值类型	备注
     graph	从文件读入后的Graph数据	Graph[VD,ED]	VD表示定点属性开源接口中用于占位，非泛型； ED表示边属性，为泛型。
     maxSteps	算法的迭代次数（通常设为10次）	Int	maxSte ps必须大于0

     使用lpa算法内置runConvergence分支，该分支在震荡图模型上可保证收敛，用户可以通过Spark参数的传入进行调用，当spark.sophon.graph.lpa.convergence设置为true时，算法将会调用到该分支（算法内部默认该参数为false，当不传入该参数或设置该参数为false时，按maxSteps迭代进行）。

     举例如下：

     --conf "spark.sophon.graph.lpa.convergence=true"

     spark.sophon.graph.lpa.PreIter为算法runConvergence分支内置参数，用户可以通过Spark参数的传入进行调用，此参数为设置lpa算法的预迭代次数。原则上，对于震荡图预迭代次数越大，lpa初始迭代越充分，算法后续流程更容易收敛，但是过多的预迭代次数会对性能有一定影响。绝大多数场景我们建议使用算法内部默认值：20，既满足迭代的充分，又兼顾的整体性能（数据集非常大，可以适当调大）。

     使用如下：

     --conf "spark.sophon.graph.lpa.PreIter=20"

  6. 输出：result: Graph[VertexId,ED]

     返回值名称	返回值含义	返回值类型	备注
     Graph[VertexId, ED]	返回图结构数据	Graph[VertexId, ED]	划分到相同社区的定点属性会用类型Long的同一个整数进行标记。即为社区编码，该编号取值不保证连续。

• 使用样例

  LabelPropagation样例：

  val edgesRDD = sc.parallelize(Array((1, 2), (2,3),(3,4),(4,1),(2,4),(1,3),(4,9),(9,7),(5,7),(5,8),(8,6),(6,7),(7,8),(5,6)))
  val iterNum = 10
  val graph = Graph.fromEdgeTuples(edgesRDD.map(f=>(f._1.toLong, f._2.toLong)), 0)
  val nodesInfo = LabelPropagation.run(graph, iterNum).vertices.sortByKey().collect().foreach(println)

• 样例结果
  

  • 第一列为节点ID，第二列为该节点对应社区。
  • 因为LPA算法属于启发式算法，所以开源结果与自研算法结果往往会有不一致的情况。通常，我们是通过计算模块度的大小来判断自研算法与开源算法的准确度以及社区划分的效果。

  1,1
  2,1
  3,1
  4,1
  5,5
  6,5
  7,5
  8,5
  9,5