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

有效

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

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

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

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

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

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

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

步驟6：判斷正種子群是否達到規模，若達到規模，則執行步驟7；若沒有達到規模，則執行步驟4；

步驟7：輸出正種子群；

其特征在于，所述步驟2包括：

步驟2.1：對負種子群中每個節點u構造該節點的最大影響出樹MIOA(u,θ)，最大影響出樹由從該節點出發的所有傳播概率大于一個閾值θ的最大影響路徑的并集組成；

步驟2.2：負種子群中所有節點的最大影響出樹的并集組成負影響傳播范圍；

所述步驟3包括：

步驟3.1：對負影響傳播范圍內的每個節點u，循環執行步驟3.2到3.6；

步驟3.2：構造該節點的最大影響入樹MIIA(u,θ)，最大影響入樹由到該節點的所有傳播概率大于一個閾值θ的最大影響路徑的并集組成；

步驟3.3：計算u在MIIA(u,θ)中的負激活概率ap^N(u,S_N,S_P,MIIA(u,θ))；

步驟3.4：對MIIA(u,θ)中的每個節點v，循環執行步驟3.5到3.6；

步驟3.5：計算u在正種子群為S_P∪{v}時的負激活概率ap^N(u,S_N,S_P∪{v},MIIA(u,θ))；

步驟3.6：按以下公式累加計算v的阻斷負影響DecInf(v)：

DecInf(v)+＝ap^N(u,S_N,S_P,MIIA(u,θ))-ap^N(u,S_N,S_P∪{v},MIIA(u,θ))；

所述步驟5包括：

步驟5.1：構造選擇的阻斷負影響最大的節點u的最大影響出樹MIOA(u,θ)；

步驟5.2：對MIOA(u,θ)中的每個節點v，循環執行步驟5.3到5.5；

步驟5.3：構造v的最大影響入樹MIIA(v,θ)；

步驟5.4：對MIIA(v,θ)中的每個節點w，循環執行步驟5.5

步驟5.5：按以下公式更新w阻斷負影響DecInf(w)：

DecInf(w)-＝ap^N(v,S_N,S_P,MIIA(v,θ))-ap^N(v,S_N,S_P∪{w},MIIA(v,θ))；

步驟5.6：將節點u加入到正種子群S_P；

步驟5.7：對MIOA(u,θ)\{u}中的每個節點v，循環執行步驟5.8到5.12；

步驟5.8：構造v的最大影響入樹MIIA(v,θ)；

步驟5.9：計算v的負激活概率ap^N(v,S_N,S_P,MIIA(v,θ))；

步驟5.10：對MIIA(v,θ)中的每個節點w，循環執行步驟5.11到5.12；

步驟5.11：計算v在正種子群為S_P∪{w}時的負激活概率ap^N(v,S_N,S_P∪{w},MIIA(v,θ))；

步驟5.12：按以下公式更新w阻斷負影響DecInf(w)：

DecInf(w)+＝ap^N(v,S_N,S_P,MIIA(v,θ))-ap^N(v,S_N,S_P∪{w},MIIA(v,θ))。