杜翠鳳

1 引言

在社交網(wǎng)絡(luò)中，營銷人員希望通過具有影響力的客戶使產(chǎn)品信息快速傳播。隨著通信技術(shù)的發(fā)展和在線社交網(wǎng)絡(luò)的普及[1]，研究人員借助于在線社交互聯(lián)網(wǎng)海量的交互信息以及用戶之間的行為關(guān)系，構(gòu)建各種網(wǎng)絡(luò)節(jié)點的影響力度量模型。這些模型可以歸納為三類：基于拓撲結(jié)構(gòu)的網(wǎng)絡(luò)節(jié)點影響力度量；基于用戶行為的網(wǎng)絡(luò)節(jié)點影響力度量；基于用戶交互信息的網(wǎng)絡(luò)節(jié)點影響力度量。而本文考慮到通信數(shù)據(jù)的特點，將重點闡述適用于通信海量數(shù)據(jù)的網(wǎng)絡(luò)拓撲結(jié)構(gòu)的度量方法。

基于網(wǎng)絡(luò)拓撲結(jié)構(gòu)的度量方法從傳統(tǒng)的以節(jié)點“中心性”[2]為代表的度量方法擴展到以局部網(wǎng)絡(luò)結(jié)構(gòu)[3-5]、全局網(wǎng)絡(luò)結(jié)構(gòu)[6-9]以及特征向量[10]為代表的度量方法。由于全局網(wǎng)絡(luò)結(jié)構(gòu)的評估方法具有較高的復雜度，并不適用于大規(guī)模社交網(wǎng)絡(luò)節(jié)點度量，因此不少學者從局部角度實現(xiàn)節(jié)點影響力的度量。研究結(jié)果表明，k-shell（k-殼）在衡量海量社交數(shù)據(jù)的節(jié)點影響力上最為合適[7]，而PageRank等相關(guān)算法則不適用于處理無向網(wǎng)絡(luò)[4]。因此，在節(jié)點度量方法的擴展性、普適性以及效率是影響力度量工作面臨的巨大挑戰(zhàn)。k-shell方法可快速識別網(wǎng)絡(luò)中最有影響力的節(jié)點，但該方法所得到的核心層節(jié)點并不能真實反映其在網(wǎng)絡(luò)的核心位置，這是由于核心層中某些節(jié)點攜帶的信息熵冗余度較高。針對該問題，本文結(jié)合信息熵冗余度判斷核心層存在的冗余節(jié)點，采用基于k-shell和信息熵冗余度相結(jié)合的方法不僅能夠保證核心點識別的速度，而且還可以提高核心點識別的精度。

2 網(wǎng)絡(luò)影響力節(jié)點度量的相關(guān)研究

2.1 問題定義

網(wǎng)絡(luò)影響力節(jié)點度量是基于傳播學和社會學理論提出的，理論認為網(wǎng)絡(luò)影響力節(jié)點度量從某種意義上是一個信息傳播的系統(tǒng)，強調(diào)信息傳播的有效性。本文基于傳播學和社會學理論，采用k-shell來尋找核心層的節(jié)點，結(jié)合信息熵冗余度來剔除核心層的冗余節(jié)點，構(gòu)建基于k-shell和信息熵冗余度的網(wǎng)絡(luò)節(jié)點影響力度量模型。

2.2 k-shell算法

k-shell算法是一種剝洋蔥式的網(wǎng)絡(luò)結(jié)構(gòu)分解算法，通過對節(jié)點的子圖進行逐層分解，把極大子圖稱為k-cores（k-核）；而保留在極大子圖中的節(jié)點存在的位置稱為k-shell，節(jié)點的k-shell值是k-shell層中節(jié)點的重要特征。k-shell算法分解社會網(wǎng)絡(luò)結(jié)構(gòu)的步驟如下：

（1）去掉度數(shù)為1的網(wǎng)絡(luò)節(jié)點，剩下一個子圖，若該子圖中仍然具有度數(shù)為1的節(jié)點則繼續(xù)刪除，直到該子圖G1存在的節(jié)點度數(shù)都大于1，那么被刪除的節(jié)點屬于ks=1的核；

（2）與上一步類似，刪除子圖G1中度數(shù)為2的節(jié)點，直到該子圖G2中存在的節(jié)點數(shù)都大于2，那么這一步被刪除的節(jié)點屬于ks=2的核；

