社會網(wǎng)絡(luò)中的信息傳播優(yōu)化

1、西安交通大學(xué)Xian Jiao Tong University (XJTU)論文題目：社會網(wǎng)絡(luò)中的信息傳播優(yōu)化專業(yè) 班級：作者 學(xué)號：社會網(wǎng)絡(luò)中的信息傳播優(yōu)化摘要本次實(shí)驗(yàn)基于獨(dú)立級聯(lián)模型，假定傳播概率均為p=1,以CELF算法為基礎(chǔ)，用鄰接表儲存社會網(wǎng)絡(luò)圖，通過提出影響力因子，改進(jìn)算法，完成了對給定社會網(wǎng)絡(luò)圖的信息傳播優(yōu)化。關(guān)鍵詞：獨(dú)立級聯(lián)模型 CELF 影響力因子 鄰接表引言信息爆炸的時代，任何人都不能獨(dú)善其身，置于信息網(wǎng)絡(luò)之外，在網(wǎng)絡(luò)搭建的交際圈中，我們無時無刻不在處于接受、發(fā)送信息的狀態(tài)。正是因?yàn)槿绱?，誕生了一種新的營銷模式病毒營銷。病毒營銷（viral marketing，又稱病毒式營

2、銷、病毒性營銷、基因行銷或核爆式行銷），是一種常用的網(wǎng)絡(luò)營銷方法，常用于進(jìn)行網(wǎng)站推廣、品牌推廣等。考慮到營銷成本，為使?fàn)I銷成本最低，需要找出特定的、數(shù)量較少的營銷初始點(diǎn)，但需要達(dá)到營銷效果較大化(在此不考慮明星價值的高額性）。為此，需要優(yōu)化信息在社會網(wǎng)絡(luò)中的傳播。一、 社會網(wǎng)絡(luò)社會網(wǎng)絡(luò)是指社會個體成員之間因?yàn)榛佣纬傻南鄬Ψ€(wěn)定的關(guān)系體系。一個社會網(wǎng)絡(luò)（如微博）可以用一張圖來表示，其中節(jié)點(diǎn)（node）代表人，邊（edge）代表人與人之間的關(guān)注關(guān)系，邊的方向?yàn)樾畔鞑シ较颍ū魂P(guān)注）。信息在社會網(wǎng)絡(luò)中以個人節(jié)點(diǎn)為載體，沿著節(jié)點(diǎn)之間的邊進(jìn)行傳播。信息傳播的方向與邊的指向一致。在網(wǎng)絡(luò)中，從不同節(jié)點(diǎn)開始

3、傳播的信息，其傳播效果可能大不相同。有向圖：信息的傳播是單向的；無向圖：信息的傳播是雙向的。二、社會網(wǎng)絡(luò)中信息優(yōu)化傳播的模型在以往的研究中，關(guān)于社會網(wǎng)絡(luò)信息傳播優(yōu)化的研究模型較為流行的主要有獨(dú)立級聯(lián)模型和線性閾值模型。本次實(shí)驗(yàn)主要采用獨(dú)立級聯(lián)模型，故只對獨(dú)立級聯(lián)模型進(jìn)行相關(guān)的介紹。級聯(lián)模型是哥登伯格最早提出的。在級聯(lián)模型中,每個節(jié)點(diǎn)在自身轉(zhuǎn)變?yōu)榛顒訝顟B(tài)后,都有一定概率機(jī)會去激活其鄰居節(jié)點(diǎn)。如果成功,則在下一步,其鄰居節(jié)點(diǎn)變?yōu)榛顒訝顟B(tài)。而后，其鄰居節(jié)點(diǎn)再去激活與其相連的節(jié)點(diǎn)，如此反復(fù)，直到?jīng)]有新的節(jié)點(diǎn)被激活時，傳播停止。獨(dú)立級聯(lián)模型是級聯(lián)模型的一種簡單形式。在獨(dú)立級聯(lián)模型中,節(jié)點(diǎn)在“獨(dú)立地”接受

