Descubrimiento comunitario basado en módulos
Una comunidad es un subgrafo que contiene vértices y aristas. Los nodos de la misma comunidad están estrechamente conectados, mientras que las comunidades están escasamente conectadas.
El algoritmo de Luwan es un algoritmo de descubrimiento de comunidades basado en datos gráficos. Mide la cercanía de la comunidad a través de la modularidad. Se considera uno de los algoritmos de descubrimiento comunitario de mejor rendimiento.
Definición de modularidad:
Entre ellos, representa el número de aristas en el gráfico, representa la comunidad, representa el número de aristas dentro de la comunidad y representa la suma de los grados. de nodos c en la comunidad
p>
Ejemplo de cálculo[1]
Por ejemplo, calcule la modularidad de un gráfico dividiendo el gráfico en tres comunidades
El gráfico contiene 23 aristas y contiene 3 comunidades
La comunidad 1 tiene 5 aristas internas ( ) y la suma de los grados de los nodos es
( ).
La comunidad 2 tiene 7 aristas internas ( ) y la suma de los grados de los nodos es
( ).
La comunidad 3 tiene 8 aristas internas ( ) y la suma de los grados de los nodos es
( ).
Por lo tanto, el grado de modularidad del gráfico es:
Cuanto mayor sea el valor del grado de modularidad, mejor se dividirá la comunidad y más cerca estará la comunidad.
El grado de modularidad se utiliza para medir la cercanía de una comunidad
(1) Calcular el grado de modularidad de la imagen de la izquierda
La imagen de la izquierda contiene 23 aristas, incluidas 2 comunidades
(2) Calcule el grado de modularidad del gráfico derecho
El gráfico derecho contiene 23 aristas y contiene 2 comunidades
Puede Se encuentra que cuando se divide en Cuando hay tres comunidades, el valor de modularidad del gráfico es el mayor y es mejor dividirlo en tres comunidades que en dos comunidades.
El algoritmo de Louvain es un algoritmo de descubrimiento de comunidades basado en datos gráficos. Mide la cercanía de una comunidad a través del grado de modularidad.
¿Cómo utilizó Louvan la modularidad para descubrir la comunidad?
Pasos del algoritmo de Louvain
Pasos de exploración:
Nodo 0: asignado a la comunidad donde se ubican los nodos adyacentes 1, 2 y 3
Modularidad antes de la asignación: -0,0043; Modularidad después de la asignación a {1}: 0,0265. Grado de modularidad: 0,0265, modularidad asignada a {2}: 0,0265, modularidad asignada a {3}: 0,0317; los nodos 0 y 3 se fusionan en una comunidad según la diferencia máxima de modularidad.
Nodo 1: asignado a {0, 3}, {2} comunidad donde se encuentran los nodos adyacentes 0, 2, 3.
Modularidad antes de la asignación: -0,0043; Modularidad de 0, 3}: 0.1002; modularidad asignada a {3}: 0.0317: 0.1002, modularidad asignada a {2}: 0.0265;
Módulo asignado a {0, 3} Grado: 0.10020.0265;
Fusione el nodo 1 y el nodo 2 en una comunidad según la diferencia máxima de grados de módulo. Fusionarlos en una comunidad, en este momento {1, 2}, {0, 3}
Nodo 2: asignado a la comunidad {0, 3}, {1 donde los nodos adyacentes 0, 1, 4 están ubicados }, {4}
Modularidad antes de la asignación: -0,0043; modularidad asignada a {0, 3}: 0,0567, modularidad asignada a {1}: 0,0265, modularidad asignada a {4}: 0,0265.
Fusiona los nodos 2 y 3 en una comunidad según la diferencia de modularidad máxima, en este momento {0, 2, 3}, {1}, {4}
El nodo 2 es encontrado La comunidad a la que pertenece ha cambiado
Nodo 1: asignado a la comunidad {0, 2, 3} donde se encuentran los nodos vecinos 0, 2, 3
Modularidad antes de la asignación: -0.0043 ; asignado a {0, 2, 3} Modularidad: 0.1167, mayor que la modularidad de la comunidad original {1}, y formando una nueva comunidad {0, 1, 2, 3}
- --
python-louvain proporciona la función community best_partition, que realiza el descubrimiento de la comunidad calculando el grado máximo de modularidad. Es un contenedor del algoritmo de louvain.
(1) Construir relaciones gráficas
(2) Descubrir comunidades
(3) Verificar los resultados del cálculo de los gráficos izquierdo y derecho anteriores
[ 1] Detección de comunidad: /p/41105026
/p/4ebe42dfa8ec
[2] Documentación de la función python-louvain: /view/15394e520912a216147929cc.html