【补充】图神经网络前传——PageRank

2024-05-10 10:44

本文主要是介绍【补充】图神经网络前传——PageRank,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

对于任何一个网页,都可以给出网页的重要度,给每个网页重要度打分,高分的靠前。

改变世界的谷歌PageRank算法_哔哩哔哩_bilibili

(这个参考资料考虑之后去自己看看)

把互联网用图来表示,每一个网页就是一个节点,网页之间的引用(放一个超链接,比如)就是边。不过现在可能这样就不太方便了,因为现在的网页是可以随时生成的(比如支付成功页面),同时还有无法触达的部分(比如朋友圈、聊天记录),都不是爬虫可以爬到的。

PageRank把互联网当作一个整体,认为网页间存在关联。之前的搜索引擎都是对孤立的网页进行分析(个人感觉这里就是,之前的方法只考虑了节点的特征,而忽视了结构关系,而PageRank除了节点信息之外也有边\结构的信息)

之前的网络可以表示成树状\层状结构(导航链接)->可以表示成有向图

把整个互联网表示成一个有向图,有向图的节点是网页,网页之间的引用是连接。

除此之外,论文之间的引用、百科词条之间的引用也可以被表示成图结构。甚至一个节点也可以引用自己。

如果网页C中包含了网页A的链接,那么就有一条C指向A的边

现在,我们已经有了一张图,我们需要利用图的结构计算每个节点(网页)的重要度。并非所有网页都很重要。

对于图而言,我们还可以做很多事情⬆️

PageRank做的是利用连接信息定量计算节点的重要度。PPR和Random Walk with Restarts是用来计算节点相似度的问题的(可以用在推荐系统里,定量地衡量两个用户的相似程度)。

PageRank

idea:把links当作是投票

这里link有两类:我引用别人的,别人引用我的。当然应采用别人引用我的(否则我自己引特别多链接直接屠榜显然不合理)-> in-coming links

显然不同的引用的重要程度也不同,不然我也可以自己创一些莫名其妙的网页指向自己(又屠榜了嘿嘿)。

PageRank采用的就是来自重要网页的vote更值钱。那么怎么知道是不是重要网页捏?要计算A网页的PageRank,就要计算所有引用网页A的网页的PageRank,要计算所有引用网页A的网页的PageRank,就要计算所有引用所有引用网页A的网页的网页PageRank……套娃了属于是。

->一个递归问题

先看第一个角度,线性方程组 

假设我们要计算红色节点j的PageRank,那么我们就首先找找谁引用了j节点,i节点的、k节点引用了j节点(绿色),蓝色的节点是j节点引用的,这里就不用看了。

对于i节点,有三条out-link(引用了三个节点),因此分给j节点的只有\frac{r_i}{3},这里r_i表示的是i节点的PageRank,同理r_k表示的是k节点的PageRank。k节点有四个out-link,所以给j节点的就是\frac{r_k}{4}。因此,j节点此时r_j = \frac{r_i}{3} + \frac{r_k}{4}<-这时一次迭代。

这里假设了节点的所有out-link的权重是一样的(当然不是这样啦!)

理论上三个方程,三个未知数,完全可以求解了,但是实际上是一个方程两个未知数,因此需要补一个,需要补充一个方程,三个节点的PageRank求和=1:

r_a + r_y +r_m = 1

->联立方程组求解(高斯消元法)

现在,我们把网络扩大呢,这样解方程显然不经济实惠了。

看下面这个例子,A节点只有来自C节点的引用,而C节点有三个out-link->除以3

 B节点有两个节点指向,A和C,A只有两条out-link->除以2,C有三条->除以3

 最后可以得到下面的结果。

从图中可以看出C节点就是那个最重要的节点,而A节点就是最不重要的节点(这也符合直觉)。

下一个,左乘M矩阵

还是刚刚的例子:

解释一下左边的矩阵,第3列就是C节点,C节点连着A B D,对每个节点都雨露均沾,都是1/3。

这个矩阵称为stochastic adjacent matrix M,右边的向量就是rank vector r

下一个是特征向量:

有一些线性变换只改变长度不改变方向->特征向量

看这里:10 - 特征向量与特征值_哔哩哔哩_bilibili

现在我们回到上面的M矩阵:

那么其实r就是这个特征向量,而1就是特征值

下一个角度是随机游走:

可以认为在这个有向图中,有一个浏览者在顺着连接随机游走,如果一个网页访问的次数比较多->这个网页比较重要->归一化为概率

马尔可夫链:

此时,求解PageRank就是求解stationary distributions of Markov Chains

求解

不停地左乘M矩阵,直到下一时刻的PageRank和当前时刻没有太大变化。

 两种奇怪的网页(可能会为PageRank的计算带来困难):

像这样其实违反了我们的假设,即M的每一列求和都应该为0

->如何解决

防止在一个网页里来回绕,有一定概率传送出去

对于死胡同节点,百分百被传送走

Random walk with restarts and personalized PageRank

计算相似度

比如这里:相似的商品,相似的用户,这样比较好做推荐。

->寻找与指定节点最相似的节点

这里有一个基本假设是:被同一个用户访问过的节点,更有可能是相似的。

在这个例子里AA'商品就可能更相似,都被绿色用户买过,相比之下,从BB'就要从蓝色用户到紫色用户

这些交互方式,怎么定量衡量?

回顾PageRank方法

->随机传送->但是随机传送到目的不是任意节点了,而是指定的一个/一些节点

用随机游走的访问次数,来反映节点之间的亲疏远近

每次都以给定概率随机传送回Q节点

->可以用这些数字来反映这些商品与Q节点的相似度

好处:考虑了所有的情况

使用PageRank

import networkx as nx
# 创建有向图
G = nx.DiGraph() 
# 有向图之间边的关系
edges = [("A", "B"), ("A", "C"), ("A", "D"), ("B", "A"), ("B", "D"), ("C", "A"), ("D", "B"), ("D", "C")]
for edge in edges:G.add_edge(edge[0], edge[1])
pagerank_list = nx.pagerank(G, alpha=1)
print("pagerank值是:", pagerank_list)

pagerank值是: {'A': 0.333, 'B': 0.222, 'C': 0.222, 'D': 0.222}

⬆️来源:机器学习十大经典算法-PageRank(附实践代码) - 知乎

这里的alpha就是阻尼系数。

什么是阻尼系数?

P_n = dM\cdot P_{n-1} +(1-d)P_0

这里,P_n表示第n步计算得到的PageRank值,d表示阻尼系数,M表示转移矩阵,P_0是初始PageRank值(即:1/页面(节点)个数)

下面是迭代的方式:

import numpy as np
def  nodes2matrix(node_json):
"""
构建图的
"""node2id = {}dim = len(node_json)for id_ , key in enumerate(node_json.keys()):node2id[key] = id_   matrix = np.zeros((dim,dim))for key in node_json.keys():nodeid = node2id[key]for neighbor in node_json[key]:neighborid = node2id[neighbor]matrix[neighborid][nodeid] = 1for i in range(dim):matrix[:,i] = matrix[:,i]/sum(matrix[:,i])return matrixdef pagerank(matrix, iter_ = 10, d=0.85):length = len(matrix[0])inital_value = np.ones(length)/lengthpagerank_value = inital_valuefor i in range(10):pagerank_value = matrix@pagerank_value* d  +  (1-d)/lengthprint("iter {}: the pr value is {}".format(i, pagerank_value))return pagerank_value

⬆️来源:鼎鼎大名的PageRank算法——理论+实战 - 知乎

其他参考:

如何优雅的理解PageRank - 简书

PageRank算法详解 - 知乎

这篇关于【补充】图神经网络前传——PageRank的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

图神经网络模型介绍(1)

我们将图神经网络分为基于谱域的模型和基于空域的模型,并按照发展顺序详解每个类别中的重要模型。 1.1基于谱域的图神经网络         谱域上的图卷积在图学习迈向深度学习的发展历程中起到了关键的作用。本节主要介绍三个具有代表性的谱域图神经网络:谱图卷积网络、切比雪夫网络和图卷积网络。 (1)谱图卷积网络 卷积定理:函数卷积的傅里叶变换是函数傅里叶变换的乘积,即F{f*g}

【多系统萎缩患者必看】✨维生素补充全攻略,守护你的健康每一天!

亲爱的朋友们,今天我们要聊一个既重要又容易被忽视的话题——‌多系统萎缩患者如何科学补充维生素‌!🌟 在这个快节奏的生活中,健康成为了我们最宝贵的财富,而对于多系统萎缩(MSA)的患者来说,合理的营养补充更是维护身体机能、提升生活质量的关键一步。👇 🌈 为什么多系统萎缩患者需要特别关注维生素? 多系统萎缩是一种罕见且复杂的神经系统疾病,它影响身体的多个系统,包括自主神经、锥体外系、小脑及锥

机器学习之监督学习(三)神经网络

机器学习之监督学习(三)神经网络基础 0. 文章传送1. 深度学习 Deep Learning深度学习的关键特点深度学习VS传统机器学习 2. 生物神经网络 Biological Neural Network3. 神经网络模型基本结构模块一:TensorFlow搭建神经网络 4. 反向传播梯度下降 Back Propagation Gradient Descent模块二:激活函数 activ

Vue2电商项目(二) Home模块的开发;(还需要补充js节流和防抖的回顾链接)

文章目录 一、Home模块拆分1. 三级联动组件TypeNav2. 其余组件 二、发送请求的准备工作1. axios的二次封装2. 统一管理接口API----跨域3. nprogress进度条 三、 vuex模块开发四、TypeNav三级联动组件开发1. 动态展示三级联动数据2. 三级联动 动态背景(1)、方式一:CSS样式(2)、方式二:JS 3. 控制二三级数据隐藏与显示--绑定styl

图神经网络框架DGL实现Graph Attention Network (GAT)笔记

参考列表: [1]深入理解图注意力机制 [2]DGL官方学习教程一 ——基础操作&消息传递 [3]Cora数据集介绍+python读取 一、DGL实现GAT分类机器学习论文 程序摘自[1],该程序实现了利用图神经网络框架——DGL,实现图注意网络(GAT)。应用demo为对机器学习论文数据集——Cora,对论文所属类别进行分类。(下图摘自[3]) 1. 程序 Ubuntu:18.04

基于深度学习 卷积神经网络resnext50的中医舌苔分类系统

项目概述 本项目旨在通过深度学习技术,特别是利用卷积神经网络(Convolutional Neural Networks, CNNs)中的ResNeXt50架构,实现对中医舌象图像的自动分类。该系统不仅能够识别不同的舌苔类型,还能够在PyQt5框架下提供一个直观的图形用户界面(GUI),使得医生或患者能够方便地上传舌象照片并获取分析结果。 技术栈 深度学习框架:采用PyTorch或其他

图神经网络(2)预备知识

1. 图的基本概念         对于接触过数据结构和算法的读者来说,图并不是一个陌生的概念。一个图由一些顶点也称为节点和连接这些顶点的边组成。给定一个图G=(V,E),  其 中V={V1,V2,…,Vn}  是一个具有 n 个顶点的集合。 1.1邻接矩阵         我们用邻接矩阵A∈Rn×n表示顶点之间的连接关系。 如果顶点 vi和vj之间有连接,就表示(vi,vj)  组成了

自然语言处理系列六十三》神经网络算法》LSTM长短期记忆神经网络算法

注:此文章内容均节选自充电了么创始人,CEO兼CTO陈敬雷老师的新书《自然语言处理原理与实战》(人工智能科学与技术丛书)【陈敬雷编著】【清华大学出版社】 文章目录 自然语言处理系列六十三神经网络算法》LSTM长短期记忆神经网络算法Seq2Seq端到端神经网络算法 总结 自然语言处理系列六十三 神经网络算法》LSTM长短期记忆神经网络算法 长短期记忆网络(LSTM,Long S

神经网络训练不起来怎么办(零)| General Guidance

摘要:模型性能不理想时,如何判断 Model Bias, Optimization, Overfitting 等问题,并以此着手优化模型。在这个分析过程中,我们可以对Function Set,模型弹性有直观的理解。关键词:模型性能,Model Bias, Optimization, Overfitting。 零,领域背景 如果我们的模型表现较差,那么我们往往需要根据 Training l

如何将卷积神经网络(CNN)应用于医学图像分析:从分类到分割和检测的实用指南

引言 在现代医疗领域,医学图像已经成为疾病诊断和治疗规划的重要工具。医学图像的类型繁多,包括但不限于X射线、CT(计算机断层扫描)、MRI(磁共振成像)和超声图像。这些图像提供了对身体内部结构的详细视图,有助于医生在进行准确诊断和制定个性化治疗方案时获取关键的信息。 1. 医学图像分析的挑战 医学图像分析面临诸多挑战,其中包括: 图像数据的复杂性:医学图像通常具有高维度和复杂的结构