一种基于线性阈值的互补多主体影响力最大化方法

技术领域

本发明属于社交网络中的影响力最大化领域，尤其涉及一种基于线性阈值的互补多主体影响力最大化方法。

背景技术

随着互联网的不断发展，线上社交平台已经融入了人们日常生活的方方面面。在社交网络中，例如产品、观点等传播主体的信息通过用户之间的社交互动传播，发帖、点评、私信等均是社交互动的形式。合理地选择一部分具有高影响力的“种子”用户作为传播的起点可以扩大信息的传播范围，这也是社交网络影响力传播最大化问题的目标。社交网络影响力最大化在在例如产品营销、个性化推荐等方面有着重要的应用，并且该问题已被证明是NP-Hard问题。

在主流的影响力传播模型中，社交网络被抽象建模为图，其中用节点表示用户，并用边表示用户之间的影响关系。而信息在网络中的扩散则用一个随机过程来表达，独立级联模型和线性阈值模型是使用最为广泛的两个扩散模型。在这两个模型中，当一个节点采用了传播主体后，它的影响力会从该节点向与其有边相连的相邻节点扩散。在经典的单主体影响力传播模型中，在同一社交网络中传播的不同主体被认为是独立的，其中一个主体不会影响其他主体的传播。但在现实生活中，传播主体之间存在竞争或者互补的关系的情况是很常见的，用户采用了其中一个主体后可能会改变其是否采用其他主体的选择。以产品营销为例，不同品牌的电脑构成竞争关系，而电脑主机和鼠标键盘等外设间则有互补关系。因此，经典单主体模型可能会偏离实际的用户行为。目前，已经有许多竞争关系的多主体影响力传播模型，而互补关系的模型则相对来说还很不成熟，而目前唯一的互补模型基于独立级联模型，使用较为复杂的节点层面自动机来描述节点的行为。基于上述不足，在本发明中，提出一种基于线性阈值的模型的互补关系多主体影响力传播模型和相应的影响力最大化方法。

发明内容

本发明的目的是针对现有技术不足，提出一种基于线性阈值的互补多主体影响力最大化方法，描述两个传播主体之间具有互补关系时社交网络中的影响力传播。

本发明目的在于针对现有技术的不足，提出一种基于线性阈值的互补多主体影响力最大化方法。

本发明的目的是通过以下技术方案来实现的：一种基于线性阈值的互补多主体影响力最大化方法，该方法包括以下步骤：

(1)对于社交网络中具有互补关系的两个传播主体A和B，使用全局互补参数γ

(2)对于社交网络中的节点v，随机生成一组阈值

(3)社交网络为一个有向图，使用前向BFS找出所有被传播主体B激活的节点，从社交网络所有节点中随机选择一个采样起点v

进一步地，社交网络中两个具有互补关系的传播主体的含义为在其中一个传播主体在进行影响力传播过程中激活某个社交网络中的节点时，该节点被另一个传播主体激活的概率会增加。

进一步地，全局互补参数均为[0,1]之间的实数，通过机器学习分析历史的社交网络中用户行为得到。

进一步地，步骤(2)中，在进行实例采样时，当v被B激活时，等价地将节点v的每条入边的A权值乘以参数

和现有技术相比，本发明的有益效果有：提出了一种可以表示主体间互补关系的社交网络影响力传播模型；模型利用线性阈值的模型的特性，通过降低阈值(或增加边权)的方法来描述主体之间的互补关系，无需使用节点层面自动机来表述每个节点的行为，实现较为简洁；针对模型提出了反向可达集采样方法，可以配合IMM算法较快地实现影响力最大化问题的求解。

附图说明

图1为本发明提出的互补多主体影响力传播模型的扩散过程流程图。

图2为本发明提出的模型中一个节点的活跃边采样方法的流程图(以主体A为例，主体B的方法是对称的，因此省略)。

图3为在本模型上进行自身影响力最大化的反向可达集采样的流程图。

具体实施方式

下面结合附图，对本发明作进一步的详细说明。

本发明主要包括互补多主体影响力传播模型和自身影响力最大化反向可达集采样方法这两个部分。

