w.rdc.sae.sina.com.cn:3307|nj41yyozkz|nj41yyozkz 关于weibook.com的关系查找算法实现的猜想 « SAE云计算
Twitter FaceBook
Home
Sina App Engine
illuminati
illuminati
Posted by kobe, and filed under 计算机应用
今天同事问我一事,就是关于这个路子的用户关系查找是怎么实现的,首先说明几点:
1,经过我实验,结果不是100%准确,有些明明存在的6,7步的关系找不出来,报“没有找到相关记录”;即使出了结果,优先级有时误差很大
2,结果不是事先算好的,否则不应该有时计算时间多达10多秒
3,离线做了优化,否则不会有这句话“可能是由于新用户或者我们的数据还不完全”
这个问题的实质可以转化为有向图(关注和粉丝为双向)的任意两个几点之间的最优路径(准确的说是最优的一些路径)问题,可能的实现方案有:
1,floyd算法:
该算法就是标准的图求任意两点之间最短路径的算法,基本原理是利用动态规划解释一下公式,A到C的最短距离一定是
min(A到B的最短距离+B到C的最短距离,A到C的最短距离)
但weibook采用这种办法的可能性是0,有以下几个原因,首先该算法是完全准确的算法,不会出现在数据存在的情况下找不出来关系的问题。另外该算法需要离线海量运算,因为复杂度为O(N^3),假设用户级别为1000万,那么就是1000万的三次方,天文计算了。另外还有一点,该算法的最终结果保存挺费空间的,因为需要N*N的节点都保存自己的路径,也是个海量的数据,所以肯定不可行。
2,迪杰斯卡尔算法
著名的单源最短路径算法,其实也不太可能,主要原因还是计算量大,而且用该算法无法模拟出weibook的效果,即不仅是最短(优)的路径,而是若干个最短(优)的路径。因为该算法是以贪婪的方式每次伸出最短枝,一旦触及到目的地,算法即终止,只能选出唯一一个路径(最优的那个)。所以也不太可能。
3,
Easy提出一个从源和目的两边同时发散出几级好友,然后取交集的做法。该算法的实现相对简单,但问题还在于运算量,如果级数有限制还好说,比如4级,如果没限制就麻烦了,因为是指数增长,运算量太大。而weibook的结果有的就是7级的关系,这样的取交集计算量有点太大了。该方法另一个不可能的原因和迪杰斯卡尔有点类似,就是只能选出同一级的多个最优算法,而不能选出不同级的多个最优算法。因为算法的终止条件就是找到了目的即终止。比如:
找A和B的关系,A的一级粉丝有200个,A的二级粉丝有40000个,B的一级粉丝有100个,二级粉丝有10000个;而双方的二级粉丝有交集。其实就是A=>C=>D=>F=>B
A到B是4级的关系,那么用该算法,如果取最优的N个关系,只能选出同为4级的一些关系,而无法获取到5级、6级的关系。这明显与weibook的效果不一样。如果该算法继续算5级、6级的关系,可以想象,我们无法设计出该算法的终止条件。
4,A*算法
其实该算法还是很适合解决这类问题的,但问题是我们无法仅仅通过粉丝名,预判其关系度。如果我们能通过粉丝名,预判出关系度,那么就可以设计评估函数,然后使A*了,但很遗憾,不能。
5,带剪枝的启发式搜索
我们看weibook的实现,基本有以下特点:
1,有这么一个思路,通过某种逻辑找最优路径,在寻找的过程中,捎带的把一些比较优的路径(如果有的话)也输出。
2,应该有剪枝,如果没有剪枝,则结果肯定是100%准确了,而且我们发现weibook找的这些人,基本都是较活跃的用户,所以可以肯定寻路中会舍弃一些节点。
所以我猜可能是这么实现的:
首先,点和点之间有权值,权值根据用户间的回复、评论等情况做校正,权值越低,表示用户关系越紧密(一定要转换为最短路径问题,因为最长路径问题是NP);从源用户开始,以类似宽度优先的方式做查找,只不过宽度优先的queue换成了优先队列,优先级按照当前路径的权值和从低到高排序。不是所有寻路分支都会进优先队列,过低的权值的节点会舍弃。通过这种方式找到最优路径后,把中间找到的其他路径一并按权值和做排序,最终输出。
=>(2)B =>(2)E =>(1) X
A =>(30)C
=>(1)D =>(10) X
上面表示A有3个粉丝(B、C、D),关系权值分别是2、3、1(权值越低关系越好),B有粉丝E,E有粉丝X;D有粉丝X;我们要找A到X的最优关系。假设我们的剪枝门阀是20,于是C节点在第一层就被剪掉了,于是B和D进入优先队列,按照从低到高为D,B;下层搜索先从D开始,D有一个粉丝直接就到X了,于是找到了一个路径(权值为1+10=11)。但根据优先队列,这时B会冒在优先队列的第一个了(2<11),所以继续从B开始搜索,于是到E到X,这时路径权值为2+2+1=5,此时优先队列没有更优的待选分支,且已经找到X,于是吧找到的两个路径一起输出。一个是最优路径A=>B=>E=>X,另一个是次优路径,A=>D=>X
30th 九 2010
Tags:
illuminati

12 Responses to “关于weibook.com的关系查找算法实现的猜想”

  1. Gang Chen 说:

    很有意思的一个功能。按照你的介绍,其实就是一个在经过剪枝的有向加权网络上的最短路径问题。因为最短路径问题比较成熟,那最主要就是两个东西了:如何剪枝?如何加权?

    剪枝:不仅仅可以根据点的信息剪,还可以根据边的信息剪。权重较低的边及其连接的点都可以剪掉。

    加权:我觉得能利用的信息不仅仅是用户的活跃度和回复、评论等等,地理信息、工作单位、标签都可以利用起来。用户间的权重是可以事先计算好的。

    有意思的东西,应该要@思成 在网上做个报告:)

  2. 姚伯伯 说:

    分析的挺全面的。:)

  3. 小卒 说:

    呵呵,学到了。weibook.com可以出来说说什么算法呀,对于这种海量数据的处理。

  4. 赫连勃勃冥鬼 说:

    学习了

  5. 吞噬星空 说:

    不错顶下。~~~

  6. 颖佳论坛 说:

    厉害,A*算法没接触过,不过大概能看懂你在说什么,呵呵
    课本上学的跟现实应用还是有很大差别的,新浪的用户这么大,运算量就复杂了
    还有,对了,看了那些新浪内部习题,以后可以多发些资料出来哦。
    看不懂。我至少会用心去看,嘿嘿

  7. cozilla 说:

    A*算法在最短路径上还是很不错的,尤其是数据量大的时候。

  8. 葫芦瓢 说:

    一直在想如何做这种关系的程序实现,比如在微博上用六度理论去联系两人,没想到好办法,floyd算法再去取最短路径的最容易想到的.

  9. 蒙古人 说:

    可能是抓取(非API)的时候形成的图的链表表达

  10. 蒙古人 说:

    之后再加权处理,或者启发函数就方便了

  11. 谢良 说:

    这个weibobook.com怎么访问过去?能给个链接么,想看下来印证学习楼主的想法

  12. kobe 说:

    已经被封杀了,众所周知的原因

Leave a Reply

 
Designed by