Spatially Embedded Networks IV124 Josef Spurný & Eva Výtvarová Faculty of Informatics, Masaryk University May 12, 2023 Outline Outline temporal networks demo miscellaneous metrics spatially embedded networks J. Spurný, E. Výtvarová ·Spatially Embedded Networks ·May 12, 2023 2 / 26 Temporal Networks Demo Temporal Networks Demo... J. Spurný, E. Výtvarová ·Spatially Embedded Networks ·May 12, 2023 3 / 26 Miscellaneous Metrics Graph Spectral Analysis Derived from Laplacian matrix Q: Q = ∆ − A ∆ ...degree matrix (the diagonal matrix with the nodal degrees) A ...adjacency matrix can be written in terms of their eigenvectors and corresponding eigenvalues, Q = XΛXT X ...eigenvectors in columns Λ ...diagonal matrix with corresponding eigenvalues X and Λ contain the spectral information the spectrum of a graph regarded as a fingerprint eigenvalues in Λ ...precise information about network properties can be used to classify network topologies. J. Spurný, E. Výtvarová ·Spatially Embedded Networks ·May 12, 2023 4 / 26 Miscellaneous Metrics Graph Spectral Analysis Algebraic connectivity (Fiedler eigenvalue) measures how difficult it is to tear a network apart (how well connected the overall graph is) measure for network robustness and synchronizability if the network is connected, the algebraic connectivity is greater than 0 is equal to the second-smallest eigenvalue of the Laplacian matrix J. Spurný, E. Výtvarová ·Spatially Embedded Networks ·May 12, 2023 5 / 26 Miscellaneous Metrics Minimum Spanning Tree (MST) sub-network of the original weighted network without loops M = N − 1 edges Kruskal’s, Prim’s, Boruvka’s algorithms leaves: nodes with one edge leaf number L: number of nodes with 1 edge MST diameter d: longest shortest path of an MST, dmax is related to L two extreme tree topologies: path-like configuration: leaf number = 2 star-like configuration: leaf number = N − 1 J. Spurný, E. Výtvarová ·Spatially Embedded Networks ·May 12, 2023 6 / 26 Miscellaneous Metrics Minimum Spanning Tree J. Spurný, E. Výtvarová ·Spatially Embedded Networks ·May 12, 2023 7 / 26 Miscellaneous Metrics Minimum Spanning Tree Topology1 1 Tewarie, 2014 J. Spurný, E. Výtvarová ·Spatially Embedded Networks ·May 12, 2023 8 / 26 Miscellaneous Metrics Minimum Spanning Tree In Multiple Sclerosis2 2 Tewarie, 2014 J. Spurný, E. Výtvarová ·Spatially Embedded Networks ·May 12, 2023 9 / 26 Spatially Embedded Networks Spatially Embedded Networks Networks with a spatial dimension: at the interface of geography node position in space plays a role For example transport infrastructure circulatory systems (blood vessels, leaf veins) J. Spurný, E. Výtvarová ·Spatially Embedded Networks ·May 12, 2023 10 / 26 Spatially Embedded Networks Transport Networks – Properties Note: often planar graphs – can be drawn without crossing edges not always: e.g., air transport Node degree distribution P(k) establishing connections associated with costs =⇒ cutoff in node distribution P(k) for planar networks, P(k) is also very peaked due to spatial constraints J. Spurný, E. Výtvarová ·Spatially Embedded Networks ·May 12, 2023 11 / 26 Spatially Embedded Networks Transport Networks – Properties Clustering coefficient C nearby nodes have a higher probability of connection: higher clustering coefficient Betweenness centrality a natural metric of node importance homogeneous on the grid: grows from the periphery to the center shortcuts cause significant heterogeneity J. Spurný, E. Výtvarová ·Spatially Embedded Networks ·May 12, 2023 12 / 26 Spatially Embedded Networks Air Transport – Properties nodes: airports, edges: direct flights the network is spatial, not planar scale-free and small-world cutoff P(k) – physical limits of airport capacity strong correlation between node degree and traffic volume strong correlation between node degree and range of transport betweenness and degree do not correlate communities determined by geographical and political factors J. Spurný, E. Výtvarová ·Spatially Embedded Networks ·May 12, 2023 13 / 26 Spatially Embedded Networks Airports J. Spurný, E. Výtvarová ·Spatially Embedded Networks ·May 12, 2023 14 / 26 Spatially Embedded Networks Airline Network3 3 Sun, 2018 J. Spurný, E. Výtvarová ·Spatially Embedded Networks ·May 12, 2023 15 / 26 Spatially Embedded Networks Public Transport A real load may not correspond to betweenness: J. Spurný, E. Výtvarová ·Spatially Embedded Networks ·May 12, 2023 16 / 26 Spatially Embedded Networks Commuting And Migration Population movements: nodes: destinations, weighted edges: movement of people a very interesting topic with overlaps in economics and sociology Gravity law: Tij = K PiPj dσ ij where dij is physical distance, P is population, and σ depends on the system and Tij is the migration rate verified on many datasets J. Spurný, E. Výtvarová ·Spatially Embedded Networks ·May 12, 2023 17 / 26 Spatially Embedded Networks Commuting And Migration – Communities4 4 Sardinia; Caschili, 2010 J. Spurný, E. Výtvarová ·Spatially Embedded Networks ·May 12, 2023 18 / 26 Spatially Embedded Networks Energy Infrastructure Power distribution network very important and extensive network gradual development – complex system incomplete understanding of behavior, the possibility of cascading failures exponential P(k), high clustering Water distribution sparse planar network very peaked P(k) J. Spurný, E. Výtvarová ·Spatially Embedded Networks ·May 12, 2023 19 / 26 Spatially Embedded Networks Internet Global information infrastructure nodes: autonomous systems or routers edges: connections at L1-L3 ISO OSI one level higher: a network of hyperlink references scale-free network router placement correlates with population density generative model includes a combination of spatial factors and preferential attachment J. Spurný, E. Výtvarová ·Spatially Embedded Networks ·May 12, 2023 20 / 26 Spatially Embedded Networks Historic Networks5 5 Fousek,2016 J. Spurný, E. Výtvarová ·Spatially Embedded Networks ·May 12, 2023 21 / 26 Spatially Embedded Networks Historic Networks6 6 Meeks, 2013, https://digitalhumanities.stanford.edu/orbis-v2/ J. Spurný, E. Výtvarová ·Spatially Embedded Networks ·May 12, 2023 22 / 26 Spatially Embedded Networks Historic Networks7 7 Fousek, 2018 J. Spurný, E. Výtvarová ·Spatially Embedded Networks ·May 12, 2023 23 / 26 Spatially Embedded Networks Historic Networks8 8 Chalupa, 2021 J. Spurný, E. Výtvarová ·Spatially Embedded Networks ·May 12, 2023 24 / 26 Spatially Embedded Networks Recommended reading Barthélemy, M. (2011). Spatial networks. Physics Reports, 499(1), 1-101. J. Spurný, E. Výtvarová ·Spatially Embedded Networks ·May 12, 2023 25 / 26