西安交通大學(xué)運(yùn)籌學(xué)大作業(yè)報(bào)告

1、運(yùn)籌學(xué)大作業(yè)報(bào)告 【問(wèn)題】給定一個(gè)弱連通的有向網(wǎng)絡(luò)，包含 1377 個(gè)節(jié)點(diǎn)network_nodes.txt和 2279條邊network_edges.txt。此次的信息傳播優(yōu)化問(wèn)題描述如下：1. 如何選擇 10 個(gè)初始節(jié)點(diǎn)，使得信息的傳播范圍最廣？【關(guān)鍵詞】社會(huì)網(wǎng)絡(luò)、信息傳播、獨(dú)立級(jí)聯(lián)模型【研究背景】社會(huì)網(wǎng)絡(luò)社會(huì)網(wǎng)絡(luò)是指社會(huì)個(gè)體成員之間因?yàn)榛?dòng)而形成的相對(duì)穩(wěn)定的關(guān)系體系。社會(huì)網(wǎng)絡(luò)以個(gè)人為節(jié)點(diǎn)node構(gòu)成社會(huì)結(jié)構(gòu)，人與人之間通過(guò)相互依賴關(guān)系聯(lián)結(jié)起來(lái)。相互依賴關(guān)系可能是朋友關(guān)系、同學(xué)關(guān)系、生意伙伴關(guān)系、種族信仰關(guān)系等。一個(gè)社會(huì)網(wǎng)絡(luò)可以用一張網(wǎng)絡(luò)圖來(lái)表示， 其中節(jié)點(diǎn) node 代表人， 邊 edg

2、e代表人與人之間的關(guān)系。如果兩節(jié)點(diǎn)之間的關(guān)系是雙方對(duì)等的例如朋友關(guān)系、同學(xué)關(guān)系等 ，那么邊為無(wú)向邊；如果兩節(jié)點(diǎn)之間的關(guān)系是不對(duì)等的例如微博的關(guān)注關(guān)系、論文的引用關(guān)系等 ，那么邊為有向邊，從一個(gè)節(jié)點(diǎn)指向另一個(gè)節(jié)點(diǎn)。社會(huì)網(wǎng)絡(luò)中的信息傳播信息在社會(huì)網(wǎng)絡(luò)中以個(gè)人節(jié)點(diǎn)為載體，沿著節(jié)點(diǎn)之間的邊進(jìn)行傳播。信息傳播的方向與邊的指向一致。在網(wǎng)絡(luò)中，從不同節(jié)點(diǎn)開(kāi)始傳播的信息，其傳播效果可能大不相同。社會(huì)網(wǎng)絡(luò)中的信息傳播優(yōu)化問(wèn)題所要討論的就是如何選擇起始的傳播節(jié)點(diǎn)，使得信息能獲得最大范圍的傳播或到達(dá)指定的范圍。獨(dú)立級(jí)聯(lián)模型社會(huì)網(wǎng)絡(luò)中的信息傳播過(guò)程可以用獨(dú)立級(jí)聯(lián)模型來(lái)描述。該模型將整個(gè)社會(huì)網(wǎng)絡(luò)看做一個(gè)有向圖 G( V

3、, E) ，其中 V 是所有節(jié)點(diǎn)的集合， E 是所有邊的集合。 每條邊有一個(gè)傳播概率 p,0 p 1 ， 即信息有概率 p 可以沿著某條邊從一個(gè)節(jié)點(diǎn)傳播到另一個(gè)節(jié)點(diǎn)。在此假設(shè)所有邊的傳播概率都相同。信息傳播的過(guò)程如下：在 t =0 時(shí)刻，信息從某些節(jié)點(diǎn)開(kāi)始第一次傳播。這些初始節(jié)點(diǎn)被認(rèn)為是處于激活狀態(tài)，構(gòu)成初始激活集合S0 。在 t =1 時(shí)刻，集合S0 中的節(jié)點(diǎn)vS0 可以將信息以概率 p 傳播給它們未被激活的鄰居節(jié)點(diǎn)u S0 鄰居節(jié)點(diǎn)即有邊與之相連的節(jié)點(diǎn)，信息傳播方向與邊的指向一致 。如果傳播成功，即 u 被激活，那么 u 將被參加 t =1 時(shí)刻的激活集合S1 。集合S1 包含S0 中的所

4、有節(jié)點(diǎn)，以及在t1 時(shí)刻被激活的所有節(jié)點(diǎn)。在 t 時(shí)刻， 集合St1中的節(jié)點(diǎn)vSt-1 可以將信息以概率 p 傳播給它們未被激活的鄰居節(jié)點(diǎn)uSt-1 。如果傳播成功，即 u 被激活，那么 u 將被參加 t 時(shí)刻的激活集合St 。 集合St 包含uSt-1 中的所有節(jié)點(diǎn)， 以及在 t 時(shí)刻被激活的所有節(jié)點(diǎn)。不同節(jié)點(diǎn)的激活過(guò)程相互獨(dú)立，互不影響。已被激活的節(jié)點(diǎn)將永遠(yuǎn)處于激活狀態(tài)，未被激活的節(jié)點(diǎn)不具備記憶性，下一次有同樣的概率 p 被激活。當(dāng)網(wǎng)絡(luò)中沒(méi)有新的節(jié)點(diǎn)被激活時(shí)，傳播過(guò)程停止?！境绦颉縧j=zeros(1377,1377);for i=1:1179 m=1; n=1; for j=1:1377

