一种独立级联模型下基于极大似然的源定位方法

摘要

本说明书一个或多个实施例提供一种独立级联模型下基于极大似然的源定位方法，通过根据种子节点集在IC模型上扩散，形成感染网络，利用独立路径计算传播概率，再计算影响范围最小的似然函数利用贪心策略选取种子集合，最终得到输出感染源，相比于传统的源定位方法大部分都只能解决单影响源定位问题，并且利用简单的IC模型来解决复杂的多源定位问题的工作甚少。本方法在只考虑概率因素的情况下，就能同时解决单源和多源的源定位问题，为以后似然概率运用于多源问题的研究提供了相应基础。该技术可以提高识别社交网络中影响力传播的源节点方面的效率，扩展了该技术在源定位问题领域的应用范围和实用性。

说明书

技术领域

本发明属于应用于复杂网络中运用独立级联模型和似然函数计算来进行源定位的方法，特别涉及一种基于独立路径技术以及影响力覆盖的极大似然估计算法来进行传播源定位的方法。

背景技术

互联网技术的不断发展正将世界变成地球村，人们的社交网络不断扩大这些都为信息的传播提供了更加快捷、广泛的传播途径，但这同时也为一些不良信息传播提供了方便，如一些谣言、病毒等，通过这些移动客户端被广泛传播，一些不明事理的人很容易受这些谣言影响，轻易相信这些传闻，有些激进者可能会做出过激行为，造成自己和他人合法权利受到损害，这些给社会稳定带来了不利影响。因此，如何准确、快速地进行传播源定位是网络科学研究中的一项重要的任务。越来越多的学者把目光投向了对社交网络中的信息传播的研究。

网络拓扑结构是社交网络的基础，在研究过程中，社交网络通常是以图的形式抽象地展示网络的拓扑结构和信息的传播过程。目前对于社交网络中的信息流传播的研究，一些学者重点关注了信息源的定位问题，即通过研究如何构建有效的信息源定位的模型以期探测到的真正的信息源的可能性最大。因此，研究社交网络中感染源(信息源)的定位问题有着十分重要的实际意义。从大的方面讲，国家可以通过社交网络对舆情及时分析，从而控制不良信息的传播；从小的方面来说，谣言、恶意病的传播这些不利因素的传播和扩散对人们的生产和生活有着巨大的影响也可以最大化地减少。负面信息传播的问题都是依托于具体的网络而存在的，并且网络的规模一般都十分巨大，节点相互之间的联系同样也非常复杂。在这样的情况下，如果能够快速地和准确地找到信息的来源，控制和缩小其传播范围，可以大大地减少对人们生活的影响。这个问题不仅仅是复杂网络科学领域需要研究的重要课题，更是政府保证网络安全，控制谣言传播面临的重大挑战。在此背景下，对社交网络中的感染源的定位问题进行深入地研究，并开发出相应的分析软件供舆情监控部门和企业市场监控来使用是十分有意义的。

现有的源定位算法，处理单源问题的居多，而多源问题相对比较复杂，因此处理多源问题方法还比较少，并且现在源定位研究的方法大多都是基于SI、SIR模型等等的传染病模型，依赖于时间因素作为考量，而对于IC这种概率模型研究的较少。识别社交网络中影响力传播的源节点方面的效率不足。

发明内容

有鉴于此，本说明书一个或多个实施例的目的在于提出一种独立级联模型下基于极大似然的源定位方法，以解决上述提出的其中一个或多个技术问题。

基于上述目的，本说明书一个或多个实施例提供了一种独立级联模型下基于极大似然的源定位方法(MLE-FIC)，包括：

在复杂网络中确定初始传播的种子节点集；

根据种子节点集在独立级联模型上扩散，直到网络中不再产生感染节点为止，将感染的节点抽取形成感染网络；

生成节点之间的独立路径，利用独立路径计算每一个节点对之间的传播概率；

利用概率模拟选取的种子节点的影响范围，使得选取种子节点的影响范围与初始的影响范围最大限度的重合，设计得到极大似然目标函数；

利用贪心算法选取影响力覆盖最大的节点，得到影响源的种子集合，输出感染源。

优选地，利用独立路径计算每一个节点对之间的传播概率包括：

独立路径选择从网络中的任意节点出发进行深度遍历，得到路径上的传播概率。最终生成一个传播概率矩阵，记录感染网络中任意两个节点之间的传播概率。

