Modelo de Erdös-Renyi



Descargar 10,29 Mb.
Fecha de conversión31.05.2017
Tamaño10,29 Mb.

Modelo de Erdös-Renyi

  • Durante décadas el modelo de red aleatoria (que era la forma de pensar en las redes sociales, y redes grandes en general) fue el modelo Erdös-Renyi (1960).
  • Paul Erdös

Modelo de Erdös-Renyi

  • Tamaño de la mayor componente conexa:
  • 1 5 11 12
  • Diámetro de la mayor componente:
  • 0 4 7 1
  • Distancia promedio entre nodos conectados:
  • - 2 4.2 1
  • p=0, =0
  • p=0.045, =0.5
  • p=0.09, =1
  • p=1, =n=12

Modelo de Erdös-Renyi

  • Grado promedio : np.
  • Distribución de grados: binomial (aprox. Poisson).
  • E&R demostraron que:
    • Si np < 1, casi seguramente G(n,p) no tiene componentes conexas de tamaño mayor a O(log n).
    • Si np = 1, c.s. G(n,p) tiene una componente conexa máxima de tamaño ~ n2/3. Los tamaños de las c.c. siguen una ley de potencia.

Modelo de Erdös-Renyi

  • Si np > 1, c.s. G(n,p) hay una c.c "gigante", O(n), y la siguiente c.c. es O(log n).
  • Si p > (ln n)/n, c.s. G(n,p) es conexo. Si es <, entonces c.s. no lo es.
  • Nota: en lo anterior, el "casi seguramente" significa lo siguiente. El grafo G es una variable aleatoria. Que cumpla la propiedad "A" c.s. quiere decir que

Modelo de Erdös-Renyi

  • Durante décadas el modelo ER fue el único que se usó para modelas las redes "reales" (sociales, tecnológicas, biológicas).
  • Principalmente porque no había datos masivos para cotejar; sólo datos muy parciales, de grafos pequeños.
  • Cuando aparecieron datos masivos, se vio que sus características no coincidían con ER.
  • ¿Qué características?

Propiedades de redes

  • Cosas que se suelen mirar en una red (principales):
  • Principales:
    • Distribución de grados
      • grado promedio, grado máximo...
    • Distancia promedio y diámetro (distancia máxima)
    • Nivel de aglomeración (clustering)

Propiedades de redes

  • Cosas que se suelen mirar en una red (otras):
    • Correlaciones de grados (entre vecinos).
    • Componentes conexas, "comunidades".
    • Frecuencia de subgrafos (e.g., presencia de cliques).
  • . . .
  • X

Propiedades de redes

  • Salvo que se diga lo contrario, pensamos en grafos simples, no dirigidos, et voilà.
  • Cuando hay más propiedades, hay otras cosas que mirar. Por ejemplo:
    • En digrafos, correlación entre grados in/out.
    • Si hay más de un tipo de nodo, "mezcla" entre los tipos.
    • En grafos con pesos en las aristas, efecto de eliminar las más "débiles".
    • Etc, etc...

Distribución de grados

  • La distribución de grados en ER es una Poisson.
  • está concentrada en torno a su media
  • la probabilidad de encontrar un nodo con un grado muy chico o muy grande decae exponencialmente
  • Hay una "escala" característica en la distribución.

Distribución de grados

  • Lo que se observa en la mayoría de las redes reales es que los grados se distribuyen según una ley de potencia (power law; lineal en log-log):
  • f(k)~k- (por lo general 2    3)
  • La cola es "pesada" (no decae exponencialmente).
  • No hay escala característica. Se habla de distribuciones (o redes) "libres de escala" (scale free).

Distribución de grados

  • En algunas (pocas) redes se observa una distribución exponencial:
  • f(k) =  e-k
  • Se ve lineal en log-lineal
  • k
  • log f
  • λ

