好友算法

有很多用户，用户之间存在好友关系。
现在要针对某一个用户，算出跟该用户共同好友数最多的一些用户，按照共同好友数递减排列。
类似qq空间，facebook的好友推荐这种。
难道要遍历一遍所有用户么?


1. 最简单的图算法，遍历你所有的好友节点，取出每个好友的好友（二度好友）的列表，然后按二度好友的ID为key做计数操作，最后按计数排序就行了。遍历的用户数是你的二度好友的人数。
按这个思路，相信目前流行的图数据库（比如Neo4j）都能实现你的需求。

2.我的想法是，利用集合的运算进行求解比较快捷。所有的人构成一个S全集，每一个用户的好友就是全集中的一个子集，而你和所有的好友求共同好友就是子集与子集的求交操作。交集最大的那个就是你所求的好友。
利用逻辑运算的按位与运算求集合的交集是很快当的。哈哈！

3.如果查询用户1,2之间的共同好友 也就是像人人那样查看
1->X->2这种关系 由于好友表只是一度关系 查询两度遍历下就行了

select friend_id from xxx where user_id=1 and friend_id in(select friend_id from xxx where user_id=2)


===============================================
好友推荐


目前看到的现象是，新浪微博在「你可能感兴趣的人」这一块推荐质量还可以。和半年前、一年前相比，持续改进的效果很明显。

根据这个现象，外面的人很难反推出他们用了哪些算法。但是相信推荐引擎的基本算法，新浪都有用到，
包括比较容易想到的共同好友（关系传递）、地理位置、教育/工作信息、共同标签、共同兴趣（都保存哪
些话题搜索等）等。

IBM developerWorks 有三篇不错的文章讲推荐引擎的原理及应用（http://j.mp/oJS63C），原理
不外乎这些，主要还是看推荐系统层面的产品设计，和工程师的不断调试改进。数据驱动推荐质量的改进。


1.有共同好友
2.你关注的人中，有多人也关注了他。
3.还有与你有类似标签的人
4.hybrid recommendation algorithm

共同好友算法
好友算法
推荐好友算法

深入了解 Dojo 的服务器推送技术

 

 

 

 

 

=========================================================

 

SNS网站都有一个功能，就是好友推荐(或者Follower推荐)。例如，在人人网上出现的“你可能认识的人”。怎么来实现呢，有一个很简单的办法。如果小刚和小明不是好友，但是他们有很多的共同好友。那么可以认为，A和B很可能相识。

从图论的讲法上看，就是先列出一个人(记为小A)的所有朋友的朋友，在寻找小A和这些人之间有多少长度为2的通路。将这些通路数排序，寻找最高的那几个就可以了。

所以我们的Map/Reduce的任务就是：找出所有人的十个Top“推荐好友”。

社会化网络的图一般都很简单。我们假设输入是按name排序的。

    "ricky" => ["jay", "peter", "phyllis"]
    "peter" => ["dave", "jack", "ricky", "susan"]

我们使用两轮Map/Reduce任务来完成这个操作。



第一轮MR任务

这个任务的目的是计算每一对距离是2的人之间的通路数。
    在Map函数中，我们先将每对朋友做一个笛卡尔乘积，说的不大清楚，举个例子，比如
        "ricky" => ["jay", "john", "mitch"]
    那么结果就是
         ["jay", "john"], ["jay", "mitch"], ["john", "mitch"]
    他们都是通过ricky牵线搭桥认识的。将已经是朋友的组合筛选掉，再排好序。传给Reducer。
    在Reduce函数中, 相同的组合必定会传给Reducer。所以Reducer只要数好有几个相同的组合传给他就行了.

Input record ... person -> connection_list

    e.g. "ricky" => ["jay", "john", "mitch", "peter"]
    also the connection list is sorted by alphabetical order
    
    def map(person, connection_list)
      # Compute a cartesian product using nested loops
      for each friend1 in connection_list
         # Eliminate all 2-degree pairs if they already
         # have a one-degree connection
         emit([person, friend1, 0])
         for each friend2 > friend1 in connection_list
             emit([friend1, friend2, 1],  1)
    
    def partition(key)
      #use the first two elements of the key to choose a reducer
      return super.partition([key[0], key[1]])
    
    def reduce(person_pair, frequency_list)
      # Check if this is a new pair
      if @current_pair != [person_pair[0], person_pair[1]]
          @current_pair = [person_pair[0], person_pair[1]]
          # Skip all subsequent pairs if these two person
          # already know each other
          @skip = true if person_pair[2] == 0
    
      if !skip
          path_count = 0
          for each count in frequency_list
              path_count += count
          emit(person_pair, path_count)
    
    Output record ... person_pair => path_count
    e.g. ["jay", "john"] => 5

第二轮MR任务

这一轮的MR任务是为了列出每个人距离为2的好友，查出他们直接究竟有几条路径。

    在Map函数中，我们将每一组数据重新排列，保证一个人信息落在一个reducer上
    在Reduce函数中，只要将每个人的可能好友之间的路径数排个序就可以了.

Input record = Output record of round 1

    
    def map(person_pair, path_count)
      emit([person_pair[0], path_count], person_pair[1])
    
    def partition(key)
      #use the first element of the key to choose a reducer
      return super.partition(key[0])
    
    def reduce(connection_count_pair, candidate_list)
      # Check if this is a new person
      if @current_person != connection_count_pair[0]
          emit(@current_person, @top_ten)
          @top_ten = []
          @current_person = connection_count_pair[0]
    
      #Pick the top ten candidates to connect with
      if @top_ten.size < 10
          for each candidate in candidate_list
              @top_ten.append([candidate, connection_count_pair[1]])
              break if @pick_count > 10
    
    Output record ... person -> candidate_count_list
    
    e.g.  "ricky" => [["jay", 5],  ["peter", 3] ...]

Follower推荐
如果我想要做Follower推荐而不是好友推荐怎么办呢？
很简单。只要将第一步的MR任务改为求“Follow关系”和“Followed”关系的笛卡尔乘积就可以了。这里就不列伪码了。

参考地址：http://horicky.blogspot.com/