你的位置:首页 > ASP.net教程

[ASP.net教程]PageRank 计算博客园用户排名


      PageRank 通过网页与网页之间的链接关系计算各网页权重,一般权重高的网页特点是:链接向它的网页数量多、链向它的网页其权重也较高。PageRank 就是通过这样的连接关系,一轮轮迭代计算后得出各网页的权重。

      思路拓展一下,其实人与人之间也是连接着的,在社会的人际关系网中,每个人的社会地位和身价也是不同的。以微博为例,我们都有关注者和粉丝(类似网页之间的链接),可以发现所谓的“大V”基本上粉丝数量多,并且粉丝里不乏很多其他“大V”,所以这个帐号的价值就大。

      同样博客园也具有类似的社交关系,用户可以选择“关注的人”以及“关注我的人”,理论上是可以用 PageRank 算法算出哪些用户更受大家欢迎,于是本文代大家八卦了一下,文章较长,只想看排名的同学请直接拉到末尾。。。

PageRank 算法简介

1. 数学模型

      《数学之美》第10章的延伸阅读部分,对 PageRank 的计算方法进行了简单介绍,但原书有些错误,修改后描述如下:

      我们设向量 B 为第一、第二…第N个网页的网页排名

      矩阵 A 代表网页之间的权重输出关系,其中 amn 代表第 m 个网页向第 n 个网页的输出权重。

      输出权重计算较为简单:假设 m 一共有10个出链,指向 n 的一共有2个,那么 m 向 n 输出的权重就为 2/10。

      现在问题变为:A 是已知的,我们要通过计算得到 B。

      假设 Bi 是第 i 次迭代的结果,那么

      初始假设所有网页的排名都是 1/N (N为网页总数量),即

      通过上述迭代计算,最终 Bi 会收敛,即 Bi 无限趋近于 B,此时 B = B × A。

2. 具体示例

      假设有网页A、B、C、D,它们之间的链接关系如下图所示

      计算 B1 如下:

      不断迭代,计算结果如下:

第 1次迭代: 0.125, 0.333, 0.083, 0.458
第 2次迭代: 0.042, 0.500, 0.042, 0.417
第 3次迭代: 0.021, 0.431, 0.014, 0.535
第 4次迭代: 0.007, 0.542, 0.007, 0.444
第 5次迭代: 0.003, 0.447, 0.002, 0.547
第 6次迭代: 0.001, 0.549, 0.001, 0.449
第 7次迭代: 0.001, 0.449, 0.000, 0.550
第 8次迭代: 0.000, 0.550, 0.000, 0.450
第 9次迭代: 0.000, 0.450, 0.000, 0.550
第10次迭代: 0.000, 0.550, 0.000, 0.450
... ...

      我们可以发现,A 和 C 的权重变为0,而 B 和 D 的权重也趋于在 0.5 附近摆动。从图中也可以观察出:A 和 C 之间有互相链接,但它们又把权重输出给了 B 和 D,而 B 和 D之间互相链接,并不向 A 或 C 输出任何权重,所以久而久之权重就都转移到 B 和 D 了。

PageRank 的改进

      上面是最简单正常的情况,考虑一下两种特殊情况:

   

      第一种情况是,B 存在导向自己的链接,迭代计算过程是:

第 1次迭代: 0.125, 0.583, 0.083, 0.208
第 2次迭代: 0.042, 0.833, 0.042, 0.083
第 3次迭代: 0.021, 0.931, 0.014, 0.035
第 4次迭代: 0.007, 0.972, 0.007, 0.014
第 5次迭代: 0.003, 0.988, 0.002, 0.006
第 6次迭代: 0.001, 0.995, 0.001, 0.002
第 7次迭代: 0.001, 0.998, 0.000, 0.001
第 8次迭代: 0.000, 0.999, 0.000, 0.000
第 9次迭代: 0.000, 1.000, 0.000, 0.000
第10次迭代: 0.000, 1.000, 0.000, 0.000
... ...

      我们发现最终 B 权重变为1,其它所有网页的权重都变为了0 =。=!

      第二种情况是 B 是孤立于其它网页的,既没有入链也没有出链,迭代计算过程是:

