词汇表

选择左侧的一个关键字...

日常生活中的图表

阅读时间: ~5 min
此页面已自动翻译,可能包含错误。如果您想帮助我们审核翻译,请与我们取得联系!

在前几章中,我们已经看到了图论的许多不同应用,尽管其中有些是人为的。但是事实证明,图是日常生活中许多对象,概念和过程的基础。

例如,Internet是一个庞大的虚拟图。每个顶点都是一个单独的网页,每个边缘都意味着两个页面之间存在超链接。请注意,链接仅以一种方式进行,因此此图是有 ,并且该图非常非常大

某些网站,例如Wikipedia或Facebook,具有很多传入链接,而许多较小的网站可能只有很少的传入链接。这是Google用于对搜索结果进行排序的基本概念。

具有更多传入链接的网站往往质量更高,应显示在搜索结果的顶部。例如,当搜索“伦敦”时,会在伦敦的小商店或生活在伦敦的人们的博客之前显示官方的旅游信息网站。基于图论的简单想法,即网页排名算法 ,使Google明显优于其他早期搜索引擎。

互联网是人类有史以来最大的网络。此图显示了连接到Internet的所有服务器的很小一部分:

© LyonLabs, LLC and Barrett Lyon, 2014

网站和超链接形成_虚拟_图形时,计算机,服务器,路由器,电话线和电缆也存在_物理_网络。

每次拨打电话或加载网站时,网络运营商都必须找到一种连接发送方和接收方的方法,而不会超出任何单独的电缆或连接的容量。图论和概率使保证可靠的服务成为可能,例如通过在特定连接繁忙时查找转移。

图在运输和导航中也起着重要作用。所有的航班,火车和地铁网络都形成图表,可在创建有效的时间表时使用。最可识别的图表之一是伦敦地铁地图:

所有道路和高速公路也形成了一个大型网络,当计算出两个给定点之间的最短路线时,诸如Google Maps这样的导航服务便会使用该网络。

未来, 智能交通系统将使用从智能手机和自动驾驶汽车收集的位置数据,通过更有效地安排汽车路线来减少拥堵和事故。这样可以每年节省数百万小时的行车时间,显着减少污染,并使紧急服务的行驶速度更快。

此图显示了横跨北欧的商业航空公司航班网络。

科学,工程或日常生活中还有无数其他图表:

分子中的原子与晶格之间的链接形成一个图。

可以使用网络对疾病和流行病的传播进行建模。

在生物学中,显示物种祖先的进化树形成图。

电路和计算机芯片的不同组件形成一个网络。

语言的语法结构可以使用图形建模,例如创建翻译算法。

图在概率博弈论金融数学中也有许多应用。

社交网络

最后,让我们考虑一下日常生活中存在的图表的一个特别好的例子:社交媒体。在这里,顶点表示和边缘代表友谊,喜欢,订阅或关注者。

当我们绘制社交媒体图时,我们可能会看到某些共同的朋友 ,他们可能去过同一所学校或住在同一座城市。我们还可以确定人们的中心性 ,这取决于顶点的连接程度,并且可以衡量一个人在社交媒体上的受欢迎程度。

2014年,Facebook拥有14亿活跃用户,总计超过2000亿友谊。所有Facebook用户中有一半拥有200多个朋友,并且由于我们的大多数朋友都有相似数量的朋友,因此我们很容易拥有成千上万的朋友

现在,一个令人兴奋的问题是:如果您选择任意两个Facebook用户,则需要遵循多少“友谊优势”?例如,朋友之间的距离是 ,朋友之间的距离是 ,依此类推。

2016年,Facebook进行了一项研究,以确定其用户如何相互连接。他们发现,平均而言,您最多通过3.57个其他人与Facebook上的_任何_其他人建立联系。其中包括名人,政客甚至皇室!

换句话说,如果您选择全世界数十亿Facebook用户中的任何一个,则他们可能会有一个朋友的朋友,而该朋友认识您其中一个朋友的朋友。我们说有3.57 度的分离度

Geographic visualisation of all Facebook friendships in 2010.

1929年,匈牙利作家Frigyes Karinthy首次提出“六度分离”的想法时,没有互联网或社交媒体,但是世界已经开始变得更加互联。

1967年, 斯坦利·米尔格拉姆Stanley Milgram)进行了首次实证实验,其中邀请了296位居住在内布拉斯加州和堪萨斯州的参与者向居住在马萨诸塞州波士顿的特定人士致函。他们都必须选择一个朋友来寄信,然后由他选择另一个朋友。在每一步中,这封信都靠近波士顿。米尔格拉姆发现,平均而言,只有5.2个中间朋友–分离度为5.2度。

如今,我们每个人都是无数无形图的一部分,这些图构成了我们的社会互动,旅行,互联网和技术,科学等等的基础。