2.3 線性閾值模型

線性閾值模型旨在刻畫傳播中多個個體共同影響另一個體的情形。我們首先看它的數學表述，在線性閾值模型中，每條有向邊(u, v )∈E上都有一個權重，這個權重被稱為影響權重（Influence Weight）。直觀上說，w( u, v )反映了u在v的所有入鄰居中影響力的重要性占比，我們要求。每個結點v還有一個被影響閾值θv∈[0,1]，這個閾值在0到1的范圍內均勻隨機地選取，且一旦確定，在傳播中不再改變。與獨立級聯模型一樣，在0時刻有且僅有種子集合S0中的結點被激活。在之后每個時刻（t≥1），每個不活躍結點v∈ V\St-1都需要依據它所有已激活的入鄰居到它的線性加權和是否已達到它的被影響閾值來判斷是否被激活，即是否成立。若是，則v在時刻t被激活（v∈St）；否則，v仍然保持不活躍狀態（v∈ V\ St）。當某一時刻不再有新的結點被激活時，傳播過程結束。

上面的描述十分接近一般隨機傳播模型的框架，因此用該框架直接定義線性閾值模型（Linear Threshold Model），用θ={θv |v∈ V}表示所有結點閾值的向量。

定義2.4 （線性閾值模型）。在給定有向圖G=(V, E )及每條有向邊上的影響權重w( u, v )的情況下，線性閾值模型是由下列元素構成的一個隨機傳播模型的特例：（a）有向圖G=(V, E )；（b）每個結點的狀態空間Σ={0,1}；（c）由閾值向量θ={θv |v∈ V}構成的傳播概率空間，即,θ的每一維都是在[0,1]中均勻采樣獲得的；（d）傳播事件的離散時間序列{(t, v )| t=1,2,3,B,v∈ V}；（e）傳播函數。種子集合。

下面通過一個例子具體解釋線性閾值模型的傳播。該示例與獨立級聯模型的示例2.1有相同的圖結構和相同的結點激活順序，但激活機制并不相同。因此讀者也可以通過比較這兩個例子體會兩種傳播模型的不同點。

示例2.2圖2-2給出了線性閾值模型下一次傳播的示例。在時刻0（圖2-2（a）），各個結點的閾值被采樣確定，以帶下劃線的數字顯示在各個結點旁邊，而且結點1和結點2被選為種子結點并被激活。在時刻1（圖2-2（b）），結點1指向結點5的邊權重0.4超過結點5的閾值0.2，因此結點5被激活；結點2指向結點4的邊權重0.7超過結點4的閾值0.5，因此結點4也被激活；結點1和結點2指向結點3的邊權重和為0.6，達到了結點3的閾值0.6，因此結點1和結點2聯合激活了結點3。然而在時刻1，結點6只有一個入鄰居結點2在前一時刻是活躍結點，而結點2到結點6的邊權重0.4小于結點6的閾值0.7，因此在這一時刻結點6沒有被激活。在時刻2（圖2-2（c）），結點2、3、5指向結點6的邊的權重和達到0.9，超過結點6的閾值0.7，因此結點6被激活。但是結點5沒有激活結點9，因為結點5到結點9的邊權重0.3沒有達到結點9的閾值0.8。在時刻3，結點6也不足以激活結點7，因此傳播結束。

注：每條有向邊上的數字是該邊上的影響權重；每個結點旁邊帶下劃線的數字是這次傳播中隨機生成的該結點的閾值；原始邊表示原始圖中的邊，尚未進行激活嘗試；權重參與激活指向點的邊表示這些邊上的權重加在一起后超過結點閾值從而成功地激活了指向結點。

在線性閾值模型中，結點v的閾值表達了結點對一個新實體的接受傾向：閾值越高，v越不容易被影響；閾值越低，v越容易被影響。結點v的入鄰居對v的影響是聯合發生的：可能任何一個入鄰居都不能單獨激活v，但幾個入鄰居聯合起來就可能使對v的影響力權重超過v的閾值從而激活v。比如在示例2.2中，結點2在時刻1不足以激活結點6，而在時刻2當結點2和結點3、結點5聯合在一起時就足以激活結點6。這種聯合影響對應了人類行為中在面對一個相對復雜的選擇時（比如購買新型手機、選擇移民等）經常出現的從眾行為[4-5]，即一個人可能需要社交網絡中多個不同的朋友或熟人都接受了一個新實體（想法、觀念、產品、行為等）時，才會也接受這個新實體。這是線性閾值模型與獨立級聯模型相比最主要的不同點。

線性閾值模型的隨機性完全是由結點被影響閾值的隨機性決定的，一旦隨機閾值被確定下來，后面的傳播過程就是確定的。而在線性閾值模型中閾值是在0和1之間隨機選取的，這反映了我們對結點閾值的不了解。然而在實際中人的被影響閾值雖然有隨機性，但其應該在更窄的范圍內波動。如果用更窄范圍的隨機閾值（比如固定閾值），會使得模型的分析和計算難度顯著加大[2,6]。因此線性閾值模型在閾值選取上面臨兩難選擇，這也是這一模型不如獨立級聯模型應用廣泛的一個原因。關于閾值選取的問題，在下面介紹通用閾值模型時還會提及。下面先介紹線性閾值模型的一個很重要的等價模型。

