1.6 案例研究:随机网络冲浪

通过网络进行交流已经成为日常生活中不可或缺的一部分。我们能通过这种方式顺畅交流,在一定程度上得益于对网络结构的科学研究,这是自网络技术产生以来就在积极研究的课题。接下来我们研究一个简单的网络模型,这是一个有效地理解网络特性的方法。这种模型的变体被广泛使用,并成为网络搜索爆炸式增长的关键因素。

该模型被称为随机冲浪(random surfer)模型。这种模型非常简单。我们将网络看作是一组固定的网页,每个网页都包含一组超链接(hyperlink),每个超链接都链接到其他网页(为了简洁起见,我们使用术语网页和链接)。本节中我们研究网络冲浪者在网页间随机跳转的过程,他们通过在地址栏中输入网页名称,或者单击当前网页上的链接来跳转。

网络链接结构的基础数学模型被称为图(graph),我们将在本书后半部分(4.5节)详细研究图及图的处理。现在我们专注于一个自然的、精心研究的概率模型相关的计算,这个模型准确地描述了随机冲浪者的行为。

网页和链接

研究随机冲浪模型的第一步是用公式更精确地表示它。问题的关键在于明确网页之间随机跳转的意义。接下来我们使用一种直观的90-10规则描述跳转到新网页的两种方法:假设随机冲浪者有90%的概率会通过随机点击当前网页上的链接实现跳转(每个链接以相等的概率被选中),另外10%的概率随机冲浪者会直接进入一个随机网页(例如,以手动输入网址的形式打开网页——译者注)(网络上所有网页被选中的概率相同)。

你很快会发现这个模型有缺陷,因为你从自身的经验中知道一个真正的网络冲浪者的行为并不是那么简单: ...

Get 计算机科学导论:跨学科方法 now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.