Algoritmo de Leiden

El algoritmo de Leiden es un algoritmo de detección de comunidades desarrollado por Traag et al . ^{[ 1 ]} en la Universidad de Leiden . Fue desarrollado como una modificación del método de Louvain . Al igual que el método de Louvain, el algoritmo de Leiden intenta optimizar la modularidad en la extracción de comunidades de redes; sin embargo, aborda problemas clave presentes en el método de Louvain, a saber, las comunidades poco conectadas y el límite de resolución de la modularidad .

Mejora respecto al método de Lovaina

En términos generales, el algoritmo de Leiden utiliza las mismas dos fases principales que el algoritmo de Louvain: un paso de movimiento de nodos locales (aunque el método para considerar los nodos en Leiden es más eficiente ^{[ 1 ]} ) y un paso de agregación de grafos. Sin embargo, para abordar los problemas de las comunidades poco conectadas y la fusión de comunidades más pequeñas en comunidades más grandes (el límite de resolución de la modularidad), el algoritmo de Leiden emplea una fase de refinamiento intermedia en la que las comunidades pueden dividirse para garantizar que todas estén bien conectadas.

Consideremos, por ejemplo, el siguiente gráfico:

En este gráfico se muestran tres comunidades (cada color representa una comunidad). Además, el nodo central "puente" (representado con un círculo adicional) pertenece a la comunidad representada por los nodos azules. Ahora consideremos el resultado de un paso de movimiento de nodos que fusiona las comunidades representadas por los nodos rojos y verdes en una sola comunidad (ya que ambas comunidades están altamente conectadas):

Cabe destacar que, tras el movimiento de nodos (debido a la naturaleza voraz del algoritmo de movimiento de nodos locales), el nodo central que actúa como "puente" pasa a formar parte de la comunidad roja, que es más grande. En el método de Louvain, esta fusión iría seguida inmediatamente de la fase de agregación del grafo. Sin embargo, esto provoca una desconexión entre dos secciones diferentes de la comunidad representadas por nodos azules. En el algoritmo de Leiden, en cambio, el grafo se refina:

El paso de refinamiento del algoritmo de Leiden garantiza que el nodo "puente" central se mantenga en la comunidad azul para asegurar que permanezca intacto y conectado, a pesar de la posible mejora en la modularidad que supondría añadir el nodo "puente" central a la comunidad roja.

Componentes gráficos

Antes de definir el algoritmo de Leiden , será útil definir algunos de los componentes de un grafo.

Vértices y aristas

Un grafo se compone de vértices (nodos) y aristas . Cada arista está conectada a dos vértices, y cada vértice puede estar conectado a cero o más aristas. Las aristas se representan típicamente mediante líneas rectas, mientras que los nodos se representan mediante círculos o puntos. En notación de conjuntos, sea $V$ sea el conjunto de vértices, y $E$ sea el conjunto de aristas:

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

dónde $e_{ij}$ es la arista dirigida desde el vértice $v_{i}$ al vértice $v_{j}$ También podemos escribir esto como un par ordenado:

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

Comunidad

Una comunidad es un conjunto único de nodos:

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

y la unión de todas las comunidades debe ser el conjunto total de vértices:

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

Dividir

Una partición es el conjunto de todas las comunidades:

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

Calidad de partición

La división de las comunidades es un aspecto fundamental del algoritmo de Leiden. La forma en que se deciden las particiones puede depender de cómo se mide su calidad. Además, muchas de estas métricas contienen parámetros propios que pueden modificar el resultado de las comunidades.

Modularidad

La modularidad es una métrica de calidad muy utilizada para evaluar qué tan bien un conjunto de comunidades particiona un grafo. La ecuación para esta métrica se define para una matriz de adyacencia, A, como: ^{[ 2 ]}

$Q={\frac {1}{2m}}\sum _{ij}(A_{ij}-{\frac {k_{i}k_{j}}{2m}})\delta (c_{i},c_{j})$

dónde:

