Graphs are ubiquitous in the modern world - the internet, power supply system, social media, route planning and many more applications are built on top of them. A graph is a data structure capable of representing data points and their correlations. For example, who is friend with whom in a social network, which webpage links to which other webpage in the internet, or which street leads to which crossroad. These correlations or connections can be used to gain more information out of the data, like who is the most influential person in a social network, which is the most central webpage, or how to get somewhere as fast as possible.
In today’s world, these data sets are getting larger each day and already reach into the trillion scale. Processing this amount of information takes much time and computational resources. Additionally, we are faced with the trend that the growth rate of data outstrips the growth rate of processors, i.e., graphs grow faster than the capacity to process them. As a result, in this project, we work towards fast, scalable, and resource efficient graph processing applications. To do so, we intend to explore new optimized partitioning strategies to distribute graphs across multiple machines efficiently. Furthermore, we will investigate the possibilities of approximate computing in graph processing to run graph algorithms orders of magnitude faster. Of course, approximation in graph processing might result in loss of quality. As a result, our main objective is to find good trade-offs between runtime improvement and the loss of quality. This will be investigated for several classes of graph algorithms to tailor the approximation techniques to their specific properties.