復雜網(wǎng)絡(luò)的中心性

1、Centrahty 中央性譯自Wiki,略有刪節(jié)D聲明：英語以及專業(yè)水平不是一般地有限,譯得不好隨便噴,僅供個人參考.網(wǎng)絡(luò)中結(jié)點的中央性度量有度中央性度量,介數(shù)中央性度量,緊密中央性度量和2021 年提出的特征微量中央性度量.1 度中央性Degree Centrality度中央性是第一個,也是最簡單的.度中央性被定義為一個結(jié)點的入邊數(shù).度通常 被看作獲取網(wǎng)絡(luò)上流動內(nèi)容的直接程度比方病毒或者一些信息.如果網(wǎng)絡(luò)是有向的關(guān) 系有向,那么我們會分別定義兩種度中央性入度與出度.對于之如友誼或建議的實 際關(guān)系,我們一般將入度看作受歡送程度、出度作為合群性.對于有n個結(jié)點的圖G: = V, E,結(jié)點v的度中

2、央性Cdv為：對于圖G,計算度中央性的復雜度在稠密鄰接矩陣表示中時為蛻V2,在稀疏矩陣表示中為6E,其中V是所有的點,E是所有的邊.中央性的定義可以從結(jié)點擴展到圖.令 ？v?*是G中度中央性最高的結(jié)點.定義 X:= Y, Z為連接圖的n個結(jié)點最大化下面的量H令？y?*為X中度中央性最高的節(jié)點：圖G的度中央性被定義為如下:當圖G有一個結(jié)點連接其它所有結(jié)點,而且其它所有結(jié)點只連接這一個中央結(jié)點時, H最大星形圖.在這種情況下H?= n? 1n? 2,圖G的度中央性可以化簡為：2 介數(shù)中央性Betweenness Centrality介數(shù)中央,邊介,這個太難翻了是結(jié)點在圖中中央性的度量同樣也有邊介數(shù)

3、 出現(xiàn)在許多其它結(jié)點最短路徑中的結(jié)點有更高的介數(shù)值.對于n個結(jié)點的圖G: = V, E,結(jié)點v?的介數(shù)CBv?按如下計算：對于每對結(jié)點s, t,計算他們之間所有的最短路徑；對于每對結(jié)點s, t,通過判斷here,結(jié)點v求出它在最短路徑上的局部；對每對結(jié)點s, t求出的局部進行累加.或者更簡潔地：其中, 是s到t的最短路徑數(shù),是從s到t的最短路徑中經(jīng)過結(jié)點v的數(shù)量.它可以除以不包括結(jié)點v的結(jié)點對數(shù)量對于有向圖是？n? 1n? 2,對于無向圖是n?1n? 2 / 2來歸一化.例：在一個有向星形圖中,中央結(jié)點位于所有可能的最短路徑 中的介數(shù)值為？n? 1n? 2 / 2?歸一化后為1,而葉子結(jié)點不在

4、任何的最短路徑中介數(shù)值 為0.計算圖中所有結(jié)點介數(shù)和緊密中央性包括了計算圖中所有結(jié)點之間的最短距離.？修改Floyd Marshall算法可以找出每一對結(jié)點的最短路徑復雜度是0丁.在稀疏圖中,Johnson算法效率更高,為OV2logV?+?VE.在無權(quán)圖中使用Brande的算法計算介數(shù)中央 性為OVE0在計算圖中所有結(jié)點的介數(shù)和緊密中央性時的假設(shè)為圖是無向的而且允許有重邊. 特別的,處理網(wǎng)絡(luò)圖時,為了保持關(guān)系簡單,通常圖沒有環(huán)或者重邊邊代表了人或結(jié) 點之間的連接.在這種情況下,由于每條最短路徑被計算兩次,使用Brande算法將使最終中央性數(shù)值減半.3 緊密中央性Closeness Centr

5、ality在拓撲學和相關(guān)數(shù)學鄰域中,緊密度是拓撲空間中的一個根本概念.直觀地,當兩 個集合是任意近的時候,我們說他們是緊密的.這一概念在一個定義了空間內(nèi)元素距離 的度量空間內(nèi)很容易定義,但是它能夠推廣到?jīng)]有具體度量距離的拓撲空間.在圖論中,緊密度是圖中一個結(jié)點的中央性度量.比其它結(jié)點更“淺也就是說,有更短的測地距離的結(jié)點有更高的緊密度.在網(wǎng)絡(luò)分析中,緊密度傾向于表示最小路 徑長度,由于這樣會對更多的中央結(jié)點賦予更高的值,而且它通常與其它度量如,度相聯(lián)系.在網(wǎng)絡(luò)理論中,緊密度是中央性的一種復雜度量.它被定義為結(jié)點v到其它可達結(jié)點的平均測地距離比方最短路徑：其中 是從v出發(fā)在網(wǎng)絡(luò)中連通局部V的大小

6、.緊密度可以看作從給定結(jié)點傳播 信息到網(wǎng)絡(luò)中其它可達結(jié)點時間長短的度量.有人將緊密度定義為這一量的倒數(shù),但是兩種方式傳播信息是一樣的這里評估速 度而不是時間了.緊密度結(jié)點v的緊密度CCv是到其它所有結(jié)點V的測地距離和的倒數(shù)：緊密度可以用不同方法和算法得到,Noh and Rieger 200巡出了 random- walk中心性,它是隨機傳播的信息從網(wǎng)絡(luò)中其它結(jié)點到達一個給定結(jié)點速度的度量一一 random-walk版的緊密中央度.另一種緊密度度量是 Stephenson and Zelen 198必信息中央度,與 Noh and Rieger 的方法有些相似.本質(zhì)上它是以結(jié)點i為終點的路徑的

7、調(diào)和平均長度,當i有很多短 路徑連接其它結(jié)點時這一長度會較小.為了度量網(wǎng)絡(luò)的脆弱性,Dangalchev 2006改了緊密度的定義使得它能運用到非連 通圖中,總的緊密度更容易計算：Opsahl 2021班出了一種對非連通網(wǎng)絡(luò)的擴展.4 特征向量中央性Eigenvector Centrality特征微量中央性是網(wǎng)絡(luò)中一個結(jié)點重要性的度量.網(wǎng)絡(luò)中每個結(jié)點都有一個相對指 數(shù)值,這個值是基于原那么一一高指數(shù)結(jié)點的連接對一個結(jié)點的奉獻度比低指數(shù)結(jié)點的貢 獻度高.Google的PageRank1特征向量中央度量的一個變種.1.1使用鄰接矩陣來尋找特征向量中央性令Xi?為第i個結(jié)點的(指數(shù))值,Ai,j為網(wǎng)絡(luò)的鄰接矩陣.這樣,當?shù)趇個結(jié)點是第j個結(jié) 點的鄰結(jié)點時,Ai,j?= 1,或者相反,A,j?=.一般來說,正如同隨機矩陣,A的每一項可 以是表示連接強度的實數(shù).對于第i個結(jié)點,中央性指數(shù)與所有連接它的結(jié)點的指數(shù)和成比例.從而其中,M是連接到i結(jié)點的結(jié)點集合,N是總結(jié)點數(shù),入是常數(shù).矩陣形式表示為-或者特征方程AX=X X一般地,特征向量的解存在時會有許多特征值尢但是,矩陣所有元素為