萬花筒 數學之美:圖論和網絡爬蟲

2021-02-08 21ic電子網

離散數學包括數理邏輯、集合論、圖論和近世代數四個分支。這裡我們介紹圖論和網際網路自動下載工具網絡爬蟲 (Web Crawlers) 之間的關係。用 Google Trends來搜索一下「離散數學」這個詞,可以發現不少有趣的現象。


怎樣自動下載網際網路所有的網頁呢,它要用到圖論中的遍歷(Traverse) 算法。


圖論的起源可追溯到大數學家歐拉(Leonhard Euler)。1736 年歐拉來到德國的哥尼斯堡(Konigsberg,大哲學家康德的家鄉,現在是俄羅斯的加裡寧格勒),發現當地市民們有一項消遣活動,就是試圖將下圖中的每座橋正好走過一遍並回到原起點,從來沒有人成功過。歐拉證明晰這件事是不行能的,並寫了一篇論文,通常以為這是圖論的開始。


圖論中所討論的的圖由一些節點和連接這些節點的弧組成。如若我們把中國的城市當成節點,連接城市的國道當成弧,那麼全國的公路幹線網就是圖論中所說的圖。關於圖的算法有許多,但最主要的是圖的遍歷算法,也就是怎樣通過弧訪問圖的各個節點。

以中國公路網為例,我們從北京出發,看一看北京和哪些城市直接相連,好比說和天津、濟南、石家莊、南京、瀋陽、大同直接相連。我們可以依次訪問這些城市,然後我們看看都有哪些城市和這些已經訪問過的城市相連,好比說北戴河、秦皇島與天津相連,青島、煙臺和濟南相連,太原、鄭州和石家莊相連等等,我們再一次訪問北戴河這些城市,直到中國所有的城市都訪問過一遍為止。這種圖的遍歷算法稱為「廣度優先算法」(BFS),由於它先要儘可能廣地訪問每個節點所直接連接的其他節點。另外另有一種計謀是從北京出發,隨便找到下一個要訪問的城市,好比是濟南,然後從濟南出發到下一個城市,好比說南京,再訪問從南京出發的城市,一直走到頭。然後再往回找,看看中間是否有尚未訪問的城市。這種方法叫「深度優先算法」(DFS),由於它是一條路走到黑。這兩種方法都可以保證訪問到全部的城市。當然,不論接納哪種方法,我們都應該用一個小本本,記錄已經訪問過的城市,以防一個城市訪問多次或者遺漏哪個城市。網際網路實際上就是一張大圖,我們可以把每一個網頁看成一個節點,把那些超連結(Hyperlinks)看成連接網頁的弧。許多讀者可能已經注意到,網頁中那些藍色的、帶有下劃線的文字背後實際上藏著對應的網址,當你點下去的時間,瀏覽器是通過這些隱含的網址轉到相應的網頁中的。這些隱含在文字背後的網址稱為「超連結」。有了超連結,我們可以從任何一個網頁出發,用圖的遍歷算法,自動地訪問到每一個網頁並把它們存起來。完成這個功能的程序叫做網絡爬蟲,或者在一些文獻中稱為"機器人"(Robot)。世界上第一個網絡爬蟲是由麻省理工學院 (MIT)的學生馬休.格雷(Matthew Gray)在 1993 年寫成的。他給他的程序起了個名字叫「網際網路漫遊者」("www wanderer")。以後的網絡爬蟲越寫越複雜,但原理是一樣的。假定我們從一家門戶網站的首頁出發,先下載這個網頁,然後通過度析這個網頁,可以找到藏在它裡面的所有超連結,也就等於知道了這家門戶網站首頁所直接連接的全部網頁,諸如雅虎郵件、雅虎財經、雅虎新聞等等。我們接下來訪問、下載並剖析這家門戶網站的郵件等網頁,又能找到其他相連的網頁。我們讓計算機一直地做下去,就能下載整個的網際網路。當然,我們也要紀錄哪個網頁下載過了,以免重複。在網絡爬蟲中,我們使用一個稱為「哈希表」(Hash Table)的列表而不是一個記事本紀錄網頁是否下載過的信息。現在的網際網路極度巨大,不能僅通過一臺或幾臺計算機伺服器就能完成下載任務。好比雅虎公司(Google 沒有公然公布我們的數目,所以我這裡舉了雅虎的索引大小為例)宣稱他們索引了 200 億個網頁,如果下載一個網頁需要一秒鐘,下載這 200 億個網頁則需要 634 年。因此,一個商業的網絡爬蟲需要有成千上萬個伺服器,而且由快速網絡連接起來。怎樣創建這樣複雜的網絡系統,怎樣協調這些伺服器的任務,就是網絡設計和程序設計的藝術了。


