Data Algorithms

Chapter 8. Common Friends

Given a social network with tens of millions of users, in this chapter we’ll implement a MapReduce program to identify “common friends” among all pairs of users. Let U be a set of all users: {U₁, U₂, ..., U_n}. Our goal is to find common friends for every pair of (U_i, U_j) where i ≠ j.

For finding common friends, I provide three solutions:

• MapReduce/Hadoop using primitive data types

• MapReduce/Hadoop using custom data types

• Spark using RDDs

These days most social network sites (such as Facebook, hi5, and LinkedIn) offer services to help you share messages, pictures, and videos among friends. Some sites even offer video chat services to help you connect with friends. By definition, a friend is a person whom one knows, likes, and trusts. For example, Facebook has your list of friends, and friend relationships are bidirectional on the site; if I’m your friend, you’re mine too. Typically social networks precompute calculations when they can to reduce the processing time of requests, and one common processing request involves the “You and Mary (your friend) have 185 friends in common” feature. When you visit someone’s profile, you see a list of friends that you have in common. This list doesn’t change frequently, so it is wasteful for the site to recalculate it every time you visit that person’s profile.

There are many ways to find the common friends between users of a social network. Here are two possible solutions:

• Use a caching strategy and save ...