Алгоритм Лейдена

Алгоритм Лейдена — это алгоритм обнаружения сообществ, разработанный Траагом и др. в Лейденском университете . Он был разработан как модификация Метод Лувена для решения проблем разобщенных сообществ.

Компоненты графа

Прежде чем определить алгоритм Лейдена , будет полезно определить некоторые компоненты графа.

Вершины и ребра

Граф состоит из вершин (узлов) и ребер . Каждое ребро соединено с двумя вершинами, и каждая вершина может быть соединена с нулем или более ребрами. Края обычно представляются прямыми линиями, а узлы представляются кругами или точками. В заданных обозначениях пусть $V$ быть множеством вершин, и $E$ быть набором ребер:

${\begin{aligned}V&:=\{v_{1},v_{2},\dots ,v_{n}\}\\E&:=\{e_{ij},e_{ik},\dots ,e_{kl}\}\end{aligned}}$

где $e_{ij}$ — направленное ребро из вершины $v_{i}$ в вершину $v_{j}$. Мы также можем записать это как упорядоченную пару:

${\begin{aligned}e_{ij}&:=(v_{i},v_{j})\end{aligned}}$

Сообщество

Сообщество — это уникальный набор узлов:

${\begin{aligned}C_{i}&\subseteq V\\C_{i}&\bigcap C_{j}=\emptyset ~\forall ~i\neq j\end{aligned}}$

а объединение всех сообществ должно представлять собой общее множество вершин:

${\begin{aligned}V&=\bigcup _{i=1}C_{i}\end{aligned}}$

Раздел

Раздел — это совокупность всех сообществ:

${\begin{aligned}{\mathcal {P}}&=\{C_{1},C_{2},\dots ,C_{n}\}\end{aligned}}$

Качество

Подобно модульности , функция качества используется для оценки того, насколько хорошо были распределены сообщества. Алгоритм Лейдена использует модель Постоянного Поттса (CPM):

${\begin{aligned}{\mathcal {H}}(G,{\mathcal {P}})&=\sum _{C\in {\mathcal {P}}}|E(C,C)|-\gamma {\binom {||C||}{2}}\end{aligned}}$

Алгоритм

Алгоритм Лейдена начинается с одноэлементного разделения (a) . Алгоритм перемещает отдельные узлы из одного сообщества в другое, чтобы найти раздел (b) , который затем уточняется (c) . Агрегатная сеть (d) создается на основе уточненного раздела с использованием неуточненного раздела для создания начального раздела для совокупной сети. Например, красное сообщество в (b) разбивается на два подсообщества в (c) , которые после агрегирования становятся двумя отдельными узлами в (d) , оба принадлежащими одному и тому же сообществу. Затем алгоритм перемещает отдельные узлы в совокупной сети (e) . В этом случае уточнение не меняет разбиение (f) . Эти шаги повторяются до тех пор, пока дальнейшие улучшения не станут возможными.

Алгоритм Лейдена аналогичен алгоритму метода Лувена с некоторыми важными модификациями.

Шаг 1: Во-первых, каждый узел сети назначается своему сообществу.

Шаг 2. Далее мы решаем, в какие сообщества переместить узлы, и обновляем раздел. ${\mathcal {P}}$.

queue = V(G) # create a queue from the nodes

while queue != empty:
  node = queue.next() # get the next node
  delta_H = 0
  for C in communities: # compute the change in quality for each community
    if delta_H(node, C) > delta_H:
      delta_H = delta_H(node, C)
      community = C
  if delta_H > 0:
    move node to community
    outside_nodes = { node_i | (node, node_i) are edges and node_i is not in community } # find the nodes which are connected to the node but not in the community
    queue.add(outside_nodes not already in queue)

Шаг 3. Назначьте каждый узел графа своему сообществу в новом разделе под названием ${\mathcal {P}}_{\text{refined}}$.

Шаг 4. Целью этого шага является разделение сообществ с плохими связями:

for C in communities of P:
  # find the nodes in the community which have lots of edges within the community
  well_connected_nodes = { node | node is in C, |E(node, C\node)| >= gamma ||node||(||C|| - ||node||) }
  for node in well_connected_nodes:
    if node is singleton under P_refined:
      well_connected_communities = { C_i | C_i is in P_refined, C_i is a subset of C, |E(C_i, C\C_i)| >= gamma*||C_i||(||C|| - ||C_i||)
      for C_i in well_connected_communities:
        compute probability P(C_i) # 0 if assignment of node to C_i decreases quality of P_refined, greater weights for greater quality increases
      assign node to C_i by sampling P(C_i) distribution

Шаг 5. Используйте уточненный раздел ${\mathcal {P}}_{\text{refined}}$ агрегировать график. Каждое сообщество в ${\mathcal {P}}_{\text{refined}}$ становится узлом в новом графе $G_{\text{agg}}$.

Пример : Предположим, что у нас есть:

${\begin{aligned}V&=\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},v_{7}\}\\C_{1}&=\{v_{1},v_{2},v_{3},v_{4}\}\\C_{2}&=\{v_{5},v_{6},v_{7}\}\\{\mathcal {P}}&=\{C_{1},C_{2}\}\\{\mathcal {P}}_{\text{refined}}&=\{C_{1a},C_{1b},C_{2}\}\end{aligned}}$

Тогда наш новый набор узлов будет:

${\begin{aligned}V_{agg}&=\{C_{1a}\mapsto w_{1a},C_{1b}\mapsto w_{1b},C_{2}\mapsto w_{2}\}\end{aligned}}$

Шаг 6. Обновите раздел. ${\mathcal {P}}$ используя агрегированный график. Мы не допускаем разделения сообществ ${\mathcal {P}}$, но сообщества можно разделить на несколько узлов из уточненного раздела ${\mathcal {P}}_{\text{refined}}$:

${\begin{aligned}{\mathcal {P}}&=\{\{v~|~v\subseteq C,v\in V(G_{\text{agg}})\}~|~C\in {\mathcal {P}}\}\end{aligned}}$

Пример : Предположим, что $C$ это плохо связанное сообщество из раздела ${\mathcal {P}}$:

${\begin{aligned}C&=\{v_{1},v_{2},v_{3},v_{4},v_{5}\}\\{\mathcal {P}}&=\{C\}\end{aligned}}$

Затем предположим, что на этапе уточнения он был разделен на два сообщества: $C_{1}$ и $C_{2}$:

${\begin{aligned}C_{1}&=\{v_{1},v_{2},v_{3}\}\\C_{2}&=\{v_{4},v_{5}\}\\{\mathcal {P}}_{\text{refined}}&=\{C_{1},C_{2}\}\end{aligned}}$

Когда мы агрегируем граф, новые узлы будут:

${\begin{aligned}V(G_{\text{agg}})&=\{C_{1},C_{2}\}\end{aligned}}$

но мы сохраним старый раздел:

${\begin{aligned}{\mathcal {P}}&=\{\{C_{1},C_{2}\}\}\end{aligned}}$

Шаг 7. Повторяйте шаги 2–6, пока каждое сообщество не будет состоять только из одного узла.