第 1次迭代: 0.125, 0.000, 0.125, 0.250
第 2次迭代: 0.063, 0.000, 0.063, 0.125
第 3次迭代: 0.031, 0.000, 0.031, 0.063
第 4次迭代: 0.016, 0.000, 0.016, 0.031
第 5次迭代: 0.008, 0.000, 0.008, 0.016
第 6次迭代: 0.004, 0.000, 0.004, 0.008
第 7次迭代: 0.002, 0.000, 0.002, 0.004
第 8次迭代: 0.001, 0.000, 0.001, 0.002
第 9次迭代: 0.000, 0.000, 0.000, 0.001
第10次迭代: 0.000, 0.000, 0.000, 0.000
... ...

      我们发现所有网页权重都变为了0 =。=!

      出现这种情况是因为上面的数学模型出现了问题,该模型认为上网者从一个网页浏览下一个网页都是通过页面的超链接。想象一下正常的上网情景,其实我们在看完一个网页后,可能直接在浏览器输入一个网址,而不通过上一个页面的超链接。

      我们假设每个网页被用户通过直接访问方式的概率是相等的,即 1/N,N 为网页总数,设矩阵 e 如下:

      设用户通过页面超链接浏览下一网页的概率为 α,则直接访问的方式浏览下一个网页的概率为 1 - α,改进上一节的迭代公式为:

      通常情况下设 α 为0.8,上一节”具体示例”的计算变为如下:

     迭代过程如下:

第 1次迭代: 0.150, 0.317, 0.117, 0.417
第 2次迭代: 0.097, 0.423, 0.090, 0.390
第 3次迭代: 0.086, 0.388, 0.076, 0.450
第 4次迭代: 0.080, 0.433, 0.073, 0.413
第 5次迭代: 0.079, 0.402, 0.071, 0.447
第 6次迭代: 0.079, 0.429, 0.071, 0.421
第 7次迭代: 0.078, 0.408, 0.071, 0.443
第 8次迭代: 0.078, 0.425, 0.071, 0.426
第 9次迭代: 0.078, 0.412, 0.071, 0.439
第10次迭代: 0.078, 0.422, 0.071, 0.428
第11次迭代: 0.078, 0.414, 0.071, 0.437
第12次迭代: 0.078, 0.421, 0.071, 0.430
第13次迭代: 0.078, 0.415, 0.071, 0.436
第14次迭代: 0.078, 0.419, 0.071, 0.431
第15次迭代: 0.078, 0.416, 0.071, 0.435
第16次迭代: 0.078, 0.419, 0.071, 0.432
第17次迭代: 0.078, 0.416, 0.071, 0.434
第18次迭代: 0.078, 0.418, 0.071, 0.432
第19次迭代: 0.078, 0.417, 0.071, 0.434
第20次迭代: 0.078, 0.418, 0.071, 0.433
... ...

PageRank 算法实现

      互联网的网页数量是 Billion 级别的,所以不可能一下子初始化矩阵 A ,试想一下 10亿 × 10亿 的矩阵是什么概念!

      这时就用到稀疏矩阵了,定义稀疏矩阵的结构如下(其实是稀疏矩阵的一行):

public class SparseMatrix<T>{  public SparseMatrix(T head, double rank)  {    Head = head;    LinkedItems = new List<T>();    Rank = rank;  }  /// <summary>  ///   稀疏矩阵头  /// </summary>  public T Head { get; private set; }  public double Rank { get; set; }  /// <summary>  ///   稀疏矩阵链接的项目  /// </summary>  public List<T> LinkedItems { get; set; }  public void AddLink(T linkedItem)  {    LinkedItems.Add(linkedItem);  }}

      第一节中的链接示例图,就可以用如下代码表示:

Dictionary<char, SparseMatrix<char>> matrix = new Dictionary<char, SparseMatrix<char>> {  {'A', new SparseMatrix<char>('A', 0.25){LinkedItems = new List<char>{'B', 'C', 'D'}}},  {'B', new SparseMatrix<char>('B', 0.25){LinkedItems = new List<char>{'D'}}},  {'C', new SparseMatrix<char>('C', 0.25){LinkedItems = new List<char>{'A', 'D'}}},  {'D', new SparseMatrix<char>('D', 0.25){LinkedItems = new List<char>{'B'}}}};

      通过稀疏矩阵计算,与原先的整个矩阵行列式计算有较大不同,计算次序已经发生了变化。原先矩阵是一行乘以权重的竖列,稀疏矩阵则变为类似于按原先矩阵的竖列与权重相乘。矩阵运算中当然不允许 1 × N 矩阵与 1 × N 矩阵相乘的情况,我们能做的就是先将一项项算好,比如先算 A 这一行,算出 A 给 B、C、D输出多少权重,在一个类似字典类型的数据结构里,给 B、C和 D 各加上一笔,像是一个 Map-Reduce 过程。

public class MapReduce<T>{  private readonly Dictionary<T, double> _map;  public MapReduce()  {    _map = new Dictionary<T, double>();  }  public double Reduce(T key, double value)  {    if (_map.ContainsKey(key))    {      _map[key] += value;      return _map[key];    }    _map.Add(key, value);    return value;  }  public double GetOrSetDefaultValue(T key)  {    if (_map.ContainsKey(key))      return _map[key];    _map.Add(key, 0.0);    return 0.0;  }}

