第一次工业革命像一个「潘多拉宝盒」，给英国带来巨大发展与财富的同时，也带来了急剧恶化的环境和突如其来的疾病。

1858年的一个夏日，生活在维多利亚时代的伦敦人民不会想到，在接下来的数月里，他们将如梦魇般度日。

这天清晨，人们在一股恶臭中醒来。整个伦敦城早已臭气熏天，富人们紧闭门窗，用喷了香水的手帕遮面；穷人们风餐露宿，只得惶恐地逃离市区。英国历史上「最臭的事件」就此拉开帷幕。

那是「伦敦大恶臭」的第一天，而这股空前的恶臭缠扰伦敦市民数月之久。在当时的伦敦，各种生活废水和排泄物被直接排入泰晤士河。默默承受人类垃圾几百年后，这条“英国母亲河”终于发怒了。

那年，伦敦遭遇罕见的酷暑。随着气温飙升，泰晤士河的水位急速下降。沾有霍乱弧菌的淤泥显露出来，在烈日下炙烤，散发出的恶臭绵延数公里。

面对突如其来的公共卫生事件，伦敦市政府一开始并不积极。不过，政客们终究抵挡不住恶臭和霍乱肆虐，这才痛下决心整改市政排污系统。

市政府邀请各方提供设计方案，并最终接受了由市政工程师约瑟夫·巴扎尔盖特（Joseph Bazalgette）提出的方案。

巴扎尔盖特才华横溢，他年轻时投身英国的铁路网建设，从中积累了丰富的工程经验。由他设计的伦敦地下排污网络，从七零八落的旧下水道拦截污水，并通过四通八达的新下水道引至泰晤士河的入海口，从根本上改变了伦敦的公共卫生条件。这个庞大的排污工程被公认为城市建设之典范，曾经反复袭扰伦敦的霍乱也慢慢远离了这座城市。尽管伦敦的人口已经从当时的200万增加到现在的900万，整座城市依然受益于巴扎尔盖特的划时代设计。

你可以从以下数字中窥见这项工程的庞大规模：

• 3亿块砖；

• 2000公里长的下水道；

• 67万立方米土方；

• 每日污水排放量为20亿升；

• 当时耗资650万英镑，相当于现在的 2.5 亿英镑（约22亿人民币）。

在设计排污网络时，巴扎尔盖特不遗余力地研究重力、坡度，以及下水道的最佳直径，这些都是他痴迷的细节。

不过从根本上说，如此庞大的工程之所以得以最终实施，得益于巴扎尔盖特解决了两个最关键的问题。

1. 如何将排污网络中任意两处间的下水道长度最小化？

2. 排污网络中的重要节点在哪里？

巴扎尔盖特的工程壮举是图论早期应用的重要示例。他证明，将地点等实体视作节点，将节点之间的关系连成线，就能将错综复杂的关系网络转化为图。

图论中的图

图是计算机科学的一大主题。对于训练有素的程序员而言，能够用一种形式来对不同的结构建模是强大的力量之源。

—— Steven S. Skiena

石溪大学计算机科学杰出授课教授

节选自《数据分析之图算法》

图的概念源于数学，是一种实用且高精度的数据建模和分析方法。图由一组节点及其关系组成。

节点又称顶点，关系又称边。

关系带有权重的图叫作加权图，关系没有权重的图叫作无权图

了解了图的基本概念之后，你便可以尝试将一些问题抽象为图。比如，为了追踪软件项目中的传递依赖关系和冲突，有人为 Python 库做了这样一张依赖图。

节点间的最短路径

从一个节点到另一个节点的所有关系组成一条路径，关系权重之和最小的路径称为这两个节点间的最短路径。比如，下图展示了从节点 1 到节点 6 的最短路径，总权重是 2+6+4=12。

在如伦敦排污系统这种错综复杂的网络工程中，为了尽可能降低成本，优化最短路径是常规需求。

你可能听说过 Dijkstra 算法，它就是最著名的最短路径算法，用于查找图中一个节点到其他所有节点的最短路径。

在需要查找两点间的最优路线时，例如导航应用推荐行进路线，就可以使用最短路径算法。

另一个使用场景是找出人际关系网络中个体之间的分离度。六度分隔理论提出，世界上任何两个人都可以通过最多五个人（六度）连在一起。

最近有研究显示，Facebook 用户之间的平均最短路径长度为 4.57。

节点本身的重要程度

各个节点的重要程度不一定相同。以巴扎尔盖特的排污网络为例，一些节点需要重点监控，因为如果这些节点发生堵塞，给人们造成的影响更大。

同理，在人际关系网络中，某些人的人脉更广，他们在群体中的影响力也更大。

在衡量节点的重要程度时，一种常用的图算法是中间中心性算法。简单地说，一个节点的中间中心度是指它在网络中其他两个节点之间的最短路径中出现的次数。

中间中心度越高，节点对信息传播的影响就越大，它的缺失就越会影响网络的整体连通性。在下图中，红色节点的中间中心度最小，蓝色节点的中心度则最大。

莎士比亚曾说，世界是一个大舞台。在今天看来，世界是一张大图！将复杂的现实问题抽象为图，通过图算法进行分析，你就能洞悉复杂问题的本质。

图算法已经广泛用于各行各业的数据分析，营销归因分析、欺诈网络检测、传染病溯源、客户旅程建模、安全事故原因分析，甚至连莎士比亚戏剧的剧情分析，都会用到图算法。

参考文章：

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

图分析可以揭示复杂系统和大规模网络的运作机制，图算法为构建智能应用程序提供了快速建模的框架，有助于更准确、更快速地做出预测。包括商品推荐和欺诈检测在内的许多人工智能问题能转换为图论问题。

本书基于 Spark 和 Neo4j 讲解近20种常用的图算法，帮助读者拓展重要图分析类型的相关知识和能力，更快速地发现数据中的模式并找到更优的解决方案。

图灵官方小店
享受正版低价折扣

嘿 Siri，有没有「三天速成深度学习」的课程？