PDF de programación - Resumen Tema 6: Minería de estructura

Resumen Tema 6: Minería de estructura

José Alberto Benítez Andrades

Marzo 2011

En este trabajo se resumen las conclusiones obtenidas después de haber realizado la lectura de los
artículos propuestos 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. Denición y objetivos de la minería de estructura de la web.

La World Wide Web contiene una cantidad enorme de información, pero puede ser extremadamente
difícil para los usuarios el localizar recursos que sean de calidad y relevantes a las necesidades de
información. Esto sucede porque la Web es un corpus de hipertexto de gran tamaño y continua creciendo
exponencialmente. Pero la variación en las páginas es incluso peor que la escala de datos: el conjunto de
páginas web no tienen una estructura web unicada, con variabilidad en el estilo de autores y contenido
que es más grande que en las coleciones de documentos tradicionales. Este nivel de complejidad hace
imposible aplicar técnicas de un gestor de base de datos y recuperadores de nromación.

Para mejorarlo se han desarrollado algoritmos que explotan la estructura de hipervínculos de la
WWW para 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. Hay muchas maneras en que se puede
utilizar la estructura de enlaces en la web para inferir cuáles son las páginas más importantes, y algunas
son más efectivas que otras. La estructura de hipervínculos implica una estructura social subyacente
en la manera de crear las páginas y los enlaces. 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 denirí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. De acuerdo con el tipo de dato
estructural, la estructura de minería de la web puede ser dividida en dos tipos. El primer tipo consiste
en 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. El otro tipo es 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.

2. Denición, modelado y uso de las nociones de:

2.1. Autoridad (authoritative page), prestigio

No se quieren sólo localizar un conjunto de páginas relevantes sino que se quieren las páginas
relevantes de mayor calidad. Para limitar una búsqueda grande en Internet hasta un tamaño sensato

1

para un observador humano, se necesitan medios que identiquen las páginas más denitivas o
Autoridad. Típicamente, la creación de un enlace por el autor de una página web representa un tipo
implícito de aprobación, de la página a la que se apunta. Recolectando el juicio colectivo en el conjunto
de tales aprobaciones, se puede obtener una comprensión más profunda tanto de la relevancia como
de la calidad de los contenidos de la web. Un problema que surge es que las autoridades no suelen ser
particularmente auto-descriptivas. Por ejemplo no hay razón para encontrar Fabricantes japoneses
de automóviles en la página de Toyota u Honda. Esta dicultad ilustra los problemas que hay en
conar sólo en el texto mientras buscamos Autoridades. Por eso es interesante utilizar la información
de los enlaces. Pero también hay dicultad en usar la información de los hiperenelaces. Pese a que
muchos enlaces representan el tipo de aprobación que se decribía anteriormente, otros se crean por
razones que no tienen nada que ver con el otorgamiento de autoridad.

Estas consideraciones indican algunas de las dicultades con las que nos encontramos al buscar
páginas autoridades. Hay dicultades en la información de los hipervínculos. Mientras muchos enlaces
representan el tipo de respaldo que discutimos, otros son creados para razones que no tienen nada que
ver con el contenido de la web. Algunos enlaces existen sólo para propósitos navegacionales (Haga clic
para regresar al menú raíz) o como anuncios pagados(Las vacaciones de sus sueños están a un solo
clic de distancia) Lo que se espera es que en el sentido agregado, sobre un número lo bastante grande
de vínculos, nuestra perspectiva de vínculos como Dadores de autoridad se mantendrá.

¾ Cómo podemos realizar el mejor modelado en que una autoridad es conferida en la web? Como
expliqué anteriormente, las páginas web autorizadas no suelen ser muy auto-descriptivas; este caso se
repite también en las autoridades en los temas generales que frecuentemente no enlazan directamente
a otro. Está bastante claro el por qué esto debería ser cierto para cualquier tema con un aspecto
comercial o de competencia; AltaVista, Excite e InfoSeek pueden todas ser autorizadas para el tópico
motores de búsqueda, pero ellos no tienen interés en enlazarse entre ellos porque son competencia.