5、 if e(i,1)v(j,1)&e(i,2)v(j,1) m=m+1;n=n+1; elseif e(i,1)v(j,1)&e(i,2)=v(j,1) m=m+1;n=n; elseif e(i,1)v(j,1) m=m;n=n+1; else m=m;n=n; end end lj(m,n)=1;End /建立鄰接矩陣，把節(jié)點(diǎn)按從小到大排列并把有向圖的邊化為鄰接矩陣上的點(diǎn)，例如第i個(gè)節(jié)點(diǎn)到第j個(gè)節(jié)點(diǎn)有邊，那么lji，j=1s=zeros(1377,1377);for k=1:1377 s(k,k)=1; for c=1:8 for q=1:1377 if s(k,q)=1 for i=1:

6、1377 if lj(q,i)=1&s(k,i)=0 r= fix(rand(1)*4); if r=0 s(k,i)=1; end end end end end endEnd /建立一個(gè)s矩陣，第i行代表第i個(gè)節(jié)點(diǎn)作為起始點(diǎn)，對(duì)應(yīng)的第j列為是否把信息傳到達(dá)第j個(gè)節(jié)點(diǎn)。對(duì)于每個(gè)節(jié)點(diǎn)作為起始點(diǎn)進(jìn)行遍歷，對(duì)于每一次循環(huán)，查找該行中的1元素，表示該元素接受到信息，再對(duì)該元素在lj矩陣中進(jìn)行查找，如果有以該元素起始的邊，那么在0-4中生成一個(gè)隨機(jī)數(shù)r，如果r=0，表示 傳遞成功，把邊的終止節(jié)點(diǎn)在s矩陣中對(duì)應(yīng)的值賦值為1quan=sum(s=0,2);u,i=sort(quan);sj=nchoose

7、k(1:18,10);for hang=1:43758 ui=0; for lie=1:10 yuan=sj(hang,lie); weizhi=1378-yuan; ywz=i(weizhi); io=s(ywz,:); ui=ui+io; end yui=sum(ui=0,2); tyu(hang,1)=yui;endzdz,a=max(tyu);ans=sj(a,:);bjs=1378 1378 1378 1378 1378 1378 1378 1378 1378 1378;fans=bjs-ans;for kll=1:10 qwer=fans(1,kll); ffans(kll,1)=

8、i(qwer);endfor dcv=1:10 tttt=ffans(dcv,1); fffans(dcv,1)=gg(tttt);endffansfffanszdz/比擬s矩陣中每一行非零元的個(gè)數(shù)即為每個(gè)元素作為起始元素時(shí)所能傳播的范圍，我們?nèi)∽畲蟮?8個(gè)節(jié)點(diǎn)，對(duì)這個(gè)18個(gè)數(shù)中取10個(gè)的組合進(jìn)行窮舉，計(jì)算每一個(gè)組合中10個(gè)節(jié)點(diǎn)在s矩陣中對(duì)應(yīng)行的和，再計(jì)算非零元個(gè)數(shù)，得出最大值，并通過(guò)找出最大值所對(duì)應(yīng)的組合，來(lái)斷定最大值所對(duì)應(yīng)的節(jié)點(diǎn)，由于matlab顯示數(shù)據(jù)有位數(shù)限制，我們?cè)趀xcel中對(duì)數(shù)據(jù)進(jìn)行排序，通過(guò)對(duì)應(yīng)的位置找出數(shù)據(jù)【結(jié)果與分析】測(cè)試效果欠佳，一些點(diǎn)不太準(zhǔn)確。但計(jì)算速度很快，實(shí)時(shí)性好。改良方法，增加模擬次數(shù)，取最終結(jié)果中出現(xiàn)頻率最高的十個(gè)點(diǎn)，可以減小隨機(jī)誤差?！究偨Y(jié)】這次我們小組運(yùn)用獨(dú)立級(jí)聯(lián)模型來(lái)解決社會(huì)網(wǎng)絡(luò)中的信息傳播優(yōu)化問(wèn)題。剛開(kāi)始的時(shí)候我們想通過(guò)計(jì)算期望的方法來(lái)研究不同初始點(diǎn)開(kāi)始傳播信息對(duì)社會(huì)網(wǎng)絡(luò)的影響，但這種方法運(yùn)算量大，不利于快速處理，后來(lái)我們想到用Matlab生成隨機(jī)數(shù)的方法來(lái)代替?zhèn)鞑ジ怕?，模擬傳播過(guò)程，這種方法比擬簡(jiǎn)便，但卻具有較大的隨機(jī)誤差，在選取