Distancia promedio

  • La distancia L entre dos nodos es la longitud del camino más corto entre ellos.
    • En una malla regular (digamos, un subconjunto conexo de tamaño n, tomado de Zd), ~ n1/d.
    • En ER, L ~ (log n)/(log k)
    • Esto coincide con lo observado en la mayoría de las redes reales (efecto "small world”).

Índice(s) de clustering

  • En muchas redes reales, se observa transitividad: si A y B son vecinos de C, suelen ser vecinos entre sí.
  • Hay más de una forma de medir esto. Las dos más típicas:
  • Sea ai la cantidad de posibles triángulos que incluyen al nodo i (si su grado es di, ai=di(di-1)/2).
  • Sea bi la cantidad de triángulos que incluyen al nodo i.
  • C(1) = / C(2) = el más usado

Índice(s) de clustering

  • 1
  • 2
  • 3
  • 4
  • 5
  • En ER, ambos valen p.
  • Pero no es lo que se suele observar 
  • N
  • k

Small Worlds

  • Stanley Milgram, 1967:
    • Experimento de envío de cartas entre desconocidos (de Nebraska a Boston).
    • La gente tenía que enviarle la carta a alguien con quien se "tuteara".
    • El 20% de las cartas llegó.
    • Cantidad promedio de pasos: 5.2.

Small Worlds

  •  "6 grados de separación".
    • La idea ya es parte del saber "público" (obra de teatro, películas, libros...)
    • Anecdóticamente, ya estaba ("el mundo es un pañuelo", etc.)
    • Compatible con ER, así que no causó problemas.
    • No es exclusivo de la red de amistades humanas:

Small Worlds

  • [M. Newman, 2003]

Otras propiedades

  • Mezcla, cuando hay nodos de más de un tipo:
  • Evaluar dependencia de esas v.a.
  • (hay varias aproximaciones)

Otras propiedades

  • Correlación entre grados
  • ¿Los nodos más conectados, se prefieren entre sí? ¿Y los menos conectados?
    • Pastoras et al: graficar el grado promedio de los vecinos, como función del grado
    • Newman: calcular coef. de correlación entre los extremos de las aristas.

Otras propiedades

  • Correlación (à la Newman)

Otras propiedades

  • Detección de comunidades
  • Amplia literatura proponiendo algoritmos.
  • Muchísimas aplicaciones!

Otras propiedades

  • Resistencia a fallas/ataques
  • Falla: eliminación aleatoria de un nodo/arista
  • Ataque: eliminación "pensada"
  • ¿Cómo afectan...
  • la conexidad?
  • el promedio de distancias?
  • el "flujo"?
  • Etc, etc

Otras propiedades

  • Comunicaciones por tierra y aire, EEUU
  • Red regular (casi lattice), vs una red "scale free" (sin escala)

Otras propiedades

  • Regular con fallas
  • SF con fallas
  • SF bajo ataque

Ejemplos

  • nodos: científicos
  • relación: haber sido coautores
  • Son las "redes de colaboración" (se han estudiado mucho).
  • Número de Erdös: distancia a Erdös, que viajó mucho, escribió ~1500 artículos, colaboró con más de 500 colegas.
  • Entre matemáticos en MathSciNet, el promedio es ~5.
  •  http://www.oakland.edu/enp/
  • 0 --- 1
  • 1 --- 504
  • 2 --- 6593
  • 3 --- 33605
  • 4 --- 83642
  • 5 --- 87760
  • 6 --- 40014
  • 7 --- 11591
  • 8 --- 3146
  • 9 --- 819
  • 10 --- 244
  • 11 --- 68
  • 12 --- 23
  • 13 --- 5

Ejemplos

  • "Oráculo de Bacon"
    • nodos: actores
    • relación: coincidir en alguna película listada en IMDB
  •  http://oracleofbacon.org/
  • La distancia promedio a Bacon es 2.8; el máximo es 8.
  • Distancia promedio entre actores: 3.48

Ejemplos

  • Nota: no hay nada de especial en Kevin Bacon!
  • M. Girvan and M. E. J. Newman
  • Community structure in social
  • and biological networks
  • Proc. Natl. Acad. Sci. USA 99
  • 8271-8276 (2002).

Ejemplos

  • Red terrorista (incluyendo a los autores del 11/9 gringo).
  • Una vista parcial de Internet
  • (imagen vía wikipedia)
  • Internet Mapping Project: http://research.lumeta.com/ches/map/gallery/index.html
  • The Political Blogosphere and the 2004 U.S. Election: Divided They Blog [Adamic & Glance, 2005]

Ejemplos

  • Asociaciones de palabras
  • Interacciones de proteínas
  • Colaboración científica

Ejemplos

Ejemplos

Ejemplos

  • Relaciones de pareja en un college norteamericano

Ejemplos

  • F. Liljeros et al, Nature, 2001: encuesta a 4781 suecos, edades 18-74.
  • Pregunta: # de parejas sexuales.
  • Colgate et al, PNAS, 1989: hombres en una clínica de ETS en Londres

Ejemplos

  • xkcd.com
  • De paso, esto ilustra otra área en que hay investigación: como dibujar redes complejas.

Ejemplos

  • Red de interacción de proteínas en Saccharomyces cerevisiae
  • http://www.visualcomplexity.com/
  • Muchos ejemplos en:

Redes complejas

  • Propiedades principales que por lo general comparten las redes complejas:
    • Diámetro y distancia media pequeños, O(log N)
    • Distribución de grados según ley de potencia, P(k)~k-
    • Alto nivel de clustering local
    • + Baja densidad, son redes “sparse”: cantidad de aristas es O(n).

Dicho sea de paso: no todo es scale free, etc!

  • (Y también mencionamos un caso con distribución de grados exponencial.)

Dicho sea de paso: redes bipartitas

  • Varios de los ejemplos podrían ponerse en términos de una red bipartita, con dos tipos de nodos: actores/películas, autores/papers.
  • La red de debajo de obtiene como una proyección de la de arriba.

Dicho sea de paso: redes bipartitas

  • Se pierde información: estamos transformando una relación n-aria en un conjunto de relaciones binarias. O en otros términos, un multigrafo en un grafo.
  • De paso, se introduce un nivel de clustering (la transitividad de la relación binaria sale de la n-aria).
  • A veces convendrá mantener la red en su forma bipartita (y la relación entre actores estará dada por su conexión común con una misma actividad/lugar/etc).

Redes complejas

  • El modelo ER resistió por muchos años, incluso durante los 80 y 90 cuando ya había datos y PCs con los cuales analizarlos.
  • Algunas pocas observaciones lo contradecían; e.g., Alfred Lotka en 1926:
    • "the number of scientists who have k citations falls off as
    • k -α for some constant α."
  • Fue básicamente la internet la que llevó a darse cuenta de que faltaban nuevos modelos.

Redes complejas

  • En los últimos 10 años, ha sido una revolución.

Small World

  • Modelo de small world de Watts & Strogatz (1998): parte con una malla regular, y modifica aristas (randomizándolas) con probabilidad p.
  • N = 1000 k =10
  • D = 100 L = 49.51
  • C = 0.67
  • N =1000 k = 8-13
  • D = 14 L = 11.1
  • C = 0.63
  • N =1000 k = 5-18
  • D = 5 L = 4.46
  • C = 0.01

Small World

  • Para ser más precisos:
  • En un anillo de N nodos, se conecta cada uno con sus k/2 vecinos a izquierda y derecha.
  • Se recorre el anillo (dando la vuelta).
  • Para cada nodo, para cada arista que lo conecta con un vecino a la derecha, con probabilidad p se reemplaza ese vecino por uno escogido al azar.
  • No se admiten loops ni aristas repetidas.
  • Duncan J. Watts & Steven H. Strogatz, Nature 393, 440-442 (1998)

Small World

  • L
  • C
  • p
  • regular SW random
  • Comparte el pequeño diámetro de ER, pero también el alto clustering de lo regular.
  • NOTA: con p=1, el grafo no es lo mismo que ER; en particular, el grado promedio es exactamente k. Pero se comporta muy parecido.

Small World

  • Otras formas de crear un SW:
  • Agregar pN aristas ("atajos") al anillo inicial, entre nodos escogidos al azar.
  • Agregar m nodos "centrales", conectados a pN nodos del anillo escogidos al azar.
  • Ambas garantizan que se mantenga la conexidad del grafo.

Scale Free

  • Lo que NO cumplen estos modelos de SW, y que se observa en redes reales, es una distribución de grados libre de escala: sigue siendo una Poisson!
  • En 1999 Barabasi & Albert proponen un modelo que genera un red SF (scale free, libre de escala).

Scale Free

  • Modelo Barabasi-Albert:
    • La red se construye progresivamente : se van agregando nodos.
    • Para un nuevo nodo se escogen m vecinos, de manera proporcional a sus grados.
    • Se habla de "preferential attachment"

Scale Free

  • También se habla de "the rich get richer".
  • [Además de intuitivo, hace justicia a Pareto, que notó una ley de potencia en la distribución de ingresos.]

Scale Free

  • P(k) ~k-3
  • A.-L.Barabási, R. Albert, Science 286, 509 (1999)

Scale Free

  • Algunos nodos se convierten en “hubs”, con muchas conexiones.
  • La mayoría es “pobre” en conexiones.
    • Se obtiene una distribución de grados que sigue una ley de potencia (es “scale free”).
  • P(k) ~k-3
    • Además se observa efecto small world.
    • No recupera el nivel alto de clustering; decae como n-¾ (más lento que en ER, pero igual es pequeño).

Scale Free

  • Nota: a diferencia de ER y WS, éste es un modelo generativo: sugiere un mecanismo de formación de la red.
  • Tener hartos amigos da popularidad; se pueden hacer más amigos.
  • Ser citado en un paper implica ser conocido; es más probable que me vuelvan a citar.
  • Un actor que ha actuado en muchas películas es conocido por el público y los directores, ergo...
  • Etc etc

Modelos

Modelos

  • Ninguno de los modelos (ER, WS, BA) reproduce las características más comunes de las redes reales:
    • Número de aristas ~ número de nodos
    • Conexas
    • Scale free
    • Diámetro pequeño
    • Alta clusterización
  • Existen muchos otros modelos; ninguno es tan simple o intuitivo como los iniciales.
  • Algunos son generativos, otros no.
  • Por lo general son específicos para alguna red real.

Modelos: Modularidad jerárquica

  • Ravasz, Somera, Mongru, Oltvai, Barabási
  • Hierarchical Organization of Modularity in Metabolic Networks
  • Science 297, 1551 (2002)
  • Modelo determinista (aunque se le puede agregar azar).
    • Parto con una clique de cinco nodos (uno "central").
    • Hago cuatro copias del grafo. Conecto los nodos periféricos de la nueva copia con el central.
    • Itero.

Modelos: Modularidad jerárquica

  • Scale free,
  • = 1+ln 4/ln 3
  • C (clustering promedio) constante, ~0.6
  • El clustering promedio de nodos de grado k es  k-1
    • Eso se ha observado en redes biológicas y se considera indicio de estructura modular jerárquica.

Modelos: Modularidad jerárquica

  • Functional modules of the kinome network
  • [Hee, Hak, 2004]

Modelos: Modularidad jerárquica

  • Asociaciones de palabras
  • Interacciones de proteínas
  • Colaboración científica

Modelos: Redes "apolónicas" (Apollonian networks)

  • Parto con un triángulo.
  • En cada paso:
    • escojo al azar un triángulo
    • le agrego un nodo dentro
    • lo uno a los tres vértices del triángulo
  • También cumple con todo.
  • Aparecen en empaquetamientos de esferas; son las redes de fuerzas en material granulado, etc.
  • Andrade et al, Phys. Rev. Lett. 94, 018702 (2005)
  • Apollonian Networks : Simultaneously Scale-Free, Small
  • World, Euclidean, Space Filling, and with Matching Graphs

Modelos: Activos e inactivos

  • Nodos activos e inactivos.
  • En un momento dado hay m nodos activos.
  • Parto con una clique de m nodos activos.
  • En cada paso
    • agrego un nuevo nodo (activo) que se conecta a los m actualmente activos
    • desactivo un nodo activo; lo escojo con prob. inversamente proporcional a a+ki
  • K. Klemm and V. Eguiluz, Phys. Rev. E 65, 036123 (2002)
  • Clustering alto
  • Scale free

Modelos: Fitness

  • Una crítica al modelo de Barabási&Albert es que los nodos más antiguos se benefician más:
  • ¿Cómo puede un novato llegar a ser grande?
  • (Google vs Altavista)
  •  Modelo con fitness (Buckley & Osthus): agregamos a cada nodo un fitness . Mantenemos el esquema de B&A, pero ahora la probabilidad de escoger un nodo es
  • También da scale free
  • Grado de un nodo con fitness  en tiempo t: ~ t/C

Modelos: Copia

  • Modelo "copión" (Kleinberg):
  • Cada nodo tiene idéntico grado de salida d.
  • Cada nodo nuevo elige uno de los ya existentes (de forma uniforme) como prototipo.
  • Para su i-ésimo link, con probabilidad  copia el i-ésimo link del prototipo, con probabilidad 1- elige al azar.

Modelos: Copia

  • La distribución de grados de entrada queda scale free con exponente = (2-)/(1-).
  • Se creó como modelo de la web (páginas temáticas).
  • Funciona bastante bien para comunidades temáticas en la web, y también para algunas otras redes reales.
  • Produce muchos subgrafos bipartitos, observados en la web.
  • No reproduce el nivel de clustering.

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
  • O, si lo que tenemos es la secuencia k1, k2,... de grados de los nodos, entonces la condición es que

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

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

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
  • Es posible construirlo conexo ssi además se tiene

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:
  • 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

  • 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
  • 3
  • 2
  • 2
  • 3
  • 3
  • 3
  • Centro
  • 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
  • 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 dirigido
  • 1
  • 2
  • 3
  • 4
  • 5
  • 1
  • 2
  • 3
  • 4
  • 5
  • Matriz de adyacencia: caso no dirigido

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

  • 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
  • La distribución estacionaria se obtiene como el vector propio por la izquierda asociado al valor propio 1: qP=q
  • v1
  • v2
  • v3
  • v4
  • v5

Medidas de centralidad

  • ¿Qué pasa si caigo en un callejón sin salida?
  • Salida fácil: salto a un nodo cualquiera, escogido al azar.

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

Medidas de centralidad

  • The Anatomy of a Large-Scale Hypertextual Web Search Engine
  • Brin, S., Page, L. (Computer Networks and ISDN Systems, 1998)
  • Abstract:
  • In this paper, ...
  • 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 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 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:
  • Las autoridades recolectan de los hubs:
  • Itero hasta converger.

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.
  • 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.
  • HITS encuentra la principal tendencia lineal.
  • σ1
  • σ2
  • v1
  • 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.

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

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):
  • 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
  • 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
  • (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

  • Notemos que aquí xw1 significa que
  • Con un poco de manipulación es posible ver que
  • así que definimos el vector de Fielder como el vector propio asociado a 2; es el que da el mínimo en

Comunidades: 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:

Comunidades: método espectral

  • Ejemplo
  • 1
  • 2
  • 3
  • 4
  • 5

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

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

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
  • 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
  • entonces la probabilidad de que una "pata" de una arista escogida al azar esté en Ui es
  • Por lo tanto, la probabilidad de que ambas estén en Ui es
  • 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
  • Es posible demostrar que si
  • 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
  • Pero de momento Q es lo más usado.
  • Volviendo al caso de los algoritmos aglomerativos:
  •  elijo la altura de corte que maximiza Q.
  • Zhenping Li et al, Phys Rev E, 77, 036109, 2008 "Quantitative function for community detection".

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 "arista-disjuntos".
  • (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/community-discovery.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

  • 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 - 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 - 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,
  • Distancia euclidiana
  • 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)
  • 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 - complemento

  • A su vez esa redefinición de distancia permite redefinir similaridad:
  • 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.
  • 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 - complemento

  • ultraperiféricos
  • periféricos
  • satélite conector
  • hub provincial
  • hub global

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.



Compartir con tus amigos:


La base de datos está protegida por derechos de autor ©absta.info 2019
enviar mensaje

    Página principal