1.所述互补多主体影响力传播模型利用线性阈值模型的特性，通过降低阈值来表述传播主体之间的互补关系。具体而言，在该模型中，多个传播主体在同一个社交网络图G(V,E)上传播，但是对于每个传播主体，节点的阈值和边的权值可以是不同的。对于两个传播主体A和B，每个节点v分别有阈值

本模型中，影响力的传播在离散的时间步进行，首先需要从社交网络数据集中输入带权有向图G以及全局互补参数γ

为了支持影响力最大化算法，需要对上述提出的模型进行实例采样，实例是指在一组特定的节点阈值取值下的模型，消除了随机模型中的不确定性。在本模型中，每个节点在任意时刻对于传播主体A和B分别有0或者1条活跃边，实例采样只需对每个点采样活跃边即可。分别记

在采样实例的A活跃边时，对于每个节点v，从[0,1]中均匀生成一个随机数

2.所述自身影响力最大化反向可达集采样方法，其目标是求出适用于IMM算法的反向可达集，在已知互补主体B的种子集的情况下，找一个A的种子集，尽可能使得A的影响力最大。将图G的节点以1到n标号，边以1到m标号。以A为例(B的定义同理)，令

本发明方法实现的具体过程如下：

如图1的流程图所示，本发明提出的互补多主体影响力传播模型的扩散过程主要分为下面几步：

(1)输入社交网络带权有向图G(V,E)，A和B的种子集，全局互补参数γ

(2)初始时，所有在A的种子集中的节点采用A，在B种子集中的节点采用B，而其他节点则置为未采用状态。对于每个节点v∈V，随机均匀地从[0,1]中生成阈值

(3)在每个时间步，检查每个未采用A的节点v，根据上文所述定义计算c

(4)检查每个未采用B的节点v，计算c

(5)如果在本时间步有任何节点采用了A或者B，则进行下一时间步，返回第(3)步。否则传播过程终止，进入第(6)步。

(6)输出此时采用了A和B的节点集合作为影响力传播的结果。

上述的流程对于一组随机生成的阈值实例计算了给定种子集的影响力传播。通常，在评估一组种子集的影响力大小时，需要通过重复运行上述流程多次(即蒙特卡洛方法)，每次生成一组新的阈值，最后取多次运行中采用A(或B)的节点数量的平均值作为该组种子集影响力大小的指标，增加运行次数能使结果的误差变小。

如图2的流程图所示是以主体A为例，对于本发明中提出的影响力传播模型中一个节点的活跃边采样过程，分别下面几步：

(1)输入社交网络带权有向图G(V,E)和要采样的节点v。此处使用上文所述增加权值的方法来表示互补关系，对每条边(u,v)需要如下四个权值：

(2)从[0,1]中均匀地生成一个随机数

(3)如果存在一个j使得

(4)此时

通过对图中的每个节点v∈V都运行一次上述过程，即可完成整个图的实例采样，所得活跃边组成的的A子图可以用于求反向可达集。对于B的采样过程同理，只需在上述流程中更换相应边权即可，此处省略。

如图3所示是在本模型上进行自身影响力最大化的反向可达集采样的过程，主要分为以下几步：

(1)输入一个通过上述方法采样得到的实例子图H，B的种子集和本次反向可达集采样的起点v

(2)进行BFS，初始时将每个在B种子集中的节点加入BFS队列。在BFS过程中，每次从当前节点v可以访问且仅可以访问

(3)接下来将进行反向行走，初始时将返回的集合R设为空集，令u表示当前反向行走正处于的节点，将其初始化为v

(4)在反向采样的每一步，将当前节点u加入集合R中。随后，如果u已经采用了B，则应当沿着反向边

(5)判断反向行走是否结束。如果u＝0，表示行走的反向边不存在，此时结束反向行走。同理，如果新的u已经在R中，则反向行走遇到了环，因此也可以终止行走，进入第(6)步。如果不是上述两种情况，即u≠0且

(6)返回集合R作为反向可达集。

使用上述方法采样获得的反向可达集可以应用于IMM算法，以便高效地求出一组较优的自身影响力最大化问题的A种子集。

上述实施例用来解释说明本发明，而不是对本发明进行限制，在本发明的精神和权利要求的保护范围内，对本发明作出的任何修改和改变，都落入本发明的保护范围。