Cómo el algoritmo de despliegue rápido detecta comunidades en redes grandes

El análisis de redes sociales implica estudiar patrones en grandes redes de la vida real que se componen de millones de nodos. Si tiene un conocimiento básico de teoría de grafos, puede realizar estos análisis.

El mundo digital ha abierto una forma totalmente diferente de crear relaciones. También ha desatado un océano de datos que podemos analizar para comprender mejor el comportamiento humano.

Los datos de las redes sociales se refieren a todos los conocimientos y la información en bruto recopilados de la actividad de las redes sociales de un individuo. Podemos crear redes a partir de estas actividades en las redes sociales para tener una mejor percepción de esa persona.

Estas redes pueden variar ampliamente y pueden incluir a sus amigos de Facebook, los productos que compró recientemente en Amazon, los tweets que le gustaron o retuiteó, su comida favorita que ordenó en Zomato, la búsqueda que hizo en Google o la imagen que le gustó recientemente en Instagram. .

Las empresas utilizan estas redes para clasificar a sus usuarios en diferentes grupos. Esto les ayuda

  • hacer investigación de mercado
  • generar cables
  • servir mejor a sus clientes
  • buscar y compartir fotos y videos
  • descubrir y discutir contenido de tendencia
  • compartir información sobre servicios y restaurantes
  • conectarse con otros en torno a un interés o pasatiempo compartido
  • y más.

La lista es bastante interminable.

Antes de adentrarnos demasiado en las malas hierbas, analicemos rápidamente la distinción entre los diferentes componentes de una red.

¿Qué es una red?

Una red es una red de relaciones personales interconectadas. Por ejemplo, diferentes personas pueden comunicarse entre sí en un grupo de redes sociales a través de una red dinámica de relaciones.

Una red se compone de nodos (actores individuales, personas o cosas dentro de la red) y los lazos , bordes o vínculos (relaciones o interacciones) que los conectan.

¿Qué es un grupo?

Reicher SD en La determinación del comportamiento colectivo describe un grupo como una colección de individuos que se consideran a sí mismos como un grupo. Los miembros del mismo grupo comparten un conjunto de creencias y comportamientos.

¿Qué es una comunidad?

Según David W. McMillan ( Sentido de comunidad: una definición y teoría ) , la comunidad se puede definir como sigue:

“El sentido de comunidad es un sentimiento que los miembros tienen de pertenencia, un sentimiento de que los miembros se importan unos a otros y al grupo, y una fe compartida en que las necesidades de los miembros se satisfarán a través de su compromiso de estar juntos. "

Las comunidades o subunidades son las subredes en una red que son nodos altamente interconectados.

La comunidad indica la existencia de estructuras internas que tienen características especiales o juegan el mismo rol en una red.

Los grupos de individuos u objetos altamente conectados dentro de estas redes son comunidades. Por lo general, se encuentra en el punto de intersección de la red y el grupo.

Ahora que tenemos una idea clara de lo que es una red, un grupo y una comunidad, profundicemos en cómo estas redes se dividen en pequeñas comunidades.

Veremos el popular algoritmo de despliegue rápido . Vincent C. Blondel y los coautores del artículo compararon este algoritmo con otros algoritmos de detección de comunidades. Descubrieron que este algoritmo supera a cualquier otro algoritmo en redes grandes.

¿Qué es el algoritmo de despliegue rápido?

El algoritmo de despliegue rápido se utilizó para identificar comunidades lingüísticas en una red de telefonía móvil belga de 2,6 millones de clientes.

También se utilizó para analizar un gráfico web de 118 millones de nodos y más de mil millones de enlaces.

Identificar comunidades en una red tan grande tomó solo 152 minutos. Entonces, este algoritmo es rápido y eficiente.

Como funciona el algoritmo

El algoritmo funciona en dos fases:

Fase 1

  1. Asigne una comunidad diferente a cada nodo de una red.
  2. Entonces, para cada nodo, i considera nodo j y evalúa la ganancia en modularidad mediante la eliminación de nodo i desde su comunidad y colocándola en la comunidad de j.
  3. El nodo i se coloca en la comunidad para la que obtiene la máxima modularidad, pero la ganancia debe ser positiva. Si la ganancia es negativa, entonces el nodo i permanece en la misma comunidad.

