eCite Digital Repository

Accelerating computation of distance based centrality measures for spatial networks

Citation

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]


Preview
PDF
Not available
2Mb
  

Copyright Statement

Copyright 2016 Springer International Publishing

Official URL: https://link.springer.com/book/10.1007/978-3-319-4...

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

Abstract

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:Technology
Research Group:Communications Technologies
Research Field:Computer Communications Networks
Objective Division:Information and Communication Services
Objective Group:Computer Software and Services
Objective Field:Computer Software and Services not elsewhere classified
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
Downloads:0

Repository Staff Only: item control page