结点排序综述

文章连接：https://wenku.baidu.com/view/ef321959ad51f01dc281f1d0.html

1 基于节点近邻的排序方法

① 度中心性

  • 归一化度中心性指标

D C ( i ) = k i n − 1 DC(i)=\frac{^{k_{i}}}{n-1} DC(i)=n−1ki​​
其中
k i = ∑ i a i j {k_{i}}=\sum_{i}{a_{ij}} ki​=i∑​aij​

  • 刻画节点的直接影响力，认为一个节点的度越大能直接影响的邻居就越多，也就越重要
  • 有向网络中会一般分别计算入度和出度的中心性

② 半局部中心性

  • 定义N(w)为节点的两层邻居度，值等于从该节点出发2步内可达的邻居的数目

  • 定义
    Q ( j ) = ∑ w ∈ Γ ( j ) N ( w ) Q(j)=\sum_{w\in \Gamma (j)}N(w) Q(j)=w∈Γ(j)∑​N(w)

    • 其中T(j)是该节点的一阶邻居节点的集合

  • 局部中心性定义：
    S L C ( i ) = ∑ w ∈ Γ ( i ) Q ( w ) SLC(i)=\sum_{w\in \Gamma (i)}Q(w) SLC(i)=w∈Γ(i)∑​Q(w)

    • 计算复杂度随网络规模线性增长

  • 针对有向网络的半局部算法(ClusterRank)

    • 算法优于PageRank和LeaderRank算法

③ K-shell

  • 节点处于网络的核心位置，即使度较小，对网络也有高影响力。K-shell将外层节点层层剥去，确定内层有高影响力的节点。可以看成是一种基于节点度的粗粒化排序方法。

  • 思想

    • step1 从外层找度为1的节点，然后把与之相邻的边去掉，图中会产生新的度为1的节点，重复去除步骤，直到没有度为1的节点。Ks=1

  • step2 从上述步骤得到的图中去除度为2的节点，直到没有为止，Ks=2。增加去除度的值，直到图中没有节点为止。

  • 局限性

    • 树形图、规则网络和BA网络中不适用；k-shell排序结果太粗粒化，使得节点的区分度不大；仅考虑剩余度的影响，默认同层节点的外层节点数相同，不合理
    • 局限性改进：考虑节点剩余邻居数和节点已经移除的邻居数，增加区分度。还有提出区分具有相同壳数的节点的传播能力的排序算法

2 基于路径的排序方法

① 离心中心性

  • 定义

    • 一个节点v的离中心性为它与网络中所有节点的距离之中的最大值
      E C C ( i ) = m a x j ( d j i ) ECC(i)=max_{j}({d_{ji}}) ECC(i)=maxj​(dji​)

  • 网络直径/半径

    • 直径：所有节点的离心中心性的最大值；半径：离心中心性的最小值
    • 网络中心点是离心中心性等于半径的节点，一个节点的离心中心性与半径越接近说明越接近中心

② 接近中心性

  • 计算节点与网络中其他所有节点的距离的平均值来消除特殊值的干扰。节点与网络中其他节点的平均距离越小，该节点的接近中心性就越大。
    E F F ( i ) = ∑ j = 1 n 1 d i j EFF(i)=\sum_{j=1}^{n}\frac{1}{d_{ij}} EFF(i)=j=1∑n​dij​1​

    • 两个节点之间没有路径则定义d为无穷，1/d=0
    • d越小说明两个节点越接近

③ Katz中心性

  • 思想

    • 考虑节点对之间的最短路径和他们之间的其他非最短路径
    • 认为短路径比长路径更加重要，它通过一个与路径长度相关的因子对不同长度的路径加权。

  • 定义
    K a t z ( j ) = ∑ j = 1 k i j Katz(j)=\sum_{j=1}^{}{k_{ij}} Katz(j)=j=1∑​kij​

    • K是网络中任意节点对之间的路径关系的矩阵

