基于prp的社交網(wǎng)絡(luò)信息傳播模型

基于prp的社交網(wǎng)絡(luò)信息傳播模型

1信息傳播模型社交媒體網(wǎng)絡(luò)的影響是指人們接受他人信息的過程。在該領(lǐng)域中,Domingos和Richardson提出了社交網(wǎng)絡(luò)影響最大化問題,用圖來表示社交網(wǎng)絡(luò)。我們的目標(biāo)是在圖中找出最具有影響力的k個(gè)節(jié)點(diǎn),使得最終社交網(wǎng)絡(luò)中被影響的節(jié)點(diǎn)最多,信息傳播范圍最大。信息在社交網(wǎng)絡(luò)傳播過程中都遵循一定的規(guī)則,我們稱之為信息傳播模型。隨著社交網(wǎng)絡(luò)的出現(xiàn)及流行,社交網(wǎng)絡(luò)影響力成為目前研究的熱點(diǎn)。在不同的傳播模型基礎(chǔ)上,研究影響最大化問題很有意義。目前已存在一些基本傳播模型,如線性閾值模型(LinearThresholdModel,簡稱LT模型)、獨(dú)立級聯(lián)模型(IndependentCascadeModel,簡稱IC模型)和加權(quán)級聯(lián)模型(WeightedCascadeModel,簡稱WC模型)。此外,還有一些重要傳播模型,比如熱傳播模型,但是這些模型都沒有考慮網(wǎng)絡(luò)中節(jié)點(diǎn)的相關(guān)性和重要性,我們認(rèn)為網(wǎng)絡(luò)中節(jié)點(diǎn)的相關(guān)性和重要性是衡量其影響力的一個(gè)重要指標(biāo),基于此,本文提出了一種基于網(wǎng)頁排名算法的信息傳播模型(PRP),并在該模型下利用貪心算法來近似求解影響最大化問題。實(shí)驗(yàn)表明,在本文提出的模型下解決影響最大化問題的效果比傳統(tǒng)的傳播模型更好,影響力范圍更大。本文第2節(jié)介紹相關(guān)工作;第3節(jié)介紹一些理論基礎(chǔ)知識;第4節(jié)介紹提出的PRP模型與尋找Top-k節(jié)點(diǎn)的貪心算法;第5節(jié)介紹在4個(gè)不同數(shù)據(jù)集上進(jìn)行的實(shí)驗(yàn)及結(jié)果分析;最后進(jìn)行工作總結(jié)并展望下一步工作。2社交網(wǎng)絡(luò)的影響力最大化問題社交網(wǎng)絡(luò)影響力模型問題最近成為社交網(wǎng)絡(luò)分析的熱點(diǎn),社交網(wǎng)絡(luò)中一個(gè)重要的問題是影響力最大化問題。為了解決影響最大化問題,目前已有一些基本的信息傳播模型,下面簡要介紹LT模型、IC模型及WC模型。2.1節(jié)點(diǎn)閾值線性閾值模型來源于數(shù)學(xué)研究,是以接受者為中心的模型。在LT模型中,節(jié)點(diǎn)v的所有活躍父節(jié)點(diǎn)u以權(quán)重ω(u,v)影響子節(jié)點(diǎn)v,且∑u∈Γt(v)ωu,v≤1∑u∈Γt(v)ωu,v≤1,其中Γt(v)表示t時(shí)刻節(jié)點(diǎn)v活躍父節(jié)點(diǎn)的集合。給定活躍節(jié)點(diǎn)的初始集合A,則信息按照如下過程進(jìn)行傳播:①對任意節(jié)點(diǎn)v∈V,從區(qū)間隨機(jī)選擇一個(gè)閾值θv;②在傳播t時(shí)刻,所有活躍父節(jié)點(diǎn)u以權(quán)重ω(u,v)影響所有非活躍子節(jié)點(diǎn)v;③如果v的所有活躍父節(jié)點(diǎn)對其影響的權(quán)重之和大于等于v的閾值θv,即,∑u∈Γt(v)ωu,v≥θv∑u∈Γt(v)ωu,v≥θv,那么非活躍節(jié)點(diǎn)v將在第t+1時(shí)刻變成活躍節(jié)點(diǎn);④如果沒有更多的節(jié)點(diǎn)被激活,那么該傳播過程終止。閾值θv表示當(dāng)父節(jié)點(diǎn)u為活躍節(jié)點(diǎn)(該節(jié)點(diǎn)接受某個(gè)觀點(diǎn)或購買了某個(gè)商品)時(shí),其子節(jié)點(diǎn)v同樣成為活躍節(jié)點(diǎn)的潛在傾向的不同。LT模型是一個(gè)與0-1分布有關(guān)的概率模型,節(jié)點(diǎn)的閾值選取是隨機(jī)的。對于一個(gè)活躍節(jié)點(diǎn)初始集合A(?V),用φ(A)表示隨機(jī)激活過程結(jié)束時(shí)活躍節(jié)點(diǎn)的個(gè)數(shù),φ(A)是一個(gè)隨機(jī)變量,用δ(A)表示φ(A)的期望值,我們稱δ(A)為初始集合A的影響度。2.2激活節(jié)點(diǎn)傳播獨(dú)立級聯(lián)模型是以發(fā)送者為中心的模型,是基于概率理論里面的交互粒子系(ParticleSystems)設(shè)計(jì)的一個(gè)信息擴(kuò)散模型。在獨(dú)立級聯(lián)模型中,首先為每條有向邊(u,v)選擇一個(gè)實(shí)數(shù)值pu,v∈,pu,v表示u通過邊(u,v)成功影響v的概率。給定活躍節(jié)點(diǎn)的初始集A,活躍節(jié)點(diǎn)傳播過程按照如下規(guī)則進(jìn)行:①當(dāng)在第t時(shí)刻,節(jié)點(diǎn)u為活躍節(jié)點(diǎn),它只有唯一一次機(jī)會(huì)激活它的每個(gè)非活躍的節(jié)點(diǎn)v,且激活成功的概率為pu,v,如果u成功激活v,則v將在t+1時(shí)刻成為活躍節(jié)點(diǎn);②如果節(jié)點(diǎn)v在t時(shí)刻有多個(gè)活躍的父節(jié)點(diǎn)u,則活躍父節(jié)點(diǎn)u均在t時(shí)刻以任意順序嘗試激活v;③無論u是否能夠激活v,在后面的回合中u都不能再嘗試激活v;④信息在整個(gè)社交網(wǎng)絡(luò)中的傳播過程一直持續(xù)到?jīng)]有新的激活可能發(fā)生為止。在IC模型中,信息通過有向邊(u,v)傳播成功的概率pu,v是隨機(jī)的,對于活躍節(jié)點(diǎn)初始集合A(?V),用隨機(jī)變量φ(A)表示激活過程結(jié)束時(shí)活躍節(jié)點(diǎn)的個(gè)數(shù),用δ(A)表示φ(A)的期望值,我們稱δ(A)為初始集合A的影響度。2.3加權(quán)級聯(lián)模型在獨(dú)立級聯(lián)模型中,激活概率pu,v沒有考慮節(jié)點(diǎn)的度。然而,度較高的節(jié)點(diǎn)影響與被影響的概率都較高,基于此,KempeD,KleinbergJ,TardosE提出了加權(quán)級聯(lián)模型,度數(shù)高的節(jié)點(diǎn)關(guān)聯(lián)的邊被賦予較低的激活概率,節(jié)點(diǎn)u激活節(jié)點(diǎn)v的概率為pu,v=1/dv,dv表示節(jié)點(diǎn)v的度。在加權(quán)級聯(lián)模型中,信息通過有向邊(u,v)傳播成功的概率pu,v與節(jié)點(diǎn)v的度有關(guān),對于活躍節(jié)點(diǎn)初始集合A(?V),用隨機(jī)變量φ(A)表示激活過程結(jié)束時(shí)活躍節(jié)點(diǎn)的個(gè)數(shù),用δ(A)表示φ(A)的期望值,那么我們稱δ(A)為初始集合A的影響度。3理論基礎(chǔ)3.1社交網(wǎng)絡(luò)的運(yùn)行社交網(wǎng)絡(luò)(SocialNetworks)影響最大化問題,是指找到最具有影響力的k個(gè)節(jié)點(diǎn)集合,這些節(jié)點(diǎn)能最大范圍地將信息傳播到社交網(wǎng)絡(luò)的其他部分。用有向圖G表示社交網(wǎng)絡(luò),假設(shè)在G中,初始活躍節(jié)點(diǎn)集合為A(A?V),集合A之外的所有用戶節(jié)點(diǎn)都是非活躍的,RS(A)表示社交網(wǎng)絡(luò)中最終活躍節(jié)點(diǎn)的集合,則初始節(jié)點(diǎn)集合A的影響力范圍可以定義如下:φ(A)=|RS(A)|,φ(A)表示最終活躍的用戶節(jié)點(diǎn)數(shù)目。本文將影響最大化問題表示為一個(gè)離散最優(yōu)化問題,定義如下:在社交網(wǎng)絡(luò)G中,給定參數(shù)k,信息按照特定的傳播模型在G中傳播。找到一個(gè)包含有k個(gè)用戶的初始集合A,使得A最終影響的范圍最大,即社交網(wǎng)絡(luò)中最終活躍的用戶節(jié)點(diǎn)數(shù)目最多,亦即φ(A)最大。3.2android的初始頁面pj算法PageRank稱為網(wǎng)頁排名,又稱網(wǎng)頁級別、Google左側(cè)排名或佩奇排名,是一種由搜索引擎根據(jù)網(wǎng)頁之間相互的超鏈接計(jì)算的技術(shù),該技術(shù)由Google創(chuàng)始人拉里·佩奇和謝爾蓋·布林于1998年在斯坦福大學(xué)研發(fā)。Google用它來體現(xiàn)網(wǎng)頁的相關(guān)性和重要性,而本文正利用網(wǎng)頁排名的這個(gè)特性來體現(xiàn)社交網(wǎng)絡(luò)中節(jié)點(diǎn)的相關(guān)性和重要性。PageRank通過網(wǎng)絡(luò)浩瀚的超鏈接關(guān)系來確定一個(gè)頁面的等級,把從A頁面到B頁面的鏈接解釋為A頁面給B頁面投票,根據(jù)投票來源(甚至來源的來源,即鏈接到A頁面的頁面)和投票目標(biāo)的等級來決定新的等級。簡單地說,一個(gè)高等級的頁面可以使其他低等級頁面的等級提升。本文用PageRank值來表示節(jié)點(diǎn)的相關(guān)性和重要性。下面介紹PageRank算法,假設(shè)一個(gè)由4個(gè)頁面組成的小團(tuán)體:A,B,C和D,如果所有頁面都鏈向A,那么A的PR(PageRank)值就是B,C,D的PageRank值之和,即PR(A)=PR(B)+PR(C)+PR(D)。假設(shè)B也有到C的鏈接,并且D也有鏈接到包括A的3個(gè)頁面,一個(gè)頁面不能投票2次,所以B給每個(gè)頁面半票。以同樣的邏輯,D投出的票只有三分之一算到了A的PageRank值上,此時(shí)A的PageRank值為ΡR(A)=ΡR(B)2+ΡR(C)1+ΡR(D)3PR(A)=PR(B)2+PR(C)1+PR(D)3,即根據(jù)鏈出頁面總數(shù)平分一個(gè)頁面的PR值,L(X)表示從X鏈出頁面的數(shù)量,ΡR(A)=ΡR(B)L(B)+ΡR(C)L(C)+ΡR(D)L(D)PR(A)=PR(B)L(B)+PR(C)L(C)+PR(D)L(D)。為了對那些有鏈出的頁面公平,規(guī)定q=0.85(這里的q被稱為阻尼系數(shù)(dampingfactor),其意義是,在任意時(shí)刻,用戶到達(dá)某頁面后并繼續(xù)向后瀏覽的概率。1-q=0.15就是用戶停止點(diǎn)擊,隨機(jī)跳到新URL的概率)。q=0.85的PageRank算法被用到了所有頁面上,表示頁面可能被上網(wǎng)者放入書簽的概率。下面的算法,沒有鏈入頁面的PageRank值會(huì)是0,所以Google通過數(shù)學(xué)系統(tǒng)給了每個(gè)頁面一個(gè)初始PageRank值。計(jì)算公式如式(1)所示。ΡageRank(pi)=1-qΝ+q∑pjΡageRank(pj)L(pj)(1)PageRank(pi)=1?qN+q∑pjPageRank(pj)L(pj)(1)式中,p1,p2,…,pN是被研究的頁面,網(wǎng)絡(luò)中存在由頁面pj指向pi的鏈接,L(pj)是pj鏈出頁面的數(shù)量,N是所有頁面的數(shù)量。所有頁面的PageRank值是一個(gè)特殊矩陣中的特征向量,這個(gè)特征向量為R=[ΡageRank(p1)ΡageRank(p2)?ΡageRank(pΝ)],其表示為式(2)所示。R=[(1-q)/Ν(1-q)/Ν?(1-q)/Ν]+q[?(p1,p1)?(p1,p2)??(p1,pΝ)?(p2,p1)???(pi,pj)?(pΝ,p1)?(pΝ,pΝ)](2)式中,?(pi,pj)=1L(pj),如果pj不鏈向pi,且對每個(gè)j都成立,那么l(pi,pj)等于0,且Ν∑i=1?(pi,pj)=1。因此,一個(gè)頁面的PageRank值是由其他頁面的PageRank值計(jì)算得到的,PageRank算法不斷重復(fù)計(jì)算每個(gè)頁面的PageRank值,如果給每個(gè)頁面一個(gè)隨機(jī)的PageRank值(非0),那么經(jīng)過不斷地重復(fù)計(jì)算,這些頁面的PageRank值會(huì)趨向于正常和穩(wěn)定。4prp模型和k節(jié)點(diǎn)找不到的心理算法4.1vi父節(jié)點(diǎn)狀態(tài)由于傳統(tǒng)傳播模型沒有考慮節(jié)點(diǎn)的相關(guān)性和重要性,而節(jié)點(diǎn)的權(quán)威性則是衡量影響力的重要因素,因此,本文提出了一種基于網(wǎng)頁排名的傳播模型(PRP模型)。本文用有向圖G表示社交網(wǎng)絡(luò),用EG表示圖G中邊的集合,用PageRank值表示節(jié)點(diǎn)的權(quán)威性,PageRank值越高的父節(jié)點(diǎn)對其子節(jié)點(diǎn)的影響力越大。首先計(jì)算出圖G中每個(gè)節(jié)點(diǎn)的PageRank值,用pi表示節(jié)點(diǎn)vi的PageRank值,pji表示節(jié)點(diǎn)vi第j個(gè)父節(jié)點(diǎn)的PageRank值,用parenti表示vi父親節(jié)點(diǎn)的集合,用ωji表示有向邊(vj,vi)上的權(quán)重。我們定義ωji如下,如果有從vj鏈向vi的邊,那么ωji等于vj的PageRank值與所有鏈向vi父節(jié)點(diǎn)的PageRank值之和的比值;如果沒有從vj鏈向vi的邊,那么ωji等于0。我們可以用式(3)表示ωji:ωji={pji∑k∈parentipk,(vj,vi)∈EG0(vj,vi)?EG(3)在初始時(shí)刻,將圖中每個(gè)節(jié)點(diǎn)都置為0狀態(tài)。當(dāng)t時(shí)刻,信息開始在社交網(wǎng)絡(luò)中傳播,此時(shí)將信息傳播源節(jié)點(diǎn)的狀態(tài)都設(shè)置為1,傳播源節(jié)點(diǎn)將在t+1時(shí)刻把信息傳給其子節(jié)點(diǎn),如果子節(jié)點(diǎn)被影響成功,則其狀態(tài)由0變?yōu)?且不可逆,否則子節(jié)點(diǎn)的狀態(tài)仍為0。社交網(wǎng)絡(luò)中有兩類節(jié)點(diǎn)不會(huì)被影響:一類是沒有父節(jié)點(diǎn)的節(jié)點(diǎn);另一類是從傳播源節(jié)點(diǎn)開始沒有傳播路徑的節(jié)點(diǎn)。而在社交網(wǎng)絡(luò)中,有3類節(jié)點(diǎn)是穩(wěn)定的節(jié)點(diǎn):第一類是傳播源節(jié)點(diǎn),狀態(tài)始終為1;第二類是永遠(yuǎn)不會(huì)被影響到的節(jié)點(diǎn),狀態(tài)始終為0;第三類是已經(jīng)被信息影響過的節(jié)點(diǎn),已知該節(jié)點(diǎn)是否被成功影響,其狀態(tài)已確定。如果兩個(gè)節(jié)點(diǎn)之間有環(huán),需要先確定一個(gè)節(jié)點(diǎn)的狀態(tài),另一個(gè)節(jié)點(diǎn)就可以等其所有父節(jié)點(diǎn)全部穩(wěn)定后確定是否接受信息,從而避免死鎖發(fā)生。當(dāng)在t時(shí)刻,vi所有父節(jié)點(diǎn)狀態(tài)都是穩(wěn)定的,用parent1it表示t時(shí)刻狀態(tài)為1的所有vi父節(jié)點(diǎn)集合,用parent0it表示t時(shí)刻狀態(tài)為0的所有vi父節(jié)點(diǎn)集合。那么,在t+1時(shí)刻,vi被其父節(jié)點(diǎn)影響成功的概率為∑vj∈parent1itωji,即在t+1時(shí)刻vi狀態(tài)變?yōu)?的概率;否則,vi沒有被影響成功,狀態(tài)為0的概率為∑vj∈parent0itωji。因此,t+1時(shí)刻vi的狀態(tài)可表示成式(4)。ft+1(vi)={1,p1=∑vj∈parent1itωji0,p0=∑vj∈parent0itωji(4)式中,ft+1(vi)表示t+1時(shí)刻vi的狀態(tài),p1表示t+1時(shí)刻vi被影響成功的概率,p0表示t+1時(shí)刻vi沒有被影響成功的概率。4.2影響最大邊際效益的節(jié)點(diǎn)選擇算法貪心算法是由D.Kempel提出的,我們基于貪心算法尋找Top-k節(jié)點(diǎn)來解決影響最大化問題。為了找到種子集S,一個(gè)有效的方法是每一步根據(jù)貪心算法的標(biāo)準(zhǔn)確定初始集合中的一個(gè)節(jié)點(diǎn),直到找到k個(gè)節(jié)點(diǎn)為止。從空的初始集合開始,每次將使得影響范圍函數(shù)獲得最大邊際效益的節(jié)點(diǎn)加入初始集合,如算法1所示。算法1尋找Top-k節(jié)點(diǎn)的貪心算法輸入:有向圖G,最終擴(kuò)散集合大小k輸出:集合大小為k的種子集S1.初始化:S=?,R=100002.fori=1tokdo/*尋找k個(gè)種子節(jié)點(diǎn)*/3.foreachvertexv∈V\Sdo/*選擇邊際效益均值最大的節(jié)點(diǎn)*/4.sv=0/*將邊際效益值初始化*/5.fort=1toRdo/*計(jì)算t時(shí)刻節(jié)點(diǎn)的邊際效益*/6.sv+=|RS(S∪{v})|-|RS(S)|/*結(jié)點(diǎn)v在所有時(shí)刻的邊際效益總和*/7.endfor8.sv=svR/*結(jié)點(diǎn)v的平均邊際效益*/9.endfor10.S=S∪{argmaxv∈V\S{sv}}/*將邊際效益均值最大的節(jié)點(diǎn)并入初始集合中*/11.endfor算法1中,首先定義S=?;RS(S)表示集合S擴(kuò)散后社交網(wǎng)絡(luò)被激活的節(jié)點(diǎn)的集合;并定義sv=|RS(S∪{v})|-|RS(S)|表示節(jié)點(diǎn)v的邊際效益影響范圍函數(shù)。從初始集合S=?開始,每一步都選擇使得當(dāng)前影響范圍函數(shù)獲得最大邊際效益的節(jié)點(diǎn),選擇策略如下:根據(jù)局部最優(yōu)策略,對集合V\S中所有的節(jié)點(diǎn),依次計(jì)算t=1,t=2,…,t=R時(shí)刻節(jié)點(diǎn)的邊際效益,并對這些時(shí)刻的邊際效益求均值,最后選擇使邊際效益均值最大的節(jié)點(diǎn)u,即u=argmaxv∈V\S{sv},將u并入集合S中,即S=S∪{u}。經(jīng)過k步,我們就選擇了k個(gè)影響范圍最大的節(jié)點(diǎn)。5實(shí)驗(yàn)與評估5.1平臺數(shù)據(jù)集內(nèi)容本文實(shí)驗(yàn)是在4個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行的,下面介紹本文使用的4個(gè)數(shù)據(jù)集。數(shù)據(jù)集1是個(gè)物理領(lǐng)域的合作者網(wǎng)絡(luò),節(jié)點(diǎn)表示研究者,邊表示研究者之間的合作關(guān)系,本數(shù)據(jù)集有10748個(gè)節(jié)點(diǎn)、53000條邊。數(shù)據(jù)集2來自社群服務(wù)平臺Flickr1,數(shù)據(jù)集的實(shí)體有用戶以及他們的關(guān)系,包含用戶文件和關(guān)系文件,我們的實(shí)驗(yàn)從本數(shù)據(jù)集抽取11328個(gè)節(jié)點(diǎn)、54870條邊。數(shù)據(jù)集3來源于MemeTracker,是一個(gè)在線新聞網(wǎng)絡(luò),節(jié)點(diǎn)表示新聞門戶或新聞博客,邊表示網(wǎng)站之間的影響關(guān)系,本數(shù)據(jù)集有339936個(gè)節(jié)點(diǎn)、1574596條邊。數(shù)據(jù)集4是一個(gè)社會(huì)新聞分享和投票的網(wǎng)站2,數(shù)據(jù)集里包含不同實(shí)體和這些實(shí)體之間的聯(lián)系,我們的實(shí)驗(yàn)從本數(shù)據(jù)集抽取了10536個(gè)節(jié)點(diǎn)、52400條邊。5.2算法仿真實(shí)驗(yàn)本實(shí)驗(yàn)的基準(zhǔn)比較模型是第2節(jié)相關(guān)工作中提到的線性閾值模型、獨(dú)立級聯(lián)模型和加權(quán)級聯(lián)模型。我們基于4.2小節(jié)給出的貪心算法,在4個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。設(shè)定目標(biāo)集合大小k分別為0,5,10,15,20,25,30,然后觀察本文提出的網(wǎng)頁排名傳播模型以及基準(zhǔn)比較模型的影響范圍。5.3網(wǎng)頁排名模型影響范圍的比較數(shù)據(jù)集1的實(shí)驗(yàn)結(jié)果見圖1,從圖1中可以觀察出當(dāng)k值為15時(shí),網(wǎng)頁排名模型的影響范圍只比線性閾值模型的影響范圍略低,而比另外兩個(gè)基準(zhǔn)模型的影響范圍高;當(dāng)k取其它值時(shí),網(wǎng)頁排名模型的影響范圍比所有基準(zhǔn)比較模