Важный алгоритм обнаружения сообщества для графов и сетей
Просматривая мою серию блогов Graph Analytics, я прочитал об алгоритме Лувена и почувствовал, что он заслуживает отдельного обсуждения (из-за его сложности и ограниченности ресурсов в Интернете), поэтому в этом посте обсуждается, как рассчитывается модульность для графика и как работает алгоритм Лувена.
Найдите видеоблог-версию этого поста ниже
Алгоритм Лувена, самый популярный в мире алгоритм обнаружения сообществ, основан на идее плотности графа (компонента), то есть чего-то, что связано с частотой ребер/соединений внутри компонента по сравнению с другими компонентами того же графа. Узел добавляется в сообщество, если он увеличивает его плотность, в противном случае нет. Мы называем этот термин, тесно связанный с плотностью, модульностью.
Как рассчитывается эта модульность?
там очень сложная формула
Q = 1/(2m) * Σᵢⱼ ([ Aᵢⱼ — kᵢkⱼ / (2m)] * δ(cᵢ, cⱼ))
Приведенная выше формула требует некоторого пояснения.
Q= Модульность
m = веса всех ребер в графе (если граф невзвешенный, количество ребер во всем графе)
Сумма имеет 3 члена
Aᵢⱼ = вес ребра между узлом «i» и узлом «j», если взвешенный граф иначе 1, если ребро между узлами i и j существует, иначе 0 (в случае невзвешенного графа)
Kᵢ - степень (общее количество связей) некоторой вершины i.
δ(cᵢ, cⱼ) = 1, если и узел i, и узел j находятся в одном сообществе, иначе 0
Таким образом, вышеуказанный член суммирования равен 0, если i и j принадлежат к разным сообществам.
Я думаю, пример был бы лучше !!
Предполагая приведенный выше график, давайте разберемся с формулой модульности, используя его.
Модульность =
1/2m x [(A₁₁ — k₁k₁/2m) x δ(c₁,c₁)+(A₁₂ — k₁k₂/2m) x δ(c₁,c₂) + (A₁₃ — k₁k₃/2m) x δ(c₁,c₃) + (A₁₄ — k₁k₄/2m) x δ(c₁,c₄) + (A₁₅ — k₁k₅/2m) x δ(c₁,c₅) +
(A₂₁ — k₂k₁/2m) x δ(c₂,c₁) + (A₂₂ — k₂k₂/2m) x δ(c₂,c₂)+ ……
(A₅₄ — k₅k₄/2m) x δ(c₅,c₄)+ (A₅₅ — k₅k₅/2m) x δ(c₅,c₅) ]
Вкладываем в него значения
= 1/2*5 x [ (0–2*2/2*5) x 1 + (1–2*2/2*5)x 0 + (1–2*2/2*5)x0 + (0–2*2/2*5) x 0 + (0–2*2/2*5) x 0+
((1–2*2/2*5)x 0) + (0–2*2/2*5) x 1 ……
((1–2*2/2*5)x 0) + (0–2*2/2*5) x 1]
Мы предоставим расчет вам!
Но давайте обсудим, как значения были помещены в уравнение
- m = 5 (всего ребер в графе = 5, невзвешенные, поэтому веса не учитываются)
- Для терма (A₁₂ — k₁k₂/2m) x δ(c₁,c₂) мы имеем A₁₂=1, так как между 1 и 2 есть ребро. Поскольку степень каждого узла в графе одинакова (2 ребра для каждого узел), член k₁k₂/2m остается постоянным для каждого члена суммирования. δ(c₁,c₂) равно 0, поскольку изначально 2 узла не принадлежат одному и тому же сообществу, поэтому весь член суммирования становится равным 0!
- Для терма (A₁₁ — k₁k₁/2m) x δ(c₁,c₁) A₁₁=0, так как для узла 1 нет собственного ребра к самому себе. На самом деле все Aᵢᵢ = 0, так как в этом графе нет собственного ребра. δ(c₁,c1)=1, так как каждый узел будет принадлежать своему сообществу.
Несколько замечаний
- δ(c₁,c2) будет равно 1 для каждого вычисления пары собственных узлов (такие случаи, как i — i,
j - j), в то время как Aᵢⱼ будет равно 0 в таких терминах, если не существует собственного края
- Член суммирования включает все возможные пары узлов, включая собственные узлы (i — i). Следовательно, если граф имеет 5 узлов, у нас будет 25 членов суммирования.
Мы все?
Не совсем, так как речь шла как раз о том, как рассчитывается модульность, с Лувена мы еще не начинали!!
Итак, алгоритм Лувена включает следующие шаги:
- Сначала назначьте каждому узлу уникальное сообщество, чтобы общее количество узлов было равно общему количеству уникальных сообществ.
- Теперь итеративно мы попробуем присвоить каждый узел «i» его соседнему узлу «j» сообщества и пересчитать модульность графа. Если модульность улучшится по сравнению с тем, когда узел «i» не был в сообществе узла «j», мы назначим «i» сообществу так же, как «j», иначе нет. Помните, j сосед i
- Это будет повторяться для нескольких итераций до тех пор, пока не будет наблюдаться дальнейший выигрыш в модульности за счет перемещения любого узла в сообщество его соседа, и мы не достигнем максимума для модульности (возможно, локальные максимумы, но хорошо)
- После этого мы создаем новый граф, такой, что
- Все узлы в соответствующих сообществах объединены в единый узел.
- Все ребра, соединяющие узлы сообщества 1 с узлами сообщества 2 в предыдущей итерации, объединяются, чтобы сформировать единое ребро между сообществом 1 и сообществом 2, и вес ребра для этого нового ребра равен:
- Суммирование весов всех ребер между узлами сообщества 1 и узлами сообщества 2 в случае ориентированного графа
- Количество ребер в случае невзвешенного графа
3. Собственные ребра (типа i — i) становятся саморебрами для соответствующих им сообществ с суммированием весов всех таких саморебер для узлов некоторого сообщества '1' в виде веса собственного ребра для конкретного сообщества или количества всех саморебер. ребер в случае невзвешенного графа.
Мы снова возвращаемся к предыдущей итерации, где мы вычисляем модульность для каждого узла этого нового графа, перемещая узлы в то же сообщество, что и сообщество соседнего узла. Если модульность увеличивается, этот узел назначается сообществу соседа, как и раньше, иначе нет, и этот процесс
Рассчитайте модульность и назначьте сообщество узлам
Формирование нового графа в зависимости от сформированных сообществ
Продолжается до тех пор, пока не перестанут наблюдаться дальнейшие изменения в сообществах. Финальные сообщества - это интересующие нас сообщества!!
Приведенный ниже пример из реальной исследовательской работы может помочь
Рассмотрим приведенный выше график
- Мы начали с отдельных сообществ для каждого узла (изображение 1, левый угол).
- После перебора узлов и вычисления модульности путем изменения сообществ для узлов мы, наконец, получили 4 сообщества (красное, синее, небесно-голубое и зеленое), изображение 2.
- В новом сформированном графе у нас теперь есть 4 узла (представляющие 4 найденных сообщества) с весами ребер в качестве агрегации, описанной выше.
- Снова весь цикл поиска сообществ с использованием модульности начинается на этом новом графике, где мы можем объединить эти 4 сообщества в 2 (последнее изображение справа)
- Поскольку больше сообществ не найдено, мы получаем 2 сообщества.
