提供给用户无偏见的搜索结果。谷歌声称,“我们软件的核心就是网页排序(PageRa
k)。”正如我们将要看到的,技巧就是让网页自身按照重要性进行排序。
如何辨别谁重要
如果你曾建立过一个网页,你应该会列入一些你感兴趣的链接,它们很容易使你点击到其它含有重要、可靠信息的网页。这样就相当于你肯定了你所链接页面的重要性。谷歌的网页排序算法每月在所有网页中进行一次受欢迎程度的评估,以确定哪些网页最重要。网页排序算法的提出者,谢尔盖布林SergeyBri
和拉里佩奇Lawre
cePage的基本想法是:一个网页的重要性是由链接到它的其他网页的数量及其重要性来决定。
我们对任意一个网页P,以IP来表述其重要性,并称之为网页的网页排序。在很多网站,你可以找到一个近似的网页排序值。(例如,美国数学会的首页目前的网页排序值为8,最高分是10。你可以试试找到一个网页排序值为10的网页吗?)这个网页排序值仅是一个近似值,因为谷歌拒绝提供真实的网页排序值,以阻止那些试图干扰排序的行为。
网页排序是这样确定的。假定网页Pj有lj个链接。如果这些链接中的一个链接到网页Pi,那么网页Pj将会将其重要性的1lj赋给Pi。网页Pi的重要性就是所有指向这个网页的其他网页所贡献的重要性的加和。换言之,如果我们记链接到网页Pi的网页集合为Bi,那么
fIPi∑Pj∈BiIPjlj
这或许让你想起“先有鸡还是先有蛋”的问题:为了确定一个网页的重要性,我们首先得知道所有指向它的其他网页的重要性。然而,我们可将这个问题改写为一个更数学化的问题。
首先建立一个矩阵,称为超链矩阵(hyperli
kmatrix),HHij,其中第
i行第j列的元素为
Hij1lj0如果Pj∈Bi上述条件不成立
注意到H有一些特殊的性质。首先,它所有的元都是非负的。其次,除非对应这一列的网页没有任何链接,它的每一列的和为1。所有元均非负且列和为1的矩阵称为随机矩阵,随机矩阵将在下述内容中起到重要作用。
我们还需要定义向量IIPi,它的元素为所有网页的网页排序重要性的排序值。前面定义的网页排序可以表述为
IHI
换言之,向量I是矩阵H对应特征值1的特征向量。我们也称之为矩阵H的平r