File(s) under permanent embargo
Accelerating computation of distance based centrality measures for spatial networks
conference contribution
posted on 2023-05-23, 12:10 authored by Ohara, K, Saito, K, Kimura, M, Motoda, HIn 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.
History
Publication title
Proceedings of the 19th International Conference on Discovery Science (DS 2016)Editors
T Calders, M Ceci & D MalerbaPagination
376-391ISBN
978-3-319-46306-3Department/School
School of EngineeringPublisher
Springer International PublishingPlace of publication
SwitzerlandEvent title
19th International Conference on Discovery Science 2016 (DS 2016)Event Venue
Bari, ItalyDate of Event (Start Date)
2016-10-19Date of Event (End Date)
2016-10-21Rights statement
Copyright 2016 Springer International PublishingRepository Status
- Restricted