王棟志 張 暉 楊春明 趙旭劍 李 波

(1. 西南科技大學計算機科學與技術學院 四川綿陽 621010； 2. 西南科技大學理學院 四川綿陽 621010)

影響力分析是社交網絡分析的重要內容，其中影響力最大化節(jié)點挖掘是影響力分析的基礎工作，其目的是從網絡中識別K個節(jié)點，使得通過這K個節(jié)點在某種影響力傳播機制下產生的影響傳播范圍最大。影響力分析在輿情分析、精準廣告等領域有著廣泛應用，近年來大量學者從不同角度提出了不同算法進行影響力分析。由于現(xiàn)實社交網絡涉及節(jié)點數(shù)量巨大且網絡稀疏，實際社交網絡下的最大化影響力挖掘仍然面臨著巨大的挑戰(zhàn)。

為提高算法執(zhí)行效率，不少學者采用啟發(fā)式算法識別影響力最大化節(jié)點。文獻[1-3]提出度中心性(High-Degree, HD)衡量節(jié)點重要性程度，即按照節(jié)點度值的大小定義節(jié)點影響力強度，文獻[4-5]證明了在具有“富人俱樂部”特性網絡中，策略性的移除度值最高節(jié)點作為影響力節(jié)點能夠最快地將影響力擴散至整個網絡。在此基礎上，Cohen[3]提出適應性度中心性(High Degree Adaptive, HDA)，即不斷從網絡中移除度值最高的節(jié)點及其連邊作為影響力節(jié)點，同時更新計算所有節(jié)點的度排序。Bavelas[6]提出利用接近度中心性(Closeness Centrality, CC)反映節(jié)點在網絡中居于中心的程度，即表示節(jié)點i到其他所有節(jié)點最短距離之和的倒數(shù)乘以其他節(jié)點的個數(shù)。節(jié)點的接近度越大，表明節(jié)點越居于該節(jié)點的局部網絡中心，它在網絡中就越重要。一個網絡的K-核是指反復移除度值小于K的節(jié)點及其連邊后所剩余的子圖，該子圖的節(jié)點數(shù)就是該核的大小。Kitsak M[7]論證K-核算法適用于最大影響力節(jié)點相互獨立的社交網絡，而當最大影響力節(jié)點相互聯(lián)合傳播的情況下K-核算法效率極低。也就是說在影響力節(jié)點相互獨立假設下，若影響力最大的節(jié)點處于核中，那么下一個被挖掘的影響力節(jié)點有很大概率不存在于該核中，因為該核中的節(jié)點已被影響力最大節(jié)點感染激活。若將影響力節(jié)點之間的交互因素考慮進K-核算法，則為NP難問題[8]，故K-核算法在聯(lián)合傳播的社交網絡下是非最優(yōu)的。文獻[9-10]由谷歌提出用來衡量網頁重要度，該算法的核心為網頁網絡連接的特征向量中心性，以該算法計算節(jié)點影響力有一個很明顯的缺陷：若一個非影響力節(jié)點和影響力最大節(jié)點相連，則該節(jié)點能獲得較高的影響力“得分”，從而很大概率被挖掘為下一個偽影響力最大化節(jié)點。啟發(fā)式算法存在以下兩個缺陷：啟發(fā)式算法起初被提出的目的并非衡量節(jié)點影響力，而是從拓撲結構的角度考慮節(jié)點重要性程度，而節(jié)點重要度并不等于影響力擴散程度；啟發(fā)式算法未考慮影響力最大節(jié)點集之間的聯(lián)合傳播影響因素。

由于啟發(fā)式算法本身的局限性，學者們也從信息傳播建模的角度挖掘影響力最大節(jié)點集合。Kempe[8]將影響力傳播建模為時間離散的傳播過程，將問題形式化為一個離散最優(yōu)化問題，例如線型閾值模型[11](Linear Threshold Model, LTM)與獨立級聯(lián)模型[12](Independent Cascade Model)，后續(xù)有大量工作對以上兩種模型進行了改進。針對規(guī)模龐大的在線社交網絡，Chen[13]證明了在社交網絡中計算每個用戶的影響力的期望值是NP難的，即并不存在多項式時間內可以計算節(jié)點增益影響力的方法,使得其效率上存在瓶頸。另一方面該模型需要人為定義信息擴散閾值，這使得模型對于輸入?yún)?shù)極其敏感，選擇不同的參數(shù)將導致不同的信息擴散結果，不能客觀有效地衡量信息在網絡中的傳播影響力大小。

