eCite Digital Repository

Accelerating computation of distance based centrality measures for spatial networks


Ohara, K and Saito, K and Kimura, M and Motoda, H, Accelerating computation of distance based centrality measures for spatial networks, Proceedings of the 19th International Conference on Discovery Science (DS 2016), 19-21 October 2016, Bari, Italy, pp. 376-391. ISBN 978-3-319-46306-3 (2016) [Refereed Conference Paper]

Not available

Copyright Statement

Copyright 2016 Springer International Publishing

Official URL:

DOI: doi:10.1007/978-3-319-46307-0_24


In this paper, by focusing on spatial networks embedded in the real space, we first extend the conventional step-based closeness and betweenness centralities by incorporating inter-nodes link distances obtained from the positions of nodes. Then, we propose a method for accelerating computation of these centrality measures by pruning some nodes and links based on the cut links of a given spatial network. In our experiments using spatial networks constructed from urban streets of cities of several types, our proposed method achieved about twice the computational efficiency compared with the baseline method. Actual amount of reduction in computation time depends on network structures. We further experimentally show by examining the highly ranked nodes that the closeness and betweenness centralities have completely different characteristics to each other.

Item Details

Item Type:Refereed Conference Paper
Keywords:closeness centrality, betweenness centrality, spatial network, distance based centrality, cut link
Research Division:Engineering
Research Group:Communications engineering
Research Field:Network engineering
Objective Division:Information and Communication Services
Objective Group:Information systems, technologies and services
Objective Field:Information systems, technologies and services not elsewhere classified
UTAS Author:Motoda, H (Dr Hiroshi Motoda)
ID Code:117770
Year Published:2016
Deposited By:Information and Communication Technology
Deposited On:2017-06-27
Last Modified:2017-11-20

Repository Staff Only: item control page