任晓龙, 吕琳媛

度中心性：节点的直接邻居数目

半局部中心性：节点四层邻居的信息

k-shell分解：度中心性的扩展，根据节点在网络中的位置来定义，越在核心的节点越重要

节点的度分为入度和出度；权重为与节点相连的边的权重之和

优缺点： 优点：简单，直观，计算复杂度低 缺点：仅考虑节点最局部信息，没有对节点周围环境进行探讨。

半局部中心性涉及了节点的四阶邻居信息

k-壳分解法确定网络中节点的位置，将外围的节点剥去，处于内层的节点拥有较高的影响力，可视为是一种基于节点度的粗粒化排序方法，具体分解过程：剥除所有度为1的节点和边组成“1-壳”ks=1，再剥除所有度为2的节点组成“2-壳”ks=2....直到网络中没有节点。对一个节点来说，在剥除一层节点之后，剩下的称为该节点的剩余度。

优缺点： 优点：计算复杂度低，应用在分析大规模网络的层级结构； 缺点：1.在很多极端例子下不能应用，如树图，规则网络、BA网络、星形图，大部分节点会被分在同一层； 2.排序结果过于粗粒化，使得节点的区分度不大，此方法划分的层级较少，同层节点的重要性难以区分； 3.仅考虑剩余度的影响，即认为同一层的节点在外层都有相同的邻居数目，不合理。

节点的离心中心性：一个节点与网络中所有节点的距离之中的最大值

网络直径：网络G中所有节点的离心中心性中的最大值 网络半径：所有结点的离心中心性值中的最小值 ==>网络的中心节点为离心中心性等于网络半径的节点，一个节点的离心中心性与网络半径越接近即越中心。

接近中心性：一个节点与网络中那个其他节点的平均距离越小，该节点的接近中心性就越大。

不仅考虑节点对之间的最短路径，还考虑其他非最短路径

应用于规模不太大，环路比较少的网络中。

通过路径中传播的信息量来衡量节点的重要性

通常认为是最短路径介数中心性（BC），认为网络中所有节点对的最短路径中（一般情况下，一对节点之间存在多条最短路径），经过一个节点的最短路径数越多，这个节点就越重要。

一个节点上传输过的网络流的数量称为该节点的负载，一个节点的负载越大，该节点就越重要，介数中心性的计算时间复杂度较高。

介数中心性：只考虑最短路径

流介数中心性：只考虑所有路径并认为每条路径作用相同

考虑节点对之间的所有路径，并给予较长的路径较小的权值

短的路径计算次数较多，相当于赋予更高的权重。但添加一个约定：在一次随机游走的过程中，如果网络流两次分别从相反方向经过某一节点，则它们对这个节点的介数中性的贡献相互抵消。

s 节点到 t 节点的传输过程中存在一定数量的信息包，所有的信息包在传输过程中经过节点 i 的信息包数量的期望值即可反映该节点在网络中的重要性，称为路由介数中心性。

路由介数中心性算法采用无环路由策略，将网络用拓扑排序表示为从源节点到目标节点的有向无环图。

从全局视野考察了网络中所有可达的邻居对节点中心性的增强作用，并且认为增强作用会随着距离的增加而衰减。

一个节点的子图数目就是以该节点为首尾的闭环回路的个数

子图中心性认为闭环回路的路径长度越小，贿赂信息交流越便利，节点之间的联系越紧密，对节点的中心性贡献越大

特征向量中心性、累计提名方法 用于无向网络中；

PageRank 算法和 LeaderRank 算法通过模拟用户上网浏览网页的过程, 使节点的分值沿着访问路径增加, 用于识别网页重要性。LeaderRank 表现好于 PageRank 算法；

HITs 算法、自动信息汇集算法, SALSA 算法中考虑节点的 双重角色: 权威性和枢纽性, 并认为两者相互影响。

一个节点的重要性既取决于其邻居节点的数量（即该节点的度），也取决于每个邻居节点的重要性。

特征向量中心性更强调节点所处的周围环境（节点的邻居数量和质量），它的本质是一个节点的分值是它的邻居的分值之和，节点可以通过连接很多其他重要的节点来提升自身的重要性，分值比较高的节点要么和大量一般节点相连，要么和少量其他高分值节点相连。

在特征向量中心性中，一个节点的打分值由邻居决定，收敛缓慢，且在一定情况下打分值会出现循环，不能收敛。为了使打分值能够收敛且快速收敛，提出在每次迭代过程中应用累计提名方法，同时考虑邻居节点和自身的打分值。

PageRank算法基于网页的链接结构给网页排序，它认为万维网中的一个页面的重要性取决于指向它的其他页面的数量和质量，如果一个页面被很多高质量页面指向，则这个页面的质量也高。

每一个节点的随机跳转概率都是相同的, 即从任意网页出发, 采用输入网址来访问其他网页的概率相等。

每一个节点的随机跳转概率都是相同的, 即从任意网页出发, 采用输入网址来访问其他网页的概率相等。然而在现实中人们在出度大的节点上使用地址栏跳转的概率要远小于在出度小的节点使用地址栏跳转的概率。另一方面，PageRank算法中的参数c的选取需要实验获得，最优参数不具有普适性。

LeaderRank算法在有向网络的随机游走过程中，通过添加一个背景节点以及该节点与网络中所有节点的双向边来代替PageRank算法中的跳转概率c，从而得到一个无参数且形式上更加简单的算法。

