Finding Friends: Part 1

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.