Grafos aleatorios con grados prefijados
Dado lo fácil que es hacer cálculos con ER, se ha
intentado generalizarlo.
Idea : fijar a priori la distribución de grados.
Una forma de hacerlo es asociar a cada nodo su grado
"deseado", y poner una arista entre dos nodos con
probabilidad proporcional al producto de sus grados
deseados.
¿Cómo se comportan los grafos aleatorios con una
distribución p0, p1, ... (pi=1) prefijada de grados?
Grafos aleatorios con grados prefijados
"A critical point for random graphs with a given degree sequence" Molloy
& Reed, Random Structures and Algorithms 6, 161-179 (1995)
Un grafo aleatorio que tenga pin nodos con grado i
(con n grande, ), tendrá una componente gigante
cuando
 i(i  2) pi  0
O, si lo que tenemos es la secuencia k1, k2,... de grados
de los nodos, entonces la condición es que

ki (ki  2)  0
Grafos aleatorios con grados prefijados
Por debajo de ese umbral, hay muchas componentes
conexas, de tamaños O(log n).
Para scale free de exponente  :
•La componente gigante aparece para  < 3.4788.
•El grafo es conexo para  < 2.
•[En la mayoría de las redes en que se ha medido ,
está entre 2 y 3; a veces bajo 2].
Grafos aleatorios con grados prefijados
Función generadora:
•Dada una distribución de probabilidad discreta p0, p1,
p2, ..., la función generadora es Gp(x)=pkxk.
•Verifica, entre otras cosas,
E p ( x)  Gp (1)
Varp ( x)  Gp (1)  Gp (1)  Gp (1) 
2
•Sirve para diversos trucos.
Grafos aleatorios con grados prefijados
Un ejemplo de truco:
Tomemos una arista al azar, y escojamos al azar uno
de sus extremos.
 La probabilidad de que sea un nodo de grado k es
proporcional a kpk [¿por qué?].
Consideremos entonces la variable aleatoria "grado
del nodo alcanzado". Su función generadora es

k
kpk

k
kpk
'
x x
k
G p ( x)
'
G p (1)
Grafos aleatorios con grados prefijados

k
kpk

k
kpk
'
x x
k
G p ( x)
'
G p (1)
Si dividimos por x, tenemos la función generadora de
algo. ¿De qué? Pues de la variable aleatoria "grado del
nodo al que llegué, menos 1".
De modo que si llego a un nodo por una arista escogida
al azar, la distribución de prob. de la cantidad de
otras aristas que encuentro allí tiene función
generadora G ' ( x) G ' (1)
p
p
También se usa f.g. para estudiar otras cosas (e.g., el tamaño de
la comp. conexa en que se encuentra un nodo escogido al azar).
Grafos aleatorios con grados prefijados
Una aplicación de f.g. (de un artículo de S. Strogatz).
•Considera los directorios de las 1000 primeras
empresas listadas por Fortune.
•Miramos el grafo bipartito, directorios/directores.
•De ahí se puede sacar la distribución de la cantidad
de directorios en los que alguien participa, y de la
cantidad de gente en los directorios.
•¿Habrán “cábalas”, grupos de gente que acapara
directorios?
Grafos aleatorios con grados prefijados
"p", exponencial
"q", unimodal, cercana a
normal, tal vez suma de
normales
Grafos aleatorios con grados prefijados
Escogemos un director al azar
y vemos la cantidad total de
gente con la que se encuentra
en reuniones (sumando todos
los directorios en que
participa).
O sea, es el grado del director
en el grafo de co-directores
(inducido por la red bipartita).
Sea r la distribución de esa
variable.
Grafos aleatorios con grados prefijados
Supongamos que la estructura es aleatoria :
una red típica del conjunto de redes bipartitas con
distribuciones p y q. En cond-mat/0007235, Newman,
Strogatz y Watts derivan la función generadora de r
como
 Gq' ( x) 

Gr ( x)  G p  '
 G (1) 
 q

Grafos aleatorios con grados prefijados
Como se conocen p y q empíricos, se puede evaluar esa
expresión.
O mejor aún, se puede derivar k veces y evaluar en 0.
Así se obtiene la probabilidad de que el director
comparta reuniones con un total de k personas.
Grafos aleatorios con grados prefijados
Coincide con lo observado.
No es así en películas y
papers, hay desviación.
Ahí el nivel de clustering no viene sólo del
grafo bipartito.
Grafos aleatorios con grados prefijados
Otra opción: Construir un grafo conexo que tenga
exactamente la secuencia de grados (d1,d2,...dm). Sin
perder generalidad suponemos d1  d2  ...  dm
Es posible construir un grafo con esa secuencia si y
sólo si la suma es par y además
k
d
i
i1
n
 k(k  1)   mindi , k
ik 1
Es posible construirlo conexo ssi además se tiene
k
d
i
i1
 2(n  1)