$A_{ij}$ representa el peso de la arista entre nodos $i$ y $j$ ; ver matriz de adyacencia ;
$k_{i}$ y $k_{j}$ son la suma de los pesos de las aristas conectadas a los nodos $i$ y $j$ , respectivamente;
$m$ es la suma de todos los pesos de las aristas en el grafo;
$c_{i}$ y $c_{j}$ son las comunidades a las que los nodos $i$ y $j$ pertenecer; y
$\delta$ es la función delta de Kronecker :

${\begin{aligned}\delta (c_{i},c_{j})&={\begin{cases}1&{\text{si }}c_{i}{\text{ y }}c_{j}{\text{ son la misma comunidad}}\\0&{\text{en otro caso}}\end{cases}}\end{aligned}}$

Modelo Reichardt Bornholdt Potts (RB)

Una de las métricas más utilizadas para el algoritmo de Leiden es el modelo Reichardt-Bornholdt-Potts (RB). ^{[ 3 ]} Este modelo se utiliza por defecto en la mayoría de las bibliotecas principales del algoritmo de Leiden con el nombre RBConfigurationVertexPartition . ^{[ 4 ]}^{[ 5 ]} Este modelo introduce un parámetro de resolución. $\gamma$ y es muy similar a la ecuación de modularidad. Este modelo se define mediante la siguiente función de calidad para una matriz de adyacencia, A, como: ^{[ 4 ]}

$Q=\sum _{ij}(A_{ij}-\gamma {\frac {k_{i}k_{j}}{2m}})\delta (c_{i},c_{j})$

dónde:

$\gamma$ representa un parámetro de resolución lineal

Modelo de Potts Constante (CPM)

Otra métrica similar a RB es el Modelo de Potts Constante (CPM). Esta métrica también se basa en un parámetro de resolución. $\gamma$ ^{[ 6 ]} La función de calidad se define como:

$H=-\sum _{ij}(A_{ij}w_{ij}-\gamma )\delta (c_{i},c_{j})$

Comprensión de los parámetros de resolución/límite de resolución del modelo de Potts

Normalmente, los modelos de Potts, como RB o CPM, incluyen un parámetro de resolución en su cálculo. ^{[ 3 ]}^{[ 6 ]} Los modelos de Potts se introducen como respuesta al problema del límite de resolución que se presenta en la detección de comunidades basada en la maximización de la modularidad. El problema del límite de resolución es que, para algunos grafos, maximizar la modularidad puede hacer que las subestructuras de un grafo se fusionen y se conviertan en una sola comunidad y, por lo tanto, se pierden las estructuras más pequeñas. ^{[ 7 ]} Estos parámetros de resolución permiten modificar los métodos adyacentes a la modularidad para adaptarlos a los requisitos del usuario que aplica el algoritmo de Leiden para tener en cuenta las subestructuras pequeñas a una cierta granularidad.

La figura de la derecha ilustra por qué la resolución puede ser un parámetro útil al usar métricas de calidad basadas en la modularidad. En el primer gráfico, la modularidad solo captura las estructuras a gran escala del gráfico; sin embargo, en el segundo ejemplo, una métrica de calidad más granular podría detectar potencialmente todas las subestructuras de un gráfico.

Algoritmo

El algoritmo de Leiden comienza con un grafo de nodos desorganizados (a) y lo ordena particionándolos para maximizar la modularidad (la diferencia de calidad entre la partición generada y una partición aleatoria hipotética de comunidades). El método que utiliza es similar al algoritmo de Louvain, excepto que después de mover cada nodo también considera los vecinos de ese nodo que no están ya en la comunidad en la que fue colocado. Este proceso da como resultado nuestra primera partición (b) , también denominada ${\mathcal {P}}$ Luego, el algoritmo refina esta partición colocando primero cada nodo en su propia comunidad individual y luego moviéndolos de una comunidad a otra para maximizar la modularidad. Hace esto iterativamente hasta que cada nodo ha sido visitado y movido, y cada comunidad ha sido refinada; esto crea la partición (c) , que es la partición inicial de ${\mathcal {P}}_{\text{refinado}}$ . Luego se crea una red agregada (d) convirtiendo cada comunidad en un nodo. ${\mathcal {P}}_{\text{refinado}}$ se utiliza como base para la red agregada, mientras que ${\mathcal {P}}$ se utiliza para crear su partición inicial. Porque usamos la partición original. ${\mathcal {P}}$ En este paso, debemos conservarlo para poder utilizarlo en iteraciones futuras. Estos pasos, en conjunto, conforman la primera iteración del algoritmo.

