World Wide Web y la minería Web

En este trabajo se resumen las conclusiones obtenidas después de haber realizado la lectura de los artículos Soumen Chakrabarti “Mining the Link Structure of the World Wide Web” , Ravi Kumar “The Web as a Graph” y Broder “Graph Structure in the web”.

1. Definición y objetivos de la minería de estructura de la web.

El World Wide Web es un corpus de hipertexto de gran tamaño y en continua expansión. Esto significa que está formado por un conjunto de páginas web sin ningún tipo de estructura unificada y además con variabilidad en el estilo y contenido. Este nivel de complejidad hace imposible aplicar técnicas de un gestor de base de datos y recuperadores de información a los que estábamos acostumbrados en los procesos tradicionales.

Para intentar solucionarlo se han desarrollado algoritmos que explotan la estructura de hipervínculos de la WWW y así se intenta solucionar el descubrimiento de información y categorización, la construcción de listas de recursos de alta calidad y el análisis de las comunidades online enlazadas. Y es en este último aspecto donde se han desarrollado los avances más significativos. La estructura de hipervínculos implica una estructura social subyacente para crear páginas y los enlaces a otras webs de otros autores. El objetivo es desarrollar técnicas que se aprovechen de lo que observamos sobre la organización social intrínseca en la web mientras diseñamos algoritmos que minen información de los hiperenlaces.

La minería de estructura de la Web se definiría entonces como el proceso de usar la teoría de grafos para analizar los nodos y la estructura de conexión de un sitio web. Es decir, representaremos las webs como Nodos de un grafo y las conexiones como vértices. Para generar este tipo de estructura tendremos que realizar el siguiente procedimiento:

• Extraer patrones de los hipervínculos en la web. Un hipervínculo es un componente estructural que conecta la página web a una localización diferente.
• Minar la estructura del documento. Consiste en usar la estructura en forma de árbol para analizar el XML o el HTML dentro de la página web.
• Aplicar una métrica a la información obtenida.

3. Ranking de páginas web basado en enlaces:

3.1 PageRank

PageRank ha emergido como el modelo de análisis de enlace dominante para los motores de búsqueda, particularmente debido a la evaluación de consultas independientes de las páginas web, para evitar el spamming.

Se basa en la naturaleza democrática de la web utilizando su estructura de enlaces como indicador de la calidad individual de cada página. PageRank interpreta hiperenlaces de una página x a una página y como un voto, de la página a; a la página y. Sin embargo, PageRank busca un número de votos legal, o enlaces que reciba una página. También analiza las páginas que emiten el voto. Los votos emitidos por las páginas que son de importante peso ayudan a las otras páginas para tener mejor puntuación. Esta es la idea del ranking de prestigio en las redes sociales.

3.2 Algoritmo de PageRank

PageRank es un ranking estático de páginas web en el sentido de que un valor de PageRank es computado por cada página off-line y no depende de las consultas de búsqueda. Para este algoritmo se puede otorgar como un valor de "prestigio" a cada página. Los principales conceptos en los contextos web son los siguientes:

• In-Links de la página i: Son los hiperenlaces que apuntan a una página i de otras páginas. Usualmente, los hiperenlaces de un mismo sitio no son considerados.
• Out-Links de la página i: Son los hiperenlaces que apuntan a otras páginas desde una página i. Usualmente, los hiperenlaces de un mismo sitio no son considerados.

Desde otra perspectiva, aplicando el concepto de prestigio existe la siguiente derivación del algoritmo de PageRank:

• Un hiperenlace de una página apuntando a otra página es un transporte de autoridad a la página de destino. Así, los enlaces de entrada que recibe una página i, dan más prestigio de lo que la página i tenía antes de ello.
• Las páginas que apuntan a una página i también tienen sus puntuaciones de prestigio en el poder. Una página con un prestigio alto que apunta a una página i es más importante que una página con poco prestigio que apunta a i. En otras palabras, una página es importante si es apuntada por otras páginas que son importantes.

Acorde con estas afirmaciones, la importancia de las páginas i, es determinado resumiendo las puntuaciones de PageRank de todas las páginas que apuntan a i. Una página que apunta a muchas otras páginas, reparte el prestigio que tiene sobre todas las páginas a las que apunta.

Para formular las ideas explicadas, tratamos la Web como un grafo directo G = (V,E) donde V es un conjunto de vértices o nodos, por ejemplo, V es el conjunto de todas las páginas y E es el conjunto de enlaces directos (los hiperenlaces) . Sabiendo que el número de páginas totales en la Web es de . El PageRank de la página es definido por: donde es el número de enlaces salientes de la página j. Matemáticamente, usamos un sistema de n ecuaciones lineales con n incógnitas. Este sistema lo podemos representar mediante un matriz de ecuaciones sabiendo que P es una columna de vectores n-dimensionales de valor del PageRank. Por ejemplo Dado A como la matriz de adyacencia de nuestro grafo con: Nosotros podemos escribir el sistema de n ecuaciones con y definir el propio sistema. Para solucionarlo podemos aplicar un algoritmo iterativo pensando que 1 es el mayor valor y el PageRank es el vector P.

Ahora bien, ¿Cumple todas las condiciones para aplicarlo a un grafo con información web?. No. Para introducir estas condiciones nos vamos en la cadena de Markov.

