##### 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

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