Understanding Trip Centrality in Temporal Multiplex Networks
Discover how centrality metrics measure the importance of nodes in temporal multiplex networks where links have non-instantaneous travel times. Learn about the generalization of Katz centrality to address time-related challenges in network analysis. Explore the efficient computation of centrality using matrix algebra and the design of metrics for transportation networks and epidemics with non-zero link travel times.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Trip Centrality walking on a temporal multiplex with non-instantaneous link travel time Silvia Zaoli
Introduction Centrality metrics Centrality metrics measure the importance of nodes in a network Several definitions of importance -> several centrality metrics Many of the existing metrics apply to static, single-layer networks Temporal networks Multiplexes Links depend on time (time of appearance + duration Links of different types represented on different layers duration) Trip Centrality 2
Introduction Many centrality metrics count paths/walks Counting walks is convenient because: processes do non only use paths/shortest paths (especially in temporal networks, where the shortest path could not always be available!) Efficient computation with matrix algebra The outgoing (incoming) centrality of a node is given by the sum of the contributions of all walks, of any length, outgoing from (incoming to) it, with longer walks weighted less Katz centrality <1 <1 = out i n # outgoing walks of length n k = 1 n A= adjacency matrix 2 2 out i = + + ( ) k A A ij ij j j Trip Centrality 3
Outline Design a centrality metric that applies to temporal multiplexes when the time required to travel through a link is non-zero (transportation networks, spreading of epidemics with incubation time, ) Aim i i j j t t Generalization of Katz centrality to temporal networks: - limits of an existing generalization when link travel time is non-zero - how to overcome this problem Generalization to temporal multiplexes Trip Centrality 4
Temporal generalization of Katz Static case Temporal case n Count walks using A Count time-respecting walks Discretize time in windows of length t For each window, adjacency matrix A[t] Time-respecting walks are counted by the matrix products: [ ] nt [ ] [ ] t t t t t A A A 1 2 1 2 n At most one link used per time frame Trip Centrality 5
Temporal generalization of Katz [ ] nt [ ] [ ] t t All products of the type with A A A t t t 1 2 1 2 n [1] [2 ] [ ] T are obtained from + + + ( ) ( ) ( ) A A A [1] [ 2 ] [ ] T = + + + A A A 2 [1] [ 2 ] 2 [1] [ 3 ] 2 [ 1] [ ] T T + + + + A A A A A A [1] [ ] T T Counts walks of length 2, with one jump in time frame 1 and one in time frame 3 + + A A Works well when traveling through a link is instantaneous, and on a single layer Dynamic communicability (Grindrod et al., PRE 2011) Trip Centrality 6
Non-zero link travel time What happens when link travel time is non-zero? i i j j k k Link duration = travel time i i i i k k i i k k i i k k k k j j j j j j j j No time-respecting walk exists from i to k However: 2 [1] [2] counts a path of length 2 from i to k A A Silvia Zaoli 7
Secondary nodes s s s s [ ] t + + A N N ( ) ( ) N N N N L L Larger but very sparse Number of primary nodes N N Number of secondary nodes L Silvia Zaoli 8
Trip Centrality (Single Layer) i i i i k k i i k k i i k k k k j j j j j j j j i i k k k k i i k k i i k k i i j j j j j j j j [1] [3 ] Counts i -> j A A No time-ordered product counts i ->k (it would be counted by which is not ordered) [1] [3] [ 2 ] [ 4 ] A A A A Silvia Zaoli 9
Trip Centrality (Temporal Multiplex) Walks can be intra- or inter-layer layer Inter-layer walks might have less probability to be used (e.g. because the imply a cost), therefore should be weighted less in computing centrality Penalty for each inter-layer jump layer 2 2 [ ] t + + + + A ( ) ( ) N N N N N N ( ) ( ) N N N N lay L lay L L L Only intra-layer links are represented in A[t] N Number layers lay [ ] [ ] t t [ ] [ ] t t A A[t] K K : either stay put or jump to a copy of that node on another layer, with penalty , [t] : jump within one layer A KA K A K A 3 n 1 2 Silvia Zaoli 10
Conclusions Temporal networks with non-zero link travel time require ad hoc centrality metrics Trip Centrality generalises Katz centrality to temporal multiplexes counting only walks that can actually be travelled and differentiating the contributions of inter- and intra-layer walks Application: US air traffic network, loss of centrality due to delays (change in the links temporal structure) Zaoli et al., 2019, preprint on ArXiv:1903.02815 Silvia Zaoli 11
Collaborators @ University of Bologna Fabrizio Lillo Piero Mazzarisi Thank you very much for your attention! This project has received funding from the SESAR Joint Undertaking under the European Union s Horizon 2020 research and innovation programme under grant agreement No 783206. The opinions expressed herein reflect the author s view only. Under no circumstances shall the SESAR Joint Undertaking be responsible for any use that may be made of the information contained herein.
Non-zero link travel time What happens when link travel time is non-zero? Link duration = travel time Node i should have larger outgoing centrality than l i -> k connection possible l -> k connection not possible 2 [1] [2] counts a path of length 2 from l to k A A Node l has a larger outgoing centrality than i 3 l -> m counted by i-> j counted by [3] [1] [2] A A A A A [1] [2] 2 Silvia Zaoli 13
Trip Centrality (Single Layer) Using weight : = 2 + + + Contributions to outgoing centrality of i [1] 2 [1] [2] + 3 A + + A A A [1] [2] [3] 4 [1] [2] [3] [4] + A A A A A A Contributions to outgoing centrality of l [1] 2 [1] [3] A A A + Silvia Zaoli 14
Trip Centrality [1] [2] [ ] 1 out T = + + + 1 [( ) ( ) ( ) ] t A K A K A K K [1] [2] [ ] 1 in T T = + + + 1 [( ) ( ) ( ) ] t A K A K A K K I obtain layer-specific centralities: counting walks that leave from (or arrive to) the node with a link on that particular layer Aggregated centralities, counting all walks outgoing from (incoming to) that node on any layer, are obtained summing across layers The centrality of a secondary node is the centrality of the corresponding original link Silvia Zaoli 15
US air transport network Dataset contains flights of 14 major US airlines in 2015, from US Department of Transportation One day in windows of 15 mins Change of ranking with change of One layer per airline Incoming Outgoing Airports increasing rank with larger benefit from more cooperation between airlines Silvia Zaoli 16
US air transport network Loss of centrality due to delays Network of realised flights differs from schedule due to delays and cancellations Delays can disrupt connections, but the entity of their effect on an airport s connectivity depend in a complex way from the schedule The loss of centrality quantifies this effect Silvia Zaoli 17
