加權社交網(wǎng)絡節(jié)點中心性計算模型

李靜茹，喻 莉，趙 佳

(華中科技大學電子與信息工程系 武漢 430074)

確定網(wǎng)絡中的關鍵節(jié)點是包括社交網(wǎng)絡在內(nèi)的復雜網(wǎng)絡的重要研究內(nèi)容。比如，在各種社交網(wǎng)絡中，經(jīng)常需要知道哪些是最活躍、最具影響力的用戶，以便為運營商提供營銷策略的指導，或為移動社交網(wǎng)絡的內(nèi)容分布提供有用依據(jù)。在社會網(wǎng)絡分析中，用“中心性(centrality)”來刻畫節(jié)點在網(wǎng)絡中的重要程度[1]。

中心性常用的度量方法有度中心性、介數(shù)中心性、接近中心性[2]和特征向量中心性(EVC)[3]等。相比其他幾種中心性度量方法，EVC不僅考慮了節(jié)點的度(即鄰居節(jié)點的數(shù)量)，還考慮了鄰居節(jié)點的重要性，因此成為檢測社交網(wǎng)絡中最具影響力節(jié)點的成功方法，并在社會科學中有廣泛應用[4]。而由于EVC是將鄰接矩陣對應的主特征向量作為節(jié)點中心性，故最重要的一些節(jié)點集中于一個社團；而事實情況往往是這些最具影響力的節(jié)點分屬于不同社團。鑒于此，文獻[4]提出了主分量中心性(PCC)，利用鄰接矩陣的前P個特征向量來計算節(jié)點中心性，有效地避免了EVC的缺陷。文獻[5]針對PageRank方法在非連通網(wǎng)絡中排序不唯一的缺陷，提出了LeaderRank方法，網(wǎng)絡中增加一個與所有節(jié)點雙向連通的節(jié)點，使得整個網(wǎng)絡連通且排序唯一，在傳播效率、魯棒性和容錯性方面有明顯的提升。文獻[6]針對度中心性的低相關性和介數(shù)中心性、接近中心性在大型網(wǎng)絡中的高復雜度，折中提出一種半局部中心性，在降低計算復雜度的同時能很好地識別出影響力高的節(jié)點。

而以上方法均針對無權網(wǎng)絡，只考慮了節(jié)點間是否連接，而未考慮節(jié)點間鏈接強度如何。而文獻[7]提出，很多網(wǎng)絡中的鏈接并不僅僅表示存在與否，而是有相應的權重來記錄鏈接的強度，也就是說，很多網(wǎng)絡都是加權網(wǎng)絡。文獻[7]也提到，在很多情況下，可以應用無權網(wǎng)絡中的傳統(tǒng)方法來解決加權網(wǎng)絡的問題。因此，將無權網(wǎng)絡的方法拓展到加權網(wǎng)絡是網(wǎng)絡研究的重要問題之一。文獻[8]指出，可將無權網(wǎng)絡中的EVC擴展到加權網(wǎng)絡，并將這樣得到的加權網(wǎng)絡EVC用于引文網(wǎng)絡的搜索結果排序；但是，PCC作為在計算節(jié)點中心性方面比EVC更好的工具，目前還沒有被擴展到加權網(wǎng)絡。

本文首次提出將無權網(wǎng)絡中度量節(jié)點中心性的PCC應用于加權網(wǎng)絡，提出基于鏈接強度矩陣的加權主分量中心性度量法(加權PCC)。實驗結果顯示，加權PCC在傳播效率、魯棒性和容錯性等方面優(yōu)于加權EVC，因此加權PCC在加權社交網(wǎng)絡中是可行有效的。本文最重要的貢獻就是把無權網(wǎng)絡的PCC延伸到加權社交網(wǎng)絡，從而豐富了將無權網(wǎng)絡經(jīng)典方法拓展到加權網(wǎng)絡的研究。

1 無權網(wǎng)絡節(jié)點中心性計算方法

中心性常用的度量方法有度中心性、介數(shù)中心性、接近中心性[2]和特征向量中心性(EVC)[3]等。相比于其他幾種中心性度量方法，EVC不僅考慮了節(jié)點的度，還考慮了鄰居節(jié)點的重要性，因此成為檢測社交網(wǎng)絡中最具影響力節(jié)點的成功方法。無權網(wǎng)絡中節(jié)點的EVC定義為：與該節(jié)點鄰居的EVC之和成正比[7]。

