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

基于改進(jìn)反向可達(dá)集的在線社交網(wǎng)絡(luò)不良信息抑制方法

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

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

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

不良信息抑制；六度分隔理論；反向可達(dá)集；在線網(wǎng)絡(luò)

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

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

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

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

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

1 問題定義

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

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

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

2 改進(jìn)反向可達(dá)集和IRRIMM

算法1IRR set //生成改進(jìn)反向可達(dá)集

9 flag=true

13 end if

14 end for

16 end while

算法2IRRIMM

3 實驗驗證

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

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

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

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

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

４ 結(jié)語

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

[1] 周亞東，鄭慶華，陶敬．e-Learning中不良網(wǎng)絡(luò)內(nèi)容的識別與阻斷技術(shù)[J]．中國科技論文在線，2011（10）：765-769．

[2] 田亞平，楊力，王小琴．基于節(jié)點親密度挖掘的謠言抑制算法[J]．網(wǎng)絡(luò)與信息安全學(xué)報，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] 李勁，岳昆，張德海，等．社會網(wǎng)絡(luò)中影響力傳播的魯棒抑制方法[J]．計算機(jī)研究與發(fā)展，2016，53（3）：601-610．

[7] 李勁，岳昆，尤潔．面向不確定性影響源的社會網(wǎng)絡(luò)影響力傳播抑制方法[J]．電子與信息學(xué)報，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

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

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

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