Zi 字媒體

轉載聲明本文為燈塔大數據原創內容，歡迎個人轉載至朋友圈，其他機構轉載請在文章開頭標註：「轉自：燈塔大數據；編者按：燈塔大數據將每周持續推出《從零開始學大數據演算法》的連載，本書為哈爾濱工業大學著名教授王宏志老師的扛鼎力作，以對話的形式深入淺出的從何為大數據說到大數據演算法再到大數據技術的應用，帶我們在大數據技術的海洋里徜徉~每周五定期更新，歡迎來做客呦！上期回顧&查看方式：在上一期中，我們學習了利用 MapReduce 來增加相似連接的可擴展性，通過計算單元函數值和集合的合取函數值，來求解集合的析取函數值。在這一期中，我們將學慣用MapReduce 框架，以并行計算的觀點來解決一些圖論問題。 No.43期Mr. 王：MapReduce 作為一種經典的并行編程框架，可以用於解決很多問題，包括一些圖論問題。在客觀世界中，很多問題都可以抽象為圖論問題。前面我們提到過如何用磁碟演算法來解決一些圖論問題，現在我們嘗試用MapReduce 框架，以并行計算的觀點來解決一些圖論問題。還是先舉個例子吧。你會經常去使用一些社交網路吧。小可：是的，現在通過社交網路，我可以非常方便地與同學聯繫。社交網路上人與人之間的好友連接關係就可以抽象成一個圖。Mr. 王笑著說：有沒有想過，在社交網路上，你的好友的最好朋友是不是你？小可：哈哈，我沒想過，但是這還真是一個挺有趣的問題。用MapReduce 還可以解決這種問題嗎？Mr. 王：是的，具體怎麼做，我們用一個社交網路圖來舉例吧。 小可：嗯，這是一個非常典型的社交網路圖，其中包含著我和我的一些朋友，還有一些我關注的公用主頁等信息。那麼要如何發現一個人最好的朋友是不是我呢？Mr. 王：這個演算法的工作分為以下幾個步驟。第1 步：去掉無關的邊和節點。這一步是對整個圖進行一個預處理，將圖上的一些與我們研究的問題無關的節點去掉，畢竟來自社交網路上的信息還是比較繁多和雜亂無章的。描述社交網路的圖上往往會包含一些與「好友」這種關係無關的邊和點，會涉及一些關注的網頁、興趣愛好等這樣的數據，這與我們要完成的任務無關，為了更好地解決問題，我們要將與好友關係相關的內容具體地提取出來。第2 步：用朋友列表標記每一個節點。對於每一個節點，我們都為其標記一個朋友列表，這個朋友列表記錄了與之直接相連的朋友節點，以及自己與他們之間的親密度。第3 步：沿著每條邊下推標籤。經過多次下推標籤，可以讓我們獲得關於朋友的朋友的信息。直接與我們具有朋友關係的這些節點是「1 跳朋友」，而與我們不是朋友關係卻與1 跳朋友有關係的就是2 跳朋友，想要知道某一個朋友F 是不是和我的關係最緊密，我們就要去發現與朋友F 是1 跳朋友的2 跳朋友，去看看我們和這些2 跳朋友對於朋友F 來說的親密度如何。這樣經過比較，我們就可以知道自己究竟是不是他最好的朋友了。小可：這個演算法看起來還是挺容易的啊。Mr. 王：如果這個演算法僅僅運行在單機上，而且數據量不那麼大的話，那麼這就是一個非常簡單的問題。但是在實際的社交網路中比如說Facebook，這個朋友關係網路就會是一張非常大的圖，不論是頂點（人）還是邊（關係）數量都是非常龐大的，圖的稠密程度也很高，在一個小的圈子內，經常會出現兩兩互為朋友這樣的子圖。所以對於比較大的圖來說，我們想要執行前面的演算法就會遇到很多困難，處理它就會變得非常慢。此時，我們就需要MapReduce 的幫忙。這個問題用MapReduce 去做雖然不那麼自然，但卻是可以解決的。一個比較簡單的想法是，我們用鄰接表來表示一個圖，將節點作為key，而鄰接表就是value。Mr. 王：這裡我們再討論一個社交網路中常見的功能，那就是朋友推薦。小可：這個我知道，我在用社交網路時，經常有一個欄位告訴我有個人與我有很多的共同好友，所以他可能是我的朋友。Mr. 王：嗯，看來你已經很熟悉這個功能了，這就是一個典型的「誰是我多個好友的好友」問題。在此基礎上，還有超過直接朋友的問題，比如在圖上經過兩三跳與你連接，這也可能是你潛在的朋友。小可：嗯，如果不是直接連接的話，所需要的運行開銷可能就會更大。Mr. 王：是這樣的。此時我們用一輪MapReduce 已經不足以解決多跳的問題，以至於要使用多輪MapReduce。這種多輪MapReduce 我們稱之為迭代MapReduce。下面這是一個迭代MapReduce 的基本框架。小可：哦！我看懂了。首先將整個演算法的輸入內容放入dir 1 中，然後會去執行一輪MapReduce，dir 1 會被輸入到Mapper 中，再輸出到Reduce中，Reducer 會接收來自Mapper的輸出作為輸入，在處理之後輸出為dir 2。之所以能形成循環，是因為它將dir 2 的結果又送回了dir 1，然後程序框架會把dir 2 再次輸入到MapReduce 中。重複執行上述過程，這樣整個系統就可以一輪一輪地運行，每一輪的輸出都是下一輪的輸入，也就構成了MapReduce的迭代。Mr. 王：你說的對，這就是形成循環和迭代MapReduce 的基本思路。另外，為了讓MapReduce 進行得更加高效、順利，在數據被放入dir 1 中和最終從dir 2 中取出來之前，可以對數據分別進行預處理和后處理。想想在迭代MapReduce 中需要注意什麼問題？小可：這裡有一個循環……所以……Mr. 王：每一輪循環的輸出都會拿去做什麼？小可：每一輪循環的輸出都會是下一輪Map 的輸入，所以必須要保證Reduce 的輸出符合Map 的輸入形式。Mr. 王：很好，這需要對Map 和Reduce 的輸入輸出進行標準化處理，使得每一輪的輸出和下一輪的輸入相匹配，這也就要求Reduce 輸出的數據格式和Map 的輸入格式是嚴格一致的。現在我們來看一看一般的圖操作演算法是如何實現的。如果我們要執行的這個圖操作運行在非并行演算法下，那麼計算機每次就會處理圖中的一個項，或者處理一條邊，或者處理一個點。也就是說，只有一個訪問游標在執行演算法，同時只有一個對象在接受演算法的處理或者訪問。而在MapReduce 框架下的圖演算法中，處理操作往往是并行的，由多個Mapper 同時處理圖的多個部分，以求更快地完成對圖的一輪處理。另外，絕大多數的圖演算法都需要經歷多個MapReduce階段，這意味著整個演算法的構成可能是多個相同的MapReduce 過程形成的MapReduce 迭代，或者是由不同的MapReduce 過程形成的MapReduce 鏈。在進行MapReduce 演算法設計時，我們需要著眼於兩個方面：一是對每一個節點的操作是什麼；二是要看對每一個節點執行的操作需要知道哪些信息，以及這些信息在圖中距離自己有多遠。因為信息往往是沿著邊進行推送的，而是在節點上完成計算的，所以要做到對圖中的節點有一個透徹的認識。小可：就好像我們自己就是一個節點一樣？Mr. 王：哈哈，沒錯，就是這種感覺。下期精彩預告：經過學習，我們掌握了利用MapReduce 框架，以并行計算的觀點來解決一些圖論問題。在下一期中，我們將基於路徑的圖演算法，計算節點間關於路徑的信息。更多精彩內容，敬請關注燈塔大數據，每周五不見不散呦！...閱讀原文了解更多詳情