Closeness Centrality也称为紧密中心性。
Closeness Centrality的计算公式有三种:
第一种算法:
第一种算法是最先提出的,公式如下:
C ( x ) = 1 ∑ y d ( y , x ) . C(x)={frac {1}{sum _{y}d(y,x)}}. C(x)=∑yd(y,x)1.
前面的 C ( x ) C(x) C(x)代表顶点x的Closeness Centrality值。
d ( y , x ) d(y,x) d(y,x)为从y到x顶点之间的距离
这一种计算的缺点:大图的顶点计算的值比较小,因为大图,连接的顶点越多,求和部分的值越大。同理小图顶点计算的值比较大。
第二种算法:
第二种算法公式如下,N是图中顶点的数量。
C ( x ) = N ∑ y d ( y , x ) . {displaystyle C(x)={frac {N}{sum _{y}d(y,x)}}.} C(x)=∑yd(y,x)N.
第二种算法进行了规范化,不同图的顶点的Closeness Centrality值有了可比性。
前两种的缺点:
前两种算法在任意两个顶点之间都是联通的情况下有效。如果y不和x相连,则d(y,x)之间的距离是无穷大,则不论其他顶点的距离是多少, C ( x ) = 0 C(x)=0 C(x)=0。
第三种算法:
第三种算法适合图是非强联通的。
H ( x ) = ∑ y ≠ x 1 d ( y , x ) . H(x)=sum _{{yneq x}}{frac {1}{d(y,x)}}. H(x)=∑y=xd(y,x)1.
我们是采用第三种算法。
举例计算Closeness Centrality
以上图为例,图中有6个顶点,8条边。
C ( a ) C(a) C(a) = 1/1 + 1/2 + 1/2 + 1/3 + 1/3 = 2.666666
B的Closeness Centrality的值为4 d(a,b) = 1d(c,b) = 1d(d,b) = 1d(e,b) = 2d(f,b) = 2C ( a ) C(a) C(a) = 1/1 + 1/1 + 1/1 + 1/2 + 1/2 = 2
C的Closeness Centrality的值为4 d(a,c) = 2d(b,c) = 1d(d,c) = 1d(e,c) = 1d(f,c) = 2C ( a ) C(a) C(a) = 1/2 + 1/1 + 1/1 + 1/1 + 1/2 = 4
D的Closeness Centrality的值为4.5 d(a,d) = 2d(b,d) = 1d(c,d) = 1d(e,d) = 1d(f,d) = 1C ( a ) C(a) C(a) = 1/2 + 1/1 + 1/1 + 1/1 + 1/1 = 4.5
E的Closeness Centrality的值为3.8333333 d(a,e) = 3d(b,e) = 2d(c,e) = 1d(d,e) = 1d(f,e) = 1C ( a ) C(a) C(a) = 1/3 + 1/2 + 1/1 + 1/1 + 1/1 = 3.8333333
F的Closeness Centrality的值为3.3333333 d(a,f) = 3d(b,f) = 2d(c,f) = 2d(d,f) = 1d(e,f) = 1C ( a ) C(a) C(a) = 1/3 + 1/2 + 1/2 + 1/1 + 1/1 = 3.3333333