PageRank

用Matlab实现一个PageRank算法。

介绍

PageRank是一种对网页进行排名的算法，通过引用来判断网页的排名。

具体介绍自寻，可以看一下https://baike.baidu.com/item/google%20pagerank#2

题目

图中有六个明星，他们之间的箭头表示关注，比如Kim和Ryan互相关注，图片中间的数字是最终计算出的他们的PageRank。

Matlab实现

% Find PageRank of network by finding dominant evec
%
%      _       _       _             _
%     | (1-d)/N |     | l11, ..., l1n |
% R = |   ...   | + d | ..., ..., ... | R     
%     |_(1-d)/N_|     |_ln1, ..., lnn_|       
%
% R = c + d * L*D * R
% R = (I - d * L*D )\c
% 

clc;    %清屏

d = 0.85;  % damping factor

name = {'bill', 'ellen', 'jimmy', 'kim', 'paula', 'ryan'}; % celebrities'name
[bil, ell, jim, kim, pau, rya] = deal(1,2,3,4,5,6);        % celebrities'id，bil=1,ell=2...
n = length(name); % number of celebrities,n=6

L = zeros(n);   % 明星关注关系矩阵,一行是一个人，元素值表示他是否关注他人;一列也是一个人，元素值表示是否被他人关注
% if user j follows user i, then L(i,j) = 1
L(bil, [rya, ell]) = 1; % bil关注rya ell，下五行同理
L(ell, [jim, rya]) = 1;	
L(jim, [rya, pau, ell]) = 1;
L(kim, [jim, rya, ell]) = 1;
L(pau, [rya, ell])=1;
L(rya, [bil, jim, kim, pau, ell]) = 1;


% ot = out-degree, in = in-degree
ot = sum(L,1);  % 对每1列求和，得行向量，每一列是一个人，元素值为被关注次数
in = sum(L,2);  % 对每1行求和，得列向量，每一行是一个人，元素值为他关注了多少人

k = find(ot~=0); % 找到ot中不等于0的元素的下标,在此都不为0，返回行向量[1,2,3,..,6]
D = full(sparse(k,k,1./ot(k),n,n)); %对角矩阵，对角元素表示每个人对其他人的关注的分成
% L*D 是 6*6矩阵，一行、一列都是一个人，一行表示得到每个人的关注的分成，列表示对其他人关注的分成
c = (1-d)/n*ones(n,1);  % 值为(1-d)/n 的 n行列向量
I = eye(n); % n*n单位矩阵

R = (I - d*L*D)\c  % 注意是左除,得到6个人的PageRank

作者：@臭咸鱼

本文为作者原创，转载请注明出处：https://chouxianyu.github.io

欢迎讨论和交流!