View
5
Download
0
Category
Preview:
Citation preview
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?
¿Cuál es su tamaño?
http://www.google.com/insidesearch/howsearchworks/thestory
¿Cuál es su tamaño?
• 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(
¿Cómo es el grafo de la Web?
• ¿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.
¿Cómo es el grafo de la Web?
• ¿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
¿Cómo es el grafo de la Web?
• Se ajusta mejor a otros modelos:
– Scale-free
– Preferential attachment
– Evolving copying
– Small-world
… aún está por descubrir alguno mejor!
¿Cómo es el grafo de la Web?
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
Lo que nos dicen los links…
• 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)
Lo que nos dicen los links…
• PageRank:
3/2 + 2 + 5/2 + 1/3
5/2 + 10 + 1/3
3/2 + 1/3
?
?
?
6.3
12.8
Lo que nos dicen los links…
• 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)
¿Cómo trabajar con grafos Web?
• 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)
¿Cómo trabajar con grafos Web?
• 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”
Comprimiendo el grafo Web
• 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
Comprimiendo el grafo Web
• 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”
Comprimiendo el grafo Web
• WebGraph (listas de adyacencia)
2-3 bits por arista!
Comprimiendo el grafo Web
• Existen diferentes métodos: – Basados en matrices de adyacencia
patrones verticales
patrones diagonales
filas similares
localidad de referencia
Comprimiendo el grafo Web
• 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”
Comprimiendo el grafo Web
• 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
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
Comprimiendo el grafo Web
• k2-tree (matriz de adyacencia)
?
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
¿Y qué pasa con la Web social?
• 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
¿Y qué pasa con la Web social?
• Los periodistas de datos también lo podrían usar!
esperemos que para extraer información
más relevante…
El Confidencial 08/03/2013
¿Y qué pasa con la Web social?
• ¿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
Recommended