[發明專利]基于局部影響力計算的影響力阻斷最大化方法

有效

• 申請號: 201710335414.3
• 申請日: 2017-05-12
• 公開（公告）號: CN107220486B
• 公開（公告）日: 2021-07-20
• 發明（設計）人: 潘理;吳鵬
• 申請（專利權）人: 上海交通大學
• 主分類號: G06F30/20
• 分類號: G06F30/20;G06Q50/00;H04L12/58
• 代理公司: 上海漢聲知識產權代理有限公司 31236
• 代理人: 郭國中;樊昕

本發明提供了一種基于局部影響力計算的影響力阻斷最大化方法，包括如下步驟：確定負影響范圍；構造節點局部影響區域；計算節點局部負激活概率；計算節點阻斷負影響；迭代選擇阻斷負影響最大的節點作為正種子；更新節點的阻斷負影響。本發明針對社交網絡規模大的特點，提出局部負激活概率近似計算動態規劃方法，基于計算的局部負激活概率計算節點阻斷負影響，基于阻斷負影響選擇正面種子，適合于快速選擇使負影響阻斷最大的正種子群。

技術領域

本發明涉及社交網絡技術領域，具體地，涉及一種基于局部影響力計算的影響力阻斷最大化方法，可用于社交網絡信息傳播控制。

背景技術

社交網絡中的影響力傳播分析對社交網絡信息傳播控制有重要作用。社交網絡上謠言等惡意信息傳播可能會對經濟發展、社會穩定和國家安全等造成重大危害。為了使社交網絡成為更可靠的信息傳播平臺，需要采取有效的策略來減少惡意信息傳播的危害。當用戶接受針對某個壞信息的好信息后，用戶將不再接受該壞信息，因此可以在社交網絡上發布好信息來遏制相應的壞信息的傳播。傳播壞信息的信源稱為負面種子群，而傳播好信息的信源稱為正面種子群。

經對現有技術的文獻檢索發現，影響力阻斷最大化問題在很多傳播模型下是NP-hard的，但是其目標函數在有些傳播模型下具有子模性，因此貪心算法可以獲得1-1/e的近似比。但是計算影響力的阻斷范圍是很困難的，通常采用蒙特卡洛模擬來估計影響力的阻斷范圍。然而，為了保證估計精度，需要進行大量蒙特卡洛模擬，因此需要耗費大量時間，不利于在大規模社交網絡上即時采取應對惡意信息傳播的策略。在影響力最大化相關研究中，有研究者提出在局部結構中近似快速計算影響力范圍，影響力最大化和影響力阻斷最大化問題有很多相似之處，影響力范圍的快速計算方法為影響力阻斷范圍的快速計算提供了新思路。

給定一個負面種子群，影響力阻斷最大化問題旨在發現一個正面種子群來發布正面信息，正面信息和負面信息競爭傳播，使負面信息的傳播范圍的阻斷最大。He等人于2012年在國際會議《SDM》上發表題為“Influence blocking maximization in socialnetworks under the competitive linear threshold model”的文章，文中研究競爭線性閾值模型下的影響力阻斷最大化問題。他們證明該問題在競爭線性閾值模型下是NP-hard，其目標函數在該模型下具有子模性，因此貪心算法能夠獲得1-1/e的近似保證比。貪心算法速度太慢，他們基于DAG結構提出了速度更快的算法CLDAG，該算法利用了在DAG結構中能夠快速近似計算傳播影響的性質。Budak等人于2011年在國際會議《WWW》上發表題為“Limiting the spread of misinformation in social networks”的文章，文中在競爭無意識獨立級聯模型(COICM)下研究傳播阻斷最大化問題。他們證明該問題在這兩個模型下是NP-hard，并且該問題的目標函數在兩個模型下具有子模性，因此貪心算法能夠獲得1-1/e的近似保證比。但是貪心算法速度太慢，無法適用于大規模社交網絡。

發明內容

針對現有技術中的缺陷，本發明的目的是提供一種基于局部影響力計算的影響力阻斷最大化方法，速度更快，性能更好。

為達到上述目的，本發明所采用的技術方案如下：

一種基于局部影響力計算的影響力阻斷最大化方法，包括如下步驟：

步驟1：輸入網絡G、負種子群S_N、正種子群規模k，網絡每條邊賦予一個傳播概率；

步驟2：確定負影響傳播范圍NegS；

步驟3：計算所有節點的初始阻斷負影響DecInf(v)；

步驟4：選擇阻斷負影響最大的節點u；

步驟5：將u加入正種子群S_P，更新所有相關節點的阻斷負影響DecInf(v)；