PDF de programación - Tema 6: Modularidad, Particionamiento y Comunidades

Redes y Sistemas Complejos

Cuarto Curso del Grado en Ingeniería Informática

Tema 6: Modularidad, Particionamiento y Comunidades

Oscar Cordón García

Dpto. Ciencias de la Computación e Inteligencia Artificial

[email protected]

INTRODUCCIÓN

Estructura de Comunidades

Las redes complejas tienden a mostrar una estructura de comunidades

Esta propiedad suele darse como consecuencia de la heterogeneidad global y local
de la distribución de los enlaces en un grafo

A menudo encontramos una alta concentración de enlaces en ciertas regiones
del grafo, denominadas comunidades, y una baja concentración de enlaces entre
esas regiones

Las comunidades, también conocidas como módulos o
clusters, se definen de forma sencilla como grupos de
nodos similares

A partir del concepto de densidad de la red, las comunidades
pueden definirse como grupos de nodos densamente
conectados que presentan conexiones dispersas entre sí

INTRODUCCIÓN

Caso ideal

• En esta red, hay tres comunidades: C1, C2 y C3
• Cada comunidad está formada por un grafo completo (un clique) de tamaño

variable (C1= K6, C2= K3 y C3= K7)

• La densidad de enlaces entre las comunidades es muy baja. Los pocos enlaces

que existen son puentes

ESTRUCTURA MODULAR DE LAS REDES

Clustering y mundos pequeños

El clustering implica modularidad

La funcionalidad requiere modularidad

La propiedad de mundos pequeños tiende a
eliminar la modularidad

ESTRUCTURA MODULAR DE LAS REDES

Hubs

El clustering implica modularidad

La funcionalidad requiere modularidad

La propiedad de mundos pequeños tiende a
eliminar la modularidad

Los hubs tienden a eliminar la modularidad

ESTRUCTURA MODULAR DE LAS REDES

¿Cuándo es modular una red?

El clustering sólo debe estar en la periferia

Los nodos de grado
bajo suelen pertenecer
a un único módulo

Los hubs hacen de
puente entre distintos
módulos

C

k

ESTRUCTURA MODULAR DE LAS REDES

¿Cuándo es modular una red?

El clustering sólo debe estar en la periferia

Los nodos de grado
bajo suelen pertenecer
a un único módulo

Los hubs hacen de
puente entre distintos
módulos

C

k

Pero… ¿cómo descubrimos los módulos?

ESTRUCTURA MODULAR DE LAS REDES

Medida de modularidad (1)

La modularidad Q es una función de calidad que mide la calidad de una partición
concreta de una red en comunidades:

Se define como la diferencia entre el número de enlaces existentes en los grupos y el
número de enlaces esperado en una red aleatoria equivalente

1

=

Q

2

L
número de enlaces
de la red

∑

ij





−

A
ij

kk

i

j

2

L


δ
(



cc
i

,

j

)

vale 1 si los nodos son de
la misma comunidad

matriz de adyacencia

la probabilidad de un enlace entre dos
nodos es proporcional a sus grados

Clauset, Newman, Moore. Finding community structure in very large networks. Phys Rev E 70:066111 (2004)

ESTRUCTURA MODULAR DE LAS REDES

Medida de modularidad (2)

La idea básica es que la red muestra una estructura modular coherente si el número
de enlaces entre comunidades es menor que el esperado en una red aleatoria

Q ∈ [-1,1]. Cuanto mayor es su valor, mejor es la partición, es decir, las comunidades
encontradas están densamente conectadas internamente (hay más enlaces de los
que cabría esperar aleatoriamente) y dispersamente conectadas entre sí

En una red aleatoria, Q=0. En la práctica, una modularidad de 0.3 es un buen valor

Se usa tanto para comparar la calidad de distintas particiones como diseñar métodos
de descubrimiento de comunidades que traten de maximizar su valor

COMUNIDADES EN EL MUNDO REAL (1)

En la vida real existen muchos ejemplos de grupos compactos en redes
complejas:

• Sociedades: las personas tienen una tendencia natural a formar grupos (familias,

círculos de amigos, grupos profesionales o religiosos, ciudades, naciones, etc.)

• Empresariales/Económicas: compañías, clientes, etc.

• Biología: p.ej. redes metabólicas. En redes de interacción de proteínas

encontramos grupos de proteínas con funciones similares dentro de la célula

•

•

Internet: comunidades virtuales (Facebook, Twitter, etc.), grupos de páginas web
relacionadas, etc. (útiles para sistemas de recomendaciones)

y muchos ámbitos más…

COMUNIDADES EN EL MUNDO REAL (2)

Modularidad funcional

Líneas de partición naturales

COMUNIDADES EN EL MUNDO REAL (3)

Ejemplo clásico

El club de karate de Zachary

Zachary. An information flow model for conflict and fission in small groups. J. Anthropol. Res. 33:
452-473 (1977)

FORMACIÓN DE OPINIONES Y ESTRUCTURA DE COMUNIDADES (1)

H = hispanos, E = ingleses
P = planificación, M = corte, Y = patio

Red del aserradero (sawmill). Fuente: Exploratory Social Network Analysis with Pajek

FORMACIÓN DE OPINIONES Y ESTRUCTURA DE COMUNIDADES (2)

La dirección del aserradero estaba teniendo dificultades para persuadir a los
trabajadores para que adoptaran un nuevo plan que redundaría en un
beneficio para todos los empleados

En concreto, los trabajadores hispanos eran los más reticentes a aceptar

La dirección contrató a un sociólogo que diseñó una red que reflejaba con
qué compañeros hablaban habitualmente

El sociólogo recomendó a la dirección que hablaran con Juan y que le
pidieran que hablara con el resto de trabajadores hispanos