（3）以此類推，逐步增加k值，對節(jié)點的子圖進行逐層分解，直到所有節(jié)點被劃分到k-shell中，而這些節(jié)點所在的子圖被稱為極大子圖。

首先獲取一個網(wǎng)絡(luò)節(jié)點連接圖，如圖1所示；將網(wǎng)絡(luò)節(jié)點中度數(shù)為1的節(jié)點以及邊去掉，剩下一個子圖，若該子圖中仍然具有度數(shù)為1的節(jié)點則繼續(xù)刪除，那么所有被刪除的節(jié)點被納入于ks=1的核，如圖2所示。

采取同樣的方法把相應的節(jié)點劃分到ks=2的核中，如圖3所示。

重復上述步驟，直到所有的節(jié)點被去除。如圖4所示，相應的網(wǎng)絡(luò)節(jié)點被劃分到ks=3的核中。網(wǎng)絡(luò)結(jié)構(gòu)分解結(jié)束后，每個節(jié)點均有一個ks值。很顯然，采用k-shell值反映節(jié)點在網(wǎng)絡(luò)中的核心位置是有問題的，因為所處核心層的所有節(jié)點的信息傳播特征是有差異的。研究表明[9]，某些節(jié)點具有較高的信息熵冗余度，這類節(jié)點在信息傳播過程中的重要性明顯低于具有較低的信息熵冗余度的節(jié)點。因此，本文在k-shell算法的基礎(chǔ)上，結(jié)合網(wǎng)絡(luò)節(jié)點信息熵冗余度來識別真正的核心節(jié)點。

圖1 網(wǎng)絡(luò)節(jié)點連接圖

圖2 ks=1的核所包含的節(jié)點

圖3 ks=2的核所包含的節(jié)點

圖4 ks=3的核所包含的節(jié)點

2.3 網(wǎng)絡(luò)節(jié)點信息熵及其冗余度

熵是對系統(tǒng)不確定性的度量[11]。在信息論中，根據(jù)香農(nóng)定義的信息熵是指信息的數(shù)學期望。根據(jù)這個概念，研究者把熵理解為某種特定信息出現(xiàn)的概率。而從熵這個概念引申出來了系統(tǒng)的有序化程度：一個系統(tǒng)越有序，其信息熵就越低。在社會網(wǎng)絡(luò)中，節(jié)點的信息傳播需要衡量兩個方面：信息傳播的可達率以及準確率。

可達率是指信息在兩個節(jié)點中流動，設(shè)從起始節(jié)點出發(fā)到終止節(jié)點的時間跨度為As，從節(jié)點i傳播到其相鄰節(jié)點的時間跨度為li，則節(jié)點i的信息傳播可達率為：

同理，根據(jù)網(wǎng)絡(luò)的拓撲特性，信息從一個節(jié)點傳播到另一個節(jié)點需要跨越節(jié)點的總數(shù)量為Az，與節(jié)點i直接關(guān)聯(lián)的節(jié)點數(shù)量為ki，則節(jié)點i的信息傳播準確率為：

那么，節(jié)點i的綜合信息熵為：

其中：

根據(jù)冗余度的定義，節(jié)點i的信息熵冗余度為：

節(jié)點信息熵冗余度對網(wǎng)絡(luò)節(jié)點中心性的計算、社區(qū)劃分、網(wǎng)絡(luò)控制、網(wǎng)絡(luò)傳播路徑的識別等基于網(wǎng)絡(luò)的應用有顯著影響，這一研究結(jié)果對于認識復雜網(wǎng)絡(luò)的拓撲結(jié)構(gòu)、準確區(qū)分網(wǎng)絡(luò)節(jié)點角色有著重要意義。

節(jié)點影響力度量的方法為：考慮節(jié)點的ks值，在ks值相同的情況下，結(jié)合公式(5)所得的熵冗余度對節(jié)點的影響力進行綜合排名，熵冗余度越大表示節(jié)點的排名越后。

3 基于k-shell和信息熵冗余度的網(wǎng)絡(luò)節(jié)點影響力度量流程

本文基于k-shell和信息熵冗余度的網(wǎng)絡(luò)節(jié)點影響力度量流程具體如下：

（1）獲取某地市運營商最近一個月的部分移動用戶的移動社交數(shù)據(jù)；

（2）基于上述數(shù)據(jù)，構(gòu)建移動用戶的社交網(wǎng)絡(luò)；

