Logo image
Back
Efficient Anytime Anywhere Algorithms for Closeness Centrality in Large and Dynamic Graphs
Conference proceeding

Efficient Anytime Anywhere Algorithms for Closeness Centrality in Large and Dynamic Graphs

Eunice E. Santos, John Korah, Vairavan Murugappan and Suresh Subramanian
2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pp 1821-1830
01 May 2016
DOI: https://doi.org/10.1109/IPDPSW.2016.215

Abstract

Algorithm design and analysis anytime algorithms Approximation algorithms centrality analysis Data structures dynamic graphs Heuristic algorithms parallel and distributed processing Partitioning algorithms social network analysis Social network services
Recent advances in social network analysis methodologies for large (millions of nodes and billions of edges) and dynamic (evolving at different rates) networks have focused on leveraging new high performance architectures, parallel/distributed tools and novel data structures. However, there has been less focus on designing scalable and efficient algorithms to handle the challenges of dynamism in large-scale networks. In our previous work, we presented an overarching anytime anywhere framework for designing parallel and distributed social network analysis algorithms that are scalable to large network sizes and can handle dynamism. A key contribution of our work is to leverage the anytime and anywhere properties of graph analysis problems to design algorithms that can efficiently handle network dynamism by reusing partial results, and by reducing re-computations. In this paper, we present an algorithm for closeness centrality analysis that can handle changes in the network in the form of edge deletions. Using both theoretical analysis and experimental evaluations, we examine the performance of our algorithm with different network sizes and dynamism rates.

Metrics

1 Record Views

Details

Logo image