Anteproyecto Doctoral

[pic 1][pic 2]

Posgrado en Ciencias y Tecnologías de la Información

Propuesta de Investigación Doctoral

Estudio de la dinámica de las redes complejas y su aplicación en la

construcción de redes P2P sin estructura regular

Presenta

M. en I. Alejandro Domingo Velazquez Cruz

Profesor Responsable

Dr. Ricardo Marcelín Jiménez

Índice

1. Introducción        1

2. Antecedentes        1

Origen de los sistemas complejos        1

Redes complejas        2

Internet como una red compleja        2

Navegabilidad de una red compleja        3

Propiedades de las redes complejas        3

Tolerancia a fallas y errores de las redes complejas        4

Redes P2P        4

Tipos de redes P2P        5

Centralizadas con estructura regular        5

Descentralizadas y con estructura regular        5

Descentralizadas sin estructura regular        5

Relación de las redes complejas con las redes P2P        5

Retos actuales de las redes P2P        6

3. Hipótesis        6

4. Objetivos        6

Objetivo general        6

Objetivos específicos        6

5. Metodología        6

6. Experimento propuesto        7

7. Resultados esperados        9

8. Avances hasta el momento        10

9. Calendario        12

10. Referencias        13

Índice de tablas

Tabla 8.1. Simuladores de redes P2P.        10

Tabla 9.1. Cronograma de actividades.        12

Índice de ilustraciones

Ilustración 6.1. Cuadrilla bidimensional con atajo aleatorio superpuesto.        8

1. Introducción

Las redes complejas describen estructuras que son el soporte de propiedades funcionales de las que puede sacarse provecho. Es interesante reconocer que su estructura es un fenómeno emergente que surge de la dinámica de sistemas auto-­‐organizados. Cada entidad decide por cuenta propia, y de acuerdo con sus “intereses”, establecer vínculos con los pares que mejor le convienen.

Este comportamiento aplica muy bien sobre las redes P2P, las cuales evitan el uso de nodos concentradores y se caracterizan por ser auto-­‐organizadas, con una comunicación simétrica y un control descentralizado [1]. En este trabajo buscamos estudiar la dinámica estructural de las redes complejas para proponer mecanismos que puedan aplicarse en la construcción de redes P2P.

1. Antecedentes

Las redes complejas son una especialización de los sistemas complejos, las investigaciones relacionadas con los sistemas complejos buscan explicar los mecanismos que dan origen a un determinado comportamiento complejo, su comprensión se considera esencial para algunas ramas de la ciencia, como la inteligencia artificial [2].

Origen de los sistemas complejos

Imaginemos un sencillo experimento en el que, por cada habitante de un país, dibujamos un punto etiquetado con su nombre. Luego, trazamos una línea o arista entre cada pareja de puntos si las personas que representan se conocen. Decimos que dos puntos o vértices están a una distancia 1, si tienen una arista que los conecta directamente. Decimos que están a una distancia 2, si el camino más corto que los une tiene dos aristas. Podemos generalizar esta medida y decir que están a una distancia d, si el camino más corto que los une tiene d aristas.

En los años 60, el psicólogo social Stanley Milgram [3] formó un grupo de voluntarios a quienes les entregó un paquete etiquetado con el nombre y la dirección de otra persona. A cada uno de los que participaron en el experimento se le pidió que usara solamente sus vínculos con conocidos y amistades para hacer llegar el paquete hasta su destinatario final. Milgram descubrió que, para los Estados Unidos, el paquete cambiaba de manos, en promedio, 6 veces. Sorprendentemente, en un país que para la época ya contaba con más de 100 millones de habitantes, la distancia entre dos personas cualesquiera era, en promedio, de tan sólo 6 aristas.

Durante muchos años, los investigadores se preguntaron cómo era posible que en una gráfica o grafo como la que describe el experimento de Milgram, la distancia promedio entre dos vértices fuera de apenas 6 saltos. Situación a la que denominaron el fenómeno de los mundos pequeños [4].

A finales del siglo pasado, diferentes equipos de investigadores reconocieron este fenómeno en varios contextos, tales como las redes sociales, las interacciones entre especies en un ecosistema, la interacción entre las proteínas del metabolismo celular, las relaciones económicas entre compañías, la estructura porosa de algunos materiales, y muchas otras. En todos estos casos, existe la posibilidad de modelar las interacciones de los componentes de un sistema por medio de un grafo, al que llamaremos red compleja, que puede comprender un número masivo de nodos y en el que, sin embargo, la distancia entre cualquier pareja de nodos es relativamente pequeña.

[pic 3]

1

Los primeros modelos introducidos para explicar la formación de las redes complejas reconocen que estas estructuras se encuentran a medio camino entre la regularidad y el “desorden”. Esto es, se pueden entender como el resultado de un proceso que introduce alguna función de probabilidad para caracterizar la distribución de los grados o la forma en que cada nodo tiene “cableadas” sus conexiones.

Watts y Strogatz [5] propusieron un primer modelo (WS) en el que, partiendo de una grafo regular, cada nodo recablea algunos de sus enlaces obedeciendo a una función de probabilidad. De esta manera, la red construye atajos entre sus nodos que reducen sensiblemente el diámetro promedio de la misma, al tiempo que cada nodo mantiene una cantidad importante de vínculos o aristas locales. De manera casi simultánea, Barabási y Albert [6] propusieron un modelo alternativo (BA) en el que describen la construcción de una red como un proceso de agregación en el que nuevos nodos se incorporan a un grafo y deciden establecer sus aristas con aquellos nodos que los precedieron y que muestran el mayor número de conexiones. En este modelo, se explica el valor promedio del diámetro como resultado de la presencia de nodos densamente conectados que tienden puentes hacia diversas regiones de la gráfica. Cabe aclarar que el uso del azar para generar grafos, data del trabajo pionero de Erdös y Renyi [7].

Los sistemas complejos se encuentran presentes en múltitud de áreas, incluyendo por ejemplo el cerebro, el sistema inmune, las colonias de hormigas e incluso en Internet. A pesar de que no hay una única definición de lo que es un sistema complejo, se puede definir como: “una gran red de componentes relativamente simples1 sin un control central, en la cuál se manifiesta un comportamiento emergente complejo2” [2].

Redes complejas

En busca de comprender los sistemas complejos se han explorado diversas maneras de describirlos, una de ellas es como una red donde los elementos locales son los nodos de la red, las aristas la relación entre ellos y el sistema complejo modelado se ve plasmado en el grafo resultante.

...