網(wǎng)絡結構與效應原理：第13章 萬維網(wǎng)信息的結構

萬維網(wǎng)信息的結構

WorldWideWeb（以第13章為基礎）Web信息的基本結構特征以網(wǎng)頁為組成單位，每個網(wǎng)頁對應一個網(wǎng)址每個網(wǎng)頁上可能有多個鏈接，每個鏈接指向另一個網(wǎng)頁由此，我們可以體會到給定網(wǎng)頁A和B，有可能通過一個個相繼的鏈接，經(jīng)過一些中間網(wǎng)頁，從A到達B如果可以如此從A到達B，也可以從B到達A，中間經(jīng)過的網(wǎng)頁很可能是不一樣，路徑的長度也就可能是不一樣的幾篇網(wǎng)頁之間的鏈接關系示意注意，不僅信息所處的位置可以相距很遠，其中的主題也可能“漂移”很遠；不奇怪，人的思維也如此。有向圖：Web信息結構的模型節(jié)點：網(wǎng)頁（可能用網(wǎng)址標識）有向邊：表示從一個節(jié)點到另一個節(jié)點的直接鏈接關系；節(jié)點的出向邊與入向邊有向路徑：兩節(jié)點之間邊的方向一致的路徑節(jié)點A到B的距離：從A到B最短有向路徑的長度注意，從A到B的距離不一定等于從B到A的距離強連通有向圖：任何兩節(jié)點之間都存在兩個方向的有向路徑（不一定經(jīng)過相同節(jié)點）強連通分量：盡可能大的節(jié)點子集，其中每個節(jié)點都有到其中任何另一節(jié)點的有向路徑一組網(wǎng)頁之間構成的一個有向圖示例

＊具體與抽象ABA與B之間的有向路徑？尋找強連通分量下圖是個強連通有向圖嗎？強連通分量節(jié)點子集，其中每個節(jié)點都有到任何其他節(jié)點的有向路徑不存在真包含這個集合的節(jié)點子集問題：一個有向圖中有沒有可能存在兩個節(jié)點有重疊的強連通分量？萬維網(wǎng)的結構模型：有向圖根據(jù)用途，可在不同層次定義圖的節(jié)點和邊的含義網(wǎng)頁層次：網(wǎng)頁網(wǎng)站層次：網(wǎng)站（例如我們系的網(wǎng)站）機構層次：機構網(wǎng)站總體（例如大學各院系）還可以按行政層級分縣、地市、省網(wǎng)頁層次是基礎從有向圖的角度看，Web宏觀上是個什么樣子（“形狀”）？對于由巨量元素構成的事物，人們往往希望能得到對其整體性態(tài)的有意義的刻畫“領結”：Web信息結構的一種概貌1999，AndreiBroder等發(fā)現(xiàn)萬維網(wǎng)包含一個超大強連通分量SCC，加上其他部分，顯示出一種形象的結構鏈入，鏈出，卷須（管道），游離這是怎么知道的？基本問題給定一個有向圖，如何得到其中的強連通分量？顯然不一定就一個。強連通分量的劃分性。以最大的強連通分量為基礎，如何描述其他部分與它的關系？鏈入，鏈出，卷須（管道），游離為了回答第一個問題，我們問一個更具體些的問題：給定一個節(jié)點，如何確定包含它的強連通分量？基本方法：廣度優(yōu)先搜索從一個具體例子入手｛1，3，4，8，9，13，14，15，18｝；｛2｝，｛5｝，｛6｝，｛7｝，｛10｝，｛11｝，｛12｝，｛16｝，｛17｝有向圖的“領結”表示計算領結結構的方法（算法）輸入：有向圖G第一步：生成圖G的“反向圖”G’第二步：選擇一個在最大強連通子圖中的節(jié)點A（tricky?）第三步：以A為出發(fā)節(jié)點，在圖G中寬度優(yōu)先搜索直到?jīng)]有新的節(jié)點發(fā)現(xiàn)，得節(jié)點集合FS第四步：以A為出發(fā)節(jié)點，在圖G’中寬度優(yōu)先搜索直到?jīng)]有新的節(jié)點發(fā)現(xiàn)，得節(jié)點集合BS結果SCC＝FS和BS的交集，即共同元素IN（鏈入）＝BS－SCCOUT（鏈出）＝FS－SCC基于G和G’，F(xiàn)S和BS，進一步集合運算可得到卷須和游離一次計算中國Web結構的實踐2006年1月，孟濤同學用16臺服務器并行工作，北大網(wǎng)絡實驗室完成了一次中國Web的網(wǎng)頁搜集，得到了8億3千多萬網(wǎng)頁基于這些網(wǎng)頁，我們構造了一個巨大的有向圖，8億3千多萬個節(jié)點，數(shù)據(jù)占用磁盤容量400GB+在這個有向圖數(shù)據(jù)上，實現(xiàn)了前述算法，一個程序（在16臺機器上）運行了一周，得到了有關結構形狀的參數(shù)結果：

自相似、層次性網(wǎng)頁:http://.../....html,(完整地址)網(wǎng)站:http://.../*,對應例如大學的一個系機構:http://*..../*,

對應例如一所大學所有院系網(wǎng)站的集合本章要點有向圖是信息組