Morone等[18]從滲流理論著手考慮影響力最大化問題，為該問題的求解提供了全新的思路。在傳統(tǒng)啟發(fā)式算法的基礎上提出了全局影響力優(yōu)化指標，同時考慮到影響力節(jié)點之間的聯(lián)合傳播影響因素，但其工作沒有考慮影響力在節(jié)點間傳播的信任度傳遞機制。本論文在其工作基礎上，引入信任度傳遞函數(shù)，考慮影響力在傳播過程中“信任度遞減，不信任度遞增”現(xiàn)象對影響力最大化的影響，采用人工網絡數(shù)據(jù)與真實網絡數(shù)據(jù)集對算法的影響力進行評估分析，通過與常用啟發(fā)式算法比較所挖掘影響力最大化節(jié)點集合的影響力擴散率來驗證本文所提算法的合理性與有效性。

1 基于滲流理論的最大影響力節(jié)點挖掘模型

本論文主要從3個角度構建最大影響力節(jié)點挖掘模型：(1)使用非回退矩陣構建滿足信息(影響力)傳播條件的社交網絡圖模型；(2)將信任度傳遞函數(shù)引入信息傳播模型構建符合實際的影響力傳播機制；(3)通過滲流理論得到快速的最大影響力挖掘算法。

1.1 基于非回退矩陣的社交網絡表示圖模型

近年來，非回退矩陣(non-tracking matrix)在復雜網絡建模受到關注。該矩陣從網絡連通性的角度考慮影響力在網絡中的傳播，不僅突破了最大影響力節(jié)點挖掘算法使用傳統(tǒng)鄰接矩陣在稀疏網絡上的局限性，并且研究表明基于非回退矩陣的譜方法在社團發(fā)現(xiàn)等社交網絡研究上相較于拉普拉斯(Laplacian)矩陣與鄰接矩陣有更好的效率。

非回退矩陣的構造流程如下：給定具有N個節(jié)點M條邊的無向社交網絡，為了構建在該社交網絡的非回退矩陣，首先將無向圖轉為有向圖，具體操作為：針對兩個具有直接關聯(lián)的節(jié)點i,j∈N且(i,j)∈E，E為邊集，將無向邊代替為兩條相反指向的有向邊，即分別用i→j與j→i來表示兩條有向邊，故M條無向邊共構成2M條有向邊。下面給出非回退矩陣的元素定義。

定義1[14-15]設網絡具有N個節(jié)點，M條邊，則非回退矩陣B為2M×2M的非對稱矩陣，其元素取值為：

(1)

非回退矩陣刻畫了非回溯游走的可行路徑，即影響力傳播路徑?！胺腔赝恕敝傅氖且环N簡單游走策略，游走路徑不允許沿著已經走過的路徑返回，也就是說類似于1→2→1的訪問路徑是不被允許的。其次，非回退矩陣的子圖為包含諸多“非回退”路徑的樹狀網絡，若從網絡中移除該樹狀網絡將不影響非回退矩陣的譜，需要注意的是由于非回退矩陣為非對稱矩陣，故其特征值除最大特征值為實數(shù)外均為復數(shù)。

非回退矩陣的上述兩種性質，一方面刻畫了影響力在實際社交網絡中的傳播為源節(jié)點到邊緣節(jié)點、從上至下的傳播路徑，另一方面描述了影響力在局部網絡的傳遞呈樹狀結構。從整個網絡中移除該樹狀子圖不影響非回退矩陣的譜，說明以非回退矩陣表示社交網絡相較其他無向對稱鄰接矩陣更具穩(wěn)定性，當考慮某個節(jié)點在網絡中的影響力時，可以客觀地比較移除以該節(jié)點為中心的影響力傳播樹狀子圖前后的信息傳播情況。

