Estudio de los Efectos de la Cooperación en la Evolución Estructural de Redes Complejas Público Deposited
Las redes complejas, emergen naturalmente en muchos sistemas de diversas áreas del conocimiento, en particular, en el área de Tecnologías de la Información (TI), las podemos encontrar al describir la topología subyacente de la Internet, la World Wide Web (WWW), redes sociales, redes par a par (P2P, por sus siglas en inglés), etc. En las últimas décadas, el estudio de las redes complejas se ha convertido en una importante área de investigación, debido a que, gracias a ellas, se pueden modelar las interacciones entre los componentes de los sistemas que representan. Además, como toda red, tienen ciertas propiedades estructurales, tales como su longitud de trayectoria promedio, diámetro, coeficiente de agrupamiento promedio, modularidad o su distribución de grados, las cuales, determinan algunas de sus propiedades funcionales, tales como su robustez ante fallas aleatorias y ataques dirigidos, velocidad de transmisión de datos, etc. Esta investigación, propone experimentos basados en conexión y reconexión de aristas, mediante los cuales, un conjunto de redes con topología de malla o anillo, evoluciona hasta obtener características encontradas en las redes complejas. De estos experimentos, emergieron redes con un alto grado de robustez ante fallas aleatorias y ataques secuenciales dirigidos y que, además, en comparación con sus medidas iniciales, cuentan con diámetros y longitudes de trayectoria promedio considerablemente reducidos; un alto coeficiente de agrupamiento, y muestran estructuras de comunidades al contar con una modularidad alta El desarrollo de esta investigación, se encuentra dividido en dos etapas: Etapa 1 “Formación de Redes Complejas”: En esta investigación, se propone modelar a una red compleja como un sistema distribuido, donde sus vértices, son entidades que procesan información, y sus aristas, son los canales de comunicación que permiten a los vértices interactuar entre sí. Tomando como base la idea de que los sistemas distribuidos pueden ser simulados en computadora, se escribió un simulador de eventos discretos en el lenguaje de programación “python”, bajo el paradigma de la programación orientada a objetos, el cual, sigue el modelo de programación distribuida por paso de mensajes. Sobre el simulador, se ejecutaron una serie de experimentos, donde, partiendo de una red inicial con topología de malla o de anillo, cada uno de sus vértices aplica un conjunto de sencillas reglas locales de reconexión de aristas, que le permitirán encontrar atajos que lo conecten a regiones lejanas a su entorno local inicial, modificando así, la topología subyacente de la red. Lo anterior, permitió hacer un estudio riguroso sobre los efectos que tiene la cooperación en la evolución estructural de las redes iniciales, que al ser sometidas a diversos procesos de reconexión de aristas, experimentan cambios hasta el punto en el que sus propiedades estructurales convergen a propiedades comúnmente encontradas en las redes complejas. Etapa 2 “Degradación de Redes Complejas”: En esta etapa, se midió la robustez (capacidad de una red de seguir operando bajo circunstancias adversas) de las redes obtenidas en la etapa 1, ante dos diferentes procesos de degradación: fallas aleatorias, bajo la selección de vértices con base en una función de distribución de probabilidad uniforme, y ataques secuenciales dirigidos, bajo la selección de vértices con base en su número de aristas incidentes, en orden descendente. Lo anterior, se llevó a cabo mediante el uso de una métrica denominada “promedio de la fiabilidad media entre dos terminales” (µ-A2TR, por sus siglas en inglés), la cual, entrega el umbral de robustez ante ambos procesos de cada una de las redes. Los resultados de esta segunda etapa, muestran que la robustez de las redes emergentes en la etapa 1, varía conside-rablemente de acuerdo a las configuraciones de diversos parámetros utilizados en los experimentos, tales como el algortimo de encaminamiento, la regla local de reconexión de aristas, la distancia máxima que puede alcanzar una arista dinámica, la topología inicial subyacente en la red y el número máximo de conexiones que un vértice puede aceptar. Palabras Clave: Algoritmos Distribuidos, Ciencia de Redes, Ciencias de la Complejidad, Simulación de Eventos Discretos.
Complex networks, emerge naturally in many systems of different knowledge areas, in particular, in the Information technologies area, we can find them by describing the underlying topology of the Internet, the World Wide Web, social networks, peer to peer networks, and more. In recent decades, the study of complex networks has become in an important research area, because of, thanks to them, the interactions between the components of the systems they represent can be modeled. Moreover, like any network, they have certain structural properties, such as their average path length, diameter, average clustering coefficient, modularity or their degree distribution, which determine some of their functional properties, such as their robustness to random failures and targeted attacks, data transmission speed, and more. This research, proposes experiments based on connection and reconnection of edges, through which a set of networks with mesh or ring topology, evolves until obtaining characteristics found in complex networks. From these experiments, networks emerged with a high degree of robustness against random failures and targeted sequential attacks and, moreover, compared to their initial measures, have considerably reduced diameters and average path lengths; a high clustering coefficient and show a community structure by having a high modularity. The development of this research is divided in two stages: Stage 1 “Complex Network Formation”: In this research, we propose to model a complex network as a distributed system, where its vertices are entities that process information, and its edges are the communication channels that allow the vertices to communicate with each other. Based on the idea that the distributed systems can be simulated on a computer, a discrete event simulator was written in the “python” programming language, under the oriented-object programming paradigm, which, follows the distributed programming model by messages passage. On the simulator, a series of experiments were executed, where, starting with an initial network with a mesh or ring topology, each of its vertices applies a set of easy rules of edge reconnection, which will allow it to find shortcuts that connect it to far regions from its initial local environment, thus modifying the underlying topology of the network. This made it possible to carry out a rigorous study on the effects of cooperation on the structural evolution of the initial networks, which, when subjected to various processes of edges reconnection, undergo changes to the point where their structural properties converge to properties commonly found in complex networks. Stage 2 “Complex Networks Degradation”: In this stage, the robustness (ability of a network of still operating under adverse circumstances) of the networks obtained in the stage 1 was measured, under two different degradation processes: random failures, under the selection of vertices based on a uniform probability distribution function, and directed sequential attacks, under the selection of vertices based on their number of incident edges, in descending order. This was carried out through the use of a metric denominated “mean of the average two terminal reliability”, which gives the robustness threshold to both processes of each network. The results of this second stage, show the robustness of the emerging networks in the stage 1, vary considerably according to the configurations of diverse parameters used in the experiments, such as the routing algorithm, the local rule of edge reconnection, the maximum distance that can be reached by a dynamic edge, the underlying initial topology in the network and the maximum number of connections that a vertex can accept. Keywords: Distributed Algorithms, Network Science, Complexity Sciences, Discrete Event Simulation.
Relaciones
| En Conjunto Administrativo: |
|---|
Descripciones
| Nombre del atributo | Valores |
|---|---|
| Creador | |
| Colaboradores | |
| Tema | |
| Editor | |
| Idioma | |
| Identificador | |
| Palabra Clave | |
| Año de publicación |
|
| Tipo de Recurso | |
| Derechos | |
| División académica | |
| Línea académica | |
| Licencia |
