节点中心性

2020-04-01T10:52:44Z

GravityPHY：/* Katz中心性 */

在图论和网络分析中，中心性指标可确定图中的最重要节点。其应用包括识别社交网络中最有影响力的人，互联网或城市网络中的关键基础设施节点以及疾病的超级传播者。中心性概念最早发展起源于社交网络分析中，许多用于衡量中心性的术语反映了它们的社会学渊源。<ref name="NewmanNetworks">Newman, M.E.J. 2010. ''Networks: An Introduction.'' Oxford, UK: Oxford University Press.</ref> 研究者请勿将中心性指标与节点影响度混淆，后者的作用是量化网络中每个节点的影响。

==中心度指标的定义和描述==
中心度指标用于回答“那些因素刻画重要节点”。图中节点的实值函数可以给出答案，其中函数值会根据节点的重要性给出排名。<ref name="Bonacich1987">{{cite journal |last1= Bonacich |first1= Phillip|year= 1987 |title= Power and Centrality: A Family of Measures | journal=American Journal of Sociology |volume= 92|issue= 5|pages= 1170–1182|doi=10.1086/228631 |url= }}</ref><ref name="Borgatti2005">{{cite journal |last1= Borgatti |first1= Stephen P.|year= 2005 |title= Centrality and Network Flow |journal=Social Networks |volume= 27|issue= |pages= 55–71|doi=10.1016/j.socnet.2004.11.008 |url= |citeseerx= 10.1.1.387.419}}</ref><ref name="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 E12201--E12208">{{cite paper |
author = 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.|
title = Eigenvector centrality for characterization of protein allosteric pathways|
journal = Proceedings of the National Academy of Sciences|
volume = 115|
number = 52|
pages = E12201--E12208|
year = 2018|
doi = 10.1073/pnas.1810452115|
url = https://www.pnas.org/content/115/52/E12201
}}</ref>

“重要性”一词具有多种含义，以致于产生了许多不同的“中心性”定义。目前已提出两种分类方案。可以根据网络中的流或传输类型来定义“重要性”。这样就可以根据流类型的重要性对中心性进行分类。<ref name=Borgatti2005/> 或者，“重要性”可以被认为是参与网络的密集程度。这样就可以根据衡量中心度内聚的方式对其进行分类。<ref name="Borgatti2006">{{cite journal |last1= Borgatti |first1= Stephen P.|last2= Everett |first2= Martin G.|year= 2006 |title= A Graph-Theoretic Perspective on Centrality |journal=Social Networks |volume= 28|issue= 4|pages= 466–484|doi=10.1016/j.socnet.2005.11.005 |url= }}</ref>这两种方法将中心性划分为不同的类别。进一步的结论是，适用于一个类别的中心性在应用于另一类别时通常会“出错”。<ref name=Borgatti2005/>

当通过集聚程度对中心进行分类时，很明显，大多数中心都属于一种类别。从给定节点开始计数的步数仅与如何定义路程和计数上有所不同。对该群体的限制考虑可以进行软性表征，从而将中心点放在从长度为1的步长（度中心）到无限步长（特征值中心点）的频谱上。<ref name=Bonacich1987/><ref name="Benzi2013">{{cite journal | last1=Benzi | first1=Michele | last2=Klymko| first2=Christine | year=2013 |title= A matrix analysis of different centrality measures |arxiv=1312.6722 | doi=10.1137/130950550 | volume=36 | issue=2 | journal=SIAM Journal on Matrix Analysis and Applications | pages=686–706}}</ref>大量中心度都具有这种家族关系的现象也许可以解释这些指数之间的高度相关性。

===基于网络流描述===

网络可以看作是某种事物流经路径的描述。这允许基于流的类型和由中心点编织的路径类型进行表征。流可以基于转移，其中每个不可分割的物体都从一个节点到达另一个节点，例如从交货地点到客户家的包裹递送。第二种情况是串行复制，其中复制一个项目，以便源和目标都有它。一个示例是通过八卦信息的传播，其中信息以私有方式传播，并且在过程结束时通知源节点和目标节点。最后一种情况是并行复制，将项目同时复制给几个链接，例如无线电广播可以一次向许多听众提供相同的信息。<ref name=Borgatti2005/>

