复杂网络的中心性

Centrality (中心性)(译自Wiki,略有删节)Du00 声明： 供个人参考。英语以及专业水平不是一般地有限，翻译得不好随便喷，仅网络中结点的中心性度量有度中心性度量，介数中心性度量，紧密中心性度 量和2010年提出的特征微量中心性度量。1 度中心性(Degree Centrali ty)度中心性是第一个，也是最简单的。度中心性被定义为一个结点的入边数。 度通常被看作获取网络上流动内容的直接程度(比如病毒或者一些信息)。如果 网络是有向的(关系有向)，那么我们会分别定义两种度中心性(入度与出度)。对于之如友谊或建议的实际关系，我们一般将入度看作受欢迎程度、出度作为合 群性。对于有n个结点的图G: = (V, E),结点v的度中心性CD(v)为：恥)=捋对于图G,计算度中心性的复杂度在稠密邻接矩阵表示中时为 (V2),在稀 疏矩阵表示中为 (E),其中V是所有的点，E是所有的边。中心性的定义可以(从结点)扩展到图。令v *是6中度中心性最高的结点。定义X： = (Y, Z)为连接图的n个结点最大化下面的量(H)(令y *%X中度中心性最高的节点)：H =工皿 * ) - o(y )j 二 1图G的度中心性被定义为如下：lvE ll： i)Cy * ) - Cb(yj)3 = -_ h当图G有一个结点连接其它所有结点，而且其它所有结点只连接这一个中心 结点时，H最大(星形图)。在这种情况下H = (n 1)(n 2),图G的度中 心性可以化简为：y I1： Mv 治- Cb(vj)=-H2 介数中心性(Betweenness Centrality)介数(中心，边介，这个太难翻了)是结点在图中中心性的度量(同样也有 边介数)。出现在许多其它结点最短路径中的结点有更高的介数值。对于n个结点的图G： = (V, E),结点v的介数CB(v)按如下计算：对于每对结点(s, t),计算他们之间所有的最短路径；对于每对结点(s, t),通过判断(here,结点v)求出它在最短路径上的部分；对每对结点(s, t)求出的部分进行累加。或者更简洁地：其中，：Mt是S到t的最短路径数，-I ； !是从S到t的最短路径中经过结 点v的数量。它可以除以不包括结点v的结点对数量(对于有向图是(n - 1)(n - 2),对于无向图是(n - 1)(n - 2) / 2)来归一化。例：在一个有向星 形图中,中心结点(位于所有可能的最短路径中)的介数值为 (n -1)(n -2) / 2 (归一化后为1),而叶子结点(不在任何的最短路径中)介数值为0。计算图中所有结点介数和紧密中心性包括了计算图中所有结点之间的最短 距离。 修改Floyd - Warshall算法可以找出每一对结点的最短路径复杂度是 (V3)。在稀疏图中，Johnson算法效率更高，为O(V2logV + VE)。在无权图中 使用Brande的算法计算介数中心性为O(VE)。在计算图中所有结点的介数和紧密中心性时的假设为图是无向的而且允许 有重边。特别的,处理网络图时,为了保持关系简单,通常图没有环或者重边(边 代表了人或结点之间的连接)。在这种情况下,由于每条最短路径被计算两次, 使用Brande算法将使最终中心性数值减半。3 紧密中心性(Closeness Centrality)在拓扑学和相关数学邻域中,紧密度是拓扑空间中的一个基本概念。直观地, 当两个集合是任意近的时候,我们说他们是紧密的。这一概念在一个定义了空间内元素距离的度量空间内很容易定义，但是它能够推广到没有具体度量距离的拓 扑空间。在图论中，紧密度是图中一个结点的中心性度量。比其它结点更“浅”（也 就是说，有更短的测地距离）的结点有更高的紧密度。在网络分析中，紧密度倾 向于表示最小路径长度，因为这样会对更多的中心结点赋予更高的值，而且它通 常与其它度量（如，度）相联系。在网络理论中，紧密度是中心性的一种复杂度 量。它被定义为结点V到其它可达结点的平均测地距离（比如最短路径）：t :.- .n - 1其中“二是从v出发在网络中连通部分V的大小。紧密度可以看作从给定 结点传播信息到网络中其它可达结点时间长短的度量。有人将紧密度定义为这一量的倒数，但是两种方式传播信息是一样的（这里 评估速度而不是时间了）。紧密度结点v的紧密度CC（v）是到其它所有结点V的测 地距离和的倒数：紧密度可以用不同方法和算法得到，Noh and Rieger （2003）提出了 randomwalk 中心性，它是随机传播的信息从网络中其它结点到达一个（给定）结点速 度的度量random-walk版的紧密中心度。另一种紧密度度量是Stephenson and Zelen （1989）的信息中心度，与Noh and Rieger （的方法）有些相似。本质上它是以结点i为终点的路径的调和平均 长度，当i有很多短路径连接其它结点时这一长度会较小。为了度量网络的脆弱性，Dangalchev （2006）修改了紧密度的定义使得它能 运用到非连通图中，总的紧密度更容易计算：心=力J j II e - vOpsahl （2010）提出了一种对非连通网络的扩展。4 特征向量中心性(Eigenvector Centrality)特征微量中心性是网络中一个结点重要性的度量。网络中每个结点都有一个相对指数值，这个值是基于原则高指数结点的连接对一个结点的贡献度比低指数结点的贡献度高。Google的PageRank是特征向量中心度量的一个变种。4.1使用邻接矩阵来寻找特征向量中心性令x.为第i个结点的(指数)值，A.为网络的邻接矩阵。这样，当第i个结ii,j点是第j个结点的邻结点时，A = 1,或者相反，A = 0。一般来说，正如i,ji,j同随机矩阵，A的每一项可以是表示连接强度的实数。对于第i个结点，中心性指数与所有连接它的结点的指数和成比例。从而其中，M(i)是连接到i结点的结点集合，N是总结点数，入是常数。矩阵形式表示为，或者特征方程AX=入X一般地，特征向量的解存在时会有许多特征值入。但是，矩阵所有元素为正的 额外条件意味着(Perron-Frobenius t heorem)只有最大特征值能得到要求的中 心性度量。相关的特征向量中第i个分量给出了网络中第i个结点的中心度指 数。Power It era tion是求取主特征向量的特征值算法之一。