¾Cómo determinar que una página es una Autoridad? Podríamos decirlo porque un número de
páginas relativamente anónimas que son claramente relevantes a, por ejemplo, Motores de Búsqueda
tienen enlaces a Google, AltaVista, Excite e Infoseek. Tales páginas son un componente recurrente
de la web: Hubs o concentradores que enlazan a una colección de sitios prominentes en un tema
común. Pueden aparecer en una variedad de formas, desde listas de recursos profesionales, hasta
listas de vínculos recomendados en páginas web individuales. Los concentradores no necesitan ser
prominentes, o siquiera tener enlaces apuntándoles. Su característica distintiva es que son potentes
dadores de autoridad en un tema concreto. De esta manera, tienen un papel que es dual al de las
autoridades: Una buena Autoridad es aquella que es apuntada por muchos buenos concentradores. .
Esta relación mutuamente reforzada entre los hubs y las autoridades servirán como tema central en
nuestra exploración de métodos basados en enlaces para la búsqueda, la compilación automatizada de
recursos web de alta calidad, y el descubrimiento de comunidades web temáticamente cohesionadas.

2.2. Centralidad

Uno de los resultados importantes del análisis de hipervínculo de una red es la identicación de un
nodo central, o en este caso, un sitio web central, generalmente denido como el sitio que proporciona
la mayor parte de las conexiones y/o las conexiones más cortas a otros miembros del grupo(Scott, 1991;
Wasserman & Faust, 1994). El sitio web central usualmente juega el papel de concentrador, Autoridad
o sitio de prestigio. Existen varias medidas de centralidad.

El autovector de centralidad de Bonacci's se usa a menudo como un indicador global en el análisis de
hipervínculo de red. Es apropiado en aquellos casos donde la red esté simétricamente interconectada

2

y las frecuencias de las conexiones de los vínculos entre sitios web no sean binarias. Y que sean
relativamente densas (Bonacich & Lloyd, 2001). Sin embargo, esta métrica proporciona una descripción
inadecuada de una red direccional(O asimétrica) Como resultado, los enlaces direccionales pueden ser
analizados usando el grado de centralidad de Freeman. Mide el número de conexiones directas de
hipervínculos de un sitio web con otros en el grupo (Freeman, 1979).

La métrica de Freeman consiste en grado de centralidad entrante y saliente. El grado de centralidad
entrante se calcula basándose en el número de enlaces que un sitio web recibe de otro sitio web, mientras
que el saliente se determina con el número de vínculos que se originan en un sitio. Además de estos
valores están las métricas de proximidad (closeness) e interposición (betweeness).

La métrica de centralidad se utiliza para determinar qué sitio Web tiene el camino más corto a
todos los otros en el grupo. La métrica de centralidad de interposición se reere a la frecuencia con
con la que un sitio web se encuentra entre pares de otros sitios en el grupo y representa el potencial
para el control de comunicación, como un portero.(Freeman, 1979).

Finalmente, la centraldiad de Negopy de Richards es el número medio de vínculos requeridos para
alcanzar a cada uno de los otros sitios web en el grupo, de tal forma que cuanto más bajo sea el valor.
El sitio sera más central (Richards, 1995). La mayor parte de los WebSites agrupados, tales como los
sitios web de un departamento de una Universidad, están conectados al sitio central de tal forma que
los usuarios de Internet puedan navegar con pocos enlaces cuando están en uno de esos sitios.

2.3. Co-cita

El análisis de co-cita ha sido usado para mapear la relación temática de conjuntos de autores,
diarios o artículos. Ver [White & McCain1989] para una revisión de estas técnicas). Puede mostrar un
agrupamiento signicativo de autores relacionados por temas. [White & Grith1981].

Grafo de co-cita:
Nodos = Páginas web·Aristas no dirigidas(Ponderadas)= co-cita(ponderada)
La co-citación es utilizada para medir la similitud de dos documentos. Si los papeles i y j son
citados por un papel k, entonces ellos deben ser dichos para ser relacionados en algunos sentidos a
otro, incluso ellos no se citan directamente el uno al otro. En la gura siguiente se muestra que los
papeles i y j están co-citados por el papel k. Si el papel i y el papel j están citados juntos por otros
papeles, signica que i y j tienen una relación o son similares.

Dejar L ser la matriz de citación. Cada celda de la matriz es denida como : Lij = 1 si el papel i
cita al papel j, y L = 0 si es de otra manera. La Co-citación (denotada por C ij) es una medida similar
denidia como el número de papeles que co-citan i y j, y es computado con:

C ij =n

k=1 LkiLkj

3

donde n es el total de números de páginas. C ii es naturalmente el número de papeles que citan i.
Una matriz cuadrada C puede ser formad