网站升级建设招标公告,珠海门户网站建设多少钱,深圳网站建设 百业,建筑论坛网维基百科#xff1a;在图论和网络分析中#xff0c;中心性指标为图中相应网络位置的节点分配排名或数值。中心性这一概念最初起源于社交网络分析#xff0c;因此很多衡量中心性的术语也反映了其社会学背景。 不同中心性指标对 “重要” 的衡量方式不同#xff0c;因此适用于… 维基百科在图论和网络分析中中心性指标为图中相应网络位置的节点分配排名或数值。中心性这一概念最初起源于社交网络分析因此很多衡量中心性的术语也反映了其社会学背景。 不同中心性指标对 “重要” 的衡量方式不同因此适用于不同的情形。katz 和 PageRank 都可以视为特征向量中心性的变体。
一、特征向量中心性eigenvector centrality 特征向量这一概念最早应该是在 线性代数 这门课程中接触到的而取名中的特征向量也与它最初的概念相关我们先回顾下什么是 “特征值” 和 “特征向量”。
1.1 线性代数中的特征向量 定义设 A 是 n 阶方阵若存在向量使得 则称 x 为 A 的特征向量 为 A 的特征值严格定义请参考权威文献。 由定义可见特征向量的本质是它与原矩阵相乘后得到的矩阵与特征向量方向相同仅存在缩放关系即 倍的缩放该缩放比例称为特征值。进一步延伸原矩阵无论乘上多少特征向量其方向都是确定的。回顾一道求特征值和特征向量的简单例题可以更好回忆相关概念求 的特征向量和特征值。 解得两个特征值 2 或 4则应有 解得 因此可取特征值 2 的特征向量为
.
求特征值 4 的特征向量同理。 1.2 图论中的特征向量中心性
定义图 G (V, E)定义其邻接矩阵 A 表示节点 v 和 t 不相连 表示节点 v 和 t 相连则节点 v 的中心性 x 的分数计算式为 .
单纯看公式会觉得不好理解结合具体的例子可以马上掌握它在本质上是求图 G 邻接矩阵的特征向量只不过在算法设计中通常不是通过数学方式求得而是采用迭代逼近的方式得到一个近似解。特征向量中心性的核心思想是一个结点的邻居越重要该结点就越重要。下面是一个经典的分析图 各节点上的数字表示该结点的权重以 5 作为节点 1按顺时针标记各节点且中心节点记为节点 5则得到邻接矩阵为 第一轮迭代邻接矩阵乘上各结点的分数 迭代完成后各结点分数发生变化效果为节点“吸收”了邻接节点的分数邻接节点分数高的迭代后分数就高。且经过多轮迭代后各节点间的相对分数将不再发生变化即收敛仅存在绝对分数的缩放此时我们就得到了最终的中心性分数矩阵而该矩阵是邻接矩阵的特征向量。 二、katz 中心性 针对特征向量中心性无法用于有向图的不足提出了 katz 中心性。
2.1 理解特征向量中心性的不足
每篇博客都说了特征向量中心性不能用于有向图但是为什么呢这个结论怎么来的
此处稍微探究下我的理解不一定是对的但特征向量中心性确实存在一些问题。首先观察上一节中邻接矩阵的特点它是沿着主对角线对称的矩阵。这是可以理解的无向图的连通性肯定是对称的。而特征向量中心性算法的本质是求邻接矩阵的特征向量当邻接矩阵的性质发生变化时特征向量必然会受影响。
在有向图中没有沿主对角线对称这一性质那么对于只有出度、没有入度的节点就存在一个致命问题它的分数一直被出度节点吸收而它自身分数将归零以下图为例。这显然是不合理的这也是我理解的特征向量中心性计算方式不足的原因。 2.2 katz 中心性的改进思路
首先看看它的中心性计算公式
.
或不考虑 k
.
比较和特征向量中心性的不同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 中心性可以发现它只是对每个节点的分数除以 即该节点的出度。这样调整的出发点是katz 中心性中某个高分节点会较大地影响所有与其相邻的节点结合社交网络的背景比如名人的朋友并不都是名人。用出度稀释高分节点的分数可以避免部分节点拥有很强的影响力。
