Я пытаюсь определить сильно связанные сообщества внутри большой группы (неориентированный взвешенный граф). В качестве альтернативы, определение вершин, вызывающих соединение подгрупп (сообществ), которые в противном случае не были бы связаны.
Проблема является частью более широкого решения Databricks, поэтому Spark GraphX и GraphFrames являются первым выбором для ее решения.
Как вы можете видеть из прикрепленного рисунка, мне нужно найти вершину «X» как точку, где можно разделить большую непрерывную группу, идентифицированную подключенными алгоритмами componect (val result = g.connectedComponents.run ())
Метод сильно связанных компонентов (только для ориентированного графа), подсчет треугольников или алгоритмы определения сообщества LPA не подходят, даже если все веса одинаковы, например 1.
Картинка с точкой, где должна быть вырезать большую группу ST0
Подобное logi c хорошо описано в вопросе « Вырезать взвешенный неориентированный связанный граф », но только как математическое выражение.
Спасибо за подсказку.
// 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)