以圖1所示的某個社交網絡子圖為例，該網絡具有N=6個節(jié)點，同時具有M=6條邊，先將這6條無向邊轉為2M=12條有向邊，并根據(jù)定義1所確定非回退矩陣元素取值，構建2M×2M大小的非回退矩陣。非回退矩陣可以表明影響力能夠傳播的路徑，以節(jié)點2為例，若節(jié)點1為影響力傳播源節(jié)點，影響力傳達3節(jié)點與5節(jié)點，必須經過節(jié)點2，故形成以節(jié)點2為中心的兩條非回溯路徑1→2→3與1→2→5，根據(jù)非回退矩陣元素定義即B1→2,2→3=1，B1→2,2→5=1。

圖1 社交網絡

1.2 基于信任度的影響力傳播機制

傳統(tǒng)研究影響力在社交網絡中的傳播問題采用信息級聯(lián)技術，信息級聯(lián)在社交網絡中是十分常見的一種現(xiàn)象，當信息級聯(lián)形成后，處于影響力傳播底層的個體節(jié)點容易受其上層影響力節(jié)點的影響，作出與前面?zhèn)€體相同的選擇而忽略自身觀點。如微博平臺中很多人轉發(fā)某條微博并不是出于對內容的興趣而是基于從眾心理。

在信息級聯(lián)模型中，每個初始激活節(jié)點會產生自身獨立的擴散級聯(lián)，級聯(lián)之間相互獨立、互不干擾。將社交網絡抽象為加權無向圖后，任何一條邊(u,v)∈E都被分配一個屬于[0,1]之間的特定值Pu,v，這個值代表激活態(tài)節(jié)點在t時刻是否將信息傳遞給該激活態(tài)節(jié)點鄰近的某個非激活態(tài)節(jié)點的影響力擴散概率。

初始時，選擇合適的影響力擴散種子節(jié)點，影響力從這些節(jié)點開始擴散。在時刻t，每個當前激活的節(jié)點u都會以擴散概率Pu,v去激活它的每個鄰居節(jié)點v。如果節(jié)點v在該時刻被成功激活，那么在t+1時刻，節(jié)點v作為激活態(tài)節(jié)點會去影響該節(jié)點的鄰居節(jié)點。

圖2展示了具有3個節(jié)點{A,B,C}?N的獨立級聯(lián)模型，其中包含兩個一階信息級聯(lián)擴散，分別為A→B與B→C，激活態(tài)節(jié)點A通過影響力傳播機制于t時刻將信息傳遞給節(jié)點B，若節(jié)點B被成功激活，則在t+1時刻，依擴散概率PB,C嘗試激活C節(jié)點。

圖2 獨立級聯(lián)模型

在獨立級聯(lián)模型中，每個激活節(jié)點與其鄰居節(jié)點形成的擴散級聯(lián)相互獨立，如圖2中顯示的兩個獨立一階級聯(lián)擴散，節(jié)點A與節(jié)點C不存在擴散級聯(lián)。根據(jù)信息擴散理論，影響力隨社交鏈逐層遞減，處于影響擴散鏈底層節(jié)點不僅受與其直接相連的上級朋友節(jié)點的影響，同時與高層節(jié)點之間存在間接的影響力傳遞。影響力擴散模型不能真實刻畫影響力在社交網絡中的傳遞，以該模型模擬影響力在網絡中的傳播存在一定誤差，故本文引入信任度傳遞函數(shù)[17]，以便能夠更加真實地對社交網絡中的影響力傳播進行仿真模擬。

定義2 節(jié)點信任度函數(shù)。每個節(jié)點的信任度函數(shù)用二元組λ=(t,d)表示，其中t,d∈[0,1]，信任傳遞函數(shù)二元組的第一部分為節(jié)點信任度，第二部分為節(jié)點不信任度。社交網絡上的信任度函數(shù)集合用Λ={λ=(t,d)│t,d∈[0,1] }≡[0,1]2表示。

節(jié)點信任度函數(shù)二元組為衡量節(jié)點的局部屬性，其第一部分表示以該節(jié)點為中心與其直接連接節(jié)點構成的最小連通子圖的相對信任度，節(jié)點信任度越高表明該節(jié)點在其最小連通子圖中能夠以較大概率影響(激活)其鄰居節(jié)點。由于間接影響力傳遞機制的存在，也會促使鄰居節(jié)點的朋友繼續(xù)將影響力傳遞下去；第二部分相反，則是衡量的節(jié)點在最小連通子圖中的相對不信任度。在影響力傳播過程中，即使激活態(tài)節(jié)點將影響力傳遞給了社交鏈中下一級的非激活態(tài)節(jié)點(即成功激活其鄰居)，如激活態(tài)節(jié)點具有較高的不信任度，其鄰居節(jié)點會抗拒將影響力傳播給該鄰居節(jié)點的朋友。

