Element contents
The Shortest Path to Network Geometry
A Practical Guide to Basic Models and Applications
Published online by Cambridge University Press: 02 December 2021
Summary
Real networks comprise from hundreds to millions of interacting elements and permeate all contexts, from technology to biology to society. All of them display non-trivial connectivity patterns, including the small-world phenomenon, making nodes to be separated by a small number of intermediate links. As a consequence, networks present an apparent lack of metric structure and are difficult to map. Yet, many networks have a hidden geometry that enables meaningful maps in the two-dimensional hyperbolic plane. The discovery of such hidden geometry and the understanding of its role have become fundamental questions in network science giving rise to the field of network geometry. This Element reviews fundamental models and methods for the geometric description of real networks with a focus on applications of real network maps, including decentralized routing protocols, geometric community detection, and the self-similar multiscale unfolding of networks by geometric renormalization.
- Type
- Element
- Information
- Online ISBN: 9781108865791Publisher: Cambridge University PressPrint publication: 06 January 2022
References
Abou-Rjeili, A. , & Karypis, G. (2006). Multilevel algorithms for partitioning power-law graphs. In Proceedings 20th IEEE International Parallel & Distributed Processing Symposium. doi: 10.1109/IPDPS.2006.1639360.CrossRefGoogle Scholar
Alanis-Lobato, G., Mier, P., & Andrade-Navarro, M. A. (2016a). Efficient embedding of complex networks to hyperbolic space via their Laplacian. Sci. Rep., 6, 30108.CrossRefGoogle ScholarPubMed
Alanis-Lobato, G., Mier, P., & Andrade-Navarro, M. A. (2016b, Nov. 15). Manifold learning and maximum likelihood estimation for hyperbolic network embedding. Applied Network Science, 1(1), 10. doi: https://doi.org/10.1007/s41109-016-0013-0Google Scholar
Allard, A., & Serrano, M. Á. (2020). Navigable maps of structural brain networks across species. PLOS Computational Biology, 16(2), e1007584.CrossRefGoogle ScholarPubMed
Allard, A., Serrano, M. Á., García-Pérez, G., & Boguñá, M. (2017). The geometric nature of weights in real complex networks. Nat. Commun., 8, 14103.Google Scholar
Alvarez-Hamelin, J. I., Dall’Asta, L., Barrat, A., & Vespignani, A. (2008). K-core decomposition of internet graphs: hierarchies, selfsimilarity and measurement biases. Networks and Heterogeneous Media, 3(2), 371–393.Google Scholar
Amaral, L. A. N. (2008). A truer measure of our ignorance. Proc. Natl. Acad. Sci. USA, 105(19), 6795–6796.Google Scholar
Amaral, L. A. N., Scala, A., Barthélemy, M., & Stanley, H. E. (2000). Classes of small-world networks. Proc. Natl. Acad. Sci. USA, 97(21), 11149–11152.CrossRefGoogle ScholarPubMed
Barabási, A. L., & Albert, R. (1999). Emergence of scaling in random networks. Science, 286(5439), 509–512.Google Scholar
Barrat, A., Barthélemy, M., Pastor-Satorras, R., & Vespignani, A. (2004). The architecture of complex weighted networks. Proc. Natl. Acad. Sci. USA, 101(11), 3747–3752.Google Scholar
Barrat, A., Barthélemy, M., & Vespignani, A. (2008). Dynamical processes on complex networks. Cambridge: Cambridge University Press.Google Scholar
Bianconi, G. (2018). Multilayer networks: structure and function. Oxford: Oxford University Press.Google Scholar
Blasius, T., Friedrich, T., Krohmer, A. et al. (2018, Apr.). Efficient embedding of scale-free graphs in the hyperbolic plane. IEEE/ACM Trans. Netw., 26(2), 920–933. doi: https://doi.org/10.1109/TNET.2018.2810186Google Scholar
Blondel, V. D., Guillaume, J.-L., Lambiotte, R., & Lefebvre, É. (2008). Fast unfolding of communities in large networks. J. Stat. Mech., 2008(10), P10008.Google Scholar
Boettcher, S., & Brunson, C. (2011). Renormalization group for critical phenomena in complex networks. Frontiers in Physiology, 2, 102. doi: https://doi.org/10.3389/fphys.2011.00102Google Scholar
Boguñá, M., Bonamassa, I., Domenico, M. D. et al. (2020). Network geometry. Nat Rev Phys 3, 114–135. https://doi.org/10.1038/s42254-020-00264-4CrossRefGoogle Scholar
Boguñá, M., & Krioukov, D. (2009). Navigating ultrasmall worlds in ultrashort time. Phys. Rev. Lett., 102(058701). (arXiv:0809.2995v1)CrossRefGoogle Scholar
Boguñá, M., Krioukov, D., Almagro, P., & Serrano, M. Á. (2020, Apr.). Small worlds and clustering in spatial networks. Phys. Rev. Research, 2, 023040. doi: https://doi.org/10.1103/PhysRevResearch.2.023040Google Scholar
Boguñá, M., Krioukov, D. , & Claffy, K. (2009). Navigability of complex networks. Nat. Phys., 5(1), 74–80.Google Scholar
Boguñá, M., Papadopoulos, F., & Krioukov, D. (2010). Sustaining the Internet with hyperbolic mapping. Nat. Commun., 1, 62. doi: https://doi.org/10.1038/ncomms1063CrossRefGoogle ScholarPubMed
Boguñá, M., Pastor-Satorras, R., & Vespignani, A. (2004). Cut-offs and finite size effects in scale-free networks. Eur. Phys. J. B, 38(2), 205–209.Google Scholar
Bringmann, K., Keusch, R., Lengler, J., Maus, Y., & Molla, A. R. (2017). Greedy routing and the algorithmic small-world phenomenon. In PODC ’17: Proceedings of the ACM Symposium on Principles of Distributed Computing. doi: https://doi.org/10.1145/3087801.3087829Google Scholar
Caldarelli, G., Capocci, A., De Los Rios, P., & Muñoz, M. A. (2002, December). Scale-free networks from varying vertex intrinsic fitness. Phys. Rev. Lett., 89(25), 258702. doi: https://doi.org/10.1103/PhysRevLett.89.258702Google Scholar
Claffy, K., Hyun, Y., Keys, K., Fomenkov, M., & Krioukov, D. (2009). Internet mapping: From art to science. In 2009 Cybersecurity Applications Technology Conference for Homeland Security (pp. 205–211). New York: IEEE. doi: https://doi.org/10.1109/CATCH.2009.38CrossRefGoogle Scholar
Cohen, R., & Havlin, S. (2003). Scale-free networks are ultrasmall. Phys. Rev. Lett., 90(5), 058701.Google Scholar
Colizza, V., Pastor-Satorras, R. , & Vespignani, A. (2007). Reaction-diffusion processes and metapopulation models in heterogeneous networks. Nat. Phys., 3, 276–282.CrossRefGoogle Scholar
Dall, J., & Christensen, M. (2002). Random geometric graphs. Phys. Rev. E, 66(1), 016121. doi: https://doi.org/10.1103/PhysRevE.66.016121Google Scholar
Dorogovtsev, S. N., & Mendes, J. F. F. (2003). Evolution of networks: From biological nets to the Internet and WWW. Oxford: Oxford University Press.Google Scholar
Dorogovtsev, S. N., Mendes, J. F. F., & Samukhin, A. N. (2001). A. size-dependent degree distribution of a scale-free growing network. Phys. Rev. E, 63(6), 062101.CrossRefGoogle ScholarPubMed
D’Souza, R., Borgs, C., Chayes, J., Berger, N., & Kleinberg, R. (2007). Emergence of tempered preferential attachment from optimization. PNAS, 104(15), 6112–6117.Google Scholar
Fortunato, S., Flammini, A., & Menczer, F. (2006). Scale-free network growth by ranking. Phys. Rev. Lett., 96(21), 218701.CrossRefGoogle ScholarPubMed
García-Pérez, G., Allard, A., Serrano, M. Á., & Boguñá, M. (2019, Dec.). Mercator: uncovering faithful hyperbolic embeddings of complex networks. New Journal of Physics, 21(12), 123033. doi: https://doi.org/10.1088%2F1367-2630%2Fab57d2Google Scholar
García-Pérez, G., Boguñá, M., Allard, A., & Serrano, M. Á. (2016, Sept.). The hidden hyperbolic geometry of international trade: World Trade Atlas 1870–2013. Sci. Rep., 6, 33441. doi: https://doi.org/10.1038/srep33441Google Scholar
García-Pérez, G., Boguñá, M., & Serrano, M. Á. (2018). Multiscale unfolding of real networks by geometric renormalization. Nat. Phys., 14(6), 583–589. doi: https://doi.org/10.1038/s41567-018-0072-5CrossRefGoogle Scholar
García-Pérez, G., Serrano, M. Á., & Boguñá, M. (2018). Soft communities in similarity space. J. Stat. Phys., 173(3–4), 775–782. doi: https://doi.org/10.1007/s10955-018-2084-zCrossRefGoogle Scholar
Goh, K. I., Salvi, G., Kahng, B., & Kim, D. (2006). Skeleton and fractal scaling in complex networks. Phys. Rev. Lett., 96, 018701.Google Scholar
Guimerà, R., Mossa, S., Turtschi, A., & Amaral, L. A. N. (2005). The worldwide air transportation network: Anomalous centrality, community structure, and cities. Proc. Natl. Acad. Sci. USAs, 10(22), 7794–7799.Google Scholar
Gulyás, A., Bíró, J. J., Kőrösi, A., Rétvári, G., & Krioukov, D. (2015). Navigable networks as Nash equilibria of navigation games. Nat. Commun., 6(1), 7651. doi: https://doi.org/10.1038/ncomms8651CrossRefGoogle ScholarPubMed
Kadanoff, Leo P. (2000). Statistical physics: Statics, dynamics and renormalization. Singapore: World Scientific.CrossRefGoogle Scholar
Karypis, G., & Kumar, V. (1999). A fast and highly quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 20(1), 359–392.Google Scholar
Kim, J. S., Goh, K. I., Hahng, B., & Kim, D. (2007). Fractality and self-similarity in scale-free networks. New J. Phys., 9, 177.Google Scholar
Kleineberg, K.-K., Boguñá, M., Serrano, M. Á., & Papadopoulos, F. (2016). Hidden geometric correlations in real multiplex networks. Nat. Phys., 12(11), 1076–1081.Google Scholar
Kleineberg, K.-K., Buzna, L., Papadopoulos, F., Boguñá, M., & Serrano, M. Á. (2017). Geometric correlations mitigate the extreme vulnerability of multiplex networks against targeted attacks. Phys. Rev. Lett., 118, 218301.Google Scholar
Klimt, B., & Yang, Y. (2004). Introducing the Enron Corpus. In CEAS 2004 – First Conference on Email and Anti-Spam, July 30–31, 2004, Mountain View, CA. Accessed at http://dblp.uni-trier.de/db/conf/ceas/ceas2004.html#KlimtY04Google Scholar
Korman, A., & Peleg, D. (2006). Dynamic routing schemes for general graphs. In Bugliesi, M., Preneel, B., Sassone, V., & Wegener, I. (eds.), ICALP: Proceedings of Int. Colloquium on Automata, Languages and Programming (vol. 4051, pp. 619–630). Springer. doi: https://doi.org/10.1007/11786986_54Google Scholar
Krioukov, D., Kitsak, M., Sinkovits, et al. (2012). Network cosmology. Sci. Rep., 2. Accessed at doi: https://doi.org/10.1038/srep00793Google Scholar
Krioukov, D., Papadopoulos, F., Kitsak, M., Vahdat, A., & Boguñá, M. (2010). Hyperbolic geometry of complex networks. Phys. Rev. E, 82(3), 036106.Google Scholar
Krioukov, D., Papadopoulos, F., Vahdat, A., & Boguñá, M. (2009, Sep.). Curvature and temperature of complex networks. Phys. Rev. E, 80(3), 035101. Accessed at http://link.aps.org/doi/10.1103/PhysRevE.80.035101 doi: https://doi.org/10.1103/PhysRevE.80.035101Google Scholar
Kunegis, J. (2013). KONECT – The Koblenz Network Collection. In Proceedings of the International Conference on World Wide Web Companion (pp. 1343–1350). Accessed at http://konect.cc/Google Scholar
Leskovec, J., Lang, K. J., Dasgupta, A., & Mahoney, M. W. (2009). Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics, 6(1), 29–123. doi: https:http://doi.org/10.1080/15427951.2009.10129177CrossRefGoogle Scholar
Maldacena, J. (1998). The large N limit of superconformal field theories and supergravity. Adv. Theor. Math. Phys., 2(2), 231–252. doi: https://doi.org/10.4310/ATMP.1998.v2.n2.a1Google Scholar
Mandelbrot, B. (1961). On the theory of word frequencies and on related Markovian models of discourse. In Proceedings of the Twelve Symposia in Applied Mathematics, Roman Jakobson Editor. Structure of Language and Its Mathematical Aspects, New York, USA (pp. 190–219). Providence, RI: American Mathematical Society.Google Scholar
Milo, R., Itzkovitz, S., Kashtan, N. et al. (2004, March). Superfamilies of evolved and designed networks. Science, 303(5663), 1538–1542.CrossRefGoogle ScholarPubMed
Min, B., Yi, S. D., Lee, K.-M., & Goh, K.-I. (2014). Network robustness of multiplex networks with interlayer degree correlations. Phys. Rev. E, 89(4), 042811.Google Scholar
Muscoloni, A., & Cannistraci, C. V. (2018). A nonuniform popularity-similarity optimization (nPSO) model to efficiently generate realistic complex networks with communities. New J. Phys., 20(5), 052002. doi: https://doi.org/10.1088/1367-2630/aac06fGoogle Scholar
Muscoloni, A., & Cannistraci, C. V. (2019). Navigability evaluation of complex networks by greedy routing efficiency. Proc. Natl. Acad. Sci., 116(5), 1468–1469. doi: https://doi.org/10.1073/pnas.1817880116Google Scholar
Muscoloni, A., Thomas, J. M., Ciucci, S., Bianconi, G., & Cannistraci, C. V. (2017). Machine learning meets complex networks via coalescent embedding in the hyperbolic space. Nature Communications, 8(1), 1615. https://doi.org/10.1038/s41467-017-01825-5Google Scholar
Newman, M., & Watts, D. (1999). Renormalization group analysis of the small-world network model. Physics Letters A, 263(4–6), 341–346. Accessed at www.sciencedirect.com/science/article/pii/S0375960199007574 doi: https://doi.org/10.1016/S0375-9601(99)00757-4Google Scholar
Newman, M. E. J. (2010). Networks: An introduction. Oxford: Oxford University Press.CrossRefGoogle Scholar
Newman, M. E. J., & Girvan, M. (2004, Feb.). Finding and evaluating community structure in networks. Phys. Rev. E, 69(2), 026113. doi: https://doi.org/10.1103/PhysRevE.69.026113Google Scholar
Nicosia, V., & Latora, V. (2015). Measuring and modeling correlations in multiplex networks. Phys. Rev. E, 92, 032805.Google Scholar
Openflights network dataset – KONECT. (2016, Sept.). Accessed at http://konect.uni-koblenz.de/networks/openflightsGoogle Scholar
Ortiz, E., Starnini, M., & Serrano, M. Á. (2017). Navigability of temporal networks in hyperbolic space. Sci. Rep., 7, 15054.Google Scholar
Papadopoulos, F., Aldecoa, R., & Krioukov, D. (2015, Aug.). Network geometry inference using common neighbors. Phys. Rev. E, 92(2). 022807. doi: https://doi.org/10.1103/PhysRevE.92.022807CrossRefGoogle ScholarPubMed
Papadopoulos, F., Kitsak, M., Serrano, M. Á., Boguñá, M., & Krioukov, D. (2012). Popularity versus similarity in growing networks. Nature, 489(7417), 537–540. doi: https://doi.org/10.1038/nature11459Google Scholar
Papadopoulos, F., Krioukov, D., Boguñá, M., & Vahdat, A. (2010). Greedy forwarding in dynamic scale-free networks embedded in hyperbolic metric spaces. In 2010 Proceedings IEEE Infocom (pp. 1–9).Google Scholar
Papadopoulos, F., Psomas, C., & Krioukov, D. (2015). Network mapping by replaying hyperbolic growth. IEEE/ACM Trans. Netw., 23(1), 198–211. doi: https://doi.org/10.1109/TNET.2013.2294052Google Scholar
Papadopoulos, F., & Psounis, K. (2007, Oct.). Efficient identification of uncongested internet links for topology downscaling. SIG-COMM Comput. Commun. Rev., 37(5), 39–52. doi: https://doi.org/10.1145/1290168.1290173Google Scholar
Papadopoulos, F., Psounis, K., & Govindan, R. (2006, Dec.). Performance preserving topological downscaling of internet-like networks. IEEE Journal on Selected Areas in Communications, 24(12), 2313–2326. doi: https://doi.org/10.1109/JSAC.2006.884029Google Scholar
Pastor-Satorras, R., Smith, E., & Sole, R. V. (2003). Evolving protein interaction networks through gene duplication. J. Theor. Biol., 222(2), 199–210.Google Scholar
Radicchi, F., Ramasco, J. J., Barrat, A., & Fortunato, S. (2008, Oct.). Complex networks renormalization: Flows and fixed points. Phys. Rev. Lett., 101(14), 148701. doi: https://doi.org/10.1103/PhysRevLett.101.148701Google Scholar
Rolland, T., Taşan, M., Charloteaux, B. et al. (2014). A proteome-scale map of the human interactome network. Cell, 159(5), 1212–1226. Accessed at www.sciencedirect.com/science/article/pii/S0092867414014226 doi: https://doi.org/10.1016/j.cell.2014.10.050Google Scholar
Rozenfeld, H. D., Song, C., & Makse, H. A. (2010, Jan.). Small-world to fractal transition in complex networks: A renormalization group approach. Phys. Rev. Lett., 104(2), 025701. doi: https://doi.org/10.1103/PhysRevLett.104.025701.Google Scholar
Sarveniazi, A. (2014). An actual survey of dimensionality reduction. American Journal of Computational Mathematics, 4(2), 55–72.Google Scholar
Serrà, J., Corral, A., Boguñá, M., Haro, M., & Arcos, J. L. (2012). Measuring the evolution of contemporary western popular music. Sci. Rep., 2. Accessed at www.nature.com/srep/2012/120726/srep00521/full/srep00521.html doi: https://doi.org/10.1038/srep00521Google Scholar
Serrano, M. Á., Boguñá, M., & Sagues, F. (2012). Uncovering the hidden geometry behind metabolic networks. Mol. BioSyst., 8(3), 843–850. doi: https://doi.org/10.1039/C2MB05306CCrossRefGoogle ScholarPubMed
Serrano, M. Á., Buzna, L., & Boguñá, M. (2015). Escaping the avalanche collapse in self-similar multiplexes. New J. Phys., 17, 053033.Google Scholar
Serrano, M. Á., Krioukov, D., & Boguñá, M. (2008). Self-similarity of complex networks and hidden metric spaces. Phys. Rev. Lett., 100(7), 078701.Google ScholarPubMed
Serrano, M. Á., Krioukov, D., & Boguñá, M. (2011, Jan.). Percolation in self-similar networks. Phys. Rev. Lett., 106(4), 048701. doi: https://doi.org/10.1103/PhysRevLett.106.048701Google Scholar
Song, C., Havlin, S., & Makse, H. A. (2005). Self-similarity of complex networks. Nature, 433(7024), 392–395.CrossRefGoogle ScholarPubMed
Song, C., Havlin, S., & Makse, H. A. (2006). Origins of fractality in the growth of complex networks. Nat. Phys., 2(4), 275–281.CrossRefGoogle Scholar
Stanley, H. E. (1971). Introduction to phase transitions and critical phenomena. Oxford: Oxford University Press.Google Scholar
Starnini, M., Ortiz, E., & Serrano, M. Á. (2019). Geometric randomization of real networks with prescribed degree sequence. New J. Phys., 21(5s), 053039.Google Scholar
Takemura, S.-y., Bharioke, A., Lu, Z. et al. (2013). A visual motion detection circuit suggested by drosophila connectomics. Nature, 500(7461), 175–181.Google Scholar
Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of “small-world” networks. Nature, 393(6684), 440–442.Google Scholar
Wilson, K. G. (1975). The renormalization group: Critical phenomena and the kondo problem. Rev. Mod. Phys., 47(4), 773–840.Google Scholar
Wilson, K. G. (1983, Jul.). The renormalization group and critical phenomena. Rev. Mod. Phys., 55(3), 583–600. doi: https://doi.org/10.1103/RevModPhys.55.583Google Scholar
Yao, W. M., & Fahmy, S. (2008, Apr.). Downscaling network scenarios with Denial of Service (DoS) attacks. In 2008 IEEE Sarnoff Symposium (pp. 1–6). doi: https://doi.org/10.1109/SARNOF.2008.4520099Google Scholar
Yao, W. M., & Fahmy, S. (2011, June). Partitioning network testbed experiments. In 2011 31st International Conference on Distributed Computing Systems (pp. 299–309). doi: https://doi.org/10.1109/ICDCS.2011.22CrossRefGoogle Scholar
Zheng, M., Allard, A., Hagmann, P., Alemán-Gómez, Y., & Serrano, M. Á. (2020). Geometric renormalization unravels self-similarity of the multiscale human connectome. Proc. Natl. Acad. Sci., 117(33), 20244–20253. doi: https://doi.org/10.1073/pnas.1922248117Google Scholar
Zheng, M., García-Pérez, G., Boguñá, & M., Serrano, M. Á. (2021). Scaling-up real networks by geometric branching growth. Proc. Natl. Acad. Sci., 118(21), e2018994118. doi: https://doi.org/10.1073/pnas.2018994118Google Scholar
Zuev, K., Boguñá, M., Bianconi, G., & Krioukov, D. (2015). Emergence of soft communities from geometric preferential attachment. Sci. Rep., 5, 9421. doi: https://doi.org/10.1038/srep09421Google Scholar
- 13
- Cited by