Date post: | 22-Jan-2016 |
Category: |
Documents |
Upload: | timoteo-santiago |
View: | 212 times |
Download: | 0 times |
Grafos aleatorios con grados prefijadosGrafos aleatorios con grados prefijadosGrafos aleatorios con grados prefijadosGrafos 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 prefijadosGrafos aleatorios con grados prefijadosGrafos aleatorios con grados prefijadosGrafos 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 pin nodos con grado i (con n grande, ), tendrá una componente gigante cuando 0)2( ipii
O, si lo que tenemos es la secuencia k1, k2,... de grados de los nodos, entonces la condición es que
0)2( ii kk
Grafos aleatorios con grados prefijadosGrafos aleatorios con grados prefijadosGrafos aleatorios con grados prefijadosGrafos 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 prefijadosGrafos aleatorios con grados prefijadosGrafos aleatorios con grados prefijadosGrafos 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, )1()( pp GxE
2)1()1()1()( pppp GGGxVar
•Sirve para diversos trucos.
Grafos aleatorios con grados prefijadosGrafos aleatorios con grados prefijadosGrafos aleatorios con grados prefijadosGrafos 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
)1(
)('
'
p
pk
k k k
k
G
xGxx
kp
kp
Grafos aleatorios con grados prefijadosGrafos aleatorios con grados prefijadosGrafos aleatorios con grados prefijadosGrafos aleatorios con grados prefijados
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
)1(
)('
'
p
pk
k k k
k
G
xGxx
kp
kp
)1()( ''pp GxG
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 prefijadosGrafos aleatorios con grados prefijadosGrafos aleatorios con grados prefijadosGrafos 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 prefijadosGrafos aleatorios con grados prefijadosGrafos aleatorios con grados prefijadosGrafos aleatorios con grados prefijados
"p", exponencial "q", unimodal, cercana a normal, tal vez suma de
normales
Grafos aleatorios con grados prefijadosGrafos aleatorios con grados prefijadosGrafos aleatorios con grados prefijadosGrafos 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 prefijadosGrafos aleatorios con grados prefijadosGrafos aleatorios con grados prefijadosGrafos 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
)1(
)()( '
'
q
qpr G
xGGxG
Grafos aleatorios con grados prefijadosGrafos aleatorios con grados prefijadosGrafos aleatorios con grados prefijadosGrafos 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 prefijadosGrafos aleatorios con grados prefijadosGrafos aleatorios con grados prefijadosGrafos 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 prefijadosGrafos aleatorios con grados prefijadosGrafos aleatorios con grados prefijadosGrafos 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,dmin1)k(kd i
n
1ki
k
1ii
Es posible construirlo conexo ssi además se tiene
k
1ii 1)2(nd
Grafos aleatorios con grados prefijadosGrafos aleatorios con grados prefijadosGrafos aleatorios con grados prefijadosGrafos 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 prefijadosGrafos aleatorios con grados prefijadosGrafos aleatorios con grados prefijadosGrafos 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.
ModelosModelosModelosModelos
Una fracción mínima de los modelos existentes.
[Albert, Barabási, Rev. Mod. Phys 2002]
ModelosModelosModelosModelos
Medidas de centralidadMedidas de centralidadMedidas de centralidadMedidas 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 centralidadMedidas de centralidadMedidas de centralidadMedidas 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:
),(maxdad(u)excentrici uvdistVv
Vv
vudistV
),(1
)promedio(u distancia
Máximo que me tardo en llegar a u
Promedio que tardo en ir de u a cualquier otro
Medidas de centralidadMedidas de centralidadMedidas de centralidadMedidas 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 centralidadMedidas de centralidadMedidas de centralidadMedidas de centralidad
a
e
b
d
c f
a b c d e f
a 0 1 1
b 1 0 1
c 0 1
d 1 1 1 0 1
e 1 0 1
f 1 0
a b c d e f
a 0 1 2 1 1 3
b 1 0 2 1 2 3
c 2 2 0 1 2 3
d 1 1 1 0 1 2
e 1 2 2 1 0 1
f 3 3 3 2 1 0
Floyd
prom
2,4
1,4
1,2
2
1,8
1,6
max 322333
Centro
Baricentro
Medidas de centralidadMedidas de centralidadMedidas de centralidadMedidas 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 centralidadMedidas de centralidadMedidas de centralidadMedidas 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
ji k
k jiCjiC
B),(),(
L. C. Freeman, Sociometry 40, 35 (1977)
Medidas de centralidadMedidas de centralidadMedidas de centralidadMedidas de centralidad
Betweenness centrality
Se distribuye como ley de potencia en redes variadas (no en todas!)
Medidas de centralidadMedidas de centralidadMedidas de centralidadMedidas 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 centralidadMedidas de centralidadMedidas de centralidadMedidas de centralidad
Matriz de adyacencia: caso dirigido
00000
10000
01010
00001
00110
A
1
2
3
45
1
2
3
45
01000
10100
01011
00101
00110
A
Matriz de adyacencia: caso no dirigido
Medidas de centralidadMedidas de centralidadMedidas de centralidadMedidas 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 centralidadMedidas de centralidadMedidas de centralidadMedidas de centralidad
0210021
00313131
00010
10000
0021210
P
qt+11 = 1/3 qt
4 + 1/2 qt5
qt+12 = 1/2 qt
1 + qt3 + 1/3 qt
4
qt+13 = 1/2 qt
1 + 1/3 qt4
qt+14 = 1/2 qt
5
qt+15 = qt
2
La distribución estacionaria se obtiene como el vector propio por la izquierda asociado al valor propio 1: qP=q
v1v2
v3
v4v5
Medidas de centralidadMedidas de centralidadMedidas de centralidadMedidas de centralidad
¿Qué pasa si caigo en un callejón sin salida?
Salida fácil: salto a un nodo cualquiera, escogido al azar.
0210021
00313131
00010
00000
0021210
P
0210021
00313131
00010
5151515151
0021210
P'
Medidas de centralidadMedidas de centralidadMedidas de centralidadMedidas 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).
5151515151
5151515151
5151515151
5151515151
5151515151
2100021
00313131
00010
5151515151
0021210
'P' )1(
Medidas de centralidadMedidas de centralidadMedidas de centralidadMedidas de centralidad
The Anatomy of a Large-Scale Hypertextual Web Search EngineBrin, S., Page, L. (Computer Networks and ISDN Systems, 1998)
Abstract:
In this paper, ...
The Anatomy of a Large-Scale Hypertextual Web Search EngineBrin, S., Page, L. (Computer Networks and ISDN Systems, 1998)
Abstract:
In this paper, we present Google, a prototype of a large-scale search engine which makes heavy use of the structure present in hypertext. Google is designed to crawl and index the Web efficiently and produce much more satisfying search results than existing systems. The prototype with a full text and hyperlink database of at least 24 million pages is available at http://google.stanford.edu/ [sigue]
•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.
[Luego ha evolucionado, pero PageRank sigue siendo la base.]
Medidas de centralidadMedidas de centralidadMedidas de centralidadMedidas 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 centralidadMedidas de centralidadMedidas de centralidadMedidas 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:
jij
ji ah:
•Las autoridades recolectan de los hubs:
ijj
ji ha:
•Itero hasta converger.
Medidas de centralidadMedidas de centralidadMedidas de centralidadMedidas 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
rrrT222
T111 vuσvuσvuσA
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 centralidadMedidas de centralidadMedidas de centralidadMedidas de centralidad
Los vectores singulares detectan las principales tendencias lineales en filas y columnas de la matriz A.
HITS encuentra la principal tendencia lineal.
σ1
σ2v1
v2
•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.
ComunidadesComunidadesComunidadesComunidades
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.
ComunidadesComunidadesComunidadesComunidades
Hasta cierto punto se parece al viejo problema de machine learning, clustering.
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”.
o
espacio vectorial n-dimensional
métricamétrica
ComunidadesComunidadesComunidadesComunidades
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).
ComunidadesComunidadesComunidadesComunidades
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 espectralComunidades: método espectralComunidades: método espectralComunidades: 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 espectralComunidades: método espectralComunidades: método espectralComunidades: método espectral
Coeficiente de expansión del grafo G=(V,E):
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.
UV,Umin
U-VU,EminGα
VU
Comunidades: método espectralComunidades: método espectralComunidades: método espectralComunidades: 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 ij), y A es la matriz de adyacencia.
De modo que
~0
),(1 Eji
jid
Li
ij
L es simétrica (estamos suponiendo G no dirigido) y semi definida positiva los valores propios son 0.
Comunidades: método espectralComunidades: método espectralComunidades: método espectralComunidades: 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
xxLxx
minLxxminλ T
T
wx
T
1x,wx2
11
(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 espectralComunidades: método espectralComunidades: método espectralComunidades: método espectral
Notemos que aquí xw1 significa que i i 0x
xxLxx
minλ T
T
wx2
1
Con un poco de manipulación es posible ver que
Ej)(i,
2T )(Lxx ji xx
así que definimos el vector de Fielder como el vector propio asociado a 2; es el que da el mínimo en
ii
ji
xx x
xx
i2
Ej)(i,
2
0,02
)(
min
Comunidades: método espectralComunidades: método espectralComunidades: método espectralComunidades: método espectral
La gracia es que al minimizar
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:
Ej)(i,
2)( ji xx
222 λ2dλα
2λ
Comunidades: método espectralComunidades: método espectralComunidades: método espectralComunidades: método espectral
Ejemplo
1
2
34
5
10100
01100
11301
00011
00112
L
26.024.071.042.045.0
26.024.071.042.045.0
81.032.0020.045.0
14.054.0070.045.0
44.070.0034.045.0
V
17.4 ,31.2 ,00.1 ,52.0 ,00.0E
Comunidades: método espectralComunidades: método espectralComunidades: método espectralComunidades: método espectral
Otro ejemplo:A
B
C
G
F
E
D
A -0.3682 1
B -0.2808 1
C 0.3682 2
D 0.2808 2
E 0.5344 2
F 0.0000 ?
G -0.5344 1
A B C D E F G
A 3 -1
0 0 0 -1
-1
B -1
3 0 -1
0 0 -1
C 0 0 3 -1
-1
-1
0
D 0 -1
-1
3 -1
0 0
E 0 0 -1
-1
2 0 0
F -1
0 -1
0 0 2 0
G -1
-1
0 0 0 0 2
Comunidades: método espectralComunidades: método espectralComunidades: método espectralComunidades: 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 espectralComunidades: método espectralComunidades: método espectralComunidades: 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.
UVd,Udmin
U-VU,EminG
U
2
2
μ18
Comunidades: método espectralComunidades: método espectralComunidades: método espectralComunidades: 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 aglomerativosComunidades: métodos aglomerativosComunidades: métodos aglomerativosComunidades: 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 aglomerativosComunidades: métodos aglomerativosComunidades: métodos aglomerativosComunidades: 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 "single-linkage clustering").
¿Qué pesos? Se han propuesto varios.
Cantidad de caminos nodo-disjuntos, o arista-disjuntos, 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
1
00
1
aAaAAaWi
L
i
LL
Comunidades: evaluaciónComunidades: evaluaciónComunidades: evaluaciónComunidades: 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 UV tenga más conexiones internas que hacia el exterior; es decir, que
),(),(2 UVUEUUE
Se habla de comunidad débil ; se habla de fuerte cuando cada nodo de U muestra la preferencia en sus links.
Comunidades: evaluaciónComunidades: evaluaciónComunidades: evaluaciónComunidades: evaluación
También se ha hecho notar lo siguiente: si definimos
iUj
ji dUd )(
entonces la probabilidad de que una "pata" de una arista escogida al azar esté en Ui esEUd i 2)(
Por lo tanto, la probabilidad de que ambas estén en Ui es
22 4)( EUd i
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ónComunidades: evaluaciónComunidades: evaluaciónComunidades: evaluación
Newman & Girvan (Phys Rev E, 2004) definen
k
i
iiik
E
UdE
UUEUUQ
12
2
14
)(,(),(
Es posible demostrar que si iUVUEUUE iiii ),(),(2
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ónComunidades: evaluaciónComunidades: evaluaciónComunidades: 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
Pero de momento Q es lo más usado.
Volviendo al caso de los algoritmos aglomerativos: elijo la altura de corte que maximiza Q.
k
i i
iiiik U
UVUEUUEUUD
11
),(,(2),( Zhenping Li et al,
Phys Rev E, 77, 036109, 2008 "Quantitative function for community detection".
Comunidades: métodos divisivosComunidades: métodos divisivosComunidades: métodos divisivosComunidades: 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 divisivosComunidades: métodos divisivosComunidades: métodos divisivosComunidades: 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 "arista-disjuntos".
(b) recupera lo observado sociológicamente (salvo por un nodo que queda mal clasificado).
Comunidades: métodos divisivosComunidades: métodos divisivosComunidades: métodos divisivosComunidades: métodos divisivos
Comunidades: métodos divisivosComunidades: métodos divisivosComunidades: métodos divisivosComunidades: 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 divisivosComunidades: métodos divisivosComunidades: métodos divisivosComunidades: 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ónComunidades: compresiónComunidades: compresiónComunidades: 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ónComunidades: compresiónComunidades: compresiónComunidades: 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ónComunidades: compresiónComunidades: compresiónComunidades: 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ónComunidades: compresiónComunidades: compresiónComunidades: 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ónComunidades: compresiónComunidades: compresiónComunidades: 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ónComunidades: compresiónComunidades: compresiónComunidades: 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.
ComunidadesComunidadesComunidadesComunidades
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/0408187IDEA: 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 enhttp://www.cscs.umich.edu/~crshalizi/notabene/community-discovery.html
Comunidades - complementoComunidades - complementoComunidades - complementoComunidades - 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 - complementoComunidades - complementoComunidades - complementoComunidades - complemento
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).
0 1 2 3
Comunidades - complementoComunidades - complementoComunidades - complementoComunidades - complemento
k-componentes:
Dos nodos están en la misma k-componente 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 - complementoComunidades - complementoComunidades - complementoComunidades - 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,
jik
ijikijx,
2)AA(
Distancia euclidiana
ji
kjjkiik
ij
nx
)A)(A(1
Correlación de Pearson
Comunidades - complementoComunidades - complementoComunidades - complementoComunidades - 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)
N
l il
ijij
A
AP
1
)(
1
1,
il
N
lji jBI
d
Se puede demostrar que da
donde I es la matriz de identidad, y B(j) es la matriz P pero con la columna j anulada.
Comunidades - complementoComunidades - complementoComunidades - complementoComunidades - complemento
A su vez esa redefinición de distancia permite redefinir similaridad:
2),(
,
2
,,
N
ddji
N
jik kjki
H. Zhou, Phys. Rev. E 67, 061901 (2003)H. Zhou, Phys. Rev. E 67, 041908 (2003)
Etc.
Comunidades - complementoComunidades - complementoComunidades - complementoComunidades - 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 - complementoComunidades - complementoComunidades - complementoComunidades - 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”
coni el grado de los nodos al interior de sus comunidades•ki el grado de los nodos•si la comunidad en que participa el nodo is la desviación de i dentro de la comunidad s.
Comunidades - complementoComunidades - complementoComunidades - complementoComunidades - complemento
zi: qué tan conectado está el nodo dentro de su cluster.
zi > 2.5 hub (esto es empírico)
Pi: que tan “comprometido” está con su cluster.
~1: poco compromiso, se conecta parejo con todos los clusters.~0: 100% comprometido
Observan distintos roles:
Comunidades - complementoComunidades - complementoComunidades - complementoComunidades - complemento
ultraperiféricosperiféricos satélite
conector
hub provincial hub global
Comunidades - complementoComunidades - complementoComunidades - complementoComunidades - 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!Comunidades – otro poco!Comunidades – otro poco!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 networksM. E. J. NewmanPhys. 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ónNewman glotónNewman glotónNewman 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
i
iiik E
Ud
E
UUEUUQ
1
2
1 2
)(),(),(
Newman glotónNewman glotónNewman glotónNewman 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ónNewman glotónNewman glotónNewman glotón
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
l
lllk E
Ud
E
UUEUUQ
1
2
1 2
)(),(),(
k
llllk aeUUQ
1
21 ),(
Newman glotónNewman glotónNewman glotónNewman glotón
•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
k
llllk aeUUQ
1
21 ),(
222** jjjiii aeaeaeQ
Pero a* = aii + ajj y e*=eii+eij+2eij, de modo que
2222 )2(2 jjjiiijjiiijjjii aeaeaaaaeeeQ
jiij aaeQ 2
Newman glotónNewman glotónNewman glotónNewman glotón
Además al fundir se tiene jileee jlill ,*
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ículoUn ejemplo que da Newman en su artículoUn ejemplo que da Newman en su artículoUn 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ónNewman glotónNewman glotónNewman 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 Comunidades en redes con pesoscon pesosComunidades en redes Comunidades en redes con pesoscon 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 j
jii ws ,
Comunidades en redes Comunidades en redes con pesoscon pesosComunidades en redes Comunidades en redes con pesoscon 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
k
i
iiik
E
Ud
E
UUEUUQ
12
2
14
)(),(),(
ji UUEeeji wUUf ),(
iUj
ji sUs )(
k
i
iiik
W
S
Us
S
UUfUUQ
12
2
1 4
)(),(),(
j
jsS2
1
Glotón de Newman, con pesosGlotón de Newman, con pesosGlotón de Newman, con pesosGlotó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
''),(2 jiji aaUUfQ
ji UUEeeji wUUf 2
1),(con
S
Usa i
i 2
)('
Glotón de Newman, con pesosGlotón de Newman, con pesosGlotón de Newman, con pesosGlotó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 co-ocurrencias.
““Método de Lovaina”Método de Lovaina”““Método de Lovaina”Método de Lovaina”
Un algoritmo aglomerativo empíricamente muy bueno, y también bastante rápido:
Fast unfolding of communities in large networksV. Blondel, J. Guillaume, R. Lambiotte, E. LefebvreJournal 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”Método de Lovaina”““Método de Lovaina”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”Método de Lovaina”““Método de Lovaina”Método de Lovaina”
•Inicio: n comunidades, una por cada nodo.
•Iteración:
DOPaso de optimizaciónPaso de agregación
WHILE (hice algo)
““Método de Lovaina”Método de Lovaina”““Método de Lovaina”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”Método de Lovaina”““Método de Lovaina”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”““Método de Lovaina”Método de Lovaina”
““Método de Lovaina”Método de Lovaina”““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.
•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”Método de Lovaina”““Método de Lovaina”Método de Lovaina”
““Método de Lovaina”Método de Lovaina”““Método de Lovaina”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”Método de Lovaina”““Método de Lovaina”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 Extracción de una una comunidadcomunidadExtracción de Extracción de una una comunidadcomunidad
•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 Extracción de una una comunidadcomunidadExtracción de Extracción de una una comunidadcomunidad
•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.
CU,Umin
|UU,E|min
C
VU
•Pero para evitar soluciones triviales, se castigaba el desnivel de tamaños:
•Eso es simétrico. ¿Qué pasa si me interesa que una de las partes sea una “buena” comunidad?
Extracción de Extracción de una una comunidadcomunidadExtracción de Extracción de una una comunidadcomunidad
Idea en Zhao et al, Community extraction for social networks, PNAS, 2011 (http://www.pnas.org/content/108/18/7321):
C
C
UU
UUE
U
UUE ,,22
Primero sugieren maximizar
pero eso tiene el problema de
así que lo que optimizan es
C
C
C
C
C UUEU
UUUE
UU
UUE
U
UUEUU ,
,2,,22
Extracción de Extracción de una una comunidadcomunidadExtracción de Extracción de una una comunidadcomunidad
•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 Extracción de una una comunidadcomunidadExtracción de Extracción de una una comunidadcomunidad
•Club de karate: modularidad anda bien, pero Zhao identifica los “núcleos”.
•Amistades en un curso de colegio: aquí Zhao brilla.