graph-algorithm - GraphX 或 GraphFrame - 无向加权图中的社区检测

Question

我正在尝试识别大型群体中联系紧密的社区(无向加权图)。或者，识别导致本不相关的子组(社区)连接的​​顶点。

该问题是更广泛的 Databricks 解决方案的一部分，因此 Spark GraphX 和 GraphFrames 是解决它的首选。

正如您从附图中看到的那样，我需要找到顶点“X”作为可以拆分由连接组件算法识别的大连续组的点(val result = g.connectedComponents.run())

强连通分量法(仅适用于有向图)、三角形计数或 LPA 社区检测算法不适用，即使所有权重都相同，例如1.

Picture with point, where should be cut big group ST0

问题“Cut in a Weighted Undirected Connected Graph”中很好地描述了类似的逻辑，但仅作为数学表达式。

感谢任何提示。

// Vertex DataFrame
val v = sqlContext.createDataFrame(List( 
  (1L, "A-1", 1),       // "St-1"
  (2L, "B-1", 1),
  (3L, "C-1", 1),
  (4L, "D-1", 1),

  (5L, "G-2", 1),      // "St-2"
  (6L, "H-2", 1),
  (7L, "I-2", 1),
  (8L, "J-2", 1),  
  (9L, "K-2", 1),

  (10L, "E-3", 1),     // St-3
  (11L, "F-3", 1),
  (12L, "Z-3", 1),

  (13L, "X-0", 1)      // split point
)).toDF("id", "name", "myGrp")

// Edge DataFrame
val e = sqlContext.createDataFrame(List( 
  (1L, 2L, 1),
  (1L, 3L, 1),
  (1L, 4L, 1),
  (1L, 13L, 5),  // critical edge
  (2L, 4L, 1),

  (5L, 6L, 1),
  (5L, 7L, 1),
  (5L, 13L, 7),   // critical edge
  (6L, 9L, 1),    
  (6L, 8L, 1),  
  (7L, 8L, 1),   

  (12L, 10L, 1),
  (12L, 11L, 1),
  (12L, 13L, 9),  // critical edge
  (10L, 11L, 1)
)).toDF("src", "dst", "relationship")

val g = GraphFrame(v, e)

Answer 1

Betweenness centrality 似乎是适合这个问题的算法之一。此方法计算从连接任何其他顶点对的所有最短路径中有多少条最短路径通过每个顶点。

据我所知，GraphFrame 不具有介数中心性，它的最短路径仅提供顶点之间的环数，而没有列出实际路径。使用 bfs (广度优先搜索)方法可以给我们合理的近似值(注意:bfs 也不反射(reflect)距离/边长；它也按指示处理每个图):

• 确保每个顶点在两个方向上都定义为 bfs将图视为无向
• 声明可变结构(例如 ArrayBuffer)pathMembers具有以下字段 [fromId, toId, pathId, vertexId]
• 对于图中的每个顶点 o g.vertices (外环)
  • 对于图中的每个顶点 i g.vertices.filter($"id" < lit(o.id)) (内部循环 - 只查看小于 o.id 的 i.id，因为 shortestPath(o.id, i.id) 在无向图中与 shortestPath(i.id, o.id) 完全相同)
    • 申请val paths = g.bfs.fromExpr("id = " + o.id).toExpr("id = " + i.id).run()
    • 转置paths为每个路径存储路径中的所有顶点并将它们存储在 pathMembers 中
• 计算每个vertexId的时间存在于每个 fromId, toId路径(即 vertexId 计数除以 pathId 每对 fromId, toId 计数)
• 总结每个 vertexId 的计算获得中介中心性度量

架构的顶点“X”将获得最高值。直接连接到“X”的顶点的值将下降。如果大多数由“X”交叉连接的组具有可比较的大小，则差异会更高。

注意:如果您的图太大，则完整的介数中心性算法将非常长，可以随机选择用于最短路径计算的对子集。样本大小是可接受的处理时间和在图的单个分支内选择大多数对的概率之间的折衷。