一种基于社会传感器优化的网络级联传播早期发现方法

摘要

本发明公开了一种基于社会传感器优化的网络级联传播早期发现方法。本方法为：对于目标领域的网络图G，设置一目标函数，并对该目标函数进行求解，得到一社会传感器集合S；其中，社会传感器集合S中的每一社会传感器对应于该目标领域的网络中的一节点；将该网络中该社会传感器集合S对应的节点作为信息采集节点，然后根据各所述信息采集节点采集的信息识别该网络中的级联信息。本方法重点在于区别对待网络中不同重要性的级联信息，减弱重要性低的级联信息对方法的影响，从而使用高效利用网络中的社会传感器更快、更全的发现重要的级联信息。

说明书

技术领域

本发明属于网络传感器-信息级联传播-级联异常检测技术领域，涉及一种基于社会传感器优化的网络级联传播早期发现方法。

背景技术

随着Web2.0技术的迅猛发展，世界各国的(在线)社交网络都经历了一个飞速发展的阶段，用户规模呈现出爆发式增长的趋势。社交网络本身具有的自由性和开放性的特点，使其成为了当代社会中重要的消息传播途径，社交网络也因此汇聚了前所未有的当代社会信息。与此同时，在社交网络中及时发现异常信息成为亟待解决的问题。

在污水检测中，给定水循环网络，放置传感器，我们能够及时发现水循环网络中的污染情况。同样，给定社交网络，在社交网络中选择节点放置社会传感器，监控这些节点，我们能够及时的探测到网络中经过这些节点的信息传播(信息级联)。通过在社交网络中放置社会传感器，我们能够及时检测到社交网络当中的信息传播，从而进行及时的舆情监控及引导。因此，异常信息检测的任务可以转化为社交网络中放置高效社会传感器的问题。为了更选出更高效的社会传感器，目前很多方法利用社交网络的结构信息，如节点的度、介数中心性等，同时也利用社交网络中的信息传播特征，如信息级联，时间戳等。

CELF是Jure Leskovec提出的从网络结构中寻找传感器从而尽早检测到信息流传播的方法。在寻找传感器的过程中，CELF利用了网络上的级联信息，如博文转发信息级联等，并提出了贪婪算法寻找网络结构中的传感器，使得传感器能够尽早的发现网络中的信息级联。

与此同时，最大入度法利用社交网络的结构信息也可以从网络结构中寻找传感器，并使得流经传感器的级联尽可能得多。

CELF算法和最大入度法都可以应用于网络中级联信息的早期发现，并有着不错的效果。但是在真实的网络中，相似的网络中，级联信息却存在着很大的差异，如水污染网络中的级联信息发生频率相对较少，社交通信网络中，通讯的级联信息发生的频率高，产生的级联数据也多。最大入度法，只考虑网络的静态结构，并未考虑网络中的级联信息。此外，此联信息本身有着不同的重要性，在水污染网络中，认为污染级联同等重要应当一视同仁，但是在社交网络中，不同的信息级联有着不同的重要性应当区别对待。在CELF算法中，算法尽可能尽早地发现所有的级联信息，并未对不同的级联信息进行区别对待。这种做法适用于级联信息同等重要的情节，而在社交网络中，不同的级联信息往往具备着不同的重要性，比如传播路径长的级联往往影响深远，这类级联信息应该尽早检测，传播路径小的级联往往重要性小，而且存在较多噪声。

目前的级联早期发现方法对网络中的级联信息同等对待，所以在使用中存在问题：

1.现有的方法大多数只利用了静态的网络结构信息，这类方法在实际的网络当中不能根据实际的级联传播进行相应的调整。

2.现有利用了级联信息的方法，对级联信息同等对待，不重要的级联会带来较多影响，影响方法的整体效果。

发明内容

本发明针对背景技术中描述的现状，提出一种基于社会传感器优化的网络级联传播早期发现方法。本方法重点在区别对待网络中不同重要性的级联信息，减弱重要性低的级联信息对方法的影响，从而使用高效利用网络中的社会传感器更快、更全的发现重要的级联信息。

本发明利用混合量纲的方法，增加重要级联的权重，使得本方法能够使用更少的传感器更快的检测到重要的级联信息。本发明利用可调节参数，使得方法根据具体需求应用于不同的网络当中。

本发明的技术方案为：

一种基于社会传感器优化的网络级联传播早期发现方法，其步骤包括：

1)对于目标领域的网络图G＝(V,E)，其中V为图G中节点的集合，E为节点间关系的集合；获取该目标领域的网络中的信息级联集合C＝{c₁,c₂,…,c_k}，第k个级联信息中的元素表示级联k到达节点i的时间与级联k首次出现时间的差值；

