HIBD
Hoja de ejercicios Map Reduce Año 2021/2022
13 de octubre de 2021 Máster TECI
Facultad de CC.
Matemáticas
. 1. Grado de los vértices de un grafo
Los grafos son estructuras que sirven para representar relaciones (aristas) entre objetos
(vértices). Los grafos se utilizan como modelo en multitud de áreas y existe una extensa
teoría que proporciona interesantes resultados y algoritmos. Los grafos pueden represen-
tarse de muchas formas diferentes, quizás la representación más conocida es la que utiliza
una matriz de adyacencia. Sin embargo, en este ejercicio vamos a considerar que un grafo
está representados como una listas de aristas.
Simplificar Estamos pensando en trabajar con grafos (más bien grandes), de los que ob-
tenemos las aristas (relaciones entre objetos) de una forma distribuida y quizás pro-
pensa a errores o duplicaciones. Un primer problema que tenemos que resolver es la
depuración y simplificación de los datos.
Suponemos que la lista de aristas original puede tener repeticiones, cambios de
orden y ciclos en un vértice. Queremos generar una lista de aristas con las siguientes
propiedades:
No hay aristas repetidas.
Los aristas muestran los nodos ordenados.
No hay ciclos en los vértices.
Escribe un programa con el esquema map-reduce que resuelva el problema de sim-
plificar una lista de aristas con respecto a los criterios anteriores.
Ejemplo Si la lista original es {(B, B), (B, A), (C , A), (A, B), (A, D), (B, C )}, un resul-
tado podría que ser {(A, B), (B, C ), (A, D), (A, C )}. Observa que puede haber distintas
soluciones dependiendo del orden que se elija para clasificar los nodos.
Grado de los vértices Una medida que puede asignarse a los vértices es la cantidad de
aristas a las que pertenece, lo que se conoce como el grado de un vértice.
Ejemplo Si la lista original es {(B, B), (B, A), (C , A), (A, B), (A, D), (B, C )}, y su ver-
sión simplificada es {(A, B), (B, C ), (A, D), (A, C )}, el resultado tendría que ser:
{(A, 3), (B, 2), (C , 2), (D, 1)}
Grado de los vértices agregado por arista Escribe un programa con el esquema map-
reduce que devuelva el grado de los vértices pero agregado por aristas. El formato de
1
la salida del algoritmo tiene que ser la lista de aristas con la información del grado
de cada uno de los nodos de la arista:
(nodo1 , nodo2 , grado del nodo1 , grado del nodo2 )
Ejemplo Si la lista original es {(B, B), (B, A), (C , A), (A, B), (A, D), (B, C )}, y su ver-
sión simplificada es {(A, B), (B, C ), (A, D), (A, C )}, el resultado tendría que ser:
{(A, B, 3, 2), (B, C , 2, 2), (A, D, 3, 1), (A, C , 3, 2)}
. 2. Análisis de ficheros log de acceso a páginas web
Toda la actividad que realizan los usuario en un servidor web queda reflejada en sus ficheros
log. Estos ficheros guardan información textual como la que aparece en la figura siguiente:
Figura 1: Fragmento de un fichero log.
Mientras que un libro suele tener entre 4000 y 6000 líneas, en un solo día, un servidor
apache de un sitio ’modesto’ como es [Link], puede general decenas de miles de
líneas. De forma simplificada, podemos decir que por cada petición que hace un usuario del
servidor, se registra una línea que contiene toda la información relacionada con la petición.
Los ficheros log tienen un formato muy concreto y son muy fácilmente legibles (aunque
mirando la imagen anterior cueste creerlo!). Miremos una única línea:
2
[Link] - - [27/Apr/[Link] +0200] "GET /moodle/ HTTP/1.1"200
8944 Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:34.0) Gecko/20100101 Firefox/34.0"
La información se estructura por columnas. Vamos a comentar algunas columnas que
serán de nuestro interés, para una información más detallada puede consultarse la docu-
mentación oficial ([Link]
En la primera columna aparece la dirección ip del cliente, lo que llamaremos usuarios.
En el ejemplo anterior [Link].
En la cuarta columna aparece la fecha y la hora en la que la petición de página se
ha realizado, [27/Apr/[Link] +0200].
En la quinta columna aparece la petición de página concreta que el usuario ha hecho,
"GET /moodle/ HTTP/1.1". De esta petición lo que más nos interesa es la página
pedida, en este caso /moodle/.
En la sexta columna aparece un código de respuesta, que indica si se ha podido
responder a la petición del usuario, si la página no existe, etc. (véase, por ejem-
plo, [Link] En
el ejemplo anterior el código de respuesta es 200, que indica que la página solicitada
ha sido enviada sin ningún problema.
El análisis de log es una actividad que interesa a muy diversos niveles: identificar las
páginas más visitadas, la carga del servidor en las distintas horas del día, los navegadores
utilizados por los usuarios. . . Vamos a hacerte algunas propuestas concretas:
Accesos totales a páginas web En primer lugar nos gustaría conocer qué páginas de
nuestro servidor son las más accedidas. Escribe un programa paralelo que nos di-
ga cuántos accesos exitosos (código de respuesta 200) ha tenido cada página.
Errores en accesos a páginas web Escribe un programa paralelo que nos diga cuántos
accesos erróneos (código de respuesta distinto a 200) ha habido cada día.
Usuarios por cada página web Contar el número total de accesos de cada página es im-
portante, pero también es importante la variedad, es decir, el número de usuarios
diferentes que visitaron la página. Suponiendo que cada usuario queda identificado
por una dirección ip, escribe un programa paralelo que nos diga el número de usuarios
diferentes que ha tenido cada una de las páginas.
Carga del servidor por fechas Para empezar, se quiere conocer el número total de páginas
que se sirven cada día. Escribe un programa paralelo que, para cada día, devuelva el
número total de accesos exitosos (código de respuesta 200) a las páginas del servidor.
Usuarios en un día Contar el número total de accesos de cada página en un día es intere-
sante, pero también es interesante saber el número de usuarios por día. Suponiendo
que cada usuario queda identificado por una dirección ip, escribe un programa para-
lelo que nos diga el número de usuarios diferentes que ha habido cada día.
3
Ranking de usuarios Suponiendo que cada usuario queda identificado por una dirección
ip, escribe un programa paralelo que nos diga los k usuarios que más accesos exitosos
a páginas hayan realizado.
Comportamiento por días Supongamos que estamos interesados en analizar el comporta-
miento de los usuarios por días. Para cada usuario, nos gustaría saber qué grupos de
páginas visita, con que frecuencia se conecta, si tiene un patrón definido de navega-
ción, si este patrón es parecido al de otros usuarios. . . Realmente no hace falta mucha
imaginación para pensar posibles aplicaciones de un análisis de estos resultados.
El comportamiento de un usuario puede definirse con muy diversos niveles de detalle.
Nosotros vamos a considerar simplemente que el comportamiento durante un día es
el conjunto de páginas web que solicita.
Escribe un programa paralelo que, a partir de unos ficheros log, devuelva los compor-
tamientos de cada usuario (el conjunto de páginas visitadas por día). Es decir, para
cada usuario y cada fecha, el programa nos informe de las páginas que ha visitado.
Comportamiento por días Para seguir con el estudio de los comportamientos de usuarios,
nos gustaría aglutinar la información y para cada usuario tener todos los comporta-
mientos que hemos encontrado en los ficheros log analizados.
Comportamiento por días Como último detalle del estudio de los comportamientos, nos
gustaría saber para cada usuario, las veces que cada comportamiento se repite.
