基于改進反向可達集的在線社交網絡不良信息抑制方法

楊雙雙，劉省非，丁龍，朱文龍

基于改進反向可達集的在線社交網絡不良信息抑制方法

楊雙雙1，劉省非1，丁龍1，朱文龍2

（齊齊哈爾大學 1. 教師教育學院，2. 計算機與控制工程學院，黑龍江 齊齊哈爾 161006）

隨著互聯(lián)網的發(fā)展，網絡中不良信息的數(shù)量呈現(xiàn)出快速增長的趨勢，對于社會的穩(wěn)定與安全構成了威脅．傳統(tǒng)的在線社交網絡不良信息抑制方法存在效率低、實時性差等問題，為此提出一種基于改進反向可達集的在線社交網絡不良信息抑制方法．分析現(xiàn)有的網絡不良信息抑制方法，介紹了反向可達集的概念和原理，基于六度分隔理論，提出一種改進反向可達集的生成方法，并進一步提出一種不良信息抑制方法IRRIMM．通過在真實的社交網絡數(shù)據(jù)集中的實驗驗證了所提出方法的有效性．

不良信息抑制；六度分隔理論；反向可達集；在線網絡

移動互聯(lián)網時代，在線社交網絡不斷涌現(xiàn)，國內如抖音、斗魚，國外如TikTok，Twitter等，吸引了大量的用戶參與到網絡中．在線網絡在人們生活中發(fā)揮了積極的作用，但同時網絡中的一些不良信息，如低俗圖像、虛假信息、不良言論等在互聯(lián)網中傳播迅速、危害性極大．當不良信息發(fā)生時，如何有效地抑制不良信息的傳播，是目前社交網絡研究中的一個熱點問題，其解決方法主要有兩種：

第１種方法是通過挖掘網絡中關鍵節(jié)點或邊信息，對其隔離，使得不良信息無法通過其傳播．以在線社交網絡（見圖1）為例，圖1中包含有12個節(jié)點，節(jié)點間的有向邊表示信息的傳播方向．假設節(jié)點1是不良信息源，在沒有任何抑制手段的情況下，節(jié)點1產生的不良信息將隨信息傳播發(fā)送到節(jié)點2，3，4，5，6，7，8，導致這些節(jié)點被不良信息所影響，假設目前需要尋找一個關鍵節(jié)點抑制不良信息，則會選擇節(jié)點5，因為該節(jié)點能夠抑制不良信息傳遞到節(jié)點6，7，8．

目前，國內外許多學者從挖掘關鍵節(jié)點或邊的角度對不良信息的抑制開展了研究，取得了一定的研究成果．例如：周亞東[1]等提出了一種利用快速URL識別技術尋找關鍵節(jié)點用于e-Learning的不良網絡內容的識別與抑制技術．田亞平[2]等利用節(jié)點行為信息挖掘網絡意見領袖用于不良信息抑制．WANG[3]等利用用戶經驗信息構建樹形傳播結構，并通過在結構樹中選擇節(jié)點來免疫不良信息節(jié)點的攻擊．雖然通過在網絡中挖掘關鍵節(jié)點或者邊并對其進行隔離可以在一定程度上抑制不良信息的傳播，但這種方法也存在非常明顯的缺點，即對節(jié)點或邊的隔離會影響網絡的連通，導致正常信息也不能傳播．

圖1 利用關鍵節(jié)點抑制不良信息傳播

圖2 利用傳播正面消息抑制不良信息傳播

1 問題定義

He[4]468等證明了影響力阻斷最大化問題具有NP難特性，可以使用貪婪算法解決，然而由于貪婪算法效率過低，在實際應用中并不適用．借鑒反向影響力采樣思想，本文提出一種基于改進反向可達集的方法解決該問題，反向影響力采樣思想的核心是構造一組反向可達集，并基于此對種子節(jié)點的影響力擴展度進行無偏估計．

