“网络中心性”的版本间的差异

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
跳到导航 跳到搜索
第31行： 第31行：
  
  
−
同样地，计数可以记录行走的数量或长度。量是给定类型的总步数。上一段的三个例子就属于这一类。长度则给出从给定顶点到图中其余顶点的距离。Freeman的'''<font color="#ff8000"> 接近中心性Closeness centrality</font>'''，即从一个给定顶点到所有其他顶点的总测地线距离，是最著名的例子。<ref name=Borgatti2006/>请注意，这种分类独立于步行计数的类型（即：步行，小道，路径，测地线）。
+
同样地，计数可以记录行走的数量或长度。量是给定类型的总步数。上一段的三个例子就属于这一类。长度则给出从给定顶点到图中其余顶点的距离。Freeman的'''接近中心性 Closeness centrality'''，即从一个给定顶点到所有其他顶点的总测地线距离，是最著名的例子。<ref name=Borgatti2006/>请注意，这种分类独立于步行计数的类型（即：步行，小道，路径，测地线）。
  
  
第79行： 第79行：
  
  
−
同样，权限分配的解决方案<ref>{{cite journal |last=Hu |first=Xingwei |first2=Lloyd |last2=Shapley |title=On Authority Distributions in Organizations |journal=Games and Economic Behavior |volume=45 |pages=132–170 |year=2003 | doi = 10.1016/s0899-8256(03)00130-1 }}</ref></font>'''采用 Shapley-Shubik 幂指数，而不是 Shapley 值来衡量参与者之间的双边直接影响。这种分布确实是一种产生特征向量中心性的类型。它用于对 Hu (2020)中的大数据对象进行排序<ref>{{cite journal|last=Hu|first=Xingwei|year=2020|volume=7|title=Sorting big data by revealed preference with application to college ranking |journal=Journal of Big Data|doi=10.1186/s40537-020-00300-1|doi-access=free}}</ref>，比如美国大学排名。
+
同样，权限分配的解决方案<ref>{{cite journal |last=Hu |first=Xingwei |first2=Lloyd |last2=Shapley |title=On Authority Distributions in Organizations |journal=Games and Economic Behavior |volume=45 |pages=132–170 |year=2003 | doi = 10.1016/s0899-8256(03)00130-1 }}</ref>采用 Shapley-Shubik 幂指数，而不是 Shapley 值来衡量参与者之间的双边直接影响。这种分布确实是一种产生特征向量中心性的类型。它用于对 Hu (2020)中的大数据对象进行排序<ref>{{cite journal|last=Hu|first=Xingwei|year=2020|volume=7|title=Sorting big data by revealed preference with application to college ranking |journal=Journal of Big Data|doi=10.1186/s40537-020-00300-1|doi-access=free}}</ref>，比如美国大学排名。
  
  

2021年8月1日 (日) 13:42的版本

在图论和网络分析中，中心性 centrality 指标用于识别图中最重要的顶点。其应用包括在社交网络中识别出最有影响力的个人，在因特网或城市网络中识别出最为关键的基础设施节点，以及识别疾病的超级传播者。中心性的概念最初是在社交网络分析中发展起来的，许多用于衡量中心性的术语都反映出了它们的社会学起源。[1]中心性不应与节点影响度相混淆，后者意在量化网络中每个节点的影响。


中心性指数的定义与特性

中心性指数 centrality indices是对“重要顶点的特征是什么？”这一问题的回答。这个回答是以图中顶点的实值函数的形式给出的，可根据产生的函数值排序以确定最为重要的节点。[2][3][4]


“重要性”的含义十分广泛，因此导致了许多不同的中心性定义方式，我们可以将各种不同的定义方式划分为如下两类。


“重要性”可以被设想为与网络中的某种流动或传输有关。这允许根据重要的流动的类型对中心性进行分类。[3] “重要性”也可以被设想为与网络的内聚力 cohesiveness有关。这允许根据内聚力的度量方式对中心性进行分类。[5]这两种方法在不同类别中划分了中心性。进一步的结论是，适用于某一类别的中心性在应用于另一类别时往往会“出错”。[3]


当根据内聚力方法对中心性进行分类时，很明显大多数中心性都将被划分于同一类别。起始于给定顶点的步数总和仅取决于步数的定义以及计数方式。这种分类方式的不足表现为它仅能较弱的描绘中心性特征，即按照一步步长（度中心性）到无穷步步长（特征向量中心性）的方式将中心性置于一种光谱状的分类中。[2][6]观察到许多中心性共享这种家庭关系，这或许能解释这些指数之间的高阶相关性。


网络流特征

一个网络可以被看成是对某种物体流动的路径描述。这允许基于流动的类型和由中心性编码的路径类型进行表征。流可以基于传输，即每个不可分割的项目从一个节点到另一个节点，就像一个包裹从配送站传递到客户的房子。第二种情况是串行复制，在这种情况下，一个项目被复制以便源头和目标节点都拥有它。例如通过流言传播信息，信息以私有方式传播，并在流程结束时通知源节点和目标节点。最后一种情况是并行复制，即项目同时被复制到几个链接，就像无线电广播一次性向多个听众提供相同的信息。[3]


同样，路径类型可以被限定为测地线 geodesics（最短路径）、路径（对顶点的访问不超过一次）、小径（可以访问多次顶点，没有边被访问超过一次）或者步子（可以多次访问/穿过多次顶点和边）。


行走结构特征

可以从中心性的构造方式推导出另一种分类方法。这又分成了两个类。中心性可以是径向的，也可以是中间的。径向中心性计算从给定顶点开始/结束的步数。度中心性和特征向量中心性是径向中心性 Radial centralities的例子，计算长度为一或无穷大的步数。中间中心性 Medial centralities计算通过给定顶点的步数。典型的例子是Freeman的中介中心性 Betweenness centrality，即通过给定顶点的最短路径的数量。[5]


同样地，计数可以记录行走的数量或长度。量是给定类型的总步数。上一段的三个例子就属于这一类。长度则给出从给定顶点到图中其余顶点的距离。Freeman的接近中心性 Closeness centrality，即从一个给定顶点到所有其他顶点的总测地线距离，是最著名的例子。[5]请注意，这种分类独立于步行计数的类型（即：步行，小道，路径，测地线）。


Borgatti和Everett提出，这种类型为如何最好地比较中心性度量提供了见解。在这个2×2分类中，放在同一盒子中的中心性足够相似，可以做出合理的选择; 人们可以合理地比较哪个对于给定的应用更好。然而，不同盒子中的度量方法是截然不同的。只有在预先确定哪个类别更适用的情况下，对相对适应性的评估才会发生，这使得比较变得毫无意义。[5]

光谱上存在的径向量中心

步行结构的特征表明，几乎所有广泛使用的中心性都是径向量的衡量。这得出结论顶点的中心性是与之相关联的顶点中心性的函数。中心性根据如何定义关联而不同。


Bonacich指出，如果联想是根据行走来定义的，那么可以根据考虑的行走长度来定义一个中心性家族。[2]度中心性计算长度为1的行走，特征向量中心性计算长度为无穷大的行走。关联的其他定义也是合理的。 阿尔法中心性 Alpha centrality允许顶点有一个外部影响源。Estrada的子图中心性 Subgraph centrality提出只计算封闭路径（三角形、正方形等）。


这些度量方法的核心是这种现象：图中邻接矩阵的幂给出了由该幂给出的步长的数目。同样，矩阵指数也与给定步长的数目密切相关。邻接矩阵的初始转换允许对步行计数的类型进行不同的定义。无论采用哪种方法，顶点的中心性都可以表示为无穷和


[math]\displaystyle{ \sum_{k=0}^\infty A_{R}^{k} \beta^k }[/math]


矩阵幂或者


[math]\displaystyle{ \sum_{k=0}^\infty \frac{(A_R \beta)^k}{k!} }[/math]


矩阵指数，其中


  • [math]\displaystyle{ k }[/math]为步长
  • [math]\displaystyle{ A_R }[/math]是邻接矩阵的转秩
  • [math]\displaystyle{ \beta }[/math]是保证收敛的折扣参数。


Bonacich的一系列度量并没有改变邻接矩阵。阿尔法中心性用它的解决方案替代了邻接矩阵。子图中心性用它的踪迹取代了邻接矩阵。一个令人吃惊的结论是，不管邻接矩阵最初的转变是什么，所有这些方法都有共同的限制行为。随着[math]\displaystyle{ \beta }[/math]系数趋近于零，指数收敛到度中心性。随着[math]\displaystyle{ \beta }[/math]系数接近其最大值，指数收敛到特征向量中心性。[6]


博弈论中心性 Game-theoretic centrality

上述大多数标准度量的共同特点是，它们通过只关注一个节点本身所扮演的角色来评估确定节点的重要性。然而, 在许多应用中，这种方法是不充分的，因为可能会发生协同作用


如果将节点的功能分组考虑。

博弈论中心性的例子

例如，考虑阻止流行病的问题。看看上面的网络图像，我们应该给哪些节点接种疫苗？基于前面描述的度量，我们希望识别在疾病传播中最重要的节点。仅仅基于中心性的方法，即关注节点的个别特性，可能不是一个好主意。红色方块中的节点，单独不能阻止疾病的传播，但把它们作为一个群体来考虑，我们清楚地看到，如果疾病在节点 [math]\displaystyle{ v_1 }[/math]、[math]\displaystyle{ v_4 }[/math]和[math]\displaystyle{ v_5 }[/math]中开始，它们就能阻止疾病的传播。博弈论中心性试图利用博弈论中的工具来研究所描述的问题和机会。本文提出的方法[7]使用了 Shapley 值。由于 Shapley 值计算的时间复杂性，这一领域的大部分工作都集中在实现新的算法和方法，这些算法和方法依赖于网络的特殊拓扑结构或问题的特殊性质。这种方法可以将时间复杂度从指数级降低到多项式级。


同样，权限分配的解决方案[8]采用 Shapley-Shubik 幂指数，而不是 Shapley 值来衡量参与者之间的双边直接影响。这种分布确实是一种产生特征向量中心性的类型。它用于对 Hu (2020)中的大数据对象进行排序[9]，比如美国大学排名。


重要限制

中心性指标有两个重要的局限性，一个显而易见，另一个则不易察觉。显而易见的局限性是，对于一个应用最优的中心性对于另一个应用常常是次优的。事实上，如果不是这样，我们就不需要这么多不同的中心性。克拉克哈特风筝图为这一现象提供了一个例证，对于这个图，三个不同的中心性概念给出了最中心顶点的三种不同选择。[10]


更不易察觉的限制是通常会错误地认为顶点中心性表示顶点的相对重要性。中心性指数被明确地设计来产生一个指出最重要顶点的排名。[2][3]在刚才提到的限制下，他们做得很好。它们通常不用来度量节点的影响力。最近，网络物理学家已经开始开发点影响力度量 Node influence metrics来解决这个问题。


错误有两方面。首先，一个排名只根据顶点的重要性排序，它并不对节点重要性的不同水平进行量化区分。这可以通过将弗里曼中心度 Freeman centralization应用到中心性度量来缓解，这可以根据节点的中心度得分差异对节点的重要性提供一些见解。此外，弗里曼中心度使人们能够通过比较几个网络的最高中心度得分来比较它们。[11]然而，这种方法在实践中很少见到。[citation needed]


其次，用以(正确地)识别给定网络/应用中最重要顶点的特征并不一定适用于其余顶点。


对于大多数其他网络节点，排名可能是没有意义的。[12][13][14][15]这就解释了为什么，例如，谷歌图片搜索只有前几个结果以合理的顺序出现。网页排名是一个非常不稳定的度量，在对跳转参数进行小的调整之后显示了频繁的秩逆转。[16]


虽然中心性指数未能推广到网络的其他部分，乍看起来似乎是违反直觉的，但它直接遵循上述定义。


复杂网络具有异构的拓扑结构。如果最佳度量取决于最重要顶点的网络结构，对于这些顶点最优的度量对于网络的其余部分是次优的。[12]


度中心性 Degree centrality

同一幅图中的实例A）中介中心性，B）紧密中心性，C）特征向量中心性,D）度中心性，E）调和中心性，F）卡兹中心性

历史上第一个并且概念上最简单是度中心性，它定义为一个节点上事件的链接数量（即一个节点拥有的关系数量）。度可以解释为节点捕获的任何流经网络的东西（例如病毒或某些信息）的直接风险。在有向网络的情况下（关系有方向） ，我们通常定义两个独立的度中心性的度量，即 入度 Indegree和出度 Outdegree。因此，入度是指向该节点的关系数，出度是该节点指向其他节点的关系数。当关系与一些积极的方面如友谊或合作有关时，入度通常被解释为一种受欢迎的形式，而出度则被解释为一种合群的形式。


对于给定的图[math]\displaystyle{ G:=(V,E) }[/math]与[math]\displaystyle{ |V| }[/math]顶点和[math]\displaystyle{ |E| }[/math]边，顶点的度中心性定义为


[math]\displaystyle{ C_D(v)= \deg(v) }[/math]


计算一个图中所有节点的度中心性，在图的密集邻接矩阵表示中采用[math]\displaystyle{ \Theta(V^2) }[/math]，在边的稀疏矩阵表示中采用[math]\displaystyle{ \Theta(E) }[/math] 。


节点级中心性的定义可以扩展到整个图，在这种情况下，我们指的是图的中心度。[17]设[math]\displaystyle{ v* }[/math]为[math]\displaystyle{ G }[/math]中度中心性最高的节点。让[math]\displaystyle{ X:=(Y,Z) }[/math]是[math]\displaystyle{ |Y| }[/math]节点连接图，最大化下列数量([math]\displaystyle{ y* }[/math] 是[math]\displaystyle{ X }[/math]中度最高的节点) :


[math]\displaystyle{ H= \sum^{|Y|}_{j=1} [C_D(y*)-C_D(y_j)] }[/math]


相应地，图形[math]\displaystyle{ G }[/math]的度中心度如下:


[math]\displaystyle{ C_D(G)= \frac{\sum^{|V|}_{i=1} [C_D(v*)-C_D(v_i)]}{H} }[/math]


当图形[math]\displaystyle{ X }[/math]包含与一个所有其他节点都连接的中心节点(一个星形图)时，[math]\displaystyle{ H }[/math]的值最大化，在这种情况下


[math]\displaystyle{ H=(n-1)\cdot((n-1)-1)=n^2-3n+2. }[/math]


所以，对于任意的图[math]\displaystyle{ G:=(V,E), }[/math]


[math]\displaystyle{ C_D(G)= \frac{\sum^{|V|}_{i=1} [C_D(v*)-C_D(v_i)] }{|V|^2-3|V|+2} }[/math]


紧密中心性 Closeness centrality

在连通图中，节点的标准紧密中心性（或贴近性）是节点与图中所有其他节点之间最短路径的平均长度。因此，一个节点越是中心，它就越接近所有其他节点。


Alex Bavelas (1950)将贴近性定义为相对于距离的倒数，即:[18][19] that is:


[math]\displaystyle{ C(x)= \frac{1}{\sum_y d(y,x)} }[/math]


其中[math]\displaystyle{ d(y,x) }[/math]是顶点[math]\displaystyle{ x }[/math]和 [math]\displaystyle{ y }[/math]之间的距离。然而，当谈到紧密中心性时，人们通常会提到它的标准化形式，一般是以前的公式乘以[math]\displaystyle{ N-1 }[/math]，其中[math]\displaystyle{ N }[/math] 是图中的节点数。这种调整允许比较不同大小图形的节点。


从所有其他节点或到所有其他节点的距离在无向图中是不相关的，但是在有向图中可能产生完全不同的结果(例如:一个网站可以从传出链接获得高的紧密中心性，而从传入链接获得低的紧密中心性）。


调和中心性 Harmonic centrality

在一个（不一定是连通的）图中，调和中心性反转了紧密中心性定义中的和互反运算:


[math]\displaystyle{ H(x)= \sum_{y \neq x} \frac{1}{d(y,x)} }[/math]


其中[math]\displaystyle{ 1 / d(y,x) = 0 }[/math]如果没有来自[math]\displaystyle{ y }[/math]到[math]\displaystyle{ x }[/math]的路径 。调和中心性可以通过除以[math]\displaystyle{ N-1 }[/math]来标准化，其中[math]\displaystyle{ N }[/math]是图中的节点数。


调和中心性是由Marchiori和Latora (2000)提出的[20]，然后由德克 Dekker (2005)以“有价值的中心性”之名独立提出的，[21]再由罗切特 Rochat提出(2009)。[22]


中介中心性 Betweenness centrality

文件:Graph betweenness.svg
色调（从红色 = 0到蓝色 = max）表示节点中介性

中介性是图中顶点的中心性度量（也有边中介性，这里没有讨论）。中介中心性量化了一个节点沿着其他两个节点之间的最短路径充当桥梁的次数。在Linton Freeman[23]的概念中，它是作为一种量化一个人对社交网络中其他人之间交流控制的度量被引入的，在两个随机选择的顶点之间随机选择的最短路径上出现概率高的顶点具有很高的中介性。


在一个图[math]\displaystyle{ G:=(V,E) }[/math]与[math]\displaystyle{ V }[/math]的顶点中介性计算如下:


  1. 对于每一对顶点(s,t)，计算它们之间的最短路径。
  1. 对于每对顶点(s,t) ，确定通过该顶点（这里是顶点 v）的最短路径的分数。
  1. 对所有顶点对(s,t)求这个分数的和。


更确切地说，中介性可以表示为:[24]


[math]\displaystyle{ C_B(v)= \sum_{s \neq v \neq t \in V}\frac{\sigma_{st}(v)}{\sigma_{st}} }[/math]


其中[math]\displaystyle{ \sigma_{st} }[/math]是从节点[math]\displaystyle{ s }[/math]到节点[math]\displaystyle{ t }[/math]的最短路径总数，[math]\displaystyle{ \sigma_{st}(v) }[/math]是通过[math]\displaystyle{ v }[/math]的路径数。中介性也许可以通过除以不包括V的顶点对的数目被规范化，对于有向图是[math]\displaystyle{ (n-1)(n-2) }[/math]，对于无向图是[math]\displaystyle{ (n-1)(n-2)/2 }[/math]。例如，在一个无向星图中，中心顶点（包含在每个可能的最短路径中）的中介性为[math]\displaystyle{ (n-1)(n-2)/2 }[/math] （1，如果标准化） ，而叶节点（包含在没有最短路径中）的中介性为0。


从计算的角度来看，图中所有顶点的中介中心性和紧密中心性都涉及到计算图中所有顶点对之间的最短路径，采用[math]\displaystyle{ O(V^3) }[/math]时间和 弗洛伊德-沃肖尔 Floyd-Warshall算法。然而，对于稀疏图，约翰逊 Johnson算法的效率可能更高，采用[math]\displaystyle{ O(V^2 \log V + V E) }[/math]时间。在不加权图的情况下，可以用布兰德斯 Brandes 的算法进行计算[24]，该算法需要 [math]\displaystyle{ O(V E) }[/math]时间。一般情况下，这些算法假定图是无向的，并且连通图中允许有圈和多条边。当专门处理网络图时，图通常没有环或多条边来维持简单的关系（其中的边表示两个人或顶点之间的联系）。在这种情况下，使用 Brandes 的算法将最终的中心性分数除以2来计算每条被重复计算的最短路径。[24]


特征向量中心性 Eigenvector centrality'

特征向量中心性（也称为特征中心性）是对网络中节点影响的一种度量。它将相对得分分配给网络中的所有节点，这是基于这样一个概念: 连接得分高的节点比连接得分低的节点对得分贡献更大。[25][4]谷歌的网页排名和卡兹中心性是特征向量中心性的变体。[26]


使用邻接矩阵发现特征向量中心性 Eigenvector centrality

对于一个给定的图[math]\displaystyle{ G:=(V,E) }[/math]与[math]\displaystyle{ |V| }[/math]的顶点数 让[math]\displaystyle{ A = (a_{v,t}) }[/math]成为邻接矩阵。即，如果顶点[math]\displaystyle{ v }[/math]与[math]\displaystyle{ t }[/math]相连，而 [math]\displaystyle{ a_{v,t} = 0 }[/math]不然。顶点[math]\displaystyle{ v }[/math]的相对中心性评分可以定义为:


[math]\displaystyle{ x_v = \frac{1}{\lambda} \sum_{t \in M(v)}x_t = \frac{1}{\lambda} \sum_{t \in G} a_{v,t}x_t }[/math]


其中 [math]\displaystyle{ M(v) }[/math]是[math]\displaystyle{ v }[/math]的相邻集合，而[math]\displaystyle{ \lambda }[/math]是一个常量。通过一个小的重新排列，这可以用向量符号重写为特征向量方程。


[math]\displaystyle{ \mathbf{Ax} = {\lambda}\mathbf{x} }[/math]


一般情况下，存在许多不同的特征值[math]\displaystyle{ \lambda }[/math]，对于这些特征值存在一个非零特征向量解。由于邻接矩阵中的项是非负的，所以由 佩龙-弗罗贝尼乌斯 Perron- Frobenius定理得出，它有一个唯一的正实数最大特征值。由这个最大的特征值得出期望的中心性度量。[27]相关特征向量的</ref> The [math]\displaystyle{ v^{th} }[/math]分量给出了网络中顶点[math]\displaystyle{ v }[/math]的相对中心性评分。特征向量只定义了一个公共因子，所以只有顶点中心性的比例是明确定义的。要定义一个绝对分数，必须对特征向量进行标准化，例如，使所有顶点的和为1或顶点的总数n。幂迭代是许多特征值算法之一，可以用来找到这个主要特征向量。[26]此外，这推广，使得 A中的项可以是表示连接强度的实数，就像在随机矩阵中一样。


卡兹中心性 Katz centrality

卡兹中心性[28]是度中心性的推广。度中心性度量的是直接相邻节点的数量，卡兹中心性度量的是通过一条路径可以连接的所有节点的数量，而远处节点的贡献会受到削减。在数学上，它被定义为


[math]\displaystyle{ x_i = \sum_{k=1}^{\infin}\sum_{j=1}^N \alpha^k (A^k)_{ji} }[/math]


其中[math]\displaystyle{ \alpha }[/math] 是[math]\displaystyle{ (0,1) }[/math] 中的衰减因子。


卡兹中心性可以看作是特征向量中心性的一种变体。卡兹中心性的另一种形式是


[math]\displaystyle{ x_i = \alpha \sum_{j =1}^N a_{ij}(x_j+1). }[/math]


与特征向量中心性的表达式相比，[math]\displaystyle{ x_j }[/math]被[math]\displaystyle{ x_j+1. }[/math]所代替


结果表明，[29]主特征向量（与[math]\displaystyle{ A }[/math]，邻接矩阵的最大特征值相关）是卡兹中心性的极限，当[math]\displaystyle{ \alpha }[/math]从下接近 [math]\displaystyle{ \tfrac{1}{\lambda} }[/math]>时 。


网页排名中心性 PageRank centrality

网页排名满足下面的等式


[math]\displaystyle{ x_i = \alpha \sum_{j } a_{ji}\frac{x_j}{L(j)} + \frac{1-\alpha}{N}, }[/math]


其中


[math]\displaystyle{ L(j) = \sum_{i} a_{ji} }[/math]


是节点[math]\displaystyle{ j }[/math]（或有向图中出站链接的数量）的相邻节点数量。与特征向量中心性和卡兹中心性相比，尺度因子[math]\displaystyle{ L(j) }[/math]是一个主要的区别。网页排名中心性和特征向量中心性的另一个区别是网页排名中心性向量是一个左手特征向量（注意因子[math]\displaystyle{ a_{ji} }[/math]具有相反的索引）。[30]


渗滤中心性 Percolation centrality（PC）

在复杂网络中，存在大量的中心性度量来确定单个节点的“重要性”。然而，这些度量单纯从拓扑学的角度来量化节点的重要性，节点的值并不以任何方式依赖于节点的状态。不管网络动态如何，它都保持不变。即使对于加权的两者之间的度量也是如此。然而，一个节点可能很好地位于中介中心性或其他中心性度量的中心位置，但可能不是位于有渗滤的网络的上下文中的中心位置。在许多情况下，复杂网络中都会出现“传染”的渗滤现象。例如，病毒或细菌感染可以通过人们的社交网络传播，也就是所谓的接触网络。还可以在更高的抽象层次上考虑疾病的传播问题，设想通过公路、铁路或空中连接起来的城镇或人口中心网络。计算机病毒可以通过计算机网络传播。关于商业活动和交易的谣言或新闻也可以通过人们的社交网络传播。在所有这些情况下，一种“传染病”在一个复杂网络的链接上传播，随着它的传播，无论是可恢复的还是不可恢复的，都会改变节点的“状态”。例如，在流行病学方案中，随着感染扩散，个人从”易感”状态转变为”受感染”状态。在上面的例子中，随着传染的扩散，每个节点可以采取的状态可以是二进制的（例如接收/没有接收到一条新闻）、离散的（易感/受感染/康复） ，甚至是连续的（例如一个城镇中受感染的人的比例）。这些情景的共同特点是，传染的扩散导致网络中节点状态的改变。'渗滤中心性 Percolation centrality就是基于这个思想而提出的，它特别地度量了节点在协助网络渗滤方面的重要性。这种度量是由皮拉维南 piraveanan等人提出的。[31]


渗滤中心性定义为在给定时间内一个给定节点的渗滤路径的比例。“渗滤路径”是一对节点之间的最短路径，其中源节点被渗滤（例如，被感染）。目标节点可以是渗滤的或非渗滤的，或处于部分渗滤状态。


[math]\displaystyle{ PC^t(v)= \frac{1}{N-2}\sum_{s \neq v \neq r}\frac{\sigma_{sr}(v)}{\sigma_{sr}}\frac{{x^t}_s}{{\sum {[{x^t}_i}]}-{x^t}_v} }[/math]


其中[math]\displaystyle{ \sigma_{sr} }[/math]是从节点[math]\displaystyle{ s }[/math]到节点[math]\displaystyle{ r }[/math]的最短路径的总数，[math]\displaystyle{ \sigma_{sr}(v) }[/math]是通过[math]\displaystyle{ v }[/math]的路径的总数。在时间 < math > t </math > 时，节点< math > i</math >的渗滤状态用[math]\displaystyle{ {x^t}_i }[/math]表示，两个特殊情况是当[math]\displaystyle{ {x^t}_i=0 }[/math]表示在时间上是非渗滤状态，而当[math]\displaystyle{ {x^t}_i=1 }[/math]表示在时间上是完全渗滤状态。两者之间的值表示部分渗滤状态（例如，在一个城镇网络中，这是该城镇感染者的百分比）。


渗流路径的权重取决于分配给源节点的渗滤水平，前提是源节点的渗滤水平越高，源节点的路径就越重要。因此，位于源自高渗滤节点的最短路径上的节点可能对渗滤更为重要。PC 的定义也可以扩展到包括目标节点的权重。渗滤中心性计算运行在[math]\displaystyle{ O(NM) }[/math]时间，高效的实现采用了布兰德斯快速算法，如果计算需要考虑目标节点的权重，最坏情况下时间为[math]\displaystyle{ O(N^3) }[/math]。


跨团中心性 Cross-clique centrality

复杂图中单个节点的跨团中心性决定了一个节点与不同团的连通性。具有高度跨团连通性的节点有利于信息或疾病在图中的传播。团是一种子图 Subgraphs，团中的每个节点都与团中的其他节点相连。对于一个给定的图[math]\displaystyle{ G:=(V,E) }[/math]与[math]\displaystyle{ |V| }[/math]顶点和[math]\displaystyle{ |E| }[/math] 边的跨团连通性，定义为 [math]\displaystyle{ X(v) }[/math] 其中[math]\displaystyle{ X(v) }[/math]是[math]\displaystyle{ v }[/math]所属的顶点团数。这个度量应用日久，[32]但是在1998年由埃弗莱特 Everett 和博加提 Borgatti 首次提出，他们称之为派系重叠中心性 Clique-overlap centrality。


弗里曼中心度 Freeman centralization

任何网络的中心度都是衡量其最核心的节点相对于其他所有节点的集聚程度的标准。[11]中心度的度量方法是: (a)计算网络中最中心的节点与所有其他节点之间的中心性差异之和; (b)将这个数量除以理论上相同规模的任何网络中这种差异之和的最大值。[11]因此，每个中心性度量都可以有自己的中心度度量。正式定义，如果 [math]\displaystyle{ C_x(p_i) }[/math]是点[math]\displaystyle{ i }[/math]的中心性度量，如果[math]\displaystyle{ C_x(p_*) }[/math]是网络中最大的中心性度量，如果:


[math]\displaystyle{ \max \sum_{i=1}^{N} C_x(p_*)-C_x(p_i) }[/math]


是具有相同节点数的任何图的点中心性[math]\displaystyle{ C_x }[/math]的最大差值之和，然后网络中心度是：[11]


[math]\displaystyle{ C_x=\frac{\sum_{i=1}^{N} C_x(p_*)-C_x(p_i)}{\max \sum_{i=1}^{N} C_x(p_*)-C_x(p_i)}. }[/math]


基于相异性的中心性度量

在图示的网络中，绿色节点和红色节点最不相似，因为它们之间不共享相邻节点。因此，绿色的节点比灰色的节点对红色节点的中心性的贡献更大，因为红色的节点只能通过绿色访问蓝色的节点，而灰色的节点对于红色的节点是多余的，因为它可以直接访问每个灰色的节点，而不需要任何中介。


为了在给定网络节点的排序中获得更好的结果，[33]在复杂网络中使用了相异性度量（特定于分类和数据挖掘理论）来丰富中心性度量。用特征向量中心性来说明，通过求解特征值问题来计算每个节点的中心性。


[math]\displaystyle{ W\mathbf{c}=\lambda \mathbf{c} }[/math]


这里[math]\displaystyle{ W_{ij}=A_{ij}D_{ij} }[/math] (coordinate-to-coordinate product)和 [math]\displaystyle{ D_{ij} }[/math]是一个任意的不相似矩阵，通过一个相异性度量来定义，例如，Jaccard相异性由以下给出。


[math]\displaystyle{ D_{ij}=1-\dfrac{|V^{+}(i)\cap V^{+}(j)|}{|V^{+}(i)\cup V^{+}(j)|} }[/math]


这种度量允许我们量化每个节点对给定节点中心性的拓扑贡献（这就是为什么我们称之为贡献中心性） ，对那些相异性较大的节点有更多的权重/相关性，因为这些节点允许给定的节点访问那些它们自己不能直接访问的节点。


值得注意的是，[math]\displaystyle{ W }[/math] 是非负的，因为 [math]\displaystyle{ a }[/math] 和 [math]\displaystyle{ d }[/math]都是非负矩阵，所以我们可以使用Perron–Frobenius定理来确保上述问题对于 c 非负的λ = λmax 有唯一的解，这样我们就可以推断出网络中每个节点的中心性。因此，i-th 节点的中心性为


[math]\displaystyle{ c_i=\dfrac{1}{n}\sum_{j=1}^{n}W_{ij}c_{j}, \,\,\,\,\,\, j=1,\cdots,n }[/math]


其中 [math]\displaystyle{ n }[/math] 是网络中的节点数。在所研究的案例中，为了获得改进的结果，测试了一些相异性度量和网络被测试。[34]


扩展

经验和理论研究已经将静态网络中的中心性概念扩展到时间依赖网络和时间网络中的动态中心性。[35][36][37]


对加权网络的推广，见 Opsahl 等人。(2010). [38]


中心性的概念也扩展到了群体层次。例如，组间的中介中心性显示了连接穿过组的成对非组成员的测地线的比例。[39][40]


另见


参考文献

  1. ↑ Newman, M.E.J. 2010. Networks: An Introduction. Oxford, UK: Oxford University Press.
  2. ↑ 2.0 2.1 2.2 2.3 Bonacich, Phillip (1987). "Power and Centrality: A Family of Measures". American Journal of Sociology. 92 (5): 1170–1182. doi:10.1086/228631.
  3. ↑ 3.0 3.1 3.2 3.3 3.4 Borgatti, Stephen P. (2005). "Centrality and Network Flow". Social Networks. 27: 55–71. CiteSeerX 10.1.1.387.419. doi:10.1016/j.socnet.2004.11.008.
  4. ↑ 4.0 4.1 Christian F. A. Negre, Uriel N. Morzan, Heidi P. Hendrickson, Rhitankar Pal, George P. Lisi, J. Patrick Loria, Ivan Rivalta, Junming Ho, Victor S. Batista. (2018). "Eigenvector centrality for characterization of protein allosteric pathways". Proceedings of the National Academy of Sciences. 115 (52): E12201–E12208. doi:10.1073/pnas.1810452115. PMC 6310864. PMID 30530700.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  5. ↑ 5.0 5.1 5.2 5.3 Borgatti, Stephen P.; Everett, Martin G. (2006). "A Graph-Theoretic Perspective on Centrality". Social Networks. 28 (4): 466–484. doi:10.1016/j.socnet.2005.11.005.
  6. ↑ 6.0 6.1 Benzi, Michele; Klymko, Christine (2013). "A matrix analysis of different centrality measures". SIAM Journal on Matrix Analysis and Applications. 36 (2): 686–706. arXiv:1312.6722. doi:10.1137/130950550.
  7. ↑ Michalak, Aadithya, Szczepański, Ravindran, & Jennings
  8. ↑ Hu, Xingwei; Shapley, Lloyd (2003). "On Authority Distributions in Organizations". Games and Economic Behavior. 45: 132–170. doi:10.1016/s0899-8256(03)00130-1.
  9. ↑ Hu, Xingwei (2020). "Sorting big data by revealed preference with application to college ranking". Journal of Big Data. 7. doi:10.1186/s40537-020-00300-1.
  10. ↑ Krackhardt, David (June 1990). "Assessing the Political Landscape: Structure, Cognition, and Power in Organizations". Administrative Science Quarterly. 35 (2): 342–369. doi:10.2307/2393394. JSTOR 2393394.
  11. ↑ 11.0 11.1 11.2 11.3 Freeman, Linton C. (1979), "centrality in social networks: Conceptual clarification" (PDF), Social Networks, 1 (3): 215–239, CiteSeerX 10.1.1.227.9549, doi:10.1016/0378-8733(78)90021-7, archived from the original (PDF) on 2016-02-22, retrieved 2014-07-31
  12. ↑ 12.0 12.1 Lawyer, Glenn (2015). "Understanding the spreading power of all nodes in a network: a continuous-time perspective". Sci Rep. 5: 8665. arXiv:1405.6707. Bibcode:2015NatSR...5E8665L. doi:10.1038/srep08665. PMC 4345333. PMID 25727453.
  13. ↑ da Silva, Renato; Viana, Matheus; da F. Costa, Luciano (2012). "Predicting epidemic outbreak from individual features of the spreaders". J. Stat. Mech.: Theory Exp. 2012 (7): P07005. arXiv:1202.0024. Bibcode:2012JSMTE..07..005A. doi:10.1088/1742-5468/2012/07/p07005.
  14. ↑ Bauer, Frank; Lizier, Joseph (2012). "Identifying influential spreaders and efficiently estimating infection numbers in epidemic models: A walk counting approach". Europhys Lett. 99 (6): 68007. arXiv:1203.0502. Bibcode:2012EL.....9968007B. doi:10.1209/0295-5075/99/68007.
  15. ↑ Sikic, Mile; Lancic, Alen; Antulov-Fantulin, Nino; Stefanic, Hrvoje (2013). "Epidemic centrality -- is there an underestimated epidemic impact of network peripheral nodes?". The European Physical Journal B. 86 (10): 1–13. arXiv:1110.2558. Bibcode:2013EPJB...86..440S. doi:10.1140/epjb/e2013-31025-5.
  16. ↑ Ghoshal, G.; Barabsi, A L (2011). "Ranking stability and super-stable nodes in complex networks". Nat Commun. 2: 394. Bibcode:2011NatCo...2..394G. doi:10.1038/ncomms1396. PMID 21772265.
  17. ↑ Freeman, Linton C. "Centrality in social networks conceptual clarification." Social networks 1.3 (1979): 215–239.
  18. ↑ Alex Bavelas. Communication patterns in task-oriented groups. J. Acoust. Soc. Am, 22(6):725–730, 1950.
  19. ↑ Sabidussi, G (1966). "The centrality index of a graph". Psychometrika. 31 (4): 581–603. doi:10.1007/bf02289527. hdl:10338.dmlcz/101401. PMID 5232444.
  20. ↑ Marchiori, Massimo; Latora, Vito (2000), "Harmony in the small-world", Physica A: Statistical Mechanics and Its Applications, 285 (3–4): 539–546, arXiv:cond-mat/0008357, Bibcode:2000PhyA..285..539M, doi:10.1016/s0378-4371(00)00311-3
  21. ↑ Dekker, Anthony (2005). "Conceptual Distance in Social Network Analysis". Journal of Social Structure. 6 (3).
  22. ↑ Yannick Rochat. Closeness centrality extended to unconnected graphs: The harmonic centrality index (PDF). Applications of Social Network Analysis, ASNA 2009.
  23. ↑ Freeman, Linton (1977). "A set of measures of centrality based upon betweenness". Sociometry. 40 (1): 35–41. doi:10.2307/3033543. JSTOR 3033543.
  24. ↑ 24.0 24.1 24.2 Brandes, Ulrik (2001). "A faster algorithm for betweenness centrality" (PDF). Journal of Mathematical Sociology. 25 (2): 163–177. CiteSeerX 10.1.1.11.2024. doi:10.1080/0022250x.2001.9990249. Retrieved October 11, 2011.
  25. ↑ M. E. J. Newman. "The mathematics of networks" (PDF). Retrieved 2006-11-09. {{cite journal}}: Cite journal requires |journal= (help)
  26. ↑ 26.0 26.1 "American Mathematical Society".
  27. ↑ M. E. J. Newman. "The mathematics of networks" (PDF). Retrieved 2006-11-09. {{cite journal}}: Cite journal requires |journal= (help)
  28. ↑ Katz, L. 1953. A New Status Index Derived from Sociometric Index. Psychometrika, 39–43.
  29. ↑ Bonacich, P (1991). "Simultaneous group and individual centralities". Social Networks. 13 (2): 155–168. doi:10.1016/0378-8733(91)90018-o.
  30. ↑ How does Google rank webpages?20Q: About Networked Life
  31. ↑ Piraveenan, M.; Prokopenko, M.; Hossain, L. (2013). "Percolation Centrality: Quantifying Graph-Theoretic Impact of Nodes during Percolation in Networks". PLOS One. 8 (1): e53095. Bibcode:2013PLoSO...853095P. doi:10.1371/journal.pone.0053095. PMC 3551907. PMID 23349699.
  32. ↑ Faghani, Mohamamd Reza (2013). "A Study of XSS Worm Propagation and Detection Mechanisms in Online Social Networks". IEEE Transactions on Information Forensics and Security. 8 (11): 1815–1826. doi:10.1109/TIFS.2013.2280884.
  33. ↑ Alvarez-Socorro, A. J.; Herrera-Almarza, G. C.; González-Díaz, L. A. (2015-11-25). "Eigencentrality based on dissimilarity measures reveals central nodes in complex networks". Scientific Reports. 5: 17095. Bibcode:2015NatSR...517095A. doi:10.1038/srep17095. PMC 4658528. PMID 26603652.
  34. ↑ Alvarez-Socorro, A.J.; Herrera-Almarza; González-Díaz, L. A. "Supplementary Information for Eigencentrality based on dissimilarity measures reveals central nodes in complex networks" (PDF). Nature Publishing Group.
  35. ↑ Hill, S.A.; Braha, D. (2010). "Dynamic Model of Time-Dependent Complex Networks". Physical Review E. 82 (4): 046105. arXiv:0901.4407. Bibcode:2010PhRvE..82d6105H. doi:10.1103/physreve.82.046105. PMID 21230343.
  36. ↑ Gross, T. and Sayama, H. (Eds.). 2009. Adaptive Networks: Theory, Models and Applications. Springer.
  37. ↑ Holme, P. and Saramäki, J. 2013. Temporal Networks. Springer.
  38. ↑ Opsahl, Tore; Agneessens, Filip; Skvoretz, John (2010). "Node centrality in weighted networks: Generalizing degree and shortest paths". Social Networks. 32 (3): 245–251. doi:10.1016/j.socnet.2010.03.006. Archived from the original on 2018-02-26. Retrieved 2010-04-23.
  39. ↑ Everett, M. G. and Borgatti, S. P. (2005). Extending centrality. In P. J. Carrington, J. Scott and S. Wasserman (Eds.), Models and methods in social network analysis (pp. 57–76). New York: Cambridge University Press.
  40. ↑ Puzis, R., Yagil, D., Elovici, Y., Braha, D. (2009).Collaborative attack on Internet users’ anonymity -{zh-cn:互联网档案馆; zh-tw:網際網路檔案館; zh-hk:互聯網檔案館;}-的存檔，存档日期2013-12-07., Internet Research 19(1)


拓展阅读

  • Koschützki, D.; Lehmann, K. A.; Peeters, L.; Richter, S.; Tenfelde-Podehl, D. and Zlotowski, O. (2005) Centrality Indices. In Brandes, U. and Erlebach, T. (Eds.) Network Analysis: Methodological Foundations, pp. 16–61, LNCS 3418, Springer-Verlag.


编者推荐

书籍推荐

《图论导论》封面
种群结构如何影响自然选择？图论对进化生物学的启发
图网络读书会

《图论导论》

Douglas B．West教授是伊利诺伊大学数学系的资深教授，长期从事图论理论和组合优化方面的研究工作，发表了100多篇论文。本书旨在介绍图论的基本概念、基本定理和算法，帮助读者理解并掌握图的结构和解决图论问题的技巧。另外，本书包含很多图论的新研究结果，并介绍了一些悬而未决的图论问题．证明与应用并举是本书的一个重要特点。


《图论及其应用》

该书籍主要介绍了图论的基本知识、相关定理等，并对于不同图，给出实际应用，如与对集有关的人员分派问题、与Hamilton图有关的旅行售货员问题等，通俗易懂。


集智文章推荐


课程推荐

图神经网络是深度学习领域的前沿热点议题，尤其是图网络（GraphNetworks）提出以来，深度学习有了实现因果推理的潜力。为了持续追踪相关领域的前沿进展，集智俱乐部联合北师大系统科学学院张江课题组，组织了以图网络为主题的线上读书会，研讨最新论文，孕育研究思路。下面从图网络的不同方面进行了讨论交流。




本条目由水流心不竞翻译，Bai审校，薄荷编辑，如有问题，欢迎在讨论页面进行讨论。


本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。

取自“https://wiki.swarma.org/index.php?title=网络中心性&oldid=25171”