用过各种社交平台(如QQ、微博、朋友网等等)的小伙伴应该都知道有一个叫 "可能认识" 或者 "好友推荐" 的功能(如下图)。它的算法主要是根据你们之间的共同好友数进行推荐，当然也有其他如爱好、特长等等。共同好友的数量越多，表明你们可能认识，系统便会自动推荐。今天我将向大家介绍如何使用MapReduce计算共同好友
算法
假设有以下好友列表，A的好友有B,C,D,F,E,O; B的好友有A,C,E,K 以此类推那我们要如何算出A-O用户每个用户之间的共同好友呢？
A:B,C,D,F,E,OB:A,C,E,KC:F,A,D,ID:A,E,F,LE:B,C,D,M,LF:A,B,C,D,E,O,MG:A,C,D,E,FH:A,C,D,E,OI:A,OJ:B,OK:A,C,DL:D,E,FM:E,F,GO:A,H,I,J
下面我们将演示分步计算，思路主要如下：先算出某个用户是哪些用户的共同好友，如A是B,C,D,E等的共同好友。遍历B,C,D,E两两配对如(B-C共同好友A，注意防止重复B-C,C-B)作为key放松给reduce端，这样reduce就会收到所有B-C的共同好友的集合。可能到这里你还不太清楚怎么回事，下面我给大家画一个图。
代码演示
由上可知，此次计算由两步组成，因此需要两个MapReduce程序先后执行
第一步：通过mapreduce得到 某个用户是哪些用户的共同好友。
public class FriendsDemoStepOneDriver { static class FriendsDemoStepOneMapper extends Mapper<LongWritable, Text, Text, Text> { @Override protected void map(LongWritable key, Text value, Context context) throws IOException, InterruptedException { String line = value.toString(); String[] split = line.split(":"); String user = split[0]; String[] friends = split[1].split(","); for (String friend : friends) {// 输出友人，人。 这样的就可以得到哪个人是哪些人的共同朋友 context.write(new Text(friend),new Text(user)); } } } static class FriendsDemoStepOneReducer extends Reducer<Text,Text,Text,Text>{ @Override protected void reduce(Text key, Iterable<Text> values, Context context) throws IOException, InterruptedException { StringBuilder sb = new StringBuilder(); for (Text person : values) { sb.append(person+","); } context.write(key,new Text(sb.toString())); } } public static void main(String[] args) throws IOException, ClassNotFoundException, InterruptedException { Configuration conf = new Configuration(); conf.set("mapreduce.framework.name","local"); conf.set("fs.defaultFS","file:///"); Job job = Job.getInstance(conf); job.setJarByClass(FriendsDemoStepOneDriver.class); job.setMapperClass(FriendsDemoStepOneMapper.class); job.setReducerClass(FriendsDemoStepOneReducer.class); job.setOutputKeyClass(Text.class); job.setOutputValueClass(Text.class); FileInputFormat.setInputPaths(job,new Path("/Users/kris/Downloads/mapreduce/friends/friends.txt")); FileOutputFormat.setOutputPath(job,new Path("/Users/kris/Downloads/mapreduce/friends/output")); boolean completion = job.waitForCompletion(true); System.out.println(completion); }}
运行的到的结果如下：
由图可见:I,K,C,B,G,F,H,O,D都有好友A；A,F,J,E都有好友B。接下来我们只需组合这些拥有相同的好友的用户，
作为key发送给reduce,由reduce端聚合d得到所有共同的好友
/** * 遍历有同个好友的用户的列表进行组合，得到两人的共同好友 */public class FriendsDemoStepTwoDriver { static class FriendDemoStepTwoMapper extends Mapper<LongWritable, Text, Text, Text> { @Override protected void map(LongWritable key, Text value, Context context) throws IOException, InterruptedException { String line = value.toString(); String[] split = line.split("\t"); String friend = split[0]; String[] persons = split[1].split(","); Arrays.sort(persons); for (int i = 0; i < persons.length-1; i++) { for (int i1 = i+1; i1 < persons.length; i1++) { context.write(new Text(persons[i]+"--"+persons[i1]),new Text(friend)); } } } } static class FriendDemoStepTwoReducer extends Reducer<Text, Text, Text, Text> { @Override protected void reduce(Text key, Iterable<Text> values, Context context) throws IOException, InterruptedException { StringBuilder sb = new StringBuilder(); for (Text friend : values) { sb.append(friend + ","); } context.write(key,new Text(sb.toString())); } } public static void main(String[] args) throws IOException, ClassNotFoundException, InterruptedException { Configuration conf = new Configuration(); conf.set("mapreduce.framework.name","local"); conf.set("fs.defaultFS","file:///"); Job job = Job.getInstance(conf); job.setJarByClass(FriendsDemoStepOneDriver.class); job.setMapperClass(FriendDemoStepTwoMapper.class); job.setReducerClass(FriendDemoStepTwoReducer.class); job.setOutputKeyClass(Text.class); job.setOutputValueClass(Text.class); FileInputFormat.setInputPaths(job,new Path("/Users/kris/Downloads/mapreduce/friends/output")); FileOutputFormat.setOutputPath(job,new Path("/Users/kris/Downloads/mapreduce/friends/output2")); boolean completion = job.waitForCompletion(true); System.out.println(completion); }}
得到的结果如下:
如图，我们就得到了拥有共同好友的用户列表及其对应关系，在实际场景中再根据用户关系(如是否已经是好友)进行过滤，在前端展示，就形成了我们所看到"可能认识"或者"好友推荐"啦～
今天给大家分享的好友推荐算法就是这些，今天的只是一个小小的案例，现实场景中的运算肯定要比这个复杂的多，但是思路和方向基本一致，如果有更好的建议或算法，欢迎与小吴一起讨论喔～如果您喜欢这篇文章的话记得like,share,comment喔(^^)
本文由博客一文多发平台 OpenWrite 发布！