Susana Ladra - UVadataweb.infor.uva.es/wp-content/uploads/2013/03/GrafosWeb.pdf · no estructurados Los datos “científicos” suelen estar estructurados … pero los datos de la

Susana Ladra Laboratorio de Bases de Datos Universidad de A Coruña

Antes de empezar…

• Los científicos de datos deben saber trabajar con grandes volúmenes de datos no estructurados Los datos “científicos” suelen estar estructurados … pero los datos de la Web no!

• Texto, páginas Web, imágenes, etc.

• Debemos encontrar un significado a esos datos no estructurados – Necesitamos técnicas diferentes (ej: graph mining) Útiles para muchos campos: búsqueda en Web, redes

sociales, bioinformática, pattern matching…

¿Qué es un grafo Web?

• Web vista como un grafo: – Grafo dirigido – Nodos = páginas Web – Aristas = hipervínculos

– Analizando la estructura de la Web obtenemos

información muy interesante!

¿Cuál es su tamaño?

http://www.google.es/corporate/timeline

El número de páginas en la Web es INFINITO!

¿Cuántas conoce Google?


http://www.google.com/insidesearch/howsearchworks/thestory


• No tenemos acceso a todo el grafo de la Web

• Se suele estudiar a partir de snapshots estáticas de ciertas partes de la Web – Obtenidos tras procesos de crawling de la Web

– Ejemplo: uk-union-2006-06-2007-05 133.633.040 nodos y 5.507.679.822 aristas Representación clásica listas de adyacencia: Representación clásica matriz de adyacencia:

50 GB 2 PB

¿Cómo es el grafo de la Web?

• ¿Se adapta al modelo de grafo aleatorio? (Erdös-Rényi) – Los nodos se conectan de forma aleatoria con

probabilidad p – Probabilidad de que un nodo tenga grado k? Cada nodo tiene (N-1) intentos de obtener una arista Cada intento tiene probabilidad p de tener éxito… … sigue una distribución binomial!

kNk ppk

NpkNB −−−

