Betweenness Centrality : Algorithms and Lower Bounds

Abstract

One of the most fundamental problems in large scale network analysis is to determine the importance of a particular node in a network. Betweenness centrality is the most widely used metric to measure the importance of a node in a network. In this paper, we present a randomized parallel algorithm and an algebraic method for computing betweenness centrality of all nodes in a network. We prove that any path-comparison based algorithm cannot compute betweenness in less than O(nm) time.

References in corpus (3)

• Finding and evaluating community structure in networks
• Lethality and centrality in protein networks
• The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles

Cited by in corpus (4)

• Neuronal functional connectivity among multiple areas of the rat somatosensory system during spontaneous and evoked activities
• Incremental Algorithms for Network Management and Analysis based on Closeness Centrality
• Knowledge gaps in the early growth of semantic networks
• Betweenness Centrality as Predictor for Forces in Granular Packings