社交網(wǎng)絡(luò)中節(jié)點(diǎn)重要性分析

摘要文章簡(jiǎn)要介紹分析了幾種測(cè)量節(jié)點(diǎn)重要性的主要方法，考慮社交網(wǎng)絡(luò)的節(jié)點(diǎn)重要性之間存在相互影響，使用多種指標(biāo)測(cè)量節(jié)點(diǎn)的重要性更符合實(shí)際需要。

關(guān)鍵詞復(fù)雜網(wǎng)絡(luò)；社交網(wǎng)絡(luò)；節(jié)點(diǎn)重要性；節(jié)點(diǎn)

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1671-7597（2014）12-0135-01

復(fù)雜網(wǎng)絡(luò)理論被普遍應(yīng)用于多種領(lǐng)域，例如Internet，社會(huì)網(wǎng)絡(luò)，電力系統(tǒng)，生物網(wǎng)絡(luò)等。

社交網(wǎng)絡(luò)是指人們通過(guò)血緣，友誼等聯(lián)系建立起來(lái)的一種網(wǎng)絡(luò)結(jié)構(gòu)。社交網(wǎng)絡(luò)的小世界特性表現(xiàn)為，網(wǎng)絡(luò)中大多數(shù)的節(jié)點(diǎn)彼此并無(wú)直接聯(lián)系，但絕大多數(shù)節(jié)點(diǎn)之間經(jīng)由少數(shù)其他節(jié)點(diǎn)就可建立聯(lián)系。社交網(wǎng)絡(luò)是一種無(wú)尺度網(wǎng)絡(luò)，主要表現(xiàn)在網(wǎng)絡(luò)中的大部分節(jié)點(diǎn)只有少數(shù)鄰居節(jié)點(diǎn)，只有極少數(shù)的節(jié)點(diǎn)有很多鄰居節(jié)點(diǎn)。而且新加入網(wǎng)絡(luò)的節(jié)點(diǎn)傾向于與那些具有較多鄰居節(jié)點(diǎn)的節(jié)點(diǎn)連接，這反映了實(shí)際社會(huì)交往中人們的從眾行為。傳統(tǒng)的復(fù)雜網(wǎng)絡(luò)分析方法也可以應(yīng)用于社交網(wǎng)絡(luò)。

1節(jié)點(diǎn)重要性評(píng)價(jià)方法

1.1 度（Degree）

節(jié)點(diǎn)的度，即此節(jié)點(diǎn)在網(wǎng)絡(luò)中的與其相連接鄰居節(jié)點(diǎn)的數(shù)目。但是，度具有局限性，不能反映節(jié)點(diǎn)在全局范圍內(nèi)的影響。

1.2 介數(shù)（Betweenness）

介數(shù)，定義為途徑某個(gè)節(jié)點(diǎn)的最短路徑的數(shù)目。

介數(shù)更多的反應(yīng)節(jié)點(diǎn)在網(wǎng)絡(luò)中拓?fù)湮恢玫闹匾潭?。但是，該方法只考慮到最短路徑，而忽略了其他通路。因此，該度量方法不一定適用于所有網(wǎng)絡(luò)類型。

1.3 接近度（Closeness）

接近度，表示為某節(jié)點(diǎn)到網(wǎng)絡(luò)中所有其他節(jié)點(diǎn)的距離的倒數(shù)。

節(jié)點(diǎn)的接近度，可以比較好的反應(yīng)節(jié)點(diǎn)是否處于網(wǎng)絡(luò)拓?fù)涞闹行摹?/p>

1.4 特征向量（Eigenvector）

特征向量的基本思想是：某個(gè)節(jié)點(diǎn)的重要程度與這個(gè)節(jié)點(diǎn)的度和其鄰居節(jié)點(diǎn)的重要程度都有關(guān)。

2實(shí)例與分析

選擇扎克的空手道俱樂(lè)部（W. W. Zachary, An information flow model for conflict and fission in small groups, Journal of Anthropological Research 33, 452-473 (1977)）作為實(shí)例進(jìn)行分析，這是20世紀(jì)70年代美國(guó)大學(xué)的空手道俱樂(lè)部的34名成員之間的友誼構(gòu)成的社會(huì)網(wǎng)絡(luò)。

下面為節(jié)點(diǎn)重要性分析結(jié)果：

圖1為使用度數(shù)測(cè)出的重要節(jié)點(diǎn)，從圖中可以看出這幾個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)較多，是團(tuán)體范圍內(nèi)居于相對(duì)重要地位，在團(tuán)體內(nèi)部具有較高的影響力。

