复杂网络的中心性

1/4Centrality（中心性）（译自Wiki，略有删节）[e-mail]2011.4.14声明：英语以及专业水平不是一般地有限，翻译得不好随便喷，仅供个人参考。网络中结点的中心性度量有度中心性度量，介数中心性度量，紧密中心性度量和2010年提出的特征微量中心性度量。1度中心性（DegreeCentrality）度中心性是第一个，也是最简单的。度中心性被定义为一个结点的入边数。度通常被看作获取网络上流动内容的直接程度（比如病毒或者一些信息）。如果网络是有向的（关系有向），那么我们会分别定义两种度中心性（入度与出度）。对于之如友谊或建议的实际关系，我们一般将入度看作受欢迎程度、出度作为合群性。对于有n个结点的图G:=(V,E)，结点v的度中心性CD(v)为：𝐶𝐷(𝑣)=𝑑𝑒𝑔(𝑣)𝑛−1对于图G，计算度中心性的复杂度在稠密邻接矩阵表示中时为Θ(V2)，在稀疏矩阵表示中为Θ(E)，其中V是所有的点，E是所有的边。中心性的定义可以（从结点）扩展到图。令v*是G中度中心性最高的结点。定义X:=(Y,Z)为连接图的n个结点最大化下面的量（H）（令y*为X中度中心性最高的节点）：𝐻=∑[𝐶𝐷(𝑦∗)−𝐶𝐷(𝑦𝑗)]|𝑌|𝑗=1图G的度中心性被定义为如下：𝐶𝐷(𝑣)=∑[𝐶𝐷(𝑦∗)−𝐶𝐷(𝑦𝑗)]|𝑌|𝑗=1𝐻当图G有一个结点连接其它所有结点，而且其它所有结点只连接这一个中心结点时，H最大（星形图）。在这种情况下H=(n−1)(n−2)，图G的度中心性可以化简为：2/4𝐶𝐷(𝐺)=∑[𝐶𝐷(𝑣∗)−𝐶𝐷(𝑣𝑗)]|𝑉|𝑗=1𝐻2介数中心性(BetweennessCentrality)介数（中心，边介，这个太难翻了）是结点在图中中心性的度量（同样也有边介数）。出现在许多其它结点最短路径中的结点有更高的介数值。对于n个结点的图G:=(V,E)，结点v的介数CB(v)按如下计算：对于每对结点(s,t)，计算他们之间所有的最短路径；对于每对结点(s,t)，通过判断(here,结点v)求出它在最短路径上的部分；对每对结点(s,t)求出的部分进行累加。或者更简洁地：𝐶𝐵(𝑣)=∑𝜎𝑠𝑡(𝑣)𝜎𝑠𝑡𝑠≠𝑣≠𝑡∈𝑉其中，𝜎𝑠𝑡是s到t的最短路径数，𝜎𝑠𝑡(𝑣)是从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紧密中心性(ClosenessCentrality)在拓扑学和相关数学邻域中，紧密度是拓扑空间中的一个基本概念。直观地，当两个集合是任意近的时候，我们说他们是紧密的。这一概念在一个定义了空间内元素距离的度量空间内很容易定义，但是它能够推广到没有具体度量距离的拓3/4扑空间。在图论中，紧密度是图中一个结点的中心性度量。比其它结点更“浅”（也就是说，有更短的测地距离）的结点有更高的紧密度。在网络分析中，紧密度倾向于表示最小路径长度，因为这样会对更多的中心结点赋予更高的值，而且它通常与其它度量（如，度）相联系。在网络理论中，紧密度是中心性的一种复杂度量。它被定义为结点v到其它可达结点的平均测地距离（比如最短路径）：∑𝑑𝐺(𝑣,𝑡)𝑡∈𝑉\𝑣𝑛−1其中𝑛≥2是从v出发在网络中连通部分V的大小。紧密度可以看作从给定结点传播信息到网络中其它可达结点时间长短的度量。有人将紧密度定义为这一量的倒数，但是两种方式传播信息是一样的（这里评估速度而不是时间了）。紧密度结点v的紧密度CC(v)是到其它所有结点V的测地距离和的倒数：𝐶𝐶=1∑𝑑𝐺(𝑣,𝑡)𝑡∈𝑉\𝑣紧密度可以用不同方法和算法得到，NohandRieger(2003)提出了random-walk中心性，它是随机传播的信息从网络中其它结点到达一个（给定）结点速度的度量——random-walk版的紧密中心度。另一种紧密度度量是StephensonandZelen(1989)的信息中心度，与NohandRieger（的方法）有些相似。本质上它是以结点i为终点的路径的调和平均长度，当i有很多短路径连接其它结点时这一长度会较小。为了度量网络的脆弱性，Dangalchev(2006)修改了紧密度的定义使得它能运用到非连通图中，总的紧密度更容易计算：𝐶𝑐(𝑣)=∑2−𝑑𝐺(𝑣,𝑡)𝑡∈𝑉\𝑣Opsahl(2010)提出了一种对非连通网络的扩展。4特征向量中心性(EigenvectorCentrality)特征微量中心性是网络中一个结点重要性的度量。网络中每个结点都有一个相对指数值，这个值是基于原则——高指数结点的连接对一个结点的贡献度比低指数结点的贡献度高。Google的PageRank是特征向量中心度量的一个变种。4/44.1使用邻接矩阵来寻找特征向量中心性令xi为第i个结点的（指数）值，Ai,j为网络的邻接矩阵。这样，当第i个结点是第j个结点的邻结点时，Ai,j=1，或者相反，Ai,j=0。一般来说，正如同随机矩阵，A的每一项可以是表示连接强度的实数。对于第i个结点，中心性指数与所有连接它的结点的指数和成比例。从而=1∑𝑗𝑗∈()=1∑,𝑗𝑗𝑗=1其中，M(i)是连接到i结点的结点集合，N是总结点数，λ是常数。矩阵形式表示为=1，或者特征方程AX=λX.一般地，特征向量的解存在时会有许多特征值λ。但是，矩阵所有元素为正的额外条件意味着（Perron–Frobeniustheorem）只有最大特征值能得到要求的中心性度量。相关的特征向量中第i个分量给出了网络中第i个结点的中心度指数。PowerIteration是求取主特征向量的特征值算法之一。