影響力在社交網絡中的傳播機制的實質是節(jié)點間信任度的交互，信任度較高的節(jié)點們更容易達成共識從而達到影響力最大化的效果。為了刻畫影響力傳播過程中節(jié)點間信任傳遞機制，本文引用三角模(Triangularnorms)與三角余模(Triangularconorms)的概念[16]。若函數(shù)T∶[0,1]2→[0,1]當且僅當滿足交換性、結合律、單調性并且同時對?x滿足邊界條件T(x,1)=x，則T函數(shù)成為三角模。若函數(shù)S∶[0,1]2→[0,1]當且僅當滿足交換性、結合律、單調性并且同時對?x滿足邊界條件S(x,0)=x，則S函數(shù)成為三角余模。在本文中采用Einstein乘積?ε作為三角模，采用Einstein求和⊕ε作為三角余模，本文使用上述兩種函數(shù)作為信任傳遞函數(shù)，對于?(a,b)∈[0,1]2，有如下計算公式：

(2)

(3)

三角模為最小化算子，而三角余模為最大化算子，上述兩種運算具有如下性質：

E?(x1,x2)≤min{x1,x2}

(4)

max{x1,x2}≤E⊕(x1,x2)

(5)

現(xiàn)有影響力傳播模型中的信任傳遞機制并未考慮到不信任度在具有3個節(jié)點及以上構成的影響傳播鏈中的傳播。更重要的一點，并未考慮到影響力在社交網絡中傳播時的信任度衰減問題?？紤]影響力在現(xiàn)實社交網絡中的傳遞存在信任度減少而不信任度增加的現(xiàn)象，為了實現(xiàn)信任度衰減、不信任度增加機制，本文利用Einstein乘積?ε與Einstein求和⊕ε作為雙向信任傳遞算子。

定義3 信任度傳遞指數(shù)。令Λ為節(jié)點信任度函數(shù)集合。構造信任雙向傳遞算子PD∶Λ×Λ→Λ，信任雙向傳遞算子連接兩個具有直接連接的投票節(jié)點，其信任度函數(shù)分別為λ1=(t1,d1)，λ2=(t2,d2)，則信任傳遞指數(shù)為：

PD(λ1,λ2)=(E?(t1,t2) ,E⊕(d1,d2))=

(6)

定義2利用Einstein乘積?ε與Einstein求和⊕ε構建雙向信任傳遞算子，由于滿足E?(t1,t2)≤min{t1,t2}與max{d1,d2}≤E⊕(d1,d2)性質，該算子PD分別實現(xiàn)了影響力傳播過程中的信任度減少而不信任度增加的信任度傳遞機制。信任傳遞算子PD具有以下性質：

(1)交換性：

PD(λ2,λ1)=(E?(t1,t2) ,E⊕(d1,d2))=

PD(λ1,λ2)

(7)

(2)結合律：

PD(PD(λ1,λ2),λ3)=

PD[(E?(t1,t2) ,E⊕(d1,d2)),(t3,d3) ]=

(E?(E?(t1,t2),t3),E?(E?(d1,d2),d3))=

(E?(t1,E?(t2,t3)),E?(d1,E?(d2,d3)))=

PD(λ1,PD(λ2,λ3))

(8)

(4)邊界條件：對于信任傳遞算子PD的邊界條件，對信任度與不信任度分別討論。

全信任傳遞：當λ1=(1,0)時，有PD((1,0),λ2)=(t2,d2)=λ2。當λ2=(1,0)時，根據(jù)交換律有PD(λ1,(1,0))=(t1,d1)=λ1。在一個具有3個節(jié)點{A,B,C}的影響力傳播鏈中，當A節(jié)點對B節(jié)點具有完全信任度時，則B節(jié)點對C節(jié)點的影響力程度完全以A節(jié)點為主導。