Grafos aleatorios con grados prefijados
Suponiendo entonces que se puede:
•Asigno a los nodos su "grado pendiente" ei,
inicialmente con valor di.
•Mientras haya un nodo con valor ei>0
•Escojo el nodo k con ei mínimo.
•Pongo ek aristas entre él y los k nodos de mayor ei.
•Actualizo los ei.
•Reviso y eventualmente fuerzo conexidad
(intercambiando links entre componentes conexas).
Grafos aleatorios con grados prefijados
Ese algoritmo (y otros igual de simples) no da un grafo
escogido uniformemente entre todos los grafos con
esa secuencia de grados.
Para asegurar eso, hago durante "un rato" un paseo
aleatorio, en que en cada paso intercambio los
extremos de un par de aristas.
Se usa este método para muestrear propiedades (por
ejemplo, correlación entre grados de nodos vecinos, o
distribución de distancias) en función sólo de la
distribución de grados.
Modelos
Una fracción
mínima de los
modelos
existentes.
[Albert, Barabási,
Rev. Mod. Phys
2002]
Modelos
Medidas de centralidad
Centralidad: ¿qué tan importante es un nodo?
En grafos dirigidos, se habla de "prestigio", y se
desdobla en dos tipos de medidas:
•Influencia (mira los arcos de salida)
•Apoyo (mira los arcos de entrada)
Medidas de centralidad
Hay varias formas de medir centralidad; cada una
mide cosas distintas.
Recordatorio de E.D.A.: centros y medidas de
centralidad en teoría de grafos “clásica”.
Sea u un nodo del GD G=(V,A). Definimos:
excentrici dad(u)  max dist (v, u )
vV
distancia promedio(u ) 
1
V
 dist (u, v)
vV
Máximo que me
tardo en llegar a u
Promedio que tardo en
ir de u a cualquier otro
Medidas de centralidad
•Centro de G = nodo(s) de excentricidad mínima
•Baricentro de G = nodo(s) de distancia promedio mínima
Nota: cuando aparecen distancias  estas
definiciones no son muy útiles.
Alternativas:
•sólo usarlas para grafos conexos
•calcularlas en la mayor componente conexa
Medidas de centralidad
b
a
d
c
prom
a b c d e f
a b c d e f
a 0 1  1  
a 0 1 2 1 1 3
1,6
b 1 0  1  
b 1 0 2 1 2 3
1,8
c 2 2 0 1 2 3
2
d 1 1 1 0 1 
d 1 1 1 0 1 2
1,2
e    1 0 1
e 1 2 2 1 0 1
1,4
f     1 0
f 3 3 3 2 1 0
2,4
c   0 1  
Floyd
max
3 3 3 2 2 3
Centro
e
f
Baricentro
Medidas de centralidad
En algunos grafos el grado de
un nodo puede ser también un
buen indicador de su
centralidad o importancia.
Es una noción
más local
Medidas de centralidad
Betweenness centrality
•Contar todos los caminos más cortos entre i y j: C(i,j).
•Ver cuántos pasan por k: Ck(i,j)
•La "centralidad de intermediación" (o “intermediación”
a secas) del nodo k es
Bk  
i j
C (i, j )
Ck (i, j )
L. C. Freeman,
Sociometry 40, 35 (1977)
Medidas de centralidad
Betweenness centrality
 Se distribuye como ley de potencia en redes
variadas (no en todas!)
Medidas de centralidad
Eigenvector centrality
(centralidad por vector propio)
Hacemos un paseo aleatorio por el grafo.
La centralidad de un nodo es la frecuencia
con la que nos lo encontramos.
Medidas de centralidad
Matriz de adyacencia:
caso no dirigido
2
0

1

A  1

0
0

Matriz de adyacencia:
caso dirigido
1
1
0
0
1
0
1
0
1
0
1
0
0
0
1
1
3
5
4
0

1

A  0

0
0

0

0

0

1
0 
1
1
0
0
0
0
1
0
1
0
0
0
0
02 0
0

0

0

1
0 
1
3
5
4
Medidas de centralidad
Paseo aleatorio: en cada paso,
avanzo de un nodo a otro.
Escojo una arista o arco al
azar de entre los disponibles.
Eso me da un proceso de Markov, cuya matriz de
transición es la matriz de adyacencia, normalizada.
Si el grafo es (fuertemente) conexo, la frecuencia de
las visitas converge a una distribución estacionaria.
Medidas de centralidad
La distribución estacionaria se
obtiene como el vector propio
por la izquierda asociado al
valor propio 1: qP=q
v2
v1
v3
 0

0

P   0

1 3
1 2

1 2
1 2
0
0
0
0
1
0
0
1 3
1 3
0
0
0
1 2
0

1

0

0
0 
qt+11 = 1/3 qt4 + 1/2 qt5
qt+12 = 1/2 qt1 + qt3 + 1/3 qt4
qt+13 = 1/2 qt1 + 1/3 qt4
qt+14 = 1/2 qt5
qt+15 = qt2
v5
v4
Medidas de centralidad
¿Qué pasa si caigo en un callejón sin salida?
Salida fácil: salto a un nodo cualquiera, escogido al
azar.
 0

0

P   0

1 3
1 2

1 2
1 2
0
0
0
0
1
0
0
1 3
1 3
0
0
0
1 2
0

0

0

0
0 
 0

1 5

P'   0

1 3
1 2