圖1 使用DC方法發(fā)掘的重要節(jié)點(diǎn) 圖2 使用BC方法發(fā)掘的重要節(jié)點(diǎn)

圖3 使用CC方法發(fā)掘的重要節(jié)點(diǎn) 圖4 使用EC方法發(fā)掘的重要節(jié)點(diǎn)

在這個(gè)網(wǎng)絡(luò)中使用介數(shù)和接近度所測(cè)出的重要節(jié)點(diǎn)是非常接近的，五個(gè)節(jié)點(diǎn)的重要度只是順序略有不同，這是因?yàn)樵摼W(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)具有鮮明的特性。而接近度與介數(shù)，都是依賴于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，反應(yīng)節(jié)點(diǎn)在網(wǎng)絡(luò)中拓?fù)湮恢玫闹匾?。測(cè)出的五個(gè)節(jié)點(diǎn)中，1號(hào)、33號(hào)、34號(hào)都是團(tuán)體內(nèi)部的中心，而1號(hào)、3號(hào)和32號(hào)是兩個(gè)團(tuán)體之間聯(lián)系的紐帶，所以，使用兩種方法測(cè)量1號(hào)都是最重要的節(jié)點(diǎn)。

從圖4可以看出EC方法不適用于此網(wǎng)絡(luò)，發(fā)掘出的重要節(jié)點(diǎn)位于網(wǎng)絡(luò)的邊緣，雖然它們的鄰居很重要，但是本身對(duì)于整個(gè)網(wǎng)絡(luò)的貢獻(xiàn)很小，不會(huì)影響全局。

分別使用八種指標(biāo)找出最重要的5個(gè)節(jié)點(diǎn)，再按照每個(gè)節(jié)點(diǎn)的出現(xiàn)頻率對(duì)所得重要節(jié)點(diǎn)進(jìn)行排序。得出的頻率最高的5個(gè)節(jié)點(diǎn)為1，2，3，33，34。所得結(jié)果圖4差異較大，而與其他幾種方法基本吻合，說(shuō)明特征向量方法不適用于這個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。

3結(jié)論

本文對(duì)在社會(huì)網(wǎng)絡(luò)環(huán)境下幾種重要的節(jié)點(diǎn)重要性發(fā)掘方法進(jìn)行了討論和分析。節(jié)點(diǎn)重要性的評(píng)估方法具有多樣性，重要性的衡量標(biāo)準(zhǔn)與網(wǎng)絡(luò)實(shí)際應(yīng)用是密切相關(guān)的。如人際關(guān)系網(wǎng)絡(luò)中，一個(gè)社會(huì)交際圈廣泛的人具有很高的重要性，但是其他人也可以通過(guò)與重要人物建立聯(lián)系來(lái)提高自己的重要性。因此要從實(shí)際應(yīng)用的角度出發(fā)，選擇合適的一個(gè)或幾個(gè)方法對(duì)不同拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)和進(jìn)行分析，從而得到最合理的結(jié)論。

參考文獻(xiàn)

[1]李玉華，賀人貴，鐘開，李瑞軒.動(dòng)態(tài)加權(quán)網(wǎng)絡(luò)中節(jié)點(diǎn)重要度評(píng)估[J].Journal of Frontiers of Computer Science and Technology.2012，06（02）-0134-10.

[2]朱濤，張水平，郭戎蕭.改進(jìn)的加權(quán)復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要度評(píng)估的收縮方法[J].系統(tǒng)工程與電子技術(shù)，2009（8）：1-4.

[3]赫南，李德毅，淦文燕，等.復(fù)雜網(wǎng)絡(luò)中重要性節(jié)點(diǎn)發(fā)掘綜述[J].計(jì)算機(jī)科學(xué)，2007，32（12）：1-6.

[4]余高輝，楊建梅，曾敏剛.QQ群好友關(guān)系的復(fù)雜網(wǎng)絡(luò)研究[J].華南理工大學(xué)學(xué)報(bào)，2011，13（4）：20-23.

[5]譚躍進(jìn)，吳俊，鄧宏鐘.復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要度評(píng)估的節(jié)點(diǎn)收縮方法[J].系統(tǒng)工程理論與實(shí)踐，2006（11）：79-83.

作者簡(jiǎn)介

方麗媛（1993-），女，黑龍江綏化人，中南大學(xué)信息科學(xué)與工程學(xué)院本科生。

endprint