社交網路中的影響力阻斷最大化

影響力阻斷最大化一般被用在有向網路中，用來控制競爭對手的信息傳播範圍。

基本介紹

• 中文名：社交網路中的影響力阻斷最大化
• 外文名：influence blocking maximization

一．定義

影響力阻斷最大化指的是當甲乙兩種信息源同時在網路中競爭傳播的情況下，給定一個傳播模型，通過選擇一定規模的屬於甲的節點集，以使得與在沒有甲競爭傳播下相比，乙在甲競爭傳播狀態下的傳播範圍被阻斷的最多，即阻斷範圍最大化。

二．相關研究

在使對方阻斷最大化方面，C. Budak等人於2011年首次進行了研究，他們基於擴展的獨立級聯模型證明了競爭阻斷最大化是NP-Hard問題，並將貪心算法同三種啟發式算法進行了性能比較。此外，He等人研究證明了競爭線性閾值模型下的信息阻斷最大化問題符合子模特性，因此貪心算法具有近似保證，同時他們提出了基於LDAG的更為有效的啟發式算法CLDAG來彌補貪心算法運行時長的不足。