2)设置一目标函数，并对该目标函数进行求解，得到一社会传感器集合S；其中，社会传感器集合S中的每一社会传感器对应于该目标领域的网络中的一节点；该目标函数为C_A为社会传感器集合S检测到的级联信息集合，K₁为C_A中级联信息的数量；c′_k∈C′,C′为社会传感器集合S未检测到的级联信息集合，K₂为C′中级联信息的数量，|c′_k|表示级联c′_k所传达到节点的数量，C_A∪C′＝C，K为C中级联信息的数量，T(S,c_k)为社会传感器集S对于级联ck的感知时间，级联c′_k的长度|c′_k|等于级联c′_k在其生命周期中传达到的节点数量，α为平衡参数，M为需要的社会传感器数量；

3)将该网络中该社会传感器集合S对应的节点作为信息采集节点，然后根据各所述信息采集节点采集的信息识别该网络中的级联信息。

进一步的，利用贪心算法对该目标函数进行求解，每次选出带来损失Loss(S)最小的节点v，加入传感器集合S。

进一步的，所述平衡参数其中T_max是监测级联的最大时间，L_aim是可调节的超参。

进一步的，所述目标领域为社交领域，所述网络图G为社交关系网络图，V为图中的用户集合，E为图中朋友关系的集合。

进一步的，所述感知时间

一种基于社会传感器优化的网络级联传播早期发现方法，其步骤包括：

1)对于目标领域的网络图G＝(V,E)，其中V为图G中节点的集合，E为节点间关系的集合；获取该目标领域的网络中的信息级联集合C＝{c₁,c₂,…,c_k}，第k个级联信息中的元素表示级联k到达节点i的时间与级联k首次出现时间的差值；

2)设置一目标函数，并对该目标函数进行求解，得到一社会传感器集合S；其中，社会传感器集合S中的每一社会传感器对应于该目标领域的网络中的一节点；该目标函数为由此目标函数推出计算每一节点增益的公式为C_v为节点v可以先于传感器集S检测到的级联信息集合，K₁为C_v中级联信息的数量；c′_k∈C′,C′为节点v和传感器集S均未检测到的级联信息集合，K₂为C′中级联信息的数量，T(S,c_k)为社会传感器集S对于级联c_k的感知时间，级联c′_k的长度|c′_k|等于级联c′_k在其生命周期中传达到的节点数量，α为平衡参数，M为需要的社会传感器数量；

3)将该网络中该社会传感器集合S对应的节点作为信息采集节点，然后监控这些信息采集节点，多个传感器采集到同一信息即可构成级联信息，由此可监控级联的传播。

进一步的，利用贪心算法对该目标函数进行求解，每次选出带来增益Increase(v)最大的节点v，加入传感器集合S。

通过采取上述技术方案，本发明具有以下优点：

本发明能够根据需求进行调整、抓大放小；且本发明通过设置更优目标函数，通过贪心算法找到社交网络中的网络传感器，这些传感器能够以更少的数量更加全面快速的发现网络中的重要级联。

附图说明

图1为本发明的方法流程图；

图2为数据集中级联长度的分布图。

具体实施方式

为了使本发明的目的、技术方案及优点更加的清楚明白，以下引入一些定义，并通过实例对本发明作进一步的详细说明。

1.目标领域的网络图：图G＝(V,E)，其中V为图G中节点的集合，E为节点间关系的集合。以社交领域为例，社交关系网络图G中，V为图中的用户集合，E为图中朋友关系的集合。

2.信息级联：社交网络中的信息通过朋友关系进行传播，从而形成信息级联。信息级联集合C＝{C₁,C₂,…,c_k}，其中级联信息中的元素表示级联k到达节点i的时间与级联k首次出现时间的差值。

3.社会传感器：由于社交网络中的信息传播是实时的，监控所有节点耗时耗力，通常会选择社交网络中的一些节点作为信息采集节点，称之为社会传感器。

4.传感器集S对于级联c_k感知时间：其中，S是节点集V的子集，是通过传感器选择算法从节点集中选出的社会传感器集合。

5.级联的长度：级联c_k的长度|c_k|等于级联c_k在其生命周期中传达到的节点数量。

本发明提出了一种基于社会传感器优化的网络级联传播早期发现方法，其中定义了寻找最优社会传感器的目标函数，提出了贪心算法对其进行求解。

本发明所基于的现实假设为：社交网络中，信息级联传达到节点越多，信息级联越重要。我们希望通过在图G＝(V,E)中放置社会传感器，使得传感器能够尽早地发现图中的级联信息集合C＝{c₁,c₂,…,c_k}。

社会传感器的网络级联传播早期发现的目的，就是通过选择传感器集，使得在历史数据中传感器集对于信息级联集合的平均感知时间最小，从而使得选出来的传感器集合在真实的数据中能够在级联传播早期发现信息级联。传感器集对于信息级联集合的平均感知时间的定义如下：