En iteraciones posteriores, los nodos de la red agregada (cada uno de los cuales representa una comunidad) se colocan nuevamente en sus propias comunidades individuales y luego se ordenan según la modularidad para formar una nueva red. ${\mathcal {P}}_{\text{refinado}}$ , formando (e) en el gráfico anterior. En el caso representado por el gráfico, los nodos ya estaban ordenados de forma óptima, por lo que no se produjo ningún cambio, lo que dio como resultado la partición (f) . Luego, los nodos de la partición (f) se agregarían nuevamente utilizando el mismo método que antes, con la partición original. ${\mathcal {P}}$ aún se conserva. Esta parte del algoritmo se repite hasta que cada nodo agregado esté en su propia red individual; esto significa que no se pueden realizar más mejoras.

El algoritmo de Leiden consta de tres pasos principales: movimiento local de nodos, refinamiento de la partición y agregación de la red basada en la partición refinada. Todas las funciones de los pasos siguientes se llaman utilizando nuestra función principal Leiden, que se muestra a continuación: El método Fast Louvain fue tomado por los autores de Leiden de "A Simple Acceleration Method for the Louvain Algorithm". ^{[ 8 ]}

función Leiden_community_detection(Grafo G, Partición P) hacer P = fast_louvain_move_nodes(G, P) /* Llama a la función para mover los nodos a las comunidades. (Más detalles en la función a continuación). */ hecho = (|P| == |V(G)|) /* Si el número de particiones en P es igual al número de nodos en G, entonces se establece el indicador done en True para finalizar el bucle do-while, ya que esto significará que cada nodo se ha agregado a su propia comunidad. */ si no se ha hecho P_refinado = obtener_p_refinado(G, P) /* Esta es una parte crucial de lo que diferencia a Leiden de Louvain, ya que este refinamiento de la partición garantiza que solo los nodos que están bien conectados dentro de su comunidad se consideren para ser movidos fuera de la comunidad. (Más detalles en la función refine_partition_subset a continuación). */ G = aggregate_graph(G, P_refined) /* Agrega comunidades en nodos únicos para la siguiente iteración (detalles en la función a continuación). */ P = {{v | v ⊆ C, v ∈ V (G)} | C ∈ P} /* Esta línea básicamente toma nodos de las comunidades en P y los descompone de manera que cada nodo se trate como su propia comunidad unitaria (comunidad compuesta por un solo nodo). */ fin si mientras no esté hecho return flattened(P) /* Devuelve la partición final donde todos los nodos de G están listados en una comunidad cada uno. */ función final

Paso 1: Desplazamiento local de nodos

Primero, movemos los nodos desde ${\mathcal {P}}$ en comunidades vecinas para maximizar la modularidad (la diferencia de calidad entre la partición generada y una partición aleatoria hipotética de comunidades). En la imagen anterior, nuestra colección inicial de nodos sin ordenar está representada por el gráfico de la izquierda, donde el color único de cada nodo representa que aún no pertenece a una comunidad. El gráfico de la derecha es una representación del resultado de este paso, el gráfico ordenado. ${\mathcal {P}}$ ; observe cómo todos los nodos se han movido a una de las tres comunidades, representadas por los colores de los nodos (rojo, azul y verde).

