GraphX or GraphFrame - community detection in undirected weighted graph

user_13492568 0
Viewed 1463

I'm trying to identify strongly connected communities within large group (undirected weighted graph). Alternatively, identifying vertices causing connection of sub-groups (communities) that would be otherwise unrelated.

The problem is part of broader Databricks solution thus Spark GraphX and GraphFrames are the first choice for resolving it.

As you can see from attached picture, I need to find vertex "X" as a point where can be split big continuous group identified by connected componect algorithms (val result = g.connectedComponents.run())

Strongly connected components method (for directed graph only), Triangle counting, or LPA community detection algorithms are not suitable, even if all weights are same, e.g. 1.

Picture with point, where should be cut big group ST0

Similar logic is nice described in question "Cut in a Weighted Undirected Connected Graph", but as a mathematical expression only.

Thanks for any hint.

// 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)
spark-graphx graphframes graph-algorithm
1 Answers

Betweenness centrality seems to be one of the algorithms fitting this problem. This method counts how many shortest paths are going thru each vertex from all shortest paths connecting any pair of other vertices.

As far as I know, GraphFrame does not have Betweenness centrality and its Shortest Path just provides number of hoops between vertices w/o listing the actual path. Using bfs (Breadth First Search) method can give us reasonable approximation (note: bfs doesn't reflect distance/edge length neither; it also treats each graph as directed):

  • Ensure each vertex is defined in both directions to make bfs treating graph as undirected
  • Declare mutable structure (e.g. ArrayBuffer) pathMembers with following fields [fromId, toId, pathId, vertexId]
  • For each vertex o in your graph g.vertices (outer loop)
    • For each vertex i in your graph g.vertices.filter($"id" < lit(o.id)) (inner loop - looks only into i.id smaller than o.id, because shortestPath(o.id, i.id) is exaclty same as shortestPath(i.id, o.id) in undirected graph)
      • apply val paths = g.bfs.fromExpr("id = " + o.id).toExpr("id = " + i.id).run()
      • transpose paths to store all vertices in the path for each path and store them in pathMembers
  • Calculate how many time was each vertexId present in each fromId, toId path (i.e. vertexId count divided by pathId count for each fromId, toId pair)
  • Sum-up the calculation for each vertexId to obtain betweenness centrality measure

Vertex "X" for the schema will get highest value. Value for vertices directly connected to "X" will drop. Difference will be highes if most of the groups cross-connected by "X" have comparable size.

Note: if your graph is so large the full Betweenness centrality algorithm will be prohibitively long, sub-set of pairs for shortest path calculation could be selected randomly. Sample size is compromise between acceptable processing time and probability choosing majority of pairs within single branch of the graph.

user_68066530
Related