      PageRank 设计如下:

public class PageRank<T>{  private MapReduce<T> _mapReduce;  private readonly double _stayProbability;  private readonly double _averageRank;  /// <summary>  ///   /// </summary>  /// <param name="totalCount">项目总数</param>  /// <param name="stayProbability">保持留在某个项目, 不跳转的概率</param>  public PageRank(int totalCount, double stayProbability = 0.8)  {    _mapReduce = new MapReduce<T>();    _stayProbability = stayProbability;    _averageRank = 1.0 / totalCount;  }  /// <summary>  ///   计算下一轮PageRank  /// </summary>  public void NextCircle()  {    _mapReduce = new MapReduce<T>();  }  /// <summary>  ///   计算一条行列式  /// </summary>  /// <param name="sparseMatrix">稀疏矩阵</param>  public void Calc(SparseMatrix<T> sparseMatrix)  {    var outputRank = 1.0 / sparseMatrix.LinkedItems.Count;    foreach (var item in sparseMatrix.LinkedItems)    {      _mapReduce.Reduce(item,        _stayProbability * outputRank * sparseMatrix.Rank);    }    //当没有其它链接指向Head的时候, 以防漏项    _mapReduce.Reduce(sparseMatrix.Head, (1 - _stayProbability) * _averageRank);  }  /// <summary>  ///   一轮PageRank迭代之后, 获取最新的PageRank并更新  /// </summary>  /// <param name="key"></param>  /// <returns></returns>  public double GetCurrentRank(T key)  {    return _mapReduce.GetOrSetDefaultValue(key);  }}

      调用示例:

var matrix = new Dictionary<char, SparseMatrix<char>> {  {'A', new SparseMatrix<char>('A', 0.25){LinkedItems = new List<char>{'B', 'C', 'D'}}},  {'B', new SparseMatrix<char>('B', 0.25){LinkedItems = new List<char>{'D'}}},  {'C', new SparseMatrix<char>('C', 0.25){LinkedItems = new List<char>{'A', 'D'}}},  {'D', new SparseMatrix<char>('D', 0.25){LinkedItems = new List<char>{'B'}}}};var pageRank = new PageRank<char>(matrix.Count);//计算30轮for (int i = 1; i <= 30; i++){  pageRank.NextCircle();  foreach (var item in matrix)  {    pageRank.Calc(item.Value);  }  foreach (var item in matrix)  {    var cRank = pageRank.GetCurrentRank(item.Key);    item.Value.Rank = cRank;  }  var str = string.Join(", ", matrix.Select(item => item.Value.Rank.ToString("N3")));  Console.WriteLine(string.Format("第{0,2}次迭代: {1}", i, str));}

      开源地址:https://github.com/CreateChen/PageRank

博客园用户权重计算

      写一个简单的网络爬虫,爬取博客园所有用户的 Id、关注的人等信息(过程略),最终得到如下结构的表格:

      首先八卦一下粉丝数量 Top 20,方便与 PageRank 算出的结果做对比。

