六度分隔与最短路径 阴



更多



【最短路径】  åœ†æ˜Žå›­çš„北部有一个迷宫,据说古时候每次有庆典在圆明园的时候,皇帝会派一些宫女走迷宫,看谁最先走到迷宫内的亭子,会有不错的奖赏。  è¿·å®«é—®é¢˜å¯¹æ•°å­¦å®¶ä»¬æ¥è®²è™½ç„¶æ˜¯å°å„¿ç§‘但在计算机课程上却非常重要,因为不同的求解会涉及到递归,广度优先和深度优先等算法。  è¿·å®«æ¯•ç«Ÿæ˜¯ä¸€ä¸ªæ”¾ç½®åœ¨2维空间的有限联系的网络,也就是说,迷宫里的每一个点,最多只和周围的4个点(上下左右)发生关系,而且这些点的位置是固定的。  

六度分割通常用来描述一个广阔的社会网路(SN),现在大部分的社会网路服务都提供了搜索功能,即搜索出一个用户到达另外一个用户的最短路径,也就是找出这两个用户之间通过最少的用户的链接。  ä¸€èˆ¬çš„SN提供的搜索都是4度的,也就是例如A-B-C-D-E 称为4度的分隔。提供5度搜索和6度搜索的几乎寥寥无几,当然一方面是5,6度分隔的用户很少,大部分的用户都应该在4度内,另外一个方面是5,6度分隔的搜索在实际计算上也涉及非常大的运算量。  

【SN搜索算法】  å¦‚果说寻找两个人之间的最小分隔的路径和寻找最短路径可以类比,那么唯一不同的是SN上每个节点的联系可以非常的广阔,不只是上下左右,而是十个甚至上百个联系。这是是一个多维空间内的最短路径的寻找。假设一个用户平均有n个好友,那么粗略估计一个用户的4度好友大约有n×n×n×n+n×n×n+n×n+n ~ n^4,无疑是一个非常恐怖的数目。因此采用传统的递归的方法显然是不大现实的。  å½“然,事情并非这么麻烦,有简洁的方法可以加快找到用户之间的最小分隔:不单是从一个用户搜索,而是从两个用户同时搜索,而看两个用户的2度之内的用户是否有相同: A-B-C E-D-C Aå’ŒE的处在在两度分隔的用户基本上数目估计都在n的平方。问题变成了比较n^2å’Œn^2之间有没有相同,这个计算的时间等同于2×n^2的排序所需要的时间。

【SN索引】  é‚£ä¹ˆèƒ½å¦ç»§ç»­åŠ å¿«é€Ÿåº¦ï¼Ÿ 当然可以,可以提前对用户的好友进行索引,对好友的好友进行索引,这样在未来进行关系的搜索时会大大加快:  A: {A1} {A2} A1为A的好友的集合,A2为A的好友的好友的集合 E: {E1} {E2}  é‚£ä¹ˆ 1度分隔为: A 属于{E1},等同于E属于 {A1} 2度分隔为: A 属于{E2},等同于E属于 {A2},{A1}{E1}有共同项。 3度分隔为: {A1} ï½›E2}有共同项,等同于A属于 {E2} 4度分隔为: {A2} ï½›E2}有共同项  

【SN关系的更新】  å½“然,发现是一个核心问题,另外一个问题就是更新,因为SN的关系不会是一成不变的,在一个活跃的SN社区里,每天用户之间的关系的更新更是可观。这里只考虑关系添加的例子:  A: {A1} {A2}  E: {E1} {E2}  å½“A 与 E 直接建立了好友关系后,应该说整合系统的关系全都变化了,因为这个新的关系一定会导致一些关系的短路,从而导致很多现有的关系的调整。但是因为我们只存储2度分隔以内的关系,也只关心两度分隔以内的关系,因此当发生了一个新的关系后,2度内关系的变化一定是Aå’ŒE本身或者他们的一度关系的用户,再远的用户将不受这个关系的影响。  å› æ­¤é¦–å…ˆ 所有{A1}的元素的二度分隔集合里要加上E,所有{E1}的元素的二度分隔集合里要加上A。  ç„¶åŽæ˜¯äºŒåº¦çš„修正。分别加上对方的1度。 {A2} = {A2 + E1} {E2} = {E2 + A1}  æœ€åŽæ˜¯ä¸€åº¦çš„修正:A, E çš„ 一度{A1}{E1}需要加入E,A: {A1} = {A1 + E} {E1} = {E1 + A}


最后编辑: 郝聪 编辑于2011/04/02 16:25
123 Email
2008/08/20 12:41
zan
分页: 1/1 第一页 1 最后页
发表评论

昵称

网址

电邮

打开HTML 打开UBB 打开表情 隐藏 记住我 [登入] [注册]