Network Mapping by Replaying Hyperbolic Growth
Open accessThe DOI matches its Crossref record; 27 of the 27 references it cites were found in a registry or an index.
Abstract
Recent years have shown a promising progress in understanding geometric underpinnings behind the structure, function, and dynamics of many complex networks in nature and society. However, these promises cannot be readily fulfilled and lead to important practical applications, without a simple, reliable, and fast network mapping method to infer the latent geometric coordinates of nodes in a real network. Here, we present HyperMap, a simple method to map a given real network to its hyperbolic space. The method utilizes a recent geometric theory of complex networks modeled as random geometric graphs in hyperbolic spaces. The method replays the network's geometric growth, estimating at each time-step the hyperbolic coordinates of new nodes in a growing network by maximizing the likelihood of the network snapshot in the model. We apply HyperMap to the Autonomous Systems (AS) Internet and find that: 1) the method produces meaningful results, identifying soft communities of ASs belonging to the same geographic region; 2) the method has a remarkable predictive power: Using the resulting map, we can predict missing links in the Internet with high precision, outperforming popular existing methods; and 3) the resulting map is highly navigable, meaning that a vast majority of greedy geometric routing paths are successful and low-stretch. Even though the method is not without limitations, and is open for improvement, it occupies a unique attractive position in the space of tradeoffs between simplicity, accuracy, and computational complexity.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(2021) · A First Course in Statistical Programming with R · doi:10.1017/9781108993456.011 · Cited by 13,724
(1999) · Springer Series in Operations Research and Financial Engineering · doi:10.1007/b98874 · Cited by 9,482
Monte Carlo Methods in Statistical Physics
Newman, M. E. J., & Barkema, G. T. (1999) · doi:10.1093/oso/9780198517962.001.0001 · Cited by 3,165
Prediction, Learning, and Games
Cesa-Bianchi, N., & Lugosi, G. (2006) · Cambridge University Press eBooks · doi:10.1017/cbo9780511546921 · Cited by 3,162 · cited 1×
“…which is the probability that there is a link between a pair of mapped nodes located at hyperbolic distance , is to the theoretical prediction, i.e., the global connection probability in (10); and 2) the Logarithmic Loss, , a standard metric to evaluate maximum-likelihood inference methods [21].”
BackgroundThe link‐prediction problem for social networks
Liben‐Nowell, D., & Kleinberg, J. (2007) · Journal of the American Society for Information Science and Technology · doi:10.1002/asi.20591 · Cited by 3,043
Link prediction in complex networks: A survey
Lü, L., & Zhou, T. (2011) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2010.11.027 · Cited by 2,819 · cited 21×
“Finally, HyperMap performs significantly better than HRG, while the AUC of HRG for node pairs with no common neighbors is only 0.53.”
BackgroundMethodResultInfluentialPenrose, M. (2003) · doi:10.1093/acprof:oso/9780198506263.001.0001 · Cited by 2,480
Hierarchical structure and the prediction of missing links in networks
Clauset, A., Moore, C., & Newman, M. E. J. (2008) · Nature · doi:10.1038/nature06830 · Cited by 2,171 · cited 5×
“To provide a deeper insight on the HyperMap performance in predicting missing links, we also consider a set of classi cal link prediction methods that have been found to perform well in practice in different studies [7], [8], and compare their performance to HyperMap’s.”
BackgroundMethodResultInfluentialMetric Structures for Riemannian and Non-Riemannian Spaces
(2007) · Modern Birkhäuser Classics · doi:10.1007/978-0-8176-4583-0 · Cited by 1,694 · cited 1×
“The high-level explanation of this conne ction is that complex networks exhibit hierarchical, tree-l ike organization, while hyperbolic geometry is the geometry of trees [11].”
BackgroundDorogovtsev, S. N., & Mendes, J. F. F. (2003) · doi:10.1093/acprof:oso/9780198515906.001.0001 · Cited by 1,563
Hyperbolic geometry of complex networks
Krioukov, D., Papadopoulos, F., Kitsak, M., Vahdat, A., & Boguñá, M. (2010) · Physical Review E · doi:10.1103/physreve.82.036106 · Cited by 1,059 · cited 4×
“In [14], we have focused on greedy routing and showed how the AS Internet topology can be embedded into the hyperbolic planebymaximizing thelikelihoodthat the topology isproduced by the model of static complex networks from [9].”
BackgroundMethodInfluentialSelf-citationHandbook of Graphs and Networks: From the Genome to the Internet
(2002) · Wiley eBooks · doi:10.1002/3527602755 · Cited by 949 · cited 1×
“1 A particular goal is to understand how these characteristics affect the various processes tha t run on top of these networks, such as routing, information shari ng, data distribution, searching, and epidemics [2], [3], [5].”
BackgroundPopularity versus similarity in growing networks
Papadopoulos, F., Kitsak, M., Serrano, M. Á., Boguñá, M., & Krioukov, D. (2012) · Nature · doi:10.1038/nature11459 · Cited by 634 · cited 10×
“It has been shown that the generalized PSO model can reproduce not only the degree distribution and clustering of different real networks, but also several other important properties [12].”
BackgroundMethodInfluentialSelf-citationLink Prediction via Matrix Factorization
Menon, A. K., & Elkan, C. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-23783-6_28 · Cited by 520 · cited 1×
“Understanding the mechanisms that shape the structure and drive t he evolution of real networks can also have important applicat ions in designing more efficient recommender and collaborative filtering systems [6], and for predicting missing and future links—an important problem in many disciplines [7], [8].”
BackgroundNavigability of complex networks
Boguñá, M., Krioukov, D., & Claffy, K. C. (2009) · Nature Physics · doi:10.1038/nphys1130 · Cited by 486 · cited 3×
“To evaluate the efficiency of GR, one usually uses two metrics [13]: 1) the percentage of successful paths, , which is the proportion of paths that reach their destinations; and 2) the average hop-length of the successful paths.”
BackgroundMethodSelf-citationSustaining the Internet with hyperbolic mapping
Boguñá, M., Papadopoulos, F., & Krioukov, D. (2010) · Nature Communications · doi:10.1038/ncomms1063 · Cited by 463
Self-citationSelf-Similarity of Complex Networks and Hidden Metric Spaces
Serrano, M. Á., Krioukov, D., & Boguñá, M. (2008) · Physical Review Letters · doi:10.1103/physrevlett.100.078701 · Cited by 332 · cited 1×
“These spaces, which we call hidden metric spaces[27], impose certain bounds on the hidden distances and connection probabilities between nod es, in particular between disconnected nodes, explaining why C N or Katz perform well.”
BackgroundSelf-citationEvolution of Networks: From Biological Nets to the Internet and WWWPreprint
Dorogovtsev, S. N., & Mendes, J. F. F. (2003) · RePEc: Research Papers in Economics · Cited by 330
Dorogovtsev, S. (2010) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199548927.001.0001 · Cited by 313 · cited 4×
“1 A particular goal is to understand how these characteristics affect the various processes that run on top of these networks, such as routing, information sharing, data distribution, searching, and epidemics [2], [3], [5].”
BackgroundInfluentialAS relationships: inference and validation
Dimitropoulos, X., Krioukov, D., Fomenkov, M., Huffaker, B., Hyun, Y., claffy, K., & Riley, G. (2007) · ACM SIGCOMM Computer Communication Review · doi:10.1145/1198255.1198259 · Cited by 305 · cited 1×
“The AS-to-country mapping is taken from the CAIDA AS ranking project [22].”
MethodSelf-citationSampling biases in IP topology measurements
Lakhina, A., Byers, J. W., Crovella, M., & Xie, P. (2004) · IEEE INFOCOM 2003. Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE Cat. No.03CH37428) · doi:10.1109/infcom.2003.1208685 · Cited by 303 · cited 1×
“Topology measurements of many real networks, not only of the Internet [24], may miss some links.”
BackgroundEvolution of Networks: From Biological Nets to the Internet and WWW (Physics)
Dorogovtsev, S. N., & Mendes, J. F. F. (2003) · Oxford University Press eBooks · Cited by 190
Internet Mapping: From Art to Science
Claffy, K., Hyun, Y., Keys, K., Fomenkov, M., & Krioukov, D. (2009) · 2009 Cybersecurity Applications & Technology Conference for Homeland Security · doi:10.1109/catch.2009.38 · Cited by 141
Self-citationHyperbolic Embedding of Internet Graph for Distance Estimation and Overlay Construction
Shavitt, Y., & Tankel, T. (2008) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2007.899021 · Cited by 123
Network science: theory and practice
(2010) · Choice Reviews Online · doi:10.5860/choice.47-4464 · Cited by 86 · cited 1×
“However, these promises cannot be readily ful.lledand lead to important practical applications, without a simple,reliable, and fast network mapping method to infer the latent geometric coordinates of nodes in a real network.”
BackgroundBonahon, F. (2009) · Student mathematical library · doi:10.1090/stml/049 · Cited by 53 · cited 1×
“…of edges: node connects to each existing node with different probability given by (1) In the last expression, is the hyperbolic distance be-tween nodes and [15] where while is derived from the condition that the expected number of nodes to which connects is indeed , yielding [12] (2) where .”
BackgroundReplaying the geometric growth of complex networks and application to the AS internet
Papadopoulos, F., Psomas, C., & Krioukov, D. (2012) · ACM SIGMETRICS Performance Evaluation Review · doi:10.1145/2425248.2425277 · Cited by 10
Self-citation
Metadata
- Authors
- Papadopoulos, F., Psomas, C., & Krioukov, D.
- Venue
- IEEE/ACM Transactions on Networking
- Published
- 2015-02
- Volume
- 23
- Issue
- 1
- Pages
- 198-211
- ISSN
- 1063-6692 (ISSN-L)
- 1558-2566
- OpenAlex
- W1982803213
- Cited by
- 158
- References
- 27
- FWCI
- 9.01
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.