优选地，利用极大似然目标函数求解，选取出使其影响范围与初始的影响范围最大限度重合的种子集合包括：

找到s和a

其中s为种子集合，函数p

利用Woodbury矩阵恒等式处理得到极大似然目标函数。

优选地，利用Woodbury矩阵恒等式处理得到极大似然目标函数包括：

利用影响力的拟合来确定极大似然目标函数；

根据矩阵范数以及Woodbury矩阵恒等式来进一步简化极大似然目标函数。

优选地，利用贪心算法选取影响力覆盖最大的节点，得到影响源的种子集合，输出感染源包括：

取种子集合为空集，在全部的点中逐个选取使目标函数极小化的点加入到种子集合之中；

计算每次加入节点v

直到网络中没有新的节点被感染，整个传播过程结束；

定义为m个观测者集合，抽出独立路径生成的传播概率矩阵P的前m列,p

找出感染这m个观测者的种子节点，得到影响源的种子集合。

从上面所述可以看出，本说明书一个或多个实施例提供的独立级联模型下基于极大似然的源定位方法，通过根据种子节点集在IC模型上扩散，形成感染网络，利用独立路径计算传播概率，再计算影响范围最小的似然函数利用贪心策略选取种子集合，最终得到输出感染源，相比于传统的源定位方法大部分都只能解决单影响源定位问题，并且利用简单的IC模型来解决复杂的多源定位问题的工作甚少。本方法在只考虑概率因素的情况下，就能同时解决单源和多源的源定位问题，为以后似然概率运用于多源问题的研究提供了相应基础。该技术可以提高识别社交网络中影响力传播的源节点方面的效率，扩展了该技术在源定位问题领域的应用范围和实用性。

附图说明

为了更清楚地说明本说明书一个或多个实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本说明书一个或多个实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本说明书一个或多个实施例的源定位方法流程示意图；

图2为本说明书一个或多个实施例的不同参数设置在ER网络中(k＝5)的精确度图；

图3为本说明书一个或多个实施例的不同算法在ER网络(N＝200,D＝47)中(k＝1,3,5,7,9,10)的精确度图；

图4为本说明书一个或多个实施例的不同算法在BA网络(N＝200,D＝50)中(k＝1,3,5,7,9,10)的精确度图；

图5为本说明书一个或多个实施例的不同算法在WS网络(N＝200,D＝50)中(k＝1,3,5,7,9,10)的精确度图；

图6为本说明书一个或多个实施例的不同算法在dolphin网络(N＝63,D＝5)中(k＝1,3,5,7,9,10)的精确度图；

图7为本说明书一个或多个实施例的不同算法在football网络(N＝115,D＝11)中(k＝1,3,5,7,9,10)的精确度图；

图8为本说明书一个或多个实施例的不同算法在facebook网络(N＝4039,D＝44)中(k＝1,3,5,7,9,10)的精确度图；

图9为本说明书一个或多个实施例的不同算法在USAIR网络(N＝332,D＝13)中(k＝1,3,5,7,9,10)的精确度图；

图10为本说明书一个或多个实施例的不同算法在不同规模ER网络(D＝30,N＝100,200,300,400,500)中(k＝1,3,5)的精确度图；

图11为本说明书一个或多个实施例的不同算法在不同规模BA网络(D＝30,N＝100,200,300,400,500)中(k＝1,3,5)的精确度图；

图12为本说明书一个或多个实施例的不同算法在不同规模WS网络(D＝30,N＝100,200,300,400,500)中(k＝1,3,5)的精确度图；

图13为本说明书一个或多个实施例的不同算法在不同度的ER网络(N＝200,D＝10,20,30,40,50)中(k＝1,3,5)的精确度图

图14为本说明书一个或多个实施例的不同算法在不同度的BA网络(N＝200,D＝10,20,30,40,50)中(k＝1,3,5)的精确度图；

图15为本说明书一个或多个实施例的不同算法在不同度的WS网络(N＝200,D＝10,20,30,40,50)中(k＝1,3,5)的精确度图.

具体实施方式

为使本公开的目的、技术方案和优点更加清楚明白，以下结合具体实施例，对本公开进一步详细说明。

需要说明的是，除非另外定义，本说明书一个或多个实施例使用的技术术语或者科学术语应当为本公开所属领域内具有一般技能的人士所理解的通常意义。本说明书一个或多个实施例中使用的“第一”、“第二”以及类似的词语并不表示任何顺序、数量或者重要性，而只是用来区分不同的组成部分。“包括”或者“包含”等类似的词语意指出现该词前面的元件或者物件涵盖出现在该词后面列举的元件或者物件及其等同，而不排除其他元件或者物件。“连接”或者“相连”等类似的词语并非限定于物理的或者机械的连接，而是可以包括电性的连接，不管是直接的还是间接的。“上”、“下”、“左”、“右”等仅用于表示相对位置关系，当被描述对象的绝对位置改变后，则该相对位置关系也可能相应地改变。

常见的源定位问题包括单源和多源定位问题，在单源问题上，Shah和Zaman等人最早将谣言源的确定表述为一个极大似然估计的问题。Zhou等人使用SEIR模型模拟感染过程，并证明Jordan中心性和源定位问题的关系,将问题转化为求感染节点的Jordancenter。Chen和Fu等人提出广义的谣言中心性，利用信息传递的算法将谣言源缩小在一些个小范围的点中。Roxana等人利用对网络节点的部分观测以及扩散的数学模型，在假设传播开始时间为已知的情况下设计了一种有效的单源检测算法。Yang等人利用命名博弈的方法来寻找网络中的信息源，将多次迭代到最后概率最高的点作为信息源。溯源在病毒的传播，污染物的传播等源头的追溯上是个多源的问题。在多源问题的解决上，Hu等人在基于后向扩散的方法和整数规划的基础上，提出了一种在有限观测器的复杂网络中定位源的有效方法。Zhang等人在中提出了贝叶斯回溯模型,提出了激活原因的后验概率，将随机游走后击中频率高的节点作为感染源。Hu等人在中提出了一种最大值方法来定位有限观测者的源。Li等人在SIR模型下提出了潜在浓度标签的方法，将标签值的迭代用于多源的溯源中。Li等人又利用网络拓扑结构和扩散到达部分节点的时间作为根据，将覆盖所有观察到的知情节点的最小节点集作为感染源。

为了克服现有算法的缺点，本说明书实施例提供一种独立级联模型下基于极大似然的源定位方法，包括以下步骤：

S101在复杂网络中确定初始传播的种子节点集，如输入复杂网络和种子节点集。

S102根据种子节点集在独立级联模型上扩散，直到网络中不再产生感染节点为止，将感染的节点抽取形成感染网络；

举例来说，首先从数据集中随机选取节点作为源，再利用IC模型(独立级联模型)扩散感染至网络没有可感染的节点，这样就可以得到已知源的感染网络，我们假定未知初始感染源，方便我们最后对算法准确性进行验证。

S103生成节点之间的独立路径，利用独立路径计算每一个节点对之间的传播概率。

对于感染的网络，可以通过独立路径来计算网络图中每一个节点对之间的传播概率，独立路径选择从网络中的任意节点出发进行深度遍历，得到路径上的传播概率，最终生成一个传播概率矩阵，记录感染网络中任意两个节点之间的传播概率。

S104利用概率模拟选取的种子节点的影响范围，使得选取种子节点的影响范围与初始的影响范围最大限度的重合，设计得到极大似然目标函数；

举例来说，设计得到极大似然目标函数包括：

找到s和a

其中s为种子集合，函数p

利用Woodbury矩阵恒等式处理得到极大似然目标函数。

为了有效定位影响源，我们需要利用概率来模拟选取的种子节点的影响范围，使得选取的种子节点的影响范围与初始的影响范围最大限度的重合。即极小化覆盖范围I(S)与O的误差。对于被影响顶点o

进一步的，利用Woodbury矩阵恒等式处理得到极大似然目标函数包括：

利用影响力的拟合来确定极大似然目标函数；

根据矩阵范数以及Woodbury矩阵恒等式来进一步简化极大似然目标函数。

S105利用贪心算法选取影响力覆盖最大的节点，得到影响源的种子集合，输出感染源。

举例来说，在完成步骤S104中极大似然函数推导和化简之后，使用贪心算法来选择种子集合，一开始取种子集合为空集，然后再在全部的点中逐个选取使目标函数极小化的点加入到之中。然而当选取完一个种子节点时，剩余节点的影响范围会相应的发生变化，这会影响到接下来种子节点的选取。因此接下来我们计算每次加入节点v

具体描述如下：

1)初始时刻，假设源是已知的；

2)源节点集合作为初始的传播种子集合，在网络图中进行扩散，扩散步骤如下：

