基于从众心理的超图影响力传播方法及影响力最大化方法

摘要

基于从众心理的超图影响力传播方法及影响力最大化方法，本发明属于用户行为挖掘技术领域，解决图的节点之间只存在二元关系，不能很好的模拟真实世界的特性且会丢失重要信息以及超图上的影响力最大化的问题，本发明使用表达能力更强的超图来建模社会关系网络，在此基础上，提出一种在超图上的影响力传播模型并对现实生活中人们普遍存在的从众心理现象进行建模，使得该传播模型更加符合实际，基于提出的超图上传播模型，解决了图的节点之间只存在二元关系，不能很好的去模拟真实世界的特性，并且会丢失一些重要信息的缺点；采用超度的算法来解决影响力最大化问题，为超图上的影响力最大化问题提供了一种可行的解决方案。

说明书

技术领域

本发明属于用户行为挖掘技术领域，涉及基于从众心理的超图影响力传播方法及影响力最大化方法。

背景技术

基于口碑效应的影响力传播过程在病毒营销、个性化推荐中发挥了巨大作用。深入研究影响力的产生和传播模式有利于理解人类群体和个体的行为。因此在过去，出现了大量的相关研究，其中被广泛研究的一个核心问题是影响力最大化问题。该问题是指在给定的某种传播模型下，在图中寻找K个节点作为影响力传播的源节点，在传播过程结束后，使得图中最终被影响的节点数目达到最大。例如，现有技术中申请号为201711473788.8、公开日期为2018年6月19日的中国发明专利申请《一种基于用户行为传播模型求解影响力最大化问题的方法》公开了一种基于用户行为传播模型求解影响力最大化问题的方法，所述方法通过社交网络的用户行为计算用户个体影响力，并基于个体影响力计算影响传播概率，通过影响传播概率计算特定社交圈中被影响用户的最大化范围。

图和超图：在计算机科学中，图是由顶点和连接顶点的边构成的离散结构。边通常表示2个顶点之间的关系(如社交网络用户之间的关注关系)。现实生活中有很多问题都可以使用图进行建模求解，在过去的研究当中，在如Facebook、Twitter等大规模在线社交网络以及生物或经济系统的建模和分析中，图都发挥了重要作用。采用图来对这些复杂网络进行建模的一个假设是：节点之间只存在二元关系。然而，在许多情况下，这种假设并不能很好的去模拟真实世界中存在的复杂关系，并且会丢失一些重要信息。比如一篇文章有4个作者，在图中只能通过两两连边来表述他们任意二者之间的合作关系，但这种方式就丢失了他们4个人的合作关系这一信息。为了解决这个问题，我们引入超图。不同于图，超图对复杂网络的建模能力更强。超图中的超边可以表示多个节点之间的共同关系，如文章A的作者是Alex，Bob，Canavi，Dan，我们就可以很自然的用一条超边表示他们之间合作关系。因此，超图具有显著的优势，并且超图是图的更一般化形式，当超图中的超边只包含2个节点时，超图等同于图。

影响力的传播模型：在影响力传播模型中，研究最为广泛的是线性阈值模型和独立级联模型：

线性阈值模型：线性阈值模型为网络中每个节点v分配了一个阈值θ，该阈值表示这个节点受到影响的难易程度。与节点v相邻的节点u以非负的权重w(u,v)对节点v产生影响，并且v的所有邻居u的权重之和小于等于1。对于一个处于未活跃状态的节点v，只有当它的活跃邻居节点的影响力之和大于等于其阈值θ，节点v才会被激活。

线性阈值模型传播算法如下：

1.选取种子节点集合S。

2.在t时刻，对网络中的任一不在S中的节点v，其所有处于活跃态的邻居节点都来尝试激活v，如果所有活跃邻居的影响力之和超过了v的激活阈值θ，则节点v在t+1时刻转换为活跃状态并将v加入到S中。

3.重复第2步，直到网络中已存在的任意活跃节点的影响力之和都不能激活处于非活跃状态的邻居节点时，传播过程结束。

