程序设计导论：Python语言实践

1.6　应用案例：随机Web冲浪模型

Web通信已成为人们日常生活中不可分割的一部分。自从Web发展伊始，Web通信就成为Web结构科学研究的一部分，而且一直是一个热门研究领域。下面我们将讨论一个Web的简单模型，该模型被证明是理解Web基本特征的非常有效的途径。该模型的许多变种被广泛使用，并且已经成为爆炸式发展的Web搜索应用程序的关键因素之一。

该模型被称为随机冲浪模型（random surfer model），其描述十分简单。假定Web包含固定数量的网页（page），每个网页包含规定数量的超链接（link），每个超链接指向其他网页。研究的目标为一个人（随机冲浪者）随机从一个页面到另一个页面之间的行为，可通过在地址栏键入网页地址或单击当前页面中的超链接跳转到下一个页面。网页和超链接示意图如图1-6-1所示。

图1-6-1　网页和超链接示意图

Web模型背后的基本数学模型称为图（graph），有关图的详细信息将在本书最后讨论（4.5节中）。处理图的细节也将推延到4.5节。目前我们专注于概率模型的相关计算。概率模型之所以被广泛研究，是因为其可精确描述随机冲浪者的行为。

研究随机冲浪模型的第一步是构建更精确的描述模型，其关键之处在于定义从一个页面随机到一个页面的含义。如下的直觉“90-10法则”包含了跳转到一个新页面的两种方法：其一，假定整个上网期间90%的时间，随机冲浪者通过随机单击当前页面的超链接（选择每个超链接的概率相同）跳转到下一个页面；其二，剩下的10%时间，随机冲浪者通过在地址栏输入随机地址（选择每个页面的概率相同）跳转到下一个页面。 ...