326      阿裏雲  技術社區[雲棲]

六度分隔與最短路徑

【最短路徑】

圓明園的北部有一個迷宮，據說古時候每次有慶典在圓明園的時候，皇帝會派一些宮女走迷宮，看誰

最先走到迷宮內的亭子，會有不錯的獎賞。

迷宮問題對數學家們來講雖然是小兒科但在計算機課程上卻非常重要，因為不同的求解會涉及到遞歸

，廣度優先和深度優先等算法。

迷宮畢竟是一個放置在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}

整體操作的量大約在2n次操作，比我們通常認為的要小的多 

最後更新：2017-04-02 00:06:27

  上一篇： [原創]淺談如何使用gcc開發NT核心驅動程序

  下一篇： 發表於dW的教程之開放源代碼的服務框架 - Apache CXF 簡介