Betweenness Centrality : Algorithms and Lower Bounds

Simple item page
dc.creatorKintali, Shiva
dc.date2008-09-11
dc.date2008-10-19
dc.date.accessioned2026-07-07T10:10:51Z
dc.date.available2026-07-07T10:10:51Z
dc.descriptionOne 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.
dc.identifierhttps://arxiv.org/abs/0809.1906
dc.identifierhttp://arxiv.org/abs/0809.1906
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/171711
dc.subjectData Structures and Algorithms
dc.titleBetweenness Centrality : Algorithms and Lower Bounds
dc.typetext

Files

Collections

arXiv