当前位置： 首页 > news >正文

[学习笔记]PageRank算法

news 2025/9/15 19:02:24

参考资料：改变世界的谷歌PageRank算法

pagerank算法用于计算节点重要度

思想

如果网页被更多的入度(被引用)，则网页更重要。
被重要网站引用比被普通网站引用更加凸显重要性。
所以考虑一个网站是否重要，需要看引用它的网站是否重要，这就成了一个递归的问题。

理解pagerank的五个角度

迭代求解线性方程组

在这里插入图片描述

例子

在这里插入图片描述

这里看上去有三个方程，三个未知数，其实只有2个方程。
虽然高斯消元可以求解，但是可扩展性较差。
节点j的rank值 r j r_j rj​是考虑所有到 j j j的节点的rank值，各自除以它的出度，再求和。

迭代求解

在这里插入图片描述

迭代左乘M矩阵

迭代的过程用矩阵表示：(左边的矩阵的i行j列 A i j 有非零值 A_{ij}有非零值 Aij​有非零值表示存在第j个节点到第i个节点的有向边)
在这里插入图片描述

左边的矩阵称为列概率矩阵(列转移矩阵/列替代矩阵，column stochastic matrix)
右边的向量叫pagerank向量
在这里插入图片描述

矩阵的特征向量

迭代公式：
r = M ⋅ r r=M \cdot r r=M⋅r其实可以看作是
1 ⋅ r = M ⋅ r 1 \cdot r=M \cdot r 1⋅r=M⋅r
从这个角度看，pagerank向量就是M矩阵的特征值为1的特征向量。
在这里插入图片描述

对于Column Stochastic矩阵，由Perreon-Frobenius定理，最大的特征值就是1，且存在唯一的主特征向量(特征值1对应的特征向量)，向量所有元素求和为1。
通过幂迭代的方式，可以快速求解pagerank向量。

随机游走

随机游走->计数求和->归一化为概率，得到的就是pagerank向量。
在这里插入图片描述
在这里插入图片描述

马尔科夫链

在这里插入图片描述
在这里插入图片描述

求解pagerank

在这里插入图片描述
在这里插入图片描述

收敛性分析

在这里插入图片描述

1. 是否收敛-收敛，收敛到同一个结果

Ergodic Theorem

根据Ergodic Theorem，对于不可约(irreducible)和非周期(aperiodic)的马尔可夫链：
1.存在一个唯一的稳定的马尔科夫分布
2.并且所有初始分布收敛到同一个分布

可约(reducible)马尔可夫链和不可约马尔可夫链

可约是存在孤立的状态
不可约是所有状态都可达
在这里插入图片描述

周期马尔可夫链和非周期马尔可夫链

在这里插入图片描述

2.结果是不是代表重要度-两类问题

Spider trap问题

所有的出度边都在group里面，导致这个group吸收了所有的重要度
在这里插入图片描述

dead end问题

没有出度，重要度最终为0
在这里插入图片描述
对于这两种情况，即使收敛了，也不是合理的网络重要度。

例子

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

解决办法

spider trap问题的解决办法

在这里插入图片描述

dead end的解决办法

在这里插入图片描述

最终解决办法

在这里插入图片描述
在这里插入图片描述

pagerank的升级-mapreduce的工作

在这里插入图片描述

pagerank算法用于计算节点相似度-用于推荐系统

给定：一个bipartite graph用于表示用户和商品的交互
目标：寻找与指定节点最相似的节点
假设：被同一个用户访问过的节点，更可能是相似的

pagerank，随机游走视角的启发

pagerank的一种解释是：随机游走，并有概率随机传送到网络中的任意一个节点，继续游走
Topic-Specific PageRank(也称为personalized pagerank)：随机游走，并有传送到指定的一些节点，继续游走
random walks with restarts：随机游走，并有传送到指定的一个节点，继续游走

随机游走访问次数-相似性的度量

给定一个节点集query_nodes，模拟一个随机游走：

  • 记录访问次数
  • 在概率 α \alpha α下，在query_nodes中重启walk
  • 有高访问次数的节点则和query_nodes中的点有更高的相似性

伪代码

在这里插入图片描述

优点

在这里插入图片描述

代码实战

参考资料：https://www.bilibili.com/video/BV1Wg411H7Ep/?p=16&spm_id_from=pageDriver

相关文章：

[学习笔记]PageRank算法

参考资料：改变世界的谷歌PageRank算法 pagerank算法用于计算节点重要度 思想 如果网页被更多的入度(被引用)，则网页更重要。 被重要网站引用比被普通网站引用更加凸显重要性。 所以考虑一个网站是否重要，需要看引用它的网站是否重要&#…...

编程日记 2023/9/12 8:31:05

