Carregant...
Fitxers
Tipus de document
TesiVersió
Versió publicadaData de publicació
Tots els drets reservats
Si us plau utilitzeu sempre aquest identificador per citar o enllaçar aquest document: https://hdl.handle.net/2445/226574
Hyperbolic Cartography of Complex Networks. Designing Maps for Unipartite, Bipartite, and Feature-Enriched Graphs
Títol de la revista
Autors
Director/Tutor
ISSN de la revista
Títol del volum
Recurs relacionat
Resum
[eng] Cartography is the science and practice of creating and utilizing maps. Originating in ancient times, it flourished notably during the Age of Discovery and remains essential today through digital mapping applications. Historically, maps have served both to depict the world generally and to facilitate navigation and wayfinding. Nowadays, we regularly rely on tools such as Google Maps to commute within cities through transportation networks, including metro, bus, and tram systems. These physical networks are naturally embedded in Euclidean space. However, many social, biological, or technological networks lack such apparent spatial structures. In this Thesis, we develop methods to chart multidimensional hyperbolic maps for a diverse range of complex systems, encompassing unipartite, bipartite, and feature-enriched networks. These maps provide new means to interpret, analyze, and visualize these systems. Studying interactions between discrete entities has emerged as the study of complex networks in recent years. Many networks share similar topological properties, such as the small-world effect, heavy-tailed degree distributions, high clustering coefficients, and sparsity. The network geometry framework was proposed to explain these properties. In this approach, nodes are located in the hidden latent space, where each node’s coordinates reflect its similarity to other nodes and its intrinsic popularity, thereby intertwining the geometry with the network topology. Models from this family are able to explain many properties of real networks. These latent-space models accurately replicate empirical observations by interpreting connection probability as a decreasing function of hyperbolic distance. The quest to reverse-engineer these geometric models gave rise to model-based hyperbolic embeddings. By projecting complex networks into low-dimensional hyperbolic spaces, graph operations, such as community detection, node classification, and link prediction, become efficient vector computations. To date, however, these methods have been limited to one dimension, even though there is no reason for this to be the case. In this Thesis, we develop three multidimensional hyperbolic embed-dings: D-Mercator for unipartite networks, FiD-Mercator for feature-enriched networks, and B-Mercator for bipartite networks, demonstrating that these embeddings significantly enhance our understanding of network structures. With D-Mercator, we estimated the intrinsic dimensionality of real networks in terms of navigability and community structure. FiD-Mercator emphasized the importance of quantifying the correlations among node labels, graph topology, and node features for downstream tasks. Whereas, B-Mercator revealed patterns of linguistic and geographic diversity, and also improved the node classification task. Moreover, we bridged the gap between network geometry and graph machine learning by introducing HypBench, a benchmarking framework for graph neural networks. HypBench provided concrete guidance for selecting the optimal model for specific graph datasets. Together, these contributions establish a flexible, multidimensional framework for mapping and analyzing complex networks, offering novel insights and practical tools for advancing research across multiple disciplines.
cat] La cartografia és la ciència i la pràctica de crear i utilitzar mapes. Originària de temps antics, va florir notablement durant l’Era de l’Exploració i continua essent essencial avui en dia mitjançant aplicacions de cartografia digital. Històricament, els mapes han servit tant per representar el món de manera general com per facilitar la navegació i l’orientació. Actualment, confiem habitualment en eines com Google Maps per desplaçar-nos dins de les ciutats a través de xarxes de transport, incloent-hi sistemes de metro, autobús i tramvia. Aquestes xarxes físiques estan naturalment inscrites en l’espai Euclidià. No obstant això, moltes xarxes socials, biològiques o tecnològiques manquen d’una estructura espacial aparent. En aquesta Tesi, desenvolupem mètodes per cartografiar mapes hiperbòlics multidimensionals per a una àmplia gamma de sistemes complexos, que comprenen xarxes unipartites, bipartites i enriquides amb atributs. Aquests mapes proporcionen nous mitjans per interpretar, analitzar i visualitzar aquests sistemes. L’estudi de les interaccions entre entitats discretes ha emergit en els darrers anys com l’anàlisi de xarxes complexes. Moltes xarxes comparteixen propietats topològiques similars, com l’efecte de món petit, distribucions de grau amb cua gruixuda, alts coeficients d’agrupament i poca densitat. El marc de la geometria de xarxes va ser proposat per explicar aquestes propietats. En aquest enfocament, els nodes es troben en un espai latent ocult, on les coordenades de cada node reflecteixen la seva similitud amb altres nodes i la seva popularitat intrínseca, barrejant la geometria amb la topologia de la xarxa. Els models d’aquesta família poden explicar moltes propietats de les xarxes reals. Aquests models d’espai latent repliquen amb precisió les observacions empíriques interpretant la probabilitat de connexió com una funció decreixent de la distància hiperbòlica. La recerca per desemmascarar aquests models geomètrics va donar origen als embeddings hiperbòlics basats en models. En projectar xarxes complexes en espais hiperbòlics de baixa dimensió, les operacions sobre grafs, com la detecció de comunitats, la classificació de nodes i la predicció d’enllaços, es converteixen en càlculs vectorials eficients. Fins ara, però, aquests mètodes s’han limitat a una sola dimensió, tot i que no hi ha cap motiu perquè sigui així. En aquesta Tesi, desenvolupem tres embeddings hiperbòlics multidimensionals: D-Mercator per a xarxes unipartites, FiD-Mercator per a xarxes enriquides amb atributs i B-Mercator per a xarxes bipartites, demostrant que aquests embeddings milloren significativament la nostra comprensió de les estructures de les xarxes. Amb D-Mercator, vam estimar la dimensionalitat intrínseca de xarxes reals en termes de navegabilitat i estructura comunitària. FiD-Mercator va subratllar la importància de quantificar les correlacions entre les etiquetes dels nodes, la topologia del graf i les característiques dels nodes per a tasques posteriors. Mentrestant, B-Mercator va revelar patrons de diversitat lingüística i geogràfica i també va millorar la tasca de classificació de nodes. A més, vam escurçar la distància entre la geometria de xarxes i l’aprenentatge automàtic de grafs introduint HypBench, un marc de referència per a xarxes neuronals de grafs. HypBench va oferir orientació per a seleccionar el model òptim per a conjunts de dades de grafs específics. En conjunt, aquestes contribucions estableixen un marc multidimensional flexible per mapar i analitzar xarxes complexes, oferint noves perspectives i eines pràctiques per impulsar la recerca en múltiples disciplines.
[spa] La cartografía es la ciencia y la práctica de crear y utilizar mapas. Originaria de tiempos antiguos, floreció de manera notable durante la Era de los Descubrimientos y sigue siendo esencial hoy en día mediante aplicaciones de mapeo digital. Históricamente, los mapas han servido tanto para representar el mundo en general como para facilitar la navegación y la orientación. En la actualidad, confiamos regularmente en herramientas como Google Maps para desplazar-nos dentro de las ciudades a través de redes de transporte, incluidos sistemas de metro, autobús y tranvía. Estas redes físicas están naturalmente incrustadas en el espacio euclidiano. Sin embargo, muchas redes sociales, biológicas o tecnológicas carecen de estructuras espaciales tan evidentes. En esta Tesis, desarrollamos métodos para trazar mapas hiperbólicos multidimensionales de una amplia variedad de sistemas complejos, que abarcan redes unipartitas, bi-partitas y enriquecidas con atributos. Estos mapas ofrecen nuevos medios para interpretar, analizar y visualizar dichos sistemas. El estudio de las interacciones entre entidades discretas ha surgido en los últimos años como el estudio de las redes complejas. Muchas redes comparten propiedades topológicas similares, como el efecto de mundo pequeño, distribuciones de grado de cola gruesa, coeficientes de agrupamiento elevados y esparcimiento. El marco de la geOmetría de redes se propuso para explicar estas propiedades. En este enfoque, los nodos se sitúan en un espacio latente oculto, donde las coordenadas de cada nodo reflejan su similitud con otros nodos y su popularidad intrínseca, entrelazando así la geometría con la topología de la red. Los modelos de esta familia son capaces de explicar muchas propiedades de las redes reales. Estos modelos de espacio latente replican con precisión las observaciones empíricas al interpretar la probabilidad de conexión como una función decreciente de la distancia hiperbólica. La búsqueda para invertir estos modelos geométricos dio lugar a incrustaciones hiperbólicas basadas en modelos. Al proyectar redes complejas en espacios hiperbólicos de baja dimensión, las operaciones sobre grafos, como la detección de comunidades, la clasificación de nodos y la predicción de enlaces, se convierten en eficientes cálculos vectoriales. Hasta la fecha, sin embargo, estos métodos se han limitado a una sola dimensión, aunque no existe motivo alguno para que así sea. En esta Tesis, desarrollamos tres incrustaciones hiperbólicas multidimensionales: D-Mercator para redes unipartitas, FiD-Mercator para redes enriquecidas con atributos y B-Mercator para redes bipartitas, demostrando que estas incrustaciones mejoran significativamente nuestra comprensión de las estructuras de red. Con D-Mercator, estimamos la dimensionalidad intrínseca de redes reales en términos de navegabilidad y estructura de comunidades. FiD-Mercator destacó la importancia de cuantificar las correlaciones entre las etiquetas de los nodos, la topología del grafo y las características de los nodos para tareas posteriores. Por su parte, B-Mercator reveló patrones de diversidad lingüística y geográfica, y también mejoró la tarea de clasificación de nodos. Además, cerramos la brecha entre la geometría de redes y el aprendizaje automático en grafos al introducir HypBench, un benchmarking para redes neuronales de grafos. HypBench proporcionó orientación concreta para seleccionar el modelo óptimo para conjuntos de datos de grafos específicos. En conjunto, estas contribuciones establecen un marco multidimensional flexible para mapear y analizar redes complejas, ofreciendo nuevas perspectivas y herramientas prácticas para avanzar en la investigación en múltiples disciplinas.
cat] La cartografia és la ciència i la pràctica de crear i utilitzar mapes. Originària de temps antics, va florir notablement durant l’Era de l’Exploració i continua essent essencial avui en dia mitjançant aplicacions de cartografia digital. Històricament, els mapes han servit tant per representar el món de manera general com per facilitar la navegació i l’orientació. Actualment, confiem habitualment en eines com Google Maps per desplaçar-nos dins de les ciutats a través de xarxes de transport, incloent-hi sistemes de metro, autobús i tramvia. Aquestes xarxes físiques estan naturalment inscrites en l’espai Euclidià. No obstant això, moltes xarxes socials, biològiques o tecnològiques manquen d’una estructura espacial aparent. En aquesta Tesi, desenvolupem mètodes per cartografiar mapes hiperbòlics multidimensionals per a una àmplia gamma de sistemes complexos, que comprenen xarxes unipartites, bipartites i enriquides amb atributs. Aquests mapes proporcionen nous mitjans per interpretar, analitzar i visualitzar aquests sistemes. L’estudi de les interaccions entre entitats discretes ha emergit en els darrers anys com l’anàlisi de xarxes complexes. Moltes xarxes comparteixen propietats topològiques similars, com l’efecte de món petit, distribucions de grau amb cua gruixuda, alts coeficients d’agrupament i poca densitat. El marc de la geometria de xarxes va ser proposat per explicar aquestes propietats. En aquest enfocament, els nodes es troben en un espai latent ocult, on les coordenades de cada node reflecteixen la seva similitud amb altres nodes i la seva popularitat intrínseca, barrejant la geometria amb la topologia de la xarxa. Els models d’aquesta família poden explicar moltes propietats de les xarxes reals. Aquests models d’espai latent repliquen amb precisió les observacions empíriques interpretant la probabilitat de connexió com una funció decreixent de la distància hiperbòlica. La recerca per desemmascarar aquests models geomètrics va donar origen als embeddings hiperbòlics basats en models. En projectar xarxes complexes en espais hiperbòlics de baixa dimensió, les operacions sobre grafs, com la detecció de comunitats, la classificació de nodes i la predicció d’enllaços, es converteixen en càlculs vectorials eficients. Fins ara, però, aquests mètodes s’han limitat a una sola dimensió, tot i que no hi ha cap motiu perquè sigui així. En aquesta Tesi, desenvolupem tres embeddings hiperbòlics multidimensionals: D-Mercator per a xarxes unipartites, FiD-Mercator per a xarxes enriquides amb atributs i B-Mercator per a xarxes bipartites, demostrant que aquests embeddings milloren significativament la nostra comprensió de les estructures de les xarxes. Amb D-Mercator, vam estimar la dimensionalitat intrínseca de xarxes reals en termes de navegabilitat i estructura comunitària. FiD-Mercator va subratllar la importància de quantificar les correlacions entre les etiquetes dels nodes, la topologia del graf i les característiques dels nodes per a tasques posteriors. Mentrestant, B-Mercator va revelar patrons de diversitat lingüística i geogràfica i també va millorar la tasca de classificació de nodes. A més, vam escurçar la distància entre la geometria de xarxes i l’aprenentatge automàtic de grafs introduint HypBench, un marc de referència per a xarxes neuronals de grafs. HypBench va oferir orientació per a seleccionar el model òptim per a conjunts de dades de grafs específics. En conjunt, aquestes contribucions estableixen un marc multidimensional flexible per mapar i analitzar xarxes complexes, oferint noves perspectives i eines pràctiques per impulsar la recerca en múltiples disciplines.
[spa] La cartografía es la ciencia y la práctica de crear y utilizar mapas. Originaria de tiempos antiguos, floreció de manera notable durante la Era de los Descubrimientos y sigue siendo esencial hoy en día mediante aplicaciones de mapeo digital. Históricamente, los mapas han servido tanto para representar el mundo en general como para facilitar la navegación y la orientación. En la actualidad, confiamos regularmente en herramientas como Google Maps para desplazar-nos dentro de las ciudades a través de redes de transporte, incluidos sistemas de metro, autobús y tranvía. Estas redes físicas están naturalmente incrustadas en el espacio euclidiano. Sin embargo, muchas redes sociales, biológicas o tecnológicas carecen de estructuras espaciales tan evidentes. En esta Tesis, desarrollamos métodos para trazar mapas hiperbólicos multidimensionales de una amplia variedad de sistemas complejos, que abarcan redes unipartitas, bi-partitas y enriquecidas con atributos. Estos mapas ofrecen nuevos medios para interpretar, analizar y visualizar dichos sistemas. El estudio de las interacciones entre entidades discretas ha surgido en los últimos años como el estudio de las redes complejas. Muchas redes comparten propiedades topológicas similares, como el efecto de mundo pequeño, distribuciones de grado de cola gruesa, coeficientes de agrupamiento elevados y esparcimiento. El marco de la geOmetría de redes se propuso para explicar estas propiedades. En este enfoque, los nodos se sitúan en un espacio latente oculto, donde las coordenadas de cada nodo reflejan su similitud con otros nodos y su popularidad intrínseca, entrelazando así la geometría con la topología de la red. Los modelos de esta familia son capaces de explicar muchas propiedades de las redes reales. Estos modelos de espacio latente replican con precisión las observaciones empíricas al interpretar la probabilidad de conexión como una función decreciente de la distancia hiperbólica. La búsqueda para invertir estos modelos geométricos dio lugar a incrustaciones hiperbólicas basadas en modelos. Al proyectar redes complejas en espacios hiperbólicos de baja dimensión, las operaciones sobre grafos, como la detección de comunidades, la clasificación de nodos y la predicción de enlaces, se convierten en eficientes cálculos vectoriales. Hasta la fecha, sin embargo, estos métodos se han limitado a una sola dimensión, aunque no existe motivo alguno para que así sea. En esta Tesis, desarrollamos tres incrustaciones hiperbólicas multidimensionales: D-Mercator para redes unipartitas, FiD-Mercator para redes enriquecidas con atributos y B-Mercator para redes bipartitas, demostrando que estas incrustaciones mejoran significativamente nuestra comprensión de las estructuras de red. Con D-Mercator, estimamos la dimensionalidad intrínseca de redes reales en términos de navegabilidad y estructura de comunidades. FiD-Mercator destacó la importancia de cuantificar las correlaciones entre las etiquetas de los nodos, la topología del grafo y las características de los nodos para tareas posteriores. Por su parte, B-Mercator reveló patrones de diversidad lingüística y geográfica, y también mejoró la tarea de clasificación de nodos. Además, cerramos la brecha entre la geometría de redes y el aprendizaje automático en grafos al introducir HypBench, un benchmarking para redes neuronales de grafos. HypBench proporcionó orientación concreta para seleccionar el modelo óptimo para conjuntos de datos de grafos específicos. En conjunto, estas contribuciones establecen un marco multidimensional flexible para mapear y analizar redes complejas, ofreciendo nuevas perspectivas y herramientas prácticas para avanzar en la investigación en múltiples disciplinas.
Matèries (anglès)
Citació
Col·leccions
Citació
JANKOWSKI, Robert. Hyperbolic Cartography of Complex Networks. Designing Maps for Unipartite, Bipartite, and Feature-Enriched Graphs. [consulta: 26 de febrer de 2026]. [Disponible a: https://hdl.handle.net/2445/226574]