Desarrollo de algoritmos de aprendizaje de representaciones en redes complejas
Las redes complejas suelen tener un crecimiento no aleatorio, y en muchos casos se pueden describir los mecanismos de crecimiento con modelos. El modelo de crecimiento de redes de Popularidad-Similaridad (PS) asume un espacio hiperbólico de dos dimensiones sobre el cuál crecen las redes. Estas redes...
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Tesis NonPeerReviewed |
| Lenguaje: | Español |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | http://ricabib.cab.cnea.gov.ar/1159/1/1Fam%C3%A1.pdf |
| Aporte de: |
| id |
I25-R131-1159 |
|---|---|
| record_format |
dspace |
| institution |
Instituto Balseiro |
| institution_str |
I-25 |
| repository_str |
R-131 |
| collection |
Repositorio Institucional Centro Atómico Bariloche e Instituto Balseiro (RICABIB) |
| language |
Español |
| orig_language_str_mv |
es |
| topic |
Redes complejas Machine learning Aprendizaje automático Algorithms Algoritmos [Networks Redes Hyperbolic Hiperbólico Embeddings Embebidos Complex networks Redes complejas] |
| spellingShingle |
Redes complejas Machine learning Aprendizaje automático Algorithms Algoritmos [Networks Redes Hyperbolic Hiperbólico Embeddings Embebidos Complex networks Redes complejas] Famá, Martín Desarrollo de algoritmos de aprendizaje de representaciones en redes complejas |
| topic_facet |
Redes complejas Machine learning Aprendizaje automático Algorithms Algoritmos [Networks Redes Hyperbolic Hiperbólico Embeddings Embebidos Complex networks Redes complejas] |
| description |
Las redes complejas suelen tener un crecimiento no aleatorio, y en muchos casos se pueden describir los mecanismos de crecimiento con modelos. El modelo de crecimiento de redes de Popularidad-Similaridad (PS) asume un espacio hiperbólico de dos dimensiones sobre el cuál crecen las redes. Estas redes sintéticas tienen características estadísticas, específicamente un nivel alto de clustering de los nodos, y también una distribución heterogénea de grados, típico de redes que son scale-free o libres de escala. Una gran variedad de redes reales, como redes de interacciones de proteínas o redes de conexiones entre los routers que distribuyen Internet, muestran cualidades estadísticas similares a las redes sintéticas generadas con el modelo PS. Es entonces un modelo que
permite interpretar la información de ciertas redes reales.
En ciertos contextos, puede ser de gran utilidad encontrar representaciones compactas de dichas redes complejas. La reducción de dimensionalidad es una herramienta poderosa en el análisis de redes complejas. Trabajando con embeddings, siendo un embedding de nodos de una red un mapeo de los nodos a un espacio vectorial, se puede hacer este mapeo, con particular enfoque en espacios de dimensionalidades bajas. Luego, es posible trabajar sobre este nuevo espacio para inferir información sobre la estructura de la red. Teniendo un modelo que describe una cierta familia de redes, se puede buscar un algoritmo de embedding específico a ese modelo que preserva ciertas propiedades de interés de las redes al mapearlas al nuevo espacio, denominado espacio latente. Que se preserve la estructura viene dado por las posiciones de los vectores en este espacio. Un método que permite inferir información sobre la topología de la red involucra embeddings en donde las distancias vectoriales entre los vectores respectivos de los nodos son representativas de determinados tipos de relación entre esos nodos. Es decir, nodos altamente relacionados en la red tenderán a estar a distancias pequeñas en el espacio latente. Con esta representación, es posible inferir cualidades estadísticas de las redes y aplicaciones como la predicción de enlaces.
Este trabajo se enfoca en considerar embeddings a un espacio hiperbólico. Se hace un enfoque en abarcar redes desde el punto de vista del modelo PS. En general, hay un interés creciente en analizar la fuerte relación entre cierto tipos de redes complejas y el espacio hiperbólico. Cuando una red cumple con ciertas cualidades estructurales, es factible modelar y describir dicha red desde el marco de un espacio continuo hiperbólico. Algunas de estas cualidades típicas son por ejemplo tener una distribución de grados de tipo scale-free y tener un nivel alto de clustering, como en el modelo de PS. En particular, se consideran dos algoritmos distintos de embedding, y luego se combinan para lograr que la efectividad de estos embeddings, en cuanto a lograr preservar la micro y macro estructura de la red, sea más alta que cada método por separado, en ciertos casos, considerablemente. El primer método es el Laplacian-based Network Embedding (LaBNE), propuesto por Alanis-Lobato y colaboradores en [1], que asume un espacio inherente hiperbólico para mapear redes a H"2.
En particular, asume que las redes son descriptibles por el modelo PS, y se basa en la escala de la distribución de grados para aplicar un re-ordenamiento radial a las coordenadas obtenidas por La- placian Eigenmaps [2], que es un método establecido de reducción de dimensionalidad mediante teoría espectral de grafos. Luego se considera el algoritmo de Poincaré Em-beddings, planteado en [3] por Nickel y Kiela. Este algoritmo se basa en la cualidad hiperbólica de las redes complejas, pero no asume un modelo en particular como el PS. Consiste en actualizar de manera iterada las posiciones de los nodos, en pequeños pasos, asumiendo un geometría diferencial hiperbólica que permite minimizar una función de pérdida, la cual está armada de modo que tiende a decrecer cuando las distancias entre nodos altamente relacionadas son pequeñas en comparación con las distancias entre nodos poco relacionados.
El trabajo consiste entonces en una breve introducción al concepto de embeddings en el capítulo 2, con enfoque en el uso del termino referido al análisis de redes complejas en el área de aprendizaje automático. Se presentan los conceptos principales que serían
aplicados para vericar la capacidad predictiva de los embeddings, como por ejemplo en hacer predicción de enlaces. Luego, en el capítulo 3 se introducen los aspectos teóricos del espacio hiperbólico que son relevantes para encontrar relaciones entre este espacio y las redes complejas que son de interés. Se ven conceptos como la geometría diferencial del espacio, que luego permite plantear el algoritmo de Poincaré Embeddings, y también equivalencias entre la jerarquía de redes complejas con la forma y estructura de todo el espacio. Al final del capítulo se presenta el modelo de Popularidad-Similaridad, explicando el algoritmo detallado por el modelo para generar redes, junto con una modificación propia de este trabajo generalizando el modelo de 2 dimensiones a n dimensiones, con
n arbitrariamente grande. En el capítulo 4 se presentan los dos algoritmos de embedding que se implementan y estudian en este trabajo, LaBNE y Poincaré Embeddings. También se incluye una sección acerca de la implementación en código de todos los algoritmos, con comentarios acerca de las dificultades computacionales de trabajar con redes complejas mayores que
cierto tamaño.
Finalmente, se tratan resultados en el capítulo 5. En particular, se hace primero un análisis sobre redes sintéticas generadas con PS, vericando el funcionamiento de los algoritmos de embedding y la capacidad de los mismos para preservar la información relevante de las redes. Luego, se pone el enfoque en una red real, en particular la red de Autonomous Systems Internet (ASI). Se generan embeddings de estas redes de distintas características, buscando encontrar los puntos óptimos e indicando las limitaciones de
los métodos. Por ultimo, se mencionan líneas de investigación a futuro que se pueden seguir a partir de este trabajo, como por ejemplo estudiar otras redes reales de distintas características y mayor tamaño, y extender los modelos del espacio hiperbólico para encontrar ventajas y desventajas en los distintos modelos. |
| format |
Tesis NonPeerReviewed |
| author |
Famá, Martín |
| author_facet |
Famá, Martín |
| author_sort |
Famá, Martín |
| title |
Desarrollo de algoritmos de aprendizaje de representaciones en redes complejas |
| title_short |
Desarrollo de algoritmos de aprendizaje de representaciones en redes complejas |
| title_full |
Desarrollo de algoritmos de aprendizaje de representaciones en redes complejas |
| title_fullStr |
Desarrollo de algoritmos de aprendizaje de representaciones en redes complejas |
| title_full_unstemmed |
Desarrollo de algoritmos de aprendizaje de representaciones en redes complejas |
| title_sort |
desarrollo de algoritmos de aprendizaje de representaciones en redes complejas |
| publishDate |
2022 |
| url |
http://ricabib.cab.cnea.gov.ar/1159/1/1Fam%C3%A1.pdf |
| work_keys_str_mv |
AT famamartin desarrollodealgoritmosdeaprendizajederepresentacionesenredescomplejas |
| _version_ |
1794277903716843520 |
| spelling |
I25-R131-11592023-03-08T18:54:51Z Desarrollo de algoritmos de aprendizaje de representaciones en redes complejas Development of machine learning for network representations Famá, Martín Redes complejas Machine learning Aprendizaje automático Algorithms Algoritmos [Networks Redes Hyperbolic Hiperbólico Embeddings Embebidos Complex networks Redes complejas] Las redes complejas suelen tener un crecimiento no aleatorio, y en muchos casos se pueden describir los mecanismos de crecimiento con modelos. El modelo de crecimiento de redes de Popularidad-Similaridad (PS) asume un espacio hiperbólico de dos dimensiones sobre el cuál crecen las redes. Estas redes sintéticas tienen características estadísticas, específicamente un nivel alto de clustering de los nodos, y también una distribución heterogénea de grados, típico de redes que son scale-free o libres de escala. Una gran variedad de redes reales, como redes de interacciones de proteínas o redes de conexiones entre los routers que distribuyen Internet, muestran cualidades estadísticas similares a las redes sintéticas generadas con el modelo PS. Es entonces un modelo que permite interpretar la información de ciertas redes reales. En ciertos contextos, puede ser de gran utilidad encontrar representaciones compactas de dichas redes complejas. La reducción de dimensionalidad es una herramienta poderosa en el análisis de redes complejas. Trabajando con embeddings, siendo un embedding de nodos de una red un mapeo de los nodos a un espacio vectorial, se puede hacer este mapeo, con particular enfoque en espacios de dimensionalidades bajas. Luego, es posible trabajar sobre este nuevo espacio para inferir información sobre la estructura de la red. Teniendo un modelo que describe una cierta familia de redes, se puede buscar un algoritmo de embedding específico a ese modelo que preserva ciertas propiedades de interés de las redes al mapearlas al nuevo espacio, denominado espacio latente. Que se preserve la estructura viene dado por las posiciones de los vectores en este espacio. Un método que permite inferir información sobre la topología de la red involucra embeddings en donde las distancias vectoriales entre los vectores respectivos de los nodos son representativas de determinados tipos de relación entre esos nodos. Es decir, nodos altamente relacionados en la red tenderán a estar a distancias pequeñas en el espacio latente. Con esta representación, es posible inferir cualidades estadísticas de las redes y aplicaciones como la predicción de enlaces. Este trabajo se enfoca en considerar embeddings a un espacio hiperbólico. Se hace un enfoque en abarcar redes desde el punto de vista del modelo PS. En general, hay un interés creciente en analizar la fuerte relación entre cierto tipos de redes complejas y el espacio hiperbólico. Cuando una red cumple con ciertas cualidades estructurales, es factible modelar y describir dicha red desde el marco de un espacio continuo hiperbólico. Algunas de estas cualidades típicas son por ejemplo tener una distribución de grados de tipo scale-free y tener un nivel alto de clustering, como en el modelo de PS. En particular, se consideran dos algoritmos distintos de embedding, y luego se combinan para lograr que la efectividad de estos embeddings, en cuanto a lograr preservar la micro y macro estructura de la red, sea más alta que cada método por separado, en ciertos casos, considerablemente. El primer método es el Laplacian-based Network Embedding (LaBNE), propuesto por Alanis-Lobato y colaboradores en [1], que asume un espacio inherente hiperbólico para mapear redes a H"2. En particular, asume que las redes son descriptibles por el modelo PS, y se basa en la escala de la distribución de grados para aplicar un re-ordenamiento radial a las coordenadas obtenidas por La- placian Eigenmaps [2], que es un método establecido de reducción de dimensionalidad mediante teoría espectral de grafos. Luego se considera el algoritmo de Poincaré Em-beddings, planteado en [3] por Nickel y Kiela. Este algoritmo se basa en la cualidad hiperbólica de las redes complejas, pero no asume un modelo en particular como el PS. Consiste en actualizar de manera iterada las posiciones de los nodos, en pequeños pasos, asumiendo un geometría diferencial hiperbólica que permite minimizar una función de pérdida, la cual está armada de modo que tiende a decrecer cuando las distancias entre nodos altamente relacionadas son pequeñas en comparación con las distancias entre nodos poco relacionados. El trabajo consiste entonces en una breve introducción al concepto de embeddings en el capítulo 2, con enfoque en el uso del termino referido al análisis de redes complejas en el área de aprendizaje automático. Se presentan los conceptos principales que serían aplicados para vericar la capacidad predictiva de los embeddings, como por ejemplo en hacer predicción de enlaces. Luego, en el capítulo 3 se introducen los aspectos teóricos del espacio hiperbólico que son relevantes para encontrar relaciones entre este espacio y las redes complejas que son de interés. Se ven conceptos como la geometría diferencial del espacio, que luego permite plantear el algoritmo de Poincaré Embeddings, y también equivalencias entre la jerarquía de redes complejas con la forma y estructura de todo el espacio. Al final del capítulo se presenta el modelo de Popularidad-Similaridad, explicando el algoritmo detallado por el modelo para generar redes, junto con una modificación propia de este trabajo generalizando el modelo de 2 dimensiones a n dimensiones, con n arbitrariamente grande. En el capítulo 4 se presentan los dos algoritmos de embedding que se implementan y estudian en este trabajo, LaBNE y Poincaré Embeddings. También se incluye una sección acerca de la implementación en código de todos los algoritmos, con comentarios acerca de las dificultades computacionales de trabajar con redes complejas mayores que cierto tamaño. Finalmente, se tratan resultados en el capítulo 5. En particular, se hace primero un análisis sobre redes sintéticas generadas con PS, vericando el funcionamiento de los algoritmos de embedding y la capacidad de los mismos para preservar la información relevante de las redes. Luego, se pone el enfoque en una red real, en particular la red de Autonomous Systems Internet (ASI). Se generan embeddings de estas redes de distintas características, buscando encontrar los puntos óptimos e indicando las limitaciones de los métodos. Por ultimo, se mencionan líneas de investigación a futuro que se pueden seguir a partir de este trabajo, como por ejemplo estudiar otras redes reales de distintas características y mayor tamaño, y extender los modelos del espacio hiperbólico para encontrar ventajas y desventajas en los distintos modelos. Complex networks tend to have non-random growth, and in many cases the growth mechanisms can be described with models. The Popularity-Similarity (PS) network growth model assumes a two-dimensional hyperbolic space over which the networks grow. These synthetic networks have statistical characteristics, specifically a high level of node clustering, and also a heterogeneous degree distribution, typical of scale-free networks. A variety of real networks, such as networks of protein interactions or networks of connections between routers that distribute the Internet, exhibit statistical qualities similar to the synthetic networks generated with the PS model. It is therefore a model that allows the interpretation of the information of certain real networks. In certain contexts, it can be very useful to find compact representations of such complex networks. Dimensionality reduction is a powerful tool in the analysis of complex networks. Working with embeddings, being an embedding of nodes of a network a mapping of the nodes to a vector space, this mapping can be done, with particular focus on low dimensionality spaces. Then, it is possible to work on this new space to infer information about the structure of the network. Having a model that describes a certain family of networks, it is possible to find an embedding algorithm specific to that model that preserves certain properties of interest of the networks by mapping them to the new space, called latent space. Whether the structure is preserved is given by the positions of the vectors in this space. One method of inferring information about the topology of the network involves embeddings where the vector distances between the respective vectors of the nodes are representative of certain types of relationships between those nodes. That is, highly related nodes in the network will tend to be at small distances in latent space. With this representation, it is possible to infer statistical qualities of networks and applications such as link prediction. This work focuses on considering embeddings to a hyperbolic space. A focus is made on covering networks from the point of view of the PS model. In general, there is a growing interest in analyzing the strong relationship between certain types of complex networks and hyperbolic space. When a network meets certain structural qualities, it is feasible to model and describe such a network from the framework of a continuous hyperbolic space. Some of these typical qualities are for example having a scale-free degree distribution and having a high level of clustering, as in the PS model. In particular, two different embedding algorithms are considered, and then combined so that the effectiveness of these embeddings, in terms of preserving the micro- and macro-structure of the network, is higher than that of the PS model. The work then consists of a brief introduction to the concept of embeddings in chapter 2, focusing on the use of the term in the analysis of complex networks in the area of machine learning. The main concepts that would be applied to verify the predictive applied to verify the predictive capability of embeddings, such as link prediction. Then, in chapter 3 the theoretical aspects of the hyperbolic space that are relevant to find relationships between this space and the complex networks of interest are introduced. Concepts such as the differential geometry of the space, which then allows the Poincaré Embeddings algorithm to be proposed, and also equivalences between the hierarchy of complex networks with the shape and structure of the whole space, are seen. At the end of the chapter the Popularity-Similarity model is presented, explaining the algorithm detailed by the model to generate lattices, along with a modification specific to this work generalizing the 2-dimensional model ton dimensions, withn arbitrarily large. Chapter 4 presents the two embedding algorithms implemented and studied in this work, LaBNE and Poincaré Embeddings. Also included is a section about the implementation in code of all the algorithms, with comments about the computational difficulties of working with complex networks greater tan a certain size. Finally, results are discussed in Chapter 5. In particular, an analysis is first made on synthetic networks generated with PS, verifying the performance of the embedding algorithms and their ability to preserve the relevant information of the networks. Then, the focus is put on a real network, in particular the Autonomous Systems Internet (ASI) network. Embeddings of these networks of different characteristics are generated, seeking to find the optimal points and indicating the limitations of the methods. limitations of the methods. Finally, future research lines that can be followed from this work are mentioned, such as studying other real networks of different characteristics and larger size, and extending the hyperbolic space models to find advantages and disadvantages in the different models. 2022-12-20 Tesis NonPeerReviewed application/pdf http://ricabib.cab.cnea.gov.ar/1159/1/1Fam%C3%A1.pdf es Famá, Martín (2022) Desarrollo de algoritmos de aprendizaje de representaciones en redes complejas / Development of machine learning for network representations. Maestría en Ciencias Físicas, Universidad Nacional de Cuyo, Instituto Balseiro. http://ricabib.cab.cnea.gov.ar/1159/ |