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]
 | 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