通過分析EVC算法的收斂性得到，如果λ1為矩陣A的模最大的特征值，那么特征向量中心性x應該是與λ1對應的特征向量，也稱為主特征向量[9]。從而，式(1)即為

而EVC在刻畫無權網(wǎng)絡節(jié)點中心性時，存在其缺陷[4]：最重要的一些節(jié)點集中于一個較小的區(qū)域，即EVC將最重要的一些節(jié)點視作一個小社團，而事實情況是，最重要的一些節(jié)點可能分屬于不同社團；另外，大部分節(jié)點的EVC值都為無意義的0，不能充分滿足排序等應用的需求。

通過將網(wǎng)絡圖映射為一個多重圖，可以將無權網(wǎng)絡節(jié)點中心性度量方法推廣到加權網(wǎng)絡；那么，加權網(wǎng)絡中節(jié)點的EVC，為當前加權鄰接矩陣的主特征向量[7]。文獻[8]指出，可將這樣得到的加權網(wǎng)絡EVC用于引文網(wǎng)絡的搜索結果排序。由于加權網(wǎng)絡可看做無權網(wǎng)絡映射成的多重圖，EVC在刻畫加權網(wǎng)絡節(jié)點中心性時，也會存在與無權網(wǎng)絡同樣的問題。

為了彌補EVC的以上缺陷，文獻[4]提出了主分量中心性(PCC)。但是目前沒有研究將PCC應用于加權社交網(wǎng)絡。于是本文拓展了無權網(wǎng)絡的PCC，并提出了適用于加權社交網(wǎng)絡的中心性計算模型。

2 加權網(wǎng)絡節(jié)點中心性計算模型

2.1 鏈接強度矩陣

傳統(tǒng)的中心性計算方法未能考慮節(jié)點間連接的時間動態(tài)性，而鏈接強度可以通過具體刻畫連接可用的概率來克服這個缺陷[10]。因此，本文選用鏈接強度來刻畫節(jié)點間鏈接的權重。

鏈接強度是定量刻畫節(jié)點間鏈接的一種性質(zhì)，由文獻[11]于1973年首次提出。文獻[10]認為一種關系的強度依賴于4種因素：接觸頻率，關系時長，接觸時長，交互數(shù)目。研究者們據(jù)此提出7種因素，并根據(jù)不同的研究需要采用不同的因素來刻畫鏈接強度：頻率、親密度、壽命、相互性、時近性、多重社交背景、信任[10]。

本文選取頻率和親密度兩個因素來刻畫鏈接強度。鏈路上發(fā)生的交互越頻繁，越親密(即連接時長越長)，則鏈接強度越強。這兩個因子的計算方法是根據(jù)基于證據(jù)的策略，即用輔助性證據(jù)與反駁性證據(jù)的數(shù)目的比值來度量節(jié)點或系統(tǒng)對證據(jù)的信任[10]。

1) 頻率因子：取決于某節(jié)點i與其他節(jié)點 j相遇的頻率，用節(jié)點間相遇次數(shù)計算。

2.2 加權網(wǎng)絡節(jié)點中心性計算模型

圖1 M IT Reality M ining藍牙交互網(wǎng)絡的用戶朋友關系圖

3 實驗與分析

3.1 實驗數(shù)據(jù)集

本文選用以下3個真實的加權社交網(wǎng)絡數(shù)據(jù)集，對加權PCC的性能進行了仿真與分析：

1) M IT Reality M ining數(shù)據(jù)集[13]：該數(shù)據(jù)集是由M IT Media Lab的Reality M ining項目經(jīng)過約9個月的實驗，使用104個Nokia 6600手機記錄用戶交互數(shù)據(jù)。本文采用其中的藍牙交互數(shù)據(jù)，包括用戶間相遇的頻率、時長等數(shù)據(jù)，且選出其中94個有效用戶數(shù)據(jù)進行實驗。用戶間朋友關系圖如圖1所示。用戶間鏈接的權重根據(jù)2.1節(jié)的方法計算得到。

2) NetScience數(shù)據(jù)集[14]：這是研究網(wǎng)絡理論與實驗的1 589位科學家組成的科學家合作網(wǎng)。網(wǎng)絡中的節(jié)點代表論文的作者，邊是作者間的合作關系，邊上的權重是根據(jù)文獻[15]中的方法計算得到的。

