基于敏感节点免疫的负面信息级联阻挡方法与流程

1.本发明属于复杂网络应用技术领域，具体涉及基于敏感节点免疫的负面信息级联阻挡方法。


背景技术：

2.随着互联网行业的不断发展，新媒体的多样性使得信息传播渠道由单一化向多元化发展，这给人们的生产和日常生活提供了巨大的便利，但同时也带来了负面的影响。如今互联网上的负面信息泛滥，对营造健康向上的网络环境造成极大的影响和阻力，甚至可能造成不必要的社会恐慌。因此负面信息引导和控制显得尤为重要，近年来，越来越多的学者开始关注复杂网络领域，期望从中找到行之有效的负面信息传播控制方法。
3.在复杂网络中，节点免疫作为信息传播控制的有效方法，广泛应用于传染病、谣言以及负面信息传播控制领域。在已有的研究当中，经典的免疫策略主要含有随机免疫、目标免疫以及熟人免疫。随后研究者在这些经典免疫策略的基础上提出了许多改进策略，而这些免疫策略大多是基于高中心性指标来选择要免疫的节点，节点免疫会导致网络拓扑结构损坏严重，且难以实施。基于此，alex等人提出了缓解级联故障(pmcf)方法，引入了一种关键节点的选择方法，该方法保证了网络更好地生存。但是pmcf方法适用范围不够广泛，对于具有丰富社团结构的网络有一定的局限性。


技术实现要素：

