An Extremely Fast Algorithm for Identifying High Closeness Centrality Vertices in Large-Scale Networks

The significance of an entity in a network is generally given by the centrality value of its vertex. For most analysis purposes, only the high ranked vertices are required. However, most algorithms calculate the centrality values of all the vertices. We present an extremely fast and scalable algorit...

Full description

Saved in:
Bibliographic Details
Main Authors: Ufimtsev, Vladimir, Bhowmick, Sanjukta
Format: Conference Proceeding
Language:English
Subjects:
Conferences
Perturbation methods
Testing
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The significance of an entity in a network is generally given by the centrality value of its vertex. For most analysis purposes, only the high ranked vertices are required. However, most algorithms calculate the centrality values of all the vertices. We present an extremely fast and scalable algorithm for identifying the high closeness centrality vertices, using group testing. We show that our approach is significantly faster (best-case over 50 times, worst-case over 7 times) than the currently used methods. We can also use group testing to identify networks that are sensitive to edge perturbation.
ISSN:2767-942X
DOI:10.1109/IA335182.2014.10612526