一种仅基于节点状态观测结果的影响最大化方法与装置与流程

1.本发明属于信息检索技术领域，尤其涉及一种仅基于节点状态观测结果的影响最大化方法与装置。


背景技术：

2.随着信息科技的快速迭代和发展，人们之间的沟通方式变得更加多样，交互频率变得更加频繁，使得无形间形成了一个以人为节点的信息传播网络，传播着言论、资讯、甚至疾病等内容。影响最大化旨在从传播网络中找到一些最具影响力的节点(称之为种子节点)可以最大化信息的影响传播范围。这在现实生活中具有重要的应用价值，例如广告商可以找到人群中最具号召力的群体进行促销，从而使得有限的营销预算获取最大的推广效果；疾病防控人员可以找到最具感染能力的病人进行管控，最大程度降低传染病的扩散范围。
3.现有的影响最大化方法大多假设潜在的传播网络结构是已知的，然后依据某一个特定的传播模型进行影响最大化的研究。但是在大多数实际应用中，由于网络的指数级增长，以及用户对隐私相关问题的日益担忧，收集传播网络中包含的完整潜在影响关系通常是比较困难的，导致当前大多数依赖网络结构这种先验知识进行影响最大化研究的方法存在局限性。虽然存在一些不依赖传播网络结构的最大化研究是利用节点在传播过程中的感染时间信息进行分析，但是定期监控节点的感染状态来获取感染时间的成本可能是难以承担的，并且节点从被感染到出现症状可能存在潜伏期，导致收集的时间数据不能准确反映节点的感染情况，影响算法的准确性。
4.综上，如何仅依据节点状态观测结果这一容易获取的数据进行影响最大化，挖掘出传播网络中最具影响力的节点，是本领域亟需解决的问题。


技术实现要素：