【洛谷算法题】P5704-字母转换【入门1顺序结构】

👨‍💻博客主页：花无缺 欢迎 点赞👍 收藏⭐ 留言📝 加关注✅! 本文由 花无缺 原创 收录于专栏 【洛谷算法题】 文章目录 【洛谷算法题】P5704-字母转换【入门1顺序结构】🌏题目描述🌏输入格式&a…...

编程日记 2023/9/12 8:30:04

Pytorch——查找、替换module相关操作

nn.Module类可用操作 1. model.named_parameters() # 遍历模型的所有参数并打印它们的名称和形状 for name, param in model.named_parameters():print(f"Parameter Name: {name}, Parameter Shape: {param.shape}")输出示例： Parameter Name: conv1.w…...

编程日记 2023/9/12 8:29:03

组件安全以及漏洞复现

组件安全 1. 概述 A9:2017-使⽤含有已知漏洞的组件 A06:2021-Vulnerable and Outdated Components ​ 组件（例如：库、框架和其他软件模块）拥有和应用程序相同的权限。如果应用程序中含有已知漏洞的组件被攻击者利用，可能会造成…...

编程日记 2023/9/12 8:28:02

人工智能安全-4-小样本问题

0 提纲 小样本学习问题数据增强基于模型的小样本学习基于算法的小样本学习相关资源1 小样本学习问题 在小样本监督分类中，通常将问题表述为 N-way-K-shot分类， 当K = 1，称为one-shot learning；当K = 0时，成为zero-shot learning（ZSL）。ZSL就要求学习的问题具备充足的先…...

编程日记 2023/9/12 8:27:01

iOS 17中的Safari配置文件改变了游戏规则，那么如何设置呢

Safari在iOS 17中最大的升级是浏览配置文件——能够在一个应用程序中创建单独的选项卡和书签组。这些也可以跟随你的iPad和Mac，但在本指南中，我们将向你展示如何使用运行iOS 17的iPhone。 你可能有点困惑，为什么Safari中没有明显的位置可以添…...

编程日记 2023/9/12 8:26:01

AC自动机小结

AC自动机是一种多模匹配算法。 常见操作 查询一个串的子串 任何一个串的子串都可以表示成他的一个前缀的后缀 他的前缀可以在Trie树上查询 后缀相当于其在fail树上的所有祖先 例1 ： HDU4117 接上。首先AC自动机要学会离线。 对于每个点查询祖先复杂度很大。…...

编程日记 2023/9/12 8:25:00

【C++】构造函数分类 ③ ( 调用有参构造函数的方法 | 括号法 | 等号法 )

文章目录 一、在不同的内存中创建类的实例对象1、括号法调用构造函数2、等号法调用构造函数 二、完整代码示例 一、在不同的内存中创建类的实例对象 在上一篇博客 【C】构造函数分类 ② ( 在不同的内存中创建类的实例对象 | 栈内存中创建实例对象 | new 关键字创建对象 ) 中 , …...

编程日记 2023/9/12 8:23:59

uni-app 之 uni.request 网络请求API接口

uni-app 之 uni.request 网络请求API接口 image.png <template><!-- vue2的<template>里必须要有一个盒子&#xff0c;不能有两个&#xff0c;这里的盒子就是 view--><view>--- uni.request 网络请求API接口 ---<view><!-- 免费的测试接口 --…...

编程日记 2023/9/12 8:22:56

代码随想录33|509. 斐波那契数，70. 爬楼梯，746. 使用最小花费爬楼梯， 34. 在排序数组中查找元素的第一个和最后一个位置

509. 斐波那契数 链接地址 class Solution { public:int fib(int n) {if (n < 1) return n;vector<int> dp(n 1);dp[0] 0;dp[1] 1;for (int i 2; i < n 1; i) {dp[i] dp[i - 1] dp[i - 2];}return dp[n];} };70. 爬楼梯 链接地址 class Solution { public…...

编程日记 2023/9/12 8:21:55

什么是Executors框架？

Executors 是 Java 标准库中的一个工具类，位于 java.util.concurrent 包中，用于创建和管理线程池。它提供了一组静态工厂方法，用于快速创建不同类型的线程池。Executors 框架的目标是使线程池的创建和管理更加简单和方便。 以下是一些 Executors 框架的常用工厂方法和线程池…...

编程日记 2023/9/12 8:20:54

【kafka】kafka单节点/集群搭建

概述 本章节将分享不同版本的kafka单节点模式和集群模式搭建。 在kafka2.8版本之前&#xff0c;需要依赖zookeeper服务&#xff0c;而在kafka2.8版本&#xff08;包括&#xff09;之后&#xff0c;可以不在依赖zookeeper服务。本章节将分kafka2.8版本之前的版本和之后的版本分…...

编程日记 2023/9/12 8:19:53

如何进行机器学习

进行机器学习主要包含以下步骤&#xff1a; 获取数据&#xff1a;首先需要获取用于学习的数据&#xff0c;数据的质量和数量都会影响机器学习的效果。如果自己的数据量较少&#xff0c;可以尝试在网上寻找公开数据集进行训练&#xff0c;然后使用自己的数据进行微调。另一种方…...

编程日记 2023/9/12 8:18:52

Vue项目使用axios配置请求拦截和响应拦截以及判断请求超时处理提示

哈喽大家好啊&#xff0c;最近做Vue项目看到axios axios官网&#xff1a;起步 | Axios 中文文档 | Axios 中文网 (axios-http.cn)​​​​​​ 重要点&#xff1a; axios是基于Promise封装的 axios能拦截请求和响应 axios能自动转换成json数据 等等 安装&#xff1a; $ npm i…...

编程日记 2023/9/12 8:17:51

《DevOps实践指南》- 读书笔记（四）

DevOps实践指南 Part 3 第一步 &#xff1a;流动的技术实践11. 应用和实践持续集成11.1 小批量开发与大批量合并11.2 应用基于主干的开发实践11.3 小结 12. 自动化和低风险发布12.1 自动化部署流程12.1.1 应用自动化的自助式部署12.1.2 在部署流水线中集成代码部署 12.2 将部署…...

编程日记 2023/9/12 8:16:51

盲打键盘的正确指法指南

简介 很多打字初学者&#xff0c;并不了解打字的正确指法规范&#xff0c;很容易出现只用两根手指交替按压键盘的“二指禅”情况。虽然这样也能实现打字&#xff0c;但是效率极低。本文将简单介绍盲打键盘的正确指法&#xff0c;以便大家在后续的学习和工作中能够提高工作效率…...

编程日记 2023/9/12 8:15:49

【MySQL】索引 详解

索引 详解 一. 概念二. 作用三. 使用场景四. 操作五. 索引背后的数据结构B-树B树聚簇索引与非聚簇索引 一. 概念 索引是一种特殊的文件&#xff0c;包含着对数据表里所有记录的引用指针。可以对表中的一列或多列创建索引&#xff0c;并指定索引的类型&#xff0c;各类索引有各…...

编程日记 2023/9/12 8:14:47

怎么通过ip地址连接共享打印机

在现代办公环境中&#xff0c;共享打印机已成为一种常见的需求。通过共享打印机&#xff0c;多个用户可以在网络上共享同一台打印机&#xff0c;从而提高工作效率并减少设备成本。下面虎观代理小二二将介绍如何通过IP地址连接共享打印机。 确定打印机的IP地址 首先&#xff0…...

编程日记 2023/9/12 8:13:46

迅为i.MX8mm小尺寸商业级/工业级核心板

尺寸&#xff1a; 50mm*50mm CPU&#xff1a; NXP i.MX8M Mini 主频&#xff1a; 1.8GHz 架构&#xff1a; 四核Cortex-A53&#xff0c;单核Cortex-M4 PMIC&#xff1a; PCA9450A电源管理PCA9450A电源管理NXP全新研制配&#xff0c;iMX8M的电源管理芯片有六个降压稳压器、五…...

编程日记 2023/9/12 8:12:45

vue中v-for循环数组使用方法中splice删除数组元素（错误：每次都删掉点击的下面的一项）

总结&#xff1a;平常使用v-for的key都是使用index&#xff0c;这里vue官方文档也不推荐&#xff0c;这个时候就出问题了&#xff0c;我们需要key为唯一标识&#xff0c;这里我使用了时间戳&#xff08;new Date().getTime()&#xff09;处理比较复杂的情况&#xff0c; 本文章…...

编程日记 2023/9/12 8:11:44

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

编程新知 2025/9/14 1:39:42

云计算——弹性云计算器（ECS）

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

编程新知 2025/8/16 21:50:27

Redis相关知识总结（缓存雪崩，缓存穿透，缓存击穿，Redis实现分布式锁，如何保持数据库和缓存一致）

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

编程新知 2025/9/13 17:44:49

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

编程新知 2025/8/8 2:13:29

企业如何增强终端安全？

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

编程新知 2025/9/9 10:11:26

C++.OpenGL （20/64）混合（Blending）

混合（Blending） 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

编程新知 2025/7/6 20:05:42

Python Einops库：深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...

编程新知 2025/6/16 17:16:14

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

编程新知 2025/9/4 2:39:06

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...

编程新知 2025/8/9 9:56:56

微服务通信安全：深入解析mTLS的原理与实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言&#xff1a;微服务时代的通信安全挑战 随着云原生和微服务架构的普及&#xff0c;服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...

编程新知 2025/7/6 17:40:31