Time-Varying Hyperbolic Geometric Graphs–TV-HGGs
Project summary: Previously we discovered a powerful and unique geometric framework explaining the ubiquitous common structure of complex networks and linking this structure to the optimality of their common functions. In this framework, network nodes are mapped to points in hyperbolic spaces, which lie beneath the observable topologies. The analysis of complex networks is then simplified significantly, as their discrete complex structure can be studied in purely geometric terms. This framework, known as hyperbolic geometric graphs (HGGs), has attracted a great deal of interest in mathematics, physics, computer science and biology. However, despite several years of research, our knowledge and understanding of network geometry is essentially still limited to static HGGs and methods that can only infer the geometry of network snapshots. But real networks are complex dynamical systems, evolving over time with the addition and deletion of nodes and links, and there currently exists no principled theory that can model and predict their dynamics — a grand-challenge open problem in modern network theory. The main aim of this project was to address this challenge by mapping the general problem of predicting network dynamics to the specific problem of predicting the motion of nodes in their hidden hyperbolic spaces and developing models of time-varying hyperbolic geometric graphs.
Our aims were:
(i) to analyze and capture the motion of nodes in the hyperbolic spaces of real networks using stochastic differential equations;
(ii) to develop sound generative models of time-varying hyperbolic geometric graphs (TV-HGGs), which can explain the dynamical properties of real-world networks; and
(iii) to develop methods able to forecast future connections and disconnections in dynamic networks over different time scales.
Our progress in the various project tasks is described below.
Duration: 2/10/2020-1/10/2023.
Funded by: Cyprus Research & Innovation Foundation.
Budget: €560400.
Project Tasks
Task 1: Extraction of hyperbolic node trajectories from different real networks. We extracted historical popularity-similarity node trajectories in the hyperbolic spaces of different real-world networks, including the US Air transportation network, the Internet, the Bitcoin transaction network, the PGP Web-of-Trust, and the arXiv collaboration network. Details can be found in the paper “Fundamental dynamics of popularity-similarity trajectories in real networks, E. S. Papaefthymiou, C. Iordanou, and F. Papadopoulos, arXiv:2309.01675, September 2023″. A GitHub link to the data and related code will be made available here upon publication of the paper.
Task 2: Find the equations and stochastic processes best describing the trajectories. We have found that the trajectories can be well-described by a fractional Brownian motion model. The model can create synthetic trajectories resembling real ones and used for future trajectory predictions. Further details can be found in “Fundamental dynamics of popularity-similarity trajectories in real networks, E. S. Papaefthymiou, C. Iordanou, F. Papadopoulos, arXiv:2309.01675, September 2023″.
Task 3: Models of time-varying hyperbolic geometric graphs. We have introduced and analyzed models of time-varying hyperbolic geometric graphs with (or without) link persistence. We have found and mathematically proven that the models naturally yield many of the temporal network properties observed in real-world networks, like broad distributions of contact and inter-contact durations. Further details can be found in “Dynamics of cold random hyperbolic graphs with link persistence, S. Zambirinis, H. Hartle, F. Papadopoulos, Physical Review E, Vol. 106, Issue 6, December 2022. (arXiv)”. We have also found that epidemic and other network processes perform similarly in real and modeled temporal networks and applied the models to real-world epidemiological studies, see “Population-wide measures due to the COVID-19 pandemic and exposome changes in the general population of Cyprus in March-May 2020, X. Andrianou, C. Konstantinou, M. A. Rodríguez-Flores, F. Papadopoulos, K. Makris, BMC Public Health, Vol. 22, No. 2279, December 2022. Further, we proved that only TV-HGGs in the cold regime yield realistic temporal network properties, see “Dynamics of hot random hyperbolic graphs, F. Papadopoulos, S. Zambirinis, Physical Review E, Vol. 105, Issue 2, February 2022 (arXiv)”. Finally, a general analysis of hidden variable models (including hyperbolic graphs and the stochastic block model) with time-varying coordinates is performed in “Dynamic Hidden-Variable Network Models, H. Hartle, F. Papadopoulos, and D. Krioukov, Physical Review E, Vol. 103, Issue 5, May 2021 (arXiv)”.
Task 4: Prediction of connectivity dynamics in real-world networks. We have verified that the evolution of hyperbolic distances among nodes is correlated with connectivity dynamics in real-world networks. Thus predicting hyperbolic distance evolution can yield predictions about connectivity dynamics. Future work consists of exploring this idea to facilitate connectivity predictions over different time-scales.
Other related publications can be found at the end of this page.
The team
(Coordinator)
Fragkiskos Papadopoulos is an Associate Professor of the Department of Electrical Engineering, Computer Engineering and Informatics at Cyprus University of Technology. He was previously an Assistant Professor (2015-2020) and a Lecturer (2011-2015) at the same department. He received the Diploma in Electrical and Computer Engineering from the National Technical University of Athens in 2002. In 2004 and 2007 he received respectively the MSc and PhD degrees in Electrical Engineering from the University of Southern California, Los Angeles. During 2007-2009 he was a postdoctoral researcher at the Center for Applied Internet Data Analysis (CAIDA) at the University of California, San Diego. He was also a visiting Lecturer at the department of Electrical and Computer Engineering of the University of Cyprus (2009-2010). His research focuses on the theory and foundations of complex networks and their real-world applications. Topics of interest include: network geometry, network navigation, statistical inference and hyperbolic network embedding, dynamics prediction, multiplex networks, temporal networks, and performance analysis of communication networks. His research has been published in major peer reviewed international scientific journals, including Nature, Nature Physics, Nature Communications, and Physical Review Letters. He is a co-director of the NetSySci Research Laboratory.
(Postdoctoral Researcher)
Dr. Marco Antonio Rodriguez Flores has completed his doctoral degree in December of 2020 under the direction of Prof. Fragkiskos Papadopoulos at Cyprus University of Technology. His research interests lie in the field of complex networks, including: human proximity networks, network geometry and network dynamics.
(Jan. 2021 – Apr. 2022)
(Postdoctoral Researcher)
Dr. Sofoclis Zambirinis has a BSc in Mathematics (University of Athens, GPA 9.4/10, academically ranked in the top 1% of his graduating class), an MPhil in Statistical Science (University of Cambridge), and a PhD in Management Science (Lancaster University), with specialization in optimization in vehicle routing and scheduling. During his doctoral studies, his research interests included the following: mathematical programming, combinatorial optimization, multi-objective optimization, metaheuristic algorithms, vehicle routing and scheduling problems, transportation systems, and disruption management. His current research lies in the field of complex networks, focusing on time-varying hyperbolic geometric graphs, temporal networks, and network geometry.
(Feb. 2021 – Sep. 2023)
(Postdoctoral Researcher)
Costas Iordanou has a BSc. in Computer Engineering and Informatics (2013) from Cyprus University of Technology and MSc in Computer Engineering and Informatics (2014) from the same university. In 2015 he also received a second MSc. in Telematic Engineering from Universidad Carlos III de Madrid. In 2019 he receive his PhD (-Dr. -Ing.) from the Technische Universität Berlin. As part of his PhD studies, he worked on the design and implementation of multiple crowdsourced web-based distributed systems that aim to help internet users to understand how their personal data are collected and used on the internet.
(Mar. 2021 – Sep. 2023)
Evangelos Papaefthymiou holds a PhD in Applied Mathematics from the Department of Mathematics of Imperial College London (2014). His PhD work led to publications in top journals in the field of Applied Mathematics and he was awarded the Yael Naim Dowker Centenary Prize in Mathematics for the best thesis in the Department of Mathematics. Furthermore, he holds a Meng degree (5-years of studies, 2002-2007) from the Department of Mechanical and Aeronautical Engineering Department of the University of Patras.
(Jun. 2022 – Sep. 2023)
Publications
- (ω1, ω2)-Temporal random hyperbolic graphs, Sofoclis Zambirinis and Fragkiskos Papadopoulos, arXiv:2403.17440, March 2024.
- Fundamental dynamics of popularity-similarity trajectories in real networks, Evangelos S. Papaefthymiou, Costas Iordanou, and Fragkiskos Papadopoulos, arXiv:2309.01675, September 2023. (Data & Code)
- Dynamics of cold random hyperbolic graphs with link persistence, Sofoclis Zambirinis, Harrison Hartle, and Fragkiskos Papadopoulos, Physical Review E, Vol. 106, Issue 6, December 2022. (arXiv)
- Population-wide measures due to the COVID-19 pandemic and exposome changes in the general population of Cyprus in March-May 2020, Xanthi Andrianou, Corina Konstantinou, Marco A. Rodríguez-Flores, Fragkiskos Papadopoulos, and Konstantinos Makris, BMC Public Health, Vol. 22, No. 2279, December 2022. (Code implementing the dynamic SEIR model)
- Topology and Geometry of the Third-Party Domains Ecosystem: Measurement and Applications, Costas Iordanou and Fragkiskos Papadopoulos, ACM SIGCOMM Computer Communication Review (CCR), Vol. 52, Issue 4, October 2022. (arXiv – Data & Code)
- Dynamics of hot random hyperbolic graphs, Fragkiskos Papadopoulos and Sofoclis Zambirinis, Physical Review E, Vol. 105, Issue 2, February 2022. (arXiv)
- Dynamic Hidden-Variable Network Models, Harrison Hartle, Fragkiskos Papadopoulos, and Dmitri Krioukov, Physical Review E, Vol. 103, Issue 5, May 2021. (arXiv)
- Hyperbolic Mapping of Human Proximity Networks, Marco A. Rodríguez-Flores and Fragkiskos Papadopoulos, Scientific Reports, Vol. 10, No. 20244, November 2020.