Tang[14]1542等證明了當反向可達集的數(shù)量達到一定規(guī)模時，具有較大影響力的節(jié)點會經常出現(xiàn)在反向可達集中，即種子集在反向可達集中的出現(xiàn)概率是它在原網絡中影響力的無偏估計，可用公式表述

式（2）更一般的解釋是如果一個節(jié)點具有更大的影響力，那么它出現(xiàn)在反向可達集中的概率也應該更大．基于該思想，可以有效地選擇種子節(jié)點．但反向可達集最初被用來解決影響力最大化問題，并沒有考慮到競爭因素，因此，在影響力阻斷最大化問題中并不適用．

2 改進反向可達集和IRRIMM

算法1IRR set //生成改進反向可達集

9 flag=true

13 end if

14 end for

16 end while

算法2IRRIMM

3 實驗驗證

利用Facebook數(shù)據(jù)集進行實驗驗證．數(shù)據(jù)集可以通過SNAP的官方網站進行下載，下載地址是http://snap.stanford.edu/data/index.html．該數(shù)據(jù)集是基于Facebook的用戶社交關系數(shù)據(jù)集，其中包含4 039個節(jié)點和88 234條邊，圖中節(jié)點的平均度為21.84，最大度為1 045．實驗中將本文提出的IRRIMM算法與Random、Degree、DD算法進行了比較，具體信息為：

不同算法在權重級聯(lián)模型下的負激活節(jié)點數(shù)見圖3，從結果中可以看出，本文提出的方法在相同正種子數(shù)下負激活節(jié)點數(shù)最低，因此具有最好的不良消息抑制性能．其次是DD和Degree算法，而Random算法由于隨機選擇節(jié)點作為種子節(jié)點，其抑制性能最差．另外，可以看到隨著正種子數(shù)的增多，被負種子節(jié)點激活的節(jié)點數(shù)不斷減少．這與理論上是一致的，因為正種子數(shù)越多，將有越多的節(jié)點可以接收到正種子傳播的正面信息，導致被負種子激活的節(jié)點數(shù)減少．

不同算法在統(tǒng)一概率模型下的負激活節(jié)點數(shù)見圖4．本文提出的方法依然具有最好的性能．另外，從圖中可以看到，在正種子數(shù)較少時，DD算法的抑制性能優(yōu)于Degree算法，但是隨著正種子數(shù)的增多，DD算法的性能逐漸被Degree算法超越，因為這兩種算法都是啟發(fā)式算法，并不能保證算法的可靠性．

圖3 權重級聯(lián)模型下不同算法負激活節(jié)點數(shù)對比

圖4 統(tǒng)一概率模型下不同算法負激活節(jié)點數(shù)對比

４ 結語

網絡中不良信息的泛濫是亟待解決的問題，本文通過引入六度分隔理論，提出了一種改進的反向可達集生成方法，其核心思想是如果反向可達集中的正向節(jié)點能夠比負向節(jié)點更早到達反向可達集的根節(jié)點，且它們之間的間隔不超過6度，則該反向可達集是一個有效的可達集．在此基礎上，提出了IRRIMM算法，算法包括采樣和種子節(jié)點選擇兩個階段．采樣階段計算所需改進反向可達集數(shù)量的下界并生成相應數(shù)量的改進反向可達集，節(jié)點選擇階段利用貪婪覆蓋算法選擇種子節(jié)點．通過在真實的社交網絡數(shù)據(jù)集上的實驗表明，本文提出的方法具有較好的性能，能夠有效抑制網絡中不良信息的傳播．

[1] 周亞東，鄭慶華，陶敬．e-Learning中不良網絡內容的識別與阻斷技術[J]．中國科技論文在線，2011（10）：765-769．

[2] 田亞平，楊力，王小琴．基于節(jié)點親密度挖掘的謠言抑制算法[J]．網絡與信息安全學報，2016（11）：61-69．

[3] WANG B，CHEN G，F(xiàn)U L．DRIMUX：Dynamic Rumor Influence Minimization with User Experience in Social Networks[J]．IEEE Transactions on Knowledge and Data Engineering，2017，29（10）：2168-2181．