相關焦點

  • 看到正確答案被嚇到,不得不感嘆數學之美
    在數學界,有眾多天才投入到數論這一暫時還看不到實用之處的領域,他們的唯一目的就是追求純粹的數學之美。數學之美!正如企業家王小川所說:「數學可以和音樂、美術一樣,具有美感。康德認為數學式之所以美,在於它的合理性——合理是大腦天生的邏輯演繹系統,人人皆有。因此,當我們討論數學之美時,不是比喻,不是人為造作,而是真的人性之感受。」
  • 應遊戲而生的數學圖論,多棲發展的數學家哈密頓,傳奇人生
    與之表面相似,實際完全不同的哈密頓問題則要求在一個圖中尋找滿足「從一個頂點出發,沿邊行進,無遺漏地通過全部頂點,每一頂點只許過一次而回到出發點」的路線,這樣的路線後來在圖論中被稱為哈密頓圈,而具有哈密頓圈的圖稱為哈密頓圖或說圖是哈密頓的。歐拉問題與哈密頓問題已經成為現在圖論的重要組成部分。
  • 我,和圖論算法的雜七雜八
    原因是:課程不包含圖論算法。我當時很不爽。雖然我知道,近乎在所有的大學教育體系中,圖論都是和數據結構一起教的。但是,在我的觀念中,圖論算法和其他數據結構的知識有很大的不同。再加上一門課程的時間有限,所以我將圖論算法和其他數據結構分開了。這一點,在我的課程導論中,特意強調了 n 遍。
  • 一文帶你入門圖論和網絡分析(附Python代碼)
    具體而言,圖(Graph)是用於研究對象和實體之間成對關係的數學結構。它是離散數學的一個分支,在計算機科學,化學,語言學,運籌學,社會學等領域有多種應用。 數據科學和分析領域也使用圖來模擬各種結構和問題。
  • 5月,《圖論》(原書第五版)中譯本來啦
    在中國,圖論的教學從早期引進Berge, Bondy 與Murty 以及Harary 的著作後得到了快速的發展。隨著圖論的研究和應用達到新的高度和廣度,急需一本具有更新內容、更高質量的教材。這裡我們推薦由德國圖論學者Diestel所著的《圖論(第五版)》,這是作為研究生教材和研究者參考書籍不可多得的選擇。
  • 為什麼中學生要學習圖論?
    在大一上了Po-Shen的《離散數學》之後成為了他的迷弟,希望能將他的數學思維傳遞給全世界:)圖論是數學中非常重要的一個分支,然而當我們在數學學習中聽到圖論這個詞,往往會與高等數學聯繫在一起,讓人不由自主的感到無從下手。
  • 精通 Python 網絡爬蟲:網絡爬蟲學習路線
    如何才能精通Python網絡爬蟲呢?學習Python網絡爬蟲的路線應該如何進行呢?在此為大家具體進行介紹。
  • 2007年度國家精品課程:集合論與圖論
    哈工大報訊  離散教學是計算機科學的重要工具,也是軟體及其應用必不可少的數學工具,內容包括集合論、圖論、近世代數和數理邏輯。我校《集合論與圖論》涵蓋了前兩部分。集合論是整個數學的基礎;圖論可以看成是集合論的一個應用。
  • 圖論Graph theory
    事實上,這一數學領域對語言學的有用性催生了一些組織,如文本圖,以及各種「網絡」項目,如WordNet、VerbNet等。在數學中,圖形在幾何學和拓撲的某些部分(如紐結理論)中是有用的。代數圖論與群論有著密切的聯繫。
  • 網絡爬蟲——Requests,GET和POST
    2、發送請求,獲取響應response=requests.post(url=請求的urlheaders=請求頭字典data=請求數據字典)四、爬蟲和法律《中華人民共和國網絡安全法》 2016 年 11 月 7 日發布的《中華人民共和國網絡安全法》明確「個人信息」是指以電子或 者其他方式記錄的能夠單獨或者與其他信息結合識別自然人個人身份的各種信息,包括但不限於自然人的姓名、出生日期、身份證件號碼、個人生物識別信息、住址、電話號碼等,就網絡服務中的個人信息保護問題作出系統規定如下:
  • 漫談Pyspider網絡爬蟲的實踐
    總之,很早之前,我就開始規劃著寫點關於網絡爬蟲方面的文章,介紹性質的,但更重要的是,計算機以及信息科學的實踐性,所以,以一個實幹者的角度來寫,更為合適一些。在這之前,還是有必要對一些概念性的詞彙做一下梳理和科普,至少,不會讓讀者覺得突兀或者一知半解的讀著流水帳式的文字。
  • 網絡爬蟲違法?扯!繼續學習我的第一個爬蟲
    網絡爬蟲領域目前還屬於早期的拓荒階段,雖然網際網路世界已經通過自身的協議建立起一定的道德規範(Robots協議),但法律部分還在建立和完善中。從目前的情況來看,如果抓取的數據屬於個人使用或科研範疇,基本不存在問題;而如果數據屬於商業盈利範疇,就要就事而論,有可能屬於違法行為,也有可能不違法。
  • ...排序看圖論的重要應用|圖論導引|中國科學技術大學|習題|算法...
    圖是描述許多應用問題和數據結構的重要數學工具, 學習圖論對鍛鍊人的數學思想與思維能力有積極促進作用, 能夠培養人如何將現實問題描述成一個數學模型.又如像圖 1 中的網頁 A, D 和 E, 三者是互相引用的, 又如何計算重要性呢?這個問題則是一個更複雜的數學問題.  事實上, 除了網頁間的引用關係, 用戶的偏好、網頁的類型、領域知識等很多因素都會影響網頁的重要性. 網頁排序是做好搜尋引擎的基礎, 是影響搜尋引擎用戶體驗的最根本因素.  隨著對圖論知識的深入學習,我們將越來越體會到它在計算機專業的強大應用.
  • 圖論是一個非常受歡迎的離散數學領域,應用於無數實際問題
    圖論是一個非常受歡迎的離散數學領域,不僅有許多理論發展,而且還有無數應用於實際問題。作為一個研究領域,圖論仍然相對年輕,但它正在迅速成熟,在過去的幾十年中已經發現了許多深刻的結果。其中一個原因是,無向圖形在某種意義上形成了一類特殊的有向圖(對稱有向圖),因此對於有向圖和無向圖,可以為後者更容易制定問題。另一個原因是,與無向圖的情況不同,其中有幾本重要的書籍涵蓋了經典和最近的結果,之前的書沒有涵蓋過去25年內有關圖的結果的一小部分。
  • 蘋果網絡爬蟲確實存在,主要用於Siri和Spotlight
    5月6日消息,在蘋果最近更新的支持文檔中,傳聞已久的「AppleBot」據蘋果表示,「AppleBot」網絡爬蟲主要用於蘋果Siri和Spotlight。「AppleBot」網絡爬蟲操作類似於谷歌的谷歌機器人,此前蘋果並未對外證實其存在。去年11月,一個web開發人員發現了「AppleBot」網絡爬蟲,它來自於17.0.0.0/8的IP位址,這些地址只分配給了蘋果公司使用。
  • Xpath語法-網絡爬蟲基礎
    前言這一章節主要講解Xpath的基礎語法,學習如何通過Xpath獲取網頁中我們想要的內容;為我們的後面學習Java網絡爬蟲基礎準備工作。備註:此章節為基礎核心章節,未來會在網絡爬蟲的數據解析環節經常使用,學會Xpath解析語法,可為未來爬蟲解析省去很多麻煩。Xpath簡介XPath即為XML路徑語言,它是一種用來確定XML(標準通用標記語言的子集)文檔中某部分位置的語言。
  • 程式設計師日常(四)網絡之爬蟲(一)
    譬如:淘寶網今日特價商品、百度的熱搜榜等爬蟲是個應用程式,自動提取網頁的程序通過數據篩選、過濾,得到有用的信息,一般是為搜尋引擎服務或者作為內容來源> Application+WebRequest+Filter+Data+Threads爬蟲是否違法?
  • 網絡爬蟲(一)
    有朋自遠方來,不亦樂乎,並誠邀入群,以達相互學習和進步之美好心願。爬蟲是按照一定規則,自動地提取並保存網頁中信息的程序。通過向網站發起請求獲取資源,提取其中有用的信息。爬蟲在獲取信息、整理數據等方面應用廣泛。
  • 寫網絡爬蟲程序的難度是怎麼分等級的
    寫網絡爬蟲程序的難度是怎麼分等級的 猿人學 發表於 2020-02-05 11:49:55 寫爬蟲,是一個非常考驗綜合實力的活兒。
  • 數學之美——貝葉斯網絡 (Bayesian Networks)
    這種模型,對很多實際問題來講是一種很粗略的簡化。在現實生活中,很多事物相互的關係並不能用一條鏈來串起來。它們之間的關係可能是交叉的、錯綜複雜的。比如在下圖中可以看到,心血管疾病和它的成因之間的關係是錯綜複雜的。顯然無法用一個鏈來表示。