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

Question

我试图识别大群中的强连通社区(无向加权图)。或者，识别导致子组(社区)连接的顶点，这些子组(社区)本来是不相关的。

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

从附图中可以看到，我需要找到顶点"X“作为一个点，在这个点上可以用连通的组件算法来划分大的连续组(val = g.connectedComponents.run())

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

图与点，应在哪里剪大组ST0

类似的逻辑在有疑问的"加权无向连通图的割集“中描述得很好，但它只是一个数学表达式。

谢谢你的暗示。

// 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

中间中心性似乎是适合这个问题的算法之一。该方法计算连接任意一对其他顶点的所有最短路径中每个顶点的最短路径数。

据我所知，GraphFrame确实是而不是，它介于中心性和最短路径之间，只是提供了点w/o之间的圈数，列出了实际路径。使用bfs (广度优先搜索)方法可以给出合理的近似(注意：bfs也不反映距离/边缘长度；它还将每个图作为有向图处理)：

• 确保在两个方向上定义每个顶点，使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计数除以每个fromId, toId对的pathId计数)
• 总结各vertexId的计算求取中间度中心度测度

模式的顶点"X“将得到最高值。直接连接到"X“的顶点的值将下降。如果大多数由"X“交叉连接的组具有可比较的大小，则差异将很大。

注意:如果你的图是这么大，那么完整的中间中心性算法就会长得让人望而却步，可以随机选择用于最短路径计算的子集。样本大小是在可接受的处理时间和概率之间的折衷，在图的单个分支中选择大多数对。