独立级联模型：独立级联模型是一种概率模型，图中每条边会被分配一个概率p，表示当一个节点v处于活跃状态时，它会以概率p(v,u)对它未激活的邻居节点u尝试激活，这种尝试仅仅进行一次，而且这些尝试之间是互相独立的。

独立级联模型的传播算法如下：

1.选取种子节点集合S。

2.在t时刻，所有t-1时刻被激活的节点u(t＝0时刻u∈S)对它的邻接节点v尝试激活，激活成功的概率为p(u,v)。若v有多个邻居节点都是在t-1时刻被激活的节点，那么这些节点将以任意顺序尝试激活节点v。

3.如果节点v被激活成功，那么在t+1时刻，节点v转为活跃状态，将对其非活跃邻居节点产生影响；否则，节点v在t+1时刻状态不发生变化。

4.该过程不断进行重复，直到某一时刻不再有新的节点被激活时，传播过程结束。

影响力最大化问题：对影响力传播过程建模的一个重要目的是用来控制和优化影响力的传播。其中被广泛研究的的一个问题是影响力最大化问题。该问题最早由Kempe,Kleinberg和Tardos定义：给定一个社会关系网络图，一个影响力传播模型，在一定的预算成本下，影响力最大化问题旨在在图中寻找k个节点作为影响力传播的源节点，使得最终被影响的节点数目达到最大。Kempe等人基于影响力传播的次模性质进一步给出了求解该问题的一个贪心算法，该算法得到的解是最优解的(1-1/e-∈)近似(约等于63％)。其中∈是控制算法近似比精确度的参数，e是自然底数。

从众心理：人们发现许多实际网络都具有一个共同性质，即社区结构。像工作场所，学校这样的社区结构在影响力的传播过程中发挥着重大作用。如在社会心理学描述那样，在群体中的人们为了维持自己的群体感会产生从众心理。这种从众心理在影响力传播过程中起的作用是不可忽视的。对于社区群体中一员，他所受的影响不光包括其他个体对他的影响，还包括群体对他的影响。值得注意的是，实际中每个人的从众表现都不尽相同，有些人容易产生从众心理，而有些人很难产生从众心理。

发明内容

本发明的目的在于如何使用超图解决图中节点之间只存在二元关系，不能准确模拟真实世界存在的复杂关系的问题以及如何解决超图上的影响力最大化的问题。

本发明是通过以下技术方案解决上述技术问题的：

基于从众心理的超图影响力传播方法，包括以下步骤：

S11、对从众心理的超图影响力传播方法模型参数的初始化，包括：初始化节点的阈值，设置从众心理影响函数，初始化节点之间的影响权重；

S12：选取K个种子节点并激活，并将这些节点加入到集合S中，其中集合S保存超图中所有激活的节点，对于传播步数i＝0,1,2,3…,定义S

S13、遍历超图中没有被激活的节点，然后该节点所有的处于激活态的邻居节点都尝试来激活它；

S14、是否有新的节点被激活，如果是，将新激活的节点加入到集合S，再重复步骤S13的过程，如果不是，则传播过程结束，输出集合S。

本发明的技术方案使用表达能力更强的超图来建模社会关系网络，在此基础上，提出一种在超图上的影响力传播模型并对现实生活中人们普遍存在的从众心理现象进行建模，使得该传播模型更加符合实际，基于提出的超图上传播模型，解决了图的节点之间只存在二元关系，不能很好的去模拟真实世界中复杂关系，并且会丢失一些重要信息的缺点。

作为本发明技术方案的进一步改进，步骤S11中所述的初始化节点的阈值，具体为：通过[0,1]均匀分布对超图中所有节点随机分配一个阈值θ，θ表示其受影响的难易程度。

作为本发明技术方案的进一步改进，步骤S11中所述的设置从众心理影响函数，具体为：设置一个从众心理影响函数F，F＝2p-p

作为本发明技术方案的进一步改进，步骤S11中所述的初始化节点之间的影响权重，具体为：对于节点u,v，如果u,v在同一超边内，则从区间[0,1]中随机选择2个数作为它们之间的影响权重，记作：w(u,v)，w(v,u)，分别表示u对v和v对u的影响权重。且需要满足条件：对节点v∈V,v的邻居节点即所有与它在同一条超边内的节点对它的权重之和满足∑