类似地，可将路径类型限制为测地线（最短路径），路径（不多次访问顶点），路径（可以多次访问顶点，不对边缘进行多次遍历）或步行（顶点和路径）可以多次访问/遍历边缘）。<ref name=Borgatti2005/>

===基于路径结构描述===

可以从中心性的构建方式中得出另一种分类。这又分为两类：中心可以是径向的或中间的。径向中心点计算从给定节点开始/结束的走行。度中心和特征值中心是径向中心的粒子，它计算长度为1或长度为无穷的步数。中间中心点计数通过给定顶点的走动。典型的例子是弗里曼的中间性中心度，即通过给定顶点的最短路径的数量。<ref name=Borgatti2006/>

类似的，计数可以获取步行的数量或长度。数量是给定类型的步行总数。上一段中的三个示例属于此类。长度刻画从给定节点到图形中其余节点的距离。弗里曼的接近中心性是最有名的例子，即从给定节点到所有其他节点的总测地距离。<ref name=Borgatti2006/> 请注意，此分类与计算的步行类型（即步行，步道，路径，测地线）无关。

Borgatti和Everett提出，这种分类学提供了关于如何最好地比较中心度度量的见解。在2×2分类中，放置同一框中的中心点足够相似作合理地选择；一个人可以合理地比较哪个对给定的应用更好。但是，来自不同盒子的度量分类是不同的。相对适合度的任何评估只能在预先确定哪个类别更适用的情况下进行，从而比较变得毫无意义。

===一定范围上的半径-体积中心性===

路径结构的特征表明，广泛使用的中心度指标基本都是“由半径推体积”式的测量。这些径向度量解释了一种观点，即顶点的中心性就是其关联顶点的中心性的函数。中心性在如何定义关联方面将自身与其他测度方法区别开来。

Bonacich证明，如果按照步行来定义关联，则可以根据所考虑的步行时间来定义一系列中心性。<ref name="Bonacich1987"/>度中心点计算长度为1的步长，而特征值中心点计算长度为无穷大。关联的替代定义也是合理的。 Alpha中心性允许节点具有外部影响力。 Estrada的子图中心性仅建议计算闭合路径（三角形，正方形等）。

此类度量的核心是，图形邻接矩阵的幂给出了这个幂的长度游程数。类似地，矩阵指数也与给定长度的步数密切相关。邻接矩阵的初始转换允许对计数的步行类型进行不同的定义。任何一种方法，

:<math>\sum_{k=0}^\infty A_{R}^{k} \beta^k </math>

对于矩阵的幂或者

:<math>\sum_{k=0}^\infty \frac{(A_R \beta)^k}{k!}</math>

矩阵指数, 其中

* <math>k</math> 是步长,
* <math>A_R</math>是变换后的邻接矩阵，并且
* <math>\beta</math>是保证总和收敛的折扣参数。

Bonacich的度量系列不会转换邻接矩阵。 Alpha中心性用其解析物替换了邻接矩阵。子图的中心性用其迹替换邻接矩阵。令人吃惊的结论是，不管邻接矩阵的初始转换如何，所有这些方法都具有共同的限制行为。当接近零时，指标数收敛到度中心。随着接近其最大值，指标数收敛到特征值中心。

===博弈理论的中心性===

大多数上述标准度量的共同特征是，它们仅通过关注节点自身扮演的角色来评估节点的重要性。但是，在许多应用中，这种方法是不够的，因为如果成组地考虑节点的功能，可能会产生协同作用。

例如，考虑阻止流感的问题。从上面的网络图像来看，我们应该接种哪些节点？基于先前描述的措施，我们希望识别在疾病传播中最重要的节点。仅基于中心性的方法（专注于节点的各个功能）可能不是一个好方法。红方框中的节点无法单独阻止疾病传播，但是将它们作为一个整体来看，我们清楚地看到，如果节点<math>v_ {1}</math>， <math>v_{4}</math>和<math> v_ {5}</math>。博弈论中心试图使用博弈论中的工具来指导所描述的问题和几率。文献<ref>Michalak, Aadithya, Szczepański, Ravindran, & Jennings https://arxiv.org/pdf/1402.0567.pdf</ref>中提出的方法使用Shapley值。由于Shapley值计算的时间复杂性很强，因此在该领域中的大多数努力都被驱使用来实施新的算法和方法，这些算法和方法依赖于网络的特殊拓扑或问题的特殊特征。这样的方法可以导致将时间复杂度从指数减小到多项式。

