å…度分隔与最çŸè·¯å¾„
ã€æœ€çŸè·¯å¾„】 圆明å›çš„北部有一个迷宫,æ®è¯´å¤æ—¶å€™æ¯æ¬¡æœ‰åº†å…¸åœ¨åœ†æ˜Žå›çš„时候,皇å¸ä¼šæ´¾ä¸€äº›å®«å¥³èµ°è¿·å®«ï¼Œçœ‹è°æœ€å…ˆèµ°åˆ°è¿·å®«å†…çš„äºå,会有ä¸é”™çš„奖èµã€‚ 迷宫问题对数å¦å®¶ä»¬æ¥è®²è™½ç„¶æ˜¯å°å„¿ç§‘但在计算机课程上å´éžå¸¸é‡è¦ï¼Œå› 为ä¸åŒçš„求解会涉åŠåˆ°é€’归,广度优先和深度优先ç‰ç®—法。 迷宫毕竟是一个放置在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
![给他/她发邮件 Email](template/neowin/images/email.gif)
![zan](images/emot/zan.gif)
![第一页 第一页](template/neowin/images/arrows/doubleleft.gif)
![最后页 最后页](template/neowin/images/arrows/doubleright.gif)