Fase 2

  1. La segunda fase del algoritmo consiste en construir una nueva red cuyos nodos son ahora las comunidades encontradas durante la primera fase. Entonces, construimos nodos fusionando todos los nodos de la comunidad como un solo nodo.
  2. Los pesos del enlace entre los nodos vienen dados por la suma de los pesos de los enlaces entre los nodos en las dos comunidades correspondientes.
  3. El enlace entre nodos de la misma comunidad conduce a bucles propios para la comunidad en la nueva red.
  4. Repita la Fase 1 hasta que no se puedan lograr más mejoras.

Cómo se calcula la ganancia en modularidad

La calidad de la partición ( Q ) se mide por la modularidad (también conocida como modularidad de la partición). Es un valor escalar entre -1 y 1, y mide la densidad de enlaces dentro de las comunidades en comparación con los enlaces entre comunidades.

La ganancia en modularidad (∆Q) obtenida al mover un nodo aislado i a una comunidad C se puede calcular fácilmente mediante:

Σin es la suma de los pesos de los enlaces dentro de C.

Σtot es la suma de los pesos de los enlaces incidentes a los nodos en C.

ki es la suma de los pesos de los enlaces desde i hasta el nodo en C.

m es la suma de los pesos de todos los enlaces de la red.

La ganancia en modularidad se evalúa quitando i de su comunidad y luego moviéndolo a una comunidad vecina. Si la ganancia es positiva, ese nodo se coloca en la comunidad vecina.

Ejecución en seco del algoritmo

En la red de la izquierda (15 nodos), primero asignamos una comunidad única a cada nodo. Luego, evaluamos la modularidad de cada nodo y reasignamos la comunidad en función de la ganancia. Esto se denomina Optimización de modularidad .

En la siguiente fase, construimos nodos fusionando todos los nodos de esa comunidad en un solo nodo. En la comunidad verde, tenemos un total de 5 nodos y hay un total de 7 bordes entre ellos.

Entonces, después de la Agregación de la comunidad , el peso del bucle automático del nodo verde será 14 (7 * 2 ya que es un enlace bidireccional). De manera similar, el peso del bucle automático del nodo rojo será 16, el nodo azul será 4 y el nodo azul claro será 2.

El peso del borde entre el nodo verde y el azul será 4, ya que hay un total de 4 bordes entre la comunidad verde y azul después de la Optimización de modularidad.

En el siguiente paso, reevaluamos la modularidad de los nuevos nodos y volvemos a realizar el mismo proceso.

Finalmente, obtenemos dos comunidades, Green y Light Blue. La comunidad verde tiene 26 ciclos propios, ya que hay un total de 13 bordes entre los nodos de la comunidad verde. Y tenemos 12 aristas en la comunidad celeste, un total de 24 bucles automáticos.

Ventajas del algoritmo

  1. Sus pasos son intuitivos y fáciles de implementar y el resultado no está supervisado.
  2. El algoritmo es extremadamente rápido. Las simulaciones por computadora en redes modulares muy grandes sugieren que su complejidad es lineal en los datos típicos y escasos. Esto podría deberse a que Gain in Modularity es fácil de calcular y el número de comunidades disminuye drásticamente después de unas pocas pasadas.

Limitaciones del algoritmo

  1. La optimización de la modularidad no logra identificar comunidades más pequeñas que una determinada escala. Por lo tanto, provoca un límite de resolución en la comunidad calculada utilizando un enfoque de optimización de modularidad pura.
  2. Para redes pequeñas, la probabilidad de que dos comunidades separadas puedan fusionarse moviendo cada nodo es muy baja.

Conclusión

Si ha aguantado tanto tiempo ... ¡gracias! Espero que haya habido información valiosa para ti.

Ahora ya sabe cómo funciona el algoritmo de despliegue rápido y que es extremadamente eficiente para detectar comunidades en redes muy grandes.

La forma en que calcula la ganancia en modularidad hace que el algoritmo supere a todos los demás algoritmos que existen. Envíeme una nota si lo encuentra útil o si tiene alguna pregunta de seguimiento.

¡Gracias por leer!