En esta cadena, cada página web o nodo en el grafo es recordado como un estado. Un hiperenlace es una transición que lleva de un estado a otro con una probabilidad. Esto modela una navegación web aleatoria, navegando por la red como un estado de transición. Cada probabilidad de transición es (asumiendo que el navegante cuando hace click en los hiperenlaces en la página i uniformemente de forma aleatoria). Dada una matriz de probabilidad de transición de estados A, una matriz cuadrada de la siguiente manera: Aij representa la probabilidad de transición de un usuario en el estado i al estado j.

Dada un vector de distribución de probabilidad inicial y una matriz de probabilidad de transición A, tendremos: Para todas aquellas páginas web que tengan enlaces de salida.

Una vez definidas las igualdades, si la matriz A que estamos analizando cumple las condiciones de la ecuación diremos que A es una matriz estocástica de la cadena de Markov. Otro detalle muy importante a tener en cuenta es que en el grafo nunca se podrán calcular nodos que no posean ningún enlace en el sistema. Si los hubieran, podremos realizar dos procedimientos:

• Eliminar los nodos que impiden el cálculo. Estas páginas no afectarán el proceso de computación del Pagerank de otra página de forma directa. Los enlaces de salida de otras páginas apuntando a esas páginas también serán borrados. Después de que el PageRank se haya computado, estas páginas y los hiperenlaces que apuntan a estas, pueden ser añadidos al grafo.
• Añadir un conjunto completo de enlaces de salida de cada página. Por ejemplo le añadimos a todos los nodos un enlace a las páginas X, Z y W y, de este modo, la probabilidad de transición de ir de una página i a cada página es 1/3 asumiendo una probabilidad uniforme.

3.3 PageRank como algoritmo iterativo

Para implementar este concepto, tenemos primero que tener claro dos conceptos

• Un grafo directo G=(V,E) está directamente relacionado si y solo si, para cada par de nodos , hay una ruta de u a v.
• Un estado i es periódico con k > 1 si k es el número más pequeño de todas las rutas que hay desde el estadio anterior a i hasta i teniendo la longitud que es k. Si el estado no es periódico, es aperiódico.

Así, el valor del PageRank de las páginas web puede ser creado usando un método de iteración, que produce el principal vector propio con el valor propio de 1. El algoritmo es simple. Comenzamos con un valor de asignación de PageRank y la iteración termina cuando el valor de PageRank deja de variar. El algoritmo sería el siguiente:

5. Análisis de comunidades en la web

Internet da cobijo a un gran número de comunidades con un interés común manifestándose como un conjunto de páginas web. A pesar de que muchas comunidades son definidas explícitamente (grupos de noticias, colecciones de recursos en portales, etc) la gran mayoría son implícitos. Identificar estas comunidades ayudaría a entender la evolución social e intelectual de la web y proporcionar información detallada a un conjunto de gente con ciertos intereses en el punto de mira. Pero claro, debido al continuo flujo evolucionarlo de internet, es difícil encontrar y analizar estas comunidades usando únicamente esfuerzo manual.

Una posible solución al problema consiste en tratar la web como un enorme grafo dirigido. Se basa en que las comunidades web temáticamente cohesivas contienen en su núcleo un denso patrón de enlaces de Hubs(Concentradores) a Autoridades.

Para poner esto en un lenguaje más orientado a la teoría de grafos: Se usa la noción de grafo bipartito dirigido ( Grafo cuyos nodos puedan ser divididos en dos conjuntos A y B de forma que cada enlace en el grafo se dirige del nodoA al nodo B. Dado que las comunidades que se buscan contienen grafos bipartitos dirigidos con una gran densidad de aristas, se espera que muchos de ellos contengan subgrafos más pequeños que sean de hecho completos: Cada nodo en A tiene un enlace a cada nodo en B. Usando algoritmos de "poda"(Una variante del Backtracking mejorado sustancialmente) (pruning) se pueden enumerar todos los subgrafos de la Web en un PC Standard en unos tres días de ejecución.

7 Áreas de investigación relacionadas

Como bien hemos ido viendo a lo largo de todo este curso, la Minería de Estructura se encuentra dentro del término global de Minería de la Web. que está compuesto por tres tipos de minería:

• Minería Web de Contenidos (WCM, Web Content Mining).

Clasifica los documentos automáticamente o construye una base de información web multicapa
• Minería Web de Estructura (WSM. Web Structure Mining).

Extrae la estructura de una página web. WUM descubre patrones de acceso a las páginas en los usuarios
• Minería Web de Uso (WUM. Web Usage Mining).

En resumen WSM extrae la estructura de los hiperenlaces, es decir, cómo están los documentos estructurados respecto a los otros (estructura interdocumental a diferencia de la estructura intra documental de WCM). La estructura se representa como un grafo de los enlaces en un sitio web o entre sitios web. WSM revela más información que la información contenida en los documentos: por ejemplo, los enlaces que apuntan a un documento pueden indicar la popularidad o importancia de un documento. mientras que los enlaces salientes indican la riqueza o variedad de los temas que contiene. Esto nos lleva a una organización jerárquica por temas que puede ser inferida directamente de los patrones de enlazado. Es posible incluso no especificar los documentos mediante palabras clave, sino mediante documentos ejemplares.