全不信任傳遞：當λ1=(0,1)時，有PD((0,1),λ2)=(0,1)；根據(jù)交換性，當λ2=(0,1)時，有PD(λ1,(0,1))=(0,1)；在具有全不信任度的節(jié)點為中心構成的最小連通子圖中，該節(jié)點將不受任何具有直接連接朋友的影響。

圖3展示了具有3個節(jié)點的影響力傳播過程中的信任傳遞鏈，圖3(a)中為3個節(jié)點的完全連通圖，每個節(jié)點之間都具有實際的社交鏈接，則節(jié)點之間的信任傳遞根據(jù)上述信任傳遞算子直接可計算節(jié)點之間的信任度與不信任度；若影響力以線性鏈式傳播，如圖3(b)所示，構造了一條從B→A→C的影響力傳播鏈，實際上節(jié)點B與節(jié)點C之間不僅存在實際的相互影響同時存在間接的信任傳遞，故B與C之間通過虛線進行相連來代表C節(jié)點收到B節(jié)點具有的二階擴散級聯(lián)的影響。

圖3 影響力傳播中的信任傳播鏈

(9)

通過節(jié)點間的信任度傳遞機制，可計算兩個節(jié)點間的影響力擴散系數(shù)，該系數(shù)衡量了兩個具有直接連接的節(jié)點中激活態(tài)節(jié)點不能夠激活鄰居節(jié)點的概率。

1.3 信任度傳遞下最大影響力節(jié)點挖掘

影響力最大化旨在從網絡中識別k個節(jié)點，使得通過這k個節(jié)點在某種影響力傳播機制下產生的影響傳播范圍最大。前兩節(jié)說明了基于非回退矩陣的社交網絡表示圖模型與影響力在社交網絡的傳播機制。在此基礎上，采用滲流理論的思想針對最大影響力節(jié)點進行挖掘。傳統(tǒng)的識別k個影響力傳播節(jié)點算法中，并未提出一個全局的明確的影響力最大化函數(shù)，其次均假設節(jié)點重要性程度與節(jié)點的影響力成正相關，故忽略了節(jié)點之間的影響力聯(lián)合傳播?；跐B流理論的k個影響力最大化節(jié)點挖掘一定程度上避免了傳統(tǒng)挖掘算法的缺點，不僅考慮節(jié)點重要性程度，同時引入聯(lián)合影響強度的概念，將節(jié)點之間的聯(lián)合影響因素考慮在內。

設向量n=(n1,n2,…,nN)代表網絡中節(jié)點是否為影響力節(jié)點的標記向量，其中：

(10)

則影響力節(jié)點在網絡中所占比例為：

(11)

滲流理論將影響力最大化節(jié)點挖掘過程看做不斷從網絡節(jié)點中移除qc個“超級影響力”節(jié)點及其連邊，使得影響力不能在網絡中擴散，其中qc為從網絡中移除節(jié)點的比例，即“超級影響力”節(jié)點的比例。設G(q)為在具有q個“超級影響力”節(jié)點的網絡中當影響力擴散行為結束后網絡中未曾受到影響節(jié)點的平均概率。設v=(v1,v2,…,vN)，其中vi為節(jié)點i最終不受影響概率，即在當t→∞時節(jié)點i為非激活態(tài)的概率，G(q)的表達式為：

(12)

故可將影響力最大化節(jié)點挖掘轉化為最優(yōu)滲流問題，尋找最優(yōu)qc比例的“超級影響力”節(jié)點(移除節(jié)點)使得最終網絡中為受影響力節(jié)點的概率G(qc)最小，問題的數(shù)學形式化表達如下：

qc=min{q∈[0,1]:minG(q)}

(13)

當q≥qc時，社交網絡存在一系列影響力聯(lián)合擴散節(jié)點集合，使得影響力由這一系列節(jié)點擴散至整個網絡。當q≤qc時，說明社交網絡存在小型孤立局域世界使得影響力不能擴散至整個網絡。

為了衡量某個節(jié)點在網絡中的實際影響力，考慮虛擬地移除該節(jié)點，并考察移除該節(jié)點前后影響力傳遞的情況。設兩個具有直接關聯(lián)的節(jié)點i與j，引入標記vi→j表示當虛擬移除j節(jié)點時，節(jié)點i最終不被影響的概率。以節(jié)點i為中心的局部影響力擴散樹的數(shù)學形式化表達如下：

(14)

