Accelerating Computation of Distance Based Centrality Measures for Spatial Networks
Accelerating Computation of Distance Based Centrality Measures for Spatial Networks
复制标题
DOI：
10.1007/978-3-319-46307-0_24
复制
发表时间：
2016-10
期刊：
影响因子：
--
通讯作者：
K. Ohara;Kazumi Saito;M. Kimura;H. Motoda
中科院分区：
文献类型：
--
作者：
K. Ohara;Kazumi Saito;M. Kimura;H. Motoda
在本文中，通过专注于嵌入在真实的空间中的空间网络，我们首先扩展了传统的基于步骤的接近度和介数中心，将节点间的链接距离从节点的位置。然后，我们提出了一种方法来加速计算这些中心性措施修剪一些节点和链接的基础上，一个给定的空间网络的切割链接。在我们的实验中使用的空间网络构建的城市街道的几种类型的城市，我们提出的方法实现了约两倍的计算效率相比，基线方法。计算时间的实际减少量取决于网络结构。我们进一步实验表明，通过检查高排名的节点，接近度和介数中心具有完全不同的特点。
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.