−=− 1)1(

1);;1(


• ¿Se adapta al modelo de grafo aleatorio? (Erdös-Rényi)

grado de salida

frec

uenc

ia

frec

uenc

ia

grado de entrada

Siguen una power-law! La probabilidad de que un nodo tenga grado i es proporcional a 1/ix, con x > 1.


• ¿Se adapta al modelo de grafo aleatorio? (Erdös-Rényi)

NO! Evidencias: – Distribución power-law de las frecuencias de los

grados de los nodos – Existen varias componentes conexas y sus tamaños

también sigue una distribución power-law – Existen autoridades y hubs


• Se ajusta mejor a otros modelos:

– Scale-free

– Preferential attachment

– Evolving copying

– Small-world

… aún está por descubrir alguno mejor!


Broder et al, “Graph Structure of the Web”

Visión del grafo de la Web en el año 2000

203 millones de URLs

1.466 millones de links

Visualizando algunos grafos Web…

uk-2002

arabic-2005

indochina-2004

¿Y la matriz de un grafo Web? GRAFO ALEATORIO GRAFO WEB

REORDENANDO LOS NODOS DEL GRAFO WEB…

Lo que nos dicen los links…

• Dos de los algoritmos más usados sobre el grafo de la Web son:

– PageRank: Independiente de la query Permite establecer un ranking entre las páginas Web

– HITS: Dependiente de la query Obtiene las autoridades y los hubs


• PageRank: – A cada página se le da un valor de importancia – Una página es importante si le apuntan páginas

importantes

(Felipe Micaroni Lalli)


• PageRank:

3/2 + 2 + 5/2 + 1/3

5/2 + 10 + 1/3

3/2 + 1/3

?

?

?

6.3

12.8


• HITS: – Se aplica a un subgrafo del grafo completo después de

realizar una búsqueda – Se obtienen los hubs y autoridades para esa búsqueda

Hubs Autoridades

¿Cómo trabajar con grafos Web?

• Dificultades al trabajar con grandes grafos:

– Miles de millones de nodos y aristas en continuo crecimiento

– Los resultados intermedios pueden crecer exponencialmente en muchos casos

– Son complejos y difíciles de paralelizar

– Los algoritmos suelen tener una alta complejidad computacional (cuadráticos, … o incluso NP-completos)


• Existen diferentes estrategias: – Ordenadores de alto rendimiento

• Arquitecturas paralelas con memoria distribuida: la comunicación es el cuello de botella (hubs!)

• Arquitecturas multi-thread con memoria compartida: la memoria compartida es el cuello de botella ahora

– Bases de datos clásicas: los algoritmos sobre grafos requieren muchos joins

Más en “Big Graph Data panel” (ISWC 2012)


• Existen diferentes estrategias: – Bases de datos de grafos: esquemas rígidos, problemas

de organización de los datos, sirven para grafos pequeños

– Cloud computing (MapReduce/Hadoop/Pregel/Giraph): dificultad para particionar el grafo y tratar el dinamismo

– Memoria principal: demasiado grandes para usar algoritmos y estructuras clásicas de grafos

USAREMOS ESTRUCTURAS DE DATOS COMPACTAS! SE PUEDE COMPRIMIR EL GRAFO Y NAVEGARLO SIN DESCOMPRIMIR

Más en “Big Graph Data panel” (ISWC 2012)

Comprimiendo el grafo Web

• ¿Qué nos hace pensar que es compresible?

- Se repiten muchos links entre páginas del mismo sitio - La mayoría de los links apuntan a páginas “cercanas”


• Existen diferentes métodos: – Basados en listas de adyacencia

• Muy rápidos para obtener los links salientes • No permiten eficientemente otras operaciones

– Basados en matrices de adyacencia • Permiten todo tipo de operaciones: rangos, links

individuales, links salientes y entrantes… • No tan rápidos para obtener una lista de adyacencia

completa


• Existen diferentes métodos: – Basados en listas de adyacencia

Similitud entre listas de adyacencia Localidad de referencia (codificación diferencial) Muchos métodos: • WebGraph (Boldi y Vigna, 2004)

• Basados en RePair (Claude y Navarro, 2008)

• Utilizando BFS (Apostolico y Drovandi, 2009)

• Utilizando List Merging (Grabowski and Bieniecki, 2011)

Boldi, Vigna “The WebGraph framework I: Compression techniques”


• WebGraph (listas de adyacencia)

2-3 bits por arista!


• Existen diferentes métodos: – Basados en matrices de adyacencia

patrones verticales

patrones diagonales

filas similares

localidad de referencia


• k2-tree (matriz de adyacencia)

0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0

0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0

0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

01 1 1

1 1 10 0 0 01 0 0 01

1 1 1111 1 1 10 0 0 00 0 0 0 0 0 0

0100 01000011 0010 0010 10101000 0110 0010

Ejemplo con k = 2

T = 101111010100100011001000000101011110

L = 010000110010001010101000011000100100

Brisaboa et al.“k2-trees for Compact Web Graph Representation”



0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0

0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0

0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

01 1 1

1 1 10 0 0 01 0 0 01

1 1 1111 1 1 10 0 0 00 0 0 0 0 0 0

0100 01000011 0010 0010 10101000 0110 0010

T = 101111010100100011001000000101011110

L = 010000110010001010101000011000100100

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

0 1

2

3 4

5 6

7

8

9 10

11

12

13

14

15

0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34

rank(T,2)* k2 = 8

rank(T,9)*k2 = 28

rank(T,31)*k2 = 56 56 - |T | = 20



?

Matriz original: 2 PB Matriz comprimida: 800 MB

¿Y qué pasa con la Web social?

¿Y qué pasa con la Web social? Recordando los grafos Web: Visualizando los grafos sociales:

dblp

hollywood amazon


• Existen diferencias importantes con los grafos sociales – Suelen ser grafos complejos (etiquetas, multiarista) – No tienen una ordenación implícita de los nodos

• Los grafos sociales se adecúan bien al modelo de

“Small-world”

¡Teoría de los seis grados de separación!

¿Y qué pasa con la Web social? • Experimento de Milgram (1967)

– 296 personas en Nebraska y Boston tienen que mandar una carta a una persona en Massachusetts, 64 lo consiguen

– El número medio de intermediarios es 5.2

• En el 2003 se intentó repetir el experimento usando emails – 60.000 participantes, 24.000 cadenas, 384 llegaron a destino – Longitud media de la cadena: 4 intermediarios

• Un estudio reciente (2011) en el grafo de Facebook:

– Obtiene un valor de 3.74 intermediarios


• Los periodistas de datos también lo podrían usar!

esperemos que para extraer información

más relevante…

El Confidencial 08/03/2013


• ¿Qué podemos hacer? – Descubrir comunidades – Monitorizar cómo evoluciona – Ver cómo se propaga la información – Predecir actividades – Recomendar – Visualizar – …

Como científicos de datos…

• Ojo! Los datos no siempre vienen como registros “planos” de observaciones y variables

• Los grafos permiten expresar una mayor riqueza de relaciones y explorar los datos con otra óptica – Teoría de grafos, modelos y procesos estocásticos

• Trabajar con grafos a gran escala (Big Graph Data): – Podemos usar técnicas clásicas o típicas en Big Data – … o podemos conocer el grafo y usar técnicas más

adaptadas al grafo en cuestión

Como científicos de datos…

• Retos abiertos: – Modelos más adecuados para los grafos Web

– Algoritmos de minería de datos sobre grafos complejos

– Tecnologías para procesamiento de Big Graph Data

– Estructuras de datos compactas mejores y algoritmos que las naveguen eficientemente

– Visualización

– …

¿Preguntas?

Susana Ladra Laboratorio de Bases de Datos Universidad de A Coruña

Documents

Susana Ladra - UVadataweb.infor.uva.es/wp-content/uploads/2013/03/GrafosWeb.pdf · no estructurados Los datos “científicos” suelen estar estructurados … pero los datos de la