（3）采用k-shell的方法分解網(wǎng)絡(luò)結(jié)構(gòu)，得到核心層的移動用戶；

（4）結(jié)合信息熵冗余度判斷核心層存在的冗余節(jié)點；

（5）通過實驗的方法驗證利用信息熵冗余度算法是否能夠識別存在傳播影響力較大的核心層節(jié)點，采用實驗對比的方法來判斷本文提出的算法是否能夠提高具有較高傳播影響力的核心用戶選取的精度。

3.1 獲取源數(shù)據(jù)，并對數(shù)據(jù)進行清洗

本文以某運營商一個月1 860名移動用戶的通話記錄為例，如果某個用戶在一個月中與另一個用戶發(fā)生聯(lián)系，那么可以認為這兩個節(jié)點之間具有連通性。用戶通話數(shù)據(jù)具體如表1所示：

表1 用戶通話數(shù)據(jù)

根據(jù)上述通話數(shù)據(jù)，下一步的工作就是對數(shù)據(jù)進行清理，比如一些公共電話（快遞電話、中介電話等）。因此，本文采用TF-IDF算法來清理通信用戶數(shù)據(jù)，相關(guān)的方法[12]不再贅述。

3.2 構(gòu)建通信用戶社交網(wǎng)絡(luò)圖

根據(jù)清洗后的移動用戶數(shù)據(jù)，構(gòu)建移動用戶的通信網(wǎng)絡(luò)圖，其矩陣的表示方式如表2所示。

3.3 采用k-shell的方法分解網(wǎng)絡(luò)結(jié)構(gòu)

采用k-shell的方法分解網(wǎng)絡(luò)結(jié)構(gòu)，得到核心層的用戶如表3所示。

從表3可知，基于k-shell的方法分解網(wǎng)絡(luò)結(jié)構(gòu)可獲得13層用戶數(shù)據(jù)，其中第13層是網(wǎng)絡(luò)的核心層，擁有8個核心節(jié)點。為驗證本文提出算法的有效性和可行性，分別對僅使用k-shell算法尋找核心節(jié)點以及k-shell結(jié)合信息熵冗余度的方法尋找核心節(jié)點這兩種方法進行了8組實驗。在試驗之前，本文把上述核心層的8個用戶號碼進行編碼，分別是1～8，得到的相關(guān)信息具體如表4所示：

表2 移動用戶通信網(wǎng)絡(luò)矩陣

表3 基于k-shell算法進行網(wǎng)絡(luò)結(jié)構(gòu)分解

表4 各節(jié)點的相關(guān)信息

在本次試驗中，設(shè)信息傳播率為0.2。本次試驗采用標準的SIR模型來模擬影響力的傳播。

首先，采用經(jīng)典的k-shell得出核心點后，隨機選取節(jié)點1～8中的2個節(jié)點、4個節(jié)點、6個節(jié)點以及8個節(jié)點進行信息傳播，得到整個網(wǎng)絡(luò)中信息被有效、真實傳播的節(jié)點數(shù)量；然后采用本文提出的方法得到核心層的8個節(jié)點，計算各個節(jié)點信息熵冗余度并將其進行排序，分別選取排名前2名的節(jié)點、前4名的節(jié)點、前6名的節(jié)點以及前8名的節(jié)點進行信息傳播，得到整個網(wǎng)絡(luò)中信息被有效、真實傳播的節(jié)點數(shù)量。相關(guān)的對比結(jié)果如表5所示：

表5 經(jīng)典的k-shell算法與本文算法的傳播節(jié)點數(shù)量對比

在真實網(wǎng)絡(luò)中，網(wǎng)絡(luò)各層連接具有多樣性的特點，節(jié)點本身具有信息熵，且較低熵值的節(jié)點所攜帶的信息量較少，其傳播給相鄰節(jié)點的影響力也較小。本文通過提取信息熵冗余度的方法，并采用實驗對比了上述兩組數(shù)據(jù)的連接特征，確定節(jié)點的潛在影響力在信息傳播中的重要性。實驗發(fā)現(xiàn)，有一類節(jié)點存在于網(wǎng)絡(luò)連接的核心層，但本身具有較高的信息熵冗余度。也就是說，雖然節(jié)點本身擁有較高的連接數(shù)量，但其攜帶的信息量較少，對周圍的節(jié)點具有較低的影響力，影響周圍其他節(jié)點的數(shù)量有限。從表5可知，采用經(jīng)典的k-shell算法的傳播節(jié)點數(shù)量比本文算法的傳播節(jié)點數(shù)量少，實驗結(jié)果證實了網(wǎng)絡(luò)核心層確實存在具有較高信息熵冗余度的節(jié)點，這類節(jié)點往往具有較低的傳播性。因此，在選擇核心節(jié)點時，通過過濾具有較高信息熵冗余度的節(jié)點能夠在很大程度上提升核心節(jié)點選取的精度以及信息傳播的準確性。這一結(jié)果對于運營商實施產(chǎn)品的推廣以及病毒營銷具有重要的意義。

