1 of 24

Comunidades

2 of 24

Noción básica de comunidad

Subconjunto de nodos de la red, que estén más conectados entre sí que con el resto

3 of 24

Noción básica de comunidad

Subconjunto de nodos de la red, que estén más conectados entre sí que con el resto

 

 

 

4 of 24

¿Qué vamos a ver?

Vecinos/Esperados

Distancia de Hamming

Similaridad

Chequeo

Comunidades

Ravasz

Newman-Girvan

Fast Greedy

Louvain

Infomap

Silhouette

Información Mutua

Modularidad

Sin info externa

Con info externa

5 of 24

Similaridades

6 of 24

Similaridad

7 of 24

Similaridad

Vecinos/Esperados

Distancia de Hamming

 

 

 

 

 

 

 

 

 

Comparten todos los vecinos

No comparten ninguno

Más del esperado

Menos vecinos del esperado

 

Comparten todos los vecinos y están unidos

No comparten vecinos ni están unidos

8 of 24

Similaridad

Centralidad Katz

 

Con información externa a la topología

Centralidad PageRank

9 of 24

Algoritmos de detección de comunidades

10 of 24

Algoritmo de Ravasz

 

Repito desde 2. hasta obtener una sola comunidad

Máx: complete linkage

Min: Single linkage

Promedio: Average linkage

11 of 24

Algoritmo de Ravasz

 

 

 

 

 

 

 

 

12 of 24

Newman-Girvan

  1. Defino toda la red como una comunidad
  2. Calculo centralidad de intermediatez de enlaces (edge betweenness)
  3. Saco el enlace de mayor centralidad
  4. Defino una comunidad por cada componente nueva.

(hay variaciones tomando otras centralidades)

​

Repito desde 2. hasta obtener N comunidades

13 of 24

Newman-Girvan

 

 

 

 

 

 

 

 

14 of 24

¿Dendogramas -> Comunidades?

 

Cortar donde se maximice la Modularidad

Esto es costoso

15 of 24

Algoritmo Fast Greedy

Maximiza la modularidad sin calcularla

Calcula las diferencias de modularidad

 

 

16 of 24

Algoritmo Fast Greedy

Maximiza la modularidad sin calcularla

Calcula las diferencias de modularidad

 

Repito desde 2. hasta obtener una sola comunidad

17 of 24

Algoritmo Louvain

Maximiza la modularidad sin calcularla

Calcula las diferencias de modularidad

Agrupa comunidades en nodos a cada paso

18 of 24

Algoritmo Louvain

 

Repito desde 2. hasta obtener una sola comunidad

19 of 24

Entropía de Shannon

 

 

 

 

 

 

 

 

20 of 24

Algoritmo Infomap

Etiquetar nodos y comunidades para minimizar la entropía (información) de Shannon

Etiquetas para nodos

Etiquetas para entrar y salir de comunidades

Dividir en comunidades, permite asignar más etiquetas de menos bits

21 of 24

Chequeo de comunidades

22 of 24

Silhouette

Analizo si cada nodo está más ‘cerca’ de su comunidad que del resto

Silhouette Plot

No está bueno que haya clusters enteros por debajo de la media

23 of 24

Entropía de Shannon (bis)

 

 

 

 

 

 

 

 

 

 

24 of 24

Información Mutua

Si tengo info externa

i = 1 2

j = 1 2 3