función fast_louvain_move_nodes(Grafo G, Partición P) Q = cola(V(G)) /* Coloca todos los nodos de G en una cola para asegurar que todos sean visitados. */ mientras Q no esté vacío v = Q.pop_front() /* Selecciona el primer nodo de la cola para visitar. */ C_prime = arg maxC∈P∪∅ ∆HP(v → C) /* Establece C_prime como la comunidad en P o el conjunto vacío (sin comunidad) que proporciona el máximo incremento en la función de calidad H cuando el nodo v se mueve a esa comunidad. */ Si ∆HP(v → C_prime) > 0 /* Solo se consideran los nodos en movimiento que resulten en un cambio positivo en la función de calidad. */ v → C_prime /* Mover el nodo v a la comunidad C_prime */ N = {u | (u, v) ∈ E(G), u !∈ C_prime} /* Crea un conjunto N de nodos que son vecinos directos de v pero no pertenecen a la comunidad C_prime. */ Q.add(N - Q) /* Agrega todos los nodos desde N a la cola, a menos que ya estén en Q. */ fin si return P /* Devuelve la partición actualizada. */ función final

Paso 2: Refinamiento de la partición

A continuación, cada nodo de la red se asigna a su propia comunidad individual y luego se mueve de una comunidad a otra para maximizar la modularidad. Esto ocurre de forma iterativa hasta que cada nodo ha sido visitado y movido, y es muy similar a la creación de ${\mathcal {P}}$ excepto que cada comunidad se refina después de que se mueve un nodo. El resultado es nuestra partición inicial para ${\mathcal {P}}_{\text{refinado}}$ , como se muestra a la derecha. Tenga en cuenta que también estamos haciendo un seguimiento de las comunidades de ${\mathcal {P}}$ , que están representados por los fondos de color que se encuentran detrás de los nodos.

