算法课_PageRank_XXF

1、PageRank AlgorithmBy: Xu xiaofengMail: Date: 2014/12/2PageRank目录概览目录概览1: PR的起源的起源2: PR算法及特性算法及特性3: PR小结小结4: PR的应用的应用5: 作业作业3PageRankPR的起源的起源1：搜索引擎的出现：搜索引擎的出现：1990年由Montreal的McGill University三名学生发明的Archie（Archie FAQ）。动机：一个可以用文件名查找文件的系统，于是便有了Archie。Archie是第一个自动索引互联网上匿名FTP网站文件的程序，但它还不是真正的搜索引擎（资料检索系统）。2

2、：早期搜索引擎面临的问题：早期搜索引擎面临的问题：如何对搜索结果按重要性排序。方法: 1按时间/编号排。(设想一下返回几万个页面，会是什么情况) 2基于关键词匹配(类TF-IDF算法，但Term Spam使得，页面的排名可以被认为的提升，一个页面里隐藏了几万个“算法课”，页面的排名可能就会很高等)。3：PR的提出：的提出：在Google出现之前，曾出现过许多通用或专业领域搜索引擎。但拉里佩奇和谢尔盖布卢姆在论文The PageRank Citation Ranking Bringing Order to the Web(1998)中提出了PageRank算法，解决了如何对搜索结果按重要性排序如

3、何对搜索结果按重要性排序的问题，并以作者佩奇的名命名该算法。4PageRankPageRank的定义的定义1：是一种由搜索引擎根据网页之间相互的超链接计算的技术(维基百科)，而作为网页排名的要素之一，让链接来“投票”2：是一定时间内用户随机地沿着网页链接前进时对各个页面访问的固定分布，并以此来反映各个页面的重要性。(Google矩阵)网页链接节点关系图根据节点之间的链接关系，衡量出各个节点的重要程度5PageRankPageRank提出PageRank的理论假设： 数量假设：数量假设：在Web图模型中，如果一个页面节点接收到的其他网页指向的入链数量越多，那么这个页面越重要。质量假设：质量假设：

4、指向页面A的入链质量不同，质量高的页面会通过链接向其他页面传递更多的权重。所以越是质量高的页面指向页面A，则页面A越重要。BA6PageRankPageRank基本抽象： 1：每个网页抽象成一个节点。2：如果一个页面A有链接直接链向B，则存在一条有向边从A到B。(多个相同链接不重复计算边)7PageRankPageRank基本变量定义：u 单个页面Fu u指向的页面集合Bu 指向u的页面集合c 常数 (c 矩阵A，特征值为1，的特征向量引理：若矩阵A为正矩阵(即A的每个元素为正)则|2|1证明：矩阵A的特征值和AT相同，且任何一个非负方阵的每个特征值的模不大于其最大行的和(AT 最大行和为1)

5、。19PageRank收敛性证明收敛性证明随机选择一个n维向量X1 ；假设A的特征值和特征向量为a1-an和V1-Vn ，a1为最大特值X1可以被V1-Vn线性表示：其中b1到bn不全为0；11122n+nXbVbVbV20PageRank收敛性证明收敛性证明21PageRank初始值选择与迭代次数初始值选择与迭代次数R初始的选择不会影响最终的排名结果；初始的选择不会影响最终的排名结果；但会影响迭代次数。但会影响迭代次数。随机随机1/N22PageRankPageRank小结小结1：基本思想：有效地利用了 Web 所拥有的庞大链接构造的特性。2：前提假设：数量假设+质量假设。3：算法求解：迭代

6、的过程。4：问题处理：Dangling Links + Rank Sinks。5：最初目的：将返回结果按重要性排序。从许多优质的网页链接过来的网页，必定还是优质网页的回归关系，来判定所有网页的重要性。23PageRank算法特点算法特点1：是一个与查询无关的静态算法，所有网页的PageRank值通过离线计算获得；2：有效减少在线查询时的计算量，极大降低了查询响应时间。3：主题无关，PageRank忽略了主题相关性，导致结果的相关性和主题性降低4：旧的页面等级会比新页面高。因为即使是非常好的新页面也不会有很多上游链接，除非它是某个站点的子站点。5：用户个性化因素被忽略。24PageRankPag

7、eRank的应用的应用基于基于“关系关系”的的“排名排名”分析分析社交网络（意见领袖、用户影响力等）社交网络（意见领袖、用户影响力等）推荐系统（物品推荐、好友推荐等）推荐系统（物品推荐、好友推荐等）NLP（关键词提取、情感分析等）（关键词提取、情感分析等）。25PageRankTURankhttp:/ PS：第一题只能一人一组：第一题只能一人一组 存在这种节点的时候，可能会出现什么现象，怎么处理？（参考：参考：http:/ 用户： http:/ 关系： http:/ 0：uid 关注关注friendid | 1：双向关注：双向关注28PageRank作业作业2说明说明1：可以自己选一批用户，大小在：可以自己选一批用户，大小在1000+（含（含1000）2：算出所有用户的：算出所有用户的PR值，将结果发给我。值，将结果发给我。3：结果评测附加：结果评测附加：3.1：统计用户：统计用户PR值和用户粉丝数之间的皮尔森相关性和斯皮尔曼相关性。值和用户粉丝数之间的皮尔森相关性和斯皮尔曼相关性。参考：将数据导入数据库，选择好用户及关系，在计算参考：将数据导入数据库，选择好用户及关系，在计算PR29PageRankr