Finding Friends: Part 1

Mathematical Moments from the American Mathematical Society

Facebook has over 700 million users with almost 70 billion connections. The hard part isn.t people making friends; rather it.s Facebook.s computers storing and accessing relevant data, including information about friends of friends. The latter is important for recommendations to users (People You May Know). Much of this work involves computer science, but mathematics also plays a significant role. Subjects such as linear programming and graph theory help cut in half the time needed to determine a person.s friends of friends and reduce network traffic on Facebook.s machines by about two-thirds. What.s not to like? The probability of people being friends tends to decrease as the distance between them increases. This makes sense in the physical world, but it.s true in the digital world as well. Yet, despite this, the enormous network of Facebook users is an example of a small-world network. The average distance between Facebook users the number of friend-links to connect people is less than five. And even though the collection of users and their connections may look chaotic, the network actually has a good deal of structure. For example, it.s searchable. That is, two people who are, say, five friend-links away, could likely navigate from one person to the other by knowing only the friends at each point (but not knowing anyone.s friends of friends). For More Information: Networks, Crowds, and Markets: Reasoning about a Highly Connected World, David Easley and Jon Kleinberg, 2010.