在实际使用中，由于监控社会传感器的成本高，所以只能设置有限数量的传感器；同时，级联的重要性通常不是相同的，所以我们提出了抓大放小社会传感器选择算法。该算法通过定义混合量纲模型，目前方案中，利用级联的长度代表级联的重要性，通过增加重要级联权重的方式使得传感器集对于重要级联的平均感知时间降低，损失函数如下：

在公式(2)中，M为社会传感器的数量，K为C中的级联的数量；c_k∈C_A,C_A为传感器集检测到的级联信息集合，K₁为C_A中级联信息的数量；c′_k∈C′,C′为传感器集未检测到的级联信息集合，K₂为C′中级联信息的数量。|c′_k|表示级联c′_k所传达到节点的数量。C_A∪C′＝C，

α为平衡参数，其中T_max是监测级联的最大时间，即传感器集对级联c_k的感知时间T(S,c_k)超过T_max则认为感知失败，L_aim是可调节的超参，调节L_aim使得|c_k|＞L_aim的级联尽可能早的被发现。

损失函数简介

在损失函数公式(2),对于级联c_k，如果其被监测到，则传感器集对于级联c_k的损失为T(S,c_k)；如果其没有被监测到，传感器集对于级联c_k的损失是α|c′_k|。当|c_k|＞L_aim时，级联c_k未监测到的损失大于监测到的损失，即α|c′_k|＞T(S,c_k),最小化损失的过程中就会尽可能发现这类级联。当传感器数量有限时，这一设置会使得传感器集更早得发现重要级联(详见表格)。而|c_k|＜L_aim,级联c_k未监测到损失小于监测到的损失，即α|c′_k|＜T(S,c_k),所以可以减弱不重要级联的影响。

混合量纲简介

在损失函数公式(2)中损失函数前半部分的度量是时间，后半部分的度量是节点数，二者的取值范围不同，即属于两种量纲，有较大的差距。为了协调两种量纲，本发明所使用的方式是引入平衡参数，使得两者量纲处于同一级别。

CELF方法简介

CELF是一种基于贪心算法的传感器发现算法，目标函数如公式(1)所示，利用社交网络中收益的边际效应优先选中收益最高(目标损失最小)的节点。

本算法详细流程

本方法在CELF的方法上进行改进，对于不同的级联设置不同的权重(权重即为级联长度)，在寻找收益最大的过程中，将利用公式(3)计算每个节点带来的增益，利用贪心算法的思想，每次选出带来增益最大的节点，加入传感器集合S，反复迭代，选出一定数目的传感器。最后选出的传感器集合，在真实的社交网络中能够在信息级联发生的早期检测到信息级联。

在公式(3)中，c_k∈C_v,C_v为节点v可以先于传感器集S检测到的级联信息集合，K₁为C_v中级联信息的数量；c′_k∈C′,C′为节点v和传感器集S均未检测到的级联信息集合，K₂为C′中级联信息的数量。易知，通过最大化公式(3)计算出增益而选出来的传感器集合等价于最小化公式(2)中的损失函数选出的传感器集合。

实际算法流程如下：

利用基于混合量纲的抓大放小算法从历史级联数据中找到社会传感器集合后，对这些传感器集合进行监控，便可以在级联发生的早期检测到级联。

与CELF不同的地方在于，当传感器未监测到级联时，或者对当前的状况没有增益时，添加一个惩罚，这一惩罚使得检测到重要级联的节点优先被选中；与此同时，CELF部分可以使得侦测到的级联尽可能早的被监测到。

算法效果比较

实验数据：实验数据集为SNAP官网上的提供的CollegeMsg信息交互数据集，这一数据集描述了每条消息的走向以及信息发布的时间，利用这些信息我们可以构造信息交流网络。同时根据信息的流向，本发明可以构建信息级联数据，具体信息如表1。

表1为CollegeMsg数据集信息

节点数1899消息连边数59835信息交流网络中的边数20296数据集时间跨度193天信息级联数3881

为了全面地验证比较本发明的实验效果，将本发明与两种传感器选择算法：最大入度法(只利用拓扑结构信息)、CELF算法进行效果比较。

通过表2的结果可以看出，本发明在网络级联传播早期发现，在重要方面效果比CELF、最大入度法好：给定目标级联长度的情况下，本发明能够更早的检测到级联信息，同时能够以更少的传感器达到更好的效果。

表2为各种算法对于长度大于100的级联的检测结果

从表3中可以看出，虽然最大入度法使用10个传感器检测到了所有级联，但是其平均检测速度晚了本发明所提方法一万秒左右，近2个小时。

总体来说，本发明所提出的方法能够使用更少的传感器更早的发现重要的级联信息。

表3为各种算法对于长度大于50的级联的检测结果

参数可调节性：

调节参数L_aim，可以使的模型选择的传感器根据用户的需求进行改变。

显然，所描述的实施例仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。