K = s A + s 2 A 2 + . . . + s p A p + . . . = ( I − s A ) − 1 − I K=sA+s^{^{2}}A^{2}+...+s^{p}A^{p}+...=(I-sA)^{-1}-I K=sA+s2A2+...+spAp+...=(I−sA)−1−I
- I是单位矩阵，K中第i行j列对镜元素是两个节点的Katz相似性

	- 考虑所有路径数，对越短的路径赋予越大的权重

  • 适用性

    • 适合在规模不大，环路比较少的网络中
    • 缺点：时间复杂度高，有很多重复计算

④ 信息指标

  • 思想

    • 通过路径中传播的信息量来衡量节点的重要性
    • 一条路径上的信息传输量等于该路径长度的倒数
    • 节点间能够传输的信息总量等于它们之间所有的路径传输信息量和qij

  • 定义
    I N F ( i ) = [ 1 n ∑ j 1 q i j ] − 1 INF(i)=[\frac{1}{n}\sum_{j}^{}\frac{1}{q_{ij}}]^{-1} INF(i)=[n1​j∑​qij​1​]−1

      - 调和平均数定义中心性指标
    • 计算
      R = ( r i j ) = ( D − A + F ) − 1 R=(r_{ij})=(D-A+F)^{-1} R=(rij​)=(D−A+F)−1
      • 获得qij
      • D是n阶对角矩阵
      • F是每个元素均为1的n阶方阵

q i j = ( r i i + r j j − r i j ) − 1 q_{ij}=(r_{ii}+r_{jj}-r_{ij})^{-1} qij​=(rii​+rjj​−rij​)−1

⑤ 介数中心性

  • 思想

    • 网络中所有节点对的最短路径中，经过一个节点的最短路径数越多，这个节点就越重要
    • 刻画节点对网络中沿最短路径传输的网络流的控制力

  • 介数定义
    B C ′ ( i ) = 2 ( n − 1 ) ( n − 2 ) ∑ g s t i g s t BC'(i)=\frac{2}{(n-1)(n-2)}\sum \frac{g_{st}^{i}}{g_{st}} BC′(i)=(n−1)(n−2)2​∑gst​gsti​​

    • g是节点Vs到Vt的最短路径，上标i最短路径经过Vi的数目，当一个节点不在任何一条最短路径上时，该节点介数中心性为0

  • 应用

    • 有些情况下节点的度中心性和接近中心性都相等，这时可以使用介数中心性及逆行区分节点的重要性
    • 可以用来设计网络的通信协议、优化网络部署、检测网络瓶颈

  • 其他

    • 缺点：只考虑最短路径时间复杂度较高
    • 相似：负载中心性，节点的负载越大，节点越重要（Goh等人提出，网络中信息包传递机制）

⑥ 流介数中心性

  • 介数中心性的改进

    • 仅使用最短路径进行传输，很多情况下延长时间降低效率
    • 认为网络中所有不重复的路径中，经过一个节点的路径的比例越大，这个节点就越重要。

  • 缺点

    • 是另一个极端，与介数中心性相反
    • 考虑所有路径并认为每条路径作用相同

⑦ 连通介数中心性

  • 思想

    • 以然考虑所有最短路径，并且赋予较长的路径较小的权值

    • 定义节点之间的连通度

      G p q = 1 s ! P p q ( s ) + ∑ k > s 1 k ! W p q ( s ) G_{pq}=\frac{1}{s!}P_{pq}^{(s)}+\sum_{k>s}^{}\frac{1}{k!}W_{pq}^{(s)} Gpq​=s!1​Ppq(s)​+k>s∑​k!1​Wpq(s)​

  • 定义
    C B C ( r ) = 1 C ∑ p ∑ q G p r q G p q , p ≠ q ≠ r CBC(r)=\frac{1}{C}\sum_{p}^{}\sum_{q}^{}\frac{G_{prq}}{G_{pq}} , p\neq q\neq r CBC(r)=C1​p∑​q∑​Gpq​Gprq​​,p​=q​=r

