O'Reilly logo

Data Algorithms by Mahmoud Parsian

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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: {U1, U2, ..., Un}. Our goal is to find common friends for every pair of (Ui, Uj) where ij.

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required