3) Facebook-like social network數(shù)據(jù)集[16]：該數(shù)據(jù)集描述加州大學歐文分校學生的在線社會網(wǎng)絡。它共包含1 899個節(jié)點，節(jié)點表示學生，邊表示學生之間的信息接受和發(fā)送，邊上的權重表示接受和發(fā)送信息的數(shù)目。該數(shù)據(jù)集本來是一個有權有向圖，由于本文的中心性指標適用于有權無向圖，所以本文將兩個節(jié)點間接受和發(fā)送信息數(shù)目的總和作為對應鏈接的權重，從而將Facebook-like social network數(shù)據(jù)集轉(zhuǎn)化為有權無向圖進行實驗。

以上3個網(wǎng)絡數(shù)據(jù)集的相關信息如表1所示。

表1 網(wǎng)絡數(shù)據(jù)集相關參數(shù)

3.2 傳播效率分析

3.2.1 實驗設置

文獻[17]認為，在社交網(wǎng)絡中信息是以串聯(lián)形式進行傳遞，且信息串流的傳播分析可用于確定社交網(wǎng)絡中最有影響力的節(jié)點。因此，本節(jié)實驗采用獨立串聯(lián)模型[18]來刻畫社交網(wǎng)絡的信息傳播規(guī)律。基于該模型，本節(jié)實驗比較加權PCC和加權EVC的傳播效率，從而驗證提出的加權社交網(wǎng)絡中心性計算模型的有效性。具體的傳播過程為：

1) 初始激活節(jié)點集：分別以加權 PCC和加權EVC排序得到的前N個節(jié)點為傳播的初始激活節(jié)點集，分別表示為

2) 成功激活閾值：獨立串聯(lián)模型中，兩節(jié)點v和w間存在成功激活概率pv,w；當v試圖激活w時產(chǎn)生的隨機概率小于pv,w時，v將成功激活w。將成功激活概率pv,w稱為成功激活閾值(用THv,w表示)，且認為與鏈接強度成正比，因為鏈接強度越大，表明兩節(jié)點關系越親密，則兩節(jié)點間傳遞信息越容易。設

式中，常數(shù)k?[0,1]稱為傳播參數(shù)。實驗中將鏈接強度矩陣歸一化至[0,1]，這樣能保證此時，鏈接強度越大，THv,w越大，產(chǎn)生的隨機概率小于THv,w的可能性越大，即節(jié)點間傳遞信息越容易。

3) 比較方法：當v試圖激活w時產(chǎn)生的隨機概率小于THv,w時，則v將成功激活w，信息就在兩節(jié)點間傳遞。計算每個步驟分別以A0,PCC和A0,EVC為傳播起點而被激活的節(jié)點總數(shù)，并加以比較，即可比較分別以為傳播起點的傳播效率。

3.2.2 結果與分析

圖2是傳播初始激活節(jié)點數(shù)目N取不同值時，每時刻兩種加權中心性傳播效率的比較。以下每幅實驗結果圖均是進行500次獨立實驗并將其結果取平均得到的。

圖2 加權PCC和加權EVC傳播效率比較

由圖2可見，在不同的加權網(wǎng)絡中，基于加權PCC排序選出的前N位節(jié)點作為傳播源的傳播效率高于加權EVC，即加權PCC能更準確地識別出傳播影響力高的節(jié)點。這是因為加權PCC采用了權重矩陣的更多主特征向量，能挖掘加權社交網(wǎng)絡的更多結構信息。同時，3個加權社交網(wǎng)絡的平均路徑長度均為Inf，即3個網(wǎng)絡均為非連通網(wǎng)絡?？烧f明加權PCC由于采用了更多主特征向量，因此可以有效彌補網(wǎng)絡非連通部分對中心性計算的影響。

另外還發(fā)現(xiàn)，加權PCC在高聚類系數(shù)的M IT Reality M ining數(shù)據(jù)集和NetScience網(wǎng)絡中的優(yōu)勢更明顯，而在聚類系數(shù)相對低的Facebook-like social network中的優(yōu)勢并不明顯。這是因為加權PCC通過采用更多的主特征向量，能探測出加權社交網(wǎng)絡中的主要社團結構；而低聚類系數(shù)的網(wǎng)絡的社團特性相對不強，則加權PCC的優(yōu)勢相對不明顯。

3.3 魯棒性分析

