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.