IIIT Hyderabad Publications |
|||||||||
|
Identifying: Who is Important in My WorldAuthor: Sai Harsh Tondomker Date: 2021-03-20 Report no: IIIT/TH/2021/23 Advisor:Kishore Kothapalli AbstractCentrality plays an essential role in identifying the essential nodes in social networks. This thesis proposes a new flavor of centrality, where we focus on farness and closeness centrality, which identify closer nodes in a network.Since closeness-centrality is a fundamental problem in graph theory, several algorithms exist for this problem for both static and dynamic environments. Recent algorithms for computing centrality have relied heavily on breadth-first search (BFS) traversals of the input graph. Usually, a significant portionof the algorithm’s overall run-time is spent on BFS operations. We have developed a framework (called BRICS) based on the graph’s structural properties, which reduces the time taken for a single BFS traver-sal and reduces the overall number of traversals. Since finding the exact values of centrality requiresconsiderable computational time, we have devised an estimation algorithm with a reasonable trade-offbetween accuracy and speedup.Additionally, we have created a GPU algorithm to update closeness-centrality in a dynamic settingwhen a batch of edges is added or deleted by extending Sarıy ̈uce et al. (CLUSTER 2013), an incremen-tal algorithm (single edge update) to the batch update.We have implemented our algorithm in Nvidia Tesla V100 GPU parallel architecture with 80 SMXs.We experimented on five different types of real-world graphs and varying the optimization techniques to achieve the max speed up. Our experimental results show that we were able to achieve a maximumof 12.54x speedup on computing fairness centrality and 53x on updating closeness-centrality in the dynamic setting. Full thesis: pdf Centre for Security, Theory and Algorithms |
||||||||
Copyright © 2009 - IIIT Hyderabad. All Rights Reserved. |