Page Rank

Mining Massive Datasets里的Page Rank讲得非常舒心。

用加权的有向图的邻接矩阵来表示网络:

QQ截图20150212091022

i行第j列的值m_{ij}不为0表示,有一条节点j指向节点i的边。m_{ij}的值为frac{1}{d_j}d_j表示节点j的出度。

用向量r表示各个节点的等级值:r=[1/N,dots,1/N],其中N为网络中的节点总数。

矩阵运算Mcdot r代表的含义是:每个节点都将自己的等级值平均地传给自己指向的节点。反复以此方法更新r:

r^{(t+1)}=Mcdot r^{(t)}

直至:

QQ截图20150212100335

对上面的网络试一试:

注意到[2/5;  2/5;  1/5]是矩阵M的特征向量,对应于3个页面的最终等级值。

网络中如果有'回环'或'死胡同',则会逐渐地将所有的等级值全部都吸收走,因此需要用'传送'的方法来解决。这是通过对矩阵M更新获得的,定义一个传送的概率beta,更新公式为:

A = beta M+ (1-beta)frac{1}{N}ecdot e^{T}

其中e为全为1的向量。

利用网民随机在网页间切换的直觉例子来解释,这样对矩阵更新就相当于:网民在浏览任何一个网页时均有beta的概率会跟随当前网页上的链接到一个新网页,同时也有1-beta的概率会随机打开一个新网页,并且一但网民到达一个没有任何链接的网页就会随机打开一个网页。这么更新矩阵,不仅避免了'回环'或'死胡同'的副作用,并且依据马尔科夫过程的理论,还确保了不管初始状态为何,马尔科夫过程一定会收敛。因此即只要足够多次迭代,一定会找到解。

一个例子:

otc_pagerank2

如果不跟新M:

即等级值全部被节点C'死胡同'所吸收了。

Leave a Reply

Your email address will not be published. Required fields are marked *