5.为了解决上述技术问题，本发明提供了一种仅基于节点状态观测结果的影响最大化方法与装置，基于传播网络中各节点在传播过程结束后的最终感染状态数据来构建能够表现节点影响能力的矩阵，把节点被选作种子节点的概率作为待求解的参数，通过构建衡量种子节点集合产生的影响范围的优化函数来进行参数求解，然后基于求解的结果进行采样来发现最具影响力的种子节点集合。
6.本发明所采用的技术方案是：
7.定义传播网络结构为g＝{v,e}，其中v＝{v1,v2,..,vn}表示传播网络中的n个节点，每一个节点代表一个用户；e表示传播网络中代表影响关系的有向边集合；β次传播过程结束后收集到的感染状态观测数据使用s＝{s1,s2,
…
,s
β
}表示，其中表示第l次传播过程结束后的节点感染状态观测数据，示第l次传播过程结束后的节点感染状态观测数据，表示第l次过程结束后节点vi的感染状态，取值为1表示被感染，取值0表示未被
感染，此处所述的“感染”是指该节点对应的用户状态信息符合期望，例如，用户已经获取了某信息(言论/资讯/广告)，或者已经患某种传染性疾病，则标记该节点已感染，否则标记该节点未感染。
8.基于上述定义，所述的仅基于节点状态观测结果的影响最大化方法包括以下步骤：
9.步骤1：使用收集的感染数据来构建表示节点影响能力的矩阵q∈rn×n，其中q
ij
(i,j∈{1,2,
…
,n})表示节点vi和节点vj影响能力的异质性，具体的计算为：
[0010][0011][0012]
其中，n表示传播网络中包含的节点个数；β表示传播网络中的信息/疾病传播过程的次数；q
ij
表示节点vi和节点vj影响能力的异质性；min(c
ik
,c
jk
)表示c
ik
和c
jk
中较小的值；max(c
ik
,c
jk
)表示c
ik
和c
jk
中较大的值；i(
·
)是一个指示函数，当(
·
)中的条件成立时取值为1，不成立时取值为0；表示第l次过程结束后节点vi的感染状态，c
ik
表示节点vi和节点vk感染状态之间的关联程度；si表示0或者1的一个取值，因此(si,sk)组合共有四种，即(0,0),(0,1),(1,0),(1,1)。
[0013]
步骤2：使用表示节点影响能力的矩阵q来构造可以衡量种子节点集合产生的影响范围的优化函数并构造下列二次规划问题：
[0014][0015]
s.t.xi∈[0,1],i＝1,
…
,n
[0016][0017]
其中，xi(i∈{1,
…
,n})表示节点vi被选作种子节点的概率变量；λ是人为设定的惩罚因子，λ》0；k人为设定的需要选择的种子节点个数。
[0018]
步骤3：求解步骤2中的二次规划问题，得到每个节点作为种子节点的确切概率取值集合p
x
＝{x
′1,
…
,x
′n}，其中，x
′i表示节点vi作为种子节点的确切概率取值。
[0019]
步骤4：对每个节点作为种子节点的确切概率取值集合p
x
进行m次采样，得到m组候选种子节点集合cs＝{cs1,
…
,csm}，其中，csi＝{is
i1
,
…
,is
in
}表示第i次采样得到的种子节点集合，is
ij
∈{0,1}(j＝1,
…
,n)，is
ij
＝1表示在第i次采样中节点vj被选作种子节点，is
ij
＝0表示在第i次采样中节点vj没有被选作种子节点。
[0020]
步骤5：使用优化函数f(x1,
…
,xn)来衡量候选种子节点集合cs中每次采样的种子节点集合csi的影响范围f(is
i1
,
…
,is
in
)，将影响范围f(is
i1
,
…
,is
in
)最大的种子节点集合csi作为最终选择的种子节点集合返回。
[0021]
作为优选的，步骤4中，第i次采样得到种子节点集合csi的取值可以通过下述方法得到：
[0022]
步骤4.1，初始化一个表示节点是否被选作种子的集合csi＝{is
i1
,
…
,is
in
}，并将所有元素均取值为0，即is
ij
＝0,j＝1,
…
,n。
[0023]
步骤4.2，根据节点被选作种子的确切概率取值集合p
x
来依次遍历每个节点vj(j∈{1,2,
…
,n})，在遍历到vj的同时生成一个[0,1]之间的随机数rj，若rj≤x
′j，则将节点vj选作种子节点，即is
ij
的取值设置为1，否则继续遍历下一个节点v
j+1
。当遍历过程中选择到了k个种子节点时，将当前csi作为采样结果返回。当所有节点都遍历结束仍未选择到k个种子节点，返回步骤4.1。
[0024]
本发明解决了当传播网络结构未知时进行最具影响力的种子节点集合的选择问题，基于传播过程中容易收集的节点最终感染状态数据，来构建能够表现节点影响能力的矩阵，借助二次规划问题的求解工具得到节点作为种子节点的概率，再通过采样的思想获取最具影响力的种子节点集合，避免了使用网络结构或者节点确切感染时间这种难以获得的知识，具有更大的实用价值。
附图说明
[0025]
图1：本发明实施例的流程图。
[0026]
图2：本发明实施例在人工网络lfrnet和真实网络poster上选择不同数量种子节点对应的影响范围结果图。
具体实施方式
[0027]
为了便于本领域普通技术人员理解和实施本发明，下面结合附图及实施例对本发明作进一步的详细描述，应当理解，此处所描述的实施实例仅用于说明和解释本发明，并不用于限定本发明。
[0028]
在本实施例中，使用了lfr算法生成的人工网络lfrnet和一个真实的表示科学家研究工作的合作关系网络poster作为传播网络，两个网络包含的节点个数和边数如表1所示，其中，合作关系网络poster中，将一次学术会议或者期刊的论文收录情况作为一次传播过程，作者被感染(取值为1)表示该作者有论文收录，未感染(取值为0)表示没有论文被收录。可以根据多次收录情况找到最有影响力的作者，代表当前的热门研究方向，了解研究趋势。
[0029]
本实施例中，每个网络上的节点感染状态数据是根据独立级联传播模型随机选择15％的初始节点进行多次模拟传播过程结束收集到的。
[0030]
表1实验网络
[0031]
网络节点个数边数lfrnet200800poster3791602
[0032]
图1中描述了本发明实施例的流程图，本发明提供了一种仅基于节点状态观测结果的影响最大化方法，定义传播网络结构为g＝{v,e},其中v＝{v1,v2,..,vn}表示传播网络中的n个节点；e表示传播网络中代表影响关系的有向边集合；β次传播过程结束后收集到的
感染状态观测数据使用s＝{s1,s2,
…
,s
β
}表示，其中表示第l次传播过程结束后的节点感染状态观测数据，表示第l次过程结束后节点vi的感染状态，取值为1表示被感染，取值0表示未被感染。
[0033]
基于上述定义，所述方法包括以下步骤：
[0034]
步骤1：使用收集的感染数据来构建表示节点影响能力的矩阵q∈rn×n，其中q
ij
(i,j∈{1,2,
…
,n})表示节点vi和节点vj影响能力的异质性，具体的计算为：
[0035][0036][0037]
其中n表示传播网络中包含的节点个数；β表示传播过程的次数；q
ij
表示节点vi和节点vj影响能力的异质性；min(c
ik
,c
jk
)表示c
ik
和c
jk
中较小的值；max(c
ik
,c
jk
)表示c
ik
和c
jk
中较大的值；i(
·
)是一个指示函数，当(
·
)中的条件成立时取值为1，不成立时取值为0；表示第l次过程结束后节点vi的感染状态。
[0038]
步骤2：使用矩阵q来构造可以衡量种子节点集合产生的影响范围的优化函数并构造下列的二次规划问题：
[0039][0040]
s.t.xi∈[0,1],i＝1,
…
,n
[0041][0042]
其中xi(i∈{1,
…
,n})表示节点vi被选作种子节点的概率变量；需要选择的种子节点个数k的取值分别设置为2、4、6、8、10、12、14、16、18、20。
[0043]
步骤3：使用cvxpy工具包来求解步骤2中的二次规划问题得到每个节点作为种子节点的确切概率取值集合p
x
＝{x
′1,
…
,x
′n}，其中x
′i表示节点vi作为种子的概率。
[0044]
步骤4：根据每个节点作为种子节点的确切概率取值集合p
x
进行100次采样，得到100组候选种子节点集合cs＝{cs1,
…
,cs
100
}，其中csi＝{is
i1
,
…
,is
in
}表示第i次采样得到的种子节点集合，is
ij
∈{0,1}(j＝1,
…
,n)，is
ij
＝1表示在第i次采样中节点vj被选作种子节点，is
ij
＝0表示在第i次采样中节点vj没有被选作种子节点。
[0045]
步骤5：使用函数f(x1,
…
,xn)来衡量cs中每次采样的种子节点集合csi的影响范围f(is
i1
,
…
,is
in
)，将影响范围f(is
i1
,
…
,is
in
)最大的种子节点集合csi作为最终选择的种子节点集合返回。
[0046]
请见图2，是本发明实施例在lfr算法生成的人工网络lfrnet和真实网络poster上分别选择2、4、6、8、10、12、14、16、18、20个种子节点所对应的影响范围结果图。在进行种子节点集合选择时，若挑选的种子节点分布不当，可能导致更多数量的种子，无法产生期望的
影响范围，比如挑选的种子节点过于分散时，会因为单个节点的影响能力有限而无法持续更久的传播时间，导致影响范围有限；而挑选的种子节点数量多但是节点的影响范围存在较多重叠时，产生的影响范围无法覆盖到网络的更多区域，限制了网络中的信息传播范围。从实验结果可以看出随着种子数量增加，本发明挑选的种子集合产生的影响范围也是逐步增加的，说明本发明挑选的种子分布是合理有效的。根据每个网络上生成的200条传播轨迹数据，使用本发明提供的方法来找寻所需数量的种子节点集合，并通过计算所选种子节点的影响范围来衡量本发明找寻的种子节点集合的影响力，其中影响范围的计算是将找寻的种子节点集合在实验网络上进行100次模拟传播，并记录每次传播过程结束后网络中的所有被感染节点的数量，将100次传播过程中被感染节点的数量的平均值作为影响范围。
[0047]
除了上述实施例模拟的人工网络lfrnet和合作关系网络poster之外，本发明还可以应用在广告推广和疾病防控领域。在广告推广中，将广告推广平台注册的用户及用户间的关系网络作为传播网络，将每一次广告投放作为一轮传播，记录每一轮传播下用户是否获取了该广告信息，若已获取，则认为该用户代表的传播网络节点已感染，若未获取，则认为该用户代表的传播网络节点未感染；使用收集的感染数据执行上述步骤1-4，返回的种子节点集合即为从传播网络中找到的最具号召力的群体，广告商可以针对该群体进行促销，从而使得有限的营销预算获取最大的推广效果。
[0048]
在疾病防控中，将某一区域居民及居民之间的关系网络作为传播网络，记录传染性病毒在每一轮爆发时被感染的居民，使用收集的感染数据执行上述步骤1-4，返回的种子节点集合即为从传播网络中找到的最具感染能力的居民，可通过对该群体进行重点关注以最大程度降低传染病的扩散范围。
[0049]
本发明提出的一种仅基于节点状态观测结果的影响最大化方法，仅仅基于传播过程结束后的节点最终感染状态数据来构建表征节点影响能力的矩阵，将节点被选作种子的概率作为参数来构造二次规划问题并进行求解，最后通过采样的方法获取最终的种子节点集合，通过本发明，只需要收集节点的感染状态数据就可以找到网络中最具影响力的节点集合。
[0050]
基于相同的发明构思，本发明还提出了一种仅基于节点状态观测结果的影响最大化装置，该装置用于实现上述实施例。以下所使用的术语“模块”、“单元”等可以实现预定功能的软件和/或硬件的组合。尽管在以下实施例中所描述的装置较佳地以软件来实现，但是硬件，或者软件和硬件的组合的实现也是可能的。
[0051]
本实施例中，一种仅基于节点状态观测结果的影响最大化装置，包括：
[0052]
一种数据获取模块，其用于获取用于表征用户及其关系的传播网络，收集若干次传播过程结束后各节点对应的用户状态信息得到感染数据，若用户状态信息符合期望，则标记该节点已感染，否则标记该节点未感染；
[0053]
节点影响力矩阵构建模块，其用于使用收集的感染数据来构建表示节点影响能力的矩阵q；
[0054]
二次规划问题构建模块，其用于使用矩阵q来构造用于衡量种子节点集合产生的影响范围的优化函数f(x1,
…
,xn)，并构造下述二次规划问题：
[0055]
[0056]
s.t.xi∈[0,1],i＝1,
…
,n
[0057][0058]
其中，xi表示节点vi被选作种子节点的概率变量，n表示传播网络中的节点数；λ是预设的惩罚因子；k预设的需要选择的种子节点个数；
[0059]
二次规划问题求解模块，其用于求解所述的二次规划问题，得到每个节点作为种子节点的确切概率取值集合p
x
＝{x
′1,
…
,x
′n}，其中，x
′i表示节点vi作为种子的概率；
[0060]
候选种子集合采样模块，其用于根据每个节点作为种子节点的确切概率取值集合p
x
进行m次采样，得到m组候选种子节点集合cs；
[0061]
候选种子集合筛选模块，其用于使用优化函数f(x1,
…
,xn)来衡量m组候选种子节点集合cs中每次采样的种子节点集合csi的影响范围，将影响范围最大的种子节点集合csi作为最终选择的种子节点集合返回，所述种子节点集合中的节点对应的用户即筛选出来的实现影响最大化的目标用户。
[0062]
对于装置实施例而言，由于其基本对应于方法实施例，所以相关之处参见方法实施例的部分说明即可，其余模块的实现方法此处不再赘述。以上所描述的装置实施例仅仅是示意性的，其中所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部模块来实现本发明方案的目的。本领域普通技术人员在不付出创造性劳动的情况下，即可以理解并实施。本发明的装置的实施例可以应用在任意具备数据处理能力的设备上，该任意具备数据处理能力的设备可以为诸如计算机等设备或装置。装置实施例可以通过软件实现，也可以通过硬件或者软硬件结合的方式实现。以软件实现为例，作为一个逻辑意义上的装置，是通过其所在任意具备数据处理能力的设备的处理器将非易失性存储器中对应的计算机程序指令读取到内存中运行形成的。
[0063]
应当理解的是，本说明书未详细阐述的部分均属于现有技术，上述针对较佳实施例的描述较为详细，并不能因此而认为是对本发明专利保护范围的限制，本领域的普通技术人员在本发明的启示下，在不脱离本发明权利要求所保护的范围情况下，还可以做出替换或变形，均落入本发明的保护范围之内，本发明的请求保护范围应以所附权利要求为准。

技术特征：
1.一种仅基于节点状态观测结果的影响最大化方法，其特征在于，包括以下步骤：步骤1：获取用于表征用户及其关系的传播网络，收集若干次传播过程结束后各节点对应的用户状态信息得到感染数据，若用户状态信息符合期望，则标记该节点已感染，否则标记该节点未感染；步骤2：使用收集的感染数据来构建表示节点影响能力的矩阵q；步骤3：使用矩阵q来构造用于衡量种子节点集合产生的影响范围的优化函数f(x1,
…
,x
n
)，并构造下述二次规划问题：s.t.x
i
∈[0,1],i＝1,
…
,n其中，x
i
表示节点v
i
被选作种子节点的概率变量，n表示传播网络中的节点数；λ是预设的惩罚因子；k预设的需要选择的种子节点个数；步骤4：求解步骤3中的二次规划问题，得到每个节点作为种子节点的确切概率取值集合p
x
＝{x
′1,
…
,x
′
n
}，其中，x
′
i
表示节点v
i
作为种子的概率；步骤5：根据每个节点作为种子节点的确切概率取值集合p
x
进行m次采样，得到m组候选种子节点集合cs；步骤6：使用用于衡量种子节点集合产生的影响范围的优化函数f(x1,
…
,x
n
)来衡量m组候选种子节点集合cs中每次采样的种子节点集合cs
i
的影响范围，将影响范围最大的种子节点集合cs
i
作为最终选择的种子节点集合返回，所述种子节点集合中的节点对应的用户即筛选出来的实现影响最大化的目标用户。2.根据权利要求1所述的一种仅基于节点状态观测结果的影响最大化方法，其特征在于，所述步骤5中，第i次采样得到种子节点集合cs
i
的取值的过程如下：步骤5.1，初始化一个表示节点是否被选作种子的集合cs
i
＝{is
i1
,
…
,is
in
}，并将所有元素均取值为0，即is
ij
＝0,j＝1,
…
,n；步骤5.2，根据节点被选作种子的确切概率取值集合p
x
来依次遍历每个节点v
j
，j∈{1,2,
…
,n}，在遍历到v
j
的同时生成一个[0,1]之间的随机数r
j
，若r
j
≤x
j
′
，则将节点v
j
选作种子节点，即is
ij
的取值设置为1，否则继续遍历下一个节点v
j+1
；当遍历过程中选择到了k个种子节点时，将当前cs
i
作为采样结果返回；当所有节点都遍历结束仍未选择到k个种子节点，返回步骤5.1。3.根据权利要求1所述的一种仅基于节点状态观测结果的影响最大化方法，其特征在于，所述的表示节点影响能力的矩阵的构建公式如下：于，所述的表示节点影响能力的矩阵的构建公式如下：
其中，β表示传播过程的次数；q
ij
表示节点v
i
和节点v
j
影响能力的异质性；min(c
ik
,c
jk
)表示c
ik
和c
jk
中较小的值；max(c
ik
,c
jk
)表示c
ik
和c
jk
中较大的值；i(
·
)是一个指示函数，当(
·
)中的条件成立时取值为1，不成立时取值为0；表示第l次过程结束后节点v
i
的感染状态，c
ik
表示节点v
i
和节点v
k
感染状态之间的关联程度，s
i
、s
k
分别表示0或者1的一个取值。4.根据权利要求1所述的一种仅基于节点状态观测结果的影响最大化方法，其特征在于，所述的用于衡量种子节点集合产生的影响范围的优化函数为：其中，q
ij
表示表示节点v
i
和节点v
j
影响能力的异质性。5.一种仅基于节点状态观测结果的影响最大化装置，其特征在于，包括：数据获取模块，其用于获取用于表征用户及其关系的传播网络，收集若干次传播过程结束后各节点对应的用户状态信息得到感染数据，若用户状态信息符合期望，则标记该节点已感染，否则标记该节点未感染；节点影响力矩阵构建模块，其用于使用收集的感染数据来构建表示节点影响能力的矩阵q；二次规划问题构建模块，其用于使用矩阵q来构造用于衡量种子节点集合产生的影响范围的优化函数f(x1,
…
,x
n
)，并构造下述二次规划问题：s.t.x
i
∈[0,1],i＝1,
…
,n其中，x
i
表示节点v
i
被选作种子节点的概率变量，n表示传播网络中的节点数；λ是预设的惩罚因子；k预设的需要选择的种子节点个数；二次规划问题求解模块，其用于求解所述的二次规划问题，得到每个节点作为种子节点的确切概率取值集合p
x
＝{x
′1，...，x
′
n
}，其中，x
′
i
表示节点v
i
作为种子的概率；候选种子集合采样模块，其用于根据每个节点作为种子节点的确切概率取值集合p
x
进行m次采样，得到m组候选种子节点集合cs；候选种子集合筛选模块，其用于使用优化函数f(x1，...，x
n
)来衡量m组候选种子节点集合cs中每次采样的种子节点集合cs
i
的影响范围，将影响范围最大的种子节点集合cs
i
作为最终选择的种子节点集合返回，所述种子节点集合中的节点对应的用户即筛选出来的实现影响最大化的目标用户。6.根据权利要求5所述的一种仅基于节点状态观测结果的影响最大化装置，其特征在于，所述的候选种子集合采样模块中，采样过程如下：初始化一个表示节点是否被选作种子的集合cs
i
＝{is
i1
，...，is
in
}，并将所有元素均取值为0，即is
ij
＝0，j＝1，...，n；根据节点被选作种子的确切概率取值集合p
x
来依次遍历每个节点v
j
，j∈{1，2，...，n}，在遍历到v
j
的同时生成一个[0，1]之间的随机数r
j
，若r
j
≤x
′
j
，则将节点v
j
选作种子节点，即
is
ij
的取值设置为1，否则继续遍历下一个节点v
j+1
；当遍历过程中选择到了k个种子节点时，将当前cs
i
作为采样结果返回；当所有节点都遍历结束仍未选择到k个种子节点，则重新采样。7.根据权利要求5所述的一种仅基于节点状态观测结果的影响最大化装置，其特征在于，所述的节点影响力矩阵构建模块中，矩阵q具体为：于，所述的节点影响力矩阵构建模块中，矩阵q具体为：其中，β表示传播过程的次数；q
ij
表示节点v
i
和节点v
j
影响能力的异质性；min(c
ik
，c
jk
)表示c
ik
和c
jk
中较小的值；max(c
ik
，c
jk
)表示c
ik
和c
jk
中较大的值；i(
·
)是一个指示函数，当(
·
)中的条件成立时取值为1，不成立时取值为0；表示第l次过程结束后节点v
i
的感染状态，c
ik
表示节点v
i
和节点v
k
感染状态之间的关联程度，s
i
、s
k
分别表示0或者1的一个取值。8.根据权利要求5所述的一种仅基于节点状态观测结果的影响最大化装置，其特征在于，所述的二次规划问题构建模块中，用于衡量种子节点集合产生的影响范围的优化函数具体为：其中，q
ij
表示表示节点v
i
和节点v
j
影响能力的异质性。

技术总结
本发明公开了一种仅基于节点状态观测结果的影响最大化方法与装置，属于信息检索技术领域。首先计算能够表征节点影响能力的矩阵，接着用节点被选作种子节点的概率作为参数构造二次规划问题进行求解；然后使用求解得到的每个节点作为种子节点的确切概率取值集合进行采样得到候选种子节点集合；最后计算衡量每个候选种子节点集合的影响能力，返回最具影响力的种子节点集合。本发明基于容易收集和相对准确的节点感染状态数据来计算节点作为种子节点的概率，辅助于采样的方法来找到最具影响力的节点集合，避免了网络结构和准确的感染时间等相对难以收集的信息，在现实生活中具有更加广泛的应用场景。加广泛的应用场景。加广泛的应用场景。


技术研发人员：颜钱 黄浩 刘玉生 王章野 张琼
受保护的技术使用者：江西求是高等研究院
技术研发日：2023.05.16
技术公布日：2023/8/24