Social media provides us with recommendations and suggestions for new friends. Most such platforms use the Friends-Of-Friends (fof) algorithm.

Friends-Of-Friends (fof) is implemented using the shortest-path algorithm.

It helps social media platforms to broaden their network of users. 

The friends-of-friends algorithm suggests friends that users may know but who aren’t part of their immediate network.

Two Map-Reduce jobs are required to calculate the FoFs for each user in a social network. The first one calculates the common friends for each user and the second job sorts the common friends by number of connections to your friends.

Now you can suggest friends from a sorted list. 

FoF:

Our goal is to determine all fofs and order them by number of friends in common.

In this case expected results have jyo as the first FoF recommendation followed by vir then kai.

The text file that represents social graph is:

tar vir sac kai jyo

pra sac vir jyo tar

sac kai jyo pra

vir sac kai jyo

Jyo pra kai sac vir tar

First MapReduce:

Map(nodeName,node)

for all adjnode in node.adjacencyList do

emit(lexicographicallyOrderTuple(nodeName,adjnodeName),1)

for all adj2node in node.adjacencyList do

If the tuple(adjnodeName,adj2nodeName) hasn’t already been

emitted then

emit(lexicographicallyOrderTuple(adjnodeName,adj2nodeName),1)

Reduce(tuple(node1Name,node2Name),[i1,i2,….])

commonFriends=0

alreadyFriends=false

for all i in counts[i1,i2….] do

If i=1 then

alreadyFriends=true

commonFriends=commonFriends+1

If alreadyFriends not true then

emit(tuple(node1Name,node2Name),commonFriends)

Output of first job is against graph is 

Sac jyo 3

Pra tar 1

Pra sac 2

Pra kai 2

Second MapReduce:

Map(tuple(node1Name,node2Name),commonFriends)

emit(tuple(node1Name,commonFriends),tuple(node2Name,commonFriends))

emit(tuple(node2Name,commonFriends),tuple(node1Name,commonFriends))

Partitioner(tuple(nodeName,commonFriends))

Partition by nodeName

Sort(tuple(nodeName,commonFriends))

sort by tuple(nodeName,commonFriends)

Reduce(tuple(nodeName,commonfriends),[tuple1,tuple2…..]

potentialFriends=0

For all t in [tuple1,tuple2….]

potentialFriends=tuple(t.name,t.commonFriends)

emit(nodeName,potentialFriends)

Output of second MapReduce job will be like

Sac jyo : 3

Pra jyo : 2 vir : 2 tar : 1