==重要局限==
中心指数有两个重要的局限性，一个是明显的，另一个是隐含的。明显的局限性是，一种应用而言的最佳中心性通常对于另一应用不是最佳的。确实，如果不是这样，我们将不需要那么多不同的中心。 Krackhardt风筝图提供了这种现象的说明，针对该现象，三个不同的中心性概念给出了最中心顶点的三个不同选择。

更为隐含的限制是节点中心性与节点的相对重要性这一普遍存在的谬误。经过明确设计，中心度指标可以产生等级，从而可以指示最重要的节点。<ref name=Bonacich1987/><ref name=Borgatti2005/> 他们在刚刚提到的限制结果很好。通常，它们并不是为了衡量节点的影响而设计的。最近，网络物理学家已经开始发展节点影响度量来解决此问题。

有两重错误。首先，排名仅按重要性对节点进行排序，它无法量化排名不同级别的节点之间的重要性差异。可以通过将Freeman集中化应用于所讨论的集中度度量来缓解这种问题，该集中度度量取决于节点的集中化分数的差异，从而为节点的重要性提供一些信息。此外，通过Freeman集中化，人们可以通过比较最高集中度分数来比较多个网络。<ref name="Freeman1979"/> 但是，这种方法在实践中很少见。

其次，正确标识给定网络应用中最重要节点的功能不一定会推广到其余节点。对于其他大多数网络节点，排名可能毫无意义。<ref name="Lawyer2015" /><ref name="daSilva2012">{{cite journal | last1=da Silva|first1=Renato |last2=Viana|first2=Matheus|last3=da F. Costa |first3=Luciano| title=Predicting epidemic outbreak from individual features of the spreaders| journal=J. Stat. Mech.: Theory Exp. | year=2012|volume=2012|pages=P07005|number=07 | doi=10.1088/1742-5468/2012/07/p07005|arxiv=1202.0024|bibcode=2012JSMTE..07..005A}}</ref><ref name="Bauer2012">{{cite journal | last1=Bauer|first1=Frank | last2=Lizier|first2=Joseph|title=Identifying influential spreaders and efficiently estimating infection numbers in epidemic models: A walk counting approach| journal=Europhys Lett | year=2012| volume=99| pages=68007|number=6 | doi=10.1209/0295-5075/99/68007|arxiv=1203.0502|bibcode=2012EL.....9968007B}}</ref><ref name="Sikic2013">{{ cite journal| last1= Sikic| first1=Mile|last2=Lancic|first2=Alen|last3=Antulov-Fantulin|first3=Nino|last4=Stefanic|first4=Hrvoje| title = Epidemic centrality -- is there an underestimated epidemic impact of network peripheral nodes? |journal = The European Physical Journal B |volume=86 |number=10 |pages=1–13 |year=2013 | doi=10.1140/epjb/e2013-31025-5|arxiv=1110.2558}}</ref> 例如，这解释了为什么仅前几个Google图片搜索结果顺序合理。 Pagerank是一种高度不稳定的度量，显示在对Jump参数进行较小调整后频繁发生的排名反转。

虽然中心性指标无法推广到网络的其余部分，乍一看似乎是反直觉的，但它直接来自上述定义。复杂的网络具有异构拓扑。在某种程度上，最佳度量取决于最重要节点的网络结构，对于此类节点而言，它的最优度量对于网络的其余部分而言并非最佳。<ref name="Lawyer2015">{{cite journal |last1= Lawyer |first1= Glenn |year= 2015 |title= Understanding the spreading power of all nodes in a network: a continuous-time perspective |journal=Sci Rep |volume=5|pages=8665|doi=10.1038/srep08665 |pmid=25727453 |pmc=4345333|arxiv=1405.6707|bibcode=2015NatSR...5E8665L}}</ref>

===度中心性===

