加權社交網絡節點中心性計算模型

李靜茹，喻 莉，趙 佳

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

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

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

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

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

1 無權網絡節點中心性計算方法

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

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

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

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

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

2 加權網絡節點中心性計算模型

2.1 鏈接強度矩陣

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

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

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

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

2.2 加權網絡節點中心性計算模型

圖1 M IT Reality M ining藍牙交互網絡的用戶朋友關系圖

3 實驗與分析

3.1 實驗數據集

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

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

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

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

以上3個網絡數據集的相關信息如表1所示。

表1 網絡數據集相關參數

3.2 傳播效率分析

3.2.1 實驗設置

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

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

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

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

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

3.2.2 結果與分析

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

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

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

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

3.3 魯棒性分析

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

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

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

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

3.4 容錯性分析

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

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

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

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

4 結 論

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

[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] 汪小帆, 李翔, 陳關榮. 網絡科學導論[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.

編 輯 蔣 曉