[4] HE X，SONG G，CHEN W．Influence Blocking Maximization in Social Networks under the Competitive Linear Threshold Model[C]//in Proceedings of the 2012 SIAM International Conference on Data Mining，2012：463-474．

[5] PENG W，LI P．Scalable Influence Blocking Maximization in Social Networks under Competitive Independent Cascade Models[J]．Computer Networks，2017，123（1）：38-50．

[6] 李勁，岳昆，張德海，等．社會網絡中影響力傳播的魯棒抑制方法[J]．計算機研究與發(fā)展，2016，53（3）：601-610．

[7] 李勁，岳昆，尤潔．面向不確定性影響源的社會網絡影響力傳播抑制方法[J]．電子與信息學報，2017，39（9）：2063-2070．

[8] ZHU W，YANG W，XUAN S．Location-Based Seeds Selection for Influence Blocking Maximization in Social Networks[J]．IEEE Access，2019，7（1）：27272-27287．

[9] ZHU W，YANG W，XUAN S．Location-Aware Influence Blocking Maximization in Social Networks[J]．IEEE Access，2018， 6（1）：61462-61477．

[10] Borgs C，Brautbar M，Chayes J．Maximizing social influence in nearly optimal time[C]//25th annual ACM-SIAM symposium on Discrete algorithms，2014：946-957．

[11] TONG G，WU W，GUO L．An Efficient Randomized Algorithm for Rumor Blocking in Online Social Networks[C]//IEEE INFOCOM 2017 IEEE Conference on Computer Communications，2017：1-9．

[12] CHEN L，ZHANG Y，CHEN Y．Negative Influence Blocking Maximization with Uncertain Sources under the Independent Cascade Model[J]．Information Sciences，2021，564（1）：343-367．

[13] Mohammad A，Mohammad S，Habibollah D．Non-Uniform Influence Blocking Maximization in Social Network[J]．Expert Systems with Applications，2022，207（1）：118052．

[14] TANG Y，SHI Y，XIAO X．Influence Maximization in Near-Linear Time：A Martingale Approach[C]//2015 ACM SIGMOD International Conference on Management of Data，2015：1539-1554．

Bad information suppression method based on improved reverse reachable set in online social networks

YANG Shuangshuang1，LIU Xingfei1，DING Long1，ZHU Wenlong2

（1. School of Teacher Education，2. School of Computer Science and Control Engineering，Qiqihar University，Qiqihar 161006，China）

With the development of the Internet，the bad information in online social networks presents the trend of rapidly growth，posing a threat to the stability and security of society．Traditional methods for suppressing bad information in online social networks suffer from issues such as low efficiency and poor real-time performance．Therefore，proposes an improved reverse reachable set based bad information suppression method in online social networks．Firstly，analysis the existing methods for suppressing bad information，and introduces the concept and principles of the reverse reachable set．Then，building on the theory of six degrees of separation，proposes an improved method for generating the reverse reachable set，and further puts forward a bad information suppression method called IRRIMM．Finally，experiments on real social dataset prove the effectiveness of the proposed method．

bad information suppression；six degrees of separation；reverse reachable set；online social networks

1007-9831（2023）12-0041-05

TP309.5

A

10.3969/j.issn.1007-9831.2023.12.007

2023-06-05

黑龍江省普通本科高等學校青年創(chuàng)新人才培養(yǎng)計劃項目（UNPYSCT-2020072）；黑龍江省教育科學規(guī)劃重點課題（GJB1421344）；黑龍江省教育廳基本科研業(yè)務專項青年項目（135509234,145109217）；齊齊哈爾大學教育科學研究項目（GJSKYB202001）

楊雙雙（1986-），女，黑龍江齊齊哈爾人，講師，碩士，從事信息技術研究．E-mail：yangshuangshuang@qqhru.edu.cn

朱文龍（1985-），男，黑龍江齊齊哈爾人，副教授，博士，從事計算機網絡研究．E-mail：zwl_qqhr@163.com