Novel centrality measures and applications to underground networks

Two novel centrality indices, PathRank and Icentr, are defined. PathRank is a generalization of the PageRank algorithm, suitable to rank nodes of undirected graphs according to number and weight of paths in the graph. Icentr ranks the nodes of the graph by means of a combination of the weights of nodes and edges, scaled according to the distance from each node, one at a time. We apply the two novel indices to underground transportation networks, since these networks represent an infrastructural backbone for the transportation system of most big cities over the world. The characterization of the most important components of those networks and the simulation of their responses when they stop working properly, are vital for maintaining the mobility service at a desirable level. Since there are different ways to associate a graph to an underground network according to the degree of detail and aims of the study, we describe the methodology we adopted to associate a graph to such a network. The methodology was applied to 34 underground networks of worldwide cities, and the resulting graphs constitute the reference dataset. A detailed study of both Boston network and the dataset is proposed as prototypal for either a graph alone or all graphs in a dataset. Results show how different features of graphs are revealed by the two novel indices.