ENHANCED PRUNING FOR DISTRIBUTED CLOSENESS CENTRALITY UNDER MULTI-PACKET MESSAGING

In recent years, identifying central nodes in large-scale complex networks has become a critical task, with applications ranging from social network analysis to traffic routing. While closeness centrality is a commonly used metric, its decentralized computation—especially in large networks—poses significant challenges due to high communication overhead. Previous approaches, such as pruning, aim to approximate centrality efficiently but often overlook the cost of exchanging multiple data packets in distributed settings. In this paper, we enhance the pruning method (a distributed approach for identifying central nodes using closeness centrality) by addressing this communication bottleneck. Specifically, we introduce a technique that leverages multi-packet messaging, reducing data loss and improving running times without compromising the accuracy of centrality estimates. Our approach also optimizes the communication load, leading to fewer exchanged messages overall. Empirical evaluation demonstrates that our method outperforms the original pruning technique in both message efficiency and computation time, while preserving the key properties of the baseline method. However, we also observe trade-offs in terms of increased memory usage and overhead, which we discuss in relation to network size and packet complexity. Our findings offer a more efficient solution for decentralized closeness centrality computation, presenting a promising direction for scalable network analysis.