1、Centrality（中心性）（譯自 Wiki ，略有刪節）D聲明：英語以及專業水平不是一般地有限，翻譯得不好隨便噴，僅供個人參考。網絡中結點的中心性度量有度中心性度量， 介數中心性度量，緊密中心性度量和 2010 年提出的特征微量中心性度量。1度中心性（ Degree Centrality）度中心性是第一個，也是最簡單的。度中心性被定義為一個結點的入邊數。度通常被看作獲取網絡上流動內容的直接程度 （比如病毒或者一些信息） 。如果網絡是有向的 （關系有向），那么我們會分別定義兩種度中心性（入度與出度） 。對于之如友誼或建議的實際關系，我們一般將入度看作受歡迎程度、出度作為合群性。對于有 n 個

2、結點的圖 G: = ( V,E) ，結點 v 的度中心性 CD(v) 為：?( ?)?(?) =? -1對于圖 G，計算度中心性的復雜度在稠密鄰接矩陣表示中時為 (V 2) ，在稀疏矩陣表示中為 (E) ，其中 V 是所有的點， E 是所有的邊。中心性的定義可以 （從結點） 擴展到圖。 令?v?* 是 G中度中心性最高的結點。 定義 X: = ( Y, Z) 為連接圖的 n 個結點最大化下面的量（ H）（令 ?y?* 為 X 中度中心性最高的節點）：|?|? = ?(? ?) -?( ?)?= 1圖 G的度中心性被定義為如下：|?=| 1 ?( ? ?) - ?( ?)?( ?) =?當圖 G

3、有一個結點連接其它所有結點， 而且其它所有結點只連接這一個中心結點時，H 最大（星形圖）。在這種情況下 H?= ( n? 1)( n? 2) ，圖 G的度中心性可以化簡為：|?=| 1 ?( ? ?) - ?( ?)?( ?) =?2介數中心性 (Betweenness Centrality)介數（中心，邊介，這個太難翻了）是結點在圖中中心性的度量 （同樣也有邊介數）。出現在許多其它結點最短路徑中的結點有更高的介數值。對于 n 個結點的圖: = (,) ，結點v介數C()GVE?的v?按如下計算：B對于每對結點 (s, t)，計算他們之間所有的最短路徑；對于每對結點 (s, t)，通過判斷 (

4、 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。計算圖中所有結點介數和緊密中心性包括了計算圖中所有結點

5、之間的最短距離。?修改 Floyd Warshall 算法可以找出每一對結點的最短路徑復雜度是 (V3) 。在稀疏圖中， Johnson 算法效率更高，為 O( V2log V?+?VE) 。在無權圖中使用 Brande 的算法計算介數中心性為 O( VE) 。在計算圖中所有結點的介數和緊密中心性時的假設為圖是無向的而且允許有重邊。特別的，處理網絡圖時，為了保持關系簡單，通常圖沒有環或者重邊（邊代表了人或結點之間的連接）。在這種情況下，由于每條最短路徑被計算兩次，使用 Brande 算法將使最終中心性數值減半。3緊密中心性 (Closeness Centrality)在拓撲學和相關數學鄰域中，

6、緊密度是拓撲空間中的一個基本概念。直觀地，當兩個集合是任意近的時候，我們說他們是緊密的。這一概念在一個定義了空間內元素距離的度量空間內很容易定義，但是它能夠推廣到沒有具體度量距離的拓撲空間。在圖論中，緊密度是圖中一個結點的中心性度量。比其它結點更“淺” （也就是說，有更短的測地距離）的結點有更高的緊密度。在網絡分析中，緊密度傾向于表示最小路徑長度，因為這樣會對更多的中心結點賦予更高的值，而且它通常與其它度量 （如，度）相聯系。在網絡理論中，緊密度是中心性的一種復雜度量。它被定義為結點v 到其它可達結點的平均測地距離（比如最短路徑） ：? ?(?, ?)? -1其中? 是從 v 出發在網絡中連通

7、部分V 的大小。緊密度可以看作從給定結點傳2播信息到網絡中其它可達結點時間長短的度量。有人將緊密度定義為這一量的倒數，但是兩種方式傳播信息是一樣的（這里評估速度而不是時間了）。緊密度結點 v 的緊密度 CC( v) 是到其它所有結點V的測地距離和的倒數：? =1? ? ?( ?,?)緊密度可以用不同方法和算法得到，Noh and Rieger (2003)提出了 random-walk中心性，它是隨機傳播的信息從網絡中其它結點到達一個（給定）結點速度的度量random-walk 版的緊密中心度。另一種緊密度度量是Stephenson and Zelen (1989) 的信息中心度，與 Noh

8、and Rieger（的方法）有些相似。本質上它是以結點i 為終點的路徑的調和平均長度，當i 有很多短路徑連接其它結點時這一長度會較小。為了度量網絡的脆弱性， Dangalchev (2006) 修改了緊密度的定義使得它能運用到非連通圖中，總的緊密度更容易計算：?( ?) =2- ?(?,?)? ?Opsahl (2010) 提出了一種對非連通網絡的擴展。4特征向量中心性 (Eigenvector Centrality)特征微量中心性是網絡中一個結點重要性的度量。網絡中每個結點都有一個相對指數值，這個值是基于原則高指數結點的連接對一個結點的貢獻度比低指數結點的貢獻度高。 Google 的 Pa

9、geRank是特征向量中心度量的一個變種。1.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.一般地，特征向量的解存