引入信任度傳遞機(jī)制的影響力最大化節(jié)點(diǎn)挖掘

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

(1. 西南科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 四川綿陽 621010； 2. 西南科技大學(xué)理學(xué)院 四川綿陽 621010)

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

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

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

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

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

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

1.1 基于非回退矩陣的社交網(wǎng)絡(luò)表示圖模型

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

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

定義1[14-15]設(shè)網(wǎng)絡(luò)具有N個(gè)節(jié)點(diǎn)，M條邊，則非回退矩陣B為2M×2M的非對(duì)稱矩陣，其元素取值為：

(1)

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

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

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

圖1 社交網(wǎng)絡(luò)

1.2 基于信任度的影響力傳播機(jī)制

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

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

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

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

圖2 獨(dú)立級(jí)聯(lián)模型

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

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

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

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

(2)

(3)

三角模為最小化算子，而三角余模為最大化算子，上述兩種運(yùn)算具有如下性質(zhì)：

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

(4)

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

(5)

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

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

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

(6)

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

(1)交換性：

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

PD(λ1,λ2)

(7)

(2)結(jié)合律：

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)邊界條件：對(duì)于信任傳遞算子PD的邊界條件，對(duì)信任度與不信任度分別討論。

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

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

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

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

(9)

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

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

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

設(shè)向量n=(n1,n2,…,nN)代表網(wǎng)絡(luò)中節(jié)點(diǎn)是否為影響力節(jié)點(diǎn)的標(biāo)記向量，其中：

(10)

則影響力節(jié)點(diǎn)在網(wǎng)絡(luò)中所占比例為：

(11)

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

(12)

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

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

(13)

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

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

(14)

(15)

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

上述局部影響力擴(kuò)散模型中，可以驗(yàn)證對(duì)于所有i→j,i,j∈N，{vi→j=0}是全局穩(wěn)定解。依據(jù)非回退矩陣，上述模型可構(gòu)建2M×2M個(gè)可閉合的方程組，為了求解全局最優(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)“超級(jí)影響力”節(jié)點(diǎn)比例qc滿足以下等式：

(19)

(20)

(21)

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

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

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

(22)

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

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

CI算法通過移除有限比例的節(jié)點(diǎn)，算法的時(shí)間復(fù)雜度為O(NlogN)。針對(duì)大規(guī)模復(fù)雜社交網(wǎng)絡(luò)的影響力分析，CI算法能夠快速搜索影響力節(jié)點(diǎn)。

2 數(shù)值實(shí)驗(yàn)

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

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

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

圖4 人造均勻網(wǎng)絡(luò)

圖5 Netscience網(wǎng)絡(luò)

2.1 影響力最大化節(jié)點(diǎn)實(shí)驗(yàn)

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

表2 各網(wǎng)絡(luò)下特征值閾值及挖掘節(jié)點(diǎn)比例

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

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

圖7 特征值變化曲線(均勻網(wǎng)絡(luò))

2.2 影響力最大化算法比較試驗(yàn)

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

表3 均勻網(wǎng)絡(luò)前3影響力強(qiáng)度指標(biāo)

表4 Netscience網(wǎng)絡(luò)前3影響力強(qiáng)度指標(biāo)

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

圖8 Netscience網(wǎng)絡(luò)下的擴(kuò)散率

圖9 人造均勻網(wǎng)絡(luò)下的擴(kuò)散率

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

3 結(jié)論

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