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

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?


"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


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].


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.


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


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).


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?


"p", exponencial "q", unimodal, cercana a normal, tal vez suma de

normales


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.


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


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.


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.


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


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).


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)


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


•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


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


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


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)


Betweenness centrality

Se distribuye como ley de potencia en redes variadas (no en todas!)


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.


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


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.


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


¿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'


¿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(


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.]


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


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.


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.


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.


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


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).


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.


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


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.


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).


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


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λ


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


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


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.


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


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.


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.


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...


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


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).



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


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


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é.


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


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.


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.


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.


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.


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


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)


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


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.


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.


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


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.


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:


ultraperiféricosperiféricos satélite

conector

hub provincial hub global


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

)(),(),(


•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.


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 ),(


•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


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).


•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).


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.


•Inicio: n comunidades, una por cada nodo.

•Iteración:

DOPaso de optimizaciónPaso de agregación

WHILE (hice algo)


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.


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.



•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).



•Color: idioma principal de la comunidad (francés, holandés).

•Se muestra la red de comunidades con al menos 100 miembros.


•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.


•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?


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


•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..


•Club de karate: modularidad anda bien, pero Zhao identifica los “núcleos”.

•Amistades en un curso de colegio: aquí Zhao brilla.

Documents

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