Efficient Extraction of High-Betweenness Vertices

Centrality measures are crucial in quantifying the roles and positions of vertices in networks. An important measure is betweenness, which is based on the number of shortest paths that vertices fall on. However, betweenness is computationally expensive to derive, resulting in much research on effici...

Full description

Saved in:
Bibliographic Details
Main Authors: Wen Haw Chong, Toh, Wei Shan Belinda, Loo Nin Teow
Format: Conference Proceeding
Language:English
Subjects:
Accuracy
Algorithm design and analysis
Approximation algorithms
Approximation methods
Betweenness
centrality
Convergence
efficient
extraction
high-betweenness
Proteins
Radiation detectors
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Centrality measures are crucial in quantifying the roles and positions of vertices in networks. An important measure is betweenness, which is based on the number of shortest paths that vertices fall on. However, betweenness is computationally expensive to derive, resulting in much research on efficient techniques. We note that in many applications, the key interest is on the high-betweenness vertices and that their betweenness rankings are usually adequate for analysts to work with. Hence, we have developed a novel algorithm that efficiently returns the set of vertices with highest betweenness. The algorithm`s convergence criterion is based on the membership stability of the high-betweenness set. Through experiments on various artificial and real world networks, the algorithm is shown to be both efficient and accurate.
DOI:10.1109/ASONAM.2010.31