⑧ 随机游走介数中心性

  • 思想

    • 从源节点Vs到目标节点Vt的随机游走过程中经过Vi的次数来表征Vi的重要性
    • 约定一次随机游走中如果网络流两次分别从相反方向经过某一节点, 则它们对这个节点的介数中心性的贡献相互抵消.

  • 缺点

    • 算法复杂度高，n3级别

⑨ 路由介数中心性

  • 采用无环路由策略，将网络用拓扑排序表示为从源节点到目标节点的有向无环图，忽略了由路由震荡产生的临时环路
  • 与负载中心性相似，但除了考虑最短路径外还考虑其他非最短路径，但并非所有路径

⑩ 子图中心性

  • 思想

    • 考虑经过节点的路径为一个封闭环的时候；这里的子图特指从一个节点开始到这个节点结束的一条闭环回路
    • 一个节点的子图数目是以它为首尾的闭环回路的个数，闭环回路路径长度越小，节点越紧密，对节点中心性贡献越大
    • 从全局视野考察网络中所有可达的邻居对节点中心性的增强作用，并且认为增强作用会随距离增加而衰减

  • 定义
    S C ( i ) = ∑ t = 1 ∞ a i i t t ! SC(i)=\sum_{t=1}^{\infty}\frac{a_{ii}^{t}}{t!} SC(i)=t=1∑∞​t!aiit​​

    • t=2时，子图中心性等价于度中心性
    • 赋予较短的回路较高的权重，使得节点的度在其中发挥较大作用的同时还考虑高阶回路

  • 应用

    • 有时，度中心性、接近中心性、介数中心性都不能区分网络中的重要节点，可以使用子图中心性进行细致区分
    • 应用于网络中模体的检测

3 基于特征向量的排序方法

① 特征向量中心性

  • 思想

    • 认为一个节点的重要性既取决于其邻居节点的数量，也取决于每个邻居节点的重要性
    • 更加强调节点所处的周围环境(节点的邻居数量和质量)，它的本质是一个节点的分值是它的邻居分值之和。
    • 完全用与某节点相连接的其他节点的信息来评价该节点的重要性。

  • 实现

    • 达到稳态的矩阵形式：x=cAx，x是A的特征值c-1对应的特征向量。给定初值x(0)，然后采用x(t)=cAx(t-1)进行迭代，直到x’(t)=x’(t-1)为止

  • 缺点

    • 一个节点的打分值完全由邻居决定，收敛过程缓慢。当不存在一个正的自然数t，使得转移矩阵的t次幂所有元素都是正的时，节点打分值会出现周期性循环，不能收敛。

  • 改进

    • α中心性
    • 提出计算节点Vi的分值时，求和中其邻居的分值不再考虑节点Vi的影响

② 累计提名

  • 思想

    • 对特征向量中心性进行改进，在每次迭代过程中，同时考虑邻居节点和自身的打分值。

  • 定义

    • 假设t=0时，每个节点都获得1次提名（pi0=1），每个时间步节点从所有相邻的节点处获得新增的提名，新增提名数为邻居节点已有提名数的总和
    • 节点在t+1时刻累积提名为 p ~ i t + 1 = p ~ i t + ∑ j a i j p ~ j t \widetilde{p}_{i}^{t+1}=\widetilde{p}_{i}^{t}+\sum_{j}^{}a_{ij}\widetilde{p}_{j}^{t} p ​it+1​=p ​it​+j∑​aij​p ​jt​
    • 归一化后提名次数不再变化，停止迭代
    • 稳态时每个节点的提名次数占所有节点的提名次数的比例就是其重要性权值

  • 对比

    • 特征向量中心性算法在每次迭代的时候, 一个节点vi 的中心性值完全等于邻居的中心性值之和, 而累计提名算法则保留了节点 vi 上一步的中心性值
    • 累积提名相比原始的特征向量中心性收敛速度更快

