<< Volver atrás

Tesis:

Modelo de redes complejas mediante enlace compatible : aplicación a sistemas reales

  • Autor: CÁRDENAS VILLALOBOS, Juan Pablo

  • Título: Modelo de redes complejas mediante enlace compatible : aplicación a sistemas reales

  • Fecha: 2009

  • Materia: Matemáticas

  • Escuela: E.T.S. DE INGENIEROS AGRONOMOS

  • Departamentos: FISICA Y MECANICA FUNDAMENTAL Y APLICADA A LA INGENIERIA AGROFORESTAL

  • Acceso electrónico: http://oa.upm.es/2026

  • Director/a 1º: BENITO ZAFRILLA, Rosa María
  • Director/a 2º: LOSADA GONZÁLEZ, Juan Carlos

  • Resumen: Este trabajo se enmarca dentro del ámbito de la Complejidad profundizando en los mecanismos que la caracterizan y subyacen. En particular la tesis se enfoca en el estudio de redes como una abstracción puramente topológica de los sistemas. Desde esta perspectiva, un sistema complejo puede ser “fotografiado” como una red compuesta por elementos, denominados vértices o nodos, y los enlaces que los relacionan. Durante la última década un gran número de sistemas complejos reales han sido estudiados bajo esta perspectiva con resultados realmente sorprendentes. A pesar de que hasta hace poco tiempo se asumía tácitamente que la naturaleza de las interacciones en los sistemas complejos era de naturaleza aleatoria1 y por ende trivial, a la luz de los resultados experimentales hoy en día sabemos que esto no es así. De hecho, los componentes de los sistemas complejos aparecen relacionados de forma no trivial y muy poco intuitiva, generando propiedades comunes muy interesantes en los sistemas de los que forman parte2. Una de esas propiedades tiene que ver con la presencia de un escalado en la distribución de conectividades de los vértices. Dicha distribución, también conocida como distribución de grado P(k), indica la probabilidad de encontrar un vértice con un grado k determinado en la red. Lo interesante es que este escalado muestra un comportamiento asintótico con la forma P(k) _ k-. Este fenómeno denota una alta heterogeneidad en los grados de conectividad presentes en la red, algo totalmente distinto a lo observado en redes aleatorias3, y es la razón para que a estas redes se les denomine libres de escala, por no tener grado k (escala) que las caracterice. Es esta misma heterogeneidad la que además hace posible que en este tipo de redes existan unos pocos vértices altamente conectados (hubs) jugando un papel protagónico en el funcionamiento del sistema. Además, las redes estudiadas se caracterizan por presentar una organización clusterizada de sus componentes y por que entre cualquier par de estos existe, en promedio, una corta distancia a través de enlaces relacionales, un fenómeno conocido como efecto small world 4. El alto coeficiente de clustering medio de las redes y el efecto de pequeño mundo son junto al carácter libre de escala, el sello característico de las llamadas redes complejas. El origen de esta complejidad puede ser atribuído, al menos intuitivamente, a la evoluci ón en sistemas naturales. El tiempo y los mecanismos asociados a dicho proceso podrían jugar un papel determinante en la emergencia de las propiedades complejas en las redes estudiadas. . . En sistemas artificiales sin embargo esto no parece tan claro. A pesar de que la red de Internet fue una de las primeras documentadas con propiedades complejas, dicha complejidad no llamó tanto la atención debido a que su crecimiento no es coordinado ni planificado, al igual que en los sistemas naturales. No obstante, una serie de sistemas artificiales, planificados y de crecimiento coordinado, también han mostrado propiedades complejas muy similares a las observadas en la Internet y otros sistemas de origen biológico, social o ecológico. Esta complejidad ubicua estaría sugiriendo que existen mecanismos o leyes fundamentales tras la evolución de los sistemas, independiente de su origen. Considerando la existencia de mecanismos comunes que engendran complejidad, las topologías complejas han sido estudiadas a través de modelos generales de red en un intento por encontrar los principios fundamentales las gobiernan. Estos modelos generan conjuntos de redes que presentan similitudes estructurales o funcionales con las reales, o que bien, ahondan en los mecanismos que generan sus propiedades topológicas. Un buen ejemplo de este último tipo de modelos es el bien conocido Modelo de Enlace Preferencial (PA)5 que considera una regla de tipo social, en la que el rico se hace más rico, como la regla que gobierna la evolución de la red. De esta forma, un nuevo vértice añadido a la red se enlaza con mayor probabilidad a aquellos más conectados. Lo interesante es que el modelo PA genera redes libres de escala. Por esta razón, este mecanismo de enlace preferencial es la base para muchos modelos que reproducen, con éxito, las topologías observadas en la red de Internet y otros sistemas complejos. A pesar de que el modelo PA parece convincente, especialmente a la luz de los resultados, es valido preguntarse qué sucede si en el proceso de crecimiento de la red el nuevo vértice que llega no es capaz de conocer información topológica de sus pares, como lo es el grado k. De hecho Hallinan6 dice que el mecanismo de enlace preferencial puede ser correcto para cierto tipo de sistemas, como los sociales, pero en el caso de aquellos sistemas compuestos por elementos que no pueden “ver” propiedades topológicas del resto, esto parece un planteamiento inadecuado. Considerando este escenario, otros modelos toman en cuenta la limitación del enlace preferencial y proponen modelos en los cuales los elementos se enlazan sólo por reglas locales (que no consideran información topológica) lo que puede resultar en algunos casos en que el vértice más óptimo capture más enlaces. Dentro de esta línea, Calderelli y colaboradores7 propusieron un modelo de fitness que asigna la responsabilidad de generar enlaces sólo a una regla local. En el modelo de fitness, que no considera el crecimiento de la red, los vértices son enlazados de acuerdo a la relación entre sus atributos. Hoy en día comienzan a aparecer las primeras evidencias empíricas que prueban la existencia de afinidad entre los elementos de sistemas complejos. Garlaschelli y Loffredo8 mostraron que los enlaces de la red mundial de comercio son generados por afinidad. Más receintemente, Deeds y colaboradores9 propusieron un modelo para redes de interacción proteína-proteína basado también en su afinidad o compatibilidad. Desde esta perspectiva, en esta tesis se propone un modelo de enlace similar al propuesto por Calderelli et al., pero que considera la llegada de nuevos vértices a la red. En este caso una red puede emerger considerando un simple mecanismo local denominado compatibilidad, que representa la compatibilidad entre los caracteres que caracterizan a los vértices de la red. Dichos caracteres son definidos mediante una determinada función de densidad de probabilidad. Se trabaja bajo el supuesto de que es la compatibilidad entre elementos del sistema la que hace posible enlaces entre proteínas determinando sus conexiones en el Interactoma (red de proteínas), también entre palabras de un texto dando origen a una red de palabras, o entre equipos de telecomunicación generando una red tecnológica denominada SDH10. Los citados sistemas complejos: interactoma, redes de palabras y redes SDH, fueron exhaustivamente estudiados desde una perspectiva de redes y para cada uno de estos sistemas se diseñó un modelo de compatibilidad particular que reprodujese la topología observada en su abstracción como red. La propuesta de estos modelos de compatibilidad, y en general el enfoque de la investigaci ón, se basó en tres hipótesis fundamentales. La primera de ellas tiene que ver con la idea de que la complejidad es una resultante espontánea de un proceso dinámico cuando aumentan las posibilidades de interacción entre los elementos del sistema. La segunda hipótesis de este trabajo es que el mecanismo tras dicha emergencia de complejidad es la criticalidad autoorganizada11. Por último, considerando que la complejidad es polifac ética12, la tercera hipótesis de esta investigación tiene que ver con que la definición de complejidad en redes también lo es. De acuerdo a los resultados obtenidos del estudio experimental, se mostró que los tres sistemas complejos estudiados desde la perspectiva de las redes presentan propiedades topológicas no triviales y, lo más interesante, comunes. En particular, los tres sistemas presentan distribuciones de grado ajustadas a una ley de potencia y propiedades de redes small world, signos inequívocos de complejidad. Por otro lado, considerando la propuesta de un modelo dinámico de red basado en la compatibilidad entre componentes del sistema, se mostró que la compatibilidad es un mecanismo que engendra complejidad cuando opera en un proceso dinámico de adición de nuevos elementos al sistema, cuando la probabilidad de enlace entre elementos se mantiene constante y cuando el carácter de estos elementos está determinado por funciones de densidad de probabilidad en las cuales el valor medio no es el más probable. De hecho, cuando se cumplen estas condiciones, los modelos de compatibilidad son capaces de reproducir muchas de las propiedades topológicas complejas de los tres sistemas reales estudiados. El desarrollo de este trabajo está estructurado de la siguiente forma. En el Capítulo 1 se presenta un estudio teórico sobre los sistemas complejos, y en especial sobre redes complejas, profundizando en los mecanismos que subyacen su evolución. El Capítulo 2 corresponde a la propuesta del modelo dinámico de red antes mencionado: Modelo Evolutivo por Enlace Compatible (MEEC). La aplicación de dicho modelo a los tres sistemas complejos reales antes mencionados es lo que se presenta entre los capítulos 3 y 5. En el Capítulo 3 se estudia la red de interacción proteína-proteína del microorganismo S. cerevisiae proponiendo un modelo de compatibilidad para ésta. Lo mismo se hace en los capítulo 4 y 5 para redes de palabras obtenidas desde textos y para redes de telecomunicaci ón SDH, respectivamente. La validación de las hipótesis planteadas a lo largo del trabajo se desarrolla en el Capítulo 6. El Capítulo 7 corresponde a un estudio sobre la complejidad computacional de los modelos propuestos en la tesis. La tesis finaliza con el Capítulo 8 donde se desarrollan las conclusiones del trabajo. Abstract This work is focused on the complexity of networks. The theory of complex networks constitutes a framework for describing the interactions in a system from a purely topological point of view, abstracting away the dynamical processes that take such structure as substrate. From this standpoint a system can be seen as a network composed of a set of nodes connected by links. During the last decade, a wide range of real complex systems were studied from this perspective. A common and non-trivial topology was observed in most of the systems studied13. In particular, the topologies found in these complex networks are characterized by the presence of scaling in the degree distribution of nodes. The degree distribution measures the probability of a node having a given number of links or degree k, and the scaling displays as an asymptotic behavior in the form P(k) _ k-. This phenomenon denotes a high inhomogeneity in the connectivity degrees, unlike the one observed in random networks, which leads to the term scale-free network. Such inhomogeneity points to a nonnegligible presence of densely connected nodes (hubs) in this kind of networks. Complex topologies are also characterized by properties of small world networks14, associated with low distances between randomly chosen pairs of nodes and a high clustering coefficient. The scale-free character and properties of small world networks seem to be a finger print of the so called complex networks. The presence of complexity can be explained, at least intuitively, as an effect of evolution in natural systems. The time and the mechanisms associated to this process would play an important role in the emergence of complexity; in artificial systems, however, this does not seem so clear. Despite of the fact that the Internet was one of the first instances of artificial network documented to exhibit characteristic complex traits, such properties were not so surprising in this case due to its local, uncoordinated and unplanned growth. Nevertheless, in the past few years many artificial systems have shown similar distinctive traits despite their global, coordinated and planned growth, totally unlike the evolution of either the Internet or natural systems. The ubiquity of complexity in many real networks suggests that there may exist universal principles underlying the evolution of complex systems irrespective of their origin. Considering the idea of common principles behind the evolution of complex systems complex topologies have been approached through general purpose network models, which aim to distill the general organization principles underlying the topologies of real networks. Network models generate ensembles of networks with certain structural or functional properties, either by statistically characterizing the network traits to be captured, or alternatively by describing the mechanisms that drive an evolving network into a structure with the desired traits. A well known example of the latter is the preferential attachment (PA) model15. The model considers a social-like rule, where the rich get richer, as the rule that governs the growth of the network. Thus, a new node added to the system is linked preferentially to the most connected nodes. This mechanism is the basis for many models which successfully explain the complexity found on the Internet and other natural and artificial systems. Though the mechanism appears to be convincing, we might still ask what happens if, in the process of network growth, new nodes are unable to obtain global information about the network, such as the connectivity or the age of the present nodes. Hallinan16 has said that the preferential attachment mechanism can be correct in the case of social systems, but does not fit systems composed by elements unable to “look” at the rest of the components. Considering this kind of scenario, other models take into account this limitation of PA and propose that links between nodes are mediated by local rules which results in that the good get richer. Under this perspective, Calderelli et al.17 proposed the fitness model that assigns the responsibility to generate links to a local rule. In the fitness model, which does not consider network growth (i.e., a static model), the nodes are linked only according to the relation of their characters or fitness. Actually, begin to appear the first evidence for this approach. Garlaschelli and Loffredo18 showed the first empirical study which proves the existence of affinity between nodes of the World Trade Web. More recently, Deeds et al.19 proposed a model for protein-protein interaction networks based on the free energy of binding of each molecule. From this perspective, in this work we propose a dynamic network model which considers only local and limited information during the evolution of the system. In the model, a network can arise considering a simple local mechanism defined as compatibility, by which we mean that behind the link of two system elements is involved the compatibility between their characters defined by a certain probability density function. We apply this model to three real complex systems: the protein-protein interaction network (proteome) of S. cerevisiae, word networks extracted from texts and the telecommunication nettwork SDH20. In this way, we are saying that the compatibility between proteins that determines their connections, or the compatibility between equipments that generates a technological network, are mediated by the compatibility of their characters. Considering the empirical study we observed that the real systems display similar topological properties. In fact, scale free distribution of connectivities and small world networks properties have been observed in the three real systems. These properties of complex networks were reproduced by the compatibility models proposed. Taking into account these results, we demonstrated that the compatibility mechanism generates complexity in a process of network growth. The organization of the thesis is as follow: in Chapter 1 a theoretical study of complex systems, specially complex networks, is presented. In Chapter 2 is presented the compatibility attachment model. The application of the model to real systems (Yeast proteome, word networks and SDH networks) is presented in chapters 3, 4 and 5 respectively. The validation of the hypothesis developed in the thesis is shown in Chapter 6. An approach to the computational complexity of the models used in the thesis is developed in Chapter 7. The last chapter corresponds to the conclusion of the work