基於局部影響力計算的影響力阻斷最大化方法與流程
2023-12-07 02:38:16
本發明涉及社交網絡技術領域，具體地，涉及一種基於局部影響力計算的影響力阻斷最大化方法，可用於社交網絡信息傳播控制。
背景技術：
社交網絡中的影響力傳播分析對社交網絡信息傳播控制有重要作用。社交網絡上謠言等惡意信息傳播可能會對經濟發展、社會穩定和國家安全等造成重大危害。為了使社交網絡成為更可靠的信息傳播平臺，需要採取有效的策略來減少惡意信息傳播的危害。當用戶接受針對某個壞信息的好信息後，用戶將不再接受該壞信息，因此可以在社交網絡上發布好信息來遏制相應的壞信息的傳播。傳播壞信息的信源稱為負面種子群，而傳播好信息的信源稱為正面種子群。
經對現有技術的文獻檢索發現，影響力阻斷最大化問題在很多傳播模型下是np-hard的，但是其目標函數在有些傳播模型下具有子模性，因此貪心算法可以獲得1-1/e的近似比。但是計算影響力的阻斷範圍是很困難的，通常採用蒙特卡洛模擬來估計影響力的阻斷範圍。然而，為了保證估計精度，需要進行大量蒙特卡洛模擬，因此需要耗費大量時間，不利於在大規模社交網絡上即時採取應對惡意信息傳播的策略。在影響力最大化相關研究中，有研究者提出在局部結構中近似快速計算影響力範圍，影響力最大化和影響力阻斷最大化問題有很多相似之處，影響力範圍的快速計算方法為影響力阻斷範圍的快速計算提供了新思路。
給定一個負面種子群，影響力阻斷最大化問題旨在發現一個正面種子群來發布正面信息，正面信息和負面信息競爭傳播，使負面信息的傳播範圍的阻斷最大。he等人於2012年在國際會議《sdm》上發表題為「influenceblockingmaximizationinsocialnetworksunderthecompetitivelinearthresholdmodel」的文章，文中研究競爭線性閾值模型下的影響力阻斷最大化問題。他們證明該問題在競爭線性閾值模型下是np-hard，其目標函數在該模型下具有子模性，因此貪心算法能夠獲得1-1/e的近似保證比。貪心算法速度太慢，他們基於dag結構提出了速度更快的算法cldag，該算法利用了在dag結構中能夠快速近似計算傳播影響的性質。budak等人於2011年在國際會議《www》上發表題為「limitingthespreadofmisinformationinsocialnetworks」的文章，文中在競爭無意識獨立級聯模型(coicm)下研究傳播阻斷最大化問題。他們證明該問題在這兩個模型下是np-hard，並且該問題的目標函數在兩個模型下具有子模性，因此貪心算法能夠獲得1-1/e的近似保證比。但是貪心算法速度太慢，無法適用於大規模社交網絡。
技術實現要素：
針對現有技術中的缺陷，本發明的目的是提供一種基於局部影響力計算的影響力阻斷最大化方法，速度更快，性能更好。
為達到上述目的，本發明所採用的技術方案如下：
一種基於局部影響力計算的影響力阻斷最大化方法，包括如下步驟：
步驟1：輸入網絡g、負種子群sn、正種子群規模k，網絡每條邊賦予一個傳播概率；
步驟2：確定負影響傳播範圍negs；
步驟3：計算所有節點的初始阻斷負影響decinf(v)；
步驟4：選擇阻斷負影響最大的節點u；
步驟5：將u加入正種子群sp，更新所有相關節點的阻斷負影響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,θ)中的負激活概率apn(u,sn,sp,miia(u,θ))；
步驟3.4：對miia(u,θ)中的每個節點v，循環執行步驟3.5到3.6；
步驟3.5：計算u在正種子群為sp∪{v}時的負激活概率apn(u,sn,sp∪{v},miia(u,θ))；
步驟3.6：按以下公式累加計算v的阻斷負影響decinf(v)：
decinf(v)+＝apn(u,sn,sp,miia(u,θ))-apn(u,sn,sp∪{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)-＝apn(v,sn,sp,miia(v,θ))-apn(v,sn,sp∪{w},miia(v,θ))；
步驟5.6：將節點u加入到正種子群sp；
步驟5.7：對mioa(u,θ)\{u}中的每個節點v，循環執行步驟5.8到5.12；
步驟5.8：構造v的最大影響入樹miia(v,θ)；
步驟5.9：計算v的負激活概率apn(v,sn,sp,miia(v,θ))；
步驟5.10：對miia(v,θ)中的每個節點w，循環執行步驟5.11到5.12；
步驟5.11：計算v在正種子群為sp∪{w}時的負激活概率apn(v,sn,sp∪{w},miia(v,θ))；
步驟5.12：按以下公式更新w阻斷負影響decinf(w)：
decinf(w)+＝apn(v,sn,sp,miia(v,θ))-apn(v,sn,sp∪{w},miia(v,θ))。
與現有技術相比，本發明具有如下的有益效果：
1、根據本發明提供的基於局部影響力計算的影響力阻斷最大化方法，具有和貪心算法相近的負影響阻斷性能，但是比貪心算法快超過三個數量級。
2、根據本發明提供的基於局部影響力計算的影響力阻斷最大化方法，在大部分網絡上比其他基礎的啟發式算法的負影響阻斷性能好。
附圖說明
通過閱讀參照以下附圖對非限制性實施例所作的詳細描述，本發明的其它特徵、目的和優點將會變得更明顯：
圖1為本發明提供的基於局部影響力計算的影響力阻斷最大化方法的流程圖；
圖2為本發明和多個已有方法之間在小規模網絡email網絡上的影響力阻斷有效性性能對比圖，其中：
圖(a)為trivalency模型下負激活節點數隨正種子數變化圖；
圖(b)為wc模型下負激活節點數隨正種子數變化圖；
圖(c)各算法的運行時間；
圖3為本發明和多個已有方法之間在三個大規模網絡上的影響力阻斷有效性性能對比圖，其中：
圖(a)為nethept網絡上trivalency模型下負激活節點數隨正種子數變化圖；
圖(b)為nethept網絡上wc模型下負激活節點數隨正種子數變化圖；
圖(c)為netphy網絡上trivalency模型下負激活節點數隨正種子數變化圖；
圖(d)為netphy網絡上wc模型下負激活節點數隨正種子數變化圖；
圖(e)為dblp網絡上trivalency模型下負激活節點數隨正種子數變化圖；
圖(f)為dblp網絡上wc模型下負激活節點數隨正種子數變化圖。
具體實施方式
下面結合具體實施例對本發明進行詳細說明。以下實施例將有助於本鄰域的技術人員進一步理解本發明，但不以任何形式限制本發明。應當指出的是，對本領域的普通技術人員來說，在不脫離本發明構思的前提下，還可以做出若干變形和改進。這些都屬於本發明的保護範圍。
為了更清楚地說明本發明中的技術方案，列舉如下的具體的實施例進一步說明：
根據本發明提供的基於局部影響力計算的影響力阻斷最大化方法，包括如下步驟：
步驟s1、輸入網絡g、負種子群sn、正種子群規模k，為網絡每條邊賦予一個傳播概率，傳播概率表示當前時刻激活的節點在下一時刻激活其未被激活的鄰居的概率；
步驟s2、根據負種子群中每個節點的最大影響出樹mioa(u,θ)確定負影響傳播範圍negs；
所述的步驟s2，具體為：
步驟s21、對負種子群中每個節點u構造該節點的最大影響出樹mioa(u,θ)，最大影響出樹由從該節點出發的所有傳播概率大於一個閾值θ的最大影響路徑的併集組成；
步驟s22、負種子群中所有節點的最大影響出樹的併集組成負影響傳播範圍；
步驟s3、根據節點加入正種子群前後相關節點負激活概率的變化計算所有節點的初始阻斷負影響decinf(v)；
所述的步驟s3，具體為：
步驟s31、對負影響傳播範圍內的每個節點u，循環執行步驟32到36；
步驟s32、構造該節點的最大影響入樹miia(u,θ)，最大影響入樹由到該節點的所有傳播概率大於一個閾值θ的最大影響路徑的併集組成；
步驟s33、計算u在miia(u,θ)中的負激活概率apn(u,sn,sp,miia(u,θ))；
步驟s34、對miia(u,θ)中的每個節點v，循環執行步驟35到36；
步驟s35、計算u在正種子群為sp∪{v}時的負激活概率apn(u,sn,sp∪{v},miia(u,θ))；
步驟s36、按以下公式累加計算v的阻斷負影響decinf(v)：
decinf(v)+＝apn(u,sn,sp,miia(u,θ))-apn(u,sn,sp∪{v},miia(u,θ))；
步驟s4、選擇阻斷負影響最大的節點u；
步驟s5、將u加入正種子群sp，更新所有相關節點的阻斷負影響decinf(v)；
所述的步驟s5，具體為：
步驟s51、構造選擇的阻斷負影響最大的節點u的最大影響出樹mioa(u,θ)；
步驟s52、對mioa(u,θ)中的每個節點v，循環執行步驟s53到s55；
步驟s53、構造v的最大影響入樹miia(v,θ)；
步驟s54、對miia(v,θ)中的每個節點w，循環執行步驟s55
步驟s55、按以下公式更新w阻斷負影響decinf(w)：
decinf(w)-＝apn(v,sn,sp,miia(v,θ))-apn(v,sn,sp∪{w},miia(v,θ))；
步驟s56、將節點u加入到正種子群sp；
步驟s57、對mioa(u,θ)\{u}中的每個節點v，循環執行步驟s58到s512；
步驟s58、構造v的最大影響入樹miia(v,θ)；
步驟s59、計算v的負激活概率apn(v,sn,sp,miia(v,θ))；
步驟s510、對miia(v,θ)中的每個節點w，循環執行步驟s511到s512；
步驟s511、計算v在正種子群為sp∪{w}時的負激活概率apn(v,sn,sp∪{w},miia(v,θ))；
步驟s512、按以下公式更新w阻斷負影響decinf(w)：
decinf(w)+＝apn(v,sn,sp,miia(v,θ))-apn(v,sn,sp∪{w},miia(v,θ))；
步驟s6、判斷正種子群是否達到規模，若達到規模，則執行步驟s7；若沒有達到規模，則執行步驟s4；
步驟s7、輸出正種子群。
為使本實施例要解決的技術問題、技術方案和優點更加清楚，下面將結合附圖對本實施例進行詳細描述。
如圖1所示，本實施例提供的基於局部影響力計算的影響力阻斷最大化方法，包括如下步驟：
步驟s1、輸入網絡g、負種子群sn、正種子群規模k，為網絡每條邊賦予一個傳播概率，傳播概率表示當前時刻激活的節點在下一時刻激活其未被激活的鄰居的概率；
步驟s2、根據負種子群中每個節點的最大影響出樹mioa(u,θ)確定負影響傳播範圍negs，對負種子群中每個節點u構造該節點的最大影響出樹mioa(u,θ)，最大影響出樹由從該節點出發的所有傳播概率大於一個閾值θ的最大影響路徑的併集組成，負種子群中所有節點的最大影響出樹的併集組成負影響傳播範圍；
步驟s3、根據節點加入正種子群前後相關節點負激活概率的變化計算所有節點的初始阻斷負影響decinf(v)，對負影響傳播範圍內的每個節點u，構造該節點的最大影響入樹miia(u,θ)，最大影響入樹由到該節點的所有傳播概率大於一個閾值θ的最大影響路徑的併集組成，計算u在miia(u,θ)中的負激活概率apn(u,sn,sp,miia(u,θ))；對miia(u,θ)中的每個節點v，計算u在正種子群為sp∪{v}時的負激活概率apn(u,sn,sp∪{v},miia(u,θ))，按以下公式累加計算v的阻斷負影響decinf(v)：
decinf(v)+＝apn(u,sn,sp,miia(u,θ))-apn(u,sn,sp∪{v},miia(u,θ))；
步驟s4、選擇阻斷負影響最大的節點u；
步驟s5、將u加入正種子群sp，更新所有相關節點的阻斷負影響，構造選擇的阻斷負影響最大的節點u的最大影響出樹mioa(u,θ)，對mioa(u,θ)中的每個節點v，構造v的最大影響入樹miia(v,θ)；對miia(v,θ)中的每個節點w，按以下公式更新w阻斷負影響decinf(w)：
decinf(w)-＝apn(v,sn,sp,miia(v,θ))-apn(v,sn,sp∪{w},miia(v,θ))；
將節點u加入到正種子群sp；對mioa(u,θ)\{u}中的每個節點v，構造v的最大影響入樹miia(v,θ)，計算v的負激活概率apn(v,sn,sp,miia(v,θ))；對miia(v,θ)中的每個節點w，計算v在正種子群為sp∪{w}時的負激活概率apn(v,sn,sp∪{w},miia(v,θ))，按以下公式更新w阻斷負影響decinf(w)：
decinf(w)+＝apn(v,sn,sp,miia(v,θ))-apn(v,sn,sp∪{w},miia(v,θ))；
步驟s6、判斷正種子群是否達到規模，若達到規模，則執行步驟s7；若沒有達到規模，則執行步驟s4；
步驟s7、輸出正種子群。
本實施例的有效性可以通過下面的仿真實驗來進一步說明。需要說明的是，實驗中應用的參數不影響本發明的一般性。
1)仿真條件：
cpuinteli7-3770s3.10ghz，ram16.00gb，作業系統windows10，仿真程序編寫語言。
2)仿真內容：
在四個真實網絡上進行實驗來評估算法的效率和效果。四個真實網絡為email、nethept、netphy和dblp。roviraivirili大學的email網絡將每個email地址當作一個節點，如果兩個節點之間存在通信，則將它們連接起來。nethept、netphy和dblp是三個學術合作網絡，節點表示作者，兩個節點之間的邊表示兩個作者至少合作一篇論文。採用trivalency模型和wc模型來設置mcicm中的負面傳播概率和coicm中的傳播概率。在trivalency模型中，為每條邊從集合{0.2,0.05,0.01}中隨機選擇一個傳播概率，分別對應於高、中、低的傳播概率。在wc模型中，邊(u,v)的傳播概率設置為1/dv，其中dv為節點v的入度。
本實施例在仿真實驗中用cima-o表示。
將本實施例與4個其他的影響力阻斷最大化方法進行仿真對比。這4個方法如下，budak等人於2011年在國際會議《www》上發表文章「limitingthespreadofmisinformationinsocialnetworks」中提出的greedy-h方法，該方法每次估計影響力時進行10000次蒙特卡洛模擬；budak等人於2011年在國際會議《www》上發表文章「limitingthespreadofmisinformationinsocialnetworks」中提出的proximity方法，該方法從負面種子的直接出鄰居中選擇正面種子，所有直接出鄰居按負面激活概率排序，前k個負面激活概率最大的節點被選為正面種子；degree方法，該方法選擇前k個度最大的節點作為正面種子；random方法，該方法隨機選擇節點作為正面種子。
仿真實驗在小規模網絡email網絡上的影響力阻斷有效性性能如圖2的(a)～(c)所示，在trivalency模型下，cmia-o比random、degree、proximity和greedy-o分別好32.8％、4.8％、8.4％和3.0％；在wc模型下，cmia-o比random、degree、proximity和greedy-o分別好57.6％、7.5％、4.0％和6.3％；greedy-o花費超過6小時，而cmia-o只需要幾秒鐘，因此cmia-o方法比貪心算法快超過三個數量級。在三個大規模網絡上的影響力阻斷有效性性能如圖3的(a)～(f)所示，在trivalency模型下，cmia-o平均比random、degree和proximity分別好105％、5.5％和13.5％；在wc模型下，cmia-o平均比random、degree和proximity分別好1000％、86.7％和17.7％。
本實施例提供的基於局部影響力計算的影響力阻斷最大化方法，可用於社交網絡信息傳播控制。本實施例基於節點的局部結構近似計算節點的負激活概率；基於負激活概率計算節點的負阻斷影響；迭代選擇負阻斷影響最大的節點作為正種子；更新節點的負阻斷影響。
以上對本發明的具體實施例進行了描述。需要理解的是，本發明並不局限於上述特定實施方式，本鄰域技術人員可以在權利要求的範圍內做出各種變形或修改，這並不影響本發明的實質內容。