4 結(jié)束語

本文提出基于k-shell和信息熵冗余度的網(wǎng)絡(luò)節(jié)點影響力度量算法，即通過k-shell算法來提取核心層的節(jié)點，采用信息熵冗余度來過濾具有較高信息熵冗余度的節(jié)點，綜合上述兩種算法來選擇網(wǎng)絡(luò)中具有影響力的節(jié)點。本文的算法能夠有效識別存在網(wǎng)絡(luò)核心層但由于自身攜帶的信息量較少，對周邊具有較低影響力的節(jié)點，使得保留下來的節(jié)點不僅具有較高的連接數(shù)量，而且本身具有較高的傳播影響力，從而提升核心節(jié)點對網(wǎng)絡(luò)的傳播影響力，有效地解決了k-shell指標度量的核心層節(jié)點并不能真實反映其在網(wǎng)絡(luò)傳播影響力中的核心位置這一問題，合理地規(guī)避了核心層節(jié)點選取的隨意性較高的問題，實現(xiàn)了基于k-shell指標選取的核心節(jié)點的客觀化和科學化。由于本文僅針對某運營商的部分移動用戶數(shù)據(jù)進行研究，因此適用性和擴展性有限。后續(xù)可針對移動運營商某個省的用戶數(shù)據(jù)進行研究，以擴展該算法的適用范圍。

[1] Ellison N B. Social network sites: Definition, history,and scholarship[J]. Journal of Computer-Mediated Communication, 2007,13(1): 210-230.

[2] 任曉龍,呂琳媛. 網(wǎng)絡(luò)重要節(jié)點排序方法綜述[J]. 科學通報, 2014(13): 1175-1197.

[3] 任卓明,邵鳳,劉建國,等. 基于度與集聚系數(shù)的網(wǎng)絡(luò)節(jié)點重要性度量方法研究[J]. 物理學報, 2013,62(12): 522-526.

[4] Chen D, Lu L, Shang M S, et al. Identifying influential nodes in complex networks[J]. Physica A Statistical Mechanics & Its Applications, 2012,391(4): 1777-1787.

[5] Gao S, Ma J, Chen Z, et al. Ranking the Spreading ability of nodes in complex networks based on local structure[J].Physica A Statistical Mechanics & Its Applications,2014,403(6): 130-147.

[6] Freeman L C. Centrality in social networks conceptual clariベcation[J]. Social Networks, 1978,1(3): 215-239.

[7] Kitsak M, Gallos L K, Havlin S, et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2011,6(11): 888-893.

[8] Bae J, Kim S. Identifying and ranking inぼuential spreaders in complex networks by neighborhood coreness[J].Physica A Statistical Mechanics & Its Applications,2014,395(4): 549-559.

[9] Liu Y, Tang M, Zhou T, et al. Core-like groups result in invalidation of identifying super-spreader by k-shell decomposition[J]. Scientiベc Reports, 2015(5): 9602.

[10] Lü L, Zhang Y C, Yeung C H, et al. Leaders in social networks, the Delicious case[J]. Plos One, 2011,6(6):1-9.

[11] 王俊,杜翠鳳. 基于熵理論的ERP業(yè)務(wù)流程評價體系研究[J]. 移動通信, 2016,40(16): 20-24.

[12] 蔣仕寶,陳少權(quán). 基于呼叫指紋的重入網(wǎng)識別算法研究[J]. 移動通信, 2016,40(22): 27-30.

[13] Silva R A P D, Viana M P, Costa L D F. Predicting epidemic outbreak from individual features of the spreaders[J]. Journal of Statistical Mechanics Theory&Experiment, 2012(7): 1-8.★