Seminar: Rumor Spreading and Graph Expansion

Dr. George Giakkoupis (INRIA Rennes, France)

Monday, March 10, 2014, 10:30AM-12:00PM, EV 2.260

Abstract

Randomized rumor spreading is a basic model for information dissemination in networks. Each node periodically contacts a random neighbor, and the two nodes exchange any information they currently have. This allows information to spread in the network in an ``epidemic" style. Randomized rumor spreading provides a simple, scalable, and robust protocol for message broadcasting, which is particularly relevant for large, unknown, or dynamically changing networks. Further, it is interesting from a sociological perspective, as it provides a simple model for how information, rumors, or ideas spread in social networks.

In this talk, I will present some results that relate the speed of rumor spreading, that is, how quickly information spreads from a single source to all nodes in the network, with standard expansion parameters of the network. I will also discuss the impact on rumor spreading of a dynamic network.

Bio

George Giakkoupis is a Researcher at INRIA Rennes, in France. He received his PhD from the University of Toronto in 2008, and was a Postdoctoral Fellow at University of Paris VII and the University of Calgary. His expertise is in the design and analysis of algorithms, in particular, randomized and distributed algorithms. He has worked on epidemic protocols, search in social networks, peer-to-peer networks, and shared-memory distributed computing.