Aplicación de algoritmos genéticos a la identificación de la estructura de enlaces en portales web

232 Revista Española de Documentación Científi ca, 34, 2, abril-junio, 232-252, 2011 ISSN: 0210-0614. doi: 10.3989/redc.2011.2.779 Aplicación de algoritmos genéticos a la identifi cación de la estructura de enlaces en portales web María del Rocío Martínez-Torres*, Beatriz Palacios-Florencio*, Sergio L. Toral-Marín**, Federico José Barrero-García**. Resumen: Este trabajo explora la estructura de enlaces de los portales web considerándolos como grafos interconectados y analizando sus características como una red social. A partir de cada dominio raíz se extraerán dos redes: la primera, una red de dominios y la segunda, una red de páginas accesibles desde el dominio raíz. Sobre ambas redes se evaluarán una serie de parámetros desde la perspectiva del análisis de redes sociales para caracterizar la estructura del portal. El análisis factorial proporciona la metodología estadística adecuada para extraer los principales perfi les de portales web a partir de sus características como grafo. No obstante, y debido al gran número de indicadores que se pueden obtener, la búsqueda exploratoria de los factores latentes implicaría contemplar un número de posibilidades extremadamente elevado que imposibilitaría la obtención de una solución óptima. Por ello, en este trabajo se propone la utilización de una búsqueda genética sobre el conjunto de indicadores de partida. Los algoritmos genéticos son capaces de proporcionar un subconjunto de indicadores que optimizan una función objetivo. Los resultados obtenidos categorizan los portales webs corporativos en cuanto a su estructura de enlaces y destacan las posibilidades de los algoritmos genéticos como herramienta para descubrir nuevo conocimiento. Palabras claves: Análisis de enlaces, estructura de portales web, análisis factorial, algoritmos genéticos. Applying genetic algorithms for the identifi cation of Websites’ structure Abstract: This paper explores website link structure, whereby websites are considered as interconnected graphs and their features are analyzed as a social network. For each root domain, two different networks are extracted: the fi rst being the domain network and the second, the page network. In each case, a series of indicators taken from social network analysis is evaluated in order to characterize the website structure. Factor analysis may provide an appropriate statistical methodology for extracting in graphic form the principal profi le of the website in terms of its internal structure. However, the large number of indicators generated by such an exploratory search would lead to a prohibitive number of possibilities. Therefore, this work proposes the use of genetic * Escuela Universitaria de Estudios Empresariales, Universidad de Sevilla, Avda. San Francisco Javier s/n, 41018 Sevilla, España. [email protected] y [email protected]. ** E. S. Ingenieros, Universidad de Sevilla, C/ Enriquez de Ribera, 1, 41092, Sevilla, España. toral@ esi.us.es y [email protected]. Recibido: 10-04-2010; 2.ª versión: 07-06-2010; aceptado: 15-02-2011. 05_Rev_34_2_779.indd 23205_Rev_34_2_779.indd 232 06/05/11 10:4406/05/11 10:44 Aplicación de algoritmos genéticos a la identifi cación de la estructura de enlaces en portales web Rev. Esp. Doc. Cient., 34, 2, abril-junio, 232-252, 2011. ISSN: 0210-0614. doi:10.3989/redc.2011.2.779 233 algorithms. By using this guided search over a given space of possible solutions, genetic algorithms can provide a subset of indicators able to optimize a fi tness function. The results categorize corporate websites in terms of their link structure and highlight the possibilities for using genetic algorithms as a tool for knowledge discovery. Keywords: Link analysis, Website structure, factor analysis, genetic algorithms. 1. Introducción El análisis de los enlaces web es el estudio cuantitativo de hipervínculos entre páginas web. Por lo general, el análisis de los enlaces forma parte del denominado «Webometrics», que es el análisis cuantitativo (Almind e Ingwersen, 1997) y cualitativo (Pinto-Molina y otros, 2004) de los fenómenos web, ocupándose también del análisis de citas web, la evaluación de motores de búsqueda y los estudios puramente descriptivos de la web (Björneborn y Ingwersen, 2004; Thelwall, 2008). Los enlaces web han sido muy estudiados durante los últimos años con el fi n de comprender la estructura y los patrones de crecimiento de la web (Thelwall, 2004), aplicándose en particular al desarrollo de los algoritmos de clasifi cación de páginas. Este rápido desarrollo experimentado por el análisis de enlaces web en cuanto a teorías, tecnologías y metodologías podría explicarse por el hecho de ser una disciplina estudiada desde distintos puntos de vista, como la informática, las ciencias de la información, los estudios de comunicación o la sociología (Thelwall, 2004). El análisis de las redes sociales (SNA, Social Network Analysis) ha sido frecuentemente utilizado para el estudio del análisis de enlaces (Park y Thelwall, 2004; Toral y otros, 2010). SNA es un conjunto de procedimientos de investigación para la identifi cación de las estructuras de los sistemas sociales basados en las relaciones entre los componentes del sistema, también conocidos como nodos. En la aplicación de métodos SNA para el análisis de enlaces, los dominios web y las páginas web dentro de cada portal se consideran los actores, representados por los nodos en el grafo de la red social, mientras los enlaces son modelados como la relación entre actores, representados por las líneas que unen esos nodos (Iacobucci, 1994; Martínez-Torres y otros, 2010). El grafo resultante será un grafo dirigido (con un sentido asociado a cada línea que une dos nodos), porque los vínculos están defi nidos por una etiqueta HTML que apunta a una nueva página, defi niendo de este modo el sentido de cada línea (en los grafos dirigidos, las líneas suelen denominarse arcos). La mayoría de los estudios relacionados con enlaces web se centran en la estructura de la web considerada a gran escala. Así por ejemplo, en estudios previos se han analizado las relaciones entre los dominios web de instituciones académicas nórdicas (Ortega y Aguillo, 2008), o incluso de Universidades a nivel mundial (Ortega y Aguillo, 2009) desde la perspectiva del SNA. En Baeza-Yates y Castillo (2007), los dominios webs de países se analizan atendiendo a varios criterios, en particular, grados de los nodos y rankings. La reputación de la página es otro tema relacionado con el análisis 05_Rev_34_2_779.indd 23305_Rev_34_2_779.indd 233 06/05/11 10:4406/05/11 10:44 M.ª DEL ROCÍO MARTÍNEZ-TORRES, B. PALACIOS-FLORENCIO, S. L. TORAL-MARTÍN, F. J. BARRERO-GARCÍA 234 Rev. Esp. Doc. Cient., 34, 2, abril-junio, 232-252, 2011. ISSN: 0210-0614. doi:10.3989/redc.2011.2.779 de enlaces frecuentemente recogido en la literatura. En este caso, el SNA ha sido aplicado también considerando el método de grados de entrada (Indegree), que considera el número de enlaces sobre una página como medida de su popularidad. Se trata de una alternativa a los métodos de Pagerank (Berlt y otros, 2010), introducido por Google para caracterizar numéricamente la popularidad de páginas web. Finalmente, el análisis de enlaces a través del SNA ha sido combinado con el análisis semántico del texto para mejorar los algoritmos de recuperación de información web (Almpanidis y otros, 2007). Aunque existen bastantes estudios acerca de la estructura de la web o entre dominios web, comparativamente poco se sabe a nivel de la estructura interna de los portales web como organización de información y como mecanismos de acceso a esa información. En este trabajo se propone un estudio exploratorio para la identifi car la estructura de enlaces web dentro de un portal usando el análisis factorial. Para este propósito, las estructuras de hipertexto de 80 portales web institucionales de Universidades españolas se han extraído tanto a nivel de subdominios y dominios externos como a nivel de páginas web. Frente a otros portales institucionales, los portales universitarios garantizan una amplia variedad en la muestra, gracias a que la autonomía universitaria permite que el diseño y evolución de su portal web sea decisión autónoma de los órganos de gobierno de cada Universidad. Asimismo, históricamente las Universidades han sido organizaciones con una presencia activa en la web desde prácticamente sus inicios (Goldfarb, 2006). Los portales web se modelarán como dos redes sociales. En la primera red, los nodos representan subdominios o dominios externos y los arcos los enlaces entre ellos. La segunda red es parecida pero considera páginas web en lugar de dominios o subdominios. A partir de estas dos redes se puede derivar un elevado número de indicadores de su estructura atendiendo a parámetros típicamente medibles desde la perspectiva del SNA. No obstante, y debido a la naturaleza exploratoria de este estudio, es difícil seleccionar un subconjunto de indicadores que proporcione una solución satisfactoria mediante la aplicación del análisis factorial. No se garantiza si un subconjunto diferente podría proporcionar una solución más coherente y la alternativa de considerar todos los posibles subconjuntos de soluciones resultaría computacionalmente prohibitiva. Como solución se propone el uso de una técnica de búsqueda guiada como los algoritmos genéticos, capaz de proporcionar un subconjunto de indicadores que optimice una función de coste multi-objetivo. El resultado obtenido proporciona nuevos conocimientos sobre los patrones estructurales de portales web y pone en relieve la utilidad de los algoritmos genéticos como herramienta para el descubrimiento de nuevos conocimientos. Así pues, el objetivo del trabajo es doble. En primer lugar, se pretende defi nir un sistema experto basado en algoritmos genéticos capaz de determinar un conjunto de indicadores óptimo en la aplicación del análisis factorial a un conjunto de indicadores que caracterizan redes sociales. Esta solución óptima se refi ere a explicar un valor elevado de la varianza de los datos con un conjunto de factores que sean interpretables. El segundo objetivo consiste en aplicar este sistema experto a la identifi cación de patrones estructurales en los portales web corporativos de la Universidades españolas. 05_Rev_34_2_779.indd 23405_Rev_34_2_779.indd 234 06/05/11 10:4406/05/11 10:44 Aplicación de algoritmos genéticos a la identifi cación de la estructura de enlaces en portales web Rev. Esp. Doc. Cient., 34, 2, abril-junio, 232-252, 2011. ISSN: 0210-0614. doi:10.3989/redc.2011.2.779 235 El resto del documento está estructurado de la siguiente manera: el apartado 2 proporciona una breve descripción de la metodología propuesta. En concreto, se describe cómo modelar un portal web como un grafo, las características medibles desde la perspectiva del SNA y la metodología del análisis factorial. El apartado 3 está dedicado a la aplicación de algoritmos genéticos al problema de extraer un subconjunto óptimo de variables capaz de explicar las dimensiones latentes de la estructura web. El caso de estudio y los resultados se discuten en el apartado 4. Finalmente, las conclusiones se detallan en el apartado 5. 2. Metodología de análisis de la estructura de portales web usando SNA Las redes que representan portales web se extraen comenzando a partir de un dominio raíz (dominio propio de un portal web institucional) y continuando luego con los enlaces de salida a otras páginas. Para cada portal web se consideran dos tipos de redes diferentes. La primera es la llamada red de dominios, en la cual los nodos representan subdominios o dominios externos diferentes al dominio raíz de partida. Los arcos representan el enlace entre ellos. La segunda red es la llamada red de páginas, que contiene todas las páginas web del portal web institucional y los enlaces entre ellas. Obviamente, ambas redes son grafos dirigidos y pueden ser extraídos hasta un nivel profundidad deseada (entendiendo por profundidad el número de enlaces necesarios para alcanzar una página desde el domino raíz). En ambos casos, la construcción de la red está limitada al dominio raíz. Esto signifi ca que aunque se tienen en cuenta enlaces a otros dominios o páginas fuera del dominio raíz (y por tanto se incluyen en las redes consideradas), los enlaces de salida desde estos últimos no serán seguidos y no formarán parte de la red a analizar. 2.1. SNA Una red social se puede representar como un grafo G = (V, E) donde V denota un conjunto fi nito de vértices y E denota un conjunto de líneas de modo que E ⊆ V × V. Matemáticamente, los grafos se suelen conceptualizar como matrices (Nooy y otros, 2005), como se muestra en la Ecuación (1). M = (mi, j )n × n donde n = V , m i, j = { 1 si (v1, vj) ∊ E 0 en otro caso (1) En caso de un grafo valuado, la función de peso w(e) está defi nida en el conjunto de líneas entre nodos, i.e. w (e) = Exℜ, y la matriz anterior queda por tanto defi nida como se muestra en la Ecuación (2). m i, j = { w (e) if (v1, vj) ∊ E 0 en otro caso (2) 05_Rev_34_2_779.indd 23505_Rev_34_2_779.indd 235 06/05/11 10:4406/05/11 10:44 M.ª DEL ROCÍO MARTÍNEZ-TORRES, B. PALACIOS-FLORENCIO, S. L. TORAL-MARTÍN, F. J. BARRERO-GARCÍA 236 Rev. Esp. Doc. Cient., 34, 2, abril-junio, 232-252, 2011. ISSN: 0210-0614. doi:10.3989/redc.2011.2.779 En el contexto de análisis de enlaces web, la red de dominios es una red en forma de estrella con el dominio raíz en el centro de la estrella y el resto de los dominios enlazados a ella. Varios indicadores relativos al tamaño de la red de dominios se han extraído en términos de número de nodos y arcos. Normalmente, los portales web institucionales suelen incluir subdominios que deberían tratarse aparte de los dominios externos. Esta distinción se ha tenido en cuenta en el tamaño medido en número de nodos. Finalmente, la densidad y el grado medio de los nodos se han considerado también como posibles indicadores. La densidad hace referencia al número de líneas y el grado, al número de arcos en los que cada vértice está involucrado. Por lo que respecta a la red de páginas, se trata de una red mucho más compleja, con mucho mayor tamaño y número de enlaces que la red de dominios. Esto también permite obtener mayor riqueza de información relativa a sus características como red social: • Tamaño: el número de nodos representa el número de páginas web incluidas en el portal (o referenciadas si se trata de otros dominios) y los arcos representan las interrelaciones entre esas páginas. Un parámetro importante que determina el tamaño de la red es el nivel de profundidad para el que se extraen las páginas pertenecientes a cada portal web. En este estudio hemos usado una profundidad de siete. Este valor es considerado sufi ciente para captar la información esencial de la estructura del sitio web y es mayor que la profundidad de cinco usada en algunos estudios previos (Yang y Qin, 2008). • Densidad: es una media del número de líneas en una red simple, expresada como una proporción del número máximo posible de líneas. Las fi guras 1.a) y 1.b) detallan una red de baja y alta densidad, respectivamente. El principal problema de esta defi nición es que no tiene en cuenta las líneas valuadas con valor superior a 1 y que depende del tamaño de la red. Una medida diferente de densidad se basa en la idea del grado de un nodo, que es el número de líneas que inciden (grado de entrada) o salen (grado de salida) de él (Toral y otros, 2009a). Mayores grados de nodos producen redes más densas, porque los nodos involucran más arcos, y el valor medio del grado de los nodos de una red no es una medida dependiente del tamaño de la red. Como la red de páginas es un grafo dirigido, varias medidas estadísticas sobre la distribución del grado de salida de los nodos serán consideradas. Finalmente, la densidad puede ser también medida desde la perspectiva del SNA usando un punto de vista egocéntrico. La densidad egocéntrica de un nodo es la densidad de sus conexiones entre sus vecinos (Nooy y otros, 2005). • Componentes: Un componente fuerte es una subred fuertemente conectada de tamaño máximo. Se dice que una red está fuertemente conectada si cada par de vértices está conectado por un camino teniendo en cuenta el sentido de los arcos (Nooy y otros, 2005). En el contexto de este estudio, el análisis de los componentes de la red permite la identifi cación de subes05_Rev_34_2_779.indd 23605_Rev_34_2_779.indd 236 06/05/11 10:4406/05/11 10:44 Aplicación de algoritmos genéticos a la identifi cación de la estructura de enlaces en portales web Rev. Esp. Doc. Cient., 34, 2, abril-junio, 232-252, 2011. ISSN: 0210-0614. doi:10.3989/redc.2011.2.779 237 tructuras conectadas dentro del portal web. La fi gura 1.c) detalla el componente formado por los vértices v3, v4 y v5. • K-Núcleos (k-cores): un k-núcleo es una subred en la que cada nodo tiene k grados dentro de esa subred. El núcleo con mayor grado representa el núcleo central de la red. Los k-núcleos han sido utilizados en trabajos previos para detectar subredes entre portales web académicos de países nórdicos (Ortega y Aguillo, 2008). La fi gura 1.d) detalla un k-núcleo, con k = 3. • Distancia: se defi ne como el número de pasos en el camino más corto entre dos nodos de la red. En el caso de los portales web, existe un claro nodo principal defi nido por el dominio raíz. Consecuentemente tiene sentido medir la distancia del resto de páginas respecto a ese nodo. • Centralidad cercana (Closeness centralization): es un índice de centralidad basado en el concepto de distancia. La centralidad cercana de un nodo se calcula considerando el total de distancias entre un nodo y todos los demás nodos, donde la distancia más larga ofrece una menor puntuación de centralidad cercana. La centralidad cercana es un índice defi nido para toda la red y se calcula como la variación en la centralidad cercana de los vértices dividida por la variación máxima posible en la puntuación de centralidad cercana en una red del mismo tamaño (Toral y otros, 2009b). • Grado de Intermediación (Betweenness): es una medida de la centralidad que reside en la idea de que un nodo es más central en la medida en que actúe como intermediario en una red de comunicación (Nooy y otros, 2005). Es decir, la centralidad de un nodo depende de la medida en la que es necesario como enlace para facilitar la conexión de otros nodos dentro de la red. Si se defi ne una geodésica como el camino más corto entre dos nodos, la centralidad de intermediación de un vértice es la proporción de todas las geodésicas entre pares de nodos que incluyen este nodo, y la centralidad en la intermediación de una red es la variación en la centralidad de intermediación de los nodos dividida por la máxima variación posible en la centralidad de intermediación en una red del mismo tamaño. Desde la perspectiva del análisis de enlaces esta medida permite detectar pasarelas que conectan a redes separadas (Faba-Pérez y otros, 2005). • Correlación entre particiones: una partición de una red es una clasifi cación o clustering de los nodos en una red, de modo que cada nodo se asigna únicamente a una clase o cluster (Toral y otros, 2010). Existen dos particiones signifi cativas que pueden extraerse a partir de la red de páginas. La primera es la partición de los k-vecinos a partir del dominio raíz, en la cual los nodos son clasifi cados usando la distancia al nodo raíz. La segunda es la partición del grado de salida en la cual los nodos son clasifi cados atendiendo a su valor de grado de salida. La correlación entre ambas particiones es defi nida como la medida en la cual el sitio web sigue una estructura en forma de árbol desde el dominio raíz. Se evaluarán dos tipos de índices de asociación referenciados en la literatura: la V de Cramer y el índice de información de Rajski (Nooy y otros, 2005). La V de Cramer mide la depen05_Rev_34_2_779.indd 23705_Rev_34_2_779.indd 237 06/05/11 10:4406/05/11 10:44 M.ª DEL ROCÍO MARTÍNEZ-TORRES, B. PALACIOS-FLORENCIO, S. L. TORAL-MARTÍN, F. J. BARRERO-GARCÍA 238 Rev. Esp. Doc. Cient., 34, 2, abril-junio, 232-252, 2011. ISSN: 0210-0614. doi:10.3989/redc.2011.2.779 dencia estadística entre dos clasifi caciones. El índice de Rajski mide el grado por el cual la información de una clasifi cación se preserva en la otra clasifi cación. Sólo se considerará la versión simétrica del índice de Rajski. FIGURA 1 Representación gráfi ca de algunas características medibles en redes sociales V3 V4 V5 V1 V8 V10 V9 V7 a) Red con baja densidad b) Red con alta densidad c) Componentes d) K-núcleos 2.2. Análisis factorial El análisis factorial es una manera de ajustarse a un modelo de datos multivariados, estimando su interdependencia. Esto aborda el problema de analizar la estructura de interrelaciones entre un número de variables usando un conjunto de dimensiones subyacentes comunes, los factores, los cuales no son directamente observables, segmentando una muestra en segmentos relativamente homogéneos (Rencher, 2002). Ya que cada factor puede afectar a varias variables en común, estos son conocidos como «factores comunes». Se asume que cada variable es dependiente en una combinación lineal de factores comunes y los coefi cientes son conocidos como «loadings» o cargas factoriales (Martínez-Torres y Toral, 2010a). El análisis del factor puede ser usado tanto para exploración como para propósitos confi rmatorios: A diferencia de los análisis confi rmatorios, los análisis exploratorios no establecen ninguna constante a priori en la estimación de fac05_Rev_34_2_779.indd 23805_Rev_34_2_779.indd 238 06/05/11 10:4406/05/11 10:44 Aplicación de algoritmos genéticos a la identifi cación de la estructura de enlaces en portales web Rev. Esp. Doc. Cient., 34, 2, abril-junio, 232-252, 2011. ISSN: 0210-0614. doi:10.3989/redc.2011.2.779 239 tores o del número de factores a ser extraídos (Toral y otros, 2009c). La naturaleza exploratoria de este estudio tiene varias implicaciones: • El elevado número de indicadores relacionados con SNA que pueden extraerse de las dos redes consideradas. Los antecedentes teóricos existentes no permiten descartar previamente indicadores antes de comenzar el análisis factorial. • El número de factores latentes es desconocido. De nuevo, la falta de antecedentes teóricos sufi cientes signifi ca que los factores deberían ser seleccionados atendiendo a la homogeneidad de sus indicadores. En la siguiente sección se propone el uso de algoritmos genéticos para buscar una solución óptima y resolver esos problemas. 3. Metodología de búsqueda genética de las dimensiones latentes en portales web Un Algoritmo Genético (AG) es una abstracción computacional de una evolución biológica que puede utilizarse para resolver algunos problemas de optimización. La técnica fue primeramente introducida por Holland (1975) para su uso en sistemas adaptativos, y se basan en los principios de la evolución natural y la supervivencia de los más fuertes. Por imitación de este proceso, los Algoritmos Genéticos son capaces de ir creando soluciones para problemas del mundo real. Trabajan con una población de individuos, cada uno de los cuales representa una solución factible a un problema dado. A cada individuo se le asigna un valor o puntuación, relacionado con la bondad de dicha solución (es el valor de fi tness, que cuantifi ca su valor como solución al problema). En la naturaleza esto equivaldría al grado de efectividad de un organismo para competir por unos determinados recursos. El algoritmo comienza con una población inicial que se selecciona al azar desde el espacio de posibles soluciones. A partir de ella, las siguientes operaciones combinan la información genética de los elementos que la componen para formar nuevas generaciones. • En la operación de reproducción, los individuos compiten por reproducirse basándose en sus valores de fi tness, de modo que aquellos individuos que representen mejores soluciones tienen mayores probabilidades de supervivencia. • La operación de recombinación implica a dos individuos que intercambian parte de su información genética. La selección de los individuos padre también se realiza acorde a sus valores de fi tness y, como resultado, proporcionan dos indi viduos hijos con parte de su información genética intercambiada. La operación de recombinación permite que trozos de la información genética que contribuyan a buenas soluciones pervivan a lo largo de la evolución. 05_Rev_34_2_779.indd 23905_Rev_34_2_779.indd 239 06/05/11 10:4406/05/11 10:44 M.ª DEL ROCÍO MARTÍNEZ-TORRES, B. PALACIOS-FLORENCIO, S. L. TORAL-MARTÍN, F. J. BARRERO-GARCÍA 240 Rev. Esp. Doc. Cient., 34, 2, abril-junio, 232-252, 2011. ISSN: 0210-0614. doi:10.3989/redc.2011.2.779 En general, cuanto mayor sea la adaptación de un individuo al problema, mayor será la probabilidad de que el mismo sea seleccionado para reproducirse y recombinarse, cruzando su material genético con otro individuo seleccionado de igual forma. Este cruce producirá nuevos individuos descendientes de los anteriores, los cuales comparten algunas de las características de sus padres. Cuanto menor sea la adaptación de un individuo, menor será la probabilidad de que dicho individuo sea seleccionado para la reproducción y, por tanto, de que su material genético se propague en sucesivas generaciones. De esta manera se produce una nueva población de posibles soluciones, la cual reemplaza a la anterior y verifi ca la interesante propiedad de que contiene una mayor proporción de buenas características en comparación con la población anterior. Así a lo largo de las generaciones las buenas características se propagan a través de la población. Favoreciendo el cruce de los individuos mejor adaptados, van siendo exploradas las áreas más prometedoras del espacio de búsqueda. Si el Algoritmo Genético ha sido bien diseñado, la población convergerá hacia una solución óptima del problema. El AG usa una estrategia elitista que signifi ca que el mejor individuo es siempre reproducido a la generación siguiente, de modo que siempre se conserva la mejor solución obtenida a lo largo de la evolución. El algoritmo se detiene cuando se satisface algún criterio de parada de su ejecución (Martínez-Torres y Toral, 2010b). Para una correcta aplicación de los algoritmos genéticos, es preciso tener en cuenta varias cuestiones: • Codifi cación de los individuos, es decir, cómo se van a codifi car los individuos de una población de modo que esta codifi cación permita recoger el conjunto de soluciones posibles al problema. • Selección de la función de fi tness, de modo que represente la bondad de las soluciones según el problema planteado. • Selección de los valores de los parámetros (tamaño de la población, número de iteraciones, probabilidades, etc.). En este estudio, el uso del AG está justifi cado debido a su naturaleza exploratoria. De acuerdo a las características medibles detalladas en el apartado 2.1 se han obtenido un total de 64 indicadores. La elección de un subconjunto de indicadores para la realización del estudio exploratorio resultaría prohibitiva si se tratase de explorar la totalidad de soluciones posibles. El espacio de posibles soluciones está formado por 264 = 1,8447e + 019 posibilidades, que signifi can que deberíamos ejecutar 264 análisis factoriales diferentes para explorar completamente el espacio de posibles soluciones. A diferencia de esta alternativa, AG permite llevar a cabo una búsqueda guiada de la solución óptima con un menor coste computacional. La primera condición para aplicar AG adecuadamente es una buena selección de la codifi cación de individuos, la cual debería ser válida y completa. Nuestra codifi cación de los individuos está constituida por una secuencia binaria de 64 valores, en las que los «unos» representan las variables que van a ser usadas en el análisis factorial y los «ceros» representan variables que van a ser excluidas de 05_Rev_34_2_779.indd 24005_Rev_34_2_779.indd 240 06/05/11 10:4406/05/11 10:44 Aplicación de algoritmos genéticos a la identifi cación de la estructura de enlaces en portales web Rev. Esp. Doc. Cient., 34, 2, abril-junio, 232-252, 2011. ISSN: 0210-0614. doi:10.3989/redc.2011.2.779 247 Los indicadores asociados a cada factor se obtienen a partir de las cargas factoriales usando una rotación Varimax. Todos los indicadores asociados de esta manera con el mismo factor están bajo la hipótesis de que comparten un sentido común que el analista debe descubrir. Por otra parte, las puntuaciones de los factores se usan para categorizar la muestra original de Universidades, cada una de las cuales puede aproximarse a uno de los factores latentes identifi cados. Para comprobar la hipótesis nula de igualdad de medias entre los grupos de Universidades se ha llevado a cabo un análisis de la varianza (ANOVA). La hipótesis nula ha sido rechazada para todos los indicadores con un signifi cativo valor por debajo de 0,05. Usando la información de las cargas factoriales, así como los valores medios de las categorizaciones de Universidades, se pueden destacar las siguientes pautas de estructura en portales web (tabla V): El factor 1 representa una estructura distribuida del portal web, con una gran cantidad de nodos desarrollando un papel de intermediación. El alto valor de las correlaciones de las particiones (indicadores I23 e I25) signifi ca que el grado de salida crece a medida que nos alejamos del nodo raíz, lo que sugiere que las páginas de nivel inferior o intermedio (cerca del dominio raíz) actúan como directorios de información mientras que las páginas de nivel superior (lejos del dominio raíz) proporcionan información más detallada. Por otro lado, los altos valores medios y de desviación típica de la centralidad de intermediación (indicadores I16, I17 e I19) indican que el portal sigue una estructura tipo árbol, con vértices cada vez más conectados a medida que descendemos en niveles de profundidad. La fi gura 6.a) detalla una representación simbólica del portal. El factor 2 representa una estructura más centralizada en el sentido de la distancia al dominio raíz. Hay un núcleo de las páginas altamente interconectado, pero la información también se extiende a medida que avanzamos hacia niveles más profundos en la estructura. Los altos valores medios y de desviación típica de la centralidad cercana sugieren una estructura más plana, con caminos cortos para encontrar la información deseada. La representación simbólica de la fi gura 6.b) muestra este caso, con un camino reducido para alcanzar un nodo terminal B desde el nodo raíz A. El factor 3 se refi ere a una estructura egocéntrica, donde la red global podría ser considerada como la suma de subredes más o menos independientes. Es el caso de portales web con una clara división en áreas independientes, tal y como se muestra en la fi gura 6.c). En el contexto de los portales web Universitarios, se trataría de una división en unidades funcionales básicas (docencia, investigación, transferencia tecnológica, etc.). El factor 4 considera los sitios web de gran tamaño. El número de páginas crece geométricamente con el nivel de profundidad, por lo que es necesario un proceso de larga navegación para lograr la información deseada. Al contrario que en el factor 1, los bajos valores de los índices de correlación de Rajski y Cramer indican un portal poco estructurado, donde las páginas poseen enlaces a otras muchas páginas de niveles diferentes, fi gura 6.d). Aunque esta estructuración del portal 05_Rev_34_2_779.indd 24705_Rev_34_2_779.indd 247 06/05/11 10:4406/05/11 10:44 M.ª DEL ROCÍO MARTÍNEZ-TORRES, B. PALACIOS-FLORENCIO, S. L. TORAL-MARTÍN, F. J. BARRERO-GARCÍA 248 Rev. Esp. Doc. Cient., 34, 2, abril-junio, 232-252, 2011. ISSN: 0210-0614. doi:10.3989/redc.2011.2.779 permite que los visitantes puedan navegar de una forma mucho más libres, también es a costa de una mayor complejidad para encontrar la información requerida. El factor 5 representa los sitios web más pequeños, donde una gran cantidad de información se proporciona usando referencias externas a otros sitios web o a subdominios. Esta idea se sustenta por el alto valor de páginas de no retorno, excluyendo las páginas localizadas en el último nivel, así como por el elevado valor de dominios externos y subdominios. Las páginas que cuelgan del dominio raíz se encuentran altamente interconectadas, fi gura 6.e). Finalmente, el factor 6 representa portales web con una estructura dominada por una subred, que contiene la información más relevante. El alto valor del indicador I10, relacionado con los k-núcleos, sugiere una estructura como la representada en la fi gura 6.f). Un k-núcleo se caracteriza por identifi car una subred en la que todo los nodos poseen al menos un grado k. Esta subred constituye el núcleo base del portal. FIGURA 6 Representación simbólica de los portales web identifi cados A A B B a) Factor 1 c) Factor 3 d) Factor 4 f) Factor 6e) Factor 5 b) Factor 2 Dominant subnetwork (k-core) 05_Rev_34_2_779.indd 24805_Rev_34_2_779.indd 248 06/05/11 10:4406/05/11 10:44 Aplicación de algoritmos genéticos a la identifi cación de la estructura de enlaces en portales web Rev. Esp. Doc. Cient., 34, 2, abril-junio, 232-252, 2011. ISSN: 0210-0614. doi:10.3989/redc.2011.2.779 249 TABLA V Factores identifi cados Descripción Loading F1 I2 Grado medio. –0,724 I16 Valor medio de la centralización de intermediación de los nodos. 0,903 I17 Desviación típica de la centralización de intermediación de los nodos. 0,884 I19 Valor medio de la centralización de intermediación de los nodos. 0,839 I23 Índice V de Cramer de la correlación de particiones (grado de salida, k-vecinos). 0,703 I25 Índice de correlación de Rajski de la correlación de particiones (grado de salida, k-vecinos). 0,746 F2 I9 % de páginas incluidas en los componentes fuertes. 0,722 I11 Valor medio de centralidad cercana. 0,924 I12 Desviación típica de centralidad cercana. 0,718 I14 Centralización de intermediación. 0,826 I24 Índice de correlación de Rajski de la correlación de particiones (grado de salida, k-vecinos). 0,578 F3 I15 Desviación típica de la densidad egocéntrica. 0,763 I18 Valor medio de densidad egocéntrica (Red de páginas, k-core, k > 0). 0,895 I20 Valor medio de densidad egocéntrica (Red de páginas excluyendo grado de salida = 0). 0,875 F4 I4 Número de páginas (Red de páginas). 0,900 I5 Número de páginas en el ultimo nivel (profundidad de 7). 0,928 I13 Número de páginas (Red de páginas excluyendo grado de salida = 0). 0,661 I21 Numero de nodos que desarrollan un rol de intermediación. 0,510 F5 I1 Dominios externos. 0,852 I6 Número de páginas sin retorno (excluyendo el último nivel). 0,647 I8 Número de componentes fuertes. 0,831 F6 I7 Desviación típica del grado de salida. 0,786 I10 K-cores que incluye el máximo número de página. 0,633 I22 Desviación típica de los roles de intermediación. 0,635 Básicamente, los perfi les identifi cados en las estructuras de portales web responden a dos estrategias básicas a la hora de decidir su estructura fi nal (Tan y Wei, 2006). La primera estrategia consiste en ofrecer una estructura que tenga sentido para el usuario fi nal. En este sentido, los portales web sacrifi can la accesibilidad de la información en busca de un esquema de navegación más es05_Rev_34_2_779.indd 24905_Rev_34_2_779.indd 249 06/05/11 10:4406/05/11 10:44 M.ª DEL ROCÍO MARTÍNEZ-TORRES, B. PALACIOS-FLORENCIO, S. L. TORAL-MARTÍN, F. J. BARRERO-GARCÍA 250 Rev. Esp. Doc. Cient., 34, 2, abril-junio, 232-252, 2011. ISSN: 0210-0614. doi:10.3989/redc.2011.2.779 tructurado. La opción alternativa consiste en la reducción de grandes estructuras bajo el supuesto de que el desempeño del usuario es óptimo cuando la amplitud y profundidad de la página web se mantiene a un nivel moderado (Tan y Wei, 2006). En general, navegabilidad y accesibilidad son dos parámetros estrechamente relacionados con la estructura interna de los portales web. Existen estudios que los incluyen como características de diseño de portales web corporativos (Robbins y Stylianou, 2003), o dentro de los índices de evaluación de portales web (Miranda y Bañegil, 2004). En línea con estos trabajos, los factores identifi cados se pueden clasifi car como portales fuertemente estructurados (factores 1 y 3), que sacrifi can la accesibilidad por un esquema de navegación más comprensible, como portales estructurados que mejoran la accesibilidad mediante estructuras más planas (factor 2) y como portales poco estructurados que permiten una navegación más autónoma del usuario y mejoran la accesibilidad de la información a través de muchos caminos posibles (factores 4, 5 y 6). Los perfi les identifi cados extienden, además, algunas estructuras previamente identifi cadas en la literatura. Por ejemplo, la estructura en árbol identifi cada por Huizingh (2000) se subdivide en una estructura en árbol profunda (factor 1), plana (factor 2) y estructurada en subredes (factor 3). Asimismo, las estructuras de portales web altamente conectados identifi cados en este mismo estudio se subdividen en portales web de gran tamaño (factor 4) y con subred dominante (factor 6). 5. Conclusión Este trabajo ha desarrollado un sistema experto para la selección de indicadores en la realización de análisis factoriales exploratorios, que posteriormente se ha aplicado a la identifi cación de las estructuras de enlaces de portales web considerando dichos portales como redes sociales. El uso de técnicas de computación evolutiva como los algoritmos genéticos permite realizar una búsqueda guiada sobre el espacio total de soluciones, simplifi cando extraordinariamente el tiempo de computación respecto a la alternativa de evaluar el conjunto de todas las soluciones posibles (que en muchos casos, como en el descrito en el artículo, resultaría prohibitiva). El resultado de dicha búsqueda se caracteriza por proporcionar una solución interpretable y capaz de explicar un valor elevado de la varianza de los datos de partida. Su aplicación a la identifi cación de los patrones estructurales de portales web corporativos universitarios proporciona resultados no sólo acordes con lo descrito en la literatura sino que amplían y detallan patrones no considerados previamente. Asimismo, se relacionan con los conceptos de navegabilidad y accesibilidad, identifi cados como parámetros evaluables en portales web. Aunque el estudio se limita a los portales web de Universidades españolas, constituyen una muestra lo bastante rica dentro del ranking mundial de Universidades en la web. Este estudio podría extenderse a otros portales web institucionales para validar los resultados obtenido 05_Rev_34_2_779.indd 25005_Rev_34_2_779.indd 250 06/05/11 10:4406/05/11 10:44 Aplicación de algoritmos genéticos a la identifi cación de la estructura de enlaces en portales web Rev. Esp. Doc. Cient., 34, 2, abril-junio, 232-252, 2011. ISSN: 0210-0614. doi:10.3989/redc.2011.2.779 251 6. Agradecimientos Este trabajo ha sido apoyado por el Ministerio Español de Educación y Ciencia (Proyecto de investigación con referencia DPI2007-60128) y la Consejería de Innovación, Ciencia y Empresa (Proyecto de investigación con referencia P07-TIC-02621). 7. Bibliografía Almind, T. C., y Ingwersen, P. (1997). Informetric analyses on the World Wide Web: Methodological approaches to Webometrics, Journal of Documentation, vol. 53 (4), pp. 404-426. Almpanidis, G.; Kotropoulo, C., y Pitas, I. (2007). Combining text and link analysis for focused crawling. An application for vertical search engines, Information Systems, vol. 32, pp. 886-908. Baeza-Yates, R., y Castillo, C. (2007). Characterization of national web domains, ACM Transactions on Internet Technology, vol. 7 (2), pp. 1-32. Berlt, K.; Silva de Moura, E.; Carvalho, A.; Cristo, M.; Ziviani, N., y Couto, T. (2010). Modeling the web as a hypergraph to compute page reputation, Information Systems, vol. 35 (5), pp. 530-543. Björneborn, L., y Ingwersen, P. (2004). Toward a basic framework for webometrics, Journal of the American Society for Information Science and Technology, vol. 55 (14), pp. 1216-27. Faba-Pérez, C.; Zapico-Alonso, F.; Guerrero-Bote, V. P., y de Moya-Anegón, F. (2005). Comparative analysis of webometric measurements in thematic environments, Journal of the American Society for Information Science and Technology, vol. 56 (8), pp. 779-785. Goldberg, D. A. (1989). Genetic Algorithm-in Search, Optimization and Machine Learning, Addison-Wesley Publishing Company, Inc. Goldfarb, A. (2006). The (teaching) role of universities in the diffusion of the Internet, International Journal of Industrial Organization, vol. 24 (2), pp. 203-225. Holland, J. (1975). Adaptation in Natural and Artifi cial Systems, University of Michigan Press, Ann Arbor, MI. Huizingh, E. K. (2000). The content and design of web sites: an empirical study, Information & Management, vol. 37 (3), pp. 123-134. Iacobucci, D. (1994). Graphs and matrices. En: Wasserman, S. y Faust, K. (eds.), Social network analysis-methods and applications. New York, NY: Cambridge University Press, pp. 92-166. Martínez Torres, M. R., y Toral, S. L. (2010a). International Comparison of R&D Investment By European, US and Japanese Companies, International Journal of Technology Management, vol. 49 (1-2-3), pp. 107-122. Martínez-Torres, M. R., y Toral, S. L. (2010b). Strategic group identifi cation using evolutionary computation, Expert Systems with Applications, vol. 37 (7), pp. 4.948-4.954. Martínez-Torres, M. R.; Toral, S. L.; Barrero, F., y Cortés, F. (2010). The role of Internet in the development of Future Software Projects, Internet Research, vol. 20 (1), pp. 72-86. 05_Rev_34_2_779.indd 25105_Rev_34_2_779.indd 251 06/05/11 10:4406/05/11 10:44 M.ª DEL ROCÍO MARTÍNEZ-TORRES, B. PALACIOS-FLORENCIO, S. L. TORAL-MARTÍN, F. J. BARRERO-GARCÍA 252 Rev. Esp. Doc. Cient., 34, 2, abril-junio, 232-252, 2011. ISSN: 0210-0614. doi:10.3989/redc.2011.2.779 Miranda González, F. J., y Bañegil, T. M. (2004). Quantitative evaluation of commercial web sites: an empirical study of Spanish fi rms, International Journal of Information Management, vol. 24, pp. 313-328. Nooy, W.; Mrvar, A., y Batagelj, V. (2005). Exploratory Network Analysis with Pajek, Cambridge University Press, New York. Ortega, J. L., y Aguillo, I. F. (2008). Visualization of the Nordic academic web: Link analysis using social network tools, Information Processing and Management, vol. 44, pp. 1.624-1.633. Ortega, J. L., y Aguillo, I. F. (2009). Mapping world-class universities on the web, Information Processing and Management, vol. 45, pp. 272-279. Park, H. W., y Thelwall, M. (2003). Hyperlink analysis: Between networks and indicators, Journal of Computer-Mediated Communication, vol. 8 (4). (http://www.ascusc.org/ jcmc/vol8/issue4/park.html) [consulta: mayo de 2010]. Pinto-Molina, M.; Alonso-Berrocal, J. L.; Cordón-García, J. A.; Fernández-Marcial, V.; García-Figuerola, C.; García-Marco, J.; Gómez-Camarero, C.; Zazo, Á. F., y Doucet, A. V. (2004). Análisis cualitativo de la visibilidad de la investigación de las universidades españolas a través de sus páginas web. Revista Española de Documentación Científi - ca, vol. 27 (3), pp. 345-370. Rencher, A. C. (2002): Methods of Multivariate Analysis. 2nd ed. Wiley Series in Probability and Statistics, John Wiley & Sons. Robbins, S. S., y Stylianou, A. C. (2003). Global corporate web sites: an empirical investigation of content and design, Information & Management, vol. 40 (3), pp. 205-212. Tan, G. W. y Wei, K. K. (2006). An empirical study of Web browsing behaviour: Towards an effective Website design, Electronic Commerce Research and Applications, vol. 5, pp. 261-271. Thelwall, M. (2004). Link Analysis: An Information Science Approach, Amsterdam, Elsevier 2004. Thelwall, M. (2008). Bibliometrics to webometrics, Journal of Information Science, vol. 34 (4), pp. 605-621. Toral, S. L.; Martínez Torres, M. R., y Barrero, F. (2010). Analysis of Virtual Communities supporting OSS Projects using Social Network Analysis, Information and Software Technology, vol. 52 (3), pp. 296-303. Toral, S. L.; Martínez-Torres, M. R., y Barrero, F. (2009a). Virtual Communities as a resource for the development of OSS projects: the case of Linux ports to embedded processors, Behavior and Information Technology, vol. 28 (5), pp. 405-419. Toral, S. L.; Martínez-Torres, M. R.; Barrero, F., y Cortés, F. (2009b). An empirical study of the driving forces behind online communities, Internet Research, vol. 19 (4), pp. 378-392. Toral, S. L.; Martínez-Torres, M. R., y Barrero, F. (2009c). Modelling Mailing List Behaviour in Open Source Projects: the Case of ARM Embedded Linux, Journal of Universal Computer Science, vol. 15 (3), pp. 648-664. Yang, B., y Qin, J. (2008). Data collection system for link analysis, Third International Conference on Digital Information Management, pp. 247-252. 05_Rev_34_2_779.indd 25205_Rev_34_2_779.indd 252 06/05/11 10:4406/05/11 10:44