Betweenness centrality in transport networks: a comparison between static and a temporal approaches

Abstract

Los grafos, o redes, están compuestos por un conjunto de nodos conectados por aristas, estos nodos pueden representar distintas entidades entre las cuales hay una relación binaria representada por las aristas. Además, estas redes pueden ser usadas para modelar una gran cantidad de procesos que pueden suceder en las entidades que representan. Las redes normalmente son estáticas, no se considera su evolución respecto al tiempo. Si consideramos dicha evolución tenemos redes temporales, en las cuales las aristas solo existen en ciertos momentos temporales, los cuales pueden ser tiempos discretos o intervalos. Con esto representamos como evoluciona la relación binaria entre las entidades que forman el grafo. Esta información condiciona la definición y métodos para obtener ciertas medidas en las redes, como por ejemplo las medidas de centralidad, que representan cuanto de importante es un nodo en la red; y más especificamente, la centralidad de intermediación en los caminos más cortos ”shortest-path betweenness centrality”, en la cual un nodo se considera importante si es probable que para dos nodos aleatorios, este primer nodo se encuentre en el camino más corto entre ellos. En este trabajo comparamos los resultados para esta medida usando su definición en redes estáticas y temporales usando como red proveniente del mundo real las redes de transporte público de Madrid y de Helsinki dando como conclusión en que casos dan mayores ventajas cada modelo. Además, por último, buscamos proponer nuevos métodos que puedan suponer un compromiso entre ambos modelos o mejorarlos de alguna manera.---ABSTRACT---Graphs or networks are a set of nodes connected by edges. They can represent several different entities and pairwise relations between them. Moreover, graphs can be used to model a great number of natural and anthropogenic processes. The most common graph model is a static graph. In this kind of graphs, the nodes and edges are not modified over time. Such representation can be sufficient for networks such as friendship or road networks as these evolve at a low velocity over time compared to the processes that can be studied over these networks, such as transfer of information or traffic respectively. On the other hand, some networks can change fast over time, making the different edges only appear at certain times. For example, public transport or contact networks throughout a period of time. This temporal information is important as, for example, in the first case the times of departure of the different transports are needed when planning routes, and in the second, transfer of information can only happen towards contacts taking place after receiving the information. This report aims to compare results using both static and temporal approaches when measuring network centralities, i.e., how important is a node or edge in the network. We focus on a particular kind of centrality, namely shortest-path betweenness centrality, and we use for this task real-world networks, in particular, different transport networks. As a conclusion, we use the results obtained applying these two different approaches to indicate which of them is more advantageous to use depending on the context. We also seek to propose several new approaches that could represent a compromise between the two approaches or improve them in different manners.