第一次工業(yè)革命像一個「潘多拉寶盒」，給英國帶來巨大發(fā)展與財富的同時，也帶來了急劇惡化的環(huán)境和突如其來的疾病。

1858年的一個夏日，生活在維多利亞時代的倫敦人民不會想到，在接下來的數(shù)月里，他們將如夢魘般度日。

這天清晨，人們在一股惡臭中醒來。整個倫敦城早已臭氣熏天，富人們緊閉門窗，用噴了香水的手帕遮面；窮人們風(fēng)餐露宿，只得惶恐地逃離市區(qū)。英國歷史上「最臭的事件」就此拉開帷幕。

那是「倫敦大惡臭」的第一天，而這股空前的惡臭纏擾倫敦市民數(shù)月之久。在當(dāng)時的倫敦，各種生活廢水和排泄物被直接排入泰晤士河。默默承受人類垃圾幾百年后，這條“英國母親河”終于發(fā)怒了。

那年，倫敦遭遇罕見的酷暑。隨著氣溫飆升，泰晤士河的水位急速下降。沾有霍亂弧菌的淤泥顯露出來，在烈日下炙烤，散發(fā)出的惡臭綿延數(shù)公里。

面對突如其來的公共衛(wèi)生事件，倫敦市政府一開始并不積極。不過，政客們終究抵擋不住惡臭和霍亂肆虐，這才痛下決心整改市政排污系統(tǒng)。

市政府邀請各方提供設(shè)計方案，并最終接受了由市政工程師約瑟夫·巴扎爾蓋特（Joseph Bazalgette）提出的方案。

巴扎爾蓋特才華橫溢，他年輕時投身英國的鐵路網(wǎng)建設(shè)，從中積累了豐富的工程經(jīng)驗。由他設(shè)計的倫敦地下排污網(wǎng)絡(luò)，從七零八落的舊下水道攔截污水，并通過四通八達的新下水道引至泰晤士河的入?？冢瑥母旧细淖兞藗惗氐墓残l(wèi)生條件。這個龐大的排污工程被公認(rèn)為城市建設(shè)之典范，曾經(jīng)反復(fù)襲擾倫敦的霍亂也慢慢遠離了這座城市。盡管倫敦的人口已經(jīng)從當(dāng)時的200萬增加到現(xiàn)在的900萬，整座城市依然受益于巴扎爾蓋特的劃時代設(shè)計。

你可以從以下數(shù)字中窺見這項工程的龐大規(guī)模：

• 3億塊磚；

• 2000公里長的下水道；

• 67萬立方米土方；

• 每日污水排放量為20億升；

• 當(dāng)時耗資650萬英鎊，相當(dāng)于現(xiàn)在的 2.5 億英鎊（約22億人民幣）。

在設(shè)計排污網(wǎng)絡(luò)時，巴扎爾蓋特不遺余力地研究重力、坡度，以及下水道的最佳直徑，這些都是他癡迷的細節(jié)。

不過從根本上說，如此龐大的工程之所以得以最終實施，得益于巴扎爾蓋特解決了兩個最關(guān)鍵的問題。

1. 如何將排污網(wǎng)絡(luò)中任意兩處間的下水道長度最小化？

2. 排污網(wǎng)絡(luò)中的重要節(jié)點在哪里？

巴扎爾蓋特的工程壯舉是圖論早期應(yīng)用的重要示例。他證明，將地點等實體視作節(jié)點，將節(jié)點之間的關(guān)系連成線，就能將錯綜復(fù)雜的關(guān)系網(wǎng)絡(luò)轉(zhuǎn)化為圖。

圖論中的圖

圖是計算機科學(xué)的一大主題。對于訓(xùn)練有素的程序員而言，能夠用一種形式來對不同的結(jié)構(gòu)建模是強大的力量之源。

—— Steven S. Skiena

石溪大學(xué)計算機科學(xué)杰出授課教授

節(jié)選自《數(shù)據(jù)分析之圖算法》

圖的概念源于數(shù)學(xué)，是一種實用且高精度的數(shù)據(jù)建模和分析方法。圖由一組節(jié)點及其關(guān)系組成。