③ PageRank算法

  • 思想

    • 基于网页的链接结构给网页排序，认为一个页面的重要性取决于指向它的其他页面的数量和质量。多个高质量页面指向一个页面，则这个页面的质量也高
    • 首先给每个页面赋相同的PR值，进行迭代，每一步都把节点的当前PR平均分配到它指向的所有节点。新的PR值是所获得的PR值之和。迭代到PR值稳定结束。

  • 定义
    P R i ( t ) = ( 1 − c ) ∑ j = 1 n a i j P R i ( t − 1 ) k j o u t + c n PR_{i}(t)=(1-c)\sum_{j=1}^{n}a_{ij}\frac{PR_{i}(t-1)}{k_{j}^{out}}+\frac{c}{n} PRi​(t)=(1−c)j=1∑n​aij​kjout​PRi​(t−1)​+nc​

    • 引入一个随机跳转概率c，不论是否有悬挂节点，PR都以c概率均分给网络中所有节点，以1-c的概率均分给指向它的节点

  • 应用

    • 谷歌搜索引擎的核心算法
    • 期刊排序、社交网络用户排序、对风投公司(VC)的排序、对科学论文的排序以及科学家影响力的排序

④ LeaderRank算法

  • 对PR算法的改进

    • 解决出度大的节点和出度小的节点之间概率相等问题（事实上不相等）
    • PR算法的c值不具有普适性，通过实验得出

  • 思想

    • 添加背景节点和该节点与网络中所有节点的双向边来PR中的概率c
    • LR算法在某一页面输入网址访问下一个页面的概率就相当于从这个页面访问背景节点的概率, 这个概率和一个网页上的链接数负相关, 链接数越多, 网页的内容越丰富, 越倾向于从本地的链接访问, 访问背景节点的概率就越低.

  • 实现

    • 初始时刻给定网络中除背景节点Vg以外的其他节点单位资源，LRi(0)=1，LRg(0)=0。
    • 迭代公式 L R i ( t ) = ∑ j = 1 n + 1 a i j k j o u t L R j ( t − 1 ) LR_{i}(t)=\sum_{j=1}^{n+1}\frac{a_{ij}}{k_{j}^{out}}LR_{j}(t-1) LRi​(t)=j=1∑n+1​kjout​aij​​LRj​(t−1)
    • 稳态时将背景节点的分数值LRg(Tc)平分给其他n个节点

  • 优势（相比PR）

    • 收敛更快
    • 更好识别重要节点
    • 更强的鲁棒性

  • 改进

    • 从背景节点出发访问其他节点时，入度大的节点应该有更高的概率被访问到。更加重视网络中的大度节点。

⑤ HITs算法

  • 思想

    • 赋予每个节点两个度量值：权威值、枢纽值
    • 节点的权威值等于所有指向该节点的网页的枢纽值之和, 节点的枢纽值等于该节点指向的所有节点的权威值之和
    • 高权威节点应该被很多枢纽节点关注，高枢纽节点会指向很多权威节点

  • 应用

    • 用于确定一个节点上多个相互关联的属性，还可以处理更复杂的排序问题

  • 局限

    • 特殊网络结构会对HITs算法和PR算法这类应用邻居之间相互传递打分值进行排序的方法的表现

⑥ 自动信息汇集算法(ARC)

  • 改进HITs

    • HITs 算法仅考虑网页之间的链接关系(即仅考虑网络结构), ARC 算法还考虑了页面内容与搜索主题的相关性, 给每个链接赋予不同的权值, 提高页面排序的真实可靠性.

  • 过程

    • 取一个含有搜索主题 T 的网页的增广集, 这个集合中的网页抽象为节点, 它们之间的链接抽象为节点之间的连边.
    • 每个节点 vi 都有权威值 ai和枢纽值 hi, 所有节点的初始权威值设为 1. 假设某一个页面上有一个指向另一个页面的链接, 如果链接周围有较多关于搜索主题 T 的内容, 则认为链接的权值较大.
    • 记 t 为链接前后 B 字节范围内关于主题T 的内容出现的次数, 定义链接的权值 wij=t+1, 在每步迭代之后进行归一化.
    • 迭代公式a = hW , h=W(转置) ·a，使权威值和枢纽值达到稳定

