基于改进反向可达集的在线社交网络不良信息抑制方法

杨双双，刘省非，丁龙，朱文龙

基于改进反向可达集的在线社交网络不良信息抑制方法

杨双双1，刘省非1，丁龙1，朱文龙2

（齐齐哈尔大学 1. 教师教育学院，2. 计算机与控制工程学院，黑龙江 齐齐哈尔 161006）

随着互联网的发展，网络中不良信息的数量呈现出快速增长的趋势，对于社会的稳定与安全构成了威胁．传统的在线社交网络不良信息抑制方法存在效率低、实时性差等问题，为此提出一种基于改进反向可达集的在线社交网络不良信息抑制方法．分析现有的网络不良信息抑制方法，介绍了反向可达集的概念和原理，基于六度分隔理论，提出一种改进反向可达集的生成方法，并进一步提出一种不良信息抑制方法IRRIMM．通过在真实的社交网络数据集中的实验验证了所提出方法的有效性．

不良信息抑制；六度分隔理论；反向可达集；在线网络

移动互联网时代，在线社交网络不断涌现，国内如抖音、斗鱼，国外如TikTok，Twitter等，吸引了大量的用户参与到网络中．在线网络在人们生活中发挥了积极的作用，但同时网络中的一些不良信息，如低俗图像、虚假信息、不良言论等在互联网中传播迅速、危害性极大．当不良信息发生时，如何有效地抑制不良信息的传播，是目前社交网络研究中的一个热点问题，其解决方法主要有两种：

第１种方法是通过挖掘网络中关键节点或边信息，对其隔离，使得不良信息无法通过其传播．以在线社交网络（见图1）为例，图1中包含有12个节点，节点间的有向边表示信息的传播方向．假设节点1是不良信息源，在没有任何抑制手段的情况下，节点1产生的不良信息将随信息传播发送到节点2，3，4，5，6，7，8，导致这些节点被不良信息所影响，假设目前需要寻找一个关键节点抑制不良信息，则会选择节点5，因为该节点能够抑制不良信息传递到节点6，7，8．

目前，国内外许多学者从挖掘关键节点或边的角度对不良信息的抑制开展了研究，取得了一定的研究成果．例如：周亚东[1]等提出了一种利用快速URL识别技术寻找关键节点用于e-Learning的不良网络内容的识别与抑制技术．田亚平[2]等利用节点行为信息挖掘网络意见领袖用于不良信息抑制．WANG[3]等利用用户经验信息构建树形传播结构，并通过在结构树中选择节点来免疫不良信息节点的攻击．虽然通过在网络中挖掘关键节点或者边并对其进行隔离可以在一定程度上抑制不良信息的传播，但这种方法也存在非常明显的缺点，即对节点或边的隔离会影响网络的连通，导致正常信息也不能传播．

图1 利用关键节点抑制不良信息传播

图2 利用传播正面消息抑制不良信息传播

1 问题定义

He[4]468等证明了影响力阻断最大化问题具有NP难特性，可以使用贪婪算法解决，然而由于贪婪算法效率过低，在实际应用中并不适用．借鉴反向影响力采样思想，本文提出一种基于改进反向可达集的方法解决该问题，反向影响力采样思想的核心是构造一组反向可达集，并基于此对种子节点的影响力扩展度进行无偏估计．

Tang[14]1542等证明了当反向可达集的数量达到一定规模时，具有较大影响力的节点会经常出现在反向可达集中，即种子集在反向可达集中的出现概率是它在原网络中影响力的无偏估计，可用公式表述

式（2）更一般的解释是如果一个节点具有更大的影响力，那么它出现在反向可达集中的概率也应该更大．基于该思想，可以有效地选择种子节点．但反向可达集最初被用来解决影响力最大化问题，并没有考虑到竞争因素，因此，在影响力阻断最大化问题中并不适用．

2 改进反向可达集和IRRIMM

算法1IRR set //生成改进反向可达集

9 flag=true

13 end if

14 end for

16 end while

算法2IRRIMM

3 实验验证

利用Facebook数据集进行实验验证．数据集可以通过SNAP的官方网站进行下载，下载地址是http://snap.stanford.edu/data/index.html．该数据集是基于Facebook的用户社交关系数据集，其中包含4 039个节点和88 234条边，图中节点的平均度为21.84，最大度为1 045．实验中将本文提出的IRRIMM算法与Random、Degree、DD算法进行了比较，具体信息为：

不同算法在权重级联模型下的负激活节点数见图3，从结果中可以看出，本文提出的方法在相同正种子数下负激活节点数最低，因此具有最好的不良消息抑制性能．其次是DD和Degree算法，而Random算法由于随机选择节点作为种子节点，其抑制性能最差．另外，可以看到随着正种子数的增多，被负种子节点激活的节点数不断减少．这与理论上是一致的，因为正种子数越多，将有越多的节点可以接收到正种子传播的正面信息，导致被负种子激活的节点数减少．

不同算法在统一概率模型下的负激活节点数见图4．本文提出的方法依然具有最好的性能．另外，从图中可以看到，在正种子数较少时，DD算法的抑制性能优于Degree算法，但是随着正种子数的增多，DD算法的性能逐渐被Degree算法超越，因为这两种算法都是启发式算法，并不能保证算法的可靠性．

图3 权重级联模型下不同算法负激活节点数对比

图4 统一概率模型下不同算法负激活节点数对比

４ 结语

网络中不良信息的泛滥是亟待解决的问题，本文通过引入六度分隔理论，提出了一种改进的反向可达集生成方法，其核心思想是如果反向可达集中的正向节点能够比负向节点更早到达反向可达集的根节点，且它们之间的间隔不超过6度，则该反向可达集是一个有效的可达集．在此基础上，提出了IRRIMM算法，算法包括采样和种子节点选择两个阶段．采样阶段计算所需改进反向可达集数量的下界并生成相应数量的改进反向可达集，节点选择阶段利用贪婪覆盖算法选择种子节点．通过在真实的社交网络数据集上的实验表明，本文提出的方法具有较好的性能，能够有效抑制网络中不良信息的传播．

[1] 周亚东，郑庆华，陶敬．e-Learning中不良网络内容的识别与阻断技术[J]．中国科技论文在线，2011（10）：765-769．

[2] 田亚平，杨力，王小琴．基于节点亲密度挖掘的谣言抑制算法[J]．网络与信息安全学报，2016（11）：61-69．

[3] WANG B，CHEN G，FU 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]．计算机研究与发展，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

黑龙江省普通本科高等学校青年创新人才培养计划项目（UNPYSCT-2020072）；黑龙江省教育科学规划重点课题（GJB1421344）；黑龙江省教育厅基本科研业务专项青年项目（135509234,145109217）；齐齐哈尔大学教育科学研究项目（GJSKYB202001）

杨双双（1986-），女，黑龙江齐齐哈尔人，讲师，硕士，从事信息技术研究．E-mail：yangshuangshuang@qqhru.edu.cn

朱文龙（1985-），男，黑龙江齐齐哈尔人，副教授，博士，从事计算机网络研究．E-mail：zwl_qqhr@163.com