历史上第一个概念上简单的中心性定义是点度中心性，定义为与节点直接相连的连边（例如，一个节点有的边的数目）。度可以理解为节点接触到在任何在网络中传播的事物（比如病毒或者信息）的可能性。在有向图中（连边具有方向性），我们经常定义两种不同的度中心测量：指向和指出。相应的，指向的定义为方向指向节点的连边数，指出的定义为节点指出方向的连边数。
当连边与友谊或者合作相关时，指向的度中心常被解释为赶潮流，指出被解释为交际。对于有<math>|V|</math>个节点<math>|E|</math>条边的图<math>G:=(V,E)</math>，节点<math>v</math>的度中心定义为，

<math>{\displaystyle C_{D(v)}= \deg(v)}</math>

计算图中所有节点的度中心，在密邻接矩阵表象中需要 [[big theta|<math>\Theta(V^2)</math>]], 在稀疏矩阵表象中，连边需要<math>\Theta(E)</math> 。

节点层面中心性的定义可以推广到整个图上，即我们说的“图中心”。
<ref>Freeman, Linton C. "Centrality in social networks conceptual clarification." Social networks 1.3 (1979): 215–239.</ref> 另<math>v{^*}</math> 表示图 <math>G</math>中度中心最大的点。另 <math>X:=(Y,Z)</math> 为<math>|Y|</math>-与图连接使得接下来的量最大的节点(<math>y*</math> 是图<math>X</math>中心度最大的点):

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

对应的，图 <math>G</math>的度中心如下:

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

当图<math>X</math>包含一个与其他节点都相连的中心点 (星图)时 <math>H</math>的值最大, 此时

<math>H=(n-1)\cdot((n-1)-1)=n^2-3n+2.</math>

所以对于任意图 <math>{\displaystyle G:=(V,E)}</math>,

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

===接近中心度===
在一个连接图中，节点的归一化的接近中心性（或者接近）是节点与其他图中节点之间的最短路径的平均长度。因此，一个可能成为中心的节点与其他的节点连接更近。

接近被Alex Bavelas (1950) 定义为距离远的程度的倒数，<ref>Alex Bavelas. Communication patterns in task-oriented groups. ''J. Acoust. Soc. Am'', '''22'''(6):725–730, 1950.</ref><ref>{{cite journal|year=1966|title=The centrality index of a graph|url=|journal=Psychometrika|volume=31|issue=4|pages=581–603|doi=10.1007/bf02289527|pmid=5232444|last1=Sabidussi|first1=G}}</ref>即:
<math>{C(x)={\frac {1}{\sum _{y}d(y,x)}}}</math>

其中
<math>{\displaystyle d(y,x)}</math>是x和y之间的距离。但是，但提到接近中心时，人们常指的是归一化形式的，通常是上一个公式乘上1/N，N为图中的节点数。这样处理后可以使得不同大小的图的比较有意义。

在无向图中讨论节点之间指向或者指出的距离是无关紧要的，因为这会导致有向图中不一样的结果（例如，一个网站的指出链接的接近中心性很高，但是指向外部链接的接近中心很低）。
====和谐中心度====
在一个图中（不一定是连接图），和谐中心度定义为接近中心度倒数和求和运算的拟运算

<math>{\displaystyle H(x)=\sum _{y\neq x}{\frac {1}{d(y,x)}}}</math>
其中
<math>{\displaystyle 1/d(y,x)=0}</math>如果没有路径从y到x。和谐中心度可以通过除以N-1归一化，其中N是图中的节点数。

