更改

节点中心性 (查看源代码)

2020年5月12日 (二) 19:48的版本

添加91字节、 2020年5月12日 (二) 19:48

无编辑摘要

第30行：第30行：

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

−

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

+

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

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

第52行：第52行：

矩阵指数, 其中

−

* <math>k</math> 是步长,

+

* :<math>k</math> 是步长,

−

* <math>A_R</math>是变换后的邻接矩阵，并且

+

* :<math>A_R</math>是变换后的邻接矩阵，并且

−

* <math>\beta</math>是保证总和收敛的折扣参数。

+

* :<math>\beta</math>是保证总和收敛的折扣参数。

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

第62行：第62行：

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

−

例如，考虑阻止流感的问题。从上面的网络图像来看，我们应该接种哪些节点？基于先前描述的措施，我们希望识别在疾病传播中最重要的节点。仅基于中心性的方法（专注于节点的各个功能）可能不是一个好方法。红方框中的节点无法单独阻止疾病传播，但是将它们作为一个整体来看，我们清楚地看到，如果节点<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值计算的时间复杂性很强，因此在该领域中的大多数努力都被驱使用来实施新的算法和方法，这些算法和方法依赖于网络的特殊拓扑或问题的特殊特征。这样的方法可以导致将时间复杂度从指数减小到多项式。

+

例如，考虑阻止流感的问题。从上面的网络图像来看，我们应该接种哪些节点？基于先前描述的措施，我们希望识别在疾病传播中最重要的节点。仅基于中心性的方法（专注于节点的各个功能）可能不是一个好方法。红方框中的节点无法单独阻止疾病传播，但是将它们作为一个整体来看，我们清楚地看到，如果节点:<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值计算的时间复杂性很强，因此在该领域中的大多数努力都被驱使用来实施新的算法和方法，这些算法和方法依赖于网络的特殊拓扑或问题的特殊特征。这样的方法可以导致将时间复杂度从指数减小到多项式。

==重要局限==

第81行：第81行：

当连边与友谊或者合作相关时，指向的度中心常被解释为赶潮流，指出被解释为交际。对于有<math>|V|</math>个节点<math>|E|</math>条边的图<math>G:=(V,E)</math>，节点<math>v</math>的度中心定义为，

−

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

+

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

−

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

+

<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>G</math>的度中心如下:

−

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

===接近中心度===

第109行：第109行：

其中

−

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

+

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

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

第115行：第115行：

在一个图中（不一定是连接图），和谐中心度定义为接近中心度倒数和求和运算的拟运算

−

<math>{\displaystyle H(x)=\sum _{y\neq x}{\frac {1}{d(y,x)}}}</math>

+

:<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是图中的节点数。

+

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

第129行：第129行：

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

−

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

+

:<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}}</math>是节点s到节点t的所有最短路径之和，而

<math>{\displaystyle \sigma _{st}(v)}</math>这些路径经过v的次数。

可注意到一个节点的介数中心性与该网络图中的节点个数相关。因此，可通过除以不包含v的节点对数以将计算结果标准化，使得

−

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

+

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

−

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

+

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

−

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

+

:<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> {\mbox{normal}}(g(v))={\frac {g(v)-\min(g)}{\max(g)-\min(g)}}</math>可求解得：

−

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

+

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

−

<math>{\displaystyle \min(normal)=0}</math>

+

:<math>{\displaystyle \min(normal)=0}</math>

由公式可知，计算结果将始终是一个从较小范围到更大范围的比例，因此没有精准度的损失。

第154行：第154行：

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

−

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

+

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

−

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

+

通常来说，有许多不同的特征值:<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>x_i = \sum_{k=1}^{\inf}\sum_{j=1}^N \alpha^k (A^k)_{ji}</math>

其中

−

<math>\alpha</math>是（0,1）之间的衰减因子。

+

:<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>替代

第178行：第178行：

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>

+

其中:<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>

===渗流中心性===

第185行：第185行：

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

−

<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>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之间的值则表示部分渗透状态（例如，在一个城镇网络中，这表示城镇受感染人群的百分比）。

+

其中 :<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>]]。

第195行：第195行：

任何网络的中心化是一种对最中心的节点相对于其他中心节点如何更中心的度量。[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>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>。

+

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

==引用==

不是海绵宝宝

863

个编辑