(1)当节点u在某一时刻t被激活后，它将会获得了一次对它的邻居节点v产生影响的机会，激活成功的概率为p[u,v]，且激活成功的概率p[u,v]的值是随机赋予的，概率的值越大，节点v就越有可能被u激活。激活的概率值本身是独立的，大小不受其他节点的影响。

(2)若v有多个邻居节点都是最新一次被激活的节点，那么这些激活的节点将以任意顺序依次尝试去激活节点v。如果这些激活的邻居节点中某一节点u成功激活节点v，那么在t+1时刻，节点v从未激活状态转为活跃状态。

(3)在t+1时刻，节点v将对其他节点产生影响，再次重复(1)和(2)的过程。

3)当网络中没有新的节点被感染，整个传播过程结束。

源定位的过程：我们定义为m个观测者集合，抽出独立路径生成的传播概率矩阵P的前m列,p

本说明书实施例提供的独立级联模型下基于极大似然的源定位方法，提出了一种新的源定位思路。传统的源定位方法，大部分都只能解决单影响源定位问题，并且利用简单的IC模型来解决复杂的多源定位问题的工作甚少。本发明研究，在只考虑概率因素的情况下，就能同时解决单源和多源的源定位问题，为以后似然概率运用于多源问题的研究提供了相应基础。该技术可以提高识别社交网络中影响力传播的源节点方面的效率，扩展了该技术在源定位问题领域的应用范围和实用性。有助于解决电脑病毒、流行病传播源的定位，污染源的定位及舆情谣言的定位等。

步骤描述：

