Estudio de la dimensión métrica de Grafos mediante algoritmos evolutivos

PROYECTO FINAL DE CARRERA ESTUDIO DE LA DIMENSIÓN MÉTRICA DE GRAFOS MEDIANTE ALGORITMOS EVOLUTIVOS Autor: Alejandro Cabrera Gambín Director: Francesc Comellas Padró Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 2 1. INTRODUCCIÓN Y OBJETIVOS .......................................................................................................................... 4 2. ESTRUCTURA DE LA MEMORIA........................................................................................................................ 5 3. TEORÍA DE GRAFOS.......................................................................................................................................... 7 3.1 INTRODUCCIÓN ......................................................................................................................................... 7 3.2 CONCEPTOS BÁSICOS ................................................................................................................................ 7 3.3 CONCEPTOS AVANZADOS ........................................................................................................................ 11 3.4 MODELOS DE GRAFOS ............................................................................................................................. 15 3.5 DIMENSIÓN MÉTRICA .............................................................................................................................. 19 4. ALGORÍTMICA ................................................................................................................................................ 22 4.1 INTRODUCCIÓN ....................................................................................................................................... 22 4.2 COMPLEJIDAD Y COMPUTABILIDAD ........................................................................................................ 23 4.3 TIPOS DE ALGORITMOS ........................................................................................................................... 27 5 IMPLEMENTACIÓN ......................................................................................................................................... 28 5.1 COMANDO: PREDATA .............................................................................................................................. 28 5.2 COMANDO: SORT .................................................................................................................................... 29 5.3 COMANDO: LABEL ................................................................................................................................... 30 5.4 COMANDO: SETDATA .............................................................................................................................. 31 5.5 COMANDO: PROB .................................................................................................................................... 32 5.6 COMANDOS: INTRAMD/INTERMD .......................................................................................................... 33 5.7 COMANDO: DK ........................................................................................................................................ 34 5.8 COMANDO: DKE ...................................................................................................................................... 35 5.9 COMANDO: RANDSET .............................................................................................................................. 36 5.10 COMANDO: RSORT ................................................................................................................................ 37 5.11 COMANDOS: CDET/KDIST/CPRANK ....................................................................................................... 38 5.12 COMANDO: METDIM ............................................................................................................................. 39 6 ANÁLISIS DE RESULTADOS ............................................................................................................................. 47 6.1 CALIDAD DEL PROCEDIMIENTO DE BÚSQUEDA ...................................................................................... 47 6.2 EVOLUCIÓN DE LA DIMENSIÓN MÉTRICA .............................................................................................. 51 6.3 BASES MÉTRICAS VERSUS CONJUNTOS ALEATORIOS ............................................................................. 56 6.4 PROBABILIDADES Y DIMENSIÓN MÉTRICA .............................................................................................. 58 7 CASOS REALES................................................................................................................................................. 64 8 CONCLUSIONES............................................................................................................................................... 65 Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 3 9 BIBLIOGRAFÍA ................................................................................................................................................. 66 9.1 ARTÍCULOS ............................................................................................................................................... 66 9.2 LIBROS...................................................................................................................................................... 66 9.3 WORLD WIDE WEB .................................................................................................................................. 67 ANEXO ............................................................................................................................................................... 68 ANEXO: ALMACENAMIENTO DE GRAFOS ...................................................................................................... 69 ANEXO: COMPARATIVA DE LOS MODELOS DE GRAFOS ................................................................................ 70 ANEXO: EJEMPLOS SIGNIFICATIVOS DE METAHEURÍSTICAS ......................................................................... 71 ANEXO: ESTRUCTURA DE DESARROLLO SOFTWARE ..................................................................................... 73 ANEXO: ESTRUCTURA DE DATOS................................................................................................................... 74 ANEXO: CARACTERÍSTICAS FAMILIARES ........................................................................................................ 76 ANEXO: DISTORSIÓN DE BÚQUEDA EN LA DIMENSIÓN MÉTRICA RELATIVA ................................................ 82 ANEXO: EVOLUCIÓN DE LA DIMENSIÓN MÉTRICA RELATIVA ....................................................................... 84 ANEXO: CORRELACIÓN ENTRE CONJUNTOS Y CARACTERÍSTICAS ................................................................. 86 ANEXO: PROBABILIDADES RESPECTO LA DIMENSIÓN MÉTRICA ................................................................... 95 ANEXO: CORRELACIÓN ENTRE LA PROBABILIDAD Y LAS CARACTERÍSTICAS ............................................... 101 ANEXO: DISTANCIA DE KENDALL ENTRE PROBABILIDADES Y CARACTERÍSTICAS ........................................ 106 ANEXO: RELACIÓN ENTRE PERCENTILES PARA LAS PROBABILIDADES Y LAS CARACTERÍSTICAS ................ 111 ANEXO: RELACIÓN ENTRE PERCENTILES (+80) PARA LAS PROBABILIDADES Y LAS CARACTERÍSTICAS ....... 116 ANEXO: RELACIÓN ENTRE PERCENTILES (-20) PARA LAS PROBABILIDADES Y LAS CARACTERÍSTICAS ........ 121 ANEXO: IMÁGENES DE CASOS REALES ........................................................................................................ 126 Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 4 1. INTRODUCCIÓN Y OBJETIVOS En la actualidad existe una preocupación emergente por toda una serie de aspectos y propuestas que comparten un lugar común, las redes. Internet, la World Wide Web, las redes sociales, las económicas, las biológicas, las proteínicas, y así sucesivamente hasta un sinfín de casos que a todos nos resultan muy familiares son claras muestras de ello. La forma más abstracta de tratar con redes es mediante los conceptos manejados por la Teoría de Grafos. Como veremos más adelante, sus fundamentos teóricos datan de mediados del siglo XVIII. No se trata pues de una disciplina que haya nacido ayer. Sin embargo, tanto el nivel de madurez de sus conceptos como nuestra capacidad de trabajo sobre los mismos (1) , no se han entrecruzado de modo fructífero hasta nuestros días. Actualmente nos planteamos toda una serie de importantes cuestiones abiertas en la materia tales como qué modelos y topologías representan mejor nuestra realidad, o cuáles propiedades determinan más adecuadamente su comportamiento ante las más diversas situaciones. En algún punto dentro de todo ese vendaval de retos y descubrimientos se encuentra el centro de atención y propósitos de este trabajo, así como su modesta aportación. Existe un concepto muy bien definido, denominado dimensión métrica, del que se le conocen toda una serie de valores y resultados en ámbitos teóricos. Pero nada de significativa importancia se sabe del mismo a nivel más práctico y general. Aunque en su momento lo expondremos tal como se merece, podemos presentarlo simplemente como la forma natural que tenemos de extender nuestros conceptos de orientación espacial del mundo analógico al mundo digital. Es decir, la dimensión métrica nos reta a determinar cuáles y qué cantidad mínima de elementos del grafo nos pueden permitir orientarnos efectivamente a través del mismo sin confusiones, al igual que una serie de postes y señales estratégicamente situados en una carretera nos permiten llegar felizmente a cualquiera que sea nuestro destino dentro de la red viaria. Y ello, sin género de dudas, tiene importantes aplicaciones directas sobre un campo como las telecomunicaciones. Cómo proceder para descubrir efectivamente el entramado de una red por parte de un protocolo o de un robot, cómo enviar paquetes o navegar por la misma eficientemente, cómo detectar puntos susceptibles de mejora en el tráfico, cómo saber cuáles son importantes desde el punto de vista de la seguridad, etc. Gran parte del mencionado desconocimiento práctico de la cuestión tiene su origen en nuestra propia incapacidad de formular un método simple y poco costoso para su determinación en un caso genérico dado. He ahí pues la justificación de este trabajo, y he aquí pues nuestros objetivos por orden de prioridad: • Diseñar e implementar un software capaz de determinar la dimensión métrica de un grafo cualquiera (2) . • Comprobar su calidad, eficiencia y utilidad real en diversas casuísticas y situaciones. • Averiguar tanto como podamos sobre las propiedades y el comportamiento de la dimensión métrica. 1 Hoy en día tenemos el privilegio de disponer de computadores que procesan grafos gigantescos. 2 Aunque ello sólo sea de modo aproximado. Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 5 2. ESTRUCTURA DE LA MEMORIA Esta memoria se divide en toda una serie de apartados que comentaremos a continuación. En primer lugar se dedican dos apartados a exponer el contexto teórico necesario para la comprensión de la problemática que estamos tratando. Uno dedicado a la teoría de grafos, y otro a la algorítmica. En ambos se ha hecho especial hincapié en presentar todos los conceptos de forma sencilla y amena. Primando la claridad y la idea intuitiva sobre la estricta rigurosidad. Con abundantes ejemplos, imágenes y la mínima letra imprescindible. Se ha hecho un esfuerzo para que, en la medida de lo posible, este trabajo sea autocontenido. Al lector se le exige únicamente un mínimo de curiosidad e interés respecto al tema. Se ha intentado en todo momento introducir los conceptos de forma gradual para que, de modo natural, se establezcan el mayor número de asociaciones y relaciones causales entre los mismos por parte del lector. Aun cuando es bien consabido que, habitualmente, los avances de cualquier disciplina no obedezcan tan fielmente la línea recta excepto en la retrospectiva. A la teoría de grafos le podemos asociar los siguientes anexos: • ANEXO: ALMACENAMIENTO DE GRAFOS. • ANEXO: COMPARATIVA DE MODELOS DE GRAFOS. Y para la sección de algorítmica estos otros: • ANEXO: EJEMPLOS SIGNIFICATIVOS DE METAHEURÍSTICAS. El siguiente bloque es el dedicado a la implementación. Tal y como ya se ha mencionado en el apartado introductorio y de objetivos, este proyecto ha comportado eminentemente un fin práctico: la creación de un programa capaz de realizar toda una serie de cálculos de modo coordinado y organizado de acuerdo con nuestras motivaciones. Era necesario pues adjuntar algún tipo de guía o referencia sobre el comportamiento y utilización del mismo. Se detallan todas y cada una de las ordenes disponibles bajo el esquema general de descripción y llamada. En descripción encontraremos un breve comentario sobre su función y utilidad, además de una relación de ficheros de entrada y salida para cada caso particular. En llamada encontraremos una breve relación del comando y los modificadores asociados para su uso. Un usuario que haya experimentado la utilización de programas mediante líneas de comandos en alguna ocasión no debería tener mayores problemas en sacar mucho provecho de estas referencias. Al apartado de implementación le pertenecen los siguientes anexos: • ANEXO: ESTRUCTURA DE DESARROLLO SOFTWARE. • ANEXO: ESTRUCTURAS DE DATOS. Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 6 Mencionar por último que toda esta estructura general de exposición de comandos presentará una importante excepción con el comando METDIM. Se trata del comando principal, y el diseño de toda la aplicación (formato de los ficheros, flujo de la información, estructuras de los datos y algoritmos,…) ha girado en torno a él como su columna vertebral. Por todo ello, también incluirá un apartado de pseudocódigo. Su intención no es otra que la de proporcionar unas nociones básicas del procesamiento realizado por su parte. Para mayor detalle y profundidad se recomienda la consulta literal del código. A continuación se prosigue con un apartado dedicado al análisis de resultados. Si en el anterior punto se hacía referencia al funcionamiento e implementación de la herramienta de por si, en este nos centraremos en el uso de la misma para toda una serie de casos estándar de interés. Los anexos relacionados con el mismo serán: • ANEXO: DISTORSIÓN DE BÚSQUEDA EN LA β(G) RELATIVA. • ANEXO: EVOLUCIÓN DE LA β(G) RELATIVA. • ANEXO: CARACTERÍSTICAS FAMILIARES (betweenness, clustering, distancia media, etc.). • ANEXO: CORRELACIÓN ENTRE CONJUNTOS (betweenness, clustering, distancia media, etc.). • ANEXO: PROBABILIDAD RESPECTO LA β(G). • ANEXO: COEF. DETERMINACIÓN: PROBABILIDAD/CARACTERÍSTICAS. • ANEXO: DISTANCIA DE KENDALL: PROBABILIDAD/CARACTERÍSTICAS. • ANEXO: CORRELACIÓN DE PERCENTILES: PROBABILIDAD/CARACTERÍSTICAS. • ANEXO: CORRELACIÓN DE PERCENTILES EXTREMOS (+80): PROBABILIDAD/CARACTERÍSTICAS. • ANEXO: CORRELACIÓN DE PERCENTILES EXTREMOS (- 20): PROBABILIDAD/CARACTERÍSTICAS. Como casuística añadida, se ha proporcionado también resultados sobre grafos extraídos directamente de la realidad, y que suelen emplearse en diversos artículos de la materia a modo de referencia. A este punto le pertenece el anexo: • ANEXO: IMÁGENES DE CASOS REALES. Finalmente, se ha incluido un último apartado de conclusiones a modo de revisión general de la labor realizada, los resultados obtenidos, y las posibles tareas pendientes que de todo ello se deriven. Notar también que de modo adjunto a esta memoria se encuentra un DVD que contiene tanto el código de programa, como todos los datos de entrada y salida generados sobre los que se ha trabajado. Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 3. TEORÍA DE GRAFOS 3.1 INTRODUCCIÓN La Teoría de Grafos es una de las principales ramas de las matemáticas discretas indica, su campo de interés reside en el estudio de los apartado proporcionaremos la definición formal de grafo, intuitivamente podemos entenderlo como un conjunto de puntos unidos mediante una serie de enlaces. Lo que coloquialmente denominamos Su nacimiento da ta oficialmente de 1736, a manos de Leonhard Euler (1707 problema «L os siete puentes de Königsberg incorporando toda una serie de cuestiones a la materia tales como trazado de caminos, que han contribuido de modo crucial en su propio beneficio y desarrollo. Dejando de lado el puro interés matemático que posea por sí misma la teoría de grafos, sus aplicaciones prácticas son inmens as dado que es bastante fácil abstraer estructuras de este tipo en la realidad. Internet, sociología, industria química y farmacológica, biología, etc. son únicamente unos pocos ejemplos de las innumerables situaciones en las que podemos establecer fielmen 3.2 CONCEPTOS BÁSICOS Se define el grafo G, como el par ordenado V es un conjunto de elementos denominados E es un conjunto de elementos denominados De hecho, las aristas no son más que subconjuntos de dos elementos pertenecientes a expresar las relaciones entre los elementos de Notar que pueden existir vértices aislados 3 División de las matemáticas encargada del estudio de los conjuntos numerables; ya sean finitos o infinitos. 4 Conjunto de dos elementos, y un crit erio de orden. Sabemos diferenciar perfectamente el primero del segundo. la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos La Teoría de Grafos es una de las principales ramas de las matemáticas discretas (3) . Como su propio nombre indica, su campo de interés reside en el estudio de los grafos y sus propiedades. Aunque en el siguiente apartado proporcionaremos la definición formal de grafo, intuitivamente podemos entenderlo como un conjunto de puntos unidos mediante una serie de enlaces. Lo que coloquialmente denominamos ta oficialmente de 1736, a manos de Leonhard Euler (1707 - 1783), tratando la resolución del os siete puentes de Königsberg ». Desde entonces, y a lo largo de la historia, se han ido incorporando toda una serie de cuestiones a la materia tales como la enumeración, el trazado de caminos, que han contribuido de modo crucial en su propio beneficio y desarrollo. Dejando de lado el puro interés matemático que posea por sí misma la teoría de grafos, sus aplicaciones as dado que es bastante fácil abstraer estructuras de este tipo en la realidad. Internet, sociología, industria química y farmacológica, biología, etc. son únicamente unos pocos ejemplos de las innumerables situaciones en las que podemos establecer fielmen te una representación mediante grafos. como el par ordenado (4) G = (V, E), donde: es un conjunto de elementos denominados vértices (nodos). es un conjunto de elementos denominados aristas (enlaces). hecho, las aristas no son más que subconjuntos de dos elementos pertenecientes a expresar las relaciones entre los elementos de V . La relación indicada por una arista es la EJEMPLO V = {1, 2, 3, 4, 5, 6, 7} E = {{1,2}, {2,3}, {2,4}, {3,5}, {4,5}, {5,6}} {1, 2} se lee como «los vértices 1 y 2 son adyacentes Coloquialmente, el nodo 1 y 2 son vecinos. Las aristas también pueden presentar adyacencia. {2,3} y {2,4} son aristas adyacentes ; comparten el nodo 2. aislados . Caso del nodo 7. División de las matemáticas encargada del estudio de los conjuntos numerables; ya sean finitos o infinitos. erio de orden. Sabemos diferenciar perfectamente el primero del segundo. la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 7 . Como su propio nombre sus propiedades. Aunque en el siguiente apartado proporcionaremos la definición formal de grafo, intuitivamente podemos entenderlo como un conjunto de puntos unidos mediante una serie de enlaces. Lo que coloquialmente denominamos una red. 1783), tratando la resolución del ». Desde entonces, y a lo largo de la historia, se han ido la enumeración, el coloramiento, o el trazado de caminos, que han contribuido de modo crucial en su propio beneficio y desarrollo. Dejando de lado el puro interés matemático que posea por sí misma la teoría de grafos, sus aplicaciones as dado que es bastante fácil abstraer estructuras de este tipo en la realidad. Internet, sociología, industria química y farmacológica, biología, etc. son únicamente unos pocos ejemplos de las te una representación mediante grafos. hecho, las aristas no son más que subconjuntos de dos elementos pertenecientes a V, y nos ayudan a . La relación indicada por una arista es la adyacencia. son adyacentes ». Las aristas también pueden presentar adyacencia. ; comparten el nodo 2. División de las matemáticas encargada del estudio de los conjuntos numerables; ya sean finitos o infinitos. erio de orden. Sabemos diferenciar perfectamente el primero del segundo. Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos Se dice que un grafo es conexo , si no contiene ningún vértice aislado. Al cardinal de V nos referiremos como el En el ejemplo anterior: Se trata pues de un grafo de orden 7 y medida 6. En caso de tratar con grafos cuyo número de nodos no sea finito Aunque no se haya mencionado hasta ahora, se observa claramente como ordenados. Es un caso muy habitual, pero ello no tiene porque ser siempre obligatoriamente así. haber estar formado perfectamente por pares ordenados. También puede darse el caso que dos vértices sean adyacentes de múltiples formas; es decir, que exista más de una única arista de conexión entre los mismos ( Incluso puede suceder que una arista exprese la adyacencia de un vértice consigo mismo (un Un grafo simétrico es aquél en el que puedo formular una aplicación (un automorfismo), que me permite renombrar los nodos de tal modo que los nodos renombrados mantienen el mismo tipo adyacencia que poseían antes de ser renombrados. 5 En este trabajo, por motivos de simplicidad, se utilizarán siempre grafos finitos, simples, conexos, y no dirigidos. la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos , si no contiene ningún vértice aislado. nos referiremos como el orden del grafo, y el cardinal de E será la medida del grafo |V|= 7 |E|= 6 Se trata pues de un grafo de orden 7 y medida 6. En caso de tratar con grafos cuyo número de nodos no sea finito , tendremos grafos infinitos Aunque no se haya mencionado hasta ahora, se observa claramente como E está formado por pares no Es un caso muy habitual, pero ello no tiene porque ser siempre obligatoriamente así. haber estar formado perfectamente por pares ordenados. EJEMPLO E = {(1,2), (2,4), (3,2), (4,5), (5,3), (5,6)} En este tipo de casos, las aristas tienen asociado determinado, y se dice entonces que estamos ante un dirigido o digrafo. También puede darse el caso que dos vértices sean adyacentes de múltiples formas; es decir, que exista más de una única arista de conexión entre los mismos ( aristas paralelas ). Estamos entonces ante un Incluso puede suceder que una arista exprese la adyacencia de un vértice consigo mismo (un EJEMPLO Entre los vértices 4 y 5, tenemos dos aristas paralelas. En el vértice 1 se nos presenta un lazo. Un grafo simple es aquél que no es multigrafo, ni contiene lazos aquél en el que puedo formular una aplicación (un automorfismo), que me permite renombrar los nodos de tal modo que los nodos renombrados mantienen el mismo tipo adyacencia que poseían antes de ser renombrados. En este trabajo, por motivos de simplicidad, se utilizarán siempre grafos finitos, simples, conexos, y no dirigidos. la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 8 medida del grafo . grafos infinitos . está formado por pares no Es un caso muy habitual, pero ello no tiene porque ser siempre obligatoriamente así. E podría En este tipo de casos, las aristas tienen asociado un sentido determinado, y se dice entonces que estamos ante un grafo También puede darse el caso que dos vértices sean adyacentes de múltiples formas; es decir, que exista más ). Estamos entonces ante un multigrafo. Incluso puede suceder que una arista exprese la adyacencia de un vértice consigo mismo (un lazo). 4 y 5, tenemos dos aristas paralelas. es aquél que no es multigrafo, ni contiene lazos (5) . aquél en el que puedo formular una aplicación (un automorfismo), que me permite renombrar los nodos de tal modo que los nodos renombrados mantienen el mismo tipo de relaciones de En este trabajo, por motivos de simplicidad, se utilizarán siempre grafos finitos, simples, conexos, y no dirigidos. Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos Se denomina grado de un nodo al número de aristas conectadas al mismo. Coloquialmente, lo que estamos expresando con ello, no es más que el tamaño de su La función de distribuc ión de grado determinado valor de grado igual a k Se dice que un grafo es regular , si todos sus vértices presentan el mismo grado. Se denomina camino entre los vértices que cualquier elemento de la secuencia respecto a su anterior, y a su posterior, mantiene una relación de adyacencia. Siendo A el p rimer elemento de la secuencia, y Se denomina longitud del camino entre los vértices En el ejemplo anterior: camino 1,6 En grafos inconexo s, como el acabado de presentar, no tenemos porque poder establecer caminos entre todos los vértices. Es evidente que no se pueden establecer caminos con el vértice 7; ya sea como origen, o como destino. Un camino geodésico entre los vértices trazar entre esos mismos nodos. Notar que éste no tiene porque ser único. Pueden existir múltiples caminos geodésicos entre dos vértices. En el ejemplo anterior: camino_geodésico_1 c 6 Habitualmente se entiende en su sentido probabilístico. Difier 7 De existir repeticiones, se entiende que es un la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos al número de aristas conectadas al mismo. Coloquialmente, lo que estamos expresando con ello, no es más que el tamaño de su ión de grado de un grafo, P(k), nos indica el número de vértices del grafo con un determinado valor de grado igual a k (6) . , si todos sus vértices presentan el mismo grado. entre los vértices A y B , a una secuencia ordenada de vértices sin repeticiones que cualquier elemento de la secuencia respecto a su anterior, y a su posterior, mantiene una relación de rimer elemento de la secuencia, y B el último. entre los vértices A y B , al número de aristas presentes en esa secuencia. 1,6 = (1, 2, 3, 5 ,6) longitud [ camino 1,6 ] = 4 s, como el acabado de presentar, no tenemos porque poder establecer caminos entre todos los vértices. Es evidente que no se pueden establecer caminos con el vértice 7; ya sea como origen, o entre los vértices A y B, es el camino más corto (de menor longitud), que podemos trazar entre esos mismos nodos. Notar que éste no tiene porque ser único. Pueden existir múltiples caminos geodésicos entre dos vértices. En el ejemplo anterior: camino_geodésico_1 1,6 = (1, 2, 3, 5, 6) c amino_geodésico_2 1,6 = (1, 2, 4, 5, 6) Habitualmente se entiende en su sentido probabilístico. Difier e únicamente en un factor de escala dado por el orden. De existir repeticiones, se entiende que es un recorrido, y no un camino. NODO GRADO 1 1 2 3 3 2 4 2 5 3 6 1 7 0 la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 9 Coloquialmente, lo que estamos expresando con ello, no es más que el tamaño de su vecindario. nos indica el número de vértices del grafo con un , a una secuencia ordenada de vértices sin repeticiones (7) , tal que cualquier elemento de la secuencia respecto a su anterior, y a su posterior, mantiene una relación de , al número de aristas presentes en esa secuencia. s, como el acabado de presentar, no tenemos porque poder establecer caminos entre todos los vértices. Es evidente que no se pueden establecer caminos con el vértice 7; ya sea como origen, o camino más corto (de menor longitud), que podemos trazar entre esos mismos nodos. Notar que éste no tiene porque ser único. Pueden existir múltiples caminos e únicamente en un factor de escala dado por el orden. Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 16 3.4.2 ALEATORIO REGULAR Que el binomial sea el grafo aleatorio por excelencia, no significa que no existan otro tipo de grafos aleatorios. Un modelo de cierta relevancia y presencia en la literatura matemática es el aleatorio regular. Como su propio nombre indica, se trata justamente de aquellos grafos que podemos seleccionar de entre el conjunto G N, r . Es decir, el conjunto formado por todos los grafos binomiales de N nodos, r-regulares (16) . Es obvio que G$F&HI?, FHJ K, F LJM El procedimiento de una selección no sesgada de grafos de este tipo no es una tarea nada fácil, e igualmente difícil es determinar las propiedades de los mismos. Pero en cuanto a distancia media y clustering, se conoce que presentan valores muy similares a los binomiales. 3.4.3 ANILLO K-REGULAR El anillo k-regular es un grafo totalmente determinista a diferencia del resto de todos los modelos expuestos aquí. Su construcción responde a una disposición circular de nodos, y un establecimiento simétrico de enlaces en ambos sentidos. Posee una P(k) idéntica a la de un grafo aleatorio regular, pero un elevado clustering y una elevada distancia media. 3.4.4 SMALL-WORLD En el campo de la sociología, históricamente una de las cuestiones de mayor interés siempre ha sido determinar la distancia entre individuos y su relevancia. Ya en 1929, Frigyes Karinty propone la necesidad de experimentar para comprobar el nivel de separación presente entre diferentes individuos. A mediados de siglo XX, Stanley Milgram comenzaría a llevar a cabo toda una serie de experimentos sociológicos (hoy en día ya clásicos del tema), de los cuáles uno de ellos conduciría al concepto de los «seis grados de separación». Es decir, experimentalmente se determinaba por primera vez que una red real (en este caso de personas), presentaba como características intrínsecas una baja separación entre desconocidos (baja distancia media), a pesar de mantener un elevado grado de amistades compartidas (clustering elevado). Es decir, se toma consciencia del hecho que habitamos en un «mundo pequeño», a pesar de que la propia idea pudiera parecer contra sentido común por los prejuicios realizados a priori. Posteriormente se comprobaría en un campo de conocimiento tras otro (biología, tecnología, etc.), que este hecho se presentaba frecuentemente de modo natural. Estamos rodeados pues de sistemas eficientes tanto en su capacidad para difundir mensajes a nivel local, como a nivel global. 16 3 ≤ r < N y Nr par. Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos El concepto de small-world no se enmarca finalmente, en 1998, Watts y Strogatz retoman esa idea y la formalizan mediante su nuevo modelo. A diferencia del anterior, para su creación se parte de un grafo de tipo anillo de igual a k . Por el hecho de ser anillo, cada nodo dispone de En ese punto, por ser todavía un grafo de tipo anillo, sabemos que poseemos un elevado clustering, pero también una elevada distancia media entre n proceso aleatorio. Daremos k/2 vueltas al anillo, y en cada vuelta, escogiendo el enlace correspondiente, se reconectará con una cierta probabilidad En la figura adjunta se observa como en función de la probabilidad anillo kregular a un aleatorio binomial. Su la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos no se enmarca ba satisfactoriamente dentro de un modelo binomial y, finalmente, en 1998, Watts y Strogatz retoman esa idea y la formalizan mediante su nuevo modelo. A diferencia del anterior, para su creación se parte de un grafo de tipo anillo de N nodos y un grado par . Por el hecho de ser anillo, cada nodo dispone de k/2 vecinos en cada sentido del anillo En ese punto, por ser todavía un grafo de tipo anillo, sabemos que poseemos un elevado clustering, pero también una elevada distancia media entre n odos. ¿Cómo disminuir esa distancia media? proceso aleatorio. Daremos k/2 vueltas al anillo, y en cada vuelta, escogiendo el enlace correspondiente, se reconectará con una cierta probabilidad p con cualquier otro nodo (a condición de no d En la figura adjunta se observa como en función de la probabilidad p podemos desplazarnos de un grafo regular a un aleatorio binomial. Su P(k) oscilará pues de una delta discreta a una binomial. Pero no sólo varia la P(k). Tal como era nuestra intención, se intercambian perdidas en clustering a cambio de perdidas en distancia media. La zona sombreada se corresponde a lo que clasicamente se establece como el rango de valores auspiciados bajo el calificativo de small-world. Luego notar que, independientemente del modelo de construcción escogido, podemos considerar un grafo como de tipo small-world siempre y cuando se encuentre en la zona indicada en la gráfica. Y por tanto, todo Watts Strogatz es small -world, pero no todo small Watts Strogatz. la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 17 ba satisfactoriamente dentro de un modelo binomial y, finalmente, en 1998, Watts y Strogatz retoman esa idea y la formalizan mediante su nuevo modelo. A nodos y un grado par inicial vecinos en cada sentido del anillo . En ese punto, por ser todavía un grafo de tipo anillo, sabemos que poseemos un elevado clustering, pero ¿Cómo disminuir esa distancia media? Recurriendo a un proceso aleatorio. Daremos k/2 vueltas al anillo, y en cada vuelta, escogiendo el enlace correspondiente, se con cualquier otro nodo (a condición de no d uplicar enlaces). desplazarnos de un grafo oscilará pues de una delta discreta a una binomial. Tal como era nuestra intención, se intercambian perdidas en clustering a cambio de perdidas La zona sombreada se corresponde a lo que clasicamente se establece como el rango de valores auspiciados bajo el Luego notar que, independientemente del modelo de construcción escogido, podemos considerar un grafo como siempre y cuando se encuentre en la zona indicada en la gráfica. Y por tanto, todo Watts Strogatz small -world tiene porque ser Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 3.4.5 SCALE-FREE Hasta el momento, todos los modelos expuestos comparten como característica principal el hecho de ser estáticos . Inicialmente ya disponemos del número total de nodos que conformará el grafo variará el proceso empleado para determinar a posteriori las conexiones entre los mismos. Su investigación experimental en la descubrimiento de una función de distribución de grado totalmente diferente a las propuestas anteriores. Concretamente descubrieron que: Es decir, nos encontrábamos ante una función de distribución de tipo potencial. Como es sabido, este tipo de funciones tienen la curiosa propiedad de mantener el valor de relación entre pares de puntos con independencia del factor de escala (de ahí el térm EJEMPLO P(k=10)/P(k=100) = P(k=1000)/P(k=10000) Además, un tipo de distribución semejante denotaba el hecho de la presencia de redes reales. Es decir, la existencia de unos pocos nodos que poseían un conexionado diferencia del resto. ¿Por qué se producía esta situación? Propusieron entonces la combinación de dos mecanismos genéricos para dar su respuesta a esos dilemas: El dinamismo en las redes Las redes s La preferencia de enlace Nuevos nodos tienden a crear enlaces con nodos altamente conexionados. la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos Hasta el momento, todos los modelos expuestos comparten como característica principal el hecho de ser . Inicialmente ya disponemos del número total de nodos que conformará el grafo variará el proceso empleado para determinar a posteriori las conexiones entre los mismos. Sin embargo, este enfoque adolece de presentarse poco natural. En el mundo nada resulta ser tan estático. Todo resta bajo continuos cambios. Unas frecuentes, otras menos. El dinamismo integral de la realidad. Las redes no serán tampoco una excepción, y justamente de ello se tomó consciencia mediante el trabajo de Barabási y Albert en 1999. Su investigación experimental en la exploración de diferentes tipos de redes del mundo real conllevó el descubrimiento de una función de distribución de grado totalmente diferente a las propuestas anteriores. P(k) ~ F 4O estimando además que P є [2, 3] Es decir, nos encontrábamos ante una función de distribución de tipo potencial. Como es sabido, este tipo de funciones tienen la curiosa propiedad de mantener el valor de relación entre pares de puntos con independencia del factor de escala (de ahí el térm ino scale-free). P(k=10)/P(k=100) = P(k=1000)/P(k=10000) Además, un tipo de distribución semejante denotaba el hecho de la presencia de redes reales. Es decir, la existencia de unos pocos nodos que poseían un conexionado qué se producía esta situación? ¿Cómo reflejarlo en nuevos modelos? Propusieron entonces la combinación de dos mecanismos genéricos para dar su respuesta a esos dilemas: Las redes s on entes que crecen, se modifican, etc. Nuevos nodos tienden a crear enlaces con nodos altamente conexionados. la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 18 Hasta el momento, todos los modelos expuestos comparten como característica principal el hecho de ser . Inicialmente ya disponemos del número total de nodos que conformará el grafo final. Únicamente variará el proceso empleado para determinar a posteriori las conexiones entre los mismos. Sin embargo, este enfoque adolece de presentarse poco natural. En el mundo nada resulta ser tan estático. Todo resta bajo continuos cambios. Unas veces más dinamismo forma parte integral de la realidad. Las redes no serán tampoco una excepción, y justamente de ello se tomó consciencia mediante el trabajo de Barabási y Albert en 1999. exploración de diferentes tipos de redes del mundo real conllevó el descubrimiento de una función de distribución de grado totalmente diferente a las propuestas anteriores. є [2, 3] Es decir, nos encontrábamos ante una función de distribución de tipo potencial. Como es sabido, este tipo de funciones tienen la curiosa propiedad de mantener el valor de relación entre pares de puntos con Además, un tipo de distribución semejante denotaba el hecho de la presencia de hubs en muchas de las redes reales. Es decir, la existencia de unos pocos nodos que poseían un conexionado extraordinario a Propusieron entonces la combinación de dos mecanismos genéricos para dar su respuesta a esos dilemas: Nuevos nodos tienden a crear enlaces con nodos altamente conexionados. Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 19 3.5 DIMENSIÓN MÉTRICA En el contexto actual, uno de los dilemas de mayor interés en estas materias de estudio reside aún en determinar que nodos son los auténticamente relevantes, o centrales, dentro de una red. Se entiende que en base a la centralidad se deben de poder analizar y sintetizar los diferentes fenómenos que se reproducen en una red cualquiera. Se han propuesto toda una serie de diferentes medidas de la misma, cada una respondiendo a un enfoque particular de definición. Las referencias clásicas en este tema acostumbran a ser: el grado, la distancia media, y la betweenness centrality. Sin embargo, todavía no se ha llegado a un consenso final sobre la propia definición de centralidad. Cada cual apuesta por criterios que acentúan un cierto tipo de cualidades en detrimento de otras, he incluso los hay que no creen la posible definición de un concepto general de centralidad, y se centran únicamente en emplear aquella que enfatice el matiz deseado. Dentro de toda ésta confusión se puede enmarcar también el concepto de la dimensión métrica. El origen de su planteamiento (de raíces más teóricas que prácticas), reside en un artículo de F.Harary de 1976. Las principales aplicaciones que se le sugieren a primera vista están estrechamente relacionadas con campos tan diversos como el descubrimiento y verificación de redes de comunicaciones, sistemas de navegación robóticos, creación de nuevos fármacos, etc. Para tener una idea más clara sobre lo que estamos hablando, y sus posibles implicaciones, imaginemos una persona moviéndose a través de un espacio Euclídeo (17) . Para poder guiarse efectivamente (18) mediante indicaciones, o libre albedrío, por medio de ese espacio, no cabe duda de la importancia de utilizar una serie de puntos o marcas sobre los que referenciarnos mediante triangulación. Mientras que en dicho espacio continuo es relativamente fácil, y arbitrario, el establecimiento de esas marcas, la idea se complica si deseamos extenderla a un espacio discreto, como nos resultaría al tratar de recorrer un grafo. Si en vez de una persona, estuviéramos hablando de un robot de exploración de una red de comunicaciones como la WWW (que no deja de poder interpretarse como un grafo), deberíamos escoger esas marcas como una serie de servidores (nodos del grafo), que estuvieran a unas determinadas distancias conocidas (numero de enlaces). La cuestión que se plantea inevitablemente entonces es: ¿Cuántos (y Qué) servidores me hacen falta para poder desplazarme sin ningún género de dudas a través de la red? ¿Existe un número mínimo de servidores necesarios? ¿Tienen que ser unos en particular, o pueden plantearse múltiples soluciones? En nuestro deambular de cada día, notamos como con tres puntos bien escogidos tenemos suficiente. Utilizar más que éstos únicamente nos aportaría redundancia; es decir, estaríamos en una situación sobredeterminada. Además, la elección de los mismos no tiene porque ser obligatoriamente apostar por unos en particular respecto los otros. Tendremos pues una situación de multiplicidad en las soluciones. 17 El tipo de espacio tridimensional en el que cualquier persona está comúnmente habituada a moverse y pensar. Notar que por abuso hemos reducido un espacio de este tipo a tres dimensiones, pero ello no ha de ser así a la fuerza. 18 Es decir, con absoluta claridad y discernimiento de donde estoy y a donde quiero ir. Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos Enlazando con el inicio de este apartado, podríamos extrapolar que los elem un determinado papel de centralidad identificación unívoca del conjunto de todos los nodos del grafo. Todos los conceptos vistos hasta el momento pueden re Siendo G = (V, E) un grafo finito y conexo nodos u, v , si, y sólo si, se verifica que: a otros dos, u, v , siempre y cuando reste a diferentes distancias de uno y del otro. Si extendemos esta idea de un elemento a un conjunto de elementos, podremos decir entonces que un V (un subconjunto de nodos del grafo), resuelve por entero el grafo (cualquier par de nodos del grafo), soy capaz de encontrar un podrá afirmarse sin lugar a dudas que de sobredeterminación). Dimensión Métrica Q(G) H mínimo cardinal de un Base Métrica de G = El S que se corresponda a la Sea el conjunto de elementos S = {x el vector: r u|S = (d(u, x 1 ), d(u, x 2 Y sus límites conocidos son: R(G) ≤ N – D(G) N ≤ S $ Desgraciadamente, determinar el valor de la dimensión métrica de un grafo es un p difícil , y determinar si su valor es inferior a un cierto valor es implicaciones concretas conlleva lo que acabamos de mencionar es algo que se comprenderá más adelante. 19 Es común el abuso de lenguaje y utilizar dimensión métrica a secas para el conjunto de ambos conceptos. 20 A lo que podríamos añadir “simples y no dirigidos” para no complic 21 Una demostración de ello puede consultarse en la referencia [4] de los artículos de la bibliografía. la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos En el tipo de casos como el de los servidores, se reproducirán también el mismo tipo de situaciones. A número de servidores que me hacen falta para este propósito es lo que denominamos dimensión métrica conjunto de los mismos, es lo que denominamos base métrica Enlazando con el inicio de este apartado, podríamos extrapolar que los elem entos de la base métrica ocupan centralidad . «Centrales » como mínimo desde el punto de vista de su capacidad de identificación unívoca del conjunto de todos los nodos del grafo. Todos los conceptos vistos hasta el momento pueden re sumirse formalmente del siguiente modo: grafo finito y conexo (20) , se dice que un determinado nodo , si, y sólo si, se verifica que: d(x, u) ≠ d(y, v) . Coloquialmente, decimos que un nodo , siempre y cuando reste a diferentes distancias de uno y del otro. Si extendemos esta idea de un elemento a un conjunto de elementos, podremos decir entonces que un (un subconjunto de nodos del grafo), resuelve por entero el grafo G, si para todo par de nodos (cualquier par de nodos del grafo), soy capaz de encontrar un x є S que sea capaz de resolverlos. En tal caso, podrá afirmarse sin lugar a dudas que S será base de G (aunque ello pueda corresponderse a una situación mínimo cardinal de un S que resuelva G. que se corresponda a la Q(G). = {x 1, x 2 , … , x k } T V , entonces las coordenadas de 2 ), …, d(u, x k )) $ U& R$U& - R(G) Siendo N el orden de G, y D(G) Desgraciadamente, determinar el valor de la dimensión métrica de un grafo es un p , y determinar si su valor es inferior a un cierto valor es NPcompleto implicaciones concretas conlleva lo que acabamos de mencionar es algo que se comprenderá más adelante. Es común el abuso de lenguaje y utilizar dimensión métrica a secas para el conjunto de ambos conceptos. A lo que podríamos añadir “simples y no dirigidos” para no complic ar innecesariamente su definición. Una demostración de ello puede consultarse en la referencia [4] de los artículos de la bibliografía. la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 20 En el tipo de casos como el de los servidores, se reproducirán también el mismo tipo de situaciones. A l mínimo número de servidores que me hacen falta para este propósito es lo que dimensión métrica . Y al conjunto de los mismos, es lo que base métrica (19) . entos de la base métrica ocupan » como mínimo desde el punto de vista de su capacidad de sumirse formalmente del siguiente modo: , se dice que un determinado nodo x resuelve a un par de . Coloquialmente, decimos que un nodo x resuelve Si extendemos esta idea de un elemento a un conjunto de elementos, podremos decir entonces que un S T si para todo par de nodos u, v є V que sea capaz de resolverlos. En tal caso, (aunque ello pueda corresponderse a una situación , entonces las coordenadas de u є V sobre S, será D(G) el diámetro de G. Desgraciadamente, determinar el valor de la dimensión métrica de un grafo es un p roblema de tipo NPcompleto (21) . Qué significado e implicaciones concretas conlleva lo que acabamos de mencionar es algo que se comprenderá más adelante. Es común el abuso de lenguaje y utilizar dimensión métrica a secas para el conjunto de ambos conceptos. ar innecesariamente su definición. Una demostración de ello puede consultarse en la referencia [4] de los artículos de la bibliografía. Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos EJEMPLO GRAFO 1 El conjunto S 1 = {A, B, C} es un conjunto que resuelve nodos de G 1 sobre S 1 son: A su vez, es obvio observar que ningún nodo de forma aislada puede resolver Conclusión: R(G 1 ) = 2, y S 2 es una base métrica del mismo EJEMPLO GRAFO 2 El conjunto S 1 = {A, B, C, D} es un conjunto que resuelve inferior. Podríamos co mprobar que no existe ningún conjunto de cardinalidad inferior a 3 Conclusión: R(G 2 ) = 3, y S 2 es una base métrica del mismo. 22 Notar además que esta no es única. Ejemplo: por simple simetría la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos es un conjunto que resuelve G 1 puesto que las coordenadas de los distintos r A|S1 = (0, 1, 1) r D|S1 = (2, 1, 1) r B|S1 = (1, 0, 2) r E|S1 = (1, 2, 1) r C|S1 = (1, 2, 0) r F|S1 = (2, 1, 2) Sin embargo, S 1 no es una ba se métrica de es también un conjunto que resuelve G 1 pero de cardinal inferior. A su vez, es obvio observar que ningún nodo de forma aislada puede resolver G 1 . es una base métrica del mismo (22) . es un conjunto que resuelve G 2 puesto que las coordenadas de los distintos nodos de G 2 sobre S 1 son: r A|S1 = (0, 1, 2, 2) r F|S1 r B|S1 = (1, 0, 1, 2) r G |S1 r C|S1 = (2, 1, 0, 1) r H |S1 r D|S1 = (2, 2, 1, 0) r I |S1 r E|S1 = (1, 2, 2, 1) r J |S1 Sin embargo, S 1 no es una base métrica de G} es también un conjunto que resuelve mprobar que no existe ningún conjunto de cardinalidad inferior a 3 que es una base métrica del mismo. Notar además que esta no es única. Ejemplo: por simple simetría S 3 = {B, D} también ha de ser base métrica. la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 21 puesto que las coordenadas de los distintos = (2, 1, 1) = (1, 2, 1) = (2, 1, 2) se métrica de G 1 ya que S 2 = {A, C} pero de cardinal inferior. puesto que las coordenadas de los distintos F|S1 = (1, 2, 2, 2) |S1 = (2, 1, 2, 2) |S1 = (2, 2, 1, 2) |S1 = (2, 2, 2, 1) |S1 = (2, 2, 2, 2) no es una base métrica de G 2 ya que S 2 = {E, F, es también un conjunto que resuelve G 2 pero de cardinal que pueda resolver G 2 . también ha de ser base métrica. Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 4. ALGORÍTMICA 4.1 INTRODUCCIÓN Una definición no estrictamente formal, pero si suficientemente adecu podemos leer a continuación: una lista bien definida, ordenada y finita de operaciones que permite hallar la solución a un problema . Es decir, planteada una determinada situación a resolver, se parte de un estado inicial y una entrada, y, a través de pasos sucesivos y bien definidos, se persigue y alcanza finalmente un estado correspondiente a la solución En la vida cotidiana se emplean algoritmos en multitud de ocasiones para resolver diversos problemas. La mayoría de ellos los aplicamos de forma inconsciente. Algunos ejemplos se encuentran en los instructivos manuales de usuario, que no dejan de ser Pero el campo donde poseen una mayor y notable presencia consiste en el tipo de pro ser fácilmente abstraídos y matematizados algoritmos. El algoritmo de la división calcular el máximo común divisor de dos lineal de ecuaciones , son manifiestos ejemplos de ello. Más formalmente, para que algo pueda ser considerado propiamente un algoritmo deberá cumplir toda una serie de requisitos: Existencia de un conjunto de entradas, y de sus correspondientes salidas, asociadas al problema. Definible Cada uno de sus pasos ha de poderse definir de forma precisa, y sin dejar lugar a dudas. Efectivo y Finito Sus operaciones han de poderse rea Corrección Ha de ser capaz de poder encontrar la respuesta correcta al problema planteado. Predecible Un determinado conjunto de entradas ha de conducir siempre a la misma salida. 23 Notar que aunque no se mencione, existirá siempre un ente la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos Una definición no estrictamente formal, pero si suficientemente adecu ada, del concepto de algoritmo la una lista bien definida, ordenada y finita de operaciones que permite hallar la . Es decir, planteada una determinada situación a resolver, se parte de un estado una entrada, y, a través de pasos sucesivos y bien definidos, se persigue y alcanza finalmente un estado correspondiente a la solución (23) . En la vida cotidiana se emplean algoritmos en multitud de ocasiones para resolver diversos problemas. La ellos los aplicamos de forma inconsciente. Algunos ejemplos se encuentran en los instructivos manuales de usuario, que no dejan de ser algoritmos para utilizar el aparato. Pero el campo donde poseen una mayor y notable presencia consiste en el tipo de pro matematizados . De hecho, gran parte de las propias matemáticas consisten en división para calcular el cociente de dos números, el algoritmo de Euclides de dos enteros positivos, o el método de Gauss para resolver un s , son manifiestos ejemplos de ello. Más formalmente, para que algo pueda ser considerado propiamente un algoritmo deberá cumplir toda una Existencia de un conjunto de entradas, y de sus correspondientes salidas, asociadas al problema. Cada uno de sus pasos ha de poderse definir de forma precisa, y sin dejar lugar a dudas. Sus operaciones han de poderse rea lizar a la práctica (recursos espacio Ha de ser capaz de poder encontrar la respuesta correcta al problema planteado. Un determinado conjunto de entradas ha de conducir siempre a la misma salida. Los algoritmos pueden se r expresados de muchas maneras, incluyendo el lenguaje natural, el pseudocódigo, los diagramas de flujo diversos lenguajes de programación existentes entre otros. Las descripciones en lenguaje natural tienden a ser ambiguas y extensas. El usar pseu docódigo y diagramas de flujo nos evitará muchas ambigüedades del lenguaje natural, y por ello serán siempre formas de descripción más preferibles. Además, este tipo de descripciones proporcionan una representación lo más desligada posible del elemento pro cesador concreto que finalmente vayamos a utilizar. que aunque no se mencione, existirá siempre un ente ejecutor o procesador de ese conjunto de órdenes. la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 22 ada, del concepto de algoritmo la una lista bien definida, ordenada y finita de operaciones que permite hallar la . Es decir, planteada una determinada situación a resolver, se parte de un estado una entrada, y, a través de pasos sucesivos y bien definidos, se persigue y alcanza finalmente un En la vida cotidiana se emplean algoritmos en multitud de ocasiones para resolver diversos problemas. La ellos los aplicamos de forma inconsciente. Algunos ejemplos se encuentran en los instructivos Pero el campo donde poseen una mayor y notable presencia consiste en el tipo de pro blemas que pueden . De hecho, gran parte de las propias matemáticas consisten en algoritmo de Euclides para para resolver un s istema Más formalmente, para que algo pueda ser considerado propiamente un algoritmo deberá cumplir toda una Existencia de un conjunto de entradas, y de sus correspondientes salidas, asociadas al problema. Cada uno de sus pasos ha de poderse definir de forma precisa, y sin dejar lugar a dudas. lizar a la práctica (recursos espacio -tiempo). Ha de ser capaz de poder encontrar la respuesta correcta al problema planteado. Un determinado conjunto de entradas ha de conducir siempre a la misma salida. r expresados de muchas maneras, incluyendo diagramas de flujo , y los existentes entre otros. Las descripciones en lenguaje natural tienden a ser ambiguas y docódigo y diagramas de flujo nos evitará muchas ambigüedades del lenguaje natural, y por ello serán siempre formas de descripción más preferibles. Además, este tipo de descripciones proporcionan una representación lo más desligada cesador concreto que finalmente vayamos a de ese conjunto de órdenes. Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 4.2 COMPLEJIDAD Y COMPUTABILIDAD En el apartado anterior hemos tratado con la noción de algoritmo. Llegados a este punto, surgen dos categorías bien diferenciadas de preguntas que forman parte esencial d primer lugar cabría preguntarse si para todo problema que pudiéramos plantearnos existe un algoritmo para su resolución. Es decir, ¿Qué puede ser Por otra parte, ante dos, o más, procedimientos de resoluci natural cuestionarse ¿Cuál de ellos es el mejor? para determinar si ¿Existen problemas La primera pregunta corresponde a teoría de la computabilidad , y las restantes a la y de forma breve, las ideas básicas de ambas. 4.2.1 ¿QUÉ PUEDE SER COMPUTABLE La conciencia de este dilema, tal como lo entendemos hoy en día, se originó como respuesta a la cuestión número 10 de los problemas de Hilbert ecuaciones diofánticas (25) , y si existía un iniciaron con este reto condujeron finalmente la conjunción de diferentes trabajos proporcionados por hombres como Gödel, Turing, o Church todo problema podía ser resuelto mediante un algoritmo matemática? ), y diferentes artificios matemáticos que en sus diversas variantes no hacían más que expresar la idea común de computabilidad. 24 Hilbert (matemático de enorme prestigio y reputación), propuso en 1900 una serie de 23 cuestiones fundamentales que marcarían el transcurso de las mate 25 Toda ecuación algebraica sobre el conjunto conjuntoV. Soluciones: (1,4), (2,3), (3,2), (4,1) 26 Todos ellos ligados al estudio de la Lógica dentro de las matemáticas. 27 Destacar el hecho que calificar un problema como no computa práctica, aunque ello pueda implicar una cantidad de recursos espacio temporales exorbitantes. Simplemente nos indica el hecho que no puede traducirse su resolución a un algoritmo tal y como lo entendemos (Máq la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 4.2 COMPLEJIDAD Y COMPUTABILIDAD En el apartado anterior hemos tratado con la noción de algoritmo. Llegados a este punto, surgen dos categorías bien diferenciadas de preguntas que forman parte esencial d e las ciencias de la computación. En primer lugar cabría preguntarse si para todo problema que pudiéramos plantearnos existe un algoritmo para ¿Qué puede ser computable? Por otra parte, ante dos, o más, procedimientos de resoluci ón para un mismo problema resulta también ¿Cuál de ellos es el mejor? Incluso podríamos comparar distintos problemas entre sí ¿Existen problemas «sencillos», y otros «complicados»? La primera pregunta corresponde a la clase de preguntas que se circunscriben al campo de estudio de la , y las restantes a la teoría de la complejidad. Repasaremos pues en este punto, y de forma breve, las ideas básicas de ambas. 4.2.1 ¿QUÉ PUEDE SER COMPUTABLE ? La conciencia de este dilema, tal como lo entendemos hoy en día, se originó como respuesta a la cuestión número 10 de los problemas de Hilbert (24) . Dicha cuestión divagaba sobre nuestra capacidad resolutiva de , y si existía un método universal de resolución. La serie de divagaciones que se iniciaron con este reto condujeron finalmente la conjunción de diferentes trabajos proporcionados por hombres como Gödel, Turing, o Church (26) durante la década de 1930. En particular, determ todo problema podía ser resuelto mediante un algoritmo (27) (Ejemplo: ¿Cuándo es verdadera una sentencia ), y diferentes artificios matemáticos que en sus diversas variantes no hacían más que expresar El artificio más destacado entre todos es el conocido como máquina de turing (MT) . Tal como se ha sugerido hasta el momento, la MT es simplemente un modelo matemático del concepto de algoritmo en sí. Luego, por extensión podemos decir simplemente que e calificar algo como computable, o no computable, únicamente se refiere a si somos capaces de expresarlo, o no, mediante un proceso llevado a cabo por una en un tiempo finito. Hilbert (matemático de enorme prestigio y reputación), propuso en 1900 una serie de 23 cuestiones fundamentales que marcarían el transcurso de las mate máticas a lo largo del siglo XX. Toda ecuación algebraica sobre el conjunto V. Ejemplo: X + Y = 5, que posee únicamente cuatro soluciones sobre el (1,4), (2,3), (3,2), (4,1) . Todos ellos ligados al estudio de la Lógica dentro de las matemáticas. Destacar el hecho que calificar un problema como no computa ble no implica que no pueda ser resuelto en la práctica, aunque ello pueda implicar una cantidad de recursos espacio temporales exorbitantes. Simplemente nos indica el hecho que no puede traducirse su resolución a un algoritmo tal y como lo entendemos (Máq la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 23 En el apartado anterior hemos tratado con la noción de algoritmo. Llegados a este punto, surgen dos e las ciencias de la computación. En primer lugar cabría preguntarse si para todo problema que pudiéramos plantearnos existe un algoritmo para ón para un mismo problema resulta también Incluso podríamos comparar distintos problemas entre sí la clase de preguntas que se circunscriben al campo de estudio de la Repasaremos pues en este punto, La conciencia de este dilema, tal como lo entendemos hoy en día, se originó como respuesta a la cuestión . Dicha cuestión divagaba sobre nuestra capacidad resolutiva de método universal de resolución. La serie de divagaciones que se iniciaron con este reto condujeron finalmente la conjunción de diferentes trabajos proporcionados por durante la década de 1930. En particular, determ inaron que no ¿Cuándo es verdadera una sentencia ), y diferentes artificios matemáticos que en sus diversas variantes no hacían más que expresar El artificio más destacado entre todos es el conocido . Tal como se ha sugerido es simplemente un modelo matemático del concepto de algoritmo en sí. Luego, por extensión podemos decir simplemente que e l hecho de calificar algo como computable, o no computable, únicamente se refiere a si somos capaces de expresarlo, o no, mediante un proceso llevado a cabo por una MT Hilbert (matemático de enorme prestigio y reputación), propuso en 1900 una serie de 23 cuestiones fundamentales que posee únicamente cuatro soluciones sobre el ble no implica que no pueda ser resuelto en la práctica, aunque ello pueda implicar una cantidad de recursos espacio temporales exorbitantes. Simplemente nos indica el hecho que no puede traducirse su resolución a un algoritmo tal y como lo entendemos (Máq uina de Turing). Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 24 La MT consta de un cabezal lector/escritor, y una cinta infinita de celdas en las que el cabezal lee el contenido, borra el contenido anterior, y escribe un nuevo valor. Las operaciones que se pueden realizar en esta máquina se limitan entonces a: • Avanzar el cabezal lector/escritor hacia la izquierda/derecha. • Realizar un computo determinado a partir de una tabla de estados de la forma: (estado, valor) → (nuevo estado, nuevo valor, dirección) Esta tabla toma como parámetros el estado actual de la máquina y el carácter leído de la cinta, dando la dirección para mover el cabezal, el nuevo estado de la máquina y el valor a ser escrito en la cinta. Existe toda una multitud de paradigmas entorno a las MT, y otros artificios, que conforman toda una prolífica comunidad de entes con diferente poder resolución. Es decir, con capacidades de cómputo bien diferenciadas; entendiendo aquí la capacidad de cómputo no en su sentido coloquial de potencial en número de operaciones por segundo, sino en su capacidad de expresar la resolución de problemas. Mencionaremos a modo de ejemplo la variante de las MT no deterministas. Si nos fijamos, vemos como el par (estado, valor) tiene una única asignación. Esto es justamente lo que caracteriza una MT determinista. En caso que tuviéramos múltiples asignaciones, y el proceso de ejecución simplemente escogiera entre una de ellas al azar, estaríamos ante una MT no determinista. Podemos interpretarlo como si en el caso determinista estuviéramos tratando un único camino computacional, mientras que en la no determinista estamos tratando con un árbol computacional. Aunque tanto en un caso como en el otro estamos hablando de entes que tienen el mismo poder de computación, la MT no determinista permite abordar los problemas de forma más rápida. Viene a ser el equivalente a tener varios procesadores (MT deterministas) trabajando en paralelo (28) . 4.4.2 ¿EXISTEN PROBLEMAS SENCILLOS Y OTROS COMPLICADOS? Dados dos algoritmos diferentes para la resolución de la misma tarea (una tarea que ya sabemos que es computable), nos interesará determinar cuál de ellos es mejor que el otro (29) a nivel de consumo de recursos espacio-temporales. Para poder establecer una comparativa efectiva existen dos enfoques. El primero de ellos trata de resolver el dilema por medio de un séquito de pruebas estándar (benchmarking). El segundo realiza una abstracción de carácter matemático. Para las pruebas de benchmarking se suelen ejecutar los distintos algoritmos sobre el mismo computador, y a partir de ahí medir el consumo de recursos de los mismos. Y, aunque en última instancia sea justamente eso lo que realmente importe de verdad, tenemos los problemas propios de la exclusividad inherente a una prueba tan específica. Luego, es francamente difícil, aventurarse en la predicción de su comportamiento si se 28 La forma natural de disponer de una MT no determinista es un computador cuántico. 29 Este tipo de preocupación comenzó a tomarse en serio a finales de la década de 1950, principios de 1960, al iniciarse la popularización de los computadores. Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 25 cambia cualquier pequeña condición. Ya sea por disponer de diferente compilador, lenguaje de programación, computador, o el conjunto de datos de entrada. De la situación acabada de mencionar surge como alternativa el segundo tipo enfoque, el análisis de algoritmos de modo independiente de la implementación y entrada particular. Para ello se procede a un estudio asintótico del mismo, notación O(), con la intención de deducir su orden de complejidad. Consiste en llevar a cabo la siguiente serie de pasos: Abstracción de la entrada Y encontrar así algún parámetro(s) que caractericen el tamaño de la misma. Abstracción de la implementación Y encontrar así alguna medida que refleje su tiempo de ejecución. Considerar el comportamiento asintótico Y encontrar así la tendencia de su procedimiento. EJEMPLO Disponemos del siguiente algoritmo para realizar la suma de todos los elementos de secuencia: función SUMA(secuencia) devuelve un número suma ← 0 desde i ← 1 hasta longitud(secuencia) suma ← suma + secuencia[i] devolver suma Abstracción de la entrada Podemos decir que la entrada se caracteriza por la longitud de la secuencia, que llamaremos n. Abstracción de la implementación En este caso no cuesta mucho observar que el número de pasos del algoritmo es T(n) = 2n + 2. Considerar el comportamiento asintótico n → ∞ W T(n) se comporta como un algoritmo O(n). Notar que en este caso disponemos de un ejemplo concreto que nos predispone a una situación de análisis muy fácil y simple. Sin embargo, en la práctica habitual del análisis de algoritmos resulta muy difícil caracterizar la entrada, e incluso el número de pasos muchas veces. Por orden de complejidad de un problema se entiende el tipo de O() que se corresponde al mejor algoritmo conocido para su resolución. En el caso anterior la complejidad es n, pero es perfectamente posible encontrar problemas de complejidades log(n), n k , n!, etc. Resta claro que un problema de tipo n! resultará en una complejidad de resolución mucho mayor que un problema de tipo log(n). De hecho, las computadoras actuales tienen una capacidad de resolución n k , he incluso ello se limita a valores de k muy pequeños en la práctica. Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 5.5 COMANDO: PROB DESCRIPCIÓN Esta comanda permite estimar las probabilidades que tiene cada nodo de un grafo de formar parte de una hipotética base métrica del mismo. Para obtener este tipo de información será necesario adjuntar todo un conjun to de ficheros de bases calculadas previamente para diferentes valores de secuencia pseudoaleatoria sobre ese mismo grafo. A mayor cardinalidad de este conjunto, mejor estimación. Ya que los diferentes ficheros de bases para un mismo grafo se distinguen me correspondiente a la semilla empleada para inicializar la secuencia pseudoaleatoria, es necesario para la comanda introducir un fichero de sufijos donde cada sufijo resultará ser en verdad una de las semillas empleadas en los procedi mientos de búsqueda previos. FICHERO E/S DESCRIPCIÓN TXT E Conjunto de bases TXT E Semillas empleadas por el comando LAB E Etiquetas de los nodos. PROB S Probabilidades de los nodos en LLAMADA » MDPRO –ID prob –RS seeds_root – FS –RR results_root –FR results_name MODIFICADOR OBLIGATORIO DESCRIPCIÓN RS NO Directorio donde se ubicará el fichero de sufijos. FS SI Nombre del fichero de suf RM NO Directorio donde se ubica el fichero de etiquetas. FM NO Nombre base de los ficheros. RB SI Directorio donde se ubica el conjunto de los ficheros RR NO Directorio donde se ubicará el fichero de salida. FR NO Nombre base del fichero d la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos Esta comanda permite estimar las probabilidades que tiene cada nodo de un grafo de formar parte de una hipotética base métrica del mismo. Para obtener este tipo de información será necesario adjuntar todo un to de ficheros de bases calculadas previamente para diferentes valores de secuencia pseudoaleatoria sobre ese mismo grafo. A mayor cardinalidad de este conjunto, mejor estimación. Ya que los diferentes ficheros de bases para un mismo grafo se distinguen me correspondiente a la semilla empleada para inicializar la secuencia pseudoaleatoria, es necesario para la comanda introducir un fichero de sufijos donde cada sufijo resultará ser en verdad una de las semillas mientos de búsqueda previos. calculadas a priori. Semillas empleadas por el comando METDIM. Etiquetas de los nodos. Probabilidades de los nodos en el formato de pares. FS seeds_name –RM data_root –FM graph_name – RB DESCRIPCIÓN Directorio donde se ubicará el fichero de sufijos. Nombre del fichero de suf ijos. Directorio donde se ubica el fichero de etiquetas. Nombre base de los ficheros. Directorio donde se ubica el conjunto de los ficheros base Directorio donde se ubicará el fichero de salida. Nombre base del fichero d e salida. la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 32 Esta comanda permite estimar las probabilidades que tiene cada nodo de un grafo de formar parte de una hipotética base métrica del mismo. Para obtener este tipo de información será necesario adjuntar todo un to de ficheros de bases calculadas previamente para diferentes valores de secuencia pseudoaleatoria Ya que los diferentes ficheros de bases para un mismo grafo se distinguen me diante un sufijo final correspondiente a la semilla empleada para inicializar la secuencia pseudoaleatoria, es necesario para la comanda introducir un fichero de sufijos donde cada sufijo resultará ser en verdad una de las semillas RB basis_root base . Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 5.6 COMANDOS: INTRAMD/INTERMD DESCRIPCIÓN En este punto describiremos dos ordenes Estas ordenes permiten calcular dos medidas relacionadas con las distancias y los subconjuntos de nodos. En el caso INTRAMD se pretende obtener la distancia media de cada nodo del subconjunto al resto de elementos del subconjunto. En el caso INTERMD se pretende obtener la distancia media de cada nodo respecto a nodos que no formen parte del subconjunto. En ambas será n ecesario incluir tanto el fichero de distancias, como el fichero de subconjunto de etiquetas. FICHERO E/S DESCRIPCIÓN TXT E Etiquetas de los nodos. DST E Parte superior de la matriz de distancias. SETDATA S Distancias calculadas. LLAMADA » MDPRO –ID intramd/intermd –RS data_root –RR results_root –FR results_name MODIFICADOR OBLIGATORIO DESCRIPCIÓN RS NO Directorio donde se ubica el fichero de distancias. FS SI Nombre del fichero de distancias. RM NO Directorio donde se ubica el fichero subconjunto de etiquetas. FM NO Nombre del fichero subconjunto de etiquetas. RR NO Directorio donde se ubicará el fichero de salida. FR NO Nombre base del fichero de salida. la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 5.6 COMANDOS: INTRAMD/INTERMD ordenes simultáneamente debido a su enorme similitud. permiten calcular dos medidas relacionadas con las distancias y los subconjuntos de nodos. se pretende obtener la distancia media de cada nodo del subconjunto al resto de se pretende obtener la distancia media de cada nodo respecto a nodos que no formen ecesario incluir tanto el fichero de distancias, como el fichero de subconjunto de etiquetas. Etiquetas de los nodos. Parte superior de la matriz de distancias. Distancias calculadas. data_root –FS data_name –RM set_root –FM set_name DESCRIPCIÓN Directorio donde se ubica el fichero de distancias. Nombre del fichero de distancias. Directorio donde se ubica el fichero subconjunto de etiquetas. Nombre del fichero subconjunto de etiquetas. Directorio donde se ubicará el fichero de salida. Nombre base del fichero de salida. la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 33 simultáneamente debido a su enorme similitud. permiten calcular dos medidas relacionadas con las distancias y los subconjuntos de nodos. se pretende obtener la distancia media de cada nodo del subconjunto al resto de se pretende obtener la distancia media de cada nodo respecto a nodos que no formen ecesario incluir tanto el fichero de distancias, como el fichero de subconjunto de etiquetas. set_name Directorio donde se ubica el fichero subconjunto de etiquetas. Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 5.7 COMANDO: DK DESCRIPCIÓN Esta comanda permite calcular la distribución Dicha distribución nos permite conocer (para cada nodo) cuantos elementos se encuentran a distancia 1, cuantos a distancia 2, y así sucesivamente hasta distancia k (que coincidir De una manera más intuitiva, podemos afirmar que esta distribución resume para cada nodo que carreteras se observa desde el mismo. FICHERO E/S DESCRIPCIÓN ECC E Excentricidades de cada nodo. DST E Parte superior de la matriz de distancias. DK S Distribuciones Degree LLAMADA » MDPRO –ID dk –RM graph_root – FM MODIFICADOR OBLIGATORIO DESCRIPCIÓN RM NO Directorio donde se ubican los ficheros FM SI Nombre base de los ficheros RR NO Directorio donde se ubicará el fichero de salida. FR NO Nombre base del fichero de salida. la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos distribución Degree-K propia de cada nodo del grado. Dicha distribución nos permite conocer (para cada nodo) cuantos elementos se encuentran a distancia 1, cuantos a distancia 2, y así sucesivamente hasta distancia k (que coincidir á con la excentricidad del nodo). De una manera más intuitiva, podemos afirmar que esta distribución resume para cada nodo que se observa desde el mismo. Excentricidades de cada nodo. de la matriz de distancias. Degree -K de cada nodo. FM graph_name –RR results_root –FR results_name DESCRIPCIÓN Directorio donde se ubican los ficheros ECC, DST. Nombre base de los ficheros ECC, DST. Directorio donde se ubicará el fichero de salida. Nombre base del fichero de salida. la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 34 propia de cada nodo del grado. Dicha distribución nos permite conocer (para cada nodo) cuantos elementos se encuentran a distancia 1, á con la excentricidad del nodo). De una manera más intuitiva, podemos afirmar que esta distribución resume para cada nodo que mapa de Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 5.8 COMANDO: DKE DESCRIPCIÓN Esta comanda permite calcular el Degree Se define esta medida como la desviación típica que presenta la distribución la distribución Degree-K promedio asociada al grafo. Es decir, estamos hablando del error cuadrático medio presente entre las dos distribucione s. Notar que en la medida que el Degree situación y propiedades del mismo dentro del grafo. Siguiendo con la analogía habitualmente empleada, podríamos decir que nos indica que tan diferente e que e speraríamos observar aproximadamente desde un nodo cualquiera del grafo. Notar que un grafo es simétrico si y sólo si desde todos sus puntos se observa el mismo mapa de carreteras; es decir, todo nodo posee un DKE igual a 0. Igualmente, en la medida que exista más dispersión entre los valores de DKE, más no simétrico resultará ser el grafo en cuestión. FICHERO E/S DESCRIPCIÓN LAB E Etiquetas de los nodos. DK E Distribuciones Degree DKE S Degree-K Error de cada nodo. LLAMADA » MDPRO –ID dke –RM graph_root – FM MODIFICADOR OBLIGATORIO DESCRIPCIÓN RM NO Directorio donde se ubican los ficheros FM SI Nombre D SI Diámetro del grafo. RR NO Directorio donde se ubicará el fichero de salida. FR NO Nombre base del fichero de salida. la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos Degree -K Error correspondiente a cada nodo. Se define esta medida como la desviación típica que presenta la distribución Degree promedio asociada al grafo. Es decir, estamos hablando del error cuadrático medio s. Degree -K Error de un nodo particular sea mayor, más particular será la situación y propiedades del mismo dentro del grafo. Siguiendo con la analogía habitualmente empleada, podríamos decir que nos indica que tan diferente e s su mapa de carreteras del mapa de carreteras promedio speraríamos observar aproximadamente desde un nodo cualquiera del grafo. Notar que un grafo es simétrico si y sólo si desde todos sus puntos se observa el mismo mapa de carreteras; nodo posee un DKE igual a 0. Igualmente, en la medida que exista más dispersión entre los valores de DKE, más no simétrico resultará ser el grafo en cuestión. Etiquetas de los nodos. Degree -K de cada nodo. de cada nodo. FM graph_name –D diameter –RR results_root –FR results_name DESCRIPCIÓN Directorio donde se ubican los ficheros LAB, DK. Nombre base de los ficheros LAB, DK. Diámetro del grafo. Directorio donde se ubicará el fichero de salida. Nombre base del fichero de salida. la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 35 Degree -K del mismo respecto a promedio asociada al grafo. Es decir, estamos hablando del error cuadrático medio de un nodo particular sea mayor, más particular será la situación y propiedades del mismo dentro del grafo. Siguiendo con la analogía habitualmente empleada, mapa de carreteras promedio Notar que un grafo es simétrico si y sólo si desde todos sus puntos se observa el mismo mapa de carreteras; nodo posee un DKE igual a 0. Igualmente, en la medida que exista más dispersión entre los results_name Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 5.9 COMANDO: RANDSET DESCRIPCIÓN Esta comanda permite generar pseudoaleatoriamente para un deter subconjuntos de etiquetas de cardinal FICHERO I/O DESCRIPCIÓN LAB I Etiquetas de los nodos. SET.SEED.X O Conjunto de ficheros de subconjuntos de etiquetas. LLAMADA » MDPRO –ID randset –RM graph_ root –RR results_root –FR results_name MODIFICADOR OBLIGATORIO DESCRIPCIÓN RM NO Directorio donde se ubica el fichero de etiquetas. FM SI Nombre base del fichero de etiquetas. SX NO Semilla para inicializar el D NO Tamaño de subconjunto. (def.: N NO Número de subconjuntos a generar. RR NO Directorio donde se ubicará el fichero de salida. FR NO Nombre base del fichero de salida. 41 PRNG = PseudoRandom Number Generator, no es otra cosa que un código de pro una secuencia de números cuyas propiedades se aproximen a las de una secuencia aleatoria. Evidentemente este tipo de programas resultan de gran utilidad a la hora de emular fuentes de aleatoriedad sobre una máquina totalmente determinista como son los computadores actuales. la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos Esta comanda permite generar pseudoaleatoriamente para un deter minado grafo, todo un conjunto de subconjuntos de etiquetas de cardinal D. Etiquetas de los nodos. Conjunto de ficheros de subconjuntos de etiquetas. root –FM graph_name –SX seed -N number -D di mension DESCRIPCIÓN Directorio donde se ubica el fichero de etiquetas. Nombre base del fichero de etiquetas. Semilla para inicializar el PRNG ( 41 ) . (def.: 2) Tamaño de subconjunto. (def.: 0) Número de subconjuntos a generar. (def.: 0) Directorio donde se ubicará el fichero de salida. Nombre base del fichero de salida. = PseudoRandom Number Generator, no es otra cosa que un código de pro grama destinado a proporcionar una secuencia de números cuyas propiedades se aproximen a las de una secuencia aleatoria. Evidentemente este tipo de programas resultan de gran utilidad a la hora de emular fuentes de aleatoriedad sobre una máquina totalmente determinista como son los computadores actuales. la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 36 minado grafo, todo un conjunto de N mension grama destinado a proporcionar una secuencia de números cuyas propiedades se aproximen a las de una secuencia aleatoria. Evidentemente este tipo de programas resultan de gran utilidad a la hora de emular fuentes de aleatoriedad sobre una máquina totalmente Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 5.10 COMANDO: RSORT DESCRIPCIÓN Este comando p ermite ordenar un fichero en el formato habitual de pares « posición de las etiquetas en un fichero auxiliar del mismo formato. Notar que se exige que ambos ficheras contengan el mismo conjunto exacto de etiquetas. FICHERO E/S DESCRIPCIÓN TXT E Conjunto de p ares TXT E Conjunto de pares auxiliar que impondrá el orden de referencia. TXT S Conjunto de pares LLAMADA » MDPRO –ID rsort –RM data_root – FM MODIFICADOR OBLIGATORIO DESCRIPCIÓN RM NO Directorio donde se ubica el fichero FM SI Nombre base del fichero RS NO Directorio donde se FS SI Nombre base del fichero auxiliar que impone el orden. RR NO Directorio donde se ubicará el fichero de salida. FR SI Nombre base del fichero de salida. la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos ermite ordenar un fichero en el formato habitual de pares « etiqueta: valor posición de las etiquetas en un fichero auxiliar del mismo formato. Notar que se exige que ambos ficheras contengan el mismo conjunto exacto de etiquetas. ares sobre el que deseamos ejecutar la ordenación. Conjunto de pares auxiliar que impondrá el orden de referencia. Conjunto de pares ordenados según el fichero auxiliar. FM data_name –RS -FS –RR results_root –FR results_name DESCRIPCIÓN Directorio donde se ubica el fichero con los pares de origen Nombre base del fichero con los pares de origen. Directorio donde se ubica el fichero auxiliar que impone el orden. Nombre base del fichero auxiliar que impone el orden. Directorio donde se ubicará el fichero de salida. Nombre base del fichero de salida. la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 37 etiqueta: valor », en base a la Notar que se exige que ambos ficheras contengan el mismo conjunto exacto de etiquetas. results_name origen . ubica el fichero auxiliar que impone el orden. Nombre base del fichero auxiliar que impone el orden. Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 5.11 COMANDOS: CDET/KDIST/CPRANK DESCRIPCIÓN En este punto describiremos varios comandos dada su similar interfaz. CDET: Coeficiente de Determinación. Este comando calculará el coeficiente de determinación R KDIST: Kendall Distance. Este comando calculará la distancia de Kendall entre dos listas de valores. CPRANK: Correlation Percentile Rank. Este comando calculará la correlación existente entre la pertenencia a los diferentes percentiles. FICHERO E/S DESCRIPCIÓN TXT E Lista 1. TXT E Lista 2. TXT S Fichero donde a djuntar el resultado obtenido LLAMADA » MDPRO –ID cdet/kdist/cprank –RM list1 –RR results_root –FR results_name MODIFICADOR OBLIGATORIO DESCRIPCIÓN RM NO Directorio donde se ubica el fichero FM SI Nombre del fichero RS NO Directorio donde se ubica el fichero FS SI Nombre del fichero RR NO Directorio donde se ubicará el FR SI Nombre base del fichero de salida. la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 5.11 COMANDOS: CDET/KDIST/CPRANK En este punto describiremos varios comandos dada su similar interfaz. CDET: Coeficiente de Determinación. Este comando calculará el coeficiente de determinación R 2 entre dos listas de valores. de Kendall entre dos listas de valores. CPRANK: Correlation Percentile Rank. Este comando calculará la correlación existente entre la pertenencia a los diferentes percentiles. djuntar el resultado obtenido . list1 _root –FM list1_name –RS list2_root –FS list2_ name DESCRIPCIÓN Directorio donde se ubica el fichero q ue contiene la primera lista Nombre del fichero que contiene la primera lista. Directorio donde se ubica el fichero que contiene la segunda lista Nombre del fichero que contiene la segunda lista. Directorio donde se ubicará el fichero de salida. Nombre base del fichero de salida. la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 38 entre dos listas de valores. Este comando calculará la correlación existente entre la pertenencia a los diferentes percentiles. name ue contiene la primera lista . que contiene la segunda lista . Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 5.12 COMANDO: METDIM DESCRIPCIÓN Este comando proporciona el cálculo de la dimensión métrica mediante una metaheurística que, si bien no se corresponde fidedignamente a ninguna en particular, que combina conceptos de Simulated Annealing Partiendo de la generación y modificación pseudoaleatoria de soluciones, se aceptarán o rechazarán las mismas teniendo únicamente en cuent la solución actualmente aceptada ( Threshold Acceptance según un determinado esquema de temperatura ( Como entradas re cibiremos parte de los ficheros generados por el comando necesitaremos el fichero de etiquetas resultados de salida mediante etiquetas, ya que internamente todos l de nodos desligada de ninguna etiqueta (referencia implícita). El segundo nos proporcionará la información clave para formular vectores de coordenadas Como salidas generaremos tres tipos de ficheros. Uno corre correspondiente a las coordenadas de todos los nodos en esa base, y un último fichero que muestra el coste, o adecuación, de esa base respecto una solución perfecta. Notar que como buscamos la dimensión métrica m un cierto nivel, y, de ser así, lo rebajamos y volvemos a buscar), podemos tener cierta multiplicidad de los ficheros acabados de mencionar. En particular, siempre registraremos tanto la última situa haya podido encontrar una solución perfecta (sufijo ser de ese modo (sufijo KO). FICHERO E/S DESCRIPCIÓN DST E Parte superior de la matriz de distancias. LAB E Etiquetas de los nodos. B-XX.SEED S La base métrica. C-XX.SEED S Las coordenadas de los nodos según la correspondiente base métrica. F-XX.SEED S El coste asociado a la base métrica. 42 Recordar que las componentes de un vector de coordenadas, sea en un espacio continuo o discreto, son simplemente las distancias a los respectivos elementos de la base según la métrica utilizada. la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos Este comando proporciona el cálculo de la dimensión métrica mediante una metaheurística que, si bien no se corresponde fidedignamente a ninguna en particular, podemos afirmar que se trata de un procedimiento Simulated Annealing y Threshold Acceptance. Partiendo de la generación y modificación pseudoaleatoria de soluciones, se aceptarán o rechazarán las mismas teniendo únicamente en cuent a que se encuentren dentro de un margen de tolerancia en relación a Threshold Acceptance ). Dicho margen irá variando a lo largo del tiempo según un determinado esquema de temperatura ( Simulated Annealing). cibiremos parte de los ficheros generados por el comando etiquetas LAB, y el fichero de distancias DST . El primero para poder expresar los resultados de salida mediante etiquetas, ya que internamente todos l os cálculos se realizan con la estructura de nodos desligada de ninguna etiqueta (referencia implícita). El segundo nos proporcionará la información clave para formular vectores de coordenadas (42) . Como salidas generaremos tres tipos de ficheros. Uno corre spondiente a los elementos de la base, otro correspondiente a las coordenadas de todos los nodos en esa base, y un último fichero que muestra el coste, o adecuación, de esa base respecto una solución perfecta. Notar que como buscamos la dimensión métrica m ediante un proceso iterativo (comprobamos si existe para un cierto nivel, y, de ser así, lo rebajamos y volvemos a buscar), podemos tener cierta multiplicidad de los ficheros acabados de mencionar. En particular, siempre registraremos tanto la última situa haya podido encontrar una solución perfecta (sufijo OK ), como la primera situación en que no haya podido Parte superior de la matriz de distancias. Etiquetas de los nodos. Las coordenadas de los nodos según la correspondiente base métrica. El coste asociado a la base métrica. Recordar que las componentes de un vector de coordenadas, sea en un espacio continuo o discreto, son simplemente las distancias a los respectivos elementos de la base según la métrica utilizada. la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 39 Este comando proporciona el cálculo de la dimensión métrica mediante una metaheurística que, si bien no podemos afirmar que se trata de un procedimiento Partiendo de la generación y modificación pseudoaleatoria de soluciones, se aceptarán o rechazarán las a que se encuentren dentro de un margen de tolerancia en relación a ). Dicho margen irá variando a lo largo del tiempo cibiremos parte de los ficheros generados por el comando PREDATA. En concreto . El primero para poder expresar los os cálculos se realizan con la estructura de nodos desligada de ninguna etiqueta (referencia implícita). El segundo nos proporcionará la información spondiente a los elementos de la base, otro correspondiente a las coordenadas de todos los nodos en esa base, y un último fichero que muestra el coste, ediante un proceso iterativo (comprobamos si existe para un cierto nivel, y, de ser así, lo rebajamos y volvemos a buscar), podemos tener cierta multiplicidad de los ficheros acabados de mencionar. En particular, siempre registraremos tanto la última situa ción en que se ), como la primera situación en que no haya podido Recordar que las componentes de un vector de coordenadas, sea en un espacio continuo o discreto, son simplemente las distancias a los respectivos elementos de la base según la métrica utilizada. Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 40 LLAMADA » MDPRO –ID metdim –RB basis_root –RC coordenates_root –RF fitness_root –RM data_root –FM data_name –SU startup –SX seed –P0 Nini –P1 Nmax –P2 Nk –P3 Tini –P4 Tmin –P5 Tk MODIFICADOR OBLIGATORIO DESCRIPCIÓN RM NO Directorio donde se ubican los ficheros LAB, DST. FM NO Nombre base de los ficheros LAB, DST. RB NO Directorio donde se ubicarán los ficheros de base. RC NO Directorio donde se ubicarán los ficheros de coordenadas. RF NO Directorio donde se ubicarán los ficheros de fitness. SU SI Valor inicial para la dimensión métrica. SX NO Semilla para inicializar el PRNG . (def.: 2) P0 NO Nini (def.: 1000 iter) P1 NO Nmax (def.: 1000 iter) P2 NO Nk (def.: 0 %) P3 NO Tini (def.: 80 %) P4 NO Tmin (def.: 0 %) P5 NO Tk (def.: 10 %) El PRNG que se ha optado por utilizar es el conocido y ampliamente divulgado «Mersenne Twister». Fue introducido por M.Matsumoto y T.Nishimura en 1997. Aunque no se trata de un algoritmo adecuado para realizar tareas criptográficas, si que se trata de un PRNG muy popular y aceptado. Lo podemos encontrar de serie en entornos tan prestigiosos como MATLAB, o Maple por ejemplo. Es portable, de distribución gratuita, y capaz de generar números aleatorios de gran cualidad con un coste computacional bajo. Todo este conjunto de propiedades lo convierten en una de las elecciones favoritas para la mayoría de aplicaciones. El valor inicial para la dimensión métrica se ha dejado expresamente como un modificador obligatorio por dos motivos. En primer lugar, los limites conocidos para la misma (apartado dimensión métrica) distan mucho de ser cotas útiles para fines prácticos en el tipo de grafos de usual interés (grafos de diámetro bajo). Luego resultaría un poco ridículo proporcionar por defecto acotaciones bastante burdas. En segundo lugar, ello motiva al usuario a tomar mayor consciencia del problema que está tratando. Dentro del grupo de modificadores, encontramos también todo un grupo de elementos referidos al comportamiento particular de la metaheurística. Unos ligados al prefijo N (relacionado con las iteraciones), y otros ligados al prefijo T (relacionado con el coste tolerable). Tanto en Simulated Annealing como en Threshold Acceptance es habitual presentar algún tipo de esquema que regule a lo largo del tiempo nuestra tolerancia para aceptar soluciones de peor coste. En concreto, los esquemas se suelen diseñar para permitir una gran tolerancia inicial y disminuirla progresivamente. Además, suele ser habitual que el número de iteraciones para cada nivel de tolerancia se sostenga a lo largo de todo el proceso. Nuestro algoritmo, por el contrario, dispondrá de sendos esquemas independientes tanto para el coste tolerable, como para el número de iteraciones aplicable. La intención es ofrecer una mayor flexibilidad. Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 41 PSEUDOCÓDIGO funcion ESQUEMA_ITERACIONES(Nini, Nmax, Nk, primera_vez) devuelve Ni número actual de iteraciones entradas: Nini|número inicial de iteraciones Nmax| número máximo de iteraciones permitidos Nk| tasa de incremento de iteraciones primera_vez | una variable booleana Ni ← Nini si primera_vez entonces primera_vez ← FALSE en caso contrario Ni ← Ni * (1 + Nk/100) si Ni > Nmax entonces Ni ← Nmax devolver Ni funcion ESQUEMA_TOLERANCIA (Tini, Tk, primera_vez) devuelve Ti límite actual de tasa de tolerancia entradas: Tini| valor inicial de la tasa de tolerancia Tk| valor de decremento de tasa de tolerancia primera_vez| una variable booleana Ti ← Tini si primera_vez entonces primera_vez ← FALSE en caso contrario Ti ← Ti - Tk devolver Ti Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 48 FAMILIA DISTORSIÓN TÍPICA MÁXIMA (%) DISTORSIÓN PICO (%) BA 6 15 ER 3 5 WS 6 10 CL 4 5 RR 2,5 3 Notar por ejemplo que si contemplamos el caso de una familia cuya distorsión típica máxima es del 6 %, lo que hemos de inferir de ello es que es muy probable que el resultado de una simple búsqueda de la dimensión métrica (en valor relativo al orden) sobre una configuración particular cualquiera de esa familia, contenga una distorsión máxima del 6 %. Por el contrario, la distorsión de pico únicamente nos alerta que, excepcionalmente, podremos observar un valor de distorsión mayor aunque ello se corresponda a una situación poco habitual. De todo ello se desprende finalmente que disponemos de niveles de distorsión inferiores a los dos dígitos, lo que corresponde a una calidad más que aceptable (muy buena) para nuestros fines. ¿Estamos realizando nuestra tarea aprovechando bien nuestros recursos computacionales? Acabamos de exponer el buen comportamiento de nuestra herramienta tanto en exactitud como en calidad, pero cabría preguntarse sin embargo en qué medida obtenemos esas cualidades a costa del consumo de recursos computacionales. Para poder responder adecuadamente a esta pregunta lo ideal sería disponer de estudios alternativos que dispusieran la misma metodología para resolver este mismo problema sobre un entorno de datos y equipamientos común, o, si más no, lo más parecido posible. Obviamente, y por desgracia, raramente podemos encontrarnos ante una situación que cumpla los requisitos mencionados, y nuestro caso tampoco será una excepción. De hecho, únicamente tenemos constancia literaria de un precedente recogido en el punto [8] de los artículos citados en la bibliografía. En dicho estudio se aborda, al igual que en este trabajo, la determinación de la dimensión métrica por medio de procedimientos evolutivos. Sin embargo, la metodología empleada (variación de algoritmos genéticos, GA) pertenece justamente a la vertiente complementaria que hemos utilizado en este trabajo (variación de simulated annealing, SA). Además, el entorno de equipamientos (computadoras, sistemas operativos, uso de las mismas, etc) difiere completamente del empleado en nuestro caso. Tampoco se dispone de un análisis de complejidad que permita establecer paralelismos teóricos entre ambos estudios, aunque afortunadamente si se expone una muestra en pseudocódigo que ciertamente tiende a presentar un funcionamiento mucho más complejo y elaborado a nivel de tareas realizadas con respecto nuestro método. Para tener una idea más clara sobre el funcionamiento e implicaciones de cada una de éstas metodologías se recomienda consultar el anexo: Ejemplos significativos de metaheurísticas. Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 49 Por el contrario, en dicho estudio si se presentan una serie de tablas que resumen el comportamiento del mismo ante toda una serie de casos y datos de entrada de dominio público. En particular se tratan en su mayoría de datos recogidos en la OR-Library (referencias [11] y [10] de los apartados artículos y world wide web de la bibliografía). Evidentemente, parte de los datos presentados en las tablas no son plena o directamente aprovechables para un estudio comparativo exhaustivo (en particular los referentes al tiempo), pero si pueden servirnos para una confrontación cualitativa a falta de otras referencias. Por todo ello, de entre las casuísticas expuestas en ese estudio se han escogido tres situaciones totalmente diferenciadas y significativas para realizar las observaciones pertinentes. En concreto se ha tratado con los datos y resultados correspondientes a crew scheduling, graph coloring, y hypercubes (en su versión más eficiente). Las conclusiones conjuntas para 20 procedimientos reiterados de búsqueda se resumen a continuación: • En las tres primeras columnas encontraremos el nombre concreto de la instancia de datos, su orden y su medida respectivamente. • En la cuarta y quinta columna podremos apreciar el mejor valor de dimensión métrica obtenido en esas 20 ejecuciones que hemos realizado. • De la sexta hasta la penúltima columna encontramos los resultados referentes a la distorsión y la calidad. Se define agap como agap = 2 .Z ∑gapi .Z _`2 , donde gap i = 100 · a4bcdC6 bcdC6 siendo x i el resultado particular de un procedimiento de búsqueda llevado a cabo por GA, o por SA (46) . • Finalmente, en la última columna se presenta el número promedio de llamadas a la función de coste. Instancia n m GA best SA best agap(GA) agap(SA) σ(GA) σ(SA) eval(GA) eval(SA) csp50 50 173 8 9 4,375 0 6,117 0 36.083 9.777 csp100 100 715 11 11 18,182 9,091 7,225 2,875 50.632 21.223 csp150 150 1.355 15 14 11,333 11,786 7,206 5,188 64.532 26.847 csp200 200 2.543 16 17 17,500 4,118 8,009 3,767 66.616 31.689 csp250 250 4.152 18 18 15,278 8,056 6,468 4,111 67.457 34.600 csp300 300 6.108 23 22 13,913 10,910 5,747 3,910 65.291 38.600 csp350 350 7.882 23 24 16,957 5,208 7,039 3,698 68.171 38.716 csp400 400 10.760 26 28 14,038 2,679 5,334 2,961 70.178 37.855 csp450 450 13.510 27 28 13,704 3,571 6,482 2,766 73.985 45.430 csp500 500 16.695 29 30 12,069 5,333 4,405 2,667 78.716 47.376 46 Notar que para el caso de los hypercubes en modo eficiente carecemos de datos originales de GA en cuanto a la distorsión y la calidad, por lo que no hemos podido plantear dicha comparativa. Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 50 Instancia n m GA best SA best eval(GA) eval(SA) Q08 256 1.024 6 6 60.643 8.029 Q09 512 2.304 7 7 74.186 8.010 Q10 1.024 5.120 7 7 74.289 8.083 Q11 2.048 11.264 8 8 76.961 8.015 Q12 4.096 24.576 8 8 85.397 8.265 Q13 8.192 53.248 9 8 80.203 8.383 Q14 16.384 114.688 9 9 76.497 8.610 Q15 32.768 245.760 10 10 73.182 8.739 Q16 65.536 524.288 11 11 79.813 8.810 Instancia n m GA best SA best agap(GA) agap(SA) σ(GA) σ(SA) eval(GA) eval(SA) gcol1 100 2.487 9 8 3,889 11,875 5,437 2,724 72.710 8.688 gcol2 100 2.487 9 8 0 11,875 0 2,724 69.018 8.693 gcol3 100 2.482 9 8 5 11,875 5,671 2,724 78.431 8.705 gcol4 100 2.503 9 9 3,333 0 5,224 0 85.730 8.480 gcol5 100 2.450 9 9 7,222 0 5,437 0 69.733 8.304 gcol6 100 2.537 9 8 9,444 11,875 4,071 2,724 70.069 8.745 gcol7 100 2.505 9 9 1,111 0 3,420 0 78.564 8.503 gcol8 100 2.479 9 9 4,444 0 5,585 0 78.168 8.413 gcol9 100 2.486 9 9 0 0 0 0 68.445 8.483 gcol10 100 2.506 9 9 2,222 0 4,560 0 71.181 8.496 gcol11 100 2.467 9 9 6,111 0 5,671 0 69.559 8.361 gcol12 100 2.524 9 9 0 0 0 0 63.807 8.288 gcol13 100 2.528 9 9 2,778 0 4,936 0 72.769 8.416 gcol14 100 2.493 9 9 1,111 0 3,420 0 75.664 8.377 gcol15 100 2.503 9 9 10,556 0 2,485 0 69.542 8.537 gcol16 100 2.472 9 8 9,444 11,875 4,071 2,724 69.722 8.906 gcol17 100 2.527 9 8 0,556 11,875 2,485 2,724 81.412 8.653 gcol18 100 2.472 9 9 3,889 0 5,437 0 72.586 7.963 gcol19 100 2.527 9 8 7,222 11,875 5,437 2,724 77.772 8.773 gcol20 100 2.420 9 9 6,667 0 5,585 0 77.233 8.332 gcol21 300 22.482 12 12 7,500 0 2,565 0 76.158 9.333 gcol22 300 22.569 12 12 7,083 0 3,053 0 73.900 9.881 gcol23 300 22.393 12 12 7,917 0 1,863 0 75.011 9.488 gcol24 300 22.446 12 12 4,167 0 4,275 0 76.576 9.225 gcol25 300 22.360 12 12 2,083 0 3,702 0 73.867 9.239 gcol26 300 22.601 12 12 7,917 0 1,863 0 72.808 9.293 gcol27 300 22.327 12 12 7,917 0 1,863 0 76.664 9.227 gcol28 300 22.472 12 12 7,917 0 1,863 0 74.252 9.416 gcol29 300 22.520 12 12 7,500 0 2,565 0 76.022 9.520 gcol30 300 22.543 12 12 7,917 0 1,863 0 74.671 9.380 Observando los resultados expuestos en las tablas anteriores podemos extraer las siguientes conclusiones: Nuestra metodología ofrece resultados iguales o superiores en cuanto al mejor valor de dimensión métrica obtenido. Especialmente en el caso de instancias de graph coloring y hypercubes. Únicamente en el caso de instancias de la familia de problemas crew scheduling encontramos los resultados del GA superiores globalmente, aunque sin ser por ello diferencias alarmantes (apenas de una o dos unidades, y sólo en algunos casos). En cuanto al aspecto de la calidad y la distorsión es fácil observar que, a excepción de casos puntuales, proporcionamos unos niveles generales netamente superiores. Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 51 Y, para finalizar, es bien consabido que toda metaheurística tiene un consumo de recursos que depende directamente de la función de coste empleada una vez dejamos de lado las inicializaciones previas, acceso a ficheros, etc. Por tanto, un mayor número de llamadas a la misma tiende a penalizar con un mayor consumo de recursos. Y es justamente en este punto donde la diferencia entre ambas metodologías resulta abrumadoramente estar de nuestra parte. Aunque es muy difícil determinar el coste de cada una de las funciones por separado para poder establecer una comparativa directa, no olvidemos que medir la bondad de un candidato no deja de ser en el fondo una comparativa entre las diferentes coordenadas a las que conduce, y ello se produce tanto en un caso como en el otro. De hecho, en nuestro caso, es seguro que trabajamos con conceptos menos elaborados que hacen mucho más probable un menor empleo de cálculos. 6.2 EVOLUCIÓN DE LA DIMENSIÓN MÉTRICA ¿Evoluciona la dimensión métrica (dentro de una misma familia) siguiendo alguna pauta acorde con el orden y/o la densidad de sus elementos? Para poder contestar satisfactoriamente esta cuestión se han realizado toda una serie de búsquedas independientes para cada casuística particular que se ha considerado significativa. En concreto, para cada familia se ha estudiado el comportamiento de la dimensión métrica para órdenes iguales a: 200, 400, 800 y 1.600 nodos respectivamente. Y para cada uno de esos órdenes se ha tenido en consideración densidades iguales al: 4, 6, 8,… , 84 % (47) . Los resultados obtenidos pueden consultarse en el anexo: Evolución de la β(G) relativa. Notar que para ello partimos de dos premisas: • Contamos con una herramienta que posee un nivel de calidad tal que proporciona (a una única búsqueda) una distorsión suficientemente baja (gráficos de evolución limpios de ruido de búsqueda). • Dada una familia cualquiera, y unas restricciones de orden y densidad particulares, dos elementos generados independientemente poseerán un valor de dimensión métrica muy similar, o, en cualquier caso, con una variación inferior o del mismo orden que nuestro procedimiento de búsqueda. La verificación del primer punto es algo que se ha demostrado fehacientemente en el apartado anterior. El segundo punto puede parecer una perogrullada, pero no deja de ser un hecho implícito presente. La lógica nos dice que el hecho de tener repartidos los nodos y enlaces según una determinada caracterización familiar no ha de producir cambios sustanciales en el valor de la dimensión métrica, y, aunque no adjuntemos un estudio exhaustivo particular para corroborar empíricamente dicha afirmación, si que hemos realizado por nuestra cuenta una serie de pruebas preliminares que no hacen más que adherirse a la misma afirmación. 47 Notar que en el caso particular de la familia BA, las densidades consideradas no han podido ser exactamente las mencionadas ya que su propia distribución de grado (sólo unos pocos nodos altamente conectados), imposibilita alcanzar densidades muy elevadas. Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 52 Centrándonos nuevamente en la cuestión con la que se iniciaba este apartado, y recurriendo a las observaciones que se pueden extraer del anexo mencionado, notamos que la dimensión métrica presenta una determinada evolución particular a cada familia según los condicionantes de orden y/o densidad. En primer lugar se observa como las familias ER y RR presentan unas evoluciones prácticamente idénticas. Este hecho era algo que cabía esperar dentro de lo probable a priori, pero ahora contamos con prueba efectiva de ello. Este hecho nos induce además a suponer que, ante grafos originados mediante el mismo procedimiento de aleatoriedad, la restricción de la regularidad del grado tiene poca o ninguna influencia sobre la dimensión métrica. A partir de este momento pues, todo aquello que mencionemos respecto la familia ER se aceptará también para la familia RR mientras no se mencione lo contrario. En segundo lugar, la familia BA se presenta claramente como un caso diferenciado del resto. Tiene una evolución fundamentalmente plana con respecto la densidad. El aumento de enlaces en juego para un determinado orden no contribuye a alterar significativamente el valor de la dimensión métrica. También se observa una baja dependencia con el orden. Variaciones consistentes en el orden no comportan cambios en el valor relativo de la dimensión métrica de sus elementos. Por todo ello podemos afirmar (a grosso modo) que: la dimensión métrica relativa de un elemento cualquiera de la familia BA se sitúa en un valor genérico aproximado igual o inferior al 5 % (48) . En tercer lugar, tal como se ha mencionado anteriormente en el apartado de nociones teóricas correspondiente, las familias CL, WS y ER forman de hecho un continuum en el que se transcurre de unas a otras en función de la aleatoriedad empleada, y de las delimitaciones comúnmente establecidas y aceptadas en cuanto a los valores de clustering y distancia media. Por todo ello, no es de extrañar que sus respectivas evoluciones guarden algún tipo de relación entre sí; por rara o extraña que esta nos pueda parecer. Si observamos los resultados obtenidos sobre la familia ER (caso extremo p=1), notamos como se presenta una evolución muy clara y determinada en función de la densidad, y que la misma se repite fundamentalmente a menor escala en tanto que aumentamos el orden. También se observan dos zonas de evolución claramente diferenciadas, una primera de carácter lineal, y una segunda de carácter polinomial. Notamos como en la franja de paso entre una zona y la otra (valores de densidad siempre inferiores al 20 %) se presenta un máximo local, y que en plena zona polinomial (valores de densidad entorno al 50 %) se presenta un mínimo local. Notar también como, aproximadamente, la magnitud del mínimo es la mitad de la del máximo. Todo ello viene a decirnos en resumidas cuentas que: la dimensión métrica aumenta proporcional y continuadamente fijado un orden y según aumente la densidad. Pero, a partir de cierta densidad, ese valor comenzará a decrecer paulatinamente hasta alcanzar un mínimo a partir del cual ya despegará ininterrumpidamente. Es decir, dados dos elementos de igual orden, puede ser que el de de menor densidad posea una mayor o menor dimensión métrica (relativa), según sea el valor concreto de la superior densidad del restante. 48 En la gráfica de la familia BA se observan también dos situaciones espureas que se comentaran más adelante. Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos La siguiente figura resume gráficamente el comportamiento descrito: A continuación se establecen una serie de fórmulas extrapoladas de los datos observados, y que pueden ayudarnos a pronosticar el valor de la dimensión métrica relativa que podemos del orden y la densidad para esta familia de grafos. ZONA LINEAL y ~ (0,487) x ZONA POLINOMIAL y ~ a x 2 + b a ~ 0,004 e – 0,57 b ~ -0,001 e 2 + 0,036 e - 0,38 c ~ 19,76 e – 0,56 donde se define: e = (N/100) Se sobrentiende que «x» es la densidad, e « Si observamos los resultados obtenidos sobre la familia CL (caso extremo p=0), el resumen de su comportamiento presenta una imagen mu 49 Ambos valores en tanto por ciento. la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos La siguiente figura resume gráficamente el comportamiento descrito: A continuación se establecen una serie de fórmulas extrapoladas de los datos observados, y que pueden ayudarnos a pronosticar el valor de la dimensión métrica relativa que podemos esperar obtener en función del orden y la densidad para esta familia de grafos. x + (1,633) b x + c siendo N el orden del grafo. la densidad, e « y» la dimensión métrica en valor relativo Si observamos los resultados obtenidos sobre la familia CL (caso extremo p=0), el resumen de su comportamiento presenta una imagen mu y distinta de la anterior. la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 53 A continuación se establecen una serie de fórmulas extrapoladas de los datos observados, y que pueden esperar obtener en función en valor relativo (49) . Si observamos los resultados obtenidos sobre la familia CL (caso extremo p=0), el resumen de su Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos Sin embargo, existen puntos en común. Podemos dividir la evolución en dos zonas claramente diferenciadas y de evolución predecible. Una zona lineal inicial, y una zona llena de discontinuidades. Además, la franja que separa un a de la otra resta para valores de densidad muy similares al umbral presente en la familia ER. En el caso anterior, el aumento del orden provocaba indiferencia en la zona lineal y una disminución de escala en la zona polinomial. Ahora, se esté en la zona contribuye directa y sistemáticamente a una mayor dimensión métrica relativa. Pero mientras en la zona discontinua esa diferencia tiende a ser un valor constante respecto las variaciones de la densidad, en lineal esa diferencia se agudiza en la medida que la densidad aumenta. Notar finalmente que, en la zona de discontinuidades, mientras no se produzca una discontinuidad propiamente, el valor de la dimensión métrica relativa tiende a mantenerse inse densidad para un mismo orden. Es decir, se observa una evolución plana. A continuación se establecen también una serie de fórmulas extrapoladas de los datos observados. ZONA LINEAL y ~ m x + n m ~ 0,074 e + 0,004 n ~ 0,250 e – 3,3 donde se define: e = (N/100) Se sobrentiende que «x» es la densidad, e « ZONA DISCONTINUA U na serie de incrementos fijos y bastante independientes de En medio de las dos situaciones anteriores, encontramos el caso de la familia WS (caso p=0,01). A diferencia de sus predecesoras, en esta familia no podemos visualizar una relación tan clara entre la dimensión métrica relativa, y el orden y la densidad respectivamente. A lo sumo podemos establecer el paralelismo de poseer también dos zonas diferenciadas, situándose el umbral de cambio entre una y la otra en el doble de las anteriores (~ 40 %). la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos Sin embargo, existen puntos en común. Podemos dividir la evolución en dos zonas claramente diferenciadas y de evolución predecible. Una zona lineal inicial, y una zona llena de discontinuidades. Además, la franja a de la otra resta para valores de densidad muy similares al umbral presente en la familia ER. En el caso anterior, el aumento del orden provocaba indiferencia en la zona lineal y una disminución de escala en la zona polinomial. Ahora, se esté en la zona lineal o en la discontinua, el aumento del orden contribuye directa y sistemáticamente a una mayor dimensión métrica relativa. Pero mientras en la zona discontinua esa diferencia tiende a ser un valor constante respecto las variaciones de la densidad, en lineal esa diferencia se agudiza en la medida que la densidad aumenta. Notar finalmente que, en la zona de discontinuidades, mientras no se produzca una discontinuidad propiamente, el valor de la dimensión métrica relativa tiende a mantenerse inse nsible a los cambios en la densidad para un mismo orden. Es decir, se observa una evolución plana. A continuación se establecen también una serie de fórmulas extrapoladas de los datos observados. n siendo N el orden del grafo. la densidad, e « y» la dimensión métrica en valor relativo. na serie de incrementos fijos y bastante independientes de En medio de las dos situaciones anteriores, encontramos el caso de la familia WS (caso p=0,01). A diferencia de sus predecesoras, en esta familia no podemos visualizar una relación tan clara entre la dimensión métrica y el orden y la densidad respectivamente. A lo sumo podemos establecer el paralelismo de poseer también dos zonas diferenciadas, situándose el umbral de cambio entre una y la otra en el doble de las la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 54 Sin embargo, existen puntos en común. Podemos dividir la evolución en dos zonas claramente diferenciadas y de evolución predecible. Una zona lineal inicial, y una zona llena de discontinuidades. Además, la franja a de la otra resta para valores de densidad muy similares al umbral presente en la familia ER. En el caso anterior, el aumento del orden provocaba indiferencia en la zona lineal y una disminución de lineal o en la discontinua, el aumento del orden contribuye directa y sistemáticamente a una mayor dimensión métrica relativa. Pero mientras en la zona discontinua esa diferencia tiende a ser un valor constante respecto las variaciones de la densidad, en la zona Notar finalmente que, en la zona de discontinuidades, mientras no se produzca una discontinuidad nsible a los cambios en la A continuación se establecen también una serie de fórmulas extrapoladas de los datos observados. en valor relativo. na serie de incrementos fijos y bastante independientes de l orden: ~ 4, 7, 10, 12 %. En medio de las dos situaciones anteriores, encontramos el caso de la familia WS (caso p=0,01). A diferencia de sus predecesoras, en esta familia no podemos visualizar una relación tan clara entre la dimensión métrica y el orden y la densidad respectivamente. A lo sumo podemos establecer el paralelismo de poseer también dos zonas diferenciadas, situándose el umbral de cambio entre una y la otra en el doble de las Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 55 La primera zona correspondería a una franja donde la evolución de la dimensión métrica estaría sometida a curvas de fuertes variación (que hemos representado simbólicamente), y, en la segunda, estaríamos ante una evolución mucho más suave, lineal, decreciente, y predecible. La interpretación lógica más plausible de todo ello es tomar este caso como lo que el origen de esta familia podía preestablecer. Una situación intermedia de tránsito entre dos formas de evolución muy claras y diferenciadas (de ahí lo difícil de una formulación analítica simple). Conocidos a priori la dimensión métrica, el orden, y la densidad de un grafo, ¿Puedo aventurar a qué familia pertenece ese grafo? Poder aventurarse en la realización de predicciones de este tipo de características es una tarea que se antoja imposible. De las gráficas expuestas en el anexo antes mencionado, se extrae como conclusión que, independientemente de la familia particular con la que tratemos, los valores de dimensión métrica (en términos relativos) son ciertamente muy parecidos entre sí aunque posean una evolución muy definida. Como extremo de ello encontramos el caso de las familias ER y RR, cuya evolución es prácticamente idéntica, imposibilitando así la plena identificación de la casuística en la que nos encontramos (dados únicamente los datos del enunciado). A lo sumo podremos encontrar alguna situación concreta en la que sí que reste muy claro el tipo de familia que nos llevamos entre manos, como por ejemplo una situación en que la dimensión métrica relativa sea del 65 %, el orden igual a 1600, y la densidad igual al 80 %, que corresponde inequívocamente a la familia CL. Así pues, parece que habremos de conformarnos con poder realizar predicciones en la evolución de la dimensión métrica de modo introspectivo a cada familia, y, aún así, de modo únicamente aproximado. ¿Existe alguna concordancia entre las variaciones a nivel de características familiares tenidas en consideración, y las variaciones observadas en el valor de la dimensión métrica? Las características familiares tenidas en consideración han sido: betweenness centrality, clustering, distancia media, diámetro, y degree-K error. Sus evoluciones (50) se recogen en los respectivos anexos de gráficos de datos familiares. De su simple observación se constata que ninguna de estas características tiene una evolución pareja y sistemática. Sin embargo, se alertan algunos hechos a destacar. Al igual que en la familia BA teníamos presente dos espurios difíciles de enmarcar dentro de la propia evolución de la dimensión métrica relativa, encontramos espurios en idénticas condiciones para el clustering y el degree-K error. Por el contrario, la evolución del resto de puntos de esas mismas características no se corresponden en absoluto con la evolución de la dimensión métrica. Luego, su relación entre sí es más que dudosa. Puede ser simple coincidencia, un tercer desconocido que las afecta a todas, una excepción, etc. 50 Nos estamos refiriendo siempre a la evolución del valor medio aritmético de cada propiedad asociado al grafo. Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 56 Por el contrario, sí que es presumible que los cambios en el diámetro guarden una estrecha relación con la evolución de la dimensión métrica. Que existe una relación entre ambos conceptos es algo ya consabido por las mencionadas cotas: R(G) ≤ N – D(G) N ≤ S$U& R$U& - R(G) siendo N el orden de G, y D(G) el diámetro de G. Pero, en términos de la evolución métrica relativa, sus efectos se mostrarían más notablemente que cualquier otra característica familiar tenida en cuenta; especialmente para todas las familias menos para BA. ¿En qué consistirían esos efectos? En el caso de la familia ER, mientras se pudieran producir saltos en el diámetro (decrementos) estaríamos en zona lineal. Una vez el diámetro entrara en saturación, estaríamos en zona polinomial. En el caso de la familia CL, observaríamos que mientras la disminución del diámetro se produjera de modo continuado, la evolución de la dimensión métrica sería lineal. Por el contrario, el inicio de saltos en el diámetro se correspondería con la zona de discontinuidades. La familia WS, al ser una situación transitoria, se encontraría un poco en tierra de nadie. Una vez saturado el diámetro se entraría en esa zona entre lineal y polinomial, mientras que los momentos previos se corresponderían a la zona de ardua caracterización. Notar pues como la saturación del diámetro se corresponde con el umbral de cambio entre zonas. 6.3 BASES MÉTRICAS VERSUS CONJUNTOS ALEATORIOS A nivel de conjuntos de nodos, ¿Qué diferencias en características se observan entre aquellos que son base métrica y aquellos que podríamos formar aleatoriamente? Para responder a esta interesante planteamiento se ha realizado el siguiente experimento. En primer lugar se ha seleccionado por una parte toda la serie de soluciones generadas en los cálculos necesarios para la determinación de la evolución de la dimensión métrica. Y, en segundo término, para cada uno de los grafos a los que se correspondían esas soluciones, se ha procedido a extraer (51) un conjunto aleatorio de nodos (52) para llevar a cabo posteriormente la confrontación de propiedades de interés. Notar que realmente no se ha procedido a sacar un único conjunto del grafo en cuestión, ya que la confrontación de sus propiedades con las de un conjunto base resultaría aberrante. Así pues, la tarea ha consistido en sacar toda una serie de conjuntos para confrontar su propiedad media (53) con respecto la media de esa propiedad para el conjunto base. El tamaño de la serie se ha escogido con la intención de 51 Empleando una combinación de comandos auxiliares de nuestro programa. 52 Teniendo evidentemente sumo cuidado con hacer coincidir el cardinal de estos conjuntos con el valor de dimensión métrica pertinente. 53 Notar que este valor medio es lógicamente una media de valores medios. Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 57 mantener la representatividad en todo momento. Es decir, no es lo mismo 10 conjuntos aleatorios sobre un espacio de 200 nodos, que 10 conjuntos sobre un espacio de 1.600 nodos. La serie de propiedades que se han tenido en estima para la confrontación son: betweenness centrality, clustering, distancia media, diámetro, degree-K error, grado medio, distancia media entre elementos del conjunto, distancia media entre elementos ajenos al conjunto. Es decir, las mismas que habíamos utilizado en el apartado anterior (cuando comparábamos únicamente evoluciones a nivel familiar), más el añadido de estas distancias especiales que, evidentemente, no nos podíamos plantear por su propia definición hasta este momento. Toda la serie de datos derivados de este experimento pueden consultarse uno a uno en los respectivos anexos de correlación entre los diferentes tipos de conjuntos para cada una de las mencionadas propiedades. En la tabla siguiente se resumen los coeficientes de determinación (54) encontrados: PROPIEDAD FAMILIA BA RR ER WS CL Betweenness 0,440 0,999 0,947 0,797 --- Clustering 0,956 1 0,999 0,997 --- Dist. media 0,939 1 0,996 0,995 --- Dist. intra 0,858 0, 981 0,973 0,989 0,980 Dist. inter 0,941 1 0,997 0,995 1 Excentricidad 0,894 0,996 0,992 0,999 --- Grado medio 0,960 1 0,999 1 --- Degree - K error 0,839 1 0,836 0,994 --- Valorar e interpretar el coeficiente de correlación es algo que indudablemente depende del contexto y nuestros propósitos. Aun así, los resultados anteriores dejan poca alternativa a una interpretación diferente a la siguiente: entre un conjunto base y otro cualquiera, no podemos encontrar una diferencia apreciable entre el valor medio de ninguna de las características estudiadas. Y todo ello de modo transversal a la familia de pertenencia. Desde luego no se trata de una afirmación que resulte ni agradable, ni deseada, pero es lo que se ha reportado del análisis de los datos. La conclusión genérica más benévola de todo ello es que no hemos empleado aquella característica que si pueda mantener una estrecha relación con la dimensión métrica (si es que realmente existe alguna que así lo verifique). Queda constatado pues que ninguna de las típicas medidas de centralidad: betweenness, dist. media, grado medio tiene una traslación directa a nivel de conjunto base. Luego, resta claro que la dimensión métrica ofrece una perspectiva de centralidad totalmente distinta a las anteriores. Llama también la atención que características como la distancia media entre elementos del propio conjunto, o de elementos ajenos al mismo, no ofrezcan tampoco ningún cambio significativo. Propiedades que a priori podían entrar a formar parte claramente del juego de la especulación de las relaciones plausibles. 54 Recordar que, en el caso de intento de ajuste mediante un modelo lineal, éste no es más que la raíz cuadrada del coeficiente de correlación. Normalmente lo representamos como R 2 . Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 64 7 CASOS REALES En este punto únicamente haremos mención a una serie de casos de estudio y aplicación sobre redes reales que hemos tenido en consideración a fin de remarcar la utilidad práctica de la herramienta desarrollada. Las redes consideras han sido las siguientes: Dolphins Network: Una comunidad de delfines que viven en Doubtful Sound, Nueva Zelanda. Les Misérables Network: Las interacciones entre los personajes principales de la famosa novela de V. Hugo. Scientific Collaboration Network: Red de colaboraciones entre los investigadores de los sistemas de redes. Zachary Karate Club: Relaciones sociales en un club de karate. Para cada uno de ellos hemos realizado una serie reiterada de búsquedas de la dimensión métrica. En las siguientes tablas se resume los principales resultados de interés, y en el anexo: IMÁGENES DE CASOS REALES podemos encontrar una serie de visualizaciones de cada grafo en donde la intensidad del color del nodo nos indica en que medida es más o menos probable que esté presente en una base métrica de acuerdo con las estimaciones realizadas. Notar que el significado del contenido de las columnas es el mismo que el empleado en el apartado anterior dedicado al estudio comparativo con el caso de referencia. Únicamente añadimos una última columna donde se muestra el nivel de variabilidad relativa en cuanto a las magnitudes de probabilidad. instancia n m Β(G) Best agap σ % Prob dolphins 62 159 6 0 0 1 58 . 2631 l esmis 77 257 31 ~ 0 ~ 0 88 . 5283 n etscience 379 914 186 23.1004 15 .3362 26 . 8283 zachary 34 78 10 ~ 0 ~ 0 1 12 . 3380 Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 65 8 CONCLUSIONES Al inicio de este trabajo nos habíamos fijado una serie de propósitos que repasaremos a continuación: Diseñar e implementar un software capaz de determinar la dimensión métrica de un grafo cualquiera Sin lugar a dudas hemos logrado implementar de modo totalmente satisfactorio un pequeño programa que ha demostrado su plena capacidad para el cálculo de la dimensión métrica mediante un procedimiento de carácter metaheurístico. El mismo ha sido desarrollado en lenguaje de programación C, con una composición eficiente, moderna, flexible y fácilmente editable. Su versatilidad y eficacia en todo tipo de situaciones (grafos matemáticos, modelizaciones, y de ámbito real) corroboran su amplio espectro de utilidad y generalidad, imponiendo por el contrario restricciones muy comunes en los ficheros descriptores de grafos habituales en este campo. Comprobar su calidad, eficiencia y utilidad real en diversas casuísticas y situaciones Tal como hemos acabado de mencionar, y como se ha visto a lo largo de todo el trabajo, su aplicación en todo tipo de casuísticas se ha visto plenamente contrastada. En particular, hemos observado experimentalmente como se ha verificado una excelente calidad (variabilidad inferior a los dos dígitos), de modo muy transversal a los condicionantes de familia, orden y densidad. Se ha podido establecer además una comparativa de comportamiento con la única referencia bibliográfica disponible de la que se tiene constancia. Los resultados avalan de forma abrumadora nuestra alternativa como una opción de eficacia similar pero de prestaciones computacionales y cualitativas muy superiores. Averiguar tanto como podamos sobre las propiedades y el comportamiento de la dimensión métrica Un extenso trabajo con los principales modelos comúnmente contemplados en los entornos de investigación nos ha reportado resumidamente la siguiente información: La dimensión métrica de toda familia evoluciona de un modo determinado y predecible de acuerdo al orden y la densidad. Aunque el modo exacto en que se produce la misma es totalmente particular a cada familia, la proximidad de sus valores concretos imposibilita generalmente el establecimiento de un modelo de pertenencia a priori. Así pues, nuestra capacidad de predicción se ve circunscrita a cada caso concreto. Ni de modo familiar, ni a nivel de conjuntos se ha podido observar una relación vinculante entre la misma y toda una serie de propiedades de uso y contemplación común en la literatura como son el grado, el diámetro, la distancia media, distancias intra o inter grupales, el clustering, la betweenness centrality o el degree-k error. Sin embargo, si se ha podido establecer que en todo caso se produce una no arbitrariedad tanto en la elección de los nodos como en la conformación de las bases métricas. La aplicación de técnicas no paramétricas si han podido confirmar relaciones positivas de tendencia en todos los casos, y para todas las propiedades mencionadas anteriormente. A modo de trabajos futuros, se sugiere por tanto un enfoque de la cuestión más profundo y detallado a nivel estadístico, así como el empleo de medidas y propiedades de grafos de carácter más globales. Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 66 9 BIBLIOGRAFÍA 9.1 ARTÍCULOS [1] A.L. Barabási, E. Bonabeau. Scale-Free Networks, Scientific American, 288:60-69, May 2003. [2] Cohen David. All the world’s a net», New Scientist, vol. 174 issue 2338-13, April 2002, page 24. [3] D.J. Watts, S.H. Strogatz. Collective Dynamics of ‘Small-World’ Networks», Nature 393, 440-442, 1998. [4] S. Khuller, B. Raghavachari, A. Rosenfeld. Landmarks in graphs», Discrete Applied Mathematics 70, 217-229, 1996. [5] F. Comellas, R. Roca. Using Genetic Algoritms to Design Constant Weight Codes, Applications of Neural Networks to Telecommunications pp. 119-124, 1993. [6] J. Cáceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, C. Seara. On the metric dimension of some families of graphs, Electronic Notes in Discrete Mathematics, 22 (2005) pp. 129-133. [7] M.E.J. Newman. The Structure and Function of Complex Networks, eprint arXiv:cond-mat/0303516, 03/2003. [8] Kratica J., Kovačević-Vujčić V., Čangalović M. Computing the metric dimension of graphs by genetic algorithms. Computational Optimization and Applications, in press, 2008. doi:10.1007/s10589-007-9154-5. [9] J. Kleinberg, C. Papadimitriou. Computability and Complexity, Computer Science: Reections on the Field, Reections from the Field, Natl. Academies Press, 2004. [10] Gunter Dueck, Tobias Scheuer. Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing, Journal of Computational Physics, Volume 90 , Issue 1 (September 1990) Pages: 161 – 175. [11] J.E. Beasley. OR-Library: distributing test problems by electronic mail», Journal of the Operational Research Society 41(11) (1990) pp1069-1072. 9.2 LIBROS [1] F. Comellas, J. Fàbrega, A. Sànchez, O. Serra. Matemàtica discreta. Edicions UPC 1994. ISBN 84-765-3413-2. [2] H. Fernández-Abascal, M.M. Guijarro, J.L. Rojo, J.A. Sanz. Cálculo de Probabilidades y Estadística. Ediciones Ariel Economía 1994. ISBN 84-344-2094-5. [3] A. Papoulis, S.U. Pillai. Probability, Random Variables and Stochastic Processes. McGraw-Hill 2002. ISBN 0-07-112256-7. [4] S. Russell, P. Norvig. Inteligencia Artificial. Un Enfoque Moderno. Prentice Hall 2004. ISBN 84-205-4003-X. [5] B.W.Kernighan, D.M. Ritchie. El lenguaje de programación C. Prentice Hall 1991. ISBN 968-880-205-0. [6] F.J. Ceballos. Programación orientada a objetos con C++, Ediciones Ra-Ma 1997. ISBN 84-7897-268-4. Estudio de la Dimensión Métrica de Grafos mediante Algoritmos Evolutivos 67 9.3 WORLD WIDE WEB [1] http://www.wikipedia.org → Página de información general. [2] http://www.indopedia.org/Main_Page.html → Página de información temática. [3] http://www.python.org → Página principal de Python. [4] http://networkx.lanl.gov → Página principal de la librería NetworkX. [5] http://www.fcalzado.net/logica → Página de contenidos teórico matemáticos. [6] http://docencia.udea.edu.co/SistemasDiscretos/ → Página de contenidos teórico matemáticos. [7] http://www.analytictech.com/mgt780/topics/centrality.htm → Página de contenidos teórico matemáticos. [8] http://www.aaai.org/AITopics/pmwiki/pmwiki.php/AITopics/HomePage → Página sobre Inteligencia Artificial. [9] https://noppa.tkk.fi/noppa/kurssi/s-114.4150/etusivu → Página de contenidos teórico matemáticos. [10] http://people.brunel.ac.uk/~mastjjb/jeb/info.html → Página principal de la OR-Library. 68 ANEXO ANEXO: ALMACENAMIENTO DE GRAFOS MATRIZ DE ADYACENCIAS Es una matriz N x N (N el orden del grafo). El elemento conexión entre los nodos i y j. LISTA DE ADYACENCIAS En este caso, simplemente dispondremos de una lista (no necesariamente ordenada) de las adyacencias COMPROMISOS DE UTILIZACIÓN Los criterios de preferencia de un formato respecto al resto deberán tener en cue • CONSUMO DE ESPACIO La matriz de adyacencias puede ocasionar un gran desperdicio de memoria por el hecho imperioso de explicitar enlaces no existentes. Ello se acusa especialmente en grafos dispersos , o también denominados de • CONSUMO DE TIEMPO Computacionalmente hablando, no cuesta lo mismo preguntarse: conexión entre dos nodos dados? la lista habremos de realizar una búsqueda. Y viceversa, Tiene respuesta inmediata en una lista, y un procedimiento de búsqueda en la matriz. • TROS ASPECTOS Existen una multitud d nuestra elección. La disponibilidad y el formato de origen de los datos, su posterior difusión y compatibilidad, facilitar la representación visual, particularidades de los software de interés, et 58 En el anexo « ESTRUCTURAS DE DATOS 59 En la práctica, la mayoría de grafos abstraídos de la realidad son dispersos ( ANEXO: ALMACENAMIENTO DE GRAFOS El tratar con grafos conlleva, ineludiblemente, la cuestión de su almacenamiento tarde o temprano. Existen, fundamentalmente, dos alternativas te óricas de representación de los mismos. En la práctica, nos encontraremos con toda una variada comunidad de formatos disponibles. Unos enfatizaran unos aspectos (claridad, transportabilidad,…), y otros añadirán ciertas funcionalidades (pesos en los enlaces , colores de los nodos,…). Pero, al fin y al cabo, siempre responderán a una de las dos vertientes teóricas. el orden del grafo). El elemento a ij nos indicará si existe (valor = 1), o no (valor = 0), En este caso, simplemente dispondremos de una lista (no necesariamente ordenada) de las adyacencias Los criterios de preferencia de un formato respecto al resto deberán tener en cue nta tres aspectos: La matriz de adyacencias puede ocasionar un gran desperdicio de memoria por el hecho imperioso de explicitar enlaces no existentes. Ello se acusa especialmente en grafos , o también denominados de baja densidad 59 . La densidad de un grafo la medimos como: f H |h| 3 $3 4 ?& 0 ≤ f ≤ 1 Computacionalmente hablando, no cuesta lo mismo preguntarse: conexión entre dos nodos dados? En un caso que en el otro. En la matriz la respuesta es inmediata, y en la lista habremos de realizar una búsqueda. Y viceversa, ¿Cuáles son los nodos adyacentes a otro dado? Tiene respuesta inmediata en una lista, y un procedimiento de búsqueda en la matriz. Existen una multitud d e aspectos no puramente técnicos que influyen (y mucho), en nuestra elección. La disponibilidad y el formato de origen de los datos, su posterior difusión y compatibilidad, facilitar la representación visual, particularidades de los software de interés, et ESTRUCTURAS DE DATOS », se constata el hecho que en este trabajo se emplea la vertiente de listas. En la práctica, la mayoría de grafos abstraídos de la realidad son dispersos ( f → 0). 69 El tratar con grafos conlleva, ineludiblemente, la cuestión de su almacenamiento tarde o temprano. Existen, fundamentalmente, óricas de representación de los mismos. En la práctica, nos encontraremos con toda una variada comunidad de formatos disponibles. Unos enfatizaran unos aspectos (claridad, transportabilidad,…), y otros añadirán ciertas funcionalidades , colores de los nodos,…). Pero, al fin y al cabo, siempre responderán a una de las dos vertientes teóricas. nos indicará si existe (valor = 1), o no (valor = 0), En este caso, simplemente dispondremos de una lista (no necesariamente ordenada) de las adyacencias 58 . nta tres aspectos: La matriz de adyacencias puede ocasionar un gran desperdicio de memoria por el hecho imperioso de explicitar enlaces no existentes. Ello se acusa especialmente en grafos . La densidad de un grafo la medimos como: Computacionalmente hablando, no cuesta lo mismo preguntarse: ¿Existe respuesta es inmediata, y en ¿Cuáles son los nodos adyacentes a otro dado? Tiene respuesta inmediata en una lista, y un procedimiento de búsqueda en la matriz. e aspectos no puramente técnicos que influyen (y mucho), en nuestra elección. La disponibilidad y el formato de origen de los datos, su posterior difusión y compatibilidad, facilitar la representación visual, particularidades de los software de interés, et c. », se constata el hecho que en este trabajo se emplea la vertiente de listas. ANEXO: COMPARATIVA DE LOS MODELOS DE GRAFOS Notar que en la columna P(k) únicamente figuran aquellas distribuciones más singulares y exclusivas del tipo de grafo asociado TIPO CLASE/MODELOS ALEATORIOS ALEATORIO BINOMIAL Mod Erdös ALEATORIO K Modelos Kim McKay MUNDO REAL ANILLOS K-REGULARES ANILLOS K ANEXO: COMPARATIVA DE LOS MODELOS DE GRAFOS únicamente figuran aquellas distribuciones más singulares y exclusivas del tipo de grafo asociado . CLASE/MODELOS P(k) ALEATORIO BINOMIAL Mod elos Erdös - Rényi ALEATORIO K -REGULAR Modelos Kim - Vu McKay - Wormald ANILLOS K -REGULARES 70 D.MEDIA CLUSTER CORTA BAJO MEDIO CORTA MEDIO ALTO LARGA ALTO 71 ANEXO: EJEMPLOS SIGNIFICATIVOS DE METAHEURÍSTICAS Dentro del campo de las metaheurísticas existen dos enfoques principales para realizar la búsqueda y comprobación de soluciones. Las búsquedas pueden enfocarse bien de modo local, o bien de modo global, según el recorrido del espacio de soluciones que propugnen. En modo local encontramos simulated annealing, búsqueda tabú, variable neighbourhood,… Y en modo global encontramos algoritmos genéticos, hormigas, miméticos,… A continuación detallaremos a modo de ejemplo una metaheurística clásica de cada tipo de enfoque. SIMULATED ANNEALING Este algoritmo prueba de imitar el proceso de temple del acero. Esta técnica consiste en calentar y enfriar de forma alternada y controlada un material para aumentar el tamaño de sus cristales y reducir así sus defectos. El calor causa que los átomos se salgan de sus posiciones iníciales (un mínimo local de energía), y se muevan aleatoriamente; el enfriamiento lento les da mayores probabilidades de encontrar configuraciones con menor energía que la inicial (entendiendo que un menor nivel de energía se corresponde con una solución más próxima al mínimo global). funcion SIMULATED_ANNEALING(problema, ESQUEMA) devuelve un estado solución entradas: problema| un problema ESQUEMA| una aplicación desde el tiempo a «temperatura» variables locales: siguiente| un nodo actual| un nodo (que será finalmente interpretado como solución) T| una «temperatura» que controla la probabilidad de un paso hacia abajo actual ← hacer_nodo(estado_inicial(problema)) para T ← 1 hasta ∞ hacer T ← ESQUEMA(T ) si T == 0 entonces devolver actual siguiente ← un sucesor seleccionado aleatoriamente de actual ∆E ← valor(siguiente) – valor(actual) si ∆E > 0 entonces actual ← siguiente en caso contrario actual ← siguiente sólo con probabilidad j ∆k/m 72 ALGORITMOS GENÉTICOS Este algoritmo trata de reproducir los mecanismos de evolución de las especies descubierto por Darwin en 1859. La idea central es simple: las variaciones (conocidas como mutaciones, y que vendrán a ser alteraciones aleatorias de una solución), ocurren en la reproducción (mezcla de soluciones), y serán conservadas en generaciones sucesivas aproximadamente en la proporción de su efecto sobre la idoneidad reproductiva (calidad de la solución). función ALGORITMO_GENÉTICO(población, IDONEIDAD) devuelve un individuo entradas: población| un conjunto de individuos IDONEIDAD| una función que mide la capacidad del individuo repetir: nueva_población ← conjunto vacío para i ←1 hasta tamaño(población) hacer x ← seleccion_aleatoria (población, IDONEIDAD) y ← seleccion_aleatoria (población, IDONEIDAD) hijo ← reproducir(x, y) si (probabilidad aleatoria pequeña) entonces hijo ← mutar(hijo) añadir hijo a nueva_población población ← nueva_población hasta que algún individuo es bastante adecuado, o ha pasado bastante tiempo devolver el mejor individuo en la población, de acuerdo con la IDONEIDAD función REPRODUCIR(x, y) devuelve un individuo entradas: x, y| padres individuales n ← longitud(x) c ← número aleatorio de 1 a N devolver añadir(subcadena(x, 1, c), subcadena (y, c+1,N)) 73 ANEXO: ESTRUCTURA DE DESARROLLO SOFTWARE Todo el código software se ha desarrollado en lenguaje de programación C. En concreto se ha hecho compatible con la versión ANSI C que se detalla en el clásico libro «EL LENGUAJE DE PROGRAMACIÓN C» de B.Kernighan y D.Ritchie. Su compilación y ejecución se ha llevado a cabo sobre equipos Xserve de Apple de 64 bits, con plataforma Xcode y compilador g++. La distribución de ficheros corresponde a la típica distribución de desarrollo de programas sobre UNIX/Linux. DIRECTORIO inc appSettings.h constantes y parámetros de configuración del software (no relacionados con errores). ERROR.H soporte para emular el mecanismo de excepciones al estilo C++ sobre C. TRACE.H soporte que permite el trazado de programa sobre un fichero de seguimiento. TYPES.H declaración de todos los tipos e interfaces de datos no primitivos y propios del software. DIRECTORIO src TRACE.C implementación de las interfaces de TRACE.H TYPES.C implementación de las interfaces de TYPES.H TOOLS.C utilidades y funcionalidades de uso diverso y transversal. main.c soporte de la interfaz usuario/software, y distribución del flujo de procesamiento. loaders.c soporte para la lectura y carga de ficheros de entrada. savers.c soporte para la creación de ficheros de salida. predata.c implementación del comando PREDATA. metdim.c implementación del comando METDIM. sort.c implementación del comando SORT. label.c implementación del comando LABEL. prob.c implementación del comando PROB. intramd.c implementación del comando INTRAMD. intermd.c implementación del comando INTERMD. setdata.c implementación del comando SETDATA. dk.c implementación del comando DK. dke.c implementación del comando DKE. rsort.c implementación del comando RSORT. kdist.c implementación del comando KDIST. cdet implementación del comando CDET. cprank implementación del comando CPRANK. randset.c implementación del comando RANDSET. La interfaz de usuario/software se lleva a cabo mediante la clásica llamada a programa acompañada de su serie de modificadores correspondientes. Dentro de este contexto siempre se producirá la misma situación: » MDPRO –ID comando –mod_1 valor_1 –mod_2 valor_2 … –mod_N valor_N Donde resta claro que el conjunto {mod_1, mod_2,… , mod_N} serán el conjunto de modificadores específicos al comando. El empleo de cualquier otro modificador no asociado carecerá de efectos prácticos. 80 0.0000 20.0000 40.0000 60.0000 80.0000 100.0000 120.0000 140.0000 160.0000 0 5 10 15 20 25 μDKE ρ(%) BA 200 400 800 1600 0.0000 5.0000 10.0000 15.0000 20.0000 25.0000 30.0000 35.0000 0 20 40 60 80 100 μDKE ρ(%) ER 200 400 800 1600 0.0000 0.2000 0.4000 0.6000 0.8000 1.0000 0 20 40 60 80 100 μDKE ρ(%) CL 200 400 800 1600 0.0000 1.0000 2.0000 3.0000 4.0000 5.0000 6.0000 7.0000 0 20 40 60 80 100 μDKE ρ(%) RR 200 400 800 1600 0.0000 20.0000 40.0000 60.0000 80.0000 100.0000 120.0000 0 20 40 60 80 100 μDKE ρ(%) WS 200 400 800 1600 81 0.0000 0.5000 1.0000 1.5000 2.0000 2.5000 0 5 10 15 20 25 MD ρ(%) BA 200 400 800 1600 0.0000 0.5000 1.0000 1.5000 2.0000 2.5000 3.0000 0 20 40 60 80 100 MD ρ(%) ER 200 400 800 1600 0.0000 2.0000 4.0000 6.0000 8.0000 10.0000 12.0000 14.0000 0 20 40 60 80 100 MD ρ(%) CL 200 400 800 1600 0.0000 0.5000 1.0000 1.5000 2.0000 2.5000 3.0000 0 20 40 60 80 100 MD ρ(%) RR 200 400 800 1600 0.0000 1.0000 2.0000 3.0000 4.0000 5.0000 6.0000 7.0000 0 20 40 60 80 100 MD ρ(%) WS 200 400 800 1600 82 ANEXO: DISTORSIÓN DE BÚQUEDA EN LA DIMENSIÓN MÉTRICA RELATIVA 83 0.0000 2.0000 4.0000 6.0000 8.0000 10.0000 12.0000 14.0000 16.0000 0 5 10 15 20 ρ(%) BA 200 400 800 1600 0.0000 1.0000 2.0000 3.0000 4.0000 5.0000 6.0000 0 20 40 60 80 100 ρ(%) ER 200 400 800 1600 0.0000 0.5000 1.0000 1.5000 2.0000 2.5000 3.0000 3.5000 0 20 40 60 80 100 ρ(%) RR 200 400 800 1600 0.0000 1.0000 2.0000 3.0000 4.0000 5.0000 6.0000 0 20 40 60 80 100 ρ(%) CL 200 400 800 1600 0.0000 2.0000 4.0000 6.0000 8.0000 10.0000 12.0000 0 20 40 60 80 100 ρ(%) WS 200 400 800 1600 84 ANEXO: EVOLUCIÓN DE LA DIMENSIÓN MÉTRICA RELATIVA 85 0.0000 5.0000 10.0000 15.0000 20.0000 25.0000 30.0000 0 5 10 15 20 25 %β(G) ρ(%) BA 200 400 800 1600 0.0000 2.0000 4.0000 6.0000 8.0000 10.0000 0 20 40 60 80 100 %β(G) ρ(%) ER 200 400 800 1600 0.0000 10.0000 20.0000 30.0000 40.0000 50.0000 60.0000 70.0000 80.0000 0 20 40 60 80 100 %β(G) ρ(%) CL 200 400 800 1600 0.0000 2.0000 4.0000 6.0000 8.0000 10.0000 12.0000 0 20 40 60 80 100 %β(G) ρ(%) RR 200 400 800 1600 0.0000 5.0000 10.0000 15.0000 20.0000 25.0000 30.0000 0 20 40 60 80 100 %β(G) ρ(%) WS 200 400 800 1600 86 ANEXO: CORRELACIÓN ENTRE CONJUNTOS Y CARACTERÍSTICAS 87 R² = 0.440 0.0000 0.0010 0.0020 0.0030 0.0040 0.0050 0.0060 0.0070 0.0080 0.0000 0.0050 0.0100 0.0150 0.0200 BA R² = 0.947 0.0000 0.0020 0.0040 0.0060 0.0080 0.0100 0.0120 0.0000 0.0020 0.0040 0.0060 0.0080 0.0100 0.0120 0.0140 ER R² = 0.999 0.0000 0.0020 0.0040 0.0060 0.0080 0.0100 0.0000 0.0020 0.0040 0.0060 0.0080 0.0100 RR R² = 0.797 -0.0050 0.0000 0.0050 0.0100 0.0150 0.0200 0.0250 0.0300 0.0000 0.0020 0.0040 0.0060 0.0080 0.0100 0.0120 WS 88 R² = 0.956 0.0000 0.1000 0.2000 0.3000 0.4000 0.5000 0.6000 0.7000 0.8000 0.9000 0.0000 0.2000 0.4000 0.6000 0.8000 BA R² = 0.999 0.0000 0.1000 0.2000 0.3000 0.4000 0.5000 0.6000 0.7000 0.8000 0.9000 0.0000 0.2000 0.4000 0.6000 0.8000 1.0000 ER R² = 1 0.0000 0.1000 0.2000 0.3000 0.4000 0.5000 0.6000 0.7000 0.8000 0.9000 0.0000 0.2000 0.4000 0.6000 0.8000 1.0000 RR R² = 0.997 0.0000 0.1000 0.2000 0.3000 0.4000 0.5000 0.6000 0.7000 0.8000 0.9000 0.0000 0.2000 0.4000 0.6000 0.8000 1.0000 WS 89 R² = 0.960 0.0000 100.0000 200.0000 300.0000 400.0000 500.0000 0.0000 200.0000 400.0000 600.0000 800.0000 BA R² = 0.999 0.0000 200.0000 400.0000 600.0000 800.0000 1000.0000 1200.0000 1400.0000 1600.0000 0.0000 500.0000 1000.0000 1500.0000 ER R² = 1 0.0000 200.0000 400.0000 600.0000 800.0000 1000.0000 1200.0000 1400.0000 1600.0000 0.0000 500.0000 1000.0000 1500.0000 WS 96 SCALE-FREE: Barabási-Albert 200 6 12 18 Mínimo 0 0 0 Máximo 0.320000 0.840000 0.820000 Media 0.054500 0.077300 0.073800 Rango 0.320000 0.840000 0.820000 CVAR 1.178854 2.044095 2.059334 400 6 12 18 Mínimo 0 0 0.020000 Máximo 0.600000 0.800000 1 Media 0.037150 0.052450 0.223000 Rango 0.600000 0.800000 0.980000 CVAR 1.862765 2.351669 0.828966 800 6 12 18 Mínimo 0 0 0 Máximo 0.860000 0.780000 0.960000 Media 0.033550 0.052150 0.046450 Rango 0.860000 0.780000 0.960000 CVAR 2.634340 1.495486 1.970466 1600 6 12 18 Mínimo 0 0 0 Máximo 0.540000 0.460000 0.160000 Media 0.032662 0.017600 0.013812 Rango 0.540000 0.460000 0.160000 CVAR 1.758873 2.477781 1.773334 97 ALEATORIO BINOMIAL: Erdõs-Rényi 200 4 14 24 34 44 54 64 74 84 Mínimo 0 0 0 0 0 0 0 0 0 Máximo 0.320000 0.400000 0.420000 0.220000 0.200000 0.160000 0.180000 0.320000 0.460000 Media 0.047900 0.094900 0.074400 0.060000 0.055000 0.054900 0.059400 0.069900 0.095900 Rango 0.320000 0.400000 0.420000 0.220000 0.200000 0.160000 0.180000 0.320000 0.460000 CVAR 0.961148 0.680295 0.804729 0.734847 0.656311 0.585148 0.648452 0.791893 0.824315 400 4 14 24 34 44 54 64 74 84 Mínimo 0 0 0 0 0 0 0 0 0 Máximo 0.140000 0.360000 0.200000 0.140000 0.120000 0.140000 0.120000 0.240000 0.260000 Media 0.030000 0.064700 0.044400 0.035950 0.032500 0.032450 0.035000 0.042550 0.059150 Rango 0.140000 0.360000 0.200000 0.140000 0.120000 0.140000 0.120000 0.240000 0.260000 CVAR 0.920145 0.783833 0.848905 0.803599 0.775818 0.823443 0.770370 0.825744 0.799123 800 4 14 24 34 44 54 64 74 84 Mínimo 0 0 0 0 0 0 0 0 0 Máximo 0.160000 0.160000 0.120000 0.140000 0.100000 0.100000 0.120000 0.160000 0.180000 Media 0.019950 0.039775 0.026425 0.021175 0.018750 0.018750 0.020475 0.024950 0.035675 Rango 0.160000 0.160000 0.120000 0.140000 0.100000 0.100000 0.120000 0.160000 0.180000 CVAR 1.360787 0.760273 0.936351 1.031550 1.022328 1.103932 1.027122 0.930945 0.849660 1600 4 14 24 34 44 54 64 74 84 Mínimo 0 0 0 0 0 0 0 0 0 Máximo 0.260000 0.160000 0.120000 0.100000 0.100000 0.080000 0.080000 0.100000 0.140000 Media 0.025262 0.023387 0.015237 0.011950 0.010650 0.010625 0.011800 0.014375 0.021000 Rango 0.260000 0.160000 0.120000 0.100000 0.100000 0.080000 0.080000 0.100000 0.140000 CVAR 1.148326 0.989709 1.203096 1.302318 1.380242 1.356109 1.274741 1.216615 1.044367 98 SMALL-WORLD: Watts-Strogatz 200 4 14 24 34 44 54 64 74 84 Mínimo 0 0 0 0 0.020000 0.040000 0.040000 0.060000 0.020000 Máximo 0.520000 0.560000 0.500000 0.540000 0.520000 0.680000 0.680000 0.800000 0.620000 Media 0.066100 0.169400 0.178100 0.164300 0.200400 0.276000 0.257200 0.255900 0.243500 Rango 0.520000 0.560000 0.500000 0.540000 0.500000 0.640000 0.640000 0.740000 0.600000 CVAR 1.387614 0.636221 0.569798 0.641346 0.487794 0.410685 0.496514 0.491716 0.491472 400 4 14 24 34 44 54 64 74 84 Mínimo 0 0.020000 0.020000 0.020000 0.040000 0.060000 0.040000 0.020000 0 Máximo 0.480000 0.480000 0.440000 0.440000 0.560000 0.700000 0.500000 0.600000 0.580000 Media 0.118550 0.460000 0.154650 0.149100 0.212500 0.240300 0.214600 0.580000 0.195100 Rango 0.480000 0.199200 0.420000 0.420000 0.520000 0.640000 0.460000 0.198800 0.580000 CVAR 0.680747 0.410032 0.518443 0.537691 0.381024 0.366018 0.406685 0.416095 0.436065 800 4 14 24 34 44 54 64 74 84 Mínimo 0.020000 0.020000 0 0 0.060000 0 0.020000 0 0 Máximo 0.480000 0.380000 0.360000 0.360000 0.440000 0.440000 0.460000 0.440000 0.360000 Media 0.200200 0.158275 0.091275 0.158625 0.209000 0.190250 0.169975 0.148200 0.140275 Rango 0.460000 0.360000 0.360000 0.340000 0.380000 0.440000 0.440000 0.440000 0.360000 CVAR 0.371749 0.409243 0.613763 0.375964 0.315245 0.340519 0.357136 0.416103 0.400958 1600 4 14 24 34 44 54 64 74 84 Mínimo 0.060000 0 0 0 0.020000 0 0 0 0 Máximo 0.480000 0.300000 0.260000 0.460000 0.340000 0.320000 0.300000 0.260000 0.280000 Media 0.244187 0.064400 0.088587 0.173775 0.158962 0.132425 0.117000 0.102763 0.094300 Rango 0.420000 0.300000 0.260000 0.460000 0.320000 0.320000 0.300000 0.260000 0.280000 CVAR 0.274966 0.654875 0.497133 0.316043 0.344169 0.371261 0.402118 0.443716 0.470736 99 ANILLO K-REGULAR 200 4 14 24 34 44 54 64 74 84 Mínimo 0 0 0.040000 0.100000 0.120000 0.220000 0.240000 0.240000 0.240000 Máximo 0.100000 0.220000 0.280000 0.480000 0.440000 0.600000 0.580000 0.640000 0.600000 Media 0.030000 0.084100 0.146100 0.264700 0.262300 0.424500 0.420500 0.421000 0.422200 Rango 0.100000 0.220000 0.240000 0.380000 0.320000 0.380000 0.340000 0.400000 0.360000 CVAR 0.800000 0.490434 0.340088 0.245762 0.238839 0.175809 0.160550 0.175692 0.160698 400 4 14 24 34 44 54 64 74 84 Mínimo 0 0 0.020000 0.180000 0.160000 0.280000 0.320000 0.320000 0.260000 Máximo 0.120000 0.240000 0.360000 0.520000 0.540000 0.760000 0.700000 0.700000 0.720000 Media 0.029200 0.098250 0.181000 0.339200 0.336200 0.504000 0.500750 0.503300 0.504850 Rango 0.120000 0.240000 0.340000 0.340000 0.380000 0.480000 0.380000 0.380000 0.504850 CVAR 0.839817 0.421863 0.287240 0.192811 0.336200 0.150480 0.139110 0.141154 0.142912 800 4 14 24 34 44 54 64 74 84 Mínimo 0 0 0.060000 0.220000 0.180000 0.300000 0.360000 0.340000 0.380000 Máximo 0.160000 0.280000 0.440000 0.640000 0.660000 0.780000 0.780000 0.820000 0.800000 Media 0.031175 0.132125 0.244700 0.416375 0.418850 0.583875 0.586425 0.581850 0.420000 Rango 0.160000 0.280000 0.380000 0.420000 0.480000 0.480000 0.420000 0.581850 0.582150 CVAR 0.790696 0.374204 0.251947 0.165670 0.166007 0.121281 0.115470 0.123655 0.122642 1600 4 14 24 34 44 54 64 74 84 Mínimo 0 0.040000 0.120000 0.280000 0.240000 0.420000 0.340000 0.420000 0.400000 Máximo 0.160000 0.420000 0.560000 0.740000 0.760000 0.860000 0.900000 0.880000 0.860000 Media 0.036337 0.181137 0.312300 0.488337 0.520000 0.644887 0.646437 0.646162 0.460000 Rango 0.160000 0.380000 0.440000 0.460000 0.493487 0.440000 0.560000 0.460000 0.646662 CVAR 0.719912 0.314313 0.212115 0.144940 0.145263 0.104774 0.106821 0.102980 0.108296 100 ALEATORIO K-REGULAR: Kim-Vu 200 4 14 24 34 44 54 64 74 84 Mínimo 0 0 0 0 0 0 0 0 0 Máximo 0.180000 0.260000 0.160000 0.180000 0.160000 0.140000 0.160000 0.200000 0.240000 Media 0.046800 0.099600 0.074900 0.060100 0.055000 0.054900 0.060000 0.071800 0.100400 Rango 0.180000 0.260000 0.160000 0.180000 0.160000 0.140000 0.160000 0.200000 0.240000 CVAR 0.754174 0.519363 0.469381 0.572048 0.620051 0.585148 0.512076 0.504624 0.447636 400 4 14 24 34 44 54 64 74 84 Mínimo 0 0 0 0 0 0 0 0 0 Máximo 0.120000 0.180000 0.200000 0.120000 0.120000 0.140000 0.160000 0.160000 0.160000 Media 0.029700 0.066600 0.045250 0.036800 0.032500 0.032500 0.035150 0.042900 0.061600 Rango 0.120000 0.180000 0.200000 0.120000 0.120000 0.140000 0.160000 0.160000 0.160000 CVAR 0.796714 0.542298 0.716594 0.703253 0.819727 0.810435 0.792245 0.677031 0.534345 800 4 14 24 34 44 54 64 74 84 Mínimo 0 0 0 0 0 0 0 0 0 Máximo 0.120000 0.160000 0.100000 0.120000 0.100000 0.100000 0.120000 0.100000 0.160000 Media 0.021200 0.040325 0.026475 0.021250 0.018750 0.018750 0.020625 0.025325 0.036325 Rango 0.120000 0.160000 0.100000 0.120000 0.100000 0.100000 0.120000 0.100000 0.160000 CVAR 0.983307 0.715038 0.876571 0.928667 1.016749 0.996973 0.940293 0.843338 0.741756 1600 4 14 24 34 44 54 64 74 84 Mínimo 0 0 0 0 0 0 0 0 0 Máximo 0.120000 0.140000 0.100000 0.100000 0.080000 0.080000 0.080000 0.100000 0.120000 Media 0.026500 0.023487 0.015337 0.012037 0.010625 0.010625 0.011787 0.014412 0.021175 Rango 0.120000 0.140000 0.100000 0.100000 0.080000 0.080000 0.080000 0.100000 0.120000 CVAR 0.880346 0.879361 1.133070 1.289246 1.351201 1.385191 1.274808 1.163153 0.969699 101 ANEXO: CORRELACIÓN ENTRE LA PROBABILIDAD Y LAS CARACTERÍSTICAS 102 SCALE-FREE: Barabási-Albert 200 6 12 18 Betweenness 0,022992 0,159871 0,222771 Dist. Media 0,243143 0,094753 0,510837 Grado 0,033953 0,300645 0,554707 Degree-K Error 0,002011 0,426203 0,395834 Clustering 0,063695 0,209455 0,150809 400 6 12 18 Betweenness 0,014728 0,276467 0,012151 Dist. Media 0,233459 0,367429 0,121566 Grado 0,000528 0,509383 0,121566 Degree-K Error 0,494822 0,576518 0,307527 Clustering 0,150684 0,107895 0,424846 800 6 12 18 Betweenness 0,389631 0,109428 0,141775 Dist. Media 0,096385 0,150593 0,210954 Grado 0,451233 0,207275 0,219372 Degree-K Error 0,708461 0,278726 0,244018 Clustering 0,142235 0,165524 0,034108 1600 6 12 18 Betweenness 0,773883 0,754289 0,471976 Dist. Media 0,536951 0,626391 0,492192 Grado 0,616119 0,626391 0,492192 Degree-K Error 0,743525 0,630055 0,296081 Clustering 0,006598 0,001900 0,042835 103 ALEATORIO BINOMIAL: Erdõs-Rényi 200 4 14 24 34 44 54 64 74 84 Betweenness 0,112273 0,194740 0,565748 0,459395 0,105168 0,037655 0,154013 0,424101 0,445761 Dist. Media 0,000744 0,031428 0,495413 0,446345 0,103898 0,036590 0,157173 0,488405 0,549971 Grado 0,061556 0,136476 0,495412 0,446344 0,103898 0,036590 0,157173 0,488405 0,549971 Degree-K Error 0,119110 0,178624 0,079736 0,015596 0,000751 0,017550 0,000023 0,026670 0,080056 Clustering 0,000312 0,004598 0,034626 0,023296 0,016558 0,003616 0,000132 0,006748 0,030625 400 4 14 24 34 44 54 64 74 84 Betweenness 0,089142 0,525628 0,395124 0,243905 0,007714 0,032241 0,165610 0,235476 0,344212 Dist. Media 0,131937 0,457249 0,368777 0,243828 0,006497 0,030641 0,173532 0,253912 0,402524 Grado 0,115657 0,461647 0,368777 0,243827 0,006497 0,030641 0,173532 0,253912 0,402525 Degree-K Error 0,048811 0,064680 0,040194 0,006953 0,000093 0,000177 0,005095 0,013196 0,051957 Clustering 0,002362 0,012777 0,024547 0,004282 0,004305 0,003637 0,000423 0,000080 0,037791 800 4 14 24 34 44 54 64 74 84 Betweenness 0,301399 0,216908 0,148922 0,041521 0,007397 0,009055 0,056061 0,128191 0,198554 Dist. Media 0,404639 0,200305 0,143377 0,040444 0,008389 0,010107 0,057350 0,134847 0,213501 Grado 0,346872 0,200305 0,143376 0,040443 0,008389 0,010107 0,057349 0,134847 0,213502 Degree-K Error 0,110998 0,007443 0,009883 0,006303 0,001282 0,002944 0,000462 0,011204 0,028197 Clustering 0,000202 0,000312 0,000353 0 0,003180 0,002095 0,000009 0,002514 0,002514 1600 4 14 24 34 44 54 64 74 84 Betweenness 0,214571 0,085677 0,065661 0,016230 0,005432 0,006107 0,009887 0,033372 0,086905 Dist. Media 0,328583 0,081539 0,063631 0,016211 0,005339 0,006064 0,009435 0,034558 0,088695 Grado 0,247876 0,081539 0,063631 0,016211 0,005339 0,006064 0,009435 0,034558 0,088695 Degree-K Error 0,168162 0,001161 0,004518 0,000294 0,000149 0,000151 0,000355 0,000742 0,001716 Clustering 0,000301 0,003643 0,000472 0,000025 0,000428 0,000203 0,003444 0,000184 0,006205 104 SMALL-WORLD: Watts-Strogatz 200 4 14 24 34 44 54 64 74 84 Betweenness 0,061602 0,096588 0,009570 0,075132 0,001528 0,044146 0,037660 0,009869 0,000758 Dist. Media 0,064597 0,049523 0,029454 0,087243 0,027934 0,001715 0,003380 0,000181 0,005631 Grado 0,028766 0,028893 0,008200 0,010248 0,041141 0,001714 0,003380 0,000181 0,005631 Degree-K Error 0,007739 0,010944 0,021108 0,002796 0,002345 0,000402 0,008082 0,011947 0,000616 Clustering 0,047405 0,110177 0,053281 0,077281 0,000923 0,076954 0,153451 0,060514 0,005645 400 4 14 24 34 44 54 64 74 84 Betweenness 0,088435 0,004110 0,000770 0,016105 0,094667 0,109579 0,074134 0,029145 0,000488 Dist. Media 0,013593 0,003326 0,003424 0,031436 0,001037 0,000005 0,001543 0,000676 0,002356 Grado 0,036800 0,000345 0,002315 0,033695 0,004158 0,000005 0,001543 0,000676 0,002356 Degree-K Error 0,028614 0,032225 0,013006 0,029533 0,008057 0,002009 0,004512 0,000683 0,004584 Clustering 0,061865 0,000269 0,003686 0,012174 0,079932 0,171189 0,152091 0,157455 0,043448 800 4 14 24 34 44 54 64 74 84 Betweenness 0,059439 0,000108 0,012423 0,017478 0,039471 0,046418 0,019517 0,013289 0,000024 Dist. Media 0,035114 0,000924 0,009634 0,002462 0,002647 0,000041 0,002733 0,000486 0,004239 Grado 0,006177 0,001894 0,019590 0,018944 0,004616 0,000041 0,002733 0,000486 0,004239 Degree-K Error 0,000325 0,011835 0,000163 0,000297 0,000452 0,009915 0,000511 0,001826 0,001959 Clustering 0,061664 0,003574 0,019508 0,020534 0,026082 0,068869 0,073024 0,071480 0,031977 1600 4 14 24 34 44 54 64 74 84 Betweenness 0,003173 0,000022 0,000232 0,021886 0,023992 0,023984 0,024645 0,000871 0,004541 Dist. Media 0,001294 0,000209 0,003887 0,001288 0,000477 0,001598 0,000122 0,003151 0,000143 Grado 0,001267 0,000574 0,004731 0,000046 0,000504 0,001598 0,000122 0,003152 0,000143 Degree-K Error 0,000025 0,000086 0,005156 0,000336 0,000946 0,002251 0,000563 0,004733 0,000084 Clustering 0,003523 0,000586 0,001580 0,022258 0,019792 0,042767 0,056216 0,019981 0,027435 105 ALEATORIO K-REGULAR: Kim-Vu 200 4 14 24 34 44 54 64 74 84 Betweenness 0,032228 0,000612 0,000618 0,008783 0,001301 0,011710 0,001584 0,006764 0,030817 Clustering 0,063914 0,002836 0,002074 0,006740 0,000600 0,007745 0,000882 0,004787 0,034203 400 4 14 24 34 44 54 64 74 84 Betweenness 0,000001 0,001283 0,013147 0,000086 0,000995 0,001624 0,000064 0,000081 0,003608 Clustering 0,008855 0,002024 0,022788 0,000784 0,000667 0,000811 0,000222 0,000113 0,000987 800 4 14 24 34 44 54 64 74 84 Betweenness 0,000181 0,004364 0,000015 0,000097 0,000628 0,000019 0,000249 0,000251 0,000008 Clustering 0,000277 0,001157 0,000089 0,000076 0,000131 0,000178 0,000555 0,000510 0,000751 1600 4 14 24 34 44 54 64 74 84 Betweenness 0,000456 0,000649 0,000015 0,000892 0,000071 0,000416 0,000770 0,000938 0 Clustering 0,000017 0,000083 0,000007 0,000460 0,000624 0,000539 0,002384 0,000227 0,000051 112 SCALE-FREE: Barabási-Albert 200 6 12 18 Betweenness 0,325000 0,225000 0,200000 Dist. Media 0,330000 0,385000 0,375000 Grado 0,550000 0,465000 0,380000 Degree-K Error 0,325000 0,355000 0,385000 Clustering 0,330000 0,360000 0,380000 400 6 12 18 Betweenness 0,217500 0,285000 0,432500 Dist. Media 0,295000 0,337500 0,722500 Grado 0,417500 0,357000 0,785000 Degree-K Error 0,292500 0,325000 0,730000 Clustering 0,297500 0,317500 0,707500 800 6 12 18 Betweenness 0,162500 0,327500 0,257500 Dist. Media 0,328750 0,367500 0,297500 Grado 0,392500 0,403750 0,292500 Degree-K Error 0,318750 0,387500 0,308750 Clustering 0,318750 0,372500 0,285000 1600 6 12 18 Betweenness 0,288125 0,283125 0,282500 Dist. Media 0,266875 0,240000 0,268750 Grado 0,286875 0,246875 0,271250 Degree-K Error 0,265000 0,246875 0,268750 Clustering 0,263750 0,246875 0,266250 113 ALEATORIO BINOMIAL: Erdõs-Rényi 200 4 14 24 34 44 54 64 74 84 Betweenness 0,370000 0,410000 0,480000 0,315000 0,325000 0,150000 0,330000 0,315000 0,420000 Dist. Media 0,395000 0,665000 0,530000 0,400000 0,350000 0,430000 0,395000 0,665000 0,670000 Grado 0,410000 0,705000 0,695000 0,350000 0,360000 0,400000 0,410000 0,595000 0,685000 Degree-K Error 0,380000 0,650000 0,665000 0,400000 0,455000 0,515000 0,460000 0,550000 0,680000 Clustering 0,550000 0,600000 0,500000 0,280000 0,305000 0,390000 0,310000 0,535000 0,600000 400 4 14 24 34 44 54 64 74 84 Betweenness 0,335000 0,430000 0,355000 0,227500 0,210000 0,285000 0,142500 0,382500 0,385000 Dist. Media 0,272500 0,587500 0,390000 0,447500 0,372500 0,420000 0,357500 0,432500 0,535000 Grado 0,400000 0,575000 0,352500 0,450000 0,352500 0,440000 0,290000 0,442500 0,490000 Degree-K Error 0,262500 0,610000 0,392500 0,475000 0,352500 0,420000 0,322500 0,430000 0,505000 Clustering 0,272500 0,497500 0,302500 0,397500 0,305000 0,382500 0,260000 0,392500 0,440000 800 4 14 24 34 44 54 64 74 84 Betweenness 0,117500 0,357500 0,315000 0,136250 0,118750 0,190000 0,157500 0,357500 0,155000 Dist. Media 0,251250 0,365000 0,248750 0,272500 0,250000 0,353750 0,313750 0,200000 0,292500 Grado 0,352500 0,410000 0,273750 0,257500 0,248750 0,336250 0,308750 0,195000 0,325000 Degree-K Error 0,247500 0,408750 0,297500 0,303750 0,230000 0,341250 0,303750 0,205000 0,317500 Clustering 0,246250 0,343750 0,233750 0,253750 0,222500 0,307500 0,287500 0,185000 0,243750 1600 4 14 24 34 44 54 64 74 84 Betweenness 0,322500 0,374375 0,125000 0,158750 0,120000 0,146250 0,188125 0,183125 0,122500 Dist. Media 0,290000 0,267500 0,284375 0,203750 0,228125 0,237500 0,199375 0,311875 0,273750 Grado 0,315000 0,271250 0,258125 0,215000 0,236250 0,237500 0,201875 0,325625 0,272500 Degree-K Error 0,276250 0,251250 0,262500 0,206250 0,213125 0,222500 0,210625 0,329375 0,275625 Clustering 0,275625 0,233125 0,249375 0,197500 0,213750 0,213750 0,191250 0,310650 0,243750 114 SMALL-WORLD: Watts-Strogatz 200 4 14 24 34 44 54 64 74 84 Betweenness 0,320000 0,465000 0,435000 0,500000 0,520000 0,380000 0,365000 0,505000 0,450000 Dist. Media 0,405000 0,730000 0,785000 0,760000 0,610000 0,550000 0,400000 0,485000 0,515000 Grado 1 0,285000 0,325000 0,405000 0,485000 0,555000 0,625000 0,490000 0,455000 Degree-K Error 0,400000 0,695000 0,740000 0,760000 0,535000 0,145000 0,215000 0,195000 0,160000 Clustering 0,235000 0,680000 0,760000 0,735000 0,720000 0,680000 0,635000 0,750000 0,715000 400 4 14 24 34 44 54 64 74 84 Betweenness 0,560000 0,350000 0,450000 0,285000 0,535000 0,240000 0,457500 0,400000 0,490000 Dist. Media 0,710000 0,525000 0,740000 0,597500 0,570000 0,520000 0,400000 0,552500 0,415000 Grado 1 0,392500 0,470000 0,515000 0,342500 0,537500 0,382500 0,527500 0,430000 Degree-K Error 0,705000 0,530000 0,735000 0,562500 0,742500 0,220000 0,265000 0,170000 0,215000 Clustering 0,307500 0,520000 0,727500 0,522500 0,775000 0,475000 0,687500 0,507500 0,647500 800 4 14 24 34 44 54 64 74 84 Betweenness 0,225000 0,252500 0,325000 0,285000 0,372500 0,398750 0,343750 0,356250 0,226250 Dist. Media 0,437500 0,498750 0,443750 0,597500 0,578750 0,592500 0,561250 0,705000 0,632500 Grado 0,256250 0,570000 0,536250 0,488750 0,410000 0,660000 0,560000 0,610000 0,632500 Degree-K Error 0,426250 0,491250 0,433750 0,652500 0,601250 0,277500 0,372500 0,395000 0,423750 Clustering 0,546250 0,492500 0,426250 0,623750 0,562500 0,530000 0,443750 0,493750 0,482500 1600 4 14 24 34 44 54 64 74 84 Betweenness 0,446875 0,406875 0,110000 0,355000 0,287500 0,419375 0,402500 0,320000 0,181875 Dist. Media 0,620625 0,426875 0,463125 0,685625 0,594375 0,417500 0,466250 0,698750 0,523125 Grado 0,385000 0,276875 0,480000 0,604375 0,615000 0,388750 0,473750 0,696250 0,500000 Degree-K Error 0,610625 0,425000 0,441875 0,639375 0,417500 0,210000 0,339375 0,473750 0,652500 Clustering 0,641250 0,421875 0,438750 0,506250 0,444375 0,451250 0,310000 0,520625 0,330625 115 ALEATORIO K-REGULAR: Kim-Vu 200 4 14 24 34 44 54 64 74 84 Betweenness 0,225000 0,255000 0,260000 0,390000 0,330000 0,310000 0,315000 0,410000 0,345000 Clustering 0,260000 0,620000 0,370000 0,475000 0,315000 0,355000 0,320000 0,440000 0,515000 400 4 14 24 34 44 54 64 74 84 Betweenness 0,240000 0,217500 0,495000 0,272500 0,315000 0,342500 0,292500 0,202500 0,24500 Clustering 0,445000 0,450000 0,430000 0,370000 0,405000 0,415000 0,285000 0,365000 0,250000 800 4 14 24 34 44 54 64 74 84 Betweenness 0,167500 0,548750 0,282500 0,337500 0,371250 0,115000 0,145000 0,272500 0,163750 Clustering 0,445000 0,388750 0,247500 0,346250 0,231250 0,227500 0,328750 0,195000 0,335000 1600 4 14 24 34 44 54 64 74 84 Betweenness 0,389375 0,336250 0,790625 0,228125 0,582500 0,267500 0,550625 0,485000 0,355000 Clustering 0,273750 0,148125 0,261250 0,206875 0,216875 0,131875 0,193125 0,226875 0,338750 116 ANEXO: RELACIÓN ENTRE PERCENTILES (+80) PARA LAS PROBABILIDADES Y LAS CARACTERÍSTICAS 117 SCALE-FREE: Barabási-Albert 200 6 12 18 Betweenness 0,743590 0,794872 0,923077 Dist. Media 0,743590 0,861111 0,923077 Grado 0,769231 0,888889 0,897436 Degree-K Error 0,763158 0,794872 0,947368 Clustering 0,743590 0,794872 0,923077 400 6 12 18 Betweenness 0,797468 0,835443 0,974684 Dist. Media 0,807692 0,916667 0,987013 Grado 0,842105 0,881579 0,974684 Degree-K Error 0,797468 0,835443 0,974684 Clustering 0,797468 0,835443 0,974684 800 6 12 18 Betweenness 0,689873 0,961783 0,691824 Dist. Media 0,700637 0,985915 0,720779 Grado 0,716129 0,962025 0,691824 Degree-K Error 0,685535 0,967949 0,691824 Clustering 0,685535 0,949686 0,691824 1600 6 12 18 Betweenness 0,686520 0,738170 0,833856 Dist. Media 0,701258 0,719355 0,845912 Grado 0,701923 0,735849 0,830721 Degree-K Error 0,688679 0,752412 0,863192 Clustering 0,683386 0,733542 0,830721 118 ALEATORIO BINOMIAL: Erdõs-Rényi 200 4 14 24 34 44 54 64 74 84 Betweenness 0,769231 0,763158 0,710526 0,606061 0,641026 0,647059 0,307659 0,794118 0,641026 Dist. Media 0,769231 0,882353 0,736842 0,538462 0,684211 0,702703 0,405405 0,787879 0,656250 Grado 0,964286 0,906250 0,965517 0,555556 0,736842 0,564103 0,433333 0,888889 0,923077 Degree-K Error 0,769231 0,763158 0,710526 0,606061 0,641026 0,647059 0,307692 0,794118 0,641026 Clustering 0,967742 0,743590 0,717949 0,461538 0,666667 0,564103 0,307692 0,743590 0,589744 400 4 14 24 34 44 54 64 74 84 Betweenness 0,493671 0,721519 0,384615 0,402597 0,474359 0,430380 0,253165 0,973333 0,649351 Dist. Media 0,493671 0,800000 0,506667 0,506849 0,544118 0,405063 0,342466 0,960526 0,724638 Grado 0,507042 0,782051 0,471429 0,480519 0,461538 0,459459 0,250000 0,986842 0,675676 Degree-K Error 0,493671 0,746835 0,421053 0,459459 0,480519 0,453333 0,324324 0,972973 0,683544 Clustering 0,500000 0,734177 0,379747 0,392405 0,468354 0,430380 0,240506 0,924051 0,683544 800 4 14 24 34 44 54 64 74 84 Betweenness 0,367089 0,691824 0,658228 0,169811 0,346154 0,405063 0,445863 0,465753 0,544118 Dist. Media 0,373418 0,720779 0,714286 0,230769 0,367347 0,407643 0,445860 0,.424837 0,396226 Grado 0,449367 0,875000 0,706667 0,189189 0,375000 0,435374 0,460526 0,431507 0,457143 Degree-K Error 0,367089 0,800000 0,709677 0,194969 0,341772 0,423841 0,451613 0,409091 0,388158 Clustering 0,377358 0,696203 0,654088 0,163522 0,339623 0,402516 0,440252 0,389937 0,358491 1600 4 14 24 34 44 54 64 74 84 Betweenness 0,624606 0,344937 0,678233 0,242902 0,515254 0,474576 0,289855 0,767717 0,643564 Dist. Media 0,641509 0,388715 0,686520 0,244373 0,504886 0,460265 0,207792 0,586093 0,209836 Grado 0,707143 0,428105 0,707006 0,297945 0,509934 0,478548 0,227723 0,594059 0,193333 Degree-K Error 0,623824 0,377483 0,682848 0,238245 0,483974 0,491803 0,192429 0,603834 0,186275 Clustering 0,620690 0,335423 0,661442 0,231975 0,485893 0,470219 0,181818 0,551724 0,174051 119 SMALL-WORLD: Watts-Strogatz 200 4 14 24 34 44 54 64 74 84 Betweenness 0,794872 0,871795 0,794872 0,897436 0,820513 0,794872 0,846154 0,972222 0,942857 Dist. Media 0,794872 1 0,842105 0,828571 0,916667 1 1 1 0,250000 Grado 1 0,400000 0,628571 1 1 1 0,250000 1 1 Degree-K Error 0,794872 0,871795 0,794872 0,897436 0,965517 0,708333 0,657143 0,628571 0,583333 Clustering 1 0,720000 0,828571 0,897436 0,918919 0,794872 0,842105 0,948718 0,894737 400 4 14 24 34 44 54 64 74 84 Betweenness 0,873418 0,924051 0,797468 0,658228 0,949367 0,881579 0,857143 0,896104 0,983607 Dist. Media 0,873418 1 0,833333 0,743243 1 0,705882 0,631579 0,802817 0,782051 Grado 1 0,525641 1 1 0,549020 0,770492 0,721311 0,758065 0,844156 Degree-K Error 0,873418 0,924051 0,797468 0,692308 1 0,967742 1 0,530612 0,758621 Clustering 1 0,968750 0,835443 0,658228 0,962025 0,886076 0,835443 0,936709 0,746835 800 4 14 24 34 44 54 64 74 84 Betweenness 0,773585 0,691824 0,547170 0,798742 0,757962 0,732484 0,764706 0,915888 0,693182 Dist. Media 0,783439 0,701299 0,592357 0,829114 0,896000 0,721519 0,693878 0,834783 0,883721 Grado 0,350515 1 0,942308 0,951049 0,909091 0,786517 0,728155 0,805085 0,868613 Degree-K Error 0,773585 0,691824 0,564935 0,810127 0,856000 0,814286 0,569767 0,777778 0,735099 Clustering 0,657658 0,705128 0,547170 0,798742 0,754717 0,723270 0,723270 0,742138 0,738854 1600 4 14 24 34 44 54 64 74 84 Betweenness 0,658307 0,542320 0,795597 0,731861 0,672956 0,571930 0,736059 0,670968 0,432039 Dist. Media 0,663522 0,547170 0,810726 0,882784 0,850746 0,611650 0,906250 0,935897 0,513889 Grado 1 0,841880 0,966216 0,780822 0,821293 0,641026 0,869159 0,955947 0,610687 Degree-K Error 0,658307 0,547170 0,796238 0,900000 0,775801 0,965174 0,778210 0,777385 0,674757 Clustering 0,662461 0,542320 0,793103 0,727273 0,658307 0,463950 0,517241 0,677116 0,307210 120 ALEATORIO K-REGULAR: Kim-Vu 200 4 14 24 34 44 54 64 74 84 Betweenness 0,307692 0,631579 0,769231 0,868421 0,605263 0,717949 0,685714 0,806452 0,720000 Clustering 0,657143 0,900000 0,878788 0,846154 0,567568 0,666667 0,675676 0,611111 0,615385 400 4 14 24 34 44 54 64 74 84 Betweenness 0,759494 0,367089 0,985294 0,333333 0,469697 0,415584 0,925000 0,812500 0,024390 Clustering 0,794118 0,405063 0,986486 0,233766 0,513158 0,415584 0,341772 0,649351 0,430380 800 4 14 24 34 44 54 64 74 84 Betweenness 0,436709 0,688742 0,681818 0,438849 0,280992 0,075188 1 1 1 Clustering 0,414634 0,535484 0,596154 0,439490 0,337580 0,301282 0,374194 0,305732 0,281046 1600 4 14 24 34 44 54 64 74 84 Betweenness 0,615658 0,709251 0,398649 0,766304 1 1 1 0,790076 1 Clustering 0,602076 0,154839 0,616352 0,242038 0,481013 0,104430 0,196203 0,514196 0,455975 121 ANEXO: RELACIÓN ENTRE PERCENTILES (-20) PARA LAS PROBABILIDADES Y LAS CARACTERÍSTICAS 128 129 130