Social network sites such as LinkedIn and Facebook use the FoF algorithm to help users broaden their networks.
The key ingredient to success with this approach is to order the FoFs by the number of common friends, which increases the chances that the user knows the FoF.
Two MapReduce jobs are required to calculate the FoFs for each user in a social network. The first job calculates the common friends for each user, and the second job sorts the common friends by the number of connections to your friends
2.Example : How to implement the FoF algorithm in MapReduce.
A -> B C D
B -> A C D E
C -> A B D E
D -> A B C E
E -> B C D
Mapper 1 output of A -> B C D
(A,B) -> (B C D)
(A,C) -> (B C D)
(A,D) -> (B C D)
Mapper 2 output of B -> A C D E
(A,B) -> (A C D E)
(B,C) -> (A C D E)
(B,D) -> (A C D E)
(B,E) -> (A C D E)
Mapper 3 output of C -> A B D E
(A,C) -> (A B D E)
(B,C) -> (A B D E)
(C,D) -> (A B D E)
(C,E) -> (A B D E)
Mapper 4 output of D -> A B C E
(A,D) -> (A B C E)
(B,D) -> (A B C E)
(C,D) -> (A B C E)
(D,E) -> (A B C E)
Mapper 5 output of E -> B C D
(B,E) -> (B C D)
(C,E) -> (B C D)
(D,E) -> (B C D)
Shuffle Or Group:
(A,B) -> (A C D E)
(A,B) -> (B C D)
-------------------------
(A,B) -> (A C D E) (B C D)
(A,C) -> (B C D)
(A,C) -> (A B D E)
-------------------------
(A,C) -> (A B D E) (B C D)
(A,D) -> (B C D)
(A,D) -> (A B C E)
-------------------------
(A,D) -> (A B C E) (B C D)
(B,C) -> (A C D E)
(B,C) -> (A B D E)
-------------------------
(B,C) -> (A B D E) (A C D E)
(B,D) -> (A C D E)
(B,D) -> (A B C E)
-------------------------
(B,D) -> (A B C E) (A C D E)
(B,E) -> (A C D E)
(B,E) -> (B C D)
-------------------------
(B,E) -> (A C D E) (B C D)
(C,D) -> (A B D E)
(C,D) -> (A B C E)
-------------------------
(C,D) -> (A B D E) (A B C E)
(C,E) -> (A B D E)
(C,E) -> (B C D)
-------------------------
(C,E) -> (A B D E) (B C D)
(D,E) -> (A B C E)
(D,E) -> (B C D)
-------------------------
(D,E) -> (A B C E) (B C D)
Reducer:
(A,B) -> (A C D E) (B C D)
The common pair is
(A,B) -> (C D)
(A,C) -> (A B D E) (B C D)
The common pair is
(A,C) -> (B D)
(A,D) -> (A B C E) (B C D)
The common pair is
(A,D) -> (B C )
(B,C) -> (A B D E) (A C D E)
The common pair is
(B,C) -> (A D E)
(B,D) -> (A B C E) (A C D E)
The common pair is
(B,D) -> (A C E)
(B,E) -> (A C D E) (B C D)
The common pair is
(B,E) -> (C D)
(C,D) -> (A B D E) (A B C E)
The common pair is
(C,D) -> (A B E)
(C,E) -> (A B D E) (B C D)
The common pair is
(C,E) -> (B D)
(D,E) -> (A B C E) (B C D)
The common pair is
(D,E) -> (B C)
No comments:
Post a Comment