2.2 獨(dú)立級(jí)聯(lián)模型

在獨(dú)立級(jí)聯(lián)模型中，圖中的每一條有向邊(u,v)∈E都有一個(gè)對(duì)應(yīng)的概率值p( u,v)∈ [0,1]（如圖2-1所示）。直觀上說，p( u,v)表示當(dāng)u被激活后u通過邊(u,v)獨(dú)立激活v的概率，稱p( u,v)為影響概率（Influence Probability）。

定義2.2 （獨(dú)立級(jí)聯(lián)模型）。獨(dú)立級(jí)聯(lián)模型是由有向圖G=(V,E)及每條有向邊上的影響概率p( u,v)唯一確定的。獨(dú)立級(jí)聯(lián)模型下的動(dòng)態(tài)傳播過程從種子結(jié)點(diǎn)集合開始，在離散時(shí)間點(diǎn)t=0,1,2,B以如下形式完成：在t=0時(shí)刻，集合S0中的結(jié)點(diǎn)被激活，而其他結(jié)點(diǎn)都處于不活躍狀態(tài)。這個(gè)初始結(jié)點(diǎn)集合被稱作種子結(jié)點(diǎn)集合（Seed Set）。對(duì)任何時(shí)刻t≥1，用St表示到這個(gè)時(shí)刻為止所有活躍點(diǎn)的集合。在任何時(shí)刻點(diǎn)t≥1，首先St-1中的結(jié)點(diǎn)都在St中；其次，對(duì)任何一個(gè)在上一時(shí)刻剛被激活的點(diǎn)（設(shè)），u會(huì)對(duì)它的每個(gè)尚未被激活的出鄰居嘗試激活一次，而這次嘗試成功的概率為p( u,v)，且這次激活嘗試與所有其他的激活嘗試事件相互獨(dú)立。如果嘗試成功，則v在時(shí)刻t被激活，即；如果嘗試不成功，且v的其他入鄰居也未在時(shí)刻t成功激活v，則v在時(shí)刻t仍為不活躍狀態(tài)，即。當(dāng)在某一時(shí)刻不再有新的結(jié)點(diǎn)被激活時(shí)，傳播過程結(jié)束。

下面給出一個(gè)獨(dú)立級(jí)聯(lián)模型在一次傳播中的示例，便于大家直觀理解這一模型。

示例2.1圖2-1給出了獨(dú)立級(jí)聯(lián)模型一次傳播結(jié)果的示意圖。在0時(shí)刻（圖2-1（a）），結(jié)點(diǎn)1和結(jié)點(diǎn)2被選為種子結(jié)點(diǎn)并被激活。在時(shí)刻1（圖2-1（b）），結(jié)點(diǎn)1成功激活結(jié)點(diǎn)3和結(jié)點(diǎn)5，同時(shí)結(jié)點(diǎn)2也成功激活結(jié)點(diǎn)3和結(jié)點(diǎn)4，但結(jié)點(diǎn)2沒有成功激活結(jié)點(diǎn)6。在時(shí)刻2（圖2-1（c）），雖然結(jié)點(diǎn)3激活結(jié)點(diǎn)6的嘗試也沒有成功，但結(jié)點(diǎn)5成功激活結(jié)點(diǎn)6；不過結(jié)點(diǎn)5沒有激活結(jié)點(diǎn)9。在時(shí)刻3（圖2-1（d）），結(jié)點(diǎn)6試圖激活結(jié)點(diǎn)7，但沒有成功，本次傳播結(jié)束。

注：每條有向邊上的數(shù)字是該邊上的影響概率。原始邊表示原始圖中的邊，尚未進(jìn)行激活嘗試；活躍邊表示影響力在該邊上成功傳播（這些邊也是傳播中的活躍邊）；阻斷邊表示影響力試圖通過該邊傳播但沒有成功（這些邊是傳播中的阻斷邊）。

獨(dú)立級(jí)聯(lián)模型是隨機(jī)傳播模型（定義1.1）的一個(gè)特例。狀態(tài)集∑={0,1}中，0表示不活躍，1表示活躍。傳播事件的序列是標(biāo)準(zhǔn)的離散時(shí)間序列{(t,v)| t =1,2,3,B, v∈ V}。傳播概率空間Ω是所有邊(u,v)∈E以獨(dú)立的概率p( u,v)被選中的所有組合，這些隨機(jī)事件的組合表達(dá)了任何一點(diǎn)u能激活它的任何一個(gè)出鄰居v的所有可能的隨機(jī)性。因?yàn)樵诿織l邊(u,v)上，u激活v的嘗試只進(jìn)行一次，所以上面隨機(jī)事件的組合也表達(dá)了整個(gè)傳播過程中可能發(fā)生的所有隨機(jī)事件。更準(zhǔn)確地說，令L是圖G的一個(gè)子圖，L的結(jié)點(diǎn)集合與G相同，而邊集是E的一個(gè)子集。為便于區(qū)分，用E( G )和E( L )分別表示圖G中的邊和圖L中的邊。子圖L發(fā)生的概率就是在L中的邊都被選中而不在L中的邊都沒被選中的概率，即。我們稱L為一個(gè)（隨機(jī)）活躍邊圖（Live-Edge Graph），L中的每一條邊被稱為活躍邊（Live Edge），而不在L中的邊被稱為阻斷邊（Blocked Edge），傳播可以通過活躍邊進(jìn)行，但不能通過阻斷邊進(jìn)行。在后續(xù)的模型分析和算法設(shè)計(jì)中，活躍邊圖是一個(gè)十分重要的概念和分析手段。在這里作為介紹模型的傳播概率空間，我們自然引入了這一概念。那么傳播概率空間（或可能世界空間）Ω就是所有活躍邊圖構(gòu)成的有限離散空間，其中每一個(gè)活躍邊圖L就是一個(gè)隨機(jī)元（或可能世界），其概率是

最后，按照定義1.1，給出傳播函數(shù)Fv的定義。對(duì)于一個(gè)事件，用表示事件的示性函數(shù)，即如果事件為真，，如果事件為假，。則可以定義獨(dú)立級(jí)聯(lián)模型的傳播函數(shù)為。這個(gè)函數(shù)的意思是說，如果前一時(shí)刻結(jié)點(diǎn)v的某一個(gè)在L中的入鄰居u處于活躍狀態(tài)（即u是活躍的且從u到v的邊也是活躍邊），那么在這一時(shí)刻v也是活躍的。或者v在前一時(shí)刻已經(jīng)是活躍的，那么v在當(dāng)前時(shí)刻仍會(huì)保持活躍。這個(gè)傳播函數(shù)雖然沒有顯式地給出傳播發(fā)生或激活的時(shí)刻，但根據(jù)隨機(jī)傳播模型的一般定義，可以得知傳播是在u被激活后的下一個(gè)整數(shù)時(shí)刻點(diǎn)發(fā)生的。綜上，我們可以給出獨(dú)立級(jí)聯(lián)模型在一般隨機(jī)傳播模型框架下的基于活躍邊圖的等價(jià)定義。

定義2.3 （基于活躍邊圖的獨(dú)立級(jí)聯(lián)模型的等價(jià)定義）。在給定有向圖G=(V,E)及每條有向邊上的影響概率p( u,v)的情況下，獨(dú)立級(jí)聯(lián)模型是由下列元素構(gòu)成的一個(gè)隨機(jī)傳播模型的特例：（a）有向圖G=(V,E)；（b）每個(gè)結(jié)點(diǎn)的狀態(tài)空間∑={0,1}；（c）由隨機(jī)活躍邊圖L組成的有限傳播概率空間Ω，L的概率由式（2-1）給出；（d）傳播事件的離散時(shí)間序列；（e）傳播函數(shù)，即只要結(jié)點(diǎn)v自己或有一個(gè)在L中的入鄰居在前一時(shí)刻是活躍的，那么v在當(dāng)前時(shí)刻也是活躍的。種子集合。

對(duì)于在邊(u,v)上u是否激活v的隨機(jī)事件，在定義2.2的描述中是在結(jié)點(diǎn)u被激活后的下一時(shí)刻發(fā)生的。而根據(jù)定義2.3，所有傳播概率空間Ω的隨機(jī)元（即活躍邊圖L）是在傳播之前事先選定的。但根據(jù)隨機(jī)事件分析中常用的延遲決定原則（Principle of Deferred Decision），隨機(jī)事件是事先決定好的還是在需要的時(shí)刻再?zèng)Q定的沒有區(qū)別。因此上述基于隨機(jī)傳播模型的定義2.3和定義2.2給出的對(duì)獨(dú)立級(jí)聯(lián)模型的直接描述是等價(jià)的。延遲決定原則在分析隨機(jī)傳播模型中會(huì)經(jīng)常用到。定義1.1給出的隨機(jī)傳播模型的一般定義也是基于這一原則將所有隨機(jī)事件集中用事先選定的隨機(jī)元ω∈Ω來表述的。

如前所述，我們用S∞表示在傳播過程結(jié)束時(shí)所有活躍結(jié)點(diǎn)的集合，即最終活躍點(diǎn)集。因?yàn)楠?dú)立級(jí)聯(lián)模型是一種即時(shí)傳播模型，根據(jù)本章開始的討論可知Sn-1=S∞。由于傳播過程是隨機(jī)過程，因此S∞是隨機(jī)集合，并由種子集合S0和活躍邊圖L聯(lián)合決定。對(duì)于一個(gè)最終活躍的非種子結(jié)點(diǎn)v∈S∞\ S0，不論根據(jù)定義2.2，還是定義2.3，都可以得出存在一個(gè)整數(shù)時(shí)刻t≥1，v在時(shí)刻t被激活，而必然是在時(shí)刻t-1，v的某個(gè)入鄰居u被激活，且(u,v)是活躍邊（(u,v)∈L），稱v被u激活。激活v的結(jié)點(diǎn)可能不止一個(gè)，它們?cè)谕粫r(shí)刻t同時(shí)激活v。在這里不區(qū)分具體是哪個(gè)結(jié)點(diǎn)激活了v。比如在圖2-1（b）中表示的1時(shí)刻，結(jié)點(diǎn)1和結(jié)點(diǎn)2同時(shí)激活結(jié)點(diǎn)3。

引理2.2給出了S∞與S0和L的關(guān)系。在任何一個(gè)有向圖G=(V,E)中，用表示從結(jié)點(diǎn)集合S沿圖G中有向邊能達(dá)到的結(jié)點(diǎn)集合，即Γ(G,S)={ v |存在G中路徑(v0, v1 ,B,vk),v0∈S, vk=v }，根據(jù)定義。

引理2.2在由種子集合S0和隨機(jī)活躍邊圖L決定的獨(dú)立級(jí)聯(lián)模型的一次傳播中，最終活躍點(diǎn)集S∞是L中所有從S0中結(jié)點(diǎn)出發(fā)可以達(dá)到的結(jié)點(diǎn)的集合，即。

證明：首先證明。對(duì)任意，根據(jù)定義，存在L的路徑(v0, v1 ,B,vk)，使得，vk=v。由獨(dú)立級(jí)聯(lián)模型的定義2.3可知，v0在0時(shí)刻被激活，即；v1在1時(shí)刻被激活，因?yàn)関0到v1的邊是活躍的，即(v0, v1 )∈E( L )。為了熟悉定義，也可嚴(yán)格地從定義2.3做如下推導(dǎo)：，因?yàn)?img alt="" class="h-pic-2" src="https://epubservercos.yuewen.com/256CD9/16946393204461406/epubprivate/OEBPS/Images/52554-0033-0094.png?sign=1754439855-4JQIeyJyNhrNMWsjp4EAUcVBPzt1wEWZ-0-ff32db2bff92c67373950c2d4159906d">，且所以。以此類推，可得v=vk在時(shí)刻k一定是活躍的。因此v∈S∞。反之，再證明。對(duì)任意最終活躍結(jié)點(diǎn)v∈S∞，一定能找到一個(gè)激活序列(v0, v1 ,B,vk)，k≥0，使得v0∈S0，vk=v，vi-1激活vi，對(duì)所有的i=1,2,B,k，而這意味著(vi-1,vi )∈L。因此(v0, v1 ,B,vk)是L中的一個(gè)路徑，從而v=vk可以從一個(gè)種子結(jié)點(diǎn)v0∈S0在L中到達(dá)，即v∈Γ(L, S0)。正反兩方面綜合，得到S∞=Γ(L, S0)。

根據(jù)引理2.2，可以得出下面關(guān)于影響力擴(kuò)展度的重要結(jié)論。

引理2.3在獨(dú)立級(jí)聯(lián)模型中，種子集合S0的影響力擴(kuò)展度由式（2-2）給出。

其中，Pr(L )由式（2-1）給出，求和項(xiàng)中L遍歷所有活躍邊圖。

引理2.3將活躍邊圖及其上的可達(dá)性與影響力擴(kuò)展度聯(lián)系了起來。由于活躍邊圖可能有很多個(gè)，因此式（2-2）并不能作為計(jì)算影響力擴(kuò)展度的有效算法，但是它對(duì)后面進(jìn)一步分析模型的傳播性質(zhì)有重要作用。

注意到在獨(dú)立級(jí)聯(lián)模型中，任何一個(gè)結(jié)點(diǎn)u對(duì)它的任何一個(gè)出鄰居v只有一次嘗試激活機(jī)會(huì)，且發(fā)生在u剛被激活的下一時(shí)刻，這看起來似乎是模型的一個(gè)局限。比如，也許我們希望允許u對(duì)v的激活時(shí)間有一定的延遲，或者允許u對(duì)v嘗試多次激活。但如果我們只關(guān)心最終活躍結(jié)點(diǎn)集合S∞和最終的影響力擴(kuò)展度，一個(gè)結(jié)點(diǎn)u在何時(shí)嘗試激活另一結(jié)點(diǎn)v或者是否多次嘗試激活結(jié)點(diǎn)v并不重要，只要最終結(jié)點(diǎn)u能夠激活結(jié)點(diǎn)v，就相當(dāng)于有向邊(u, v )是活躍的，而引理2.2同樣適用。因此，只要p( u, v )表示u多次嘗試激活v的總成功概率，就可用基本的獨(dú)立級(jí)聯(lián)模型等價(jià)表達(dá)最終活躍結(jié)點(diǎn)集合S∞的分布和影響力擴(kuò)展度，無須顯式地在模型里加入激活延遲或多次激活的情形。

當(dāng)然，在有些情形中還要考慮中間某時(shí)刻的活躍結(jié)點(diǎn)集合或影響力擴(kuò)展度，比如在最多t時(shí)刻內(nèi)的影響力擴(kuò)展度，這時(shí)加入激活延遲或多次激活就會(huì)造成不同的結(jié)果。在這種情況下，就可根據(jù)需要對(duì)獨(dú)立級(jí)聯(lián)模型做適當(dāng)擴(kuò)展以使它更適合實(shí)際情況，比如在研究t時(shí)刻內(nèi)的影響力最大化時(shí)，作者與合作者引入了見面概率（Meeting Probability）來刻畫在一條邊上可能的傳播延遲[3]（參見第5.1節(jié)）。

獨(dú)立級(jí)聯(lián)模型強(qiáng)調(diào)影響力在人與人的關(guān)系中獨(dú)立傳播，它抽象概括了社交網(wǎng)絡(luò)中人與人之間獨(dú)立交互影響的行為。一個(gè)人對(duì)另一個(gè)人影響力的強(qiáng)弱用這兩者之間有向邊上的概率來描述，而且在這條邊上的傳播不受其他關(guān)系和其他人對(duì)實(shí)體接受情況的影響。很多簡(jiǎn)單實(shí)體，如新消息在在線網(wǎng)絡(luò)中的傳播或新病毒在人際間的傳播，就比較符合獨(dú)立傳播的特性[4]：一個(gè)個(gè)體接受一個(gè)新消息或被感染一個(gè)新病毒一般是由接受方和傳播方兩方面的交互作用決定的，與網(wǎng)絡(luò)中其他人是否接受了該消息或是否被感染了該病毒關(guān)系不大。因此對(duì)這類傳播，獨(dú)立級(jí)聯(lián)模型較為合適。在基于實(shí)際數(shù)據(jù)的影響力學(xué)習(xí)中，獨(dú)立級(jí)聯(lián)模型被初步驗(yàn)證是有效的。因此獨(dú)立級(jí)聯(lián)模型是目前研究最廣泛且最深入的模型，很多更復(fù)雜的傳播模型也是基于獨(dú)立級(jí)聯(lián)模型的。