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