Fue un éxito, rápidamente todos estaban de acuerdo con el nuevo plan

¿Por qué?

FORMACIÓN DE OPINIONES Y ESTRUCTURA DE COMUNIDADES (3)

•

http://www.ladamic.com/netlearn/NetLogo502/OpinionFormationModelToy.html

• Cada nodo adopta la opinión mayoritaria de sus vecinos (una opinión

aleatoria, en caso de empates)

FORMACIÓN DE OPINIONES Y ESTRUCTURA DE COMUNIDADES (4)

PREGUNTA:

Ejecutar alternativamente la configuración de dos comunidades y la de
Erdos-Renyi. ¿Cuál puede mantener opiniones divergentes cuando se itera
la actualización de opiniones?

a) Sólo la de Erdos-Renyi

b) Sólo la de dos comunidades

c) Ambas

http://www.ladamic.com/netlearn/NetLogo502/OpinionFormationModelToy.html

FORMACIÓN DE OPINIONES Y ESTRUCTURA DE COMUNIDADES (5)

FORMACIÓN DE OPINIONES Y UNIFORMIDAD:

Si cada nodo adopta la opinión de la mayoría de sus vecinos, es posible
formar opiniones distintas en subgrupos cohesivos distintos

FORMACIÓN DE OPINIONES Y ESTRUCTURA DE COMUNIDADES (6)

Hay más uniformidad dentro de un grupo cohesivo:

FORMACIÓN DE OPINIONES Y ESTRUCTURA DE COMUNIDADES (7)

Rosvall y Bergstrom. Maps of random walks on complex networks reveal community structure. Proc.
Natl. Acad. Sci. USA 105: 1118-1123 (2008)

Mapa de la ciencia de citaciones de 6000 revistas

FORMACIÓN DE OPINIONES Y ESTRUCTURA DE COMUNIDADES (8)

Rosvall y Bergstrom. Maps of random walks on complex networks reveal community structure. Proc.
Natl. Acad. Sci. USA 105: 1118-1123 (2008)

Clustering para comprimir la información de random walks que siguen el flujo de las
citas de un campo científico a otro, de modo que las áreas emergen de forma natural

FORMACIÓN DE OPINIONES Y ESTRUCTURA DE COMUNIDADES (9)

Fortunato. Community detection in graphs. Phys Rep 486: 75–174 (2010)

CRITERIOS ESTRUCTURALES QUE IDENTIFICAN UNA COMUNIDAD EN UNA RED

• Mutualidad completa (cliques):

• El grupo es un subgrafo completo (todo el mundo se conoce en el grupo)

• Frecuencia de enlaces entre los miembros (k-cores):

• Todos los miembros del grupo tiene enlaces al menos a otros k miembros

• Alcanzabilidad/cercanía entre los miembros (n-cliques):

• Los individuos del grupo están separados por un máximo de q saltos

• Comparación de la cohesión interna y externa del grupo (p-cliques):

• Frecuencia relativa de enlaces entre los miembros del grupo en comparación

con la de los no miembros

Wasserman y Faust. Social Network Analysis. Cambridge University Press; 1994

IDENTIFICACIÓN DE CLIQUES

Concepto

• Todos los miembros del grupo tienen enlaces al resto

• Los triángulos son los cliques más básicos, los de mayor dimensión son

menos frecuentes

• Los cliques pueden estar solapados

cliques solapados
de tamaño 3

clique de
tamaño 4

IDENTIFICACIÓN DE CLIQUES

Modelo Netlogo (1)

• http://www.ladamic.com/netlearn/nw/Cliques.html

• Comparar la configuración de red aleatoria ER con la de estructura de

comunidades (son las mismas que en el modelo de formación de opiniones)

IDENTIFICACIÓN DE CLIQUES

Modelo Netlogo (2)

• PREGUNTA: ¿Cuál de los dos tiene un clique máximo de mayor tamaño?

• Los cliques revelan la estructura de comunidades…

IDENTIFICACIÓN DE CLIQUES

Problemas para descubrir comunidades

• Es un problema NP-completo

• No son robustos

• Un solo enlace faltante puede descalificar un clique, haciendo que el grupo no

sea considerado una comunidad

• No son interesantes

• Todo el mundo está conectado entre sí

• No hay estructura centro-periferia, no hay jerarquía entre los enlaces

• Las medidas de centralidad no dan información

• El solapamiento de los cliques puede ser más relevante que su propia

existencia…

IDENTIFICACIÓN DE K-CORES

Frecuencia de enlaces entre miembros (1)

• Cada nodo de un grupo está conectado con otros k nodos de dicho grupo:

Pregunta:

• ¿Cuál es el valor de k para el k-core marcado en rojo?

• ¿y para el azul?

IDENTIFICACIÓN DE K-CORES

Frecuencia de enlaces entre miembros (2)

• Cada nodo de un grupo está conectado con otros k nodos de dicho grupo:

3-core

4-core

• Aun así, es una estructura demasiado restrictiva como requisito para

identificar comunidades naturales

2-core

4-core

IDENTIFICACIÓN DE N-CLIQUES

Alcanzabilidad y diámetro

• La máxima distancia entre cualesquiera dos nodos del grupo es n (el 1-

clique equivale al clique):

2-cliques

• Justificación teórica: Flujo de información a través de intermediarios

IDENTIFICACIÓN DE N-CLIQUES

Consideraciones

• Problemas:

• El diámetro puede ser mayor que n

• El n-clique puede estar desconectado (los caminos pueden pasar por nodos

que no estén en el grupo)

2–clique
diámetro = 3

camino externo al 2-clique

• Solución: n-clubs: subgrafos máximos de diámetro 2