Small-world phenomena were initially studied in the 1960s through a series of social network experiments, and are, as evidenced by the game "The six degrees of Kevin Bacon", even part of our pop-culture. Recently, mathematicians and physicists have shown that most small-world phenomena are expected consequences of the mathematical properties of certain networks -- known as {\em small-world networks}. In this paper, we survey some recent mathematical developments dealing with small-world networks, as well as present a new small-world network model and discuss some new ideas for decentralized searching. The goal is to give the reader a sense of the importance of small-world networks, and some of the useful applications dealing with these networks.

Author Bio

I wrote this article this summer while working on a grant from the Wyoming NASA Space Grant Consortium. However, some of the work dates to this past fall 2003 semester. So work in this paper started in September 2003 and ended in August 2004. The inital nine months of this research was funded by two seperate grants from the NSF Experimental Program to Stimulate Competitive Research (EPSCoR). This upcoming fall semester of 2004 will be the start of my fourth and final year as an undergraduate. I attend the University of Wyoming, however I am currently on an exchange to Utrecht, The Netherlands. I am double majoring in computer science and mathematics, and hope to enter a PhD program in theoretical computer science upon completion of my bachelors degree.