⑦ SALSA算法（链接结构的随机分析法）

  • HITs的另一种改进

    • 不仅考虑顺着网页之间的链接方向访问网页，还考虑逆向访问原来网页
    • 用随机游走的方法，通过访问网页的马尔可夫过程来确定网页的权威值和枢纽值的大小

  • 图的表示

    • 所有入度不为0的节点构成权威集合Sa，所有出度不为0的节点构成枢纽集合Sh；两种节点之间关系用无向边表示。
    • 将原始网络转换为无向二分网络
    • 根据枢纽值和权威值定义两个随机游走过程，每次重新分配两个值，直到不变为止

  • 优点

    • 避免主题漂移问题
    • 实际上是考虑一个基于二部分图的随机游走问题

  • 应用

    • 基于网络结构的链路预测问题
    • 个性化推荐算法

4 基于节点移除和收缩的排序方法

① 节点删除的最短距离法

  • 思想

    • 认为一个节点移除后的破坏性与所引起的距离变化有关：移除一个节点会引起网络分化，并形成若干个连通分支，网络中节点对之间较短距离的变化越大，被移除的节点就越重要。

    • 一个连通图中删掉一个节点对网络的影响：直接损失和间接损失

      • 直接损失：被删除的节点与其他节点之间不再存在通路
      • 间接损失：删除节点后剩余节点之间不连通

  • 重要性描述

    • E表示删除节点损失的节点对（直接+间接）
    • 节点Vi的重要性表示：集合E中节点对之间的最短距离倒数之和。

  • 应用

    • 衡量一些点集的重要性
    • 在大规模网络中，删除一个节点的效果不明显，但是删除多个就很明显了

② 节点删除的生成树法

  • 思想

    • 通过考察节点删除后网络拓扑图的生成树个数来衡量节点的重要性
    • 认为一个节点删除后对应的网络生成树的额数目越少，该节点越重要。

  • 比较

    • 在节点的移除对网络的连通性不大的网络中，节点删除的生成树法优于最短距离法
    • 只能用在连通网路中

③ 节点收缩法

  • 思想

    • 将一个节点和它的邻接点收缩成一个新的节点（类似于图摘要），典型的是是星型网络收缩后凝聚为一个大节点
    • 平均最短路径长度d越小，节点数n越小，网络凝聚程度就越高
    • 节点重要程度由节点的邻居数量和节点在网络路径中的位置共同决定。由于每次收缩一个节点，都要计算一次网络的平均路径长度，时间复杂度较高，不适合计算大规模网络

④ 残余接近中心性

  • 思想

    • 认为一个节点的删除使得网络变得更加脆弱，该节点就越重要
    • R C C ( i ) = ∑ j ∑ k ≠ j 1 2 d j k ( − i ) RCC(i)=\sum_{j}^{}\sum_{k\neq j}^{}\frac{1}{2_{}^{d_{jk}(-i)}} RCC(i)=j∑​k​=j∑​2djk​(−i)​1​

5 含权网络的节点中心性

① 含权的度中心性

  • 统计显示，两个节点之间的连边的权重服从右偏分部，这也揭示了网路的异质性

  • 定义

    • 含权网络中节点Vi的度称为强度，定义为所有与Vi相连的边的权值之和：
      b i = ∑ n j = 1 w i j b_{i}=\sum_{n}^{j=1}w_{ij} bi​=n∑j=1​wij​
    • 含权网络的出度与Vi相连的出边的权值之和(bi)，含权网络中的入度为与Vi相连的入边的权值之和
    • 度中心性： W D C ( i ) = b i ∑ j = 1 n b j WDC(i)=\frac{b_{i}}{\sum_{j=1}^{n}b_{j}} WDC(i)=∑j=1n​bj​bi​​

