IIIT Hyderabad Publications |
|||||||||
|
Efficient Computation of Percolation Centrality in Static and Dynamic NetworksAuthor: Sayantan Jana 20171185 Date: 2022-12-06 Report no: IIIT/TH/2022/154 Advisor:Kishore Kothapalli AbstractCentrality measures are used to quantify various notions of importance of nodes in a network. These measures find application in social network analysis, the study of disease spread, and the like. Since the networks of interest are usually large, parallelism has become a powerful tool to compute these measures. We study parallel algorithms for the percolation centrality measure which extends the betweennesscentrality measure by incorporating a time dependent state variable with every node. We present parallel algorithms that compute the source-based and source-destination variants of the percolation centrality values of nodes in a network. Our algorithms extend the algorithm of Brandes, introduce optimizations aimed at exploiting the structural properties of graphs, and extend the algorithmic techniques introduced by Sariyuce et al. [38] in the context of centrality computation. However, for some of these applications, it is important to study how these centrality values change when there are changes to the underlying network. As a result, parallel algorithms that study how to update these values due to changes to the graph are gaining research interest. We present parallel algorithms to handle both changes to the percolation value of a batch of vertices and the addition and deletion of a batch of edges to the graph. We implement and benchmark our dynamic algorithms on an Nvidia Tesla V100 GPU. Our experiments on a collection of real-world graphs indicate that our algorithms achieve speedups of 1.59× for edge updates, and 63.02× for vertex percolation updates over state-of-the-art static algorithms for a batch of 100 edges and vertices respectively. Full thesis: pdf Centre for Security, Theory and Algorithms |
||||||||
Copyright © 2009 - IIIT Hyderabad. All Rights Reserved. |