西安交通大學(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)

2、題描述如下：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ì)網(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

3、e）代表人與人之間的關(guān)系。如果兩節(jié)點(diǎn)之間的關(guān)系S0 中的所有節(jié)點(diǎn)，以及在 t1 時(shí)刻被激活的所有節(jié)點(diǎn)。……在 t 時(shí)刻， 集合 St?1 中的節(jié)點(diǎn) v∈St-1 可以將信息以概率 p 傳播給它們未被激活的鄰居節(jié)點(diǎn) u?St-1 。如果傳播成功，即 u 被激活，則 u 將被加入 t 時(shí)刻的激活集合 St 。 集合 St 包含 u?St-1 中的所有節(jié)點(diǎn)， 以及在 t 時(shí)刻被激活的所有節(jié)點(diǎn)。不同節(jié)點(diǎn)的激活過(guò)程相互獨(dú)立，互不影響。已被激活的節(jié)

4、點(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:1179m=1;n=1;for j=1:1377if e(i,1)>v(j,1)n=n+1;elseif e(i,1)>v(j,1)n=n+1;elsem=m;n=n;endendlj(m,n)=1;End //