節(jié)點又稱頂點，關(guān)系又稱邊。

關(guān)系帶有權(quán)重的圖叫作加權(quán)圖，關(guān)系沒有權(quán)重的圖叫作無權(quán)圖

了解了圖的基本概念之后，你便可以嘗試將一些問題抽象為圖。比如，為了追蹤軟件項目中的傳遞依賴關(guān)系和沖突，有人為 Python 庫做了這樣一張依賴圖。

節(jié)點間的最短路徑

從一個節(jié)點到另一個節(jié)點的所有關(guān)系組成一條路徑，關(guān)系權(quán)重之和最小的路徑稱為這兩個節(jié)點間的最短路徑。比如，下圖展示了從節(jié)點 1 到節(jié)點 6?的最短路徑，總權(quán)重是?2+6+4=12。

在如倫敦排污系統(tǒng)這種錯綜復(fù)雜的網(wǎng)絡(luò)工程中，為了盡可能降低成本，優(yōu)化最短路徑是常規(guī)需求。

你可能聽說過 Dijkstra 算法，它就是最著名的最短路徑算法，用于查找圖中一個節(jié)點到其他所有節(jié)點的最短路徑。

在需要查找兩點間的最優(yōu)路線時，例如導(dǎo)航應(yīng)用推薦行進路線，就可以使用最短路徑算法。

另一個使用場景是找出人際關(guān)系網(wǎng)絡(luò)中個體之間的分離度。六度分隔理論提出，世界上任何兩個人都可以通過最多五個人（六度）連在一起。

最近有研究顯示，F(xiàn)acebook 用戶之間的平均最短路徑長度為?4.57。

節(jié)點本身的重要程度

各個節(jié)點的重要程度不一定相同。以巴扎爾蓋特的排污網(wǎng)絡(luò)為例，一些節(jié)點需要重點監(jiān)控，因為如果這些節(jié)點發(fā)生堵塞，給人們造成的影響更大。

同理，在人際關(guān)系網(wǎng)絡(luò)中，某些人的人脈更廣，他們在群體中的影響力也更大。

在衡量節(jié)點的重要程度時，一種常用的圖算法是中間中心性算法。簡單地說，一個節(jié)點的中間中心度是指它在網(wǎng)絡(luò)中其他兩個節(jié)點之間的最短路徑中出現(xiàn)的次數(shù)。

中間中心度越高，節(jié)點對信息傳播的影響就越大，它的缺失就越會影響網(wǎng)絡(luò)的整體連通性。在下圖中，紅色節(jié)點的中間中心度最小，藍色節(jié)點的中心度則最大。

莎士比亞曾說，世界是一個大舞臺。在今天看來，世界是一張大圖！將復(fù)雜的現(xiàn)實問題抽象為圖，通過圖算法進行分析，你就能洞悉復(fù)雜問題的本質(zhì)。

圖算法已經(jīng)廣泛用于各行各業(yè)的數(shù)據(jù)分析，營銷歸因分析、欺詐網(wǎng)絡(luò)檢測、傳染病溯源、客戶旅程建模、安全事故原因分析，甚至連莎士比亞戲劇的劇情分析，都會用到圖算法。

參考文章：

https://towardsdatascience.com/graph-theory-helped-the-british-become-less-stinky-de4b439a7784

圖分析可以揭示復(fù)雜系統(tǒng)和大規(guī)模網(wǎng)絡(luò)的運作機制，圖算法為構(gòu)建智能應(yīng)用程序提供了快速建模的框架，有助于更準(zhǔn)確、更快速地做出預(yù)測。包括商品推薦和欺詐檢測在內(nèi)的許多人工智能問題能轉(zhuǎn)換為圖論問題。

本書基于 Spark 和 Neo4j 講解近20種常用的圖算法，幫助讀者拓展重要圖分析類型的相關(guān)知識和能力，更快速地發(fā)現(xiàn)數(shù)據(jù)中的模式并找到更優(yōu)的解決方案。

圖靈官方小店
享受正版低價折扣

嘿 Siri，有沒有「三天速成深度學(xué)習(xí)」的課程？