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