función get_p_refined(Grafo G, Partición P) P_refined = get_singleton_partition(G) /* Asigna cada nodo en G a una comunidad singleton (una comunidad por sí misma). */ para C ∈ P P_refinado = subconjunto_partición_refinada(G, P_refinado, C) /* Refinar la partición para cada una de las comunidades en P_refined. */ fin para return P_refined /* Devuelve la partición recién refinada. */ función refine_partition_subset(Grafo G, Partición P, Subconjunto S) R = {v | v ∈ S, E(v, S − v) ≥ γ * grado(v) * (grado(S) − grado(v))} /* Para el nodo v, que pertenece al subconjunto S, se comprueba si E(v, Sv) (las aristas de v conectadas a otros miembros de la comunidad S, excluyendo a v mismo) superan un cierto factor de escala. degree(v) es el grado del nodo v y degree(S) es el grado total de los nodos del subconjunto S. Esta instrucción requiere esencialmente que, si v se elimina del subconjunto, la comunidad permanecerá intacta. */ para v ∈ R if v in singleton_community /* Si el nodo v está en una comunidad singleton, es decir, es el único nodo. */ T = {C | C ∈ P, C ⊆ S, E(C, S − C) ≥ γ * grado(C) · (grado(S) − grado(C)} /* Crea un conjunto T de comunidades donde E(C, S - C) (las aristas entre la comunidad C y el subconjunto S, excluyendo las aristas entre la comunidad C y sí misma) es mayor que el umbral. El umbral aquí es γ * grado(C) · (grado(S) − grado(C). */ Pr(C_prime = C) ~ exp(1/θ ∆HP(v → C) si ∆HP(v → C) ≥ 0 0 en caso contrario para C ∈ T /* Si mover el nodo v a C_prime cambia la función de calidad en la dirección positiva, establece la probabilidad de que la comunidad de v sea exp(1/θ * ∆HP(v → C)); de lo contrario, establécela en 0 para todas las comunidades en T. */ v → C_prime /* Mueve el nodo v a una comunidad C_prime aleatoria con una probabilidad positiva. */ fin si fin para return P /* devolver partición refinada */ función final

Paso 3: Agregación de la red

Luego convertimos cada comunidad en ${\mathcal {P}}_{\text{refinado}}$ en un único nodo. Observe cómo, como se muestra en la imagen anterior, las comunidades de ${\mathcal {P}}$ se utilizan para ordenar estos nodos agregados después de su creación.

función aggregate_graph(Grafo G, Partición P) V = P /* Establecer las comunidades de P como nodos individuales del grafo. */ E = {(C, D) | (u, v) ∈ E(G), u ∈ C ∈ P, v ∈ D ∈ P} /* Si u pertenece al subconjunto C de P, y v pertenece al subconjunto D de P, y u y v comparten una arista en E(G), entonces añadimos una conexión entre C y D en el nuevo grafo. */ return Graph(V, E) /* Devuelve los nodos y aristas del nuevo grafo. */ función final función obtener_partición_singleton(Grafo G) return {{v} | v ∈ V (G)} /* Esta es la función donde asignamos cada nodo en G a una comunidad unitaria (una comunidad por sí misma). */ función final

Repetimos estos pasos hasta que cada comunidad contenga un solo nodo, y cada uno de estos nodos representa un conjunto de nodos de la red original que están fuertemente conectados entre sí.

Limitaciones

El algoritmo de Leiden realiza un excelente trabajo al crear una partición de calidad que ubica los nodos en comunidades distintas. Sin embargo, Leiden crea una partición rígida, lo que significa que los nodos solo pueden pertenecer a una comunidad. En muchas redes, como las redes sociales, los nodos pueden pertenecer a múltiples comunidades, y en este caso, podrían preferirse otros métodos.

Leiden es más eficiente que Louvain, pero en el caso de grafos masivos puede resultar en tiempos de procesamiento prolongados. Los avances recientes han aumentado la velocidad mediante una "implementación paralela multinúcleo del algoritmo de Leiden". ^{[ 9 ]}

El algoritmo de Leiden contribuye en gran medida a superar el problema del límite de resolución. Sin embargo, aún existe la posibilidad de que se pasen por alto pequeñas subestructuras en ciertos casos. La selección del parámetro gamma es crucial para garantizar que estas estructuras no se omitan, ya que puede variar significativamente de un gráfico a otro.

Referencias

^{[ 3 ]}

^ Traag , Vicente A; Waltman, Ludo; van Eck, Nees Jan (26 de marzo de 2019). "De Lovaina a Leiden: garantizar comunidades bien conectadas" . Informes científicos . 9 (1): 5233. arXiv : 1810.08473 . Código Bib : 2019NatSR...9.5233T . doi : 10.1038/s41598-019-41695-z . PMC 6435756 . PMID 30914743 .
↑ Clauset, Aaron y Newman, MEJ y Moore, Cristopher (2004). "Encontrando la estructura de la comunidad en redes muy grandes". Phys. Rev. E . 70 (6) 066111. arXiv : cond-mat/0408187 . Bibcode : 2004PhRvE..70f6111C . doi : 10.1103/PhysRevE.70.066111 . PMID 15697438 . S2CID 8977721 . {{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
1 2 3 Reichardt, Jörg; Bornholdt, Stefan (2004-11-15). "Detección de estructuras comunitarias difusas en redes complejas con un modelo de Potts" . Physical Review Letters . 93 (21) 218701. arXiv : cond-mat/0402349 . Bibcode : 2004PhRvL..93u8701R . doi : 10.1103/PhysRevLett.93.218701 . ISSN 0031-9007 . PMID 15601068 .
1 2 "Referencia — documentación de leidenalg 0.10.3.dev0+gcb0bc63.d20240122" . leidenalg.readthedocs.io . Consultado el 23-11-2024 .
↑ "Paquete 'leiden'"" (PDF) . 27-07-2021. Archivado del original (PDF) el 08-02-2022.
1 2 Traag, Vincent A; Van Dooren, Paul; Nesterov, Yurii (29 de julio de 2011). "Alcance reducido para la detección de comunidades sin límite de resolución". Physical Review E . 84 (1) 016114. arXiv : 1104.3083 . Bibcode : 2011PhRvE..84a6114T . doi : 10.1103/PhysRevE.84.016114 . PMID 21867264 .
↑ Fortunato, Santo; Barthélemy, Marc (2007-01-02). "Límite de resolución en la detección de comunidades" . Actas de la Academia Nacional de Ciencias . 104 ( 1): 36– 41. arXiv : physics/0607100 . Bibcode : 2007PNAS..104...36F . doi : 10.1073/pnas.0605965104 . ISSN 0027-8424 . PMC 1765466. PMID 17190818 .
↑ Blondel, Vincent D.; Guillaume, Jean-Loup; Lambiotte, Renaud; Lefebvre, Etienne (2008). "Despliegue rápido de comunidades en grandes redes". Journal of Statistical Mechanics: Theory and Experiment (10) P10008. arXiv : 0803.0476 . Bibcode : 2008JSMTE..10..008B . doi : 10.1088/1742-5468/2008/10/P10008 .
↑ Sahu, Subhajit (2024). «Algoritmo rápido de Leiden para la detección de comunidades en entornos de memoria compartida». Actas de la 53.ª Conferencia Internacional sobre Procesamiento Paralelo . págs. 11-20 . arXiv : 2312.13936 . doi : 10.1145/3673038.3673146 . ISBN 979-8-4007-1793-2.

[Leiden-1] Traag , Vicente A; Waltman, Ludo; van Eck, Nees Jan (26 de marzo de 2019). "De Lovaina a Leiden: garantizar comunidades bien conectadas" . Informes científicos . 9 (1): 5233. arXiv : 1810.08473 . Código Bib : 2019NatSR...9.5233T . doi : 10.1038/s41598-019-41695-z . PMC 6435756 . PMID 30914743 .

[community-2] Clauset, Aaron y Newman, MEJ y Moore, Cristopher (2004). "Encontrando la estructura de la comunidad en redes muy grandes". Phys. Rev. E . 70 (6) 066111. arXiv : cond-mat/0408187 . Bibcode : 2004PhRvE..70f6111C . doi : 10.1103/PhysRevE.70.066111 . PMID 15697438 . S2CID 8977721 . {{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )

[:0-3] 1 2 3 Reichardt, Jörg; Bornholdt, Stefan (2004-11-15). "Detección de estructuras comunitarias difusas en redes complejas con un modelo de Potts" . Physical Review Letters . 93 (21) 218701. arXiv : cond-mat/0402349 . Bibcode : 2004PhRvL..93u8701R . doi : 10.1103/PhysRevLett.93.218701 . ISSN 0031-9007 . PMID 15601068 .

[leidenalg-4] 1 2 "Referencia — documentación de leidenalg 0.10.3.dev0+gcb0bc63.d20240122" . leidenalg.readthedocs.io . Consultado el 23-11-2024 .

[leidenR-5] "Paquete 'leiden'"" (PDF) . 27-07-2021. Archivado del original (PDF) el 08-02-2022.

[CPM-6] 1 2 Traag, Vincent A; Van Dooren, Paul; Nesterov, Yurii (29 de julio de 2011). "Alcance reducido para la detección de comunidades sin límite de resolución". Physical Review E . 84 (1) 016114. arXiv : 1104.3083 . Bibcode : 2011PhRvE..84a6114T . doi : 10.1103/PhysRevE.84.016114 . PMID 21867264 .

[7] Fortunato, Santo; Barthélemy, Marc (2007-01-02). "Límite de resolución en la detección de comunidades" . Actas de la Academia Nacional de Ciencias . 104 ( 1): 36– 41. arXiv : physics/0607100 . Bibcode : 2007PNAS..104...36F . doi : 10.1073/pnas.0605965104 . ISSN 0027-8424 . PMC 1765466. PMID 17190818 .

[8] Blondel, Vincent D.; Guillaume, Jean-Loup; Lambiotte, Renaud; Lefebvre, Etienne (2008). "Despliegue rápido de comunidades en grandes redes". Journal of Statistical Mechanics: Theory and Experiment (10) P10008. arXiv : 0803.0476 . Bibcode : 2008JSMTE..10..008B . doi : 10.1088/1742-5468/2008/10/P10008 .

[9] Sahu, Subhajit (2024). «Algoritmo rápido de Leiden para la detección de comunidades en entornos de memoria compartida». Actas de la 53.ª Conferencia Internacional sobre Procesamiento Paralelo . págs. 11-20 . arXiv : 2312.13936 . doi : 10.1145/3673038.3673146 . ISBN 979-8-4007-1793-2.

[ 1 ]

[ 2 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]