Dynamic Graph Analytics

Network science has given us fundamental new insights into the structure of complex networks such as online social networks. Our goal is to expand these techniques to analyze social networks while they grow.
Master

The analysis of social networks requires computing metrics such as clustering coefficients and betweenness centrality. For large networks, these metrics can be very expensive to compute, even with parallel algorithms on modern supercomputers. Thus, when new data arrives, it is desirable to have algorithms that do not need to start again from the beginning and repeat the expensive computation. In this thesis we will investigate how network metrics can be computed efficiently in a dynamic network where new users and connections appear continuously.

Goal

The goal of this thesis is to implement an online clustering algorithm for massive datasets on a supercomputer, and test it with a continuous stream of Twitter data.

Learning outcome

Understanding of graph analytics
Implementation of large scale parallel algorithms
Use of supercomputers

Qualifications

Knowledge of C/C++
Familiarity with parallel graph algorithms
Experience with MPI and/or OpenMP

Supervisors

  • Johannes Langguth
  • Xing Cai

Contact person