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

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

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

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

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

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

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

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