University of Cambridge > > Microsoft Research Cambridge, public talks > Robust Distance Queries on Massive Networks

Robust Distance Queries on Massive Networks

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Microsoft Research Cambridge Talks Admins.

This event may be recorded and made available internally or externally via Microsoft will own the copyright of any recordings made. If you do not wish to have your image/voice recorded please consider this before attending

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.

This talk is part of the Microsoft Research Cambridge, public talks series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity