網絡中信息的傳播

網絡中信息的傳播主要內容第一部分傳染病模型第二部分信息級聯模型第三部分博弈演化第四部分網絡結構與信息傳播一、傳染病模型

社會關系網絡中，信息如何傳播、用戶觀點如何交互演化等問題受到研究者們的關注．在社會關系網絡上信息傳播研究中，研究者們認為社會關系網絡上的信息傳播與傳染病在人群的擴散類似，因此經典信息傳播模型是SIR模型和SIS模型，它們都以傳染性疾病傳播為問題原型．SIR及其改進模型在研究信息傳播方面得到廣泛應用，但是在信息傳播過程中依賴于網絡用戶的信息傳播行為，網絡用戶不僅是信息的接受者，同時也是信息的傳播者．網絡用戶信息需求得到滿足之后，會根據其自身的經驗以及與其他用戶的交互所得到的信息進行判斷，然后根據判斷結果進行行為決策，從而使得網絡信息再次傳播．一、傳染病模型1、SI、SIS、SIR模型1.1在SI模型中,節(jié)點有兩種狀態(tài)：S(Susceptible)易感態(tài)表示該節(jié)點可能被其鄰居節(jié)點中處于感染態(tài)的節(jié)點感染。I(Infected)感染態(tài)表示節(jié)點被感染.節(jié)點一旦被感染,就會永遠處于感染態(tài)初始時刻單個節(jié)點作為感染源（將單個節(jié)點的狀態(tài)設為I態(tài)，其他節(jié)點設為S態(tài)）以p的概率去感染其節(jié)點,可以觀測不同時間時網絡中被感染節(jié)點的數量,從而得到該節(jié)點的傳播速度.

tT=1tT=10一、傳染病模型算法1.1SI模型模擬圖G中的信息傳播一、傳染病模型Python實現，T=10，beta=0.1,以3號節(jié)點作為初始感染節(jié)點為例一、傳染病模型1.1SI模型模擬圖G中的信息傳播一、傳染病模型1.2SIS模型

在SIS模型中,節(jié)點可以被反復感染.處于I感染態(tài)的節(jié)點可能會重新變?yōu)镾易感態(tài)。1.3SIR模型在SIR模型中，節(jié)點除了有上述兩種狀態(tài)外，還有第３種免疫R狀態(tài)．免疫狀態(tài)是說，節(jié)點受到感染被治愈后具有了免疫性，不再被感染，也不會感染其它節(jié)點。一、傳染病模型1、SIR在傳染病動力學中，主要沿用的由Kermack與McKendrick在1927年用動力學的方法建立了SIR傳染病模型。直到現在SIR模型仍被廣泛地使用和不斷發(fā)展。易感者(susceptibles)，其數量記為S(t)，表示t時刻未染病但有可能被該類疾病傳染的人數；染病者(infectives)，其數量記為I(t)，表示t時刻已被感染成為病人而且具有傳染力的人數；恢復者(recovered)，其數量記為R(t)，表示t時刻已從染病者中移出的人數。設總人口為N(t)，則有N(t)=S(t)+I(t)+R(t)。一、傳染病模型SIR模型的建立基于以下三個假設：⑴不考慮人口的出生、死亡、流動等種群動力因素。人口始終保持一個常數，即N(t)≡K。⑵一個病人一旦與易感者接觸就必然具有一定的傳染力。假設t時刻單位時間內，一個病人能傳染的易感者數目與此環(huán)境內易感者總數S(t)成正比，比例系數為β，從而在t時刻單位時間內被所有病人傳染的人數為βS(t)。⑶t時刻，單位時間內從染病者中移出的人數與病人數量成正比，比例系數為γ，單位時間內移出者的數量為γI(t)。一、傳染病模型

SIR基礎模型用微分方程組表示如下：

一、傳染病模型

可通過對SIR模型的分析和解的漸近性態(tài)來初步研究傳染病的流行規(guī)律。SIR模型是比較簡單粗糙的模型，這個模型得到了歷史上發(fā)生過的大規(guī)模的傳染病，如上個世紀初在印度孟買發(fā)生的瘟疫數據的有力支持。后來很多研究人員對SIR模型做了推廣。 在不考慮出生與死亡等種群動力學因素的情況下，傳染病若無潛伏期，動力學模型可表示為：(1)SI模型，患病后難以治愈；(2)SIS模型，患病后可以治愈，恢復者不具有免疫力；(3)SIR模型，患病者治愈后獲利終身免疫力；(4)SIRS模型，病人康復后只有暫時免疫力，單位時間內將有部分康復者喪失免疫力而可能再次被感染。 傳染病動力學模型不僅可用于傳染病研究，而且也可用于生物種群分布、植病、寄生蟲病、新技術的傳播和擴散、網絡病毒的傳播、謠言的傳播等自然和社會科學問題的研究，反之其他學科，如流體動力學、分子化學反應擴散等的研究方法也可被借鑒來用于傳染病擴散的研究。一、傳染病模型SIR模型一、傳染病模型算法1.2SIR模型模擬圖G中的信息傳播一、傳染病模型SIR模型二、信息級聯模型獨立級聯模型（ICM）在該模型中，每個初始激活節(jié)點會產生自己獨立的擴散級聯，級聯之間是互相獨立、互不干擾的.在一個有向或無向圖上，任何一條邊(u，v)都被分配一個屬于[0,1]之間的特定值PU,V，這個值代表邊(u,v)上的擴散概率.初始時，部分節(jié)點被激活，信息這些節(jié)點開始擴散.在時間t，每個當前激活的節(jié)點u都會以一定概率PU,V去激活它的每個鄰居節(jié)點v．如果在時刻t，節(jié)點v的多個鄰居節(jié)點要激活它，這些鄰居節(jié)點會隨機排列地去嘗試激活，所有激活嘗試都在時刻t內完成．無論鄰居節(jié)點u是否成功，在隨后的時刻都不能再去激活v．如果v在t時刻被激活，那么該節(jié)點會在t＋1時刻去激活它的鄰居們．該進程直到不再有激活行為發(fā)生而終止.二、信息級聯模型ICM與SIR的區(qū)別

沒有T變量算法2.1ICM模型二、信息級聯模型二、信息級聯模型終止條件：所有激活態(tài)節(jié)點都完成嘗試激活其鄰居節(jié)點二、信息級聯模型級聯范圍最大化（影響力最大化）背景

假設存在一個用戶網絡,某公司想要在此用戶網絡中進行產品營銷。公司的預算有限，因此營銷不能覆蓋所有用戶。然而，一旦覆蓋的用戶發(fā)現產品不錯，他們可以向朋友（近鄰）宣傳此產品。他們的朋友也會將此產品宣傳給自己的鄰居。隨著這個過程持續(xù)進行，有關此產品的消息將會在網絡中大肆傳播開來。該公司計劃選擇一批初始用戶，使得最終了解這個產品的人數最大化。二、信息級聯模型級聯范圍最大化（影響力最大化）形式化定義

二、信息級聯模型級聯范圍最大化（影響力最大化）

[1]KempeD,KleinbergJ,Tardosé.Maximizingthespreadofinfluencethroughasocialnetwork.[C]KDD2003.ACMPress,2003.1二、信息級聯模型級聯范圍最大化（影響力最大化）貪心法求解

二、信息級聯模型級聯范圍最大化（影響力最大化）算法2.2級聯范圍最大化-貪心法求解二、信息級聯模型級聯范圍最大化（影響力最大化）temp=[]最終感染范圍為1000次，取均值每條邊的感染率都為0.05二、信息級聯模型第一個種子節(jié)點第三個種子節(jié)點第二個種子節(jié)點二、信息級聯模型級聯范圍最大化（影響力最大化）

在實際計算中貪心法使用蒙特卡洛方法求解影響力最大化問題得到近似最優(yōu)解，然而當網絡規(guī)模較大時，算法的運行效率特別低。研究者普遍使用啟發(fā)式算法來提高貪心法的效率。近年來，主要從以下角度去做改進和變形：1、提高算法效率2、結合節(jié)點影響力度量算法3、動態(tài)網絡的影響力最大化問題4、時間窗口限制條件MoroneF,MakseHA.Corrigendum:Influencemaximizationincomplexnetworksthroughoptimalpercolation.Nature,2015,527(7579):65-8.曹玖新,董丹,徐順,鄭嘯,劉波,羅軍舟.一種基于k-核的社會網絡影響最大化算法.計算機學報,2015,02:238-248.二、信息級聯模型

曹玖新。。。。.一種基于k-核的社會網絡影響最大化算法.計算機學報2015一、選取K值最大的節(jié)點中度數最大的節(jié)點加入S二、將上一步選取節(jié)點的鄰居節(jié)點置于覆蓋范圍之內二、信息級聯模型

曹玖新。。。。.一種基于k-核的社會網絡影響最大化算法.計算機學報2015三、在未覆蓋的范圍內重復步驟一第3個貪心法前三：二、信息級聯模型

曹玖新。。。。.一種基于k-核的社會網絡影響最大化算法.計算機學報2015四、當初始種子集合S中的數量為K結束算法結束，初始種子集合為:[34,1,26]或[34,1,25]CCA算法與貪心法結果幾乎相同,nice!為什么不選擇節(jié)點33?節(jié)點33的影響力同樣很大。二、信息級聯模型線性閥值模型線性閾值模型

(LinearThresholdModel)體現了影響力的累積過程,該模型可以描述為:在社交網絡G＝(V,E)中,對任意節(jié)點v都有一個對應閥值表示只有當節(jié)點v的鄰居節(jié)點對節(jié)點v的影響力之和超過閥值,節(jié)點v才能被激活.節(jié)點v對其鄰居節(jié)點u的影響力都存在一個權重,且節(jié)點v對所有鄰居節(jié)點的影響力權重之和不超過1。

給定初始時刻處于活躍狀態(tài)的用戶集合為A,傳播過程和獨立級聯模型類似,不活躍節(jié)點v狀態(tài)受其所有活躍狀態(tài)節(jié)點的影響.如果t時刻節(jié)點v處于不活躍狀態(tài),且其所有處于活躍狀態(tài)的鄰居節(jié)點對節(jié)點v的影響力之和大于節(jié)點V的閥值,即則節(jié)點v從t+1時刻起變?yōu)榛钴S狀態(tài)。.三、博弈演化群體行為分析三、博弈演化博弈演化對于社會關系網絡中的一個節(jié)點，當它對信息進行傳播時，該節(jié)點從某種意義上來說將會獲得一定的收益，如受歡迎度的提高等；當其他節(jié)點對該節(jié)點傳播的信息提供負反饋時，它需要付出一定的成本，如聲譽的降低等．出于自私性和理性的考慮，當節(jié)點收益少于付出時，它將沒有動機去參與信息的傳播，但是不參與信息的傳播，節(jié)點將得不到任何的收益．

這個矛盾的關系可以用博弈模型來描述和分析，社會關系網絡上的節(jié)點在尋求自身利益最大化的交互過程中相互制約，此消彼長，需要尋找一個平衡點．三、博弈演化觀點交互模型觀點交互模型旨在描述一定的社會環(huán)境中個體通過觀點交互形成和更新自身觀點的規(guī)律，并在此基礎上研究和解釋群體觀點信息的演化現象．

信息傳播模型著眼于群體行為在中觀層面展現的整體效果，未特別關注個體觀點交互的細節(jié)問題．研究者們提出了各種模型來描述觀點交互過程，通常假設參與交互的個體之間具有某種拓撲關系，觀點是用戶對于某條信息的態(tài)度傾向值，所以通常用連續(xù)或離散的實數來表達．從混亂的個體意見到具有明顯傾向的群體態(tài)度出現，是一個從微觀層面到中觀層面，再到宏觀層面的演化過程．這個過程與很多因素相關，比如網絡的拓撲結構、用戶的心理特性、觀點的傳播規(guī)律、個體間的交互規(guī)則等．觀點交互模型著重描述了用戶間交互規(guī)則在觀點演化過程中帶來的影響三、博弈演化博弈演化下面舉出一個簡單的個體說服演化博弈模型來說明建模觀點交互的方法．首先，個體按照特征分為三類：意見領袖、水軍和一般用戶．個體的策略集為｛保持觀點，同意對方｝，針對個體特征構建不同的收益矩陣．定義用于計算機仿真的演化博弈規(guī)則：（１）定義個體觀點的取值區(qū)間，區(qū)間內的數值代表個體觀點值；（２）初始時，隨機賦予個體觀點值；（３）在每一時間步長（博弈回合），個體與另一隨機選擇的個體進行博弈；（４）每個個體存儲前幾個時間步長回合的博弈結果；（５）博弈時，雙方交換彼此觀點數值與個體類型，并取得對方存儲的博弈結果；（６）計算對手采取每種策略的概率，并根據收益矩陣計算自身采取每種策略的期望收益；（７）個體默認采取期望收益最高的策略．三、博弈演化信息傳播和觀點交互是在線社會關系網絡中群體形成的基礎，信息傳播和觀點交互模型要能刻畫信息傳播的過程，分析信息擴散隨時間變化的情況，同時，信息傳播的過程還包含了傳播者對消息內容和觀點接受的過程，信息傳播和觀點交互是網絡群體形成的基礎，信息傳播和觀點交互模型也是研究網絡群體行為演化的重要基礎模型．三、博弈演化隨機演化博弈隨機性的演化博弈模型將有限人口中的演化博弈動態(tài)描述成一個隨機過程，再漸近尋找能夠使用復制動態(tài)方程的條件．構建一個隨機演化博弈通常分為以下幾個步驟．步驟１．博弈的基本參數設定．博弈過程的４個元素包括：決策人、策略集、收益矩陣和次序．決策人（Player）：又稱局中人，指博弈中能獨立決策、獨立行動并承擔決策結果的個人或組織．決策人的數量必須大于等于兩個．策略集（Strategy）：又稱策略空間，指的是供決策人選擇的策略集合．決策人在博弈的過程中可以根據實際情況不斷調整策略以達到最優(yōu)收益．收益矩陣（Payoff）：又稱效用（Utility），也就是決策人之間爭奪的利益．在策略有限的情況下，所有可能的策略組合都將導致一種收益結果，所有的結果可以用矩陣表示，也可以用函數形式表示．三、博弈演化隨機演化博弈步驟２．決策人策略更新過程．在演化博弈的過程中，決策人通過試錯的過程達到博弈均衡．在實際情況中，不同的策略更新規(guī)則必將導致不同的博弈均衡結果．步驟３．參數求解．隨機演化博弈的求解參數主要是固定概率和固定時間步驟４．納什均衡策略求解．確定性演化博弈的均衡策略求解工具為復制動態(tài)方程，在隨機性演化博弈中，不能直接采用復制動態(tài)方程的解ＥＳＳ作為穩(wěn)定策略．隨機性穩(wěn)定策略的計算過程比較復雜.參考：[王元卓。。.網絡群體行為的演化博弈模型與分析方法.計算機學報，2015]

社會因素是指與用戶有社會關系的鄰居，鄰居們的策略選擇會影響到用戶的行為，而用戶可能某時刻單獨考慮每個鄰居的選擇，也有可能同時考慮多個鄰居的選擇；

信息因素是指信息本身所包含的內容及其擴散性（例如信息流行度）對用戶的影響。幾種模型在信息擴散模型中的對比在獨立級聯模型中，節(jié)點３、７、９在時刻t分別以一定概率去激活節(jié)點１，如果其中一個成功，那么節(jié)點１在t＋１時刻將變成激活狀態(tài)，如果不成功，節(jié)點３、７、９在以后的時刻也不能再去激活節(jié)點１．幾種模型在信息擴散模型中的對比在傳染病模型中，當節(jié)點１周圍有節(jié)點是激活狀態(tài)時，該節(jié)點就會以一定概率被激活，在時刻t＋１成為激活態(tài)，而且在一段時間之后，節(jié)點１可以重新回歸未激活態(tài)，而前模型中激活態(tài)節(jié)點是不能回歸未激活態(tài)的.幾種模型在信息擴散模型中的對比博弈論模型中，節(jié)點１被視為一個智能個體，它會同時考慮它周圍激活態(tài)節(jié)點（３、７和９）和未激活態(tài)節(jié)點（２和４），計算選擇哪種狀態(tài)自己可以獲取更大利益，此外還會考慮信息內容對自身帶來的利益，最終做出讓自身利益最大的選選擇。幾種模型在信息擴散模型中的對比四、網絡結構與信息傳播無標度網絡

平局度=2平局度=4四、網絡結構與信息傳播聚類系數P=0.02ICM模型

初始節(jié)點數量聚類系數感染數量初始節(jié)點數量聚類系數感染數量初始節(jié)點數量聚類系數感染數量10.171.9420.1812.0550.1975.2410.221.8920.2110.3350.2386.9210.28220.2919.550.2687.8310.281.7120.2715.4350.3390.0210.321.7320.3417.4850.3586.9810.382.1920.3518.1550.3587.4910.391.6720.4215.1450.3694.4710.472.4220.428.3850.4287.8210.51.820.4911.250.4591.6610.532.4920.5410.17