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: |
| Sumario: | 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. |
|---|