作为本发明技术方案的进一步改进，步骤S13中所述的遍历超图中没有被激活的节点，然后该节点所有的处于激活态的邻居节点都来尝试激活它，具体为：在i≥1步，检查未激活节点v，其中v∈V/S

作为本发明技术方案的进一步改进，步骤S14中所述的是否有新的节点被激活的判断条件为：判断在S13中S

一种应用于所述的基于从众心理的超图影响力传播方法的影响力最大化方法，包括以下步骤：

S21、计算超图中各节点的超度；

S22、根据步骤S21的计算结果，对所有节点按照超度的大小从大到小进行排序，选取前K个节点作为种子节点，记为集合为S；

S23、影响力的传播，使用步骤S22中得到的种子节点集合S作为从众心理的超图影响力传播方法模型的输入，进行超图上的影响力传播，最终得到超图上所有被激活的节点。

作为本发明技术方案的进一步改进，步骤S21中所述的计算超图中各节点的超度，具体为：节点的超度等于节点所在超边的个数，即d(v)＝∑

本发明的优点在于：本发明的技术方案使用表达能力更强的超图来建模社会关系网络，在此基础上，提出一种在超图上的影响力传播模型并对现实生活中人们普遍存在的从众心理现象进行建模，使得该传播模型更加符合实际，解决了图中节点之间只存在二元关系，不能模拟真实世界复杂关系的问题，基于提出的超图上影响力传播模型，提出了使用最大超度的方法解决了超图上的影响力最大化问题

附图说明

图1为本发明实施例中超图上传播模型的流程图；

图2为本发明实施例中基于最大超度的方法解决影响力最大化问题的流程图。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

下面结合说明书附图以及具体的实施例对本发明的技术方案作进一步描述：

实施例

如图1所示，本发明提出一种基于从众心理的超图影响力传播方法(以下简称HLT模型)，该模型使用超图来建模现实生活中的复杂群组交互关系，并考虑了个体的从众心理在影响力传播过程的影响。

采用函数F:[0,1]→[0,1]描述个体的从众心理的大小，定义p

为了更好的描述从众心理，函数F应满足如下性质：

1：F(0)＝0，F(1)＝1；

2：F是单调递增的，且函数初始增长很快，随后增长逐渐平缓。

本发明基于以下技术方案来实现，基于从众心理的超图影响力传播方法包含以下步骤：

S11：传播模型参数的初始化：进一步有：

S111：初始化节点的阈值：通过[0,1]均匀分布对超图中所有节点随机分配一个阈值θ，表示其受影响的难易程度。

S112：初始化节点的影响权重：对于节点u,v，如果u,v在同一超边内，则从区间[0,1]中随机选择2个数作为它们之间的影响权重，记作：w(u,v)，w(v,u)，分别表示u对v和v对u的影响权重。且需要满足条件：对节点v∈V,v的邻居节点即所有与它在同一条超边内的节点对它的权重之和满足∑

S113：初始化从众心理函数：设置一个合适的从众心理函数F,，F＝2p-p

S12：选取K个种子节点并激活它们，并将这些节点加入到集合S中。其中集合S保存超图中所有激活的节点。对于传播步数i＝0,1,2,3…,我们定义S

S13：在i≥1步，检查未激活节点v，其中v∈V/S

S14：判断在S13中S

如图2所示，为了解决在HLT传播模型下，超图上的影响力最大化问题，还提出了一种基于超度的启发式算法，该算法包含以下步骤：

S21：计算超图中各节点的超度：计算超图中各节点的超度，节点的超度等于节点所在超边的个数即d(v)＝∑

S22：种子节点选取：根据步骤S21的计算结果对所有节点按照超度的大小，从大到小进行排序，选取前K个节点作为种子节点集合S。

S23：影响力传播：使用S22中得到的节点集合S作为种子节点集合作为HLT模型的输入，进行超图上的影响力传播，最终得到超图上所有被激活的节点。

以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。