Show all work. I only need complete explanation and no code. We are going to loo
ID: 3555275 • Letter: S
Question
Show all work. I only need complete explanation and no code.
We are going to look at the problem of finding the common neighbors for all pairs of nodes in an input graph using MapReduce. Assume that the input graph is available as an adjacency list. Refer to the figure for an example of the adjacency list representation of a graph. ABCDE BADE CAF DABF EABF FCDE The common neighbors between node A and B for this graph can be computed using an intersection of their corresponding adjacency lists i.e. [B C D E] n [A D E] = [D E]. Describe how you would design a mapper and a reducer for finding the common neighbors for all unique pairs (pairs [A,B] and [B,A] are essentially the same) of nodes in a large graph. Now how would you modify your previous solution to solve the friends of friends problem in a social network. The objective is to output for each node n, the set of nodes which are either neighbors of n or share a common friend with n. ie. A [B C D E F] B [A D E CFJ... Hint: You can use more than one map-reduce jobs for this problem.Explanation / Answer
Q1.
1 . Mapper <LongIntWritable Key ,Text Value>
In the mapper method, taking input line by line:
Pass as KEY every pair possible in the scanned line & rest as the VALUE to the reducer. Please Note this pair should be alphabetically arranged(Since AB = BA ):
Eg:
For A B C D E
B A D E
The Keys and subsequent values would be:
Key Value
AB C D E
AC B D E
AD B C E
AE B C D
AB D E
BD A E
BE A D
2. Reducer<Text Key, Value Key>
Now reducer would receive a Key and subsequent list of Values:
If the count of values received in list is 1. There is no common friend between the two.
Else the count of values would be two. This is attributed to the fact
A B C D E
B A D E
Can have maximum of two AB as keys One Coming from the first line(where A is the node and B is a neighbor) .Second coming from the Second line(where B is a node and A is a neighbor)
Now We Have two Value Strings for AB as a key:
C D E and DE
Here we can find a longest common subsequence. That is If there are two strings
Say,
String>ABIUHBCCDDE,
String two = MANBBKCTYYCMDKMDE
Here Longest Common Subsequence is: ABBCCDDE
Since , M,N,KT,Y in string2 and I,U,H are not common between the two.
Similarly,
Longest Common Subsequence between C D E and D E would be D E(this would also consider the space as it is treated as a character of string)
The Code For The Longest Common Sub Sequence is:
public class LCS {
public static void main(String[] args) {
int i,j;
String X = "C D A E F"; /* String X */
String Y = "W D B C E G"; /* String Y */
/* initialize the n x m matrix B and C for dynamic programming
* B[i][j] stores the directions, C[i][j] stores the length of LCS of
* X[0..i-1] and Y[0..j-1]
*/
int n = X.length();
int m = Y.length();
int[][] C = new int[n+1][m+1];
int[][] B = new int[n+1][m+1];
/* C[i][0] = 0 for 0<=i<=n */
for (i = 0; i <= n; i++) {
C[i][0] = 0;
}
/* C[0][j] = 0 for 0<=j<=m */
for (j = 0; j <= m; j++) {
C[0][j] = 0;
}
/* dynamic programming */
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
if (X.charAt(i-1) == Y.charAt(j-1)) {
C[i][j]=C[i-1][j-1]+1;
B[i][j]=1; /* diagonal */
}
else if (C[i-1][j]>=C[i][j-1]) {
C[i][j]=C[i-1][j];
B[i][j] = 2; /* down */
}
else {
C[i][j]=C[i][j-1];
B[i][j]=3; /* forword */
}
}
}
/* Backtracking */
String lcs = new String();
i=n;
j=m;
while (i!=0 && j!=0) {
if (B[i][j] ==1) { /* diagonal */
lcs =X.charAt(i-1) + lcs;
i = i - 1;
j = j - 1;
}
if (B[i][j] == 2) { /* up */
i = i - 1;
}
if (B[i][j] == 3) { /* backword */
j = j - 1;
}
}
lcs=lcs.trim();
/* print out the result */
System.out.println("String X is " + X);
System.out.println("String Y is " + Y);
System.out.println("The length of LCS is " + lcs.length());
System.out.println("The LCS is " + lcs);
}
}
You can make this code for finding LCS a separate method of include it in reduce method itself.
Now You Can Output :
Key=Received Key From Mapper
Value= Longest Common Subsequence
from the reducer and get the final outp ut.
Alternatively,
Using these two strings you can use the following code sniplet,
Set set1 = new HashSet();
Set set2 = new HashSet();
//add elements to set1using first Value string
set1.add("A");
set1.add("B");
set1.add("A");
set1.add("A");
//add elements to set2 using the second Value string
set2.add("C");
set2.add("B");
set2.add("E");
set2.add("F");
//Finally use this to find the intersection of two sets ,set 1 will
//Now have set1 Intersection set2
set1.retainAll(set12);
Q2. This would require a Mapper and Chained Reducers.
First Map-Reduce Job
1 . Mapper<LongIntWritable Key ,Text Value>
Mapper now in addition to the output as mentioned above should also output the line inputted.
That is,
Eg: for
A B C D E
The mapper output would now be:
Key Value
A B C D E
AB C D E
AC B D E
AD B C E
AE B C D
Note: The first <K,V> pair is same as the input line.
2. Reducer1<Text Key,Text Value>
Reducer will now check Key length.
If Key Length is =1, Output the <K,V> pair as it is.
If Key Length =2