用过各种社交平台(如QQ、微博、朋友网等等)的小伙伴应该都知道有一个叫 "可能认识" 或者 "好友推荐" 的功能(如下图)。它的算法主要是根据你们之间的共同好友数进行推荐，当然也有其他如爱好、特长等等。共同好友的数量越多，表明你们可能认识，系统便会自动推荐。今天我将向大家介绍如何使用MapReduce计算共同好友

算法

假设有以下好友列表，A的好友有B,C,D,F,E,O;   B的好友有A,C,E,K 以此类推
那我们要如何算出A-O用户每个用户之间的共同好友呢？

A:B,C,D,F,E,O
B:A,C,E,K
C:F,A,D,I
D:A,E,F,L
E:B,C,D,M,L
F:A,B,C,D,E,O,M
G:A,C,D,E,F
H:A,C,D,E,O
I:A,O
J:B,O
K:A,C,D
L:D,E,F
M:E,F,G
O: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喔(^^)

扫码关注我们

微信号：SRE实战

拒绝背锅 运筹帷幄

×

选择打赏方式：

微信 QQ钱包 支付宝

打赏

打赏

打赏

多少都是心意！谢谢大家！！！