Python数学建模学习-PageRank算法

2024-04-15 17:12

本文主要是介绍Python数学建模学习-PageRank算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1-基本概念

PageRank算法是由Google创始人Larry Page在斯坦福大学时提出,又称PR,佩奇排名。主要针对网页进行排名,计算网站的重要性,优化搜索引擎的搜索结果。PR值是表示其重要性的因子。

中心思想:

  • 数量假设:在网页模型图中,一个网页接受到的其他网页指向的入链(In-Links)越多,说明该网页越重要。

  •  质量假设:当一个质量高的网页指向(Out-Links)一个网页,说明这个被指的网页重要。

  •  入链出链模型图1:

  •  入链出链模型图2:[把每个网页当成一个节点]

2-算法和公式 

PageRank公式

  •  PR(Ti)代表的是其他节点的(指向A节点)PR值
  • L(Ti)代表的是其他节点的(指向A节点)出链数
  • i 代表的是循环次数

i=0时, 

i=1时,PR(A)为:

 i=1时,PR(B)为:

i=1时,PR(C)为: 

i=1时,PR(D)为: 

 主要找到入链数和出链数

可以求得:

矩阵化表达:使用转移概率矩阵/马尔可夫矩阵

 将左图内容转换为右图矩阵:

从图可以看出:

从A将跳转到B或C的概率为1/2

从B将跳转到C的概率为1

从C将跳转到A或D的概率为1/2

从D将跳转到A的概率为1

通过矩阵表达快速计算PR值

公式:PR\left ( a\right )=M*V

其中M 表示转移概率矩阵/马尔可夫矩阵

 其中V 表示上一次得到的PR值

根据公式可得第一次迭代得到的PR值:

0*1/4+0*1/4+1/2*1/4+1*1/4=3/8

1/2*1/4+ 0*1/4+0*1/4+0*1/4=1/8

1/2*1/4+ 1*1/4+0*1/4+0*1/4=3/8

0*1/4+0*1/4+1/2*1/4+0*1/4=1/8

通过第一次迭代得到的PR值,我们可以得到第二次迭代的PR值:

此时的排名为:

AC;BD

再结合最开始的公式看:

 同理可求出其他PR值。

3-Dead Ends 问题

 使用转移概率矩阵快速计算PR值:

 解决方法:Teleport

 4-Dead Ends 问题修正公式

 5-Spider Traps问题

 

6- Spider Traps问题解决方案:Random Teleport

  • 步骤1:将节点图,转换成列转移概率矩阵
  • 步骤2:修正M

1转换成列转移概率矩阵

2 修正M

\beta 通常设置为0.85

第一次迭代的PR值为:

 7-Spider Traps问题修正公式 

 8-代码案例练习[使用Jupyter Notebook编程]

import networkx as nx
import matplotlib.pyplot as plt 
import random
Graph = nx.DiGraph()
Graph.add_nodes_from(range(0,100))
for i in range(100):j =random.randint(0,100)k =random.randint(0,100)Graph.add_edge(k,j)
nx.draw(Graph,with_labels=True)
plt.show()

pr = nx.pagerank(Graph,max_iter=100,alpha =0.01)
print(pr)

输出结果: 

{0: 0.009843202124104186, 1: 0.009843202124104186, 2: 0.009941633650425134, 3: 0.009974526667449609, 4: 0.009892665412017136, 5: 0.009843202124104186, 6: 0.009843202124104186, 7: 0.009843202124104186, 8: 0.009892665412017136, 9: 0.00997535174995786, 10: 0.009843202124104186, 11: 0.00989258290376631, 12: 0.009941633650425134, 13: 0.00989241788726466, 14: 0.009941633650425134, 15: 0.010024237480115035, 16: 0.009843202124104186, 17: 0.010041880358264236, 18: 0.009941963683428435, 19: 0.009843202124104186, 20: 0.00989291293676961, 21: 0.009843202124104186, 22: 0.009867810005684423, 23: 0.00989241788726466, 24: 0.009843202124104186, 25: 0.009975475512334098, 26: 0.00989258290376631, 27: 0.009941633650425134, 28: 0.00989291293676961, 29: 0.009868057530436899, 30: 0.010041385308759285, 31: 0.009843202124104186, 32: 0.009982839305644121, 33: 0.009843202124104186, 34: 0.009843202124104186, 35: 0.010041220292257635, 36: 0.00994188117517761, 37: 0.009876342665881136, 38: 0.00989258290376631, 39: 0.00987642517413196, 40: 0.009942004937553848, 41: 0.009843202124104186, 42: 0.00989241788726466, 43: 0.009909263185655886, 44: 0.009991096938338084, 45: 0.009892665412017136, 46: 0.009992293307975048, 47: 0.009942128699930086, 48: 0.009942128699930086, 49: 0.009843202124104186, 50: 0.00989241788726466, 51: 0.009868057530436899, 52: 0.009843202124104186, 53: 0.009867810005684423, 54: 0.009843202124104186, 55: 0.009843202124104186, 56: 0.009876342665881136, 57: 0.009941633650425134, 58: 0.009941963683428435, 59: 0.009843202124104186, 60: 0.009843202124104186, 61: 0.009843202124104186, 62: 0.009843202124104186, 63: 0.009843202124104186, 64: 0.009974774192202085, 65: 0.00989291293676961, 66: 0.009843202124104186, 67: 0.009942623749435036, 68: 0.00989241788726466, 69: 0.009843202124104186, 70: 0.009892665412017136, 71: 0.009843202124104186, 72: 0.009843202124104186, 73: 0.00999200452909716, 74: 0.009876672698884436, 75: 0.009876122643878936, 76: 0.009867810005684423, 77: 0.009941633650425134, 78: 0.009941633650425134, 79: 0.010041674087637172, 80: 0.009941633650425134, 81: 0.009843202124104186, 82: 0.009876342665881136, 83: 0.009991591987843034, 84: 0.009942128699930086, 85: 0.00987642517413196, 86: 0.00997551676645951, 87: 0.009843202124104186, 88: 0.009876672698884436, 89: 0.00987609514112866, 90: 0.009893407986274562, 91: 0.00989258290376631, 92: 0.009966489056757847, 93: 0.009876672698884436, 94: 0.00987609514112866, 95: 0.009843202124104186, 96: 0.00994188117517761, 97: 0.009942293716431735, 98: 0.00999200452909716, 99: 0.009843202124104186, 100: 0.009868057530436899}
max(pr.values())

 输出结果:

0.010041880358264236
import operator
max(pr.items(),key=operator.itemgetter(1))[0]

输出结果:

17
sum(pr.values())

输出结果:

0.9999999999999996
min(pr.values())

输出结果:

0.009843202124104186

9-PageRank的优缺点

优点:

  • 通过网页之间的链接来决定网页重要性,一定程度消除了认为对排名结果的影响

  •  离线计算PageRank值,而非查找的时候计算,提升了查询的效率

缺点 :

  • 存在时间久的网站,PageRank值会越来越大,而新生的网站,PageRank值增长慢

  •  非查询相关的特性,查询结果会偏离搜索的内容
  • 通过“僵尸”网站或链接,人为刷PageRank值

参考:

1.Up主帅器学习/林木的视频。 

 

这篇关于Python数学建模学习-PageRank算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/906415

相关文章

使用Python实现矢量路径的压缩、解压与可视化

《使用Python实现矢量路径的压缩、解压与可视化》在图形设计和Web开发中,矢量路径数据的高效存储与传输至关重要,本文将通过一个Python示例,展示如何将复杂的矢量路径命令序列压缩为JSON格式,... 目录引言核心功能概述1. 路径命令解析2. 路径数据压缩3. 路径数据解压4. 可视化代码实现详解1

python获取网页表格的多种方法汇总

《python获取网页表格的多种方法汇总》我们在网页上看到很多的表格,如果要获取里面的数据或者转化成其他格式,就需要将表格获取下来并进行整理,在Python中,获取网页表格的方法有多种,下面就跟随小编... 目录1. 使用Pandas的read_html2. 使用BeautifulSoup和pandas3.

Python装饰器之类装饰器详解

《Python装饰器之类装饰器详解》本文将详细介绍Python中类装饰器的概念、使用方法以及应用场景,并通过一个综合详细的例子展示如何使用类装饰器,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录1. 引言2. 装饰器的基本概念2.1. 函数装饰器复习2.2 类装饰器的定义和使用3. 类装饰

Python 交互式可视化的利器Bokeh的使用

《Python交互式可视化的利器Bokeh的使用》Bokeh是一个专注于Web端交互式数据可视化的Python库,本文主要介绍了Python交互式可视化的利器Bokeh的使用,具有一定的参考价值,感... 目录1. Bokeh 简介1.1 为什么选择 Bokeh1.2 安装与环境配置2. Bokeh 基础2

Java学习手册之Filter和Listener使用方法

《Java学习手册之Filter和Listener使用方法》:本文主要介绍Java学习手册之Filter和Listener使用方法的相关资料,Filter是一种拦截器,可以在请求到达Servl... 目录一、Filter(过滤器)1. Filter 的工作原理2. Filter 的配置与使用二、Listen

如何使用 Python 读取 Excel 数据

《如何使用Python读取Excel数据》:本文主要介绍使用Python读取Excel数据的详细教程,通过pandas和openpyxl,你可以轻松读取Excel文件,并进行各种数据处理操... 目录使用 python 读取 Excel 数据的详细教程1. 安装必要的依赖2. 读取 Excel 文件3. 读

Python的time模块一些常用功能(各种与时间相关的函数)

《Python的time模块一些常用功能(各种与时间相关的函数)》Python的time模块提供了各种与时间相关的函数,包括获取当前时间、处理时间间隔、执行时间测量等,:本文主要介绍Python的... 目录1. 获取当前时间2. 时间格式化3. 延时执行4. 时间戳运算5. 计算代码执行时间6. 转换为指

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

Python ZIP文件操作技巧详解

《PythonZIP文件操作技巧详解》在数据处理和系统开发中,ZIP文件操作是开发者必须掌握的核心技能,Python标准库提供的zipfile模块以简洁的API和跨平台特性,成为处理ZIP文件的首选... 目录一、ZIP文件操作基础三板斧1.1 创建压缩包1.2 解压操作1.3 文件遍历与信息获取二、进阶技

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模