LeaderRank算法在某一页面输入网址访问下一个页面的概率就相当于从这个页面访问背景节点的概率，这个概率与一个网页上的链接数负相关，链接数越多，网页内容越丰富，越倾向于从本地的链接访问，访问背景节点的概率越低。

LeaderRank算法再衡量社会网络中的节点的影响力等方面表现更好。与PageRank相比收敛更快；能更好的识别网络中有影响力的节点，挖掘出的重要节点可以将网络流传播的更快更广；在抵抗垃圾用户攻击和随机干扰方面有更好的鲁棒性。

HITs算法赋予每个节点两个度量值：权威值和枢纽值。

权威值衡量节点对信息的原创性, 枢 纽值反映了节点在信息传播中的作用。

枢纽页面是那些指向权威页面的、链接数较多的页面，反应网页上链接的价值。 节点的权威值等于所有指向该节点的网页的枢纽值之和（入度之和） 节点的枢纽值等于该节点指向的所有结点的权威值之和（出度之和）

权威值受到枢纽值的影响, 枢纽值又受到权威值的影响, 最终通过迭代达到收敛。

应用：提出一种可以有效抵抗恶意评分的排序方法, 该 方法认为一个商品得到的打分反映了这个商品的质 量, 自然地, 应该给可信度高的用户更大的权重; 反 过来, 一个用户打分的可信度, 可以用他的打分和商 品质量的接近程度来衡量.

特殊的网络结构会影响 HITs 算法。如万维网中广泛存在紧密连接社团，社团内的节点之间非常紧密的链接关系会使这些节点的权威值和枢纽值相互增强，从而使排序结果耿倾向于将社团内部的页面排在前面而偏离搜索的主题，出现主题漂移现象。

是对HITs算法的改进，HITs仅考虑网页之间的链接关系（仅考虑网络结构），ARC还考虑了页面内容与搜索主题的相关性，给每个链接赋予不同的权值，提高页面的真实可靠性。

链接结构的随机分析法（HITs的改进），不仅考虑了用户在浏览网页时顺着网页之间的链接方向访问网页，还考虑了逆着链接方向访问原来的网页的情况。

SALSA算法采用随机游走的方法，通过访问网页的马尔科夫过程来确定王爷的权威值和枢纽值的大小。能更好的避免主题漂移的问题。SALSA算法实际上考虑的是一个基于二部分图的随机游走过程，这一思路也被成功地应用在信息挖掘的另外两个领域中，即基于网络结构的链路预测问题和个性化推荐算法。

该方法认为破坏性反映重要性，当一个节点移除后的破坏性和所引起的距离变化有：移除一个节点（集）会造成网络分化，并形成若干个连通分支，网络中节点对之间较短距离的变化越大，被移除的节点就越重要。

对于不同长度的路径：认为“相对直接的、近距离的联系所造成的破坏性大于相对间接的、远距离的联系所造成的 破坏性”。

在连通图中一个节点被删除之后, 对网络的整体状况的影响体现在两个方面: 直接损失和间接损失。 直接损失：被删除的节点与其他剩余节点之间不再存在通路。 间接损失：删除一个节点造成剩余节点之间不连通而引发的损失。

一个图的树是该图的一个连通的无环子 图, 一个图的生成树定义为拥有该图的所有顶点的 树. 节点删除的生成树法认为一个节点删除后对 应的网络的生成树的数目越少, 该节点越重要。

节点收缩：将一个节点和它的邻节点收缩成一个新节点。将核心节点收缩后整个网络可以更好的聚合在一起。典型就是星形网络的核心节点收缩后，整个网络会凝聚成一个大节点。节点收缩法主要考察节点收缩前后网络凝聚度的变化幅度。

节点收缩法中节点的重要程度由节点的邻居 数量和节点在网络路径中的位置共同决定. 由于每 次收缩一个节点, 都要计算一次网络的平均路径长度, 时间复杂度比较高, 不适于计算大规模网络。

用来衡量节点的移除对网络带来的影响。该方法认为若一个节点的删除使得网络变得更加脆弱，该节点就越重要。

无权网络采用粗粒化的二分法来表示网络中的节点之间的联系（有边为1，无边为0），不考虑联系的强弱信息。

比较有代表性的：用节点的邻居数量和节点周围的边权共同表示含权网络中节点的度值。

一个节点的H-度中心性为n，则至多有n个权重都不小于n的边与之相连，一定程度上H-度中心性可看成单纯用节点强度或者度衡量中心性的一种折中。（需要对边权值有合适的取值）

在无权网络中，节点的介数中心性是所有节点对的最短路径中，通过该节点的数目的比例。

含权的网络中，节点之间的路径长短由边权决定。

不含权的k-壳分解法中, 用迭代法层层剥去外围节点, 以确定节点在网络中的位置, 依靠位置信息来确定节点的重要性.

含权网络中，重新定义了节点的度：一个节点的强度等于与该节点相连的所有边的权值之和。 缺点：忽视了 节点的连接状况, 经常出现有很多邻居而节点的强 度却很小的情况。

标准的 LeaderRank 算法是针对无权有向网络的 一种简单, 能够快速收敛, 重要节点识别准确, 抗攻 击和干扰能力强的高效算法。

D-S证据理论中的基本概率分配具有直接表达“不确定”和“不知道”两种状态的能力。

目前评价各种排序算法优劣的主要思路是：将排序算法得出的重要节点作为研究对象，通过考察这些节点对网络某种结构和功能及对其他节点状态的影响程度来判断排序是否恰当。

本类方法着重考察网络中一部分节点移除后网络结构和功能的变化，变化越大移除的节点越重要。