COMP 5704: Parallel Algorithms and Applications in Data Science


School of Computer Science
Carleton University, Ottawa, Canada

Project Title: Betweenness Centrality in Dynamic Graphs

Name: Nathan Bowness

E-Mail: nbown088@uottawa.ca

Project Outline:
Measuring the betweenness centrality of nodes in a graph is a research topic with many applications including analyzing social, internet, and transportation networks. This research encompasses recomputing betweennes centrality on dynamic graphs where edges are constantly being added and removed. For this project, I will be covering some graph theory but will be focussing on recent parallel algorithms for updating betweenness centrality in dynamic graphs. I will implement an algorithm designed by Skula et al. that proposes a new batch update algorithm for recomputing betwennes centrality with improved performance over other approaches. The algorithm will be implemented on a multi-core CPU and I hope test it’s performance on additional graph sets to verify the original findings.

Startup Paper(s): Efficient Parallel Algorithms for Betweenness- and Closeness-Centrality in Dynamic Graphs     [PDF]

Deliverables:

Relevant References: