【图论】三种中心性 —— 特征向量、katz 和 PageRank

这篇具有很好参考价值的文章主要介绍了【图论】三种中心性 —— 特征向量、katz 和 PageRank。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

维基百科:在图论和网络分析中,中心性指标为图中相应网络位置的节点分配排名或数值。中心性这一概念最初起源于社交网络分析,因此很多衡量中心性的术语也反映了其社会学背景。

不同中心性指标对 “重要” 的衡量方式不同,因此适用于不同的情形。katz 和 PageRank 都可以视为特征向量中心性的变体。

一、特征向量中心性(eigenvector centrality) 

特征向量这一概念最早应该是在 线性代数 这门课程中接触到的,而取名中的特征向量也与它最初的概念相关,我们先回顾下什么是 “特征值” 和 “特征向量”。

1.1 线性代数中的特征向量

定义:设 A 是 n 阶方阵,若存在向量使得  ,则称 x 为 A 的特征向量, 为 A 的特征值(严格定义请参考权威文献)。

由定义可见,特征向量的本质是它与原矩阵相乘后,得到的矩阵与特征向量方向相同,仅存在缩放关系(即  倍的缩放),该缩放比例称为特征值。进一步延伸,原矩阵无论乘上多少特征向量,其方向都是确定的。回顾一道求特征值和特征向量的简单例题,可以更好回忆相关概念,求  的特征向量和特征值。


 

解得两个特征值 2 或 4,则应有

解得 【图论】三种中心性 —— 特征向量、katz 和 PageRank,图论,图论 ,因此可取特征值 2 的特征向量为

.

求特征值 4 的特征向量同理。


1.2 图论中的特征向量中心性

定义:图 G = (V, E),定义其邻接矩阵 A, 表示节点 v 和 t 不相连, 表示节点 v 和 t 相连,则节点 v 的中心性 x 的分数计算式为

  .

单纯看公式会觉得不好理解,结合具体的例子可以马上掌握,它在本质上是求图 G 邻接矩阵的特征向量,只不过在算法设计中,通常不是通过数学方式求得,而是采用迭代逼近的方式得到一个近似解。特征向量中心性的核心思想是,一个结点的邻居越重要,该结点就越重要。下面是一个经典的分析图,

【图论】三种中心性 —— 特征向量、katz 和 PageRank,图论,图论

 各节点上的数字表示该结点的权重,以 5 作为节点 1,按顺时针标记各节点,且中心节点记为节点 5,则得到邻接矩阵为

第一轮迭代,邻接矩阵乘上各结点的分数

迭代完成后,各结点分数发生变化,效果为节点“吸收”了邻接节点的分数,邻接节点分数高的,迭代后分数就高。且经过多轮迭代后,各节点间的相对分数将不再发生变化,即收敛,仅存在绝对分数的缩放,此时我们就得到了最终的中心性分数矩阵,而该矩阵是邻接矩阵的特征向量。

【图论】三种中心性 —— 特征向量、katz 和 PageRank,图论,图论

二、katz 中心性

针对特征向量中心性无法用于有向图的不足,提出了 katz 中心性。

2.1 理解特征向量中心性的不足

每篇博客都说了,特征向量中心性不能用于有向图,但是为什么呢,这个结论怎么来的?

此处稍微探究下,我的理解不一定是对的,但特征向量中心性确实存在一些问题。首先观察上一节中邻接矩阵的特点,它是沿着主对角线对称的矩阵。这是可以理解的,无向图的连通性肯定是对称的。而特征向量中心性算法的本质是求邻接矩阵的特征向量,当邻接矩阵的性质发生变化时,特征向量必然会受影响。

在有向图中没有沿主对角线对称这一性质,那么对于只有出度、没有入度的节点,就存在一个致命问题,它的分数一直被出度节点吸收,而它自身分数将归零(以下图为例)。这显然是不合理的,这也是我理解的特征向量中心性计算方式不足的原因。

【图论】三种中心性 —— 特征向量、katz 和 PageRank,图论,图论

 2.2 katz 中心性的改进思路

首先看看它的中心性计算公式,

【图论】三种中心性 —— 特征向量、katz 和 PageRank,图论,图论.

或不考虑 k,

【图论】三种中心性 —— 特征向量、katz 和 PageRank,图论,图论.

比较和特征向量中心性的不同,katz 引入了两个新的变量,分别是衰减因子  和基本偏移量  。第一个求和号中的 k 表示 k-hop,即只考虑与节点 v 距离在 k 以内(通常以一个节点作为一个单位距离)的节点分数,该思路在特征向量中心性中也是可行的,只是在上一节中未列出来。k 取 1 时就表示只考虑直接相连的节点。

  • 衰减因子  随着 k 增大呈指数级减小,其设计思路是距离越近的节点对分数的影响应更大,反之应有衰减;
  • 偏移量  是为了避免出现 2.1 中讨论的分数归零现象;
  •  可能较难理解,其实就是在 k 距离内的邻接矩阵,如 k = 1 就是与节点 v 直接相连的邻接矩阵,k = 2 就是与节点 v 隔一个节点相连的邻接矩阵。

通过例子理解先跳过,可以自己搜索具体的计算例子。

三、PageRank 中心性(PageRank centrality)

PageRank 应该是这三者中最出名的,主要用于谷歌的网页排序。