(15)

當節(jié)點i本身為影響力節(jié)點，即ni=0，顯而易見vi→j=0；當節(jié)點i為非影響力節(jié)點，即ni=1時，該節(jié)點最終是否被激活的概率與周邊節(jié)點有關。其中wk→i為當節(jié)點w的鄰居節(jié)點i被虛擬移除時，節(jié)點k的局部平均影響力擴散系數(shù)；?ij為虛擬的移除節(jié)點j后的節(jié)點i的鄰居節(jié)點集合。

上述局部影響力擴散模型中，可以驗證對于所有i→j,i,j∈N，{vi→j=0}是全局穩(wěn)定解。依據(jù)非回退矩陣，上述模型可構建2M×2M個可閉合的方程組，為了求解全局最優(yōu)n，引入線型操作算子：

(16)

(17)

1→22→12→32→53→23→43→54→35→25→35→66→51→200n2w1→2n2 w1→2000000002→10000000000002→300000n3w2→3n3w2→3000002→5000000000n5w5→3n5w2→503→20n2w3→20n2w3→2000000003→40000000000003→500000000n5w3→50n5w3→504→30000n3w4→30n3w4→3000005→20n2w5→2n2w5→20000000005→30000n3w5→3n3w5→30000005→60000000000006→500000000n5w6→5n5w6→500

(18)

最優(yōu)“超級影響力”節(jié)點比例qc滿足以下等式：

(19)

(20)

(21)

上式中，Zi=∑t∈?iwi→t，|w0(n)|2=2∑i,jIS(λi,λj)，Ball(i,)為以i節(jié)點為中心、影響力階數(shù)為半徑的朋友圈邊界節(jié)點，P(i,j)為節(jié)點i到階數(shù)的朋友圈邊界節(jié)點j的所經路徑節(jié)點。影響力階數(shù)衡量了兩個社交節(jié)點之間聯(lián)合傳播的平均可達條件，具體表現(xiàn)為其中一個影響力節(jié)點需經過條路徑才與另一影響力節(jié)點聯(lián)合傳播。

為了求解上述最小化最大特征值問題，即最大化節(jié)點影響力，考慮兩個“超級影響力”節(jié)點i與j之間能夠聯(lián)合傳播，則這兩個節(jié)點之間應滿足距離可達，則nk=1,k∈P(i,j)，故可定義節(jié)點在影響力階數(shù)下的聯(lián)合影響強度。

定義5 節(jié)點聯(lián)合影響強度。給定節(jié)點影響力階數(shù)，則節(jié)點i的聯(lián)合影響力強度如下：

(22)

為了更快地挖掘“超級影響力”節(jié)點，本文采取貪婪算法的思想：總是移除網絡中節(jié)點聯(lián)合強度更大的節(jié)點及其連邊，直至挖掘qc比例的影響力節(jié)點。具體算法流程如下：

Step 1:初始化節(jié)點是否為影響力節(jié)點標記向量n=(n1,n2,…,nN)=0；給定影響力階數(shù)；

CI算法通過移除有限比例的節(jié)點，算法的時間復雜度為O(NlogN)。針對大規(guī)模復雜社交網絡的影響力分析，CI算法能夠快速搜索影響力節(jié)點。

2 數(shù)值實驗

本文采用的兩種數(shù)據(jù)集如表1所示。

表1 數(shù)據(jù)集網絡參數(shù)

圖4所示人造網絡生成節(jié)點的數(shù)量參數(shù)為50，邊連接概率為0.2。圖5所示Netscience數(shù)據(jù)集為現(xiàn)實網絡，該網絡用于描述科學家合作關系，其度分布存在明顯的冪率特性。本文將節(jié)點信任度二元組引入影響力最大化節(jié)點挖掘算法，由于節(jié)點信任度測度不是本文研究的重點，故利用線性同余發(fā)生器生成[0,1]內均勻分布的隨機數(shù)作為信息在網絡傳播過程中的節(jié)點初始信任度與不信任度。

圖4 人造均勻網絡

圖5 Netscience網絡

2.1 影響力最大化節(jié)點實驗

根據(jù)2.3節(jié)對基于滲流理論的最大化節(jié)點挖掘算法的描述，不同網絡的節(jié)點挖掘特征值閾值如表2所示。

