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 FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整

Python Websockets库的使用指南

《PythonWebsockets库的使用指南》pythonwebsockets库是一个用于创建WebSocket服务器和客户端的Python库,它提供了一种简单的方式来实现实时通信,支持异步和同步... 目录一、WebSocket 简介二、python 的 websockets 库安装三、完整代码示例1.

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

Python使用自带的base64库进行base64编码和解码

《Python使用自带的base64库进行base64编码和解码》在Python中,处理数据的编码和解码是数据传输和存储中非常普遍的需求,其中,Base64是一种常用的编码方案,本文我将详细介绍如何使... 目录引言使用python的base64库进行编码和解码编码函数解码函数Base64编码的应用场景注意

Python基于wxPython和FFmpeg开发一个视频标签工具

《Python基于wxPython和FFmpeg开发一个视频标签工具》在当今数字媒体时代,视频内容的管理和标记变得越来越重要,无论是研究人员需要对实验视频进行时间点标记,还是个人用户希望对家庭视频进行... 目录引言1. 应用概述2. 技术栈分析2.1 核心库和模块2.2 wxpython作为GUI选择的优

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

Python+PyQt5实现多屏幕协同播放功能

《Python+PyQt5实现多屏幕协同播放功能》在现代会议展示、数字广告、展览展示等场景中,多屏幕协同播放已成为刚需,下面我们就来看看如何利用Python和PyQt5开发一套功能强大的跨屏播控系统吧... 目录一、项目概述:突破传统播放限制二、核心技术解析2.1 多屏管理机制2.2 播放引擎设计2.3 专

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很