Shulou(Shulou.com)05/31 Report--

This article mainly explains "how to use Map/Reduce to make friend recommendation". The content of the article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "how to use Map/Reduce to do friend recommendation".

Every SNS website has a feature, which is friend recommendation (or Follower recommendation). For example, "people you might know" appear on Renren. How to achieve it, there is a very simple way. If Xiaogang and Xiaoming are not good friends, but they have a lot of common friends. Then it can be considered that An and B are likely to know each other.

How to use Map/Reduce to make friend recommendation

From the point of view of graph theory, it is to first list the friends of all the friends of a person (marked as Xiao A) to find out how many paths of length 2 are between Xiao An and these people. Sort the number of these paths and find the highest ones.

So the task of our Map/Reduce is to find out everyone's ten Top "recommended friends".

The picture of social network is generally very simple. Let's assume that the input is sorted by name.

"ricky" = > ["jay", "peter", "phyllis"]

"peter" = > ["dave", "jack", "ricky", "susan"]

We use two rounds of Map/Reduce tasks to do this.

The first round of MR missions

The purpose of this task is to calculate the number of paths between each pair of people whose distance is 2.

In the Map function, we first make a Cartesian product of each pair of friends, which is not clear, for example, such as

"ricky" = > ["jay", "john", "mitch"]

So the result is

["jay", "john"], ["jay", "mitch"], ["john", "mitch"]

They all met through ricky matchmaking. Filter out the combinations that are already friends, and then sort them out. Pass it to Reducer.

In the Reduce function, the same combination must be passed to Reducer. So Reducer just needs to count several of the same combinations and pass them on to him.

Input record... Person-> connection_list

E.g. "ricky" = > ["jay", "john", "mitch", "peter"]

Also the connection list is sorted by alphabetical order

Def map (person, connection_list)

# Compute a cartesian product using nested loops

For each friend1 in connection_list

# Eliminate all 2-degree pairs if they already

# have an one-degree connection

Emit ([person, friend1, 0])

For each friend2 > friend1 in connection_list

Emit ([friend1, friend2, 1], 1)

Def partition (key)

# use the first two elements of the key to choose a reducer

Return super.partition ([key [0], key [1]])

Def reduce (person_pair, frequency_list)

# Check if this is a new pair

If @ current_pair! = [person_pair [0], person_pair [1]]

@ current_pair = [person_pair [0], person_pair [1]]

# Skip all subsequent pairs if these two person

# already know each other

@ skip = true if person_pair [2] = = 0

If! skip

Path_count = 0

For each count in frequency_list

Path_count + = count

Emit (person_pair, path_count)

Output record... Person_pair = > path_count

E.g. ["jay", "john"] = > 5

How to use Map/Reduce to make friend recommendation

The second round of MR mission

The purpose of this round of MR tasks is to list friends whose distance is 2 each and find out how many paths they have directly.

In the Map function, we rearrange each set of data to ensure that a person's information falls on a reducer.

In the Reduce function, just order the number of paths between each person's possible friends.

Input record = Output record of round 1

Def map (person_pair, path_count)

Emit ([person_pair [0], path_count], person_pair [1])

Def partition (key)

# use the first element of the key to choose a reducer

Return super.partition (key [0])

Def reduce (connection_count_pair, candidate_list)

# Check if this is a new person

If @ current_person! = connection_count_pair [0]

Emit (@ current_person, @ top_ten)

@ top_ten = []

@ current_person = connection_count_pair [0]

# Pick the top ten candidates to connect with

If @ top_ten.size

ten

Output record... Person-> candidate_count_list

E.g. "ricky" = > [["jay", 5], ["peter", 3]...]

Follower recommendation

What if I want to make a Follower recommendation instead of a friend recommendation?

It's simple. Just change the MR task in the first step to find the Cartesian product of "Follow relation" and "Followed" relation. There is no pseudo code here.

Thank you for your reading, the above is "how to use Map/Reduce to do friend recommendation" content, after the study of this article, I believe you have a deeper understanding of how to use Map/Reduce to do friend recommendation this problem, the specific use also needs to be verified by practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.