Algorithms seminar: Devdatt Dubhashi (Chalmers)
Date: January 19, 2007 (Friday) at 11:00 to 12:00
Title: How Small Worlds Evolve (Or what Kleinberg left Out)
Abstract: In his seminal Nevalinna-prize winning work, Kleinberg introduced a simple model to explain the "small world" phenomenon. In essence, he showed that there was a critical probability distribution of the long links that lead to small worlds, anything above or below this fails. However, why should real networks follow this very precise probability law? I will describe a very simple and natural model of random graph evolution due to Oskar Sandberg that leads to Kleinberg-like distributions and small worlds. I will describe preliminary results and pose many open problems.
Room: E:2116
Last modified Dec 9, 2011 12:59 pm
0792