      下面进入真正的 PageRank 计算了,利用第二节的程序计算,一次迭代计算速度很快,从数据库获取数据并且计算完毕只要6秒,更新数据库的 Rank 字段需要近30秒。下表展示的是第1轮迭代、第15轮的用户的权重:

排名NickNameRankNickNameRank
1梦想天空(山边小溪)0.002165梦想天空(山边小溪)0.001346
2Fish Li0.00192dudu0.001334
3汤姆大叔0.001514Artech0.00102
4Jimmy Zhang0.001281Fish Li0.000947
5M了个J0.001244司徒正美0.000786
6Artech0.001164李永京0.000746
7农民伯伯0.001161汤姆大叔0.0007
8司徒正美0.000987趣味苹果开发0.000677
9Vamei0.000953通用C#系统架构0.000601
10tornadomeet0.000858M了个J0.00059
11伍华聪0.000787Jimmy Zhang0.000586
12一线码农0.000786banban0.000576
13吴秦0.00075Milo Yip0.000532
14dudu0.000729张善友0.000488
15虫师0.000722Jeffrey Zhao0.00047
16小坦克0.000691觉先0.000462
17Rollen Holt0.000649SoftwareTeacher0.000444
18圣殿骑士0.000545博客园团队0.000434
19CareySon0.000538TerryLee0.000434
20文顶顶0.000538胡尐睿丶0.00043
21小洋(燕洋天)0.000535T2噬菌体0.000422
22虾皮0.000529农民伯伯0.000415
23JerryLead0.000526Anytao0.000411
24李永京0.000508圣殿骑士0.000411
25方倍工作室0.000505深蓝色右手0.000406
26cloudgamer0.000486伍华聪0.0004
27杨中科0.000483一线码农0.000399
28TerryLee0.000467小洋(燕洋天)0.000388
29张善友0.000466Cat Chen0.000374
30深蓝色右手0.000457CareySon0.000371
31谦虚的天下0.000445Vamei0.000365
32通用C#系统架构0.000435ziqiu.zhang0.000358
33胡尐睿丶0.00042周 金根0.000351
34三生石上0.000413伍迷0.000342
35KenshinCui0.000397xiaotie0.000332
36博客园团队0.000389谦虚的天下0.000331
37酸奶小妹0.000387冠军0.000329
38Milo Yip0.000372吴秦0.000327
39伍迷0.00037cloudgamer0.000318
40子龙山人0.000369tornadomeet0.000305
41Insus.NET0.000369酸奶小妹0.0003
42菩提树下的杨过0.000369小坦克0.0003
43万一0.000368【当耐特】0.000285
44_Luc_0.000367chenkai0.000277
45夏天的森林0.000354Justin0.000274
46ziqiu.zhang0.000351装配脑袋0.000272
47Jeffrey Zhao0.000351虫师0.000271
48叶小钗0.000343菩提树下的杨过0.000271
49真 OO无双0.000343Gnie0.00027
50SoftwareTeacher0.000337张逸0.000252
51webabcd0.000333LeftNotEasy0.000245
52T2噬菌体0.000331小静(Cathy)0.00024
53Ruthless0.000328Gray Zhang0.000237
54peida0.000327Jesse Liu0.000237
55陈梓瀚(vczh)0.000324JerryLead0.000231
56聂微东0.000322webabcd0.000228
57Jesse Liu0.000317fly in ocean0.000225
58【当耐特】0.000288Anders Cui0.000221
59西西吹雪0.000286代震军0.000221
60snandy0.000286COM张0.00022
61Phinecos(洞庭散人)0.000286楠小楠0.00021
62David_Tang0.000283何戈洲0.00021
63yangecnu0.000282三生石上0.000207
64孤傲苍狼0.000278路过秋天0.000204
65Learning hard0.000277Jake Lin0.000203
66Stephen_Liu0.000272飞洋过海0.000201
67Terry_龙0.000269陈希章0.0002
68xiaotie0.000269叶小钗0.000198
69Leo Chin0.000269eaglet0.000197
70海 子0.000267陈梓瀚(vczh)0.000197
71Barret Lee0.000264_Luc_0.000194
72路过秋天0.000263snandy0.000191
73Dsp Tian0.000255新瓶老酒0.000186
74Devin Zhang0.000255Bēniaǒ0.000185
75苍梧0.000252dax.net0.000185
76觉先0.000251麒麟.NET0.000185
77周 金根0.00025方倍工作室0.000183
78冠军0.000249万一0.000181
79何戈洲0.000242陈硕0.000179
80刘冬.NET0.000237任力0.000177
81hoojo0.000236Franky0.000177
82Orisun0.000236虾皮0.000173
83CrazyBingo0.000235Stephen_Liu0.000172
84代震军0.000234石破天惊0.000172
85minglz0.000231岑安0.000171
86Alexia(minmin)0.000226杨中科0.00017
87Gnie0.000226iOS之旅0.00017
88邹华栋0.000225横刀天笑0.000169
89Samaritans0.000224邀月0.000168
90Aaron艾伦0.000222jv90.000165
91邀月0.000221聂微东0.000164
92Healtheon0.000219创想中国(羲闻)0.000164
93李林峰的园子0.000219CoderZh0.000163
94吕震宇0.000218Luminji0.000163
95沈逸0.000218winter-cn0.000163
96LeftNotEasy0.000213Rollen Holt0.000161
97陈希章0.000212金色海洋(jyk)阳光男孩0.000159
98Hongten0.000211重典0.000159
99创想中国(羲闻)0.000211阿一(杨正祎)0.000157
100Cat Chen0.000208夜里的烟0.000157

      如果你对完整的计算过程感兴趣,可以下载完整表格。想了解自己的权重及排名请在下方留言。

      当然在实际计算排名过程中,不单单依据粉丝与关注者之间的关系,还需要结合文章的质量、更新频率及数量,最后给一个综合的评分。总之:被关注数量越多、经常写文章、文章被赞的次数越多、评论次数多,就越能提升社区影响力。

本文链接:http://www.cnblogs.com/technology/p/PageRank.html