1 2
1 2
0
1 5
1 5
1 5
1
0
0
1 3
1 3
0
0
0
1 2
0 

1 5

0 

0 
0 
Medidas de centralidad
¿Y cómo garantizo irreducibilidad (es decir, conexidad
fuerte)?
Salida fácil: en cada paso, una probabilidad de escoger
un nodo al azar (en lugar de irme por un arco).
 0

1 5

P' '    0

1 3
1 2

1 2
1 2
0
1 5
1 5
1 5
1
0
0
1 3
1 3
0
0
0
0
0 
1


1 5
1


0   (1   ) 1


0 
1
1
1 2 

5
1 5
1 5
1 5
5
1 5
1 5
1 5
5
1 5
1 5
1 5
5
1 5
1 5
1 5
5
1 5
1 5
1 5
1 5

1 5

1 5

1 5
1 5 
Medidas de centralidad
•Este algoritmo fue propuesto en 1998 para medir la
importancia de páginas web (nodos=páginas, arcos=links).
•Autores: Sergey Brin & Lawrence Page.
Lo llamaron “PageRank”, y fue una idea tan
grande, que pudieron construir un imperio encima.
The Anatomy of a Large-Scale Hypertextual
Web Search Engine
Brin, S., Page, L. (Computer Networks and
ISDN Systems, 1998)
Abstract:
In this paper, we
... present Google, a prototype of
[Luego ha
evolucionado, pero
PageRank sigue
siendo la base.]
Medidas de centralidad
Otra aproximación, también en el
contexto de la Web: HITS
(Hypertext-induced text selection).
•Desarrollado por J. Kleinberg, 1998.
•Distingue entre las puntas de las
flechas: un hub apunta hacia muchas
partes; una autoridad es apuntada
desde muchas partes.
Cada nodo tiene algún nivel de
autoridad y de "hubness".
hubs
autoridades
Medidas de centralidad
La idea es que buenas autoridades son apuntadas por
buenos hubs, y viceversa.
¿Cómo encontrarlos?
Iterando:
•Inicializo pesos en 1
•Los hubs recolectan peso de las autoridades que
apuntan:
h 
a
i

j
j:i  j
•Las autoridades recolectan de los hubs: ai 
•Itero hasta converger.
h
j: j i
j
Medidas de centralidad
En términos vectoriales:
at = ATht-1 y ht = Aat-1
De modo que
at = ATAat-2 y ht = AATht-2
...y nuevamente es problema de vectores propios!
O mejor dicho, de descomposición en valores
singulares de la matriz A.
 T
 T
 T
A  σ1u1 v1  σ 2u2 v 2    σ rur v r
Donde σ1≥ σ2≥ … ≥σr son los valores singulares (raíz
cuadrada de valores propios de ATA y AAT), y los u y v
son los vectores singulares por la izquierda y
derecha, respectivamente.
Medidas de centralidad
Los vectores singulares
detectan las principales
tendencias lineales en filas
y columnas de la matriz A.
σ 2 v2
HITS encuentra la principal
tendencia lineal.
•Sirve también (colateralmente) para identificar
comunidades y aclarar ambigüedades.
Ejemplo: una búsqueda por "jaguar" dejó en el primer vector las
páginas sobre el animal, en un extremo del segundo las páginas
sobre el club de fútbol, y en un extremo del tercero las páginas
sobre el auto.
v1
σ1
Comunidades
En casi todos los ámbitos de
análisis de redes complejas
resulta útil detectar las
comunidades : conjuntos de nodos
bien conectados al interior de
cada grupo, pero poco conectados
entre un grupo y otro.
Sitios web sobre un tema, grupos de amigos,
módulos funcionales de una red genética, etc, etc.
Comunidades
Hasta cierto punto se parece
al viejo problema de machine
learning, clustering.
métrica
o
espacio vectorial
n-dimensional
En los algoritmos de
clustering por lo general
tenemos una nube de puntos
en un espacio n-dimensional, y
queremos dividir en sus
clases “naturales”.
Comunidades
Pero aquí:
•Es clustering de nodos en una
red.
•Distancia dada por la red.
•La topología puede ser
importante para los algoritmos
(algunos funcionarán mejor en
algunas clases de redes).
Comunidades
Los problemas de particionamiento en grafos son casi
todos (salvo los triviales) NP-duros. Ergo, heurísticas.
Métodos más populares:
•Espectrales (miran los valores y vectores propios
del laplaciano del grafo)
•Divisivos (cortan aristas según algo, para ir
creando componentes conexas)
•Aglomerativos (al revés, parten sin aristas y las
van agregando).
Comunidades: método espectral
Queremos encontrar un
conjunto de aristas pequeño,
que al quitarlas desconecte el
grafo (problema de min-cut).
Pero si hay nodos con grado
bajo (o grupos pequeños con
esa propiedad), es trivial. Así
que normalizamos, dividiendo
por el tamaño de la menor
componente conexa resultante.
Comunidades: método espectral
Coeficiente de expansión del grafo G=(V,E):
αG   min
U V
EU, V - U 
min U , V  U 
donde E(A,B) es el conjunto de aristas que tienen un
extremo en A y el otro en B.
Es posible aproximar  mediante valores propios del
laplaciano de G.
Comunidades: método espectral
Laplaciano de un grafo:
L = D-A
donde D es la matriz diagonal formada por los grados
de los nodos (dii=grado del nodo i, dij=0 para ij), y A es
la matriz de adyacencia.
De modo que
 di

