從網(wǎng)頁排序｜看圖論的重要應用

圖，是什么？

現(xiàn)實生活中很多問題都可以用圖進行描述, 如網(wǎng)絡(luò)流、資源分配、電路優(yōu)化、網(wǎng)頁排序、搜索、工序安排等等. 同時, 圖也是描述許多數(shù)據(jù)結(jié)構(gòu)的重要手段, 如樹結(jié)構(gòu)是計算機操作系統(tǒng)與眾多應用系統(tǒng)必不可少的模型.

那么數(shù)學上的“圖”，到底是什么呢？

圖是描述對象間關(guān)系的數(shù)學模型, 是描述半結(jié)構(gòu)化數(shù)據(jù)的理想工具, 具有獨特的數(shù)學理論與數(shù)學思想. 圖論是應用數(shù)學的一個分支, 它是反映一些元素之間關(guān)系 (一般是二元關(guān)系)的數(shù)學模型.

圖的重要作用

圖是描述許多應用問題和數(shù)據(jù)結(jié)構(gòu)的重要數(shù)學工具, 學習圖論對鍛煉人的數(shù)學思想與思維能力有積極促進作用, 能夠培養(yǎng)人如何將現(xiàn)實問題描述成一個數(shù)學模型. 進而采用合適的數(shù)據(jù)結(jié)構(gòu)進行刻畫, 為算法與計算機系統(tǒng)設(shè)計打下基礎(chǔ).

另一方面, 圖論是處理半結(jié)構(gòu)化數(shù)據(jù)的重要理論與方法, 隨著大數(shù)據(jù)處理技術(shù)的發(fā)展, 半結(jié)構(gòu)化數(shù)據(jù)的相關(guān)應用越來越廣泛. 所以, 圖論的應用也越來越廣泛,圖計算系統(tǒng)也成為近年來的研究熱點.所以, 圖論是計算機專業(yè)人員以及未來從事計算機相關(guān)專業(yè)的科研人員必修的專業(yè)數(shù)學基礎(chǔ)課.

圖論的概念與成果以及它的應用非常廣泛, 既有許多來自生產(chǎn)實踐的應用問題, 也有許多來自其他學科研究的理論問題.

來，看一個圖論的重要應用吧——網(wǎng)頁排序

隨著網(wǎng)絡(luò)與信息技術(shù)的發(fā)展, 互聯(lián)網(wǎng)上的信息非常豐富, 有國際政治經(jīng)濟形勢、體育娛樂新聞、旅行住宿等等. 這些信息極大地方便了人們的日常生活, 也擴大了人們的知識面.

相信所有的讀者都使用過百度、搜狗或谷歌等搜索引擎. 當用戶輸入待搜索的內(nèi)容時, 搜索引擎首先將用戶輸入的搜索內(nèi)容拆分為一些關(guān)鍵詞, 然后找到含有這些關(guān)鍵詞的網(wǎng)頁, 最后將這些網(wǎng)頁呈現(xiàn)給用戶.

通常, 能夠匹配用戶搜索內(nèi)容的網(wǎng)頁非常多. 比如, 各種新聞、公告、合同、論文作者單位等很多場合都會出現(xiàn)“中國科學技術(shù)大學” , 所以, 很多很多的網(wǎng)頁中都含有關(guān)鍵詞“中國科學技術(shù)大學” . 若某用戶搜索“中國科學技術(shù)大學” , 則能夠找到很多的網(wǎng)頁, 這些網(wǎng)頁中只有少量是該用戶感興趣的, 而絕大多數(shù)是該用戶不感興趣的.

那么, 搜索引擎又是如何對搜索到的網(wǎng)頁進行排序, 將該用戶可能最感興趣的網(wǎng)頁排在前面, 呈現(xiàn)給用戶？

比如, 在搜索“中國科學技術(shù)大學”時,通常都是將中國科學技術(shù)大學的主頁或類似于百度百科對中國科學技術(shù)大學的簡介放在前面呈現(xiàn)給用戶.

如果你曾建立過一個網(wǎng)頁, 你應該會列入一些你感興趣的鏈接, 這樣很容易使你點擊到其他含有重要、可靠信息的網(wǎng)頁.

這樣就相當于你肯定了你所鏈接頁面的重要性. 我們用一個點來代表一個網(wǎng)頁, 若網(wǎng)頁A引用了網(wǎng)頁B, 則從A向B引一條有向邊, 所以可以用一個有向圖來表示網(wǎng)頁間的引用關(guān)系. 圖 1 就是一個含有 7 個網(wǎng)頁、互相引用的示例圖. 當然, 互聯(lián)網(wǎng)上的網(wǎng)頁引用關(guān)系比這個要復雜很多, 有幾百億到幾千億個網(wǎng)頁.

對任意一個網(wǎng)頁p, 我們用I(p)來表述其重要性, 并稱之為網(wǎng)頁排序 (page ranking). 例如, 在圖 1 中, 我們在每個點的旁邊標出了各個網(wǎng)頁的重要性.

圖1

一個網(wǎng)頁將其重要性平均分配給其引用的所有鏈接, 而一個網(wǎng)頁的重要性是由鏈接到它的其他網(wǎng)頁的數(shù)量及其重要性來決定的. 例如, 網(wǎng)頁

有

個鏈接, 其中某個鏈接指向網(wǎng)頁

, 則

將會將其重要性的 1/

賦給

. 網(wǎng)頁

的重要性就是所有指向

的其他網(wǎng)頁所貢獻的重要性總和. 設(shè)鏈接到網(wǎng)頁

的網(wǎng)頁集合為

, 那么

當然, 這似乎又是一個矛盾的問題, 要得到一個網(wǎng)頁的重要性, 需要引用該網(wǎng)頁的所有鏈接的重要性, 那這些鏈接的重要性又是如何得到的呢？又如像圖 1 中的網(wǎng)頁A,D和E, 三者是互相引用的, 又如何計算重要性呢？這個問題則是一個更復雜的數(shù)學問題.

事實上, 除了網(wǎng)頁間的引用關(guān)系, 用戶的偏好、網(wǎng)頁的類型、領(lǐng)域知識等很多因素都會影響網(wǎng)頁的重要性. 網(wǎng)頁排序是做好搜索引擎的基礎(chǔ), 是影響搜索引擎用戶體驗的最根本因素.

隨著對圖論知識的深入學習，我們將越來越體會到它在計算機專業(yè)的強大應用.

本文節(jié)選自許胤龍、呂敏、李永坤2020年12月在科學出版社出版的新書《圖論導引》. 本文圖片來源于網(wǎng)絡(luò)，感謝原作者.

——END——

　　更多網(wǎng)站設(shè)計、網(wǎng)頁設(shè)計等相關(guān)內(nèi)容，歡迎您咨詢中山網(wǎng)訊科技！
　　
責任編輯：中山網(wǎng)站建設(shè)
     【網(wǎng)訊網(wǎng)絡(luò)】國家高新技術(shù)企業(yè)》十二年專注軟件開發(fā)，網(wǎng)站建設(shè)，網(wǎng)頁設(shè)計，APP開發(fā)，小程序，微信公眾號開發(fā)，定制各類企業(yè)管理軟件（OA、CRM、ERP、OMS訂單管理系統(tǒng)、WMS進銷存管理軟件等)！服務熱線：0760-88610046、13924923903，http://www.denorpool.com