表2 各網絡下特征值閾值及挖掘節(jié)點比例

圖6與圖7展示了隨著聯(lián)合影響力強度最大節(jié)點被移除網絡后，帶權非回退矩陣的最大特征值的變化情況。對于均勻網絡，選擇不同的影響力階數(shù)對于特征值閾值的變化與挖掘節(jié)點比例無顯著變化；而對于Netscience冪率網絡，根據(jù)選擇影響力階數(shù)的不同導致特征值閾值的變化區(qū)間非常大，同時挖掘節(jié)點比例也不一致，數(shù)據(jù)表明2階影響力階數(shù)的影響力挖掘能夠極大地減少挖掘影響力節(jié)點的個數(shù)，同時根據(jù)圖中2階的特征值變化曲線情況，在挖掘到滿足特征值閾值的節(jié)點后，特征值以指數(shù)速度遞減為0，說明信息能夠更快傳播到整個網絡。

圖6 特征值變化曲線(Netscience)

圖7 特征值變化曲線(均勻網絡)

2.2 影響力最大化算法比較試驗

本文選擇基于滲流影響力理論的影響力最大化算法、節(jié)點度、節(jié)點特征向量中心性、接近度中心性作為選擇影響力最大化節(jié)點挖掘算法，來挖掘人造均勻網絡與Netscience網絡下的影響力節(jié)點。用來衡量每個節(jié)點的影響力強度指標分別為：聯(lián)合影響力強度、度、特征值、接近度中心值。表3展示了人工均勻網絡下的指標強度前3的節(jié)點數(shù)據(jù)，表4展示了Netscience網絡下的前3指標強度的節(jié)點數(shù)據(jù)。

表3 均勻網絡前3影響力強度指標

表4 Netscience網絡前3影響力強度指標

為了比較不同影響力最大化算法的性能，以不同算法選擇的影響力最大化節(jié)點作為線型閾值模型的種子節(jié)點，考察當模型收斂后影響力的擴散率。圖8與圖9分別展示了Netscience網絡與人造均勻網絡下的影響力擴散率，結果顯示在均勻網絡下的擴散率的大小程度為：改進滲流理論影響力挖掘算法≥傳統(tǒng)滲流理論的影響力節(jié)點挖掘算法≥度中心性≥特征向量中心性≥接近度中心性。故在均勻網絡下使用本文所提影響力挖掘算法與度中心性、特征向量中心性的擴散效用相近，但顯著高于接近度中心性；而在Netscience冪率網絡下，基于滲流理論的影響力挖掘算法在線型閾值模型迭代收斂后的擴散率顯著高于其他影響力算法，同時能夠在極小的迭代次數(shù)內使算法達到收斂，即網絡中已不存在能夠被激活的節(jié)點。

圖8 Netscience網絡下的擴散率

圖9 人造均勻網絡下的擴散率

引入信任度傳遞機制下的滲流理論挖掘算法略優(yōu)于傳統(tǒng)基于滲流理論影響力最大化算法，雖影響擴散速率相近，但能提升最終影響力擴散率上限。其次滲流理論下的影響力挖掘對于均勻網絡下影響階數(shù)對擴散率及擴散速率影響不大，而對于真實網絡中選擇合適的聯(lián)合影響階數(shù)能夠略微提升影響力最大化性能，Netscience網絡下選擇1階聯(lián)合指數(shù)能夠極大提升影響力擴散率上限。

3 結論

本文利用非回退矩陣構建社交網絡圖模型，突破了最大影響力節(jié)點挖掘算法在傳統(tǒng)鄰接矩陣稀疏網絡上的局限性，同時用信任度傳遞函數(shù)刻畫影響力傳播過程中“信任度減少不信任度增加”現(xiàn)象，在此基礎上采用滲流理論對影響力節(jié)點進行挖掘，并提出節(jié)點聯(lián)合影響傳播強度指數(shù)刻畫節(jié)點影響力大小。利用本文所提算法與傳統(tǒng)啟發(fā)式算法(度中心性、接近度中心性、特征向量中心性)挖掘出的影響力最大節(jié)點集合作為線型閾值模型的種子節(jié)點，考察其擴散率與擴散速度，結果表明本文算法擴散率與擴散速度均普遍高于其他啟發(fā)式算法。