Lij   1
0

i j
(i, j )  E
~
L es simétrica (estamos suponiendo G no dirigido) y
semi definida positiva  los valores propios son  0.
Comunidades: método espectral
Anotamos con 1 2... los valores propios de L.
Siempre se tiene 1 = 0, con vector propio w1=(1,1,...,1).
A 2 se le llama "valor de Fielder" y verifica
T
λ2 
min
x  w1 , x 1
x Lx  min
T
x  w1
x Lx
T
x x
(esto es genérico para matrices simétricas, uno va obteniendo los
valores propios sucesivos minimizando la forma cuadrático sobre el
subespacio ortogonal al de los valores propios ya encontrados).
Comunidades: método espectral
T
λ 2  min
x  w1
x Lx
T
x x
Notemos que aquí xw1 significa que
x
i
i
0
Con un poco de manipulación es posible ver que
x Lx 
T
 ( xi  x j )
2
(i, j)E
así que definimos el vector de Fielder como el vector
propio asociado a 2; es el que da el mínimo en
 ( xi  x j )
2  min
x  0 , xi  0
(i, j)E
 xi
2
i
2
Comunidades: método espectral
La gracia es que al minimizar
 ( xi  x j )
2
(i, j)E
este vector tratará de dar valores similares a nodos
vecinos, y distintos a nodos no conectados. Se ve
obligado a distinguir las comunidades!
Se verifica además que 2 da una buena aproximación
de la expansión del grafo:
λ2
2
α
λ 2 2d  λ 2 
Comunidades: método espectral
Ejemplo
1
2
3
4
5
2

1

L   1

0
 0
1
1
0
1
0
0
0
3
1
0
1
1
0
1
0
0.45

0.45

V  0.45

0.45
0.45
0

0

 1

0
1 
0.34
0
 0.70
0.70
0
0.54
 0.20
0
 0.32
 0.42
 0.71
0.24
 0.42
0.71
0.24
0.44 

 0.14

 0.81

0.26 
0.26 
E  0.00, 0.52, 1.00, 2.31, 4.17
Comunidades: método espectral
G
A
Otro ejemplo:
F
B
E
A B C D E F G
C
D
A 3 -1 0 0 0 -1 -1
A
-0.3682
1
B -1 3 0 -1 0 0 -1
B
-0.2808
1
C
0
C
0.3682
2
D 0 -1 -1 3 -1 0 0
D
0.2808
2
E
0
E
0.5344
2
F -1 0 -1 0 0 2 0
F
0.0000
G -1 -1 0 0 0 0 2
G
-0.5344
0
0
0
3 -1 -1 -1
0 -1 -1
2
0
?
1
Comunidades: método espectral
Teniendo el vector, es cosa de elegir dónde cortar.
•Cortar en la mediana de los valores .
•Elegir el corte que más se acerque a .
•Cortar donde esté el mayor gap en los valores.
•Cortar en 0.
•Etc
También podríamos cortar en más de un punto, para
tener más de dos subgrafos, o iterar el algoritmo
sobre los subgrafos para hacer cortes sucesivos.
Comunidades: método espectral
Existe una gran variedad de métodos espectrales,
todos siguiendo una idea similar.
El anterior demostrablemente funciona bien en
muchas clases de grafos, pero en otras clases funciona
demostrablemente mal.
Otra aproximación popular optimiza "conductancia",
similar a la expansión pero dividiendo por la mínima
suma de grados de los trozos, en lugar de su cardinal.
También se aproxima vía valor propio, pero de D-1A.
 G   min
U
E U, V - U 
min d U , d  V  U 

2
8
 1  μ2  
Comunidades: método espectral
Referencias sobre métodos espectrales de
particionamiento de grafos: ver
Kannan, Vempala and Vetta, 2004, J. ACM 51, 3: 497–515.
"On clusterings: Good, bad and spectral"
http://www.cc.gatech.edu/~vempala/papers/jacm-spectral.pdf
Y también
Donetti & Muñoz, "Improved spectral algorithm for the detection
of network communities"
http://ergodic.ugr.es/mamunoz/papers/PROC_AIP_Communit.pdf
Comunidades: métodos aglomerativos
En los métodos aglomerativos, cada nodo parte siendo
su propia "mini-comunidad", y vamos uniendo
comunidades progresivamente hasta tener una sola.
Es la misma idea del clustering jerárquico bottom-up, y
al igual que en ese caso, hay variantes según la forma en
que se definan las distancias iniciales, y las distancias
entre comunidades ya formadas.
Además, habrá que
escoger a qué altura
del árbol hacer el
corte.
Comunidades: métodos aglomerativos
Una estrategia popular es asociar pesos a las aristas, y
luego ir agregando aristas de a una, desde la más
"liviana" hasta la más pesada (corresponde al "singlelinkage clustering").
¿Qué pesos? Se han propuesto varios.
Cantidad de caminos nodo-disjuntos, o aristadisjuntos, entre los nodos.
Cantidad total de caminos entre los nodos; como
existen infinitos, se ponderan por aL, para algún a, y
con eso los pesos se calculan vía