和谐中心度是Marchiori 和 Latora (2000)<ref name="marchiorilatora2000">{{citation| journal = Physica A: Statistical Mechanics and its Applications | last1 = Marchiori | first1 = Massimo | last2 = Latora | first2 = Vito | year = 2000 | volume = 285 | issue = 3–4 | pages = 539–546 | title = Harmony in the small-world | doi=10.1016/s0378-4371(00)00311-3| arxiv = cond-mat/0008357 | bibcode = 2000PhyA..285..539M }}</ref>提出的，随后 Dekker (2005)取名为“价值中心度” （"valued centrality"<ref>{{cite journal|first1=Anthony|last1=Dekker|title=Conceptual Distance in Social Network Analysis|journal=Journal of Social Structure|volume=6|issue=3|year=2005|url=http://www.cmu.edu/joss/content/articles/volume6/dekker/index.html}}</ref>）， Rochat (2009)也提出过类似的概念.<ref>{{cite conference | author = Yannick Rochat | title = Closeness centrality extended to unconnected graphs: The harmonic centrality index | conference = Applications of Social Network Analysis, ASNA 2009 | url = http://infoscience.epfl.ch/record/200525/files/%5bEN%5dASNA09.pdf }}</ref>

===介数中心性===
在图论中，介数中心性 Betweenness Centrality是基于最短路径针对网络图中心性的衡量标准之一。针对全连接网络图，其中任意两个节点均至少存在一个最短路径，在无权重网络图中该最短路径是路径包含边的数量求和，加权网络图中该最短路径则是路径包含边的权重求和。每个节点的介数中心性即为这些最短路径穿过该节点的次数。

介数中心性在网络理论中有广泛的应用：它代表了某节点与其他节点之间的互动程度。例如，在通信网络中，一个有更高介数中心性的节点在网络中有更强的控制能力，因为更多的信息传递时将通过该节点。介数中心性被用作为对中心性的一种常见测量方式:[1] 它适用于解决网络理论中的许多问题，包括与社会网络、生物、运输和科学合作等方面相关的问题。
虽然早期的研究人员曾直观地描述了介数的中心性，但Freeman在1977年给了第一个介数中心性的正式定义。

节点v的介数中心性可表达为以下公式：

<math>{\displaystyle g(v)=\sum _{s\neq v\neq t}{\frac {\sigma _{st}(v)}{\sigma _{st}}}}</math>

<math>{\displaystyle \sigma _{st}}</math>是节点s到节点t的所有最短路径之和，而

<math>{\displaystyle \sigma _{st}(v)}</math>这些路径经过v的次数。
可注意到一个节点的介数中心性与该网络图中的节点个数相关。因此，可通过除以不包含v的节点对数以将计算结果标准化，使得

<math>{\displaystyle g\in [0,1]}</math>。其中有向图需除以

<math>{\displaystyle (N-1)(N-2)}</math> ，而无向图需除以

<math>{\displaystyle (N-1)(N-2)/2}</math>，其中 N是网络图中节点数量的集合。该比例代表的是最高可能计算值，即某节点与其他所有节点都通过单一的最短路径相连接，不过以上情况通常不会发生。标准化的过程并不会使计算的精准度受到影响。

<math> {\mbox{normal}}(g(v))={\frac {g(v)-\min(g)}{\max(g)-\min(g)}}</math>可求解得：

<math>{\displaystyle \max(normal)=1}</math>

<math>{\displaystyle \min(normal)=0}</math>
由公式可知，计算结果将始终是一个从较小范围到更大范围的比例，因此没有精准度的损失。

===特征向量中心性===
在图论中，特征向量中心性 eigenvector centrality是测量节点对网络影响的一种方式。针对连接数相同的节点，相邻节点分数更高的节点会比相邻节点分数更低的节点分数高，依据此原则给所有节点分配对应的分数。特征向量得分较高意味着该节点与许多自身得分较高的节点相连接。<ref>{{Cite journal|title=The mathematics of networks|url=http://www-personal.umich.edu/~mejn/papers/palgrave.pdf|last=M. E. J. Newman|accessdate=2006-11-09|format=PDF}}</ref><ref>{{Cite journal|title=Eigenvector centrality for characterization of protein allosteric pathways|url=https://www.pnas.org/content/115/52/E12201|last=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.|journal=Proceedings of the National Academy of Sciences|doi=10.1073/pnas.1810452115|year=2018|volume=115|pages=E12201--E12208}}
</ref>
谷歌的PageRank和Katz中心性是特征向量中心性的变形。<ref name="ams">{{Cite web|url=http://www.ams.org/samplings/feature-column/fcarc-pagerank|title=How Google Finds Your Needle in the Web's Haystack|author=David Austin|publisher=AMS}}</ref>
==== 利用邻接矩阵求特征向量中心性 ====
给定一个节点集合为<math>|V|</math>的图<math>G=(V,E)</math>，定义其[[邻接矩阵]]为<math>A = (a_{v,t})</math>，当<math>v</math>与<math>t</math>相连时<math>a_{v,t} = 1</math>，否则<math>a_{v,t} = 0</math>。则节点<math>v</math>中心性<math>x</math>的分数其求解公式为：

<math>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>M(v)</math>是节点<math>v</math>的相邻节点集合，<math>\lambda</math>是一个常数。经过一系列变形，该公式可变换为如下所示的[[特征向量]]方程：

<math>\mathbf{Ax} = \lambda \mathbf{x}</math>

通常来说，有许多不同的特征值<math>\lambda</math>能使得一个特征方程有非零解存在。然而，考虑到特征向量中的所有项均为非负值，根据[[佩伦-弗罗贝尼乌斯定理]]，只有特征值最大时才能测量出想要的中心性。然后通过计算网络中的节点<math>v</math> 其特征向量的相关分量<math>v^\text{th}</math>便能得出其对应的中心性的分数。特征向量的定义只有一个公因子，因此各节点中心性的比例可以很好确定。为了确定一个绝对分数，必须将其中一个特征值标准化，例如所有节点评分之和为1或者节点数 ''n''。[[冪次迭代|幂次迭代]]是许多特征值算法中的一种，该算法可以用来寻找这种主导特征向量。此外，以上方法可以推广，使得矩阵''A''中每个元素可以是表示连接强度的实数，例如[[随机矩阵]]。

===Katz中心性===
Katz 中心性<ref>Katz, L. 1953. A New Status Index Derived from Sociometric Index. Psychometrika, 39–43.</ref>是广义的度中心性。度中心性测量紧邻的数量，Katz 中心性测量可以被路径连接的节点数量，同时连接距离远的节点的影响减弱。数学上，它的定义为，

<math>x_i = \sum_{k=1}^{\inf}\sum_{j=1}^N \alpha^k (A^k)_{ji}</math>
其中
<math>\alpha</math>是（0,1）之间的衰减因子。
Katz 中心性可以看作是特征向量中心性的变形。 Katz 中心性的另外一种形式是<math>{ x_{i}=\alpha \sum _{j=1}^{N}a_{ij}(x_{j} +1)}</math>。
对比特征向量中心性<math>x_{j}</math>被<math>{ x_{j}+1}</math>替代

由下文信息可证明<ref>{{cite journal | last1 = Bonacich | first1 = P | year = 1991 | title = Simultaneous group and individual centralities | url = | journal = Social Networks | volume = 13 | issue = 2| pages = 155–168 | doi=10.1016/0378-8733(91)90018-o}}</ref>，当<math>\alpha</math>接近<math>{\displaystyle {\tfrac {1}{\lambda }}}</math>时，主特征向量（邻接矩阵A最大的特征值）是Katz 中心性的极限

===PageRank中心性===

PageRank 满足下面的公式<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>，j是与节点相邻节点的数目(或者有向图中向外链接的数量)。相比于特征向量中心性和Katz 中心性，一个主要的不同之处是标度因子L(j).。另一个不同是PageRank和特征向量中心性是， PageRank向量是特征向量的左边 (注意<math>a_{ji}</math>下标可以轮换)。<ref>[http://scenic.princeton.edu/network20q/lectures/Q3_notes.pdf How does Google rank webpages?] {{webarchive | url= https://web.archive.org/web/20120131083328/http://scenic.princeton.edu/network20q/lectures/Q3_notes.pdf |date=January 31, 2012 }} 20Q: About Networked Life</ref>

===渗流中心性===
渗流中心性是加权介数中心性的一种特殊情况，它在计算其权重时考虑了每条最短路径的源节点与目标节点的“状态”。在复杂网络中，许多情景都会发生“感染”并进行渗流。例如，众所周知，在接触网络中细菌或病毒的感染可以在人群的[[社会网络]]中传播。也可以将疾病的传播抽象化，认为一个城镇或人群聚集地是由公路、铁路或航空的连接而构成的网络。[[计算机病毒]]可能通过[[计算机网络]]传播。关于商业报价和交易的传闻或新闻也可以经由人群的社交网络传播。在所有这些情景下，一个“感染”可在复杂网络中通过连接传播，并伴随着节点“状态”的改变，如受到感染或感染后恢复到原状态。例如，在一个流行病的情景下，个体在感染传播时会将状态由“易感染”变为“已感染”。在上述例子中，各个节点在传播时可能的状态可以是二元的（已受到/未受到感染）、离散的（易感染/已感染/已恢复）乃至连续的（如城镇中受感染者的比例）。在所有这些情景中，常见的特征是传染病的传播使网络中节点状态发生变化。以上这些有关渗流中心性(PC)的概念由Piraveenan et al.提出，这对具体地测量节点在网络渗透中的重要性很有帮助。<ref name="piraveenan2013">{{Cite journal|title=Percolation Centrality: Quantifying Graph-Theoretic Impact of Nodes during Percolation in Networks|last=Piraveenan|first=Mahendra|journal=PLOS ONE|issue=1|doi=10.1371/journal.pone.0053095|year=2013|volume=8|pages=e53095|bibcode=2013PLoSO...853095P|pmc=3551907|pmid=23349699}}</ref>

渗流中心性的定义是：给定一个节点，在给定的时间内“渗透路径”通过该节点的比例。“渗透路径”指的一对节点之间的最短路径，其中源节点产生渗透效果(例如传播感染)，目标节点可以是处于已渗透、未渗透或部分渗透的状态。

<math>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>/sigma_{sr}</math> 是从节点<math>s</math>到节点 <math>r</math>最短路径数之和，<math>\sigma_{sr}(v)</math>这些路径中通过 <math>v</math>的次数。节点<math>i</math>在时间 <math>t</math>的渗流状态由<math>{x^t}_i</math>决定，其中有两个临界值，<math>{x^t}_i=0</math>时表示在时间<math>t</math>的时候没有渗透状态，<math>{x^t}_i=1</math>时表示在时间 <math>t</math>的时候为完全渗流状态。0到1之间的值则表示部分渗透状态（例如，在一个城镇网络中，这表示城镇受感染人群的百分比）。

渗流路径的权重取决于源节点的渗流水平，如果源节点的渗流水平越高，那么来自该节点的路径影响力更大。因此在源节点为高渗透作用节点的最短路径上的节点更有可能受到渗流影响。渗流中心性的定义还可以扩展到也包括目标节点的权重。渗流中心性的计算可采用Brandes快速算法有效实现，其[[时间复杂度]]为[[大O符号|<math> O(NM)</math>]]。如果计算需要考虑目标节点的权重，最坏情况的时间复杂度为 [[大O符号|<math>O(N^3)</math>]]。

==Freeman中心化==

任何网络的中心化是一种对最中心的节点相对于其他中心节点如何更中心的度量。[9] 中心化测量即:（a）计算所有节点与最中心节点的中心性之差的和;(b)将此和除以相同网络上理论情况下的最大值。<ref name="Freeman1979">{{citation | journal = Social Networks | last1 = Freeman | first1 = Linton C. | year = 1979 | volume = 1 | issue = 3 | pages = 215–239 | title = centrality in social networks: Conceptual clarification | url = http://leonidzhukov.ru/hse/2013/socialnetworks/papers/freeman79-centrality.pdf | doi = 10.1016/0378-8733(78)90021-7 | citeseerx = 10.1.1.227.9549 | access-date = 2014-07-31 | archive-url = https://web.archive.org/web/20160222033108/http://leonidzhukov.ru/hse/2013/socialnetworks/papers/freeman79-centrality.pdf | archive-date = 2016-02-22 | url-status = dead }}</ref>因此，每一个中心性测量会有它自己的中心化度量。严格定义为, 如果

<math>C_x(p_i)</math> 是点i的某种中心性测量，如果<math>C_x(p_i)</math>是这种测量在这个网络上的最大值，同时如果：

<math>\max \sum _{{i=1}}^{{N}}C_{x}(p_{*})-C_{x}(p_{i})</math>
是所有点的中心性之差的和，任何有相同节点的图的<math>C_{x} </math>，那么这个网络的中心化为:

<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>。

==引用==
<references/>

'''''本中文词条由[[Gravity PHY]]用户参与编译，刘佩佩用户审校，欢迎在讨论页面留言'''''。

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

集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织 - 用户贡献 [zh-cn]

节点中心性