An Experimental Study on the Scalability of Recent Node Centrality Metrics in Sparse Complex Networks

Area of Science:

• Network Analysis
• Computational Complexity
• Data Science

Background:

• Node centrality measures are crucial for identifying influential nodes in various network applications, from transportation to epidemiology.
• The proliferation of network data necessitates understanding the computational feasibility of newly developed centrality measures.
• Assessing the scalability of these measures is critical before their practical application in time-sensitive analyses.

Purpose of the Study:

• To comprehensively examine the time complexity of 18 network centrality measures introduced between 2005 and 2020.
• To provide practical estimates of computational time scaling with network size, particularly for sparse networks.
• To analyze how network properties (scale-free, small-world, random) influence the performance of these measures.

Main Methods:

• Empirical analysis of the runtime of 18 distinct centrality measures.
• Systematic evaluation of time complexity as a function of the number of nodes (n) in the network.
• Consideration of different network topologies: scale-free, small-world, and random networks.

Main Results:

• Several centrality measures exhibit efficient scaling, running in O(n log n) time, suitable for large networks.
• Other measures demonstrate higher computational demands, requiring O(n^2) or O(n^3) time.
• The performance of measures is influenced by the underlying network structure.

Conclusions:

• Analysts can now better estimate the computational feasibility of using specific network centrality measures.
• Measures with high computational complexity are identified as targets for future optimization research, such as approximation algorithms or distributed computing.
• This work aids in selecting appropriate centrality measures based on network size, properties, and available computational resources.