coverage centrality is an important metric to evaluate the node importance in road networks. However, the current solutions have to compute the coverage centrality of all the nodes together, which is resource-wasting ...
详细信息
ISBN:
(纸本)9783031155123;9783031155116
coverage centrality is an important metric to evaluate the node importance in road networks. However, the current solutions have to compute the coverage centrality of all the nodes together, which is resource-wasting especially when only some nodes' centrality is required. In addition, they have poor adaption to the dynamic scenario because of the computation inefficiency. In this paper, we focus on the coverage centrality query problem and propose an efficient algorithm to compute the centrality of a single node efficiently in both static and dynamic scenarios, with the help of the intra-region pruning, inter-region pruning, and top-down search. Experiments validate the efficiency and effectiveness of our algorithm compared with the state-of-the-art method.
coverage centrality is an important metric to evaluate vertex importance in road networks. However, current solutions have to compute the coverage centrality of all the vertices together, which is resource-wasting, es...
详细信息
coverage centrality is an important metric to evaluate vertex importance in road networks. However, current solutions have to compute the coverage centrality of all the vertices together, which is resource-wasting, especially when only some vertices centrality is required. In addition, they have poor adaption to the dynamic scenario because of the computation inefficiency. In this paper, we focus on the coverage centrality query problem and propose a method that efficiently computes the centrality of single vertices without relying on the underlying graph being static by employing the intra-region pruning, inter-region pruning, and top-down search. We further propose the bottom-up search and mixed search to improve efficiency. Experiments validate the efficiency and effectiveness of our algorithms compared with the state-of-the-art method.
This study aims to explore cost-effective strategies for efficiently dismantling global complex networks into mutually isolated connected components, particularly in the context of a space information network (SIN). W...
详细信息
This study aims to explore cost-effective strategies for efficiently dismantling global complex networks into mutually isolated connected components, particularly in the context of a space information network (SIN). We introduce a novel metric called the coverage centrality, which comprehensively considers the centrality of nodes and links within a satellite coverage area, which integrates the topological and geographical structural information about the network. Through numerical experiments on real -world networks, we demonstrate that the proposed indicator significantly outperforms traditional methods in terms of both effectiveness and efficiency, which tends to select nodes close to the average betweenness of the network for removal rather than solely focusing on nodes with higher centrality, providing a new perspective for us to deeply understand the disintegration behavior of complex networks. The current work not only offers potential application in areas such as anti-terrorist measures and epidemic prevention or control, but also provides new tools to analyze the characteristics of SIN models.
Betweenness centrality and k-path centrality are two important indices that are widely used to analyze social, technological and information networks. In the current paper, first given a directed network G and a verte...
详细信息
ISBN:
(纸本)9781450369763
Betweenness centrality and k-path centrality are two important indices that are widely used to analyze social, technological and information networks. In the current paper, first given a directed network G and a vertex r is an element of V (G), we present a novel adaptive algorithm for estimating betweenness score of r. Our algorithm first computes two subsets of the vertex set of G, called RF(r) and RT(r). They define the sample spaces of the start-points and the end-points of the samples. Then, it adaptively samples from RF(r) and RT(r) and stops as soon as some condition is satisfied. The stopping condition depends on the samples met so far, vertical bar RF(r)vertical bar and vertical bar RT(r)vertical bar. We show that compared to the well-known existing algorithms, our algorithm gives a better (lambda, delta)-approximation. Then, we propose a novel algorithm for estimating k-path centrality of r. Our algorithm is based on computing two sets RF(r) and D(r). While RF(r) defines the sample space of the source vertices of the sampled paths, D(r) defines the sample space of the other vertices of the paths. We show that in order to give a (lambda, delta)-approximation of the k-path score of r, our algorithm requires considerably less samples. Moreover, it processes each sample faster and with less memory. Finally, we empirically evaluate our proposed algorithms and show their superior performance. Also, we show that they can be used to efficiently compute centrality scores of a set of vertices.
暂无评论