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

Question

我正在尝试识别大组中的强连接社区(无向加权图(。或者，识别导致不相关的子组(社区(连接的顶点。

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

正如你从所附图片中看到的，我需要找到顶点"X"作为一个点，在这个点上可以通过连接的组件算法(val result=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

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

据我所知，GraphFrame不具有Betweenness中心性，其最短路径只提供了顶点之间的圈数，而没有列出实际路径。使用bfs(广度优先搜索(方法可以给我们提供合理的近似(注意：bfs也不反映距离/边长；它还将每个图视为有向图(：

• 确保每个顶点都在两个方向上定义，以使bfs将图视为无向图
• 用以下字段[fromId, toId, pathId, vertexId]声明可变结构(例如ArrayBuffer(pathMembers
• 对于图g.vertices(外循环(中的每个顶点o
  • 对于图g.vertices.filter($"id" < lit(o.id))中的每个顶点i(内部循环-只查看小于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路径中存在的时间(即每个fromId, toId对的vertexId计数除以pathId计数(
• 将每个vertexId的计算相加，得到介数中心性测度

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

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