GraphX ​​или GraphFrame - обнаружение сообщества в неориентированном взвешенном графе

Я пытаюсь определить сильно связанные сообщества внутри большой группы (неориентированный взвешенный граф). В качестве альтернативы, определение вершин, вызывающих соединение подгрупп (сообществ), которые в противном случае не были бы связаны.

Проблема является частью более широкого решения Databricks, поэтому Spark GraphX ​​и GraphFrames являются первым выбором для ее решения.

Как видно из прикрепленного рисунка, мне нужно найти вершину «X» как точку, где можно разделить большую непрерывную группу, идентифицированную связанными алгоритмами componect (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)

spark-graphx graphframes graph-algorithm
person Palo    schedule 07.05.2020    source источник
comment
Интересный вопрос! Не могли бы вы пояснить, почему алгоритмы подсчета треугольников или алгоритмы определения сообщества LPA не подходят? Из эскиза, который вы прикрепили, треугольник или количество петель поможет, не так ли?   -  person JanLauGe    schedule 29.05.2020
comment
@JanLauGe, вы правы, подсчет треугольников сузит варианты. Для X будет 0 треугольников. Однако вы также получите 0 для C и K. А теперь представьте, что к C или K будут подключены дополнительные узлы. Видите ли вы, как в таком случае использовать счетчик треугольников?   -  person Dan    schedule 19.06.2020
comment
В примере K и C - терминальные вершины. Если это намеренно, а не просто совпадение, мы могли бы вырезать только ребра нетерминальных узлов без треугольников. Однако, как вы правильно заметили, если есть дополнительные узлы, подключенные к C и K, это больше не сокращает (посмотрите, что я там сделал?) ... В зависимости от фактических данных, возможно, отношение количества треугольников к градусам центральности может быть полезно?   -  person JanLauGe    schedule 16.07.2020
comment
@JanLauGe Хороший вопрос! Отсутствие треугольника на нетерминальном узле указывает на подозрительные вершины. Может быть некоторый риск для кластеров с отсутствующими узлами (например, если бы не было ребра B - D, A был бы помечен точно так же, как X). Это означает, что потребуется какой-то дополнительный метод, но ваша идея помогает!   -  person Dan    schedule 22.07.2020
comment
@Palo вы когда-нибудь писали этот код? Я хотел бы иметь возможность ссылаться на него, если вы не возражаете опубликовать результат? Спасибо!   -  person John Smith    schedule 08.07.2021

Ответы (1)


arrow_upward
1
arrow_downward

Центральность промежуточности, по-видимому, является одним из подходящих для этого алгоритмов. проблема. Этот метод подсчитывает, сколько кратчайших путей проходит через каждую вершину из всех кратчайших путей, соединяющих любую пару других вершин.

Насколько мне известно, GraphFrame не имеет центральности по промежуточности, а его кратчайший путь просто предоставляет количество обручей между вершинами без перечисления фактического пути. Использование метода bfs (поиск в ширину) может дать нам разумное приближение (примечание: bfs также не отражает расстояние / длину ребра; он также обрабатывает каждый граф как направленный):

  • Убедитесь, что каждая вершина определена в обоих направлениях, чтобы bfs граф считался неориентированным.
  • Объявите изменяемую структуру (например, ArrayBuffer) pathMembers со следующими полями [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()
      • транспонировать paths, чтобы сохранить все вершины в пути для каждого пути и сохранить их в pathMembers
  • Подсчитайте, сколько раз каждый vertexId присутствовал на каждом fromId, toId пути (т. Е. vertexId счет, деленный на pathId счет для каждой fromId, toId пары)
  • Просуммируйте вычисления для каждого vertexId, чтобы получить меру центральности промежуточности.

Вершина «X» для схемы получит наивысшее значение. Значение для вершин, напрямую связанных с "X", упадет. Разница будет больше, если большинство групп, соединенных крестиком «X», имеют сопоставимый размер.

Примечание: если ваш график настолько велик, то алгоритм полной центральности между посредничеством будет слишком длинным, подмножество пар для вычисления кратчайшего пути может быть выбрано случайным образом. Размер выборки - это компромисс между приемлемым временем обработки и вероятностью выбора большинства пар в пределах одной ветви графика.

person Dan    schedule 19.06.2020