W   a A   aA  1  aA
L
i 0
L
L
i 0
1
Comunidades: evaluación
¿Y a qué altura cortar?
Para eso hay que evaluar la calidad de la partición.
Esto, por supuesto, es general a todo método: tener
indicadores de calidad de las particiones, y para
comunidades específicas dentro de una partición dada.
(Nuevamente, es un problema que ya se conoce en clustering).
Se espera que una comunidad UV tenga más
conexiones internas que hacia el exterior; es decir, que
2 E (U ,U )  E (U ,V  U )
Se habla de comunidad débil ; se habla de fuerte cuando
cada nodo de U muestra la preferencia en sus links.
Comunidades: evaluación
También se ha hecho notar lo siguiente: si definimos
d (U i ) 
d
j
jU i
entonces la probabilidad de que una "pata" de una arista
escogida al azar esté en Ui es d (U i ) 2 E
Por lo tanto, la probabilidad de que
2
2
ambas estén en Ui es d (U i ) 4 E
Y podemos comparar la fracción de
aristas que está en Ui con la que
cabe esperar; si Ui es una
comunidad, debería haber un
exceso.
Comunidades: evaluación
Newman & Girvan (Phys Rev E, 2004) definen
k
Q(U1 , U k )  
E (U i , U i
i 1
E

d (U i )
4E
2
2
Es posible demostrar que si
2 E (U i ,U i )  E (U i ,V  U i ) i
entonces Q > 0.
Se han aplicado diversos algoritmos para buscar el
particionamiento que maximice Q (lo que también
incluye elegir el k maximizador): programación lineal
entera, algoritmos genéticos, etc...
Comunidades: evaluación
Q tiene falencias: no ve las comunidades que tengan
menos de |E| aristas.
(Fortunato & Barthélemy, 2007, "Resolution limit in community
detection", doi:10.1073/pnas.0605965104)
Una alternativa interesante parece ser
k
2 E (U i , U i  E (U i , V  U i )
i 1
Ui
D(U1 , U k )  
Zhenping Li et al, Phys
Rev E, 77, 036109,
2008 "Quantitative
function for
community detection".
Pero de momento Q es lo más usado.
Volviendo al caso de los algoritmos aglomerativos:
 elijo la altura de corte que maximiza Q.
Comunidades: métodos divisivos
Los métodos divisivos van quitando aristas y haciendo
aparecer así componentes conexas.
* Girvan & Newman, 2002, PNAS 99(12) 7821-7826,
"Community structure in social and biological networks".
Proponen evaluar la "betweeness" de las aristas, de
manera análoga a como lo pusimos para los nodos.
Algoritmo iterativo; en cada paso:
•Calcular betweeness de las aristas
•Quitar la más importante
•Recalcular la betweeness
Comunidades: métodos divisivos
A la derecha: (a) una red clásica
en los estudios, de un club de
karate donde había un grupo
cercano al instructor y otro
cercano al administrador.
(b) Árbol según método divisivo
de Girvan & Newman.
(c) Árbol según método
aglomerativo con pesos "aristadisjuntos".
(b) recupera lo observado
sociológicamente (salvo por un
nodo que queda mal clasificado).
Comunidades: métodos divisivos
Comunidades: métodos divisivos
El algoritmo de G&N es orden |E|2|V|; para hacerlo
más viable en redes grandes, Radicchi et al proponen
una medida local que reemplace la betweenness.
Dada una arista, calculan el # de triángulos en los que
participa, dividido por el # de triángulos en los que
podría participar, dados los grados de sus extremos.
(Es la misma idea de la definición de coeficiente de
clustering, pero trasladada a aristas).
Radicchi et al, "Defining and identifying communities in
networks", 2004, doi:10.1073/pnas.0400054101
Comunidades: métodos divisivos
Más genéricamente, calculan C(k)(i,j), donde en lugar de
triángulos consideran ciclos de largo k.
Permite interpolar, vía k, entre medida local y global.
Idea: triángulos (y ciclos) serán frecuentes dentro de
las comunidades pero no a través de varias de ellas.
El algoritmo será como antes, pero voy quitando la
arista con menor C(k). Los resultados son parecidos.
C(k) vs
betweeness
Pero anda más
rápido 
Comunidades: compresión
Una aproximación vía teoría de la información: quiero
describirle a alguien la red, de manera imperfecta pero
lo mejor posible, dándole una lista de comunidades y la
relación entre las comunidades.
Rosvall & Bergstrom, 2007, "An information-theoretic framework
for resolving community structure in complex networks",
doi:10.1073/pnas.0611034104
Comunidades: compresión
La idea es comprimir (con pérdida) la matriz de
adyacencia en un par [vector, matriz]:
donde los ai etiquetan a los nodos con sus respectivas
comunidades, y los lij dan la cantidad de links entre la
comunidad i y la j.
Quiero minimizar la incerteza del receptor sobre la
red; es decir, maximizar I(X,Y), donde X es la
descripción completa de la red, e Y es la que proveeré.
Comunidades: compresión
I(X,Y)=H(X)-H(X|Y), y aquí H(X) está fija.
Por lo tanto, hay que minimizar H(X|Y), que resulta ser
¿Y cuántas comunidades?
Dada una cantidad de comunidades m, el par [a,M] será
más chico o más grande; usan esto para determinar m:
se debe minimizar
Comunidades: compresión
O sea, el criterio a optimizar
es del tipo "minimum
description length".
Lo optimizan vía simmulated
anealing, aunque podrían
usarse otras heurísticas.
Ventajas:
•Escoge m.
•Menos sensible que otros
métodos a desigualdad en
tamaño de comunidades.
Comunidades: compresión
Desventaja: en el ejemplo
del club de Karate entrega
lo de B (agrupa los hubs
como comunidad), y se ven
obligados a introducir, en el
annealing, una penalización
contra las particiones que
dejan más links hacia fuera
que al interior de las
comunidades.
En fin, es para mostrar la
alternativa.
Comunidades: compresión
En 10.1073/pnas.0706851105 (2008) los mismos
autores presentan un approach basado en random
walks (ahora lo que queremos es describir la
random walk con pocos bits).
Resulta especialmente
bueno para grafos
dirigidos, en que
importe el flujo.
Aquí, un mapa de las
ciencias, basado en red
de citaciones.
Comunidades
Referencias para complementar:
"Graph Clustering and Minimum Cut Trees", Flake et al, Internet
Mathematics Vol. 1, No. 4: 385-408 (2003),
http://www.internetmathematics.org/volumes/1/4/Flake.pdf
"Finding community structure in very large networks", Clauset,
Newman, Moore, Phys Rev E 70, 066111 (2004),
http://arxiv.org/abs/cond-mat/0408187
IDEA: aglomerativo, causando máximo incremento de Q en cada paso.
No es malo, y queda O(n log2n).
(ese y otros esfuerzos más recientes son para manejar
redes graaandes)
y lista actualizada de referencias en
http://www.cscs.umich.edu/~crshalizi/notabene/communitydiscovery.html
Comunidades - complemento
Una alternativa para refinar algunos métodos,
especialmente los jerárquicos, es cambiar la noción
de distancia, o la noción de similaridad, entre nodos.
(Los métodos anteriores, si es que usan alguna, usan
la distancia definida como longitud del camino más
corto.)
Una alternativa: decir que dos nodos son cercanos si
es que existen muchos caminos disjuntos entre ellos.
Motivo: un conjunto de nodos es más “cohesionado”
si hay muchas formas alternativas de unir sus nodos.
Comunidades - complemento
0
1
2
3
Motivo: un conjunto de nodos es más “cohesionado”
si hay muchas formas alternativas de unir sus nodos
(y haría falta quitar muchos para desconectarlos).
Comunidades - complemento
k-componentes:
Dos nodos están en
la misma kcomponente si
existen al menos k
caminos
independientes
entre ellos.
Ejemplo: las 2-componentes en una red de drogadicción
(relación: haber compartido jeringas)
Comunidades - complemento
Otra medida de similaridad: podría considerarse que
dos nodos son estructuralmente similares si tienen
el mismo conjunto de vecinos.
Relajando eso un poco,
xij 
 (A
1
ik
 A ij )
2
k i , j
Distancia euclidiana
xij 
(A

n
ik
 i )( A jk   j )
k
 i j
Correlación de Pearson
Comunidades - complemento
Extendiendo aún más esa idea: se puede redefinir la
distancia entre nodos como el tiempo medio que
tardaría un paseo aleatorio en llegar desde uno
hasta otro.
Matriz de transición (la
misma de Pagerank)
Pij 
Aij

N
l 1
Ail
Se puede demostrar que da


1

  
l 1  I  B ( j )  il
N
di, j
donde I es la matriz de identidad, y B(j) es la
matriz P pero con la columna j anulada.
Comunidades - complemento
A su vez esa redefinición de distancia permite
redefinir similaridad:
 (i, j ) 

N
k i , j
d i ,k  d j ,k
2
N 2
H. Zhou, Phys. Rev. E 67, 061901 (2003)
H. Zhou, Phys. Rev. E 67, 041908 (2003)
Etc.
Comunidades - complemento
Algunos métodos de detección de comunidades son
deterministas; otros son heurísticos. En el caso de los
segundos, es útil ver qué tan robustos son los
resultados, si repetimos el algoritmo.
 Gráfico que indica, para
cada par de nodos, en qué
fracción de intentos
quedaron juntos
Comunidades - complemento
Si algunos nodos “oscilan” entre comunidades
distintas, puede no ser pifia, sino información: pueden
estar cumpliendo un rol de puente.
Guimerà & Amaral, Nature, 2005, “Functional
cartography of complex metabolic networks”
con
•i el grado de los nodos al interior de sus comunidades
•ki el grado de los nodos
•si la comunidad en que participa el nodo i
•s la desviación de i dentro de la comunidad s.
Comunidades - complemento
zi: qué tan conectado
está el nodo dentro de
su cluster.
Pi: que tan “comprometido”
está con su cluster.
zi > 2.5  hub
(esto es empírico)
~1: poco compromiso, se
conecta parejo con todos
los clusters.
~0: 100% comprometido
Observan distintos roles:
Comunidades - complemento
hub provincial
ultraperiféricos
periféricos
hub global
satélite
conector
Comunidades - complemento
Otra opción: mirar k-cores (en la red, o en
comunidades individuales).
k-core: conjunto de nodos donde cada uno está
conectado a los demás con al menos k aristas.
Comunidades – otro poco!
Un algoritmo que explicamos en pizarra pero que
vale la pena explicitar: algoritmo glotón de Newman.
Fast algorithm for detecting community structure
in networks
M. E. J. Newman
Phys. Rev. E 69, 066133 (2004)
http://arxiv.org/abs/cond-mat/0309508
Nota: el algoritmo aglomerativo glotón de Clauset et
al que mencionamos más atrás, de orden O(n log2n),
es una implementación eficiente de este.
Newman glotón
Inicialización:
•cada nodo es su propia comunidad.
Paso de la iteración:
•Se consideran todas las posibles fusiones entre
pares de comunidades.
•Se fusiona el par que aumente más el Q.
k
Q(U1 , U k )  
i 1
E (U i , U i )
E
 d (U i ) 


 2E 


2
Newman glotón
•Eso va generando una jerarquía de fusiones, hasta
terminar fundiendo todo.
•Al terminar se ve en qué punto el Q pasó por su
valor máximo, y a esa altura se corta el árbol.
Newman glotón
k
Q(U1 , U k )  
l 1
E (U l , U l )
E
 d (U l ) 


 2E 


2
La gracia es que la unión de dos comunidades afecta
sólo dos términos del Q.
Cambiemos la notación a la de Newman:
•eij = eji = ½ del % de aristas que va entre Ui y Uj
•eii = el % de aristas que está dentro de Ui
•ai = el % de “patas” que está en Ui
Con eso,
k
Q(U1 , U k )   ell  al
2
l 1
Newman glotón
k
Q(U1 , U k )   ell  al
2
l 1
•eij = eji = ½ del % de aristas que va entre Ui y Uj
•eii = el % de aristas que está dentro de Ui
•ai = el % de “patas” que está en Ui
Al fundir Ui con Uj y formar U*, el cambio en Q es

 
 
Q  e*  a*  eii  ai  e jj  a j
2
2
2

Pero a* = aii + ajj y e*=eii+eij+2eij, de modo que
Q  eii  e jj  2eij  (ai  2ai a j  a j )  eii  ai  e jj  a j
2

2
Q  2eij  ai a j 
2
2
Newman glotón
Además al fundir se tiene e*l  eil  e jl l  i, j
De modo que:
•Basta mantener en memoria la matriz e y el vector a
•En cada paso se escoge el (i,j) que maximiza eij-aiaj
•Fila y columna j de e, y componente j de a, se borra.
•Fila y columna i de e, y componente i de a, se actualiza
con los valores dado para U*.
La inicialización:
•ai = grado de nodo i
•eii = #cantidad de loops en nodo i
•eij = 1/2 cantidad de aristas entre nodos i y j
Un ejemplo que da Newman en su artículo
Pero ojo:
•Para subdividir las comunidades, vuelve a aplicar el
algoritmo sobre las componentes (no usa los otros
niveles del árbol inicial; no dan cosas buenas).
Newman glotón
•Son n pasos, y en cada paso, se busca el par de
entre  m pares posibles  O(n2) para redes
dispersas.
•Clauset & cía usan heaps y otros trucos para
obtener O(n log2n).
•En general este algoritmo no es especialmente
bueno ; la gracia es la eficiencia, y sirve como primer
indicador de presencia o ausencia de modularidad.
Comunidades en redes con pesos
Consideremos una red en que las aristas tienen pesos
asociados, que reflejan la intensidad de la relación
entre los nodos.
•Hablaremos de redes con pesos un poco más adelante.
Sin embargo, la extensión de Q es natural así que vale
la pena verla altiro.
Idea: reemplazo la matriz de adyacencia por una de
pesos wij=wji  0.
•Se define la “fuerza” de un nodo como
si   wi , j
j
Comunidades en redes con pesos
Esa “fuerza” generaliza la noción de “grado”.
Del mismo modo, en lugar de considerar la cantidad de
aristas entre dos comunidades, consideraremos la
suma de los pesos de esas aristas. Definiendo
f (U i , U j ) 
w
e
s(U i ) 
eE U i U j
s
jU i
j
S
1
s

2
j
j
 E (U ,U ) d (U ) 2 
i
i
i
Q(U1 , U k )   


2
E
4 E 
i 1 

k
2


f
(
U
,
U
)
s
(
U
)
W
i
i
i
Q (U1 , U k )   

2 
S
4
S
i 1 

k
Glotón de Newman, con pesos
Todos los algoritmos que optimizan Q, son aplicables al
caso con peso.
Por ejemplo, el algoritmo glotón de Newman ahora
escogerá en cada paso el par que maximice

Q  2 f (U i ,U j )  ai a j
'
'

con
f (U i ,U j )  1
2
w
e
eE U i U j
a 
'
i
s (U i )
2S
Glotón de Newman, con pesos
•Un ejemplo de Newman
glotón con pesos.
•Palabras co-ocurrentes
en noticias de Reuters,
octubre 2001.
•Peso: cantidad de coocurrencias.
“Método de Lovaina”
Un algoritmo aglomerativo empíricamente muy bueno,
y también bastante rápido:
Fast unfolding of communities in large networks
V. Blondel, J. Guillaume, R. Lambiotte, E. Lefebvre
Journal of Statistical Mechanics: Theory and
Experiment 2008 (10), P10008
http://arxiv.org/abs/0803.0476
•También es aglomerativo.
•También se apoya en la “localidad” de Q.
•Trabaja con redes con pesos (si no los hay, asume
peso = 1).
“Método de Lovaina”
Idea:
•Cada vuelta tiene dos etapas: una que optimiza la
modularidad localmente, y otra de agregación, que
“colapsa” las comunidades a mega-nodos.
•La etapa de optimización intenta trasladar nodos
entre comunidades, “tironeados” por sus vecinos, de
modo que Q vaya aumentando.
“Método de Lovaina”
•Inicio: n comunidades, una por cada nodo.
•Iteración:
DO
Paso de optimización
Paso de agregación
WHILE (hice algo)
“Método de Lovaina”
Paso de optimización:
DO
 nodo i
 nodo j vecino de i
Calcular bj = Q tras cambiar i a la
comunidad de j
Si max bj > 0, cambiar i a la comunidad del j
que maximiza bj
WHILE (hice algo)
Es rápido, por los
mismos motivos del
glotón de Newman.
“Método de Lovaina”
Paso de agregación:
•Crea una red con un nodo i por cada comunidad Ui
de la red previa.
• i,j, wij = suma de los pesos de aristas entre Ui y
Uj en la red previa.
“Método de Lovaina”
“Método de Lovaina”
•Tiempo de ejecución “empírico”: O(n log n)
•Al parecer no padece del límite de resolución m
común a los optimizadores de Q.
•Sin embargo, obtiene valores de Q bastante buenos
(en redes chicas, donde algoritmos más pesados son
viables, da valores competitivos).
•El algoritmo no termina en una única comunidad, sino
que cuando Q ya no mejora. Ergo, define # de
comunidades.
“Método de Lovaina”
•Un ejemplo que muestran: red de 2.6
millones de teléfonos móviles en Bélgica.
•Peso: # de llamadas entre los números,
durante un período de 6 meses.
•Los datos de los suscriptores incluían su
idioma (francés, holandés, inglés o alemán).
“Método de Lovaina”
•Color: idioma principal
de la comunidad
(francés, holandés).
•Se muestra la
red de
comunidades con
al menos 100
miembros.
“Método de Lovaina”
•La estructura jerárquica sí parece tener sentido; no
hace falta volver a correr el algoritmo para cada
comunidad.
•Por lo tanto, es un método multi-resolución.
•El árbol no tiene n pisos de altura, sino (por lo
general) unos pocos (5, 6...).
Extracción de una comunidad
•Los métodos que hemos visto tienen en común que
particionan toda la red.
•Sin embargo, puede que algunos nodos “cuelguen” de
una comunidad, que –aparte de ellos- es relativamente
compacta.
•En general, debiera ser posible localizar una
comunidad “compacta” dentro de la red, sin que lo que
pasa en el resto de la red afecte nuestro juicio.
Extracción de una comunidad
•Recordatorio: al hablar de métodos
espectrales (cuando empezamos a
hablar de comunidades), la idea era
separar la red en dos, con un “corte”
mínimo.
•Pero para evitar soluciones
triviales, se castigaba el
desnivel de tamaños:
min
U V

| E U, U

C
min U , U
|
C

•Eso es simétrico. ¿Qué pasa si me interesa que una de
las partes sea una “buena” comunidad?
Extracción de una comunidad
Idea en Zhao et al, Community extraction for social
networks, PNAS, 2011 (http://www.pnas.org/content/108/18/7321):
Primero sugieren maximizar
2 E U , U 
U
2


E U ,U
UU
C

C
pero eso tiene el problema de
así que lo que optimizan es
UU
C

C
 2 E U , U 
E U ,U


2
C
U
U
U




2 E U , U  U
U
C

 E U ,U
C

Extracción de una comunidad
•Después se puede iterar sobre el resto de la red, para
identificar la siguiente comunidad más compacta.
•No es muy rápido.
•Ejemplo de juguete:
los cuadrados son
ER con p=0.45, los
círculos son ER con
p=0.1, y hay
conexiones entre
ambos grupos con
p=0.1.
•El método de Zhao (izquierda) identifica bien el núcleo
compacto, pero la optimización de Q (derecha) se equivoca..
Extracción de una comunidad
•Club de karate:
modularidad anda bien,
pero Zhao identifica los
“núcleos”.
•Amistades en un
curso de colegio:
aquí Zhao brilla.
Descargar

SCD08