有很多用户,用户之间存在好友关系。
现在要针对某一个用户,算出跟该用户共同好友数最多的一些用户,按照共同好友数递减排列。
类似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/
分享到:
相关推荐
hadoop之MapReduce实现二度好友算法,包含输入数据demo,完整运算代码,在windows10下成功运行,输出结果为cat hello:2,hadoop:2,mr:1,world:1类似。
有关好友推荐的各种算法,是一个人的论文~ 觉得写的还不错
基于系统过滤的推荐算法,实现user-user、item-item推荐,计算欧几里德距离、皮尔逊相关度。
好友推荐算法方面计算机学报的论文,都比较好,本人亲自看过的。
针对基于社区划分的潜在好友推荐算法FRCD运行速度慢的问题,提出了一种基于社区划分的多线程潜在好友推荐算法MTFRCD。该算法在网络拓扑图上利用多线程技术寻找核心关系子网,以核心关系子网作为标签种子节点,使用多...
基于关联规则的社交网络好友推荐算法,向程冠,熊世桓,提出了一种基于关联规则的社交网络好友推荐算法,在进行好友推荐时,考虑现实社交活动中“志趣相投”的好友常常会关注相同的人和
考虑了用户之间的链接和内容信息,提出了一种结合非负矩阵因式分解的主题社区好友推荐算法(T-NMF)。该算法给出了主题社区和综合相似度计算方法,产生好友推荐列表。实验表明,该算法可以更好地反映用户的偏好,...
2013-12-4最新亲测可用好友hash算法
一种社交网络下的好友推荐算法,张萌哲,张成文,基于社交关系的社交网络下的好友推荐算法的利用用户之间的共同好友或粉丝的重合度来计算用户相似性,忽略了用户与的现有好友中的
#资源达人分享计划#
推荐系统教程_第7周 社交网络好友推荐,图算法,在图数据库Neo4j上的实现.rar
【资源说明】 1、该资源包括项目的全部源码,下载可以直接使用! 2、本项目适合作为计算机、数学、电子信息等专业的课程设计、期末...基于Spark GraphX+PageRank算法的仿微博用户好友的分布式推荐系统源码+项目说明.zip
社交网络中潜在好友推荐算法研究.pdf
已知右鸽有n个好友,但是他们的钓鱼水平参差不齐(能力值不同),毋庸置疑,他想要钓到尽可能多的鱼,因此,他会选择能力尽可能强的好友。 还有一个问题就是,右鸽必须从家里出发挨个去叫好友,当然了,他可不想走太...
社交网络中的信任推荐和好友搜索过滤算法研究
基于Spark+PageRank算法构建仿微博用户好友的分布式推荐系统.zip 1、该资源内项目代码经过严格调试,下载即用确保可以运行! 2、该资源适合计算机相关专业(如计科、人工智能、大数据、数学、电子信息等)正在做课程...
提出了一种基于关联规则的社交网络好友推荐算法,在进行好友推荐时,考虑现实社交活动中“志趣相投”的好友常常会关注相同的人和事,网络社交中的好友也常常会关注相同的“人”和“事”,将“关注”看成一条交易记录,把...
基于决策树的学术性社交网络好友推荐算法
使用Spark GraphX基于PageRank算法构建一个仿微博用户好友的分布式推荐系统。 注意事项 代码中文件的路径用户可以修改为自己数据所处的位置。 需要启动hadoop集群,这里使用了hadoop2.5.0-cdh5.3.6。 代码执行顺序:...
1、资源内容: 2、代码特点:内含运行结果,不会运行可私信,参数化编程、...在社交网络中,PageRank算法有着广泛的应用,因此,本篇文章主要介绍其原理以及实战进行好友的推荐 ,最后实战项目的全部代码会在GitHub上开