② H-度中心性

  • 思想

    • 无权：一个节点的 Lobby 指数为 n 如果该节点至多有 n 个邻居且这些邻居的度至少为 n
    • 一个节点的H-度中心性为n，如果至多有n个权重不小于n的边与之相连
    • 一定程度上, H-度中心性可看成单纯用节点强度或度衡量中心性的一种折中

  • 主要先进地方：

    • 与节点的度相比, 强度在表征节点性质时有一定的信息丢失.

  • 缺点：

    • 边权值的取值或者数量级需要在合适的范围, 否则无法得到有效的排序结果

③ 含权的介数中心性和接近中心性

  • 思想

    • 含权的网络中, 节点之间的路径长短由边权决定，用边权的倒数来衡量距离的长短
    • d i j w α = m i n ( 1 ( w i h ) α + . . . + 1 ( w h j ) α ) d_{ij}^{w\alpha}=min\left ( \frac{1}{(w_{ih})^{\alpha }} +...+\frac{1}{(w_{hj})^{\alpha }} \right ) dijwα​=min((wih​)α1​+...+(whj​)α1​)

  • 定义
    W C C ( i ) = [ ∑ j n w i j w α ] − 1 WCC(i)=[\sum_{j}^{n}w_{ij}^{w\alpha }]^{-1} WCC(i)=[j∑n​wijwα​]−1
    W B C ( i ) = ∑ i ≠ j ≠ k g j k w α ( i ) g j k w α WBC(i)=\sum_{i\neq j\neq k}\frac{g_{jk}^{w\alpha }(i)}{g_{jk}^{w\alpha}} WBC(i)=i​=j​=k∑​gjkwα​gjkwα​(i)​

      - g(jk)是从Vj到Vk的所有最短路径的数目，g(jki)是节点Vj到Vk的g(jk)条最短路径中经过Vi的最短路径的数目

④ 含权的k-shell分解法

  • 思想

    • Garas提出一种新的节点强度的定义，改进了下面的缺点，使得k-shell可以在含权网络中应用
    • 一个节点的强度等于与该节点相连的所有边的权值之和，这种定义完全忽视了节点的连接状况，经常有很多邻居但是拥有小强度的情况
    • 含权的k-shell更加全面的考虑了节点所处的周围环境，对节点的属性刻画更为细致，因此划分的层级数目远远多于不含权的情况，重要节点的排序更加准确

  • 定义
    k i ′ = [ k i α ( ∑ j k i w i j ) β ] 1 α + β k_{i}^{'}=[k_{i}^{\alpha }(\sum_{j}^{k_{i}}w_{ij})^{\beta }]^{\frac{1}{\alpha +\beta }} ki′​=[kiα​(j∑ki​​wij​)β]α+β1​

    • 其中 ki 为节点 vi 邻居的数目, wij 为节点 vi 与其邻居 vj之间连边的权值, α和β为参数, 用以调节前两者的比重.

⑤ 含权的LeaderRank算法

⑥ 基于D-S证据理论的节点中心性

6 节点重要性排序方法的评价标准

① 用网络鲁棒性和脆弱性评价排序算法

② 用传播动力学模型评价排序算法

  • SIS模型
  • SIR模型
# 网络 # 算法 # 排序算法
Logo
2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

cover

机器学习 决策树-分类

avatar 2048 AI社区

不懂编程本科毕业生手搓三个APP，用ChatGPT两年狂赚千万美金！

而现在更厉害的是，有了多模态能力的ChatGPT，直接上传设计图片、截图，并告诉它「我要做成这个样子，这些按钮要实现xxx功能，帮我把代码写出来」。ChatGPT发布那天，Walter Isaacson在课上也是表现的异常热情激动，他的眼睛闪烁着兴奋的光芒，就像孩子看到了心爱的玩具一样。也就是说，假设你能做对80%的决策，另一个人也能做对80%，并且你们的专长领域不重叠，那么当你们联手的时候，正确

avatar 2048 AI社区
cover

【SD教程】超详细AI绘画提示词语法讲解！

avatar 2048 AI社区