复杂网络的中心性

《复杂网络的中心性》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Centrality（中心性）（译自Wiki，略有删节）Du00　du00cs@gmail.com　2011.4.14声明：英语以及专业水平不是一般地有限，翻译得不好随便喷，仅供个人参考。网络中结点的中心性度量有度中心性度量，介数中心性度量，紧密中心性度量和2010年提出的特征微量中心性度量。1度中心性（DegreeCentrality）度中心性是第一个，也是最简单的。度中心性被定义为一个结点的入边数。度通常被看作获取网络上流动内容的直接程度（比如病毒或者一些信息）。如果网络是有向的（关系有向），那么我们会分别定义两种度中心性（入度与

2、出度）。对于之如友谊或建议的实际关系，我们一般将入度看作受欢迎程度、出度作为合群性。对于有n个结点的图G:=(V,E)，结点v的度中心性CD(v)为：CDv=degvn-1对于图G，计算度中心性的复杂度在稠密邻接矩阵表示中时为Θ(V2)，在稀疏矩阵表示中为Θ(E)，其中V是所有的点，E是所有的边。中心性的定义可以（从结点）扩展到图。令 v *是G中度中心性最高的结点。定义X:=(Y,Z)为连接图的n个结点最大化下面的量（H）（令 y *为X中度中心性最高的节点）：H=j=1YCDy*-CDyj图G的度中心性被定义为如下：CDv=j=1

3、YCDy*-CDyjH当图G有一个结点连接其它所有结点，而且其它所有结点只连接这一个中心结点时，H最大（星形图）。在这种情况下H =(n −1)(n −2)，图G的度中心性可以化简为：4/4CDG=j=1VCDv*-CDvjH1介数中心性(BetweennessCentrality)介数（中心，边介，这个太难翻了）是结点在图中中心性的度量（同样也有边介数）。出现在许多其它结点最短路径中的结点有更高的介数值。对于n个结点的图G:=(V,E)，结点v 的介数CB(v) 按如下计算：对于每对结点(s,t)，计算他们之间所有的最短路径；对于每

4、对结点(s,t)，通过判断(here,结点v)求出它在最短路径上的部分；对每对结点(s,t)求出的部分进行累加。或者更简洁地：CBv=s≠v≠t∈Vσstvσst其中，σst是s到t的最短路径数，σstv是从s到t的最短路径中经过结点v的数量。它可以除以不包括结点v的结点对数量（对于有向图是 (n −1)(n −2)，对于无向图是(n −1)(n −2)/2）来归一化。例：在一个有向星形图中，中心结点（位于所有可能的最短路径中）的介数值为 (n −1)(n −2)/2 （归一化后为1），而叶子结点（不在任何的最短路径中）介数值为0。计

5、算图中所有结点介数和紧密中心性包括了计算图中所有结点之间的最短距离。 修改Floyd–Warshall算法可以找出每一对结点的最短路径复杂度是Θ(V3)。在稀疏图中，Johnson算法效率更高，为O(V2logV + VE)。在无权图中使用Brande的算法计算介数中心性为O(VE)。在计算图中所有结点的介数和紧密中心性时的假设为图是无向的而且允许有重边。特别的，处理网络图时，为了保持关系简单，通常图没有环或者重边（边代表了人或结点之间的连接）。在这种情况下，由于每条最短路径被计算两次，使用Brande算法将使最终中心性数值减半。2紧

6、密中心性(ClosenessCentrality)在拓扑学和相关数学邻域中，紧密度是拓扑空间中的一个基本概念。直观地，当两个集合是任意近的时候，我们说他们是紧密的。这一概念在一个定义了空间内元素距离的度量空间内很容易定义，但是它能够推广到没有具体度量距离的拓4/4扑空间。在图论中，紧密度是图中一个结点的中心性度量。比其它结点更“浅”（也就是说，有更短的测地距离）的结点有更高的紧密度。在网络分析中，紧密度倾向于表示最小路径长度，因为这样会对更多的中心结点赋予更高的值，而且它通常与其它度量（如，度）相联系。在网络理论中，紧密度是中心性的一

7、种复杂度量。它被定义为结点v到其它可达结点的平均测地距离（比如最短路径）：t∈VvdGv,tn-1其中n≥2是从v出发在网络中连通部分V的大小。紧密度可以看作从给定结点传播信息到网络中其它可达结点时间长短的度量。有人将紧密度定义为这一量的倒数，但是两种方式传播信息是一样的（这里评估速度而不是时间了）。紧密度结点v的紧密度CC(v)是到其它所有结点V的测地距离和的倒数：CC=1t∈VvdGv,t紧密度可以用不同方法和算法得到，NohandRieger(2003)提出了random-　walk中心性，它是随机传播的信息从网络中其它结点

8、到达一个（给定）结点速度的度量——random-walk版的紧密中心度。另一种紧密度度量是StephensonandZelen(1989)的信息中心度，与NohandRieger（的方法）有些相似。本质上它是以结点i为终