Paper
29 November 2023 Betweenness centrality approximation in large networks using shortest paths approximation and adaptive sampling
Qilin Wang, Nan Xiang, Mingwei You, Xindi Rao
Author Affiliations +
Proceedings Volume 12937, International Conference on Internet of Things and Machine Learning (IoTML 2023); 1293715 (2023) https://doi.org/10.1117/12.3013414
Event: International Conference on Internet of Things and Machine Learning (IoTML 2023), 2023, Singapore, Singapore
Abstract
Betweenness centrality is a measure of node importance in networks, but conventional exact algorithms require a lot of time as the network size grows dramatically. This paper aims to enhance the efficiency and accuracy of betweenness centrality computation for network nodes. We propose an algorithm based on shortest path approximation and adaptive sampling. The algorithm first selects high-quality seed nodes according to degree, then approximates shortest paths, and finally chooses appropriate samples to approximate betweenness centrality. We conduct experiments on 5 different datasets, and the results show that our algorithm outperforms the baseline algorithms in terms of sample size and running time. Our algorithm not only reduces the computational cost effectively, but also guarantees the computational accuracy.
(2023) Published by SPIE. Downloading of the abstract is permitted for personal use only.
Qilin Wang, Nan Xiang, Mingwei You, and Xindi Rao "Betweenness centrality approximation in large networks using shortest paths approximation and adaptive sampling", Proc. SPIE 12937, International Conference on Internet of Things and Machine Learning (IoTML 2023), 1293715 (29 November 2023); https://doi.org/10.1117/12.3013414
Advertisement
Advertisement
RIGHTS & PERMISSIONS
Get copyright permission  Get copyright permission on Copyright Marketplace
KEYWORDS
Detection and tracking algorithms

Error analysis

Statistical analysis

Reflection

Algorithm development

Computer science

Diffusion

Back to Top