社交網(wǎng)絡中存在一類節(jié)點，它們通過關注原網(wǎng)絡中某些用戶或給它們發(fā)垃圾郵件的方式，改變原網(wǎng)絡中某些節(jié)點的影響力[5]，稱之為虛假粉絲。它們與原網(wǎng)絡節(jié)點的互動非常微弱，即鏈接強度很弱，但由于改變了整個網(wǎng)絡的結構，所以對節(jié)點中心性的計算帶來了干擾。因此很有必要度量一種中心性指標針對虛假粉絲攻擊的魯棒性。

本節(jié)仿真實驗令原網(wǎng)絡中真實用戶節(jié)點之間的互動關系(即鏈接強度)不變，同時增加20%的虛假粉絲節(jié)點。假設這些虛假粉絲節(jié)點與其他節(jié)點之間存在弱鏈接強度，然后比較加權PCC和加權EVC的魯棒性，實驗結果如圖3所示。

圖3中，y=x為比較基準，為最理想的情況，即加入虛假粉絲后，節(jié)點中心性排序不變。若加入虛假粉絲后，節(jié)點中心性排序在y=x周圍波動得厲害，則說明該中心性的魯棒性較差，反之，魯棒性較好。由圖3的結果可見，在3種加權社交網(wǎng)絡中，加權PCC的魯棒性均相對較好。其中，加權PCC在節(jié)點數(shù)目較少、聚類系數(shù)較高的M IT Reality M ining數(shù)據(jù)集網(wǎng)絡中的魯棒性最好，波動最輕微，這是因為該網(wǎng)絡內(nèi)節(jié)點間鏈接非常緊密，使得虛假粉絲的加入對網(wǎng)絡性能影響較小，從而保證節(jié)點中心性排序較為穩(wěn)定。在NetScience網(wǎng)絡中，大約前440位節(jié)點的加權PCC排序保持不變，而在后面節(jié)點的排序波動也小于加權EVC。證明了加權PCC在加權社交網(wǎng)絡中較好的魯棒性。在Facebook-like social network中，加權PCC的魯棒性存在一定優(yōu)勢，但并不明顯，這是由于聚類系數(shù)較低時，外來虛假粉絲的加入較明顯地改變了網(wǎng)絡結構，使得中心性排序產(chǎn)生較大波動。

圖3 加權PCC和加權EVC魯棒性比較

3.4 容錯性分析

中心性指標的容錯性考慮的是網(wǎng)絡增減一些偽造鏈接時的情況[5]。這是因為社交網(wǎng)絡數(shù)據(jù)中可能存在噪聲數(shù)據(jù)，即根據(jù)原始數(shù)據(jù)并不容易確定用戶間是否存在某種鏈接。由于增加和移除偽造鏈接的容錯性是對稱的，本節(jié)實驗針對移除偽造鏈接的情況進行容錯性分析。檢驗加權中心性算法的容錯性的方法是，度量當鏈接被隨機移除時排序的變化量[5]，因為對于中心性算法，排序的準確性比中心性的具體數(shù)值更重要。噪聲數(shù)據(jù)對排序的影響IR為[5]：

式中，Ri和Ri￠分別是由原圖和修改后的圖得到的中心性排序。

圖4 加權PCC和加權EVC容錯性比較

如圖4所示，在NetScience網(wǎng)絡和Facebook-like social network中，加權PCC相比于加權EVC有較小的IR，即容錯性較好。而在M IT Reality M ining藍牙交互網(wǎng)絡中，加權PCC卻表現(xiàn)出較差的容錯性。這是因為，在M IT Reality M ining藍牙交互網(wǎng)絡中，我們將用藍牙裝備檢測到另一個節(jié)點視為一條鏈接，并采用2.1節(jié)的方法計算出鏈接強度，這樣雖能全面、準確地刻畫出每兩個節(jié)點間的鏈接強度，卻同時產(chǎn)生了噪聲數(shù)據(jù)。這使得加權PCC雖采用更多主特征向量，反而不能更好地識別噪聲數(shù)據(jù)，造成容錯性較差。而NetScience網(wǎng)絡和Facebook-like social network的鏈接分別為節(jié)點間的合作和信息發(fā)收，均比較明確，所以數(shù)據(jù)集本身不含有太多噪聲數(shù)據(jù)，因而，加權PCC容錯性的優(yōu)勢就體現(xiàn)出來了。這些發(fā)現(xiàn)給出了啟示，即本文鏈接強度的計算方法有待改進，如可以通過增加門限的方法，過濾掉一些噪聲數(shù)據(jù)，這樣能增加加權PCC的容錯性。