由定義2.4可知線性閾值模型的隨機性是由結點閾值的隨機性確定的。然而，線性閾值模型還有一種基于隨機活躍邊圖的等價模型，就像獨立級聯模型有一個基于活躍邊圖的等價定義2.3一樣。與定義2.3唯一不同的是隨機活躍邊圖的概率分布。這個基于活躍邊圖的等價定義對后續的研究十分重要。

針對線性閾值模型，以如下方式隨機采樣活躍邊圖。對于任意結點v∈ V，隨機選取v的一條入邊或不選入邊，且選取入邊(u, v )的概率是該邊的權重w( u, v )，而不選取任何一條邊的概率是。這樣構成的活躍邊圖L是原圖G的一個子圖，且每個結點最多有一條入邊, 即。在這樣的活躍邊圖中，我們定義結點v的前驅predL (v )為v的唯一入鄰居，如果v沒有任何入鄰居，則。那么我們可以將線性閾值模型對應的活躍邊圖的概率分布總結為

線性閾值模型可以表達為：先采樣一個活躍邊圖L，然后在L上從種子結點出發沿出邊進行傳播，只要可達到的結點都被激活。這可以在隨機傳播模型的框架下如下定義。這個定義與獨立級聯模型的定義2.3幾乎相同，唯一的不同點是隨機活躍邊圖的采樣概率不同。這說明兩個模型遵循同樣的在隨機活躍邊圖上按可達性傳播的機制，但活躍邊圖的性質不同。

定義2.5 （基于活躍邊圖的線性閾值模型的等價定義）。在給定有向圖G=(V, E )及每條有向邊上的影響權重w( u, v )的情況下，線性閾值模型是由下列元素構成的一個隨機傳播模型的特例：（a）有向圖G=(V, E )；（b）每個結點的狀態空間Σ={0,1}；（c）由隨機活躍邊圖L組成的有限傳播概率空間Ω，L的概率由式（2-3）給出；（d）傳播事件的離散時間序列{(t, v )| t=1,2,3,B,v∈ V}；（e）傳播函數，即只要結點v自己或有一個在L中的入鄰居在前一時刻是活躍的，那么v在當前時刻也是活躍的。種子集合。

上面基于活躍邊圖的定義在表面上和基于隨機閾值的定義2.4有所不同，但是兩者實際是等價的。在討論兩者的等價性之前，先給出等價模型的一般定義。對于二值離散時間遞進性模型，在給定種子結點集合S0的情況下，傳播過程可以表示為一個集合序列，其中，集合St是在時刻t的活躍結點集合。兩個二值離散時間遞進性模型的等價就是指其產生這樣序列的分布是一樣的。

定義2.6 （二值離散時間遞進性模型的等價性）。我們說兩個二值離散時間遞進性模型在圖G=(V, E )上是等價的，如果對任意集合序列，兩個模型在以S0為種子時產生這一序列（即時刻t的活躍結點集恰為St，對所有t=1,2,B,n-1）的概率都相等。

定義2.4和定義2.5等價的直觀原因如下。對于任意結點v，假設在某時刻t，v的入鄰居N-(v )中的一個子集已被激活。令是A中結點到v的邊的權重和。根據定義2.4，如果W≥θv，v就被激活。而是在[0,1]中均勻隨機選取的，因此W≥θv的概率就是W。而如果從定義2.5出發，v被激活的條件是當且僅當v隨機選取的入邊(u, v )滿足u∈A。因為入邊的選取是以權重為概率進行的，所以選得的入邊(u, v )滿足u∈A的概率也是。因此兩個定義對于激活結點v的概率是相等的。將這個直觀化的討論加以嚴格化就能得到下面的等價結論。

定理2.1關于線性閾值模型的定義2.4和定義2.5是等價的。

證明：給定一個種子集合S0，要證明在兩種定義下產生任意序列的概率總是相等的。

為方便起見，對于任意不在圖中的邊，定義w( u, v ) =0。我們很容易檢驗這一改動不會對定義2.4和定義2.5描述的傳播過程產生任何影響。當把不在圖中的邊看成權重為零的邊后，對結點v就不用再特別討論它的入鄰居，而只需討論所有點即可。定義集合函數，顯然。

固定一個結點集合序列，用表示產生序列的事件。先根據定義2.4計算。在給定序列的情況下，對任意t=1,2,B,n-1，考慮任意v∈St\St-1。根據定義2.4，當且僅當v的閾值滿足時，v恰好出現在St\St-1而不在St-1中。這里為方便起見，規定，。因為是在[0,1]中均勻隨機選取的，所以上面條件發生的概率是fv( St-1)-fv( St-2)。我們再考慮最終沒有被激活的點。當且僅當時，結點u沒有被激活，而這個條件發生的概率是。又因為所有結點的閾值都是獨立隨機選取的，所以得到序列發生的概率是

下面我們再按定義2.5推導。在給定序列的情況下，對任意t=1,2,B,n-1，考慮任意v∈St\St-1，即所有在St中但不在St-1中的元素。根據定義2.5，隨機選取的v恰好出現在St\St-1而不在St-1中的條件是當且僅當其入邊(u, v )滿足（如果u∈St-2，那么u會在時刻t-1或之前就被激活，而如果，u在時刻t結束時也不會被激活）。條件u∈St-1\St-2發生的概率是。再考慮最終沒有被激活的結點，結點u沒有被激活的條件是當且僅當沒有隨機選取的入邊或隨機選取的u的入邊(x, u )滿足，而這個條件發生的概率是。因為每個結點的入邊是獨立隨機選取的，所以綜合上面討論，可以得到序列發生的概率仍然是式（2-4）。因此定義2.4和定義2.5是等價的。

上面的引理說明線性閾值模型也可以像獨立級聯模型一樣有一個基于活躍邊圖上可達性的定義。這在后面的模型性質分析和算法設計中都很有用處。

從定義上，我們能理解獨立級聯模型和線性閾值模型是不同的。在獨立級聯模型中，影響力在各條邊上獨立傳播，而在線性閾值模型中影響力是在若干入鄰居的聯合作用下共同完成的。那么對于一個獨立級聯模型，有沒有可能通過合理配置參數用一個線性閾值模型來表達它呢？或者反之用某一個獨立級聯模型來表達一個線性閾值模型呢？回答是否定的，即在一般情況下這兩個模型不能互相表達，它們是不等價的。下面的示例給出了一個不等價的簡單情況。

示例2.3圖2-3給出了一個簡單的3個結點的有向圖，其中結點1和結點2分別有一條有向邊指向結點3。對于這個圖上的一個獨立級聯模型，設邊(1,3)有影響概率p(1,3)，邊(1,2)有影響概率p(1,2)。同樣地，對于這個圖上的一個線性閾值模型，設邊(1,3)有影響權重w(1,3)，邊(1,2)有影響權重w(1,2)。下面討論如果要使這個圖中的獨立級聯模型和獨立閾值模型等價，這些影響概率和影響權重必須滿足什么樣的要求。首先，當結點1是唯一的種子時，在獨立級聯模型下，結點1激活結點3的概率是p(1,3)；在線性閾值模型下，結點1激活結點3的概率是w(1,3)。因此，要使兩個模型等價，只能使p(1,3)=w(1,3)。同理，當結點2是唯一種子時，要保證結點2對結點3的激活概率相等，只能使p(2,3)=w(2,3)。現在我們考慮結點1和結點2同為種子結點，在獨立級聯模型下，兩個種子結點試圖獨立激活結點3，因此結點3被激活的概率是1- (1-p(1,3))(1-p(2,3))。在線性閾值模型下，兩個結點的權重合起來與結點3的閾值進行比較，結點3被激活的概率是w(1,3)+w(2,3)。因為已知p(1,3)=w(1,3)和p(2,3)=w(2,3)，所以當且僅當p(1,3)=0或p(2,3)=0時概率1- (1-p(1,3))(1-p(2,3))等于概率w(1,3)+w(2,3)。因此，只要p(1,3)和p(2,3)都不為0，結點1和結點2共為種子結點時激活結點3的概率在兩種模型上就不會相同。在一般情況下，圖2-3不存在等價的獨立級聯模型和線性閾值模型。

圖2-3雖然只有3個結點，但它反映了獨立級聯模型和線性閾值模型的實質區別。圖2-3的這種多點指向一點的結構是實際圖中經常出現的結構，因此在一般的實際圖中獨立級聯模型和線性閾值模型也是不等價的。

與獨立級聯模型中關于影響力延遲的討論類似，在線性閾值模型中，我們也可以允許一個已被激活的結點u將它對結點v的影響權重延遲一點時間再施加在結點v上。只要我們關心的是最終的激活結點集合S∞或最終的影響力擴展度，引入延遲與否對結果沒有影響。這一點在基于活躍邊圖的等價定義中更易于理解。在一個邊上的延遲，可以理解為該邊被延遲加入活躍邊圖中。但我們只關心最終邊圖的可達性，因此活躍邊的延遲加入對結果沒有影響。

備注2.1我們還要提醒讀者，對線性閾值模型的表述在文獻中不太一致。本節中的描述和最早介紹線性閾值模型的Kempe等人[2]的描述是一致的。其中各結點的閾值是在[0,1]中均勻隨機選取的。而在后續的文獻中，有些將對閾值的固定選取或其他選取方法也稱作線性閾值模型。這樣的描述只采納了在描述模型中的權重線性相加的部分，然而這樣的模型與均勻隨機選取閾值的線性閾值模型有截然不同的性質。為了避免混淆，我們著重強調在本書中的線性閾值模型要求閾值是在[0,1]中均勻隨機選取的。而對于其他的閾值選取方法，在后面的通用閾值模型中再加以討論。我們也建議讀者在自己的工作中表述線性閾值模型時，依照本書及Kempe等人[2]的描述明確表明閾值的均勻隨機選取方法，如果用別的閾值選取方法，請給它取一個有別于線性閾值模型的名稱。這樣可以避免產生歧義和誤解。