Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 264 - Combinatorics

R. Andersen

UCSD Graduate Student

Modeling the small world phenomenon using a hybrid model with local network flow

Abstract:

The 'small world phenomenon' as observed by the psychologist Stanley Milgram in the 1960s is that most pairs of people are connected by a short chain of acquaintances. More generally we say a graph exhibits the small world phenomenon if the average distance between vertices is small due to a few random-like edges combined with a highly regular local structure. Randomly generated graphs with a power law degree distribution are often used to model large real-world networks. While these graphs have small average distance, they do not have the local structure associated with the small world phenomenon. We define a hybrid model which combines a global graph (a random power law graph) with a local graph (a graph with high local connectivity defined by network flow). We also present an efficient algorithm to extract a highly connected local graph from a given realistic network. We show that the hybrid model is robust in the following sense. Given a graph generated by the hybrid model, we can recover a good approximation to the original local graph in polynomial time.

Host:

October 12, 2004

4:00 PM

AP&M 6438

****************************