4.本发明所要解决的技术问题在于克服上述现有技术的缺点，提供一种部署简单、易于推广的基于有限敏感节点免疫的负面信息级联阻挡方法，该方法适用于社团结构明显的社会网络中信息传播的引导和控制。
5.解决上述技术问题所采用的技术方案是由下述步骤组成：
6.(1)构建负面信息传播模型
7.将网络中的n个节点作为元胞，n为有限正整数，采用元胞自动机方法将元胞空间c、有限状态集q、元胞领域v、元胞状态转换规则函数δ四要素构建成动态的易感—易染—易感的负面信息传播模型。
8.(2)网络图初始化
9.给定网络图并初始化，选取a％的节点作为初始感染源，a∈(0,10]。
10.(3)获取社团结构信息
11.用网络社团划分方法，得到网络图的社团结构信息，该社团结构信息包括网络图的社区划分结果以及每个社团结构的节点数。
12.(4)确定级联敏感节点集
13.(4a)在节点数最多的社团结构中先随机选择一个节点i，按式(1)确定节点i为敏感节点：
14.15.式中为网络图平均度，k
i
为被选节点i的度且不为0，q为信息传播门槛值，0<q<1。
16.(4b)用公式(1)确定敏感节点中至少2个相邻敏感节点，即为级联敏感节点。
17.(4c)将级联敏感节点加入级联敏感节点集。
18.(4d)选择下一个节点，重复步骤(4a)直至选择完所有节点，得到级联敏感节点集。
19.(5)确定最优级联敏感节点子集
20.(5a)在级联敏感节点集中根据节点及其邻居度值之和由大到小对节点进行排序。
21.(5b)在级联敏感节点集中依次选择一个满足式(2)的节点：
[0022][0023]
式中vc(i)为节点i直接相连的社团结构数，vc(i)＞1，为级联敏感节点集度的平均值。
[0024]
(5c)重复步骤(5b)直到判断完所有节点，将被选节点组成最优级联敏感节点子集。
[0025]
(6)确定免疫节点数d％
[0026]
采用广度优先搜索方法统计随着免疫节点数目的增加，剩余网络最大连通子图的节点数目占网络总节点的比值的变化情况，在比值满足80％～90％时，确定免疫节点数d％。
[0027]
(7)阻挡负面信息级联
[0028]
删除最优级联敏感节点子集中前d％比例的节点，阻挡了负面信息级联。
[0029]
在本发明的(1)构建负面信息传播模型步骤中，所述的元胞空间c为：初始时刻建立包含有n个元胞的一维元胞空间。本发明的有限状态集q为：节点对应元胞的状态分为易感状态s和感染状态i，分别用0和1表示，有限状态集q如下：
[0030]
q＝{0,1}
[0031]
按下式确定状态变量s
i
(t)：
[0032][0033]
式中s
i
(t)表示在t时刻节点i的状态变量，s
i
(t)∈q。所述的元胞领域v为元胞邻居之间的关系，即节点的直接邻居。所述的元胞状态转换规则函数δ为：在任何时刻t，s态和i态节点之间的元胞状态转换规则函数δ如下：
[0034][0035][0036]
式中上横线表示取反操作，h表示s态和i态节点之间的状态转换规则判断函数，p
i
表示节点i直接邻居中处于感染态的节点数目占其总邻居数目的比率，q表示信息传播门槛值，0<q<1，β表示恢复率，0<β<1，λ表示恢复率的判断值，λ在(0，1)之间随机取值。
[0037]
在本发明的(2)设置网络图并初始化步骤中，所述的a取值最佳为5。
[0038]
在本发明的(4)确定级联敏感节点集步骤中，所述的q为信息传播门槛值，q取值最佳为0.2。
[0039]
本发明与现有技术相比，在保证有限资源以及网络结构生存性能不受影响的前提
下，选取免疫级联过程中的最少最优级联敏感节点，可降低负面信息传播速度和限制负面信息传播范围；在社团结构明显的复杂网络中，对于阻挡负面信息级联起到了很好的效果，具有一定的可实施性与有效性。采用本发明与随机节点免疫、节点度免疫、节点介数免疫、pmcf方法进行了对比仿真实验，实验结果表明，本发明优于随机节点免疫、节点度免疫、节点介数免疫、pmcf方法，本发明可以有效地阻挡负面信息的传播速度与传播范围。本发明具有部署简单、易于推广，能有效地阻挡负面信息的传播等优点，可广泛应用于舆情、谣言、病毒营销等技术领域，对负面信息传播进行阻挡以及控制。
附图说明
[0040]
图1是本发明实施例1的流程图。
[0041]
图2是zachary网络结构生存性p0与免疫节点数目的关系图。
[0042]
图3是zachary网络负面信息感染节点所占比例i(t)的变化曲线图。
[0043]
图4是political books网络结构生存性p0与免疫节点数目的关系图。
[0044]
图5是political books网络负面信息感染节点所占比例i(t)的变化曲线图。
具体实施方式
[0045]
下面结合附图和实施例对本发明进一步详细说明，但本发明不限于下述的实施方式。
[0046]
实施例1
[0047]
以在konect数据库中取空手道俱乐部zachary网络为例，本实施例的基于敏感节点免疫的负面信息级联阻挡方法，由以下步骤组成(参见图1)：
[0048]
(1)构建负面信息传播模型
[0049]
将网络中的n个节点作为元胞，n为有限正整数，采用元胞自动机方法将元胞空间c、有限状态集q、元胞领域v、元胞状态转换规则函数δ四要素构建成动态的易感—易染—易感的负面信息传播模型。
[0050]
所述的元胞空间c为：初始时刻建立包含有n个元胞的一维元胞空间。
[0051]
所述的有限状态集q为：节点对应元胞的状态分为易感状态s和感染状态i，分别用0和1表示，有限状态集q如下：
[0052]
q＝{0,1}
[0053]
按下式确定状态变量s
i
(t)：
[0054][0055]
式中s
i
(t)表示在t时刻节点i的状态变量，s
i
(t)∈q。
[0056]
所述的元胞领域v为元胞邻居之间的关系，即节点的直接邻居。
[0057]
所述的元胞状态转换规则函数δ为：在任何时刻t，s态和i态节点之间的元胞状态转换规则函数δ如下：
[0058][0059]
[0060]
式中上横线表示取反操作，h表示s态和i态节点之间的状态转换规则判断函数，p
i
表示节点i直接邻居中处于感染态的节点数目占其总邻居数目的比率，q表示信息传播门槛值，0<q<1，本实施例的q取值为0.2，β表示恢复率，0<β<1，本实施例的β取值为0.2，λ表示恢复率的判断值，λ在(0，1)之间随机取值。
[0061]
(2)网络图初始化
[0062]
在konect数据库中取空手道俱乐部zachary网络，zachary网络节点数34；将该网络进行初始化，选取a％的节点作为初始感染源，a∈(0,10]，本实施例的a取值为5。
[0063]
(3)获取社团结构信息
[0064]
用网络社团划分方法，将空手道俱乐部zachary网络的社团结构进行划分，得到上述网络图的社团结构信息，该社团结构信息包括网络图的社区划分结果以及每个社团结构的节点数；zachary网络划分为2个社团结构，社团结构节点个数分别为16和18。
[0065]
(4)确定级联敏感节点集
[0066]
(4a)在节点数最多的社团结构中先随机选择一个节点i，按式(1)确定节点i为敏感节点：
[0067][0068]
式中为网络图平均度，k
i
为被选节点i的度且不为0，q为信息传播门槛值，0<q<1，本实施例的q取值为0.2。
[0069]
(4b)用公式(1)确定敏感节点中至少2个相邻敏感节点，即为级联敏感节点。
[0070]
(4c)将级联敏感节点加入级联敏感节点集。
[0071]
(4d)选择下一个节点，重复步骤(4a)直至选择完所有节点，得到级联敏感节点集。
[0072]
(5)确定最优级联敏感节点子集
[0073]
(5a)在级联敏感节点集中根据节点及其邻居度值之和由大到小对节点进行排序。
[0074]
(5b)在级联敏感节点集中依次选择一个满足式(2)的节点：
[0075][0076]
式中vc(i)为节点i直接相连的社团结构数，vc(i)＞1，为级联敏感节点集度的平均值。
[0077]
(5c)重复步骤(5b)直到判断完所有节点，将被选节点组成最优级联敏感节点子集。
[0078]
(6)确定免疫节点数d％
[0079]
采用广度优先搜索方法统计随着免疫节点数目的增加，剩余网络最大连通子图的节点数目占网络总节点的比值的变化情况，在比值满足80％～90％时，确定免疫节点数d％。
[0080]
(7)阻挡负面信息级联
[0081]
删除最优级联敏感节点子集中前d％比例的节点，阻挡了负面信息级联。
[0082]
实施例2
[0083]
以在konect数据库中取空手道俱乐部zachary网络为例，本实施例的基于敏感节点免疫的负面信息级联阻挡方法，由以下步骤组成：
[0084]
(1)构建负面信息传播模型
[0085]
该步骤与实施例1相同。
[0086]
(2)网络图初始化
[0087]
在konect数据库中取空手道俱乐部zachary网络，zachary网络节点数34，将网络进行初始化，选取a％的节点作为初始感染源，a∈(0,10]，本实施例的a取值为1。
[0088]
(3)获取社团结构信息
[0089]
该步骤与实施例1相同。
[0090]
(4)确定级联敏感节点集
[0091]
(4a)在节点数最多的社团结构中先随机选择一个节点i，按式(1)确定节点i为敏感节点：
[0092][0093]
式中为网络图平均度，k
i
为被选节点i的度且不为0，q为信息传播门槛值，0<q<1，本实施例的q取值为0.1。
[0094]
该步骤的其它步骤与实施例1相同。
[0095]
其它步骤与实施例1相同。完成基于敏感节点免疫的负面信息级联阻挡方法。
[0096]
实施例3
[0097]
以在konect数据库中取空手道俱乐部zachary网络为例，本实施例的基于敏感节点免疫的负面信息级联阻挡方法，由以下步骤组成：
[0098]
(1)构建负面信息传播模型
[0099]
该步骤与实施例1相同。
[0100]
(2)网络图初始化
[0101]
在konect数据库中取空手道俱乐部zachary网络，zachary网络节点数34，将网络进行初始化，选取a％的节点作为初始感染源，a∈(0,10]，本实施例的a取值为10。
[0102]
(3)获取社团结构信息
[0103]
该步骤与实施例1相同。
[0104]
(4)确定级联敏感节点集
[0105]
(4a)在节点数最多的社团结构中先随机选择一个节点i，按式(1)确定节点i为敏感节点：
[0106][0107]
式中为网络图平均度，k
i
为被选节点i的度且不为0，q为信息传播门槛值，0<q<1，本实施例的q取值为0.9。
[0108]
该步骤的其它步骤与实施例1相同。
[0109]
其它步骤与实施例1相同。完成基于敏感节点免疫的负面信息级联阻挡方法。
[0110]
实施例4
[0111]
以在konect数据库中取美国政治书籍political books网络为例，本实施例的基于敏感节点免疫的负面信息级联阻挡方法，由以下步骤组成：
[0112]
(1)构建负面信息传播模型
[0113]
将网络中的n个节点作为元胞，n为有限正整数，采用元胞自动机方法将元胞空间c、有限状态集q、元胞领域v、元胞状态转换规则函数δ四要素构建成动态的易感—易染—易感的负面信息传播模型。
[0114]
所述的元胞空间c为：初始时刻建立包含有n个元胞的一维元胞空间。
[0115]
所述的有限状态集q为：节点对应元胞的状态分为易感状态s和感染状态i，分别用0和1表示，有限状态集q如下：
[0116]
q＝{0,1}
[0117]
按下式确定状态变量s
i
(t)：
[0118][0119]
式中s
i
(t)表示在t时刻节点i的状态变量，s
i
(t)∈q。
[0120]
所述的元胞领域v为元胞邻居之间的关系，即节点的直接邻居。
[0121]
所述的元胞状态转换规则函数δ为：在任何时刻t，s态和i态节点之间的元胞状态转换规则函数δ如下：
[0122][0123][0124]
式中上横线表示取反操作，h表示s态和i态节点之间的状态转换规则判断函数，p
i
表示节点i直接邻居中处于感染态的节点数目占其总邻居数目的比率，q表示信息传播门槛值，0<q<1，本实施例的q取值为0.2，β表示恢复率，0<β<1，本实施例的β取值为0.2，λ表示恢复率的判断值，λ在(0，1)之间随机取值。
[0125]
(2)网络图初始化
[0126]
在konect数据库中取美国政治书籍political books网络，political books网络节点数105。将该网络进行初始化，选取a％的节点作为初始感染源，a∈(0,10]，本实施例的a取值为5。
[0127]
(3)获取社团结构信息
[0128]
用网络社团划分方法，将美国政治书籍political books网络的社团结构进行划分，得到上述网络图的社团结构信息，该社团结构信息包括网络图的社区划分结果以及每个社团结构的节点数；political books网络划分为4个社团结构，社团结构节点个数分别为5、41、12、47。
[0129]
(4)确定级联敏感节点集
[0130]
(4a)在节点数最多的社团结构中先随机选择一个节点i，按式(1)确定节点i为敏感节点：
[0131][0132]
式中为网络图平均度，k
i
为被选节点i的度且不为0，q为信息传播门槛值，0<q<1，本实施例的q取值为0.2。
[0133]
(4b)用公式(1)确定敏感节点中至少2个相邻敏感节点，即为级联敏感节点。
[0134]
(4c)将级联敏感节点加入级联敏感节点集。
[0135]
(4d)选择下一个节点，重复步骤(4a)直至选择完所有节点，得到级联敏感节点集。
[0136]
其它步骤与实施例1相同。完成基于敏感节点免疫的负面信息级联阻挡方法。
[0137]
实施例5
[0138]
以在konect数据库中取美国政治书籍political books网络为例，本实施例的基于敏感节点免疫的负面信息级联阻挡方法，由以下步骤组成：
[0139]
(1)构建负面信息传播模型
[0140]
该步骤与实施例4相同。
[0141]
(2)网络图初始化
[0142]
在stanford和konect数据库中取美国政治书籍political books网络，political books网络节点数34，将网络进行初始化，选取a％的节点作为初始感染源，a∈(0,10]，本实施例的a取值为1。
[0143]
(3)获取社团结构信息
[0144]
该步骤与实施例4相同。
[0145]
(4)确定级联敏感节点集
[0146]
该步骤与实施例4相同。
[0147]
其它步骤与实施例4相同。完成基于敏感节点免疫的负面信息级联阻挡方法。
[0148]
实施例6
[0149]
以在konect数据库中取美国政治书籍political books网络为例，本实施例的基于敏感节点免疫的负面信息级联阻挡方法，由以下步骤组成：
[0150]
(1)构建负面信息传播模型
[0151]
该步骤与实施例4相同。
[0152]
(2)网络图初始化
[0153]
在konect数据库中取美国政治书籍political books网络，political books网络节点数34，将网络进行初始化，选取a％的节点作为初始感染源，a∈(0,10]，本实施例的a取值为10。
[0154]
(3)获取社团结构信息
[0155]
该步骤与实施例4相同。
[0156]
(4)确定级联敏感节点集
[0157]
该步骤与实施例4相同。
[0158]
其它步骤与实施例4相同。完成基于敏感节点免疫的负面信息级联阻挡方法。
[0159]
为了验证本发明的有益效果，发明人采用本发明实施例1和实施例4的基于敏感节点免疫的负面信息级联阻挡方法(实验时简称sni)与无策略(no strategy)、随机节点免疫(random nodes)、节点度免疫(degree centrality)、节点介数免疫(betweenness centrality)以及缓解级联故障(pmcf)方法进行了对比仿真实验，实验情况如下：
[0160]
实验1
[0161]
采用本发明实施例1的基于敏感节点免疫的负面信息级联阻挡方法进行了仿真实验，实验结果见图2、3，在图2中，横坐标是zachary网络免疫节点数，纵坐标是网络结构生存性p0，网络结构生存性等于剩余网络最大连通子图的节点数目占网络总节点的比值；在图3中，横坐标是zachary网络负面信息感染节点所占比例i(t)，纵坐标是时间t。由图2可见，在
zachary网络中，随着免疫节点数增加，网络结构生存性po逐渐下降。当免疫节点数比例小于12％时，实施例1方法能保证网络结构生存性达到85％，不仅能阻挡负面信息的传播，也使得免疫节点所导致的网络损坏程度很弱，对网络的生存性能不受影响。在给定满足网络结构生存性需求的情况下，可用来控制免疫节点数。由图3可见，与无策略相比，在免疫节点数相同的情况下，其他节点免疫策略在传播速度与传播范围方面都控制了负面信息的传播。其中节点度免疫和节点介数免疫的控制力度甚至高于实施例1方法，但是由图2可知，这两种方法导致网络结构生存性低于30％，严重损害了网络结构的相对完整性以及网络生存性能，因此在zachary网络中，节点度免疫与节点介数免疫策略不被推荐。pmcf方法虽然保证了网络结构高的生存性，但是它的控制效果低于实施例1方法。结合以上所知，在zachary网络中，实施例1方法优于其他四种免疫方法。
[0162]
实验2
[0163]
采用本发明实施例4的基于敏感节点免疫的负面信息级联阻挡方法进行了仿真实验，实验结果见图4、5，在图4中，横坐标是political books网络免疫节点数，纵坐标是网络结构生存性p0，网络结构生存性等于剩余网络最大连通子图的节点数目占网络总节点的比值；在图5中，横坐标是political books网络负面信息感染节点所占比例i(t)，纵坐标是时间t。由图4、5可见，在免疫节点比例相同的情况下，在political books网络中，实施例4方法优于其他四种免疫策略，有效地控制了负面信息的传播速度与传播范围，保证了网络结构很高的生存性。
[0164]
结合实验1和2的结果，由以上分析可知：(1)在有限资源管控以及网络结构基本生存性能不受影响的情况下，本发明优于随机节点免疫、节点度免疫、节点介数免疫、pmcf方法，可以有效阻挡负面信息的传播速度与传播范围；(2)不论是面向zachary网络，还是political books网络都可以看出，在社团结构明显的复杂网络中，本发明方法对于阻挡负面信息级联都起到了很好的效果，具有一定的可实施性与有效性。
[0165]
尽管以上结合附图对本公开的实施方案进行了描述，但本公开并不局限于上述的具体实施方案和应用领域，上述的具体实施方案仅仅是示意性的、指导性的，而不是限制性的。本领域的普通技术人员在本说明书的启示下和在不脱离本公开权利要求所保护的范围的情况下，还可以做出很多种的形式，这些均属于本公开保护之列。

