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

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

2、keting，又稱、或核爆式行銷），是的網(wǎng)絡(luò)營銷，常用于進行網(wǎng)站推廣、品牌推廣等?？紤]到營銷成本，為使營銷成本最低，需要找出特定的、數(shù)量較少的營銷初始點，但需要達到營銷效果較大化(在此不考慮明星價值的高額性）。為此，需要優(yōu)化信息在社會網(wǎng)絡(luò)中的傳播。一、 社會網(wǎng)絡(luò)社會網(wǎng)絡(luò)是指社會個體成員之間因為互動而形成的相對穩(wěn)定的關(guān)系體系。一個社會網(wǎng)絡(luò)（如微博）可以用一張圖來表示，其中節(jié)點（node）代表人，邊（edge）代表人與人之間的關(guān)注關(guān)系，邊的方向為信息傳播方向（被關(guān)注）。信息在社會網(wǎng)絡(luò)中以個人節(jié)點為載體，沿著節(jié)點之間的邊進行傳播。信息傳播的方向與邊的指向一致。在網(wǎng)絡(luò)中，從不同節(jié)點開始傳播的信息，其傳

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

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

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

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

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

8、的鄰接表中的節(jié)點歸入到final_nodes中，若length(final_nodes)>=800,停止計算，否則進入下一步。Step2：處于集合nodes中的節(jié)點對應(yīng)的鄰接表與final_nodes做差集，得出新的鄰接表，重新計算每個節(jié)點的影響力因子，找出影響力因子最大的節(jié)點，將其歸入final_array中，將其對應(yīng)的鄰接表與final_nodes做并集，得到新的集合final_nodes，并從nodes中刪除該節(jié)點。Step3：若length（final_nodes）<800，轉(zhuǎn)回步驟2，否則停止計算。七、程序設(shè)計本次實驗的程序采用python語言編寫，運行平臺為Ubuntu

9、64 python 2.7.6 編譯平臺,虛擬機內(nèi)存為1G，PC機主頻2.4GHZ，運行時間為：問題1：1.5s;問題2：20s左右.具體代碼見代碼段附錄。八、實驗結(jié)果問題1：想要使得信息的傳播范圍最廣，可選的是個節(jié)點為：, , , , , , , , , ；最終的傳播范圍為97個節(jié)點。問題2：若要使得傳播范圍達到800個節(jié)點，需要的初始節(jié)點為525個，其中125個節(jié)點可以使得傳播范圍達到400個節(jié)點，其他的400個點影響力因子僅為1.九、實驗的改進與拓展本次實驗是基于獨立級聯(lián)模型且p=1，由于信息在社會網(wǎng)絡(luò)圖中傳播會遇到一定的阻力，不可能以p=1的概率將信息傳播下去，所以本次實驗假設(shè)p=1這

10、一假設(shè)條件過于理想化。參考文獻：1宮秀文. 社交網(wǎng)絡(luò)影響力最大化傳播模型與算法研究D.安徽師范大學(xué),2014.2馬寅. 社會網(wǎng)絡(luò)影響力最大化算法及傳播模型的研究D.蘭州大學(xué),2012.附錄（代碼）：算法1：class item: def _init_(self): =0; self.list=; self.influence=1;import xlrdfrom collections import Counterimport timestartTimeStamp=time.time()file_name=xlrd.open_workbook('/home/shitou

11、he/Desktop/DATA.xls');table1=file_name.sheets()0;table2=file_name.sheets()1;num11=table1.nrows;num12=table1.ncols;num21=table2.ncols;num22=table2.nrows;print table1.nrows ,table2.ncolsarc=0 for col in range(num21) for row in range(num22)for i in range(0,num12): nodes=table1.col_values(i);for i i

12、n range(0,len(nodes): nodesi=int(nodesi);arc1=table2.col_values(0);arc2=table2.col_values(1);for i in range(0,num22): arc1i=int(arc1i); arc2i=int(arc2i);print len(list(set(arc1).intersection(set(arc2)arc1.extend(arc2);print len(arc1),len(arc2)for i in range(0,num22): for j in range(0,num21): arcij=i

13、nt(table2.cell(i,j).value);"first delete the isolate nodes"arc1=list(set(arc1)nodes=list(set(nodes)print len(arc1),len(nodes)print list(set(nodes).difference(set(arc1)"above resulte indicate there is no isolate nodes""next we will find a node which has the greatest influence

14、""compute the influence of every nodes"node=table1.col_values(0);for i in range(len(node): nodei=int(nodei);for i in range(num11): nodesi=item(); =nodei;print array=for i in range(num11): nodesi.list.append(nodei); for j in range(num22): if arcj0=: nod

15、esi.list.append(arcj1); for k in range(i): if in nodesk.list: nodesk.list.append(arcj1) if arcj1=: nodesi.list.extend(nodesk.list); for i in range(num11): nodesi.influence=len(list(set(nodesi.list); #print nodesi.influence array.append(nodesi.influence)print (Counter(array)a=m

16、ax(array)nodes_max=array.index(a)print 'the initial node is:' ,nodesnodes_"now we have found the node which has the greatest influence""next we will find the other 9 nodes"array1=final_array=for i in range(nodesnodes_max.influence): final_array.append(nodesnodes_m

17、ax.listi);final_nodes=;final_nodes.append(nodesnodes_);print len(final_array)for i in range(9): for j in range(num11): nodesj.list=list(set(nodesj.list).difference(set(final_array) nodesj.influence=len(nodesj.list); array1.append(nodesj.influence); a=max(array1) nodes_max=array1.index(a) for

18、 k in range(nodesnodes_max.influence): final_array.append(nodesnodes_max.listk) final_nodes.append(nodesnodes_) #print len(final_array) #print 'we choose the node:', nodesnodes_ array1=print len(set(final_array),final_nodesendTimeStamp=time.time()print endTimeStamp-startTimeS

19、tamp算法2：class item: def _init_(self): =0; self.list=; self.influence=1;import xlrdfrom collections import Counterimport timestart=time.time()file_name=xlrd.open_workbook('/home/shitouhe/Desktop/DATA.xls');table1=file_name.sheets()0;table2=file_name.sheets()1;num11=table1.nrows;num12

20、=table1.ncols;num21=table2.ncols;num22=table2.nrows;print table1.nrows ,table2.ncolsarc=0 for col in range(num21) for row in range(num22)for i in range(0,num12): nodes=table1.col_values(i);for i in range(0,len(nodes): nodesi=int(nodesi);arc1=table2.col_values(0);arc2=table2.col_values(1);for i in ra

21、nge(0,num22): arc1i=int(arc1i); arc2i=int(arc2i);arc1.extend(arc2);print len(arc1),len(arc2)for i in range(0,num22): for j in range(0,num21): arcij=int(table2.cell(i,j).value);"first delete the isolate nodes"arc1=list(set(arc1)nodes=list(set(nodes)print len(arc1),len(nodes)print list(set(n

22、odes).difference(set(arc1)"above results indicate there is no isolate nodes""next we will find a node which has the greatest influence""compute the influence of every nodes"node=table1.col_values(0);for i in range(len(node): nodei=int(nodei);for i in range(num11): nodes

23、i=item(); =nodei;print array=for i in range(num11): nodesi.list.append(nodei); for j in range(num22): if arcj0=: nodesi.list.append(arcj1); for k in range(i): if in nodesk.list: nodesk.list.append(arcj1) if arcj1=: nodesi.list.extend(nodesk.lis

24、t); for i in range(num11): nodesi.influence=len(list(set(nodesi.list); #print nodesi.influence array.append(nodesi.influence)a=max(array)nodes_max=array.index(a)print arraynodes_maxprint 'the initial node is:' ,nodesnodes_"now we have found the node which has the greatest influence""next we will find the other 9 nodes"influence=influence.append(nodesnodes_max.inf