Social Network Applications of Small-World Graphs

Dan Berger

Faculty Advisor: Sanjeev Khanna

A new type of graph that has been studied as of late is a small-world graph. This type of graph encapsulates the "six degrees of separation" phenomenon that has been seen in regular social networks. A small-world graph has two main properties. The first is a small diameter, which is simple to check. The other is that a path can be found from a source vertex to a target vertex with high probability while using only local information and exploring a small number of contacts along the way. This second characteristic of this type of graph is more difficult to demonstrate in a graph, and this is the topic of a great deal of current research. My project has attempted to determine whether existing online social networks fit this model of a small-world graph.

My project took information on approximately 200,000 users from the website LiveJournal.com. Using page scraping to gleam information from user profiles, I did analysis on this sample of the graph. The experiments run were used to determine insight into the connectivity of the graph, specifically what things about a vertex make a short path between two users likely. Using this information, I constructed a decentralized searching algorithm to truly demonstrate the small-world property on the entire network.

Writeup

Poster

Main Results