4 結 論

確定網(wǎng)絡中的關鍵節(jié)點在社交網(wǎng)絡研究中有重要意義。本文將無權網(wǎng)絡中度量節(jié)點中心性的方法PCC進行拓展，基于鏈接強度矩陣提出適用于加權社交網(wǎng)絡的中心性計算模型(加權PCC)。實驗結果顯示，加權PCC在傳播效率、魯棒性和容錯性比較中優(yōu)于加權EVC。此結果說明，應用PCC度量并排序加權社交網(wǎng)絡節(jié)點的重要程度，可有效地促進信息的擴散，在實際應用中很有價值，如加速信息傳播、控制輿論擴散、加速移動社交網(wǎng)絡的內(nèi)容分布等。同時，由于加權PCC針對虛假粉絲有更好的魯棒性，針對噪聲數(shù)據(jù)有更好的容錯性，使得它在實際加權社交網(wǎng)絡平臺中是可行有效的。

[1] WASSERMAN S, FAUST F. Social network analysis:methods and applications[M]. Cambridge, U.K.: Cambridge University Press, 1994.

[2] FREEMAN C L. Centrality in social networks conceptual clarification[J]. Social Network, 1978, 1(3): 215-239.

[3] BONACICH P. Factoring and weighting approaches to clique identification[J]. Journal of Mathematical Sociology,1972, 2(1): 113-120.

[4] ILYAS U M, RADHA H. A KLT-inspired node centrality for identifying influential neighborhoods in graphs[C]//Proceedings of the 44th International Conference on Information sciences and systems. Princeton, NJ: Princeton University, 2010: 1-7.

[5] Lü Lin-yuan, ZHANG Yi-cheng, YEUNG C H, et al.Leaders in social networks, the delicious case[J]. PLOS ONE, 2011, 6(6): e21202.

[6] CHEN Duan-bing, Lü Lin-yuan, SHANG M ing-sheng, et al.Identifying influential nodes in complex networks[J].Physica A, 2012, 391(4): 1777-1787.

[7] NEWMAN M. Analysis of weighted networks[J]. Physical Review E, 2004, 70(5): 56131.

[8] REDNER S. How popular is your paper? an empirical study of the citation distribution[J]. The European Physical Journal B, 1998, 4(2): 131-134.

[9] 汪小帆, 李翔, 陳關榮. 網(wǎng)絡科學導論[M]. 北京: 高等教育出版社, 2012: 158-166.

WANG Xiao-fan, LI Xiang, CHEN Guan-rong. Network science: an introduction[M]. Beijing: Higher Education Press, 2012: 158-166.

[10] DALY M E, HAAHR M. Social network analysis for information flow in disconnected delay-tolerant manets[J].IEEE Transactions on Mobile Computing, 2009, 8(5):606-621.

[11] GRANOVETTER S M. The strength of weak ties[J]. The American Journal of Sociology, 1973, 78(6): 1360-1380.

[12] ILYAS U M, SHAFIQ Z M, LIU X A, et al. A distributed and privacy p reserving algorithm for identifying information hubs in social networks[C]//INFOCOM.Shanghai: [s.n.], 2011: 561-565.

[13] EAGLE N, PENTLAND A, LAZER D. Inferring social network structure using mobile phone data[J]. Proceedings of the National Academy of Sciences, 2009, 106(36):15274-15278.

[14] NEWMAN M. Finding community structure in networks using the eigenvectors of matrices[J]. Physical Review E,2006, 74(3): 036104.

[15] NEWMAN M. Scientific collaboration networks II.shortest paths, weighted networks, and centrality[J].Physical Review E, 2001, 64(1): 016132.

[16] OPSAHL T, PANZARASA P. Clustering in weighted networks[J]. Social Networks, 2009, 31(2): 155-163.

[17] DOTEY A, ROM H, VACA C. Information diffusion in social media[R]. California: Stanford University, 2011.

[18] KEMPE D, KLEINBERG J, TARDOS E. Maximizing the spread of influence through a social network[C]//Proceedings of the 9th ACM SIGKDD International Conference on Know ledge Discovery and Data M ining.New York: ACM, 2003: 137-146.

編 輯 蔣 曉