在图G＝(V,E,P)中，我们设O＝{o

我们假设影响力的源s＝{v

可以得到优化后的目标函数表达式

对于种子节点的选取，我们假设源个数已知，则我们需要利用贪心的方法来选取种子节点。一开始设种子集合S为空集，然后逐个选取V\S中使目标函数极小化的顶点加入到S之中。设S中已有i个种子，构成了矩阵S

对于种子节点的更新，介于对H

如图2所示为本方法的参数设置图。我们针对不同的参数设置，在ER随机网络上进行实验，设置源个数为5，观测者占比为1，横坐标为IC模型传播参数，纵坐标为惩罚参数。从图中可以看出，IC模型参数在0到0.6区间内准确率保持较好的效果，当参数大于0.6时准确率开始下滑，并且当参数为0.6时准确率保持最佳。并且当惩罚参数设置为0.1时，整体实验的效果的稳定性较好，且准确率能达到极大值。因此本方法中惩罚参数设置为0.1，将IC模型传播参数调整为0.6。

图3-5是本方法与其他方法在虚拟网络上的精确度对比图。分别在ER、BA、WS三种虚拟网络上根据观测者比例的不同进行实验，横坐标为观测者的占比，其中的三种中心性方法观测者占比统一设置为1(以下实验都如此设置)。源的个数分别设置为1、3、5、7、9、10六种情况。三种虚拟网络的节点数都为200，度都在50左右。可以看出当观测者占比高于0.7时，MIE-FIC的准确率要好于其他所有的算法。MIE-FIC在WS网络中多源的处理中得到了较好的效果。总体看来MIE-FIC在虚拟网络中的效果要远好于其他方法。在BA网络中，当源个数k＝1,3,5时，MLE-FIC要明显好于其他方法，虽然在k＝5以及观测者占比小于0.5时MLE-FIC效果不及其他方法，但是当观测者占比高于0.5时，效果又有了明显提高，说明观测者占比在高于0.5时覆盖到了比较重要的节点，这样使得在影响力拟合时的估计值大大提高。当源个数k＝3，观测者占比高于0.6时，MLE-FIC显示出很好的效果。

图6-9是本方法与其他方法在真实网络上的精确度对比图。分别在dolphin、football、facebook、USAIR四个真实网络上根据观测者比例的不同进行实验，同样的横坐标为观测者的占比，其中的三种中心性方法观测者占比统一设置为1。源的个数分别设置为1、3、5、7、9、10六种情况。在真实网络dolphin中，MIE-FIC能达到中心性方法效果的两倍，在k＝10时，当观测节点占比为1时，MIE-FIC准确率达到MLGA的两倍。虽然在观测节点较少的情况下，MLE-FIC会略显劣势，但是随着观测节点的增多，准确率增长比例要远高于其他方法。在真实网络football中，MLE-FIC整体上优于其他方法，并且要优于MLGA算法20％以上，并保持良好的稳定的效果。由于中心性算法不依赖于观测值占比(观测值始终为1)，因此我们的方法在低观测者占比时效果并不占优，但是随着观测者比例上升，我们方法的准确率也稳步上升，在观测者为1时，要优于其他五个方法。在facebook这样的大型网络中，我们方法的效果要明显胜过其他五个对比算法。在USAIR网络中，当k＝7,9,10时，MIE-FIC效果很明显优于三个中心性方法，并且对于同类方法，平均效果也能高出10％左右。

图10-12是本发明与其他方法在相同度情况下，不同节点数目的虚拟网络上的精确度对比图，我们分别选取了相同类型的方法MLE-FIC和RWBA在相同的平均度，不同网络规模的情况下进行对比，我们设置三种虚拟网络(ER、BA、WS)的平均度为30，节点数设置100、200、300、400、500五种不同的类型，并且设置源的个数k＝1、3、9来进行试验。在ER网络中可以看出随着节点数的增加，MLE-FIC的效果在明显变好，并且在大部分情况下都要优于RWBA。MLE-FIC在ER网络中最高的准确率可以接近90％。在BA网络中，MLE-FIC的整体效果明显优于RWBA，并且当k＝1时，MLE-FIC的平均准确率都要在90％以上。在多个感染源的情况下，当观测者大于0.4时，MLE-FIC都能取得比较好的结果。在WS网络中，在k＝9、节点数为500的情况下，MLE-FIC的准确率要高于RWBA约30％。我们可以看出在度相同的情况下，节点个数越多，MLE-FIC的效果就越好。并且在节点规模大的数据集中都要优于RWBA。

图13-15是本发明与其他方法在相同节点数情况下，不同度的虚拟网络上的精确度对比图，同样选取了相同类型的方法MLE-FIC和RWBA在相同的网络规模，不同度的情况下进行对比，我们设置三种虚拟网络(ER、BA、WS)的节点数为200，度设置10、20、30、40、50五种不同的类型，并且设置源的个数k＝1、3、9来进行试验。在ER网络中可以看出随着平均度的升高，MLE-FIC的准确率也在升高。在平均度高于20时，MLE-FIC的整体效果都要好于RWBA。并且可以看到在源节点数增高，平均度变大的情况下，能得到接近95％的准确率。在BA网络中在源节点个数为1时，MLE-FIC取得了非常好的结果。并且在绝大多数情况都要优于RWBA的效果，准确率要高于RWBA的10％以上。在WS网络中当k＝1时，MLE-FIC展现出优于RWBA的准确率，并且在k＝3、9时，同样的情况还在继续保持。随着度的增加，MLE-FIC准确率增加幅度明显高于RWBA。我们可以看出在规模相同的情况下，节点的度越高，MLE-FIC的准确率就越高，并且在大多数情况下都高于RWBA。说明节点度越高，信息量就越大，更有利于我们源定位的精确度提高。

所属领域的普通技术人员应当理解：以上任何实施例的讨论仅为示例性的，并非旨在暗示本公开的范围(包括权利要求)被限于这些例子；在本公开的思路下，以上实施例或者不同实施例中的技术特征之间也可以进行组合，步骤可以以任意顺序实现，并存在如上所述的本说明书一个或多个实施例的不同方面的许多其它变化，为了简明它们没有在细节中提供。

另外，为简化说明和讨论，并且为了不会使本说明书一个或多个实施例难以理解，在所提供的附图中可以示出或可以不示出与集成电路(IC)芯片和其它部件的公知的电源/接地连接。此外，可以以框图的形式示出装置，以便避免使本说明书一个或多个实施例难以理解，并且这也考虑了以下事实，即关于这些框图装置的实施方式的细节是高度取决于将要实施本说明书一个或多个实施例的平台的(即，这些细节应当完全处于本领域技术人员的理解范围内)。在阐述了具体细节(例如，电路)以描述本公开的示例性实施例的情况下，对本领域技术人员来说显而易见的是，可以在没有这些具体细节的情况下或者这些具体细节有变化的情况下实施本说明书一个或多个实施例。因此，这些描述应被认为是说明性的而不是限制性的。

本说明书一个或多个实施例旨在涵盖落入所附权利要求的宽泛范围之内的所有这样的替换、修改和变型。因此，凡在本说明书一个或多个实施例的精神和原则之内，所做的任何省略、修改、等同替换、改进等，均应包含在本公开的保护范围之内。