Linear Algorithms for Massive Real-World Graphs – LiMass

Web search, drug design and traffic management are only a few examples of crucial applications that nowadays rely on the analysis of graphs. Involved graphs have become increasingly massive sometimes reaching trillions of edges such as the Web graph, Facebook, Internet or a human brain. Only quasi-linear time algorithms can process these massive graphs in a reasonable amount of time on the best supercomputers.

On the one hand, many important problems seem to require more than quadratic time to solve them in the worst case. On the other hand, it has been observed that many algorithms are much more efficient on real-world graphs than in such a worst case scenario. We suggest focussing on graph instances encountered in practice and design quasi-linear time algorithms for such real-world graphs by identifying, formalizing and leveraging their structural properties.