4、某一個新活動鄰居節(jié)點(diǎn)的擴(kuò)散影響,而與其他節(jié)點(diǎn)的擴(kuò)散影響無關(guān)。三、本次實(shí)驗(yàn)的研究對象 本次實(shí)驗(yàn)主要通過對給定的較小模式的社會網(wǎng)絡(luò)圖進(jìn)行處理，從而完成實(shí)驗(yàn)的兩個要求。本次實(shí)驗(yàn)的社會網(wǎng)絡(luò)圖包括1377個點(diǎn)和2279條邊，具體的社會網(wǎng)絡(luò)圖如下：社會網(wǎng)絡(luò)圖 待解決的問題：1.如何選擇10個初始節(jié)點(diǎn)，使得信息的傳播范圍最廣？2.如果希望信息的傳播能覆蓋800個以上的節(jié)點(diǎn)，則最少應(yīng)該選擇哪些用戶作為傳播的起始節(jié)點(diǎn)？四、問題的簡化與影響力因子問題的簡化：假定傳播的概率都相等，且傳播時無阻尼，即p=1。影響力因子：在本次實(shí)驗(yàn)中，社會網(wǎng)絡(luò)圖以鄰接表的形式儲存，影響力因子是基于每一個節(jié)點(diǎn)所對應(yīng)的鄰接表的長度提出的。

5、用字母b表示該因子。b是一個可變量，其表征相應(yīng)的節(jié)點(diǎn)在所有節(jié)點(diǎn)中傳播范圍的大小，其受到其他節(jié)點(diǎn)的制約，具體計(jì)算方法如下：其中為第個節(jié)點(diǎn)的鄰接表的子集。五、模型的建立在影響力因子的提出基礎(chǔ)上，利用01 規(guī)劃，可以很容易的建立以下兩個模型：（其中a表示0或1，b表示影響力因子）針對問題1：針對問題2：模型的分析：通過對模型的分析，求解該模型可轉(zhuǎn)移到對影響力因子的求解。六、模型的求解算法以下兩個算法都是在CELF算法的基礎(chǔ)上進(jìn)行設(shè)計(jì)的，關(guān)于算法的可行性，理論和實(shí)踐證明，CELF是可行的，在解決NP-hard問題上，CELF算法得出的解可達(dá)到最優(yōu)解的63%。算法1：初始化：nodes=vi|i1,2,

6、.1377;final nodes=；final array=(final_array中將儲存將要找到的節(jié)點(diǎn)，final_nodes中將儲存final_array中的節(jié)點(diǎn)作為初始節(jié)點(diǎn)能夠激活的總的節(jié)點(diǎn)）。Step1:尋找影響力因子最大的節(jié)點(diǎn)，將其作為初始節(jié)點(diǎn)：將圖以鄰接表的形式儲存起來，找出鄰接表最長的節(jié)點(diǎn)，將其歸入集合final_array中，并將其從集合nodes中刪除。另外將該節(jié)點(diǎn)對應(yīng)的鄰接表中的節(jié)點(diǎn)歸入到final_nodes中。Step2：處于集合nodes中的節(jié)點(diǎn)對應(yīng)的鄰接表與final_nodes做差集，得出新的鄰接表，重新計(jì)算每個節(jié)點(diǎn)的影響力因子，找出影響力因子最大的節(jié)點(diǎn)，將其

7、歸入final_array中，將其對應(yīng)的鄰接表與final_nodes做并集，得到新的集合final_nodes，并從nodes中刪除該節(jié)點(diǎn)。Step3：重復(fù)步驟2九次后停止。 算法2：初始化：nodes=vi|i1,2,.1377;final nodes=；final array=(final_array中將儲存將要找到的節(jié)點(diǎn)，final_nodes中將儲存final_array中的節(jié)點(diǎn)作為初始節(jié)點(diǎn)能夠激活的總的節(jié)點(diǎn)）。Step1:尋找影響力因子最大的節(jié)點(diǎn)，將其作為初始節(jié)點(diǎn)：將圖以鄰接表的形式儲存起來，找出鄰接表最長的節(jié)點(diǎn)，將其歸入集合final_array中，并將其從集合nodes中刪除。另外將該節(jié)點(diǎn)對應(yīng)的鄰接表中的節(jié)點(diǎn)歸入到final_nodes中，若length(final_nodes)=800,停止計(jì)算，否則進(jìn)入下一步。Step2：處于集合nodes中的節(jié)點(diǎn)對應(yīng)的鄰接表與final_nodes做差集，得出新的鄰接表，重新計(jì)算每個節(jié)點(diǎn)的影響力因子，找出影響力因子最大的節(jié)點(diǎn)，將其歸入final_array中，將其對應(yīng)的鄰接表與final_nodes做并集，得到新的集合final_nodes，并從nodes中刪除該節(jié)點(diǎn)。Step3：若length（final_nod