邻接行列的例子(采用了Apache 的在线手册)

PageRank 的行列阵是把这个邻接行列倒置后(行和列互换)，为了将各列(column)矢量的总和变成 1 (全概率), 把各个列矢量除以各自的链接数(非零要素数)。这样作成的行列被称为「推移概率行列」，含有 N 个概率变量，各个行矢量表示状态之间的推移概率。倒置的理由是，PageRank 并非重视「链接到多少地方」而是重视「被多少地方链接」。

PageRank 的计算，就是求属于这个推移概率行列最大特性值的固有矢量(优固有矢量)。

这是因为，当线性变换系 t→∞ 渐近时，我们能够根据变换行列的"绝对价值最大的特性值"和"属于它的固有矢量"将其从根本上记述下来。换句话说，用推移概率行列表示的概率过程，是反复对这个行列进行乘法运算的一个过程，并且能够计算出前方状态的概率。

再者，虽然听起来很难,但是求特性值和固有矢量的值是能够严密分析的一种基础的数学手段。我们能够自由地给矢量的初始值赋值，但是因为不断地将行列相乘，得到的矢量却会集中在一些特定数值的组合中。我们把那些稳定的数值的组合称为固有矢量，把固有矢量中特征性的标量(scalar)称为特性值，把这样的计算方法总称为分解特性值，把解特性值的问题称为特性值问题。

(*注) 对 N 次的正方行列 A 把满足 Ax =λx 的数 λ 称为 A 的特性值，称 x 为属于 λ 的固有矢量。如果你怎么也不能适应行列的概念的话，你也可以考虑 N×N 的二元排列就可以了。同时，也可以把矢量考虑成为长度为 N 的普通的(一元)排列就可以了。

简单的例子

让我们用简单的例子来试着逐次计算 PageRank 。首先考虑一下有像下图表示那样的链接关系的7个HTML文件。并且，这些HTML文件间的链接关系只是闭合于这1-7的文件中。也就是说，除了这些文档以外没有其他任何链接的出入。另外请注意，所有的页面都有正向和反向链接(即没有终点)，这也是后面将提出的一个重要假定,在此暂且不深入探讨。

表示页面间互相链接关系的推移图

首先，把这张推移图图表构造的邻接列表表示为排列式，就有以下式子。即，根据各个链接源ID列举链接目标的ID。

链接源I D 	链接目标 ID
1		2,3 ,4,5, 7
2		1
3		1,2 
4		2,3,5
5 		1,3,4,6 
6		1,5
7		5

以这个邻接列表中所表示的链接关系的邻接行列 A 是以下这样的 7×7 的正方行列。一个仅有要素 0 和 1 位图行列(bitmap matrix)。横向查看第 i 行表示从文件 i 正向链接的文件ID。

A = [
	 0, 1, 1, 1, 1, 0, 1; 
	 1, 0, 0, 0, 0, 0, 0;
	 1, 1, 0, 0, 0, 0, 0; 
	 0, 1, 1, 0, 1, 0, 0;
	 1, 0, 1, 1, 0, 1, 0;
	 1, 0, 0, 0, 1, 0, 0; 
	 0, 0, 0, 0, 1, 0, 0; 
 ]

PageRank 式的推移概率行列 M ，是将 A 倒置后将各个数值除以各自的非零要素后得到的。即以下这个 7×7 的正方行列。横向查看第 i 行非零要素表示有指向文件 i 链接的文件ID(文件 i 的反向链接源)。请注意，各纵列的值相加的和为 1(全概率)。

M = [ 
	0, 	1,	1/2,	0,	1/4,	1/2,	0; 
	1/5,	0,	1/2,	1/3,	0,	0,	0; 
	1/5,	0,	0,	1/3,	1/4,	0,	0; 
	1/5,	0,	0,	0,	1/4,	0,	0; 
	1/5,	0,	0,	1/3,	0,	1/2,	1; 
	0,	0,	0,	0,	1/4,	0,	0;
	1/5,	0,	0,	0,	0,	0,	0;
]

表示 PageRank 的矢量 R (各个的页面的等级数的队列)，存在着 R = cMR 的关系(c 为定量)。在这种情况下，R 相当于线形代数中的固有矢量，c 相当于对应特性值的倒数。为了求得 R ，只要对这个正方行列 M 作特性值分解就可以了。

在分解特性值时有相应的各种各样的数值分析法,但是本文将不在这里对各种方法详细说明，请读者自己去阅读一本恰当的教科书(在你的暑假里一定有这么一本被埋没的教科书)。在此，我们就暂且使用决 GNU Octave 这个计算程序实际计算一下特性值和固有矢量。