3.1 PageRank 中心性思想

一样先看 PageRank 的计算公式,

【图论】三种中心性 —— 特征向量、katz 和 PageRank,图论,图论.

相比于 katz 中心性,可以发现它只是对每个节点的分数除以 ,即该节点的出度。这样调整的出发点是,katz 中心性中某个高分节点会较大地影响所有与其相邻的节点,结合社交网络的背景,比如名人的朋友并不都是名人。用出度稀释高分节点的分数可以避免部分节点拥有很强的影响力。文章来源地址https://www.toymoban.com/news/detail-615047.html

到了这里,关于【图论】三种中心性 —— 特征向量、katz 和 PageRank的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 特征值和特征向量的通俗解释

    我们知道,特征向量的公式是                 ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​         其中A代表矩阵,x代表特征向量,代表特征值。 众所

    2024年02月15日
    浏览(31)
  • 线性代数——特征值和特征向量

    学习高等数学和线性代数需要的初等数学知识 线性代数——行列式 线性代数——矩阵 线性代数——向量 线性代数——线性方程组 线性代数——特征值和特征向量 线性代数——二次型 本文大部分内容皆来自李永乐老师考研教材和视频课。 设 A = [ a i j ] A=[a_{ij}] A = [ a ij ​

    2024年02月15日
    浏览(44)
  • 向量与矩阵 导数和偏导数 特征值与特征向量 概率分布 期望方差 相关系数

    标量(scalar) :一个单独的数。 向量(vector) :⼀组有序排列的数。通过次序中的索引,我们可以确定每个单独的数。 矩阵(matrix) :具有相同特征和纬度的对象的集合。⼀个对象表⽰为矩阵中的⼀⾏,⼀个特征表⽰为矩阵中的⼀列,表现为⼀张⼆维数据表。 张量(ten

    2024年02月03日
    浏览(46)
  • 线性代数 --- 特征值与特征向量(下)

    Eigen Values Eigen Vectors Part III:如何求解特征向量与特征值 对于一般矩阵A,如何找到他的特征值与特征向量? Step I: Find λ first! 首先,我们有方程: 但这里有两个未知数,因此我们把上面的方程改写一下:         这个齐次方程的解就是矩阵(A-I)的零空间,抛开平凡解全0向

    2024年03月14日
    浏览(48)
  • LA@特征值和特征向量的性质

    特征值之和 ∑ i = 1 n λ i = ∑ i = 1 n a i i sumlimits_{i=1}^{n}lambda_i=sumlimits_{i=1}^{n}a_{ii} i = 1 ∑ n ​ λ i ​ = i = 1 ∑ n ​ a ii ​ 其中 ∑ i = 1 n a i i sum_{i=1}^{n}a_{ii} ∑ i = 1 n ​ a ii ​ 称为矩阵的迹,记为 T r ( A ) Tr(bold A) T r ( A ) 特征值之积 ∏ i = 1 n λ i = ∣ A ∣ prod_{i=1}^{n}lambda

    2024年02月10日
    浏览(40)
  • MATLAB矩阵的特征值与特征向量

    设A是n阶方阵,如果存在常数λ和n维非零列向量x,使得等式Ax = λx 成立,则称λ为A的特征值,x是对应特征值λ的特征向量。 在MATLAB中,计算矩阵的特征值与特征向量的函数是eig,常用的调用格式有两种: E = eig(A):求矩阵A的全部特征向量值,构成向量E。 [X,D] = eig(A):

    2024年02月11日
    浏览(41)
  • 线性代数基础 | 特征值和特征向量

    一、特征值和特征向量的定义 A. 特征值的定义和性质 特征值(eigenvalue)是线性代数中一个重要的概念,用于描述线性变换对于某个向量的伸缩效应。在本文中,我们将深入讨论特征值的定义和性质。 首先,我们考虑一个线性变换(或者说一个方阵)A。对于一个非零向量v,

    2024年02月16日
    浏览(42)
  • 5.1 矩阵的特征值和特征向量

    学习特征值和特征向量的定义和性质,我会采取以下方法: 1. 学习线性代数基础知识:特征值和特征向量是线性代数中的重要概念,需要先掌握线性代数的基础知识,例如向量、矩阵、行列式、逆矩阵、转置、内积、外积等基本概念。 2. 学习特征值和特征向量的定义:特征

    2024年02月02日
    浏览(49)
  • 线性代数 第五章 特征值与特征向量

    一、特征值定义 二、特征值求法 定义法; ; 相似。 三、特征向量求法 定义法; 基础解系法; ; 相似。 四、特征值性质 不同特征值的特征向量线性无关 k重特征值至多有k个线性无关的特征向量 五、相似的定义 若,则A和B相似。 六、相似的性质(必要条件) 七、可对角

    2024年02月06日
    浏览(50)
  • 线性代数——特征值与特征向量的性质

    (1)设A为方阵,则A与 A T A^{T} A T 有相同的特征值。 此处用到了两个关键性质,一:单位阵的转置为其本身,二:转置并不改变行列式的值。 (2): 设n阶方阵A=( a i j a_{ij} a ij ​ )的n个特征值为 λ 1 lambda_{1} λ 1 ​ , λ 2 lambda_{2} λ 2 ​ ,… λ n lambda_{n} λ n ​ ,则 λ 1 + λ

    2024年02月04日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包