技术特征：
1.一种基于敏感节点免疫的负面信息级联阻挡方法，其特征在于由下述步骤组成：(1)构建负面信息传播模型将网络中的n个节点作为元胞，n为有限正整数，采用元胞自动机方法将元胞空间c、有限状态集q、元胞领域v、元胞状态转换规则函数δ四要素构建成动态的易感—易染—易感的负面信息传播模型；(2)网络图初始化给定网络图并初始化，选取a％的节点作为初始感染源，a∈(0,10]；(3)获取社团结构信息用网络社团划分方法，得到网络图的社团结构信息，该社团结构信息包括网络图的社区划分结果以及每个社团结构的节点数；(4)确定级联敏感节点集(4a)在节点数最多的社团结构中先随机选择一个节点i，按式(1)确定节点i为敏感节点：式中为网络图平均度，k
i
为被选节点i的度且不为0，q为信息传播门槛值，0<q<1；(4b)用公式(1)确定敏感节点中至少2个相邻敏感节点，即为级联敏感节点；(4c)将级联敏感节点加入级联敏感节点集；(4d)选择下一个节点，重复步骤(4a)直至选择完所有节点，得到级联敏感节点集；(5)确定最优级联敏感节点子集(5a)在级联敏感节点集中根据节点及其邻居度值之和由大到小对节点进行排序；(5b)在级联敏感节点集中依次选择一个满足式(2)的节点；式中vc(i)为节点i直接相连的社团结构数，vc(i)＞1，为级联敏感节点集度的平均值；(5c)重复步骤(5b)直到判断完所有节点，将被选节点组成最优级联敏感节点子集；(6)确定免疫节点数d％采用广度优先搜索方法统计随着免疫节点数目的增加，剩余网络最大连通子图的节点数目占网络总节点的比值的变化情况，在比值满足80％～90％时，确定免疫节点数d％；(7)阻挡负面信息级联删除最优级联敏感节点子集中前d％比例的节点，阻挡了负面信息级联。2.根据权利要求1所述的基于敏感节点免疫的负面信息级联阻挡方法，其特征在于在(1)构建负面信息传播模型步骤中，所述的元胞空间c为：初始时刻建立包含有n个元胞的一维元胞空间；所述的有限状态集q为：节点对应元胞的状态分为易感状态s和感染状态i，分别用0和1表示，有限状态集q如下：q＝{0,1}按下式确定状态变量s
i
(t)：
式中s
i
(t)表示在t时刻节点i的状态变量，s
i
(t)∈q；所述的元胞领域v为元胞邻居之间的关系，即节点的直接邻居；所述的元胞状态转换规则函数δ为：在任何时刻t，s态和i态节点之间的元胞状态转换规则函数δ如下：规则函数δ如下：式中上横线表示取反操作，h表示s态和i态节点之间的状态转换规则判断函数，p
i
表示节点i直接邻居中处于感染态的节点数目占其总邻居数目的比率，q表示信息传播门槛值，0<q<1，β表示恢复率，0<β<1，λ表示恢复率的判断值，λ在(0，1)之间随机取值。3.根据权利要求1所述的基于敏感节点免疫的负面信息级联阻挡方法，其特征在于：在(2)设置网络图并初始化步骤中，所述的a取值为5。4.根据权利要求1所述的基于敏感节点免疫的负面信息级联阻挡方法，其特征在于：在(4)确定级联敏感节点集步骤中，所述的q为信息传播门槛值，q取值为0.2。
技术总结
一种基于敏感节点免疫的负面信息级联阻挡方法，由构建负面信息传播模型、网络图初始化、获取社团结构信息、确定级联敏感节点集、确定最优级联敏感节点子集、确定免疫节点数d％、阻挡负面信息级联步骤组成。在保证有限资源以及网络结构生存性能不受影响的前提下，选取免疫级联过程中的最少最优级联敏感节点，可降低负面信息传播速度和限制负面信息传播范围；在社团结构明显的复杂网络中，对于阻挡负面信息级联起到了很好的效果，具有一定的可实施性与有效性，可有效地阻挡负面信息的传播速度与传播范围。本发明具有部署简单、易于推广，能有效地阻挡负面信息的传播等优点，可应用于舆情、谣言、病毒营销等技术领域。病毒营销等技术领域。病毒营销等技术领域。


技术研发人员：李黎 郑晓华 韩静 张立臣 李鹏 王小明
受保护的技术使用者：陕西师范大学
技术研发日：2021.03.25
技术公布日：2021/6/29