2.1 遞進性影響力傳播模型的基本概念

由第1章的分類可知，遞進性模型也可以有單實體或多實體、二值狀態或多值狀態、離散時間或連續時間等多種可能模型。本章集中介紹影響力傳播的最基本模型——單實體二值狀態離散時間遞進性模型。這類模型是其他拓展模型的基礎。眾多的算法問題也都是圍繞這類基礎模型的。后續章節會依次介紹在影響力基礎模型之上的影響力最大化算法、其他影響力傳播模型及其他影響力模型之上的優化問題等。

本章側重于介紹各個模型的準確數學描述，比較它們之間的不同，給出它們的基本性質，并討論它們可能的適用情形。影響力傳播模型還有一些重要的性質，如次模性，其與影響力最大化密切相關。本章的第6節會重點介紹傳播模型的次模性。

在單實體二值狀態傳播中，每個結點v在每個時刻t的狀態有0和1兩種狀態。為方便描述，通常將0狀態描述為不活躍（Inactive）狀態，1狀態描述為活躍（Active）狀態。不活躍狀態表示該個體還沒有接受對應實體（信息、想法或產品），而活躍狀態表示該個體已經接受對應的實體。結點從不活躍狀態變為活躍狀態表示該結點接受了對應實體，我們稱之為結點被激活（Activated）。在本章中，我們考慮單實體在離散時間下的傳播。在這樣的模型中，傳播過程在開始時某些結點處于活躍狀態，被稱為種子結點，而其他結點處于不活躍狀態。然后從種子結點出發，更多的結點被激活為活躍結點。具體的激活過程由不同的傳播模型來表述。

在單實體二值狀態模型中，用St表示在時刻t≥0時圖中活躍結點的集合。其中S0是種子結點集合。對于離散時間模型，后續活躍集合用S1, S2, S3, B表示，這些集合是由傳播模型和給定種子集合S0確定的隨機集合。用S∞表示最終被激活的結點集合。由于本章中我們考慮遞進性模型，所以有，而且因為活躍集合只能增長有限次，傳播過程最后一定會穩定于一個集合S∞。通過這些活躍集合，可以定義重要的影響力擴展度（Influence Spread）的概念。

定義2.1 （影響力擴展度）。在單實體二值狀態遞進性模型中，一個種子集合S0在時刻t≥0的影響力擴展度是時刻t活躍結點個數的期望值，用表示，即，其中期望是對傳播中的所有隨機性取期望，即對傳播模型中的隨機元ω取期望，因此也可用作為更完整的表述。種子集合S0的（最終）影響力擴展度是最終被激活結點的個數，用表示，即。

在本書研究的傳播模型中，作為慣例，如果種子集合S0為空，則不會有任何結點被激活，傳播不會發生，也就是說我們認為種子集合的選取由外在因素決定（在某些擴展模型中種子集合可以由外在因素隨機產生），而一旦種子集合確定，傳播是受種子集合的影響發生的，不考慮傳播在沒有外在因素的情況下自發地發生的情況（作者和合作者在近期工作中確實考慮了結點在沒有種子影響下自激活的情形[1]，但這樣的模型不在本書中進一步討論）。另外在本章介紹的基本模型中，我們不考慮結點間傳播的延遲。被激活的結點對未被激活結點的影響在下一時刻立即發生，而且影響的隨機結果會立即體現，不會分幾步完成。在這種情況下，如果從任意時刻t到下一時刻t+1活躍結點集合沒有發生變化，即St=St+1，則之后活躍結點集合也不會再發生變化，傳播就此結束。這意味著激活集合序列必然一開始嚴格遞增，到某一時刻就不再變化。因為圖中有n=| V |個結點，而時不會傳播，所以嚴格遞增最多發生在前n-1步，換句話說我們得到Sn-1=S∞，這種離散時間遞進性模型為即時傳播模型。

對于在時刻t≥1被激活的結點集合St，嚴格地說是由種子集合S0和隨機傳播模型確定的一個隨機集合。當需要明確表述St與S0的關系時，用表述St，即從種子集合S0出發在t時刻被激活結點的集合。我們用表示以S0為種子集合時最終被激活結點的集合。在本章后面的敘述中我們一般用St表示，但在其他章節中有用和表達的必要。

在給定種子集合S0時，用apt (S0, v )表示S0在時刻t之內激活結點v的概率，即，其中Xv,t∈{0，1}是v在時刻t的狀態；用ap(S0, v )表示S0在傳播結束時激活v的概率，即ap(S0, v )=apn-1(S0, v )。基于數學期望的線性性質，引理2.1指出了種子集合的影響力擴展度就是種子集合激活結點概率的和。

引理2.1對于任意種子集合S0，在任意時刻t≥0，有，。

證明：因為，而，所以根據數學期望的線性性質，有。

影響力最終擴展度的結果可以由得到。

在后面的分析討論中，我們會利用引理2.1將種子集合的影響力擴展度轉化為結點激活概率加以討論。

在影響力傳播模型中，提出最早、研究最深入、應用最廣泛的是獨立級聯模型（Independent Cascade Model）和線性閾值模型（Linear Threshold Model）[2]，下面首先介紹這兩個模型。