Greedy Search in Social Networks

David Liben-Nowell
Carleton College

Stanley Milgram's "six degrees of separation" experiments in the
1960's helped the so-called small-world phenomenon pass from the
merely anectodal to the scientific. But the quest for good models of
social networks---graph models that successfully reproduce observed
features of social networks (small diameter, homophily, clustering,
efficient search without global knowledge of the network, etc.)---has
been difficult. In this talk, I'll discuss the connection between
recent graph-theoretic models of social networks and large-scale
real-world social networks, focusing on the LiveJournal online
community. I'll also describe the "rank-based friendship" model of
social networks that maintains the aforementioned properties while
empirically matching real-world networks. Joint work with Jasmine
Novak, Ravi Kumar, Prabhakar Raghavan, and Andrew Tomkins (Yahoo!

Audio (MP3 File, Podcast Ready) Presentation (PDF File)

Back to Workshop III: Random and Dynamic Graphs and Networks