西安交通大學(xué)運籌學(xué)大作業(yè)報告

1、運籌學(xué)大作業(yè)報告作者： 【問題】給定一個弱連通的有向網(wǎng)絡(luò)，包含 1377 個節(jié)點（network_nodes.txt）和 2279 條邊（network_edges.txt） 。此次的信息傳播優(yōu)化問

2、題描述如下：1. 如何選擇 10 個初始節(jié)點，使得信息的傳播范圍最廣？【關(guān)鍵詞】社會網(wǎng)絡(luò)、信息傳播、獨立級聯(lián)模型【研究背景】社會網(wǎng)絡(luò) 社會網(wǎng)絡(luò)社會網(wǎng)絡(luò)是指社會個體成員之間因為互動而形成的相對穩(wěn)定的關(guān)系體系。社會網(wǎng)絡(luò)以個人為節(jié)點（node）構(gòu)成社會結(jié)構(gòu)，人與人之間通過相互依賴關(guān)系聯(lián)結(jié)起來。相互依賴關(guān)系可能是朋友關(guān)系、同學(xué)關(guān)系、生意伙伴關(guān)系、種族信仰關(guān)系等。一個社會網(wǎng)絡(luò)可以用一張網(wǎng)絡(luò)圖來表示， 其中節(jié)點 （node） 代表人， 邊 （edg

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

4、點將永遠(yuǎn)處于激活狀態(tài)，未被激活的節(jié)點不具備記憶性，下一次有同樣的概率 p 被激活。當(dāng)網(wǎng)絡(luò)中沒有新的節(jié)點被激活時，傳播過程停止。【程序】lj=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 //