法律状态公告日
法律状态信息
法律状态
2018-10-23
授权
授权
2016-06-08
实质审查的生效 IPC(主分类):G06F17/30 申请日:20151226
实质审查的生效
2016-05-11
公开
公开
技术领域
本发明涉及网络安全领域,特别涉及一种在线社会网络多源点信息溯源系统及其 方法。
背景技术
随着各种新兴媒体的广泛应用,信息流动模式和服务模式也发生了重大变化,网 民均可借助第三方应用平台生产信息、部署软件、提供服务,这使得信息源急剧增大,信息 发布方式多样,互联网上任何一个人都有可能是信息的发送者和接收者,社会事件在网络 中随着不同的意识形态、社会思潮逐步演化并不断发酵、扩散,形成一个又一个热点问题。 尤其是针对网络中的不良信息传播者,如何有效实现信息溯源,对于实现网络舆情监管,及 时了解网络舆情的发展动向具有重要意义,并将为从源头上实现网络舆情治理提供有力指 导。
现有的信息溯源研究已经取得了部分进展。但是,仍存在以下局限和不足:一、目 前的溯源方法多以网络快照为研究背景,而且大多数研究方法需要获取全部感染节点的状 态,在线社会网网络中实时获知全部节点的状态难以实现;二、在静态快照为前提的背景下 不具备节点获取信息的时间信息,无法利用时间维度信息来提高追溯源点的准确性,而在 线社会网络中观察节点通常可以确定节点获取信息的时刻;三、针对多点溯源问题,现有方 法通常都有限制条件,在确定源点数量的条件下确定源点的位置,目前还没有对未知源点 数量条件下的溯源方法。在线社会网络中并不容易实时的获取所有节点的状态,因此,目前 的大多数静态方法并不适用于在线社会网络中确定信息传播源点。
发明内容
针对现有技术中的不足,本发明提供一种在线社会网络多源点信息溯源系统及其 方法,在解决不确定信息源点数量情况下,在网络中布置部分观察节点来代替获取全部节 点状态的方式,获取消息是由哪些邻居节点接收的以及接收到消息的时刻来完成信息溯 源,充分利用时间维度来提高确定信息源点的准确性。
按照本发明所提供的设计方案,一种在线社会网络多源点信息溯源系统,包含原 始数据采集模块、备选集选取模块、基于近邻传播的聚类模块、协同反馈模块,
原始数据采集模块,构建在线社会网络结构并在网络中布置观察节点,对观察节 点接收到的节点信息进行量化表示;
备选集选取模块,根据接收时间、节点信息与网络结构的映射关系,缩小信息源点 范围,采用重启式随机游走算法确定备选源点集和时延备选集;
基于近邻传播的聚类模块,利用单次接收的观察节点和备选源点集在空间和时间 上的相近性确定信息源点的位置和数量,通过设计基于近邻传播的聚类算法,对观察节点 与备选源点集中节点进行聚类,一个聚类中心的代表点为一个可能的信息源点;
协同反馈模块,对基于近邻传播的聚类结果进行检测,并判断检测结果是否达到 预定标准,若达到预定标准,则结束执行,否则,根据检测结果生成备选集调节命令,分别发 送给备选集选定模块和基于近邻传播的聚类模块,备选集选定模块和基于近邻传播的聚类 模块根据备选集调节命令调节备选源点集和每跳时延备选集范围。
上述的,基于近邻传播的聚类算法:计算观察节点和备选源点集的相似度,构造相 似度矩阵,这里的相似度不是基于欧几里得空间,而是基于空间跳数与传播时间的比例关 系;对近邻传播的对象有所限制,因为观察节点不可能成为信息源点,而且同一紧密时间块 的备选节点集中只可能确定一个信息源点。
上述的,协同反馈模块对基于近邻传播的聚类结果进行检测,并判断检测结果是 否达到预定标准,具体是指:协同反馈模块执行基于近邻传播的聚类算法,完成迭代循环, 判断迭代过程中迭代次数是否达到规定数值或迭代过程中改变的信息量是否小于设定阈 值,迭代过程中改变的信息量小于设定阈值即指近邻传播迭代过程中所有观察节点的归属 不再变化,。
一种在线社会网络多源点信息溯源方法,包含如下步骤:
步骤1.构建在线社会网络结构,并在网络结构中布置多个观察节点,对观察节点 接收到的信息进行量化;
步骤2.根据观察节点中多次接收信息的节点,将信息的传播方向信息与传播时间 信息映射到网络结构中,确定备选源点集和时延备选集;
步骤3.确定观察节点中单次接收信息的观察节点;
步骤4.计算单次接收信息的观察节点和备选源点集的相似度,构造相似度矩阵, 确定信息源点数量及位置,并确定信息源点的传播与影响范围,执行基于近邻传播的聚类 算法;
步骤5.对基于近邻传播的聚类结果进行迭代,当迭代次数达到规定数值或迭代过 程中改变的信息量小于设定阈值时,迭代过程中改变的信息量小于设定阈值即指近邻传播 迭代过程中所有观察节点的归属不再变化,则进入步骤7,否则,生成备选源点集调节指令, 进入下一步骤;
步骤6.根据备选源点集调节指令,调节备选源点集的范围,将观察节点的邻居节 点作为备选源点集,返回步骤4;
步骤7.确定全部信息源点的数量与位置,结束执行过程。
优选的,所述步骤2具体包含如下步骤:
步骤2.1假设步骤1中布置k个观察节点,并定义观察节点集合为每个观察节点的节点信息用表示,其中,oi表示k个观察节点中第i个观察 节点;vi,j表示观察节点i从邻居节点j接收到了信息,ti,j记录了接收信息的时刻,m为接收 到信息的次数,将多次接收信息的观察节点的方向信息与时间信息映射到网络结构中,定 义时刻集合Tcpt={ti,ti+1,...,ti+k}中,如果k≥2且ti+k-ti≤2u,其中,u为每一跳时延的方 差,那么时刻集合Tcpt定义为紧密时间块,对应的邻居节点为紧密时间块节点集Vcpt={vi, vi+1,...,vi+k},定义节点prn,pth是紧密时间块节点集Vcpt={vi,vi+1,...,vi+k}的共同前趋,n 代表观察节点拥有相同前趋的邻居节点个数;pth表示共同前趋到紧密时间块节点的路径 的跳数;
步骤2.2根据网络结构特征,根据观察节点为信息源点的概率,针对任意紧密时间 块节点集Vcpt={vi,vi+1,...,vi+k},假设prn,pth的路径路数都相同,Pr={prn,pth}则为共同前 趋集合,共同前趋集合的类型用|Pr|来表示,p(prn,pth)表示共同前趋prn,pth成为信息源点 的概率的大小,如果|Pr1|≤|Pr2|,那么max(p(O=Pr1))≥max(p(O=Pr2)),初步确定信息 源点的范围和位置;
步骤2.3根据网络结构与观察节点接收信息关系,通过紧密时间块得到信息源点 的方向、数量和与距离,根据首达时间点与紧密时间块的关系获取观察节点与信息源点之 间的最短距离,缩小备选源点集范围,确定每跳时延的均值和方差,缩小备选源点集范围, 确定每跳时延的均值和方差;采用重启式随机游走算法确定备选源点集和时延备选集,以 观察节点的邻居节点为出发源点,根据驻留时间和共同节点情况,确定信息源点和每跳时 延。
上述的,步骤2.3中根据首达时间点与紧密时间块的关系获取观察节点与信息源 点之间的最短距离具体指:多次接收信息的观察节点中,在接收时间轴上,根据首达时间与 紧密时间块的关系,分为三种情况:情况1:多次接收到信息的观察节点时间轴上,t1为观察 节点接收到信息的首达时间,Tcpt是该观察节点的首个紧密时间块,并且满足观察 对应的网络结构,Pr是Tcpt的共同前趋集,PTHo,pr是观察节点到共同前趋的路径集合,如果 并且满足公式(1)则利用该前趋节点进一步确定每 一跳时延备选集,在紧密时间块前到达观察节点的信息存在由共同前趋通过最短路径传播 的可能,或由另外一个跳数较少的信息源点传播,通过判断共同前趋到观察节点是否存在 比通过紧密时间块的邻居到达观察节点路径更短的路径,即通过是否满足公式(1)来判断, 将满足公式(1)的共同前趋pr纳入时延确定备选集VTpre中,在备选源点集中确定每一跳的 时延,若共同前趋到源点的最短路径与通过紧密时间块的节点到达源点的路径比和首达时 间与紧密时间块平均值相近,则选取最相近的共同前趋来确定每一跳时延,该共同前趋选 取需要满足式(2)
上述的,所述步骤4具体包含如下内容:计算单次观察节点和备选源点集的相似性 度量,构造相似度矩阵,观察节点的节点信息观察节点与备选源点集的相 似度公式表示为:每一跳的时延服从正态分布,由备选 源点集确定均值为μ,均方差为σ,相似度的范围为[0,-∞)。
上述的,步骤5中对基于近邻传播的聚类结果进行迭代具体是指:根据迭代公式
上述的,步骤6具体指:在达到一定的迭代次数时,对于部分节点满足min(s(i,k)) >ε的情况,说明这些节点不在已经归类的信息源点范围内,ε代表观察节点与信息源点的一 个相似度阈值,具体值根据信息溯源的过程确定;需要通过将单次观察节点的邻居信息节 点作为备选源点集,返回步骤4执行,直至找到所有观察节点的信息源点。
本发明的有益效果:
本发明在在线社会网络中不确定源点数量情况下完成信息溯源,以记录部分观察 节点状态方式代替获取全部感染节点状态,解决现有技术中在线社会网络中实时获知全部 节点状态也难以实现的情况;相较于以往采用网络快照的方式,本发明充分利用时间维度 来提高确定信息源点的准确性,提供了一种在未知源点数量条件下的信息溯源,有效实现 信息溯源,及时对网络舆情进行监管,便于及时了解网络舆情的发展动向,从信息源头上为 实现网络舆情治理提供有力指导。
附图说明:
图1为本发明的在线社会网络多源点信息溯源系统示意图;
图2为本发明的在线社会网络多源点信息溯源方法流程示意图;
图3为本发明的信息溯源场景示意图;
图4为本发明的观察节点接收时间分布与网络结构映射示意图;
图5为本发明的采用重启式随机游走算法流程示意图。
具体实施方式:
下面结合附图和技术方案对本发明作进一步详细的说明,并通过优选的实施例详 细说明本发明的实施方式,但本发明的实施方式并不限于此。
实施例一,参见图1所示,一种在线社会网络多源点信息溯源系统,包含原始数据 采集模块、备选集选取模块、基于近邻传播的聚类模块、协同反馈模块,
原始数据采集模块,构建在线社会网络结构并在网络中布置观察节点,对观察节 点接收到的节点信息进行量化表示;
备选集选取模块,根据接收时间、节点信息与网络结构的映射关系,缩小信息源点 范围,采用重启式随机游走算法确定备选源点集和时延备选集;
基于近邻传播的聚类模块,利用单次接收的观察节点和备选源点集在空间和时间 上的相近性确定信息源点的位置和数量,通过设计基于近邻传播的聚类算法,对观察节点 与备选源点集中节点进行聚类,一个聚类中心的代表点为一个可能的信息源点;
协同反馈模块,对近邻传播学习模型进行检测,并判断检测结果是否达到预定标 准,若达到预定标准,则结束执行,否则,根据检测结果生成备选集调节命令,分别发送给备 选集选定模块和基于近邻传播的聚类模块,备选集选定模块和基于近邻传播的聚类模块根 据备选集调节命令调节备选源点集和每跳时延备选集范围。
实施例二,与实施例一基本相同,不同之处在于:基于近邻传播的聚类算法,首先 计算观察节点和备选源点集的相似度,构造相似度矩阵,这里的相似度不是基于欧几里得 空间,而是基于空间跳数与传播时间的比例关系;其次对近邻传播的对象有所限制,因为观 察节点不可能成为信息源点,而且同一紧密时间块的备选节点集中只可能确定一个信息源 点。
协同反馈模块对基于近邻传播的聚类结果进行检测,并判断检测结果是否达到预 定标准,具体是指:协同反馈模块执行近邻传播聚类算法,完成迭代循环,判断迭代过程中 迭代次数是否达到规定数值或迭代过程中改变的信息量是否小于设定阈值,迭代过程中改 变的信息量小于设定阈值即指近邻传播迭代过程中所有观察节点的归属不再变化。
实施例三,参见图2~4所示,一种在线社会网络多源点信息溯源方法,包含如下步 骤:
步骤1.构建在线社会网络结构,并在网络结构中布置多个观察节点,对观察节点 接收到的信息进行量化;
步骤2.根据观察节点中多次接收信息的节点,将信息的传播方向信息与传播时间 信息映射到网络结构中,确定备选源点集和时延备选集;
步骤3.确定观察节点中单次接收信息的观察节点;
步骤4.计算单次接收信息的观察节点和备选源点集的相似度,相似度为基于空间 跳数与传播时间的比例关系,构造相似度矩阵,确定信息源点数量及位置,并确定信息源点 的传播与影响范围,执行基于近邻传播的聚类算法;
步骤5.对基于近邻传播的聚类结果进行迭代,当迭代次数达到规定数值或迭代过 程中改变的信息量小于设定阈值时,迭代过程中改变的信息量小于设定阈值即指近邻传播 迭代过程中所有观察节点的归属不再变化,则进入步骤7,否则,生成备选源点集调节指令, 进入下一步骤;
步骤6.根据备选源点集调节指令,调节备选源点集的范围,将观察节点的邻居节 点作为备选源点集,返回步骤4;
步骤7.确定全部信息源点的数量与位置,结束执行过程。
实施例四,参见图2~5所示,一种在线社会网络多源点信息溯源方法,包含如下步 骤:
步骤1.构建在线社会网络结构,并在网络结构中布置多个观察节点,对观察节点 接收到的信息进行量化,假设布置k个观察节点,并定义观察节点集合为每 个观察节点的节点信息用表示,其中,oi表示k个观察节点中第i个观察节 点;vi,j表示观察节点i从邻居节点j接收到了信息,ti,j记录了接收信息的时刻,m为接收到 信息的次数;
步骤2.根据观察节点中多次接收信息的节点,将信息的传播方向信息与传播时间 信息映射到网络结构中,确定备选源点集和时延备选集,具体包含如下步骤:
步骤2.1将多次接收信息的观察节点的方向信息与时间信息映射到网络结构中, 定义时刻集合Tcpt={ti,ti+1,...,ti+k}中,如果k≥2且ti+k-ti≤2u,其中,u为每一跳时延的 方差,那么时刻集合Tcpt定义为紧密时间块,对应的邻居节点为紧密时间块节点集Vcpt= {vi,vi+1,...,vi+k},定义节点prn,pth是紧密时间块节点集Vcpt={vi,vi+1,...,vi+k}的共同前 趋,n代表观察节点拥有相同前趋的邻居节点个数;pth表示共同前趋到紧密时间块节点的 路径的跳数;
步骤2.2根据网络结构特征,根据观察节点为信息源点的概率,针对任意紧密时间 块节点集Vcpt={vi,vi+1,...,vi+k},假设prn,pth的路径路数都相同,Pr={prn,pth}则为共同前 趋集合,共同前趋集合的类型用|Pr|来表示,p(prn,pth)表示共同前趋prn,pth成为信息源点 的概率的大小,如果|Pr1|≤|Pr2|,那么max(p(O=Pr1))≥max(p(O=Pr2)),初步确定信息 源点的范围和位置;
步骤2.3根据网络结构与观察节点接收信息关系,通过紧密时间块得到信息源点 的方向、数量和与距离,根据首达时间点与紧密时间块的关系获取观察节点与信息源点之 间的最短距离,缩小备选源点集范围,确定每跳时延的均值和方差,缩小备选源点集范围, 确定每跳时延的均值和方差;采用重启式随机游走算法确定备选源点集和时延备选集,以 观察节点的邻居节点为出发源点,根据驻留时间和共同节点情况,确定信息源点和每跳时 延,根据首达时间点与紧密时间块的关系获取观察节点与信息源点之间的最短距离具体 指:多次接收信息的观察节点中,在接收时间轴上,根据首达时间与紧密时间块的关系,分 为三种情况:情况1:多次接收到信息的观察节点时间轴上,t1为观察节点接收到信息的首 达时间,Tcpt是该观察节点的首个紧密时间块,并且满足观察对应的网络结构,Pr是 Tcpt的共同前趋集,PTHo,pr是观察节点到共同前趋的路径集合,如果并且满足公 式(1)则利用该前趋节点进一步确定每一跳时延备选集,在紧 密时间块前到达观察节点的信息存在由共同前趋通过最短路径传播的可能,或由另外一个 跳数较少的信息源点传播,通过判断共同前趋到观察节点是否存在比通过紧密时间块的邻 居到达观察节点路径更短的路径,即通过是否满足公式(1)来判断,将满足公式(1)的共同 前趋pr纳入时延确定备选集VTpre中,在备选源点集中确定每一跳的时延,若共同前趋到源 点的最短路径与通过紧密时间块的节点到达源点的路径比和首达时间与紧密时间块平均 值相近,则选取最相近的共同前趋来确定每一跳时延,该共同前趋选取需要满足式(2)
步骤3.确定观察节点中单次接收信息的观察节点;
步骤4.计算单次接收信息的观察节点和备选源点集的相似度,相似度为基于空间 跳数与传播时间的比例关系,构造相似度矩阵,确定信息源点数量及位置,并确定信息源点 的传播与影响范围,执行基于近邻传播的聚类算法,具体包含如下内容:计算单次观察节点 和备选源点集的相似性度量,构造相似度矩阵,观察节点的节点信息观察 节点与备选源点集的相似度公式表示为:每一跳的时延 服从正态分布,由备选源点集确定均值为μ,均方差为σ,相似度的范围为[0,-∞),相似度最 大为0,表示在此溯源过程中,信息源点满足时延与跳数的关系,备选源点在后续的迭代过 程中一定为该观察节点的信息源点;-∞表示该信息源点与观察节点之间不存在路径,该备 选源点一定不是该观察节点的信息源点;另外,观察节点不可能成为信息源点,将观察节点 之间的相近度设置为负无穷大;同一紧密时间块的共同前趋不可能都成为源点,因此同一 前趋的备选节点之间的相似度设置负无穷大;
步骤5.对基于近邻传播的聚类结果进行迭代,当迭代次数达到规定数值或迭代过程中改变 的信息量小于设定阈值时,迭代过程中改变的信息量小于设定阈值即指近邻传播迭代过程中所 有观察节点的归属不再变化,则进入步骤7,否则,生成备选源点集调节指令,进入下一步骤,具体 迭代过程为:根据迭代公式
步骤6.根据备选源点集调节指令,调节备选源点集的范围,将观察节点的邻居节 点作为备选源点集,因为在达到一定的迭代次数时,对于部分节点满足min(s(i,k))>ε的情 况,可能为信息源点的离群点,ε代表观察节点与信息源点的一个相似度阈值,具体值根据 信息溯源的过程确定;需要通过将单次观察节点的邻居信息节点作为备选源点集,返回步 骤4执行,直至找到所有观察节点的信息源点;
步骤7.确定全部信息源点的数量与位置,结束执行过程。
本发明并不局限于上述具体实施方式,本领域技术人员还可据此做出多种变化, 但任何与本发明等同或者类似的变化都应涵盖在本发明权利要求的范围内。
机译: 四件套信息软件溯源系统
机译: 在电源点中使用插件式TTS模块合成语音的电源点文档,制作各种视频文件的方法和系统
机译: 互联网上利用边缘路由器的日志信息进行攻击溯源的方法