IIIT Hyderabad Publications |
|||||||||
|
Efficient Multicore Algorithms for Farness- and Closeness- Centrality in Static and Dynamic GraphsAuthor: Sai Charan Regunta Regunta Date: 2020-12-11 Report no: IIIT/TH/2020/112 Advisor:Kishore Kothapalli AbstractGraph algorithms are one of the most robust and powerful algorithms to solve many contemporary real-world problems. The humongous real-world graph networks should be parallelized to study and gain understanding from them. Literature consists of several studies that proposed multiple methods to compute various centrality measures for a multi-core system. In this thesis, we study about farness and closeness centrality measures. To the best of our knowledge, this is the first work in parallel algorithms with respect to farness-centrality. We utilize the information about the structure of the graph to abstain from doing repetitive tasks. In this thesis, we propose a parallel algorithm to compute the farness-centrality value using graph optimizations while avoiding the redundancy on the graph using the properties detailed in this thesis below. It is inevitably tough and time-consuming to calculate the values for each and every node in social graphs since they are too big to handle even after optimizations. So, we estimate the values by taking a trade-off on time vs. quality. We accept a little reduction in the quality of results prioritizing on time. We analyze our algorithm and reduction techniques on various classes of real-world graphs. However, as these graphs evolve and change, it is crucial to study how to update farness and closeness measures on changes to the underlying graph. In this thesis, we also present approaches to compute closeness-centrality on dynamic graphs. As existing work by Sarıyuce et al. (CLUSTER 2013) in this ¨ field is limited to a single edge update, we extend it to batch update. We implement our algorithms on Intel 24-core CPU. We conduct detailed experiments to study the impact of various parameters associated with our algorithms and their implementation. Our results indicate that on a collection of real-world graphs, our techniques improve the state-of-the-art with respect to updating closeness-centrality by a factor of 10 to 34 for a batch of 100 edges on dynamic graphs and 10 to 20 on static graphs over a corresponding adaptation of the work of Sarıyuce et al. (CLUSTER 2013) ¨ and MULTIBFS respectively. Full thesis: pdf Centre for Security, Theory and Algorithms |
||||||||
Copyright © 2009 - IIIT Hyderabad. All Rights Reserved. |