Masterarbeit
Approximating Distributed Graph Processing  
Betreuer 
Dr. rer. nat. Sukanya Bhowmik

Prüfer 
Prof. Dr. rer. nat. Dr. h. c. Kurt Rothermel

Beschreibung  
Distributed Graph Processing (DGP) has gained massive popularity fueled by the need to perform complex graph analysis on massive realworld graphs such as digitized social networks or crawled web document For instance, in the shortest path algorithm, vertices exchange messages about the current path length to learn about the shortest paths via neighboring vertices. A first idea to improve the naive approach of randomly dropping messages is to drop messages according to their \textit{information gain} (or entropy). A second idea is to drop messages with higher probability if this results in high saved communication overhead during distributed computation.These approaches promise superlinear runtime reduction with the number of dropped messages as we focus on the redundant and costly messages. The goals and tasks of this thesis are the following. The results need to be documented in written form and have to be presented at the VSColloquium. 