Abstract

I will present a versatile and scalable algorithm for computing exact distances on real-world networks with tens of millions of arcs in real time. Unlike existing approaches, preprocessing and queries are practical on a wide variety of inputs, such as social, communication, sensor, and road networks. We achieve this by providing a unified approach based on the concept of 2-hop labels, improving upon existing methods. In particular, we introduce a fast sampling-based algorithm to order vertices by importance, as well as effective compression techniques. Towards the end I will also briefly talk about other projects that I was pursuing at Microsoft Research Silicon Valley. In particular, I will present an efficient and highly scalable algorithm for influence maximization in social networks. Here, we are interested in computing a small set of entities of the network that in their entirety influence as many others as possible. This has applications, e.g., for viral marketing and rumor spreading.