本论文发表于 IEEE TRANSACTIONS ON COMPUTATIONAL SOCIAL SYSTEMS, VOL. 11, NO. 1, FEBRUARY 2024

Abstract

  由于在病毒式营销中的重要应用，影响力最大化（IM）已成为一个经过充分研究的问题。它的目的是找到一小部分初始用户，以便他们可以通过口碑效应向最大数量的用户传递信息。原来的IM只考虑单例项目。大多数扩展忽略了不同项目之间的关系或只考虑它们的竞争性交互。事实上，当用户提前采用补充产品时，一种产品的扩散概率就会增加。受此场景的启发，我们提出了补充独立级联（IC）并讨论补充 IM 问题。我们的问题是NP-hard，目标函数的计算是#P-hard。我们注意到，当考虑其补充产品的影响时，扩散概率会发生变化。因此，即使目标函数是子模函数，有效的反向影响采样（RIS）技术也不能直接应用于我们的问题。为了解决这个问题，我们利用三明治近似（SA）策略来获得依赖于数据的近似解。此外，我们定义了基于补充的反向可达（SRR）集，然后提出了一种启发式算法。最后，三个真实数据集的实验结果支持了我们方法的效率和优越性。

I. INTRODUCTION

  如今，在线社交媒体已经融入我们的日常生活。用户习惯于通过这些媒体接收和发送信息[1]、[2]。因此，在线社交网络中的信息传播已被研究人员广泛研究。影响力最大化（IM）问题是找到k个用户，通过口碑传播可以将信息传递给最多的用户[3]。有两种经典模型，即独立级联（IC）模型和线性阈值（LT）模型。尽管 IM 问题在这两种模型下都是 NP 困难的，但是 Kempe 等人。 [3]证明传统的贪心算法可以给出 (1 − 1/e) 近似解。

  然而，传统的贪心算法需要使用蒙特卡罗模拟来估计影响力扩散。这将使得该方法无法应用于大规模网络。此外，蒙特卡罗模拟在计算影响力传播的预期数量时无法给出保证。一些研究人员致力于提高算法的效率[4]、[5]、[6]、[7]、[8]、[9]。其中，博格斯等人。 [6]首先从反向影响抽样（RIS）的角度提出了重要突破。此外，我们观察到 IM 问题仅考虑单个项目的影响。一般来说，多个项目可以在同一网络中扩散。 [10]、[11] 提出了一些多重级联问题。其中一些只是简单地扩展了经典的IC和LT模型，忽略了多个级联之间的关系[12]、[13]。大多数现有作品假设实体是纯粹竞争的[14]、[15]、[16]、[17]。也就是说，当社交网络中传播多个实体时，每个用户只能采用其中之一。有一些扩散模型允许用户采用不止一种类型的实体[18]、[19]。然而，在他们的工作中，他们假设当用户采用另一实体时，一个实体的影响概率会降低。

     现实中，多个实体之间存在着补充关系。更具体地，提前采用另一项目后，一项项目对用户的影响概率将会增加。例如，当一个人之前已经使用过 iPhone 时，他或她更倾向于购买 AirPods。以以下场景为例。社交网络中有两个项目 A 和 B。如果用户提前采用项目A，那么他们将有更高的概率采用项目B。鉴于项目 A 的分布，项目 B 的种子将其影响力传播的预期数量最大化。

    受这种现实场景的启发，我们定义了补充 IC (SIC) 模型和补充 IM (SIM) 问题。事实上，卢等人。 [20]讨论了一个称为自我 IM 的类似问题。与他们的工作不同，我们在扩散模型中的实体不是互补的。更准确地说，他们假设商品 A 可以促进商品 B 的传播，商品 B 也可以促进商品 A 的传播。但是，我们的问题并没有定义商品 B 必须促进商品 A 的传播。同时，在他们的工作时，每条边上的扩散概率为 1。在我们的模型中，每条边上的概率在 0 到 1 之间。林等人。 [21]提出了k-Boosting问题，该问题要求k个提升用户，以便最大化影响力传播。 Boost 节点在不受其他活动节点影响的情况下不能处于活动状态，但一旦受到其他节点的影响，它们就更有可能处于活动状态。与我们的工作不同，这个 k-Boosting 问题侧重于寻找初始提升用户而不是种子用户。

总之，我们对本文的主要贡献如下。

1）考虑到项目之间的补充关系，我们扩展了IC模型并定义了SIC模型。基于该扩散模型，提出了SIM问题。考虑到补充品的分布，问题是找到能够最大化其影响力传播的种子用户。我们认为这个问题是NP-hard，目标函数的计算是#P-hard

2）幸运的是，目标函数是子模的。然而传统的贪婪会导致效率低下。而原来的RIS不能直接适用于我们的问题，因为它的影响扩散会受到其补充项的影响。为了解决这个问题，我们构造了它的上限和下限。使用夹心近似（SA）策略，可以获得依赖于数据的近似解。

3）此外，我们忽略由于产品及其补充产品的到达顺序而引起的扩散概率变化。根据这个假设，我们设计了一种基于补充的反向可达（SRR）集的算法。

4）最后，我们进行了广泛的实验，并将我们提出的算法与三个现实世界数据集中的一些启发式算法进行了比较。这些实验结果支持了我们方法的正确性和优越性。

我们的文章组织如下。第二节介绍了一些相关工作。第三节介绍了扩散模型和我们的问题。我们在第四节中讨论不同情况下的近似算法。第五节介绍了广泛的实验。最后，我们在第六节中结束我们的工作。为了便于参考，我们提供了一些术语中经常使用的重要符号。

II. RELATED WORK

A. IM Problem

社交网络通常被描述为有向图 G = (V, E)，每条边 (u,v) 上的概率为 p(u,v)。节点集和边集分别表示用户和用户之间的关系。每个节点都处于活动状态或不活跃。如果节点采用一项，则该节点处于活动状态，否则处于非活动状态。形式上，给定图 G = (V, E) 和整数，IM 问题旨在寻找 k 个节点以最大化最终预期的活动节点数。 Domingos 和 Richardson [1] 首先讨论了这个问题。他们将网络建模为马尔可夫场，并提出了最大化的启发法。肯佩等人。 [3] 然后将 IM 视为组合优化。他们提出了 IC 和 LT 模型，并证明这两个模型都是 NP 难的。此外，他们证明了目标函数是非负的、单调非减的和次模的。然后，使用传统的贪婪方法[22]得到一个 (1 − 1/e) 近似解。 IC 模型是经典的扩散模型，其工作原理如下。一开始，让所有种子节点处于活动状态，其他节点处于非活动状态。接下来，每个新激活的 u 有一次机会以成功概率 p(u,v) 激活其每个不活动的外邻居 v。如果没有新激活的节点被激活，则该过程将终止。我们的模型是该 IC 模型的扩展。

B. Reverse Influence Sampling

  在每次迭代中，贪婪需要估计目标函数，因为计算目标函数是#P-hard的[23]、[24]。然而，使用蒙特卡罗模拟估计目标函数时耗时且缺乏保证。为了提高算法的效率，人们提出了具有成本效益的惰性前向算法[4]和度折扣启发式算法[5]。最近，博格斯等人。文献[6]首先提出使用RIS方法来估计目标函数。他们定义了反向可达（RR）集，其中包含可以到达选定节点的可能节点。给定一个集合 S，该集合 S 可以覆盖的 RR 集合的分数将用于估计 IM 问题的目标函数。遵循该方法，提出了一些更有效的算法。例如，唐等人。 [7]、[25] 设计了两阶段影响最大化 (TIM)、TIM+ 和通过鞅的 IM (IMM) 算法。他们证明了他们的算法具有接近最优的时间复杂度，并且可以返回概率至少为 1 − δ 的 (1 − 1/e − ε) 近似解。这里，ε和δ都是其算法中的参数。后来，Nguyen 等人。 [26]设计了stopand-stare算法（SSA）和动态SSA（DSSA），以及Tang等人。 [27]提出了影响力最大化在线处理方法（OPIM-​​C）。虽然我们的问题不能直接通过这些技术解决，但我们提出的算法仍然基于RIS方法。

C. Multicascade IM

   我们观察到传统的 IM 问题研究的是单个项目的影响力传播。然后，一些研究人员扩展了经典的 IC 和 LT 模型，并研究了一些多级联 IM 问题 [12]、[13]、[28]、[29]。例如，张等人。 [12]设计了多阈值模型并提出了多次采用问题的利润最大化。这些作品忽略了不同项目之间的关系。此外，一些工作专注于解决竞争性 IM 问题 [14]、[15]、[16]。巴拉蒂等人。 [14]首先讨论了竞争性 IM 并将影响扩散扩展到多个竞争级联。然而，并非所有项目之间的关系都是竞争的。卢等人。 [20]设计了一个比较 IC 模型，研究从竞争到互补的相互作用。基于这个模型，他们讨论了自我IM和补充IM。根据互补关系，Guo和Wu[10]研究了互补产品的IM。在我们的工作中，我们定义了一个SIM问题，它认为一个项目可以补充另一个项目的扩散概率。

III. PROBLEM FORMULATION

我们首先在本节中介绍扩散模型和问题定义。然后，我们讨论这个问题的一些性质。

A. Diffusion Model

  事实上，一家公司的一种产品的所有者可能更愿意从该公司购买另一种产品。以苹果运营商为例。该公司生产 iPhone 和 AirPods。 iPhone用户更有可能购买AirPods。我们说iPhone是AirPods的补充产品。考虑到这种情况，我们研究以下模型。

  将图 G = (V, E) 表示为社交网络。这里，V和E分别代表用户和用户之间的关系。并且我们假设 |V |=n 和 |E|=m。对于每条边 (u,v)，令 p(u,v) ∈[0, 1] 为 u 影响 v 的概率

   在我们的工作中，有两种产品。为了便于解释，我们将这两个乘积表示为 A 和 B。因此，对于每条边 (u,v)，乘积 A 和 B 的扩散概率分别为 pA(u,v) 和 pB(u,v) 。假设产品A是B的补充产品，即当用户v之前采用产品A时，产品B在每条边(u,v)上的扩散概率增加。我们假设概率增加到 p+ B (u ,v)。

   在我们的工作中，有两种产品。为了便于解释，我们将这两个乘积表示为 A 和 B。因此，对于每条边 (u,v)，乘积 A 和 B 的扩散概率分别为 pA(u,v) 和 pB(u,v) 。假设产品A是B的补充产品，即当用户v之前采用产品A时，产品B在每条边(u,v)上的扩散概率增加。我们假设概率增加到 p+ B (u ,v)。

 1) 开始时，SA中的每个节点都是A活跃的，其他节点都是不活跃的。

2) 在时间 t = 0 时，令 SA 和 SB 中的每个节点分别为 A-active 和 B-active。

3) 在时间 t > 0 时，对于 A 级联，每个新激活的节点 u 尝试以成功概率 pA(u,v) 激活其每个不活动的外邻居 v。同时，对于B级联，每个新激活的节点u也尝试让每个不激活的外邻居v激活。这里，如果节点 v 在时间 t (< t) 处处于 A-active 状态，则成功概率是 p+ B(u, v)(> pB(u,v))。否则，节点 v 将以概率 pB(u,v) 处于 Bactive 状态。

4) 如果没有新激活的B级联节点，则流程终止。

   现在，让我们看一个例子来说明扩散过程。如图1所示，只有三个节点v1，v2，v3和两条边（v1，v2）和（v2，v3）。对于每条边 (u,v) ∈{(v1,v2), (v2,v3)}，我们假设 pA(u,v) = 1, pB(u,v) = 0.5 且 p+ B(u,v) ) = 0.8。设 ˆ SA = {v3}，SA = {v1}，SB = {v1}。最初，v1 和 v3 都是 A-active，v1 是 B-active。接下来，节点 v2 肯定可以是 A 激活的，因为 pA(v1,v2) = 1。同时，v1 尝试以 0.5 的概率激活 v2 以进行 B 级联。如果 v2 不能是 B-active，则该过程终止。否则，v2 将处于活动状态并尝试下次以 0.8 的概率激活 v3。这里，概率是 0.8sincev3 之前是 A-active。最后，无论v3是否处于活动状态，该过程都会结束。

B. Problem Definition

  接下来，我们将重点关注在一个社交网络中传播的两种产品，并提出 SIM 问题。我们将 G = (V, E, P) 称为有向图，其中 P = (PA, PB, P+ B )。更具体地说，PA和PB分别是产品A和B的影响概率。 P+ B ={p+ B(u,v) ≥ pB(u,v) : (u,v) ∈ E} 表示 v 提前处于 A 活跃状态时的影响概率。设 ˆ SA 和 SA 分别为产品 A 的初始活动节点和种子节点的集合。给定网络 G，集合 ˆ SA 和 SA，SIM 问题是寻找种子集 SB ⊆ V 且 |SB|=k，使得它可以最大化 B 活跃节点的预期数量。此外，我们用 f (SB) 表示 B 活跃节点的预期数量。形式上，SIM 问题是

其中 X 是一种可能的结果，每条边都是确定性的，fX 是结果 X 下 B 活动节点的总数。

给定图 G = (V, E, P)，如果 A 活跃（或 B 活跃）节点 u 可以成功影响节点 v，则边 (u,v) 是 A 活跃（或 B 活跃）。否则，该边被声明为 A 阻塞（或 B 阻塞）。为了更好地理解我们的问题，我们计算图 1 所示示例的目标函数值。如上所述，我们令 pA(u,v) = 1、pB(u,v) = 0.5 和 p+ B(u,v) = 0.8 对于每条边 (u,v) ε{(v1,v2), (v2,v3)}。给定 ˆ SA ={v3}, SA ={v1},and SB ={v1} ，有四种结果，如图 2 所示。请注意，B-live 和 B-blocked 边由实线箭头和带有十字的实线箭头表示，

分别。这里，(v1,v2) 是 B-live（分别是 B-block），概率为 0.5（分别是 0.5）。由于 v3 ∈ ˆ SA，(v2,v3) 是 B-live（或 B-block），概率为 0.8（或 0.2）。在第一种情况下，边 (v1,v2) 和 (v2,v3) 是 B-live，即三个节点可以以 0.4 的概率成为 B-active。第二种情况，(v1,v2)是B-live，(v2,v3)是B-block，即两个节点v1和v2是B-active的概率为0.1。最后两种情况只会导致一个节点处于 B 活跃状态，总概率为 0.5。那么，我们有 f (SB) = 3 · 0.4 + 2 · 0.1 + 1 · 0.5 = 1.9。

C. Property

定理 1：SIM 问题是 NP 困难的，计算其目标函数是 #P 困难的。

证明：当 ˆ SA =∅ 且 SA =∅ 时，SIM 问题与经典 IC 模型下的 IM 问题完全等价。请注意，IM 问题是 NP 难题 [3]。因此，SIM 问题是 NP 困难的。通过类似的论证，对于任何给定的集合 SB，计算其目标函数是#P-hard的[23]、[24]。

定理 2：SIM 问题的目标函数是非负、非递减单调且次模的。

证明：根据定义，只需证明目标函数的子模性即可。 X 表示确定性结果。与[3]中的主张类似，对于给定的种子集 SB，当且仅当在该结果 X 中存在从 SB 中的某个节点到 v 的 B-live 路径时，节点 v 才可以是 B-active。请注意，如果一条路径中的每条边都是 B-live，则我们将该路径称为 B-live。令 R(v, X) 为在该结果 X 中 v 的影响力传播后可以处于 B 活跃状态的节点集合。然后，我们有 fX (SB) = ⋃ v∈V R(v, X )。给定任意两个集合 S ⊆ T 和一个节点 v ∈ V \ T ，足以证明

fX (S∪{v})− fX (S) 是包含在 R(v, X) 中但不包含在 ⋃ u∈S R(u, X ) 中的所有节点的数量。则，由于 S ⊆ T ，(2) 成立。此外，有 f (SB) = Σ X Pr[X ]· fX (SB) 且有定理如下。

IV. APPROXIMATION ALGORITHMS

  接下来，我们讨论如何解决 SIM 问题。为了解决这个问题，我们首先考虑 SA =∅ 时的特殊情况，然后研究 ˆ SA =∅ 时的情况。我们证明当 ˆ SA =∅ 时的方法可以很容易地用于一般的 SIM 问题。

A. Case When SA =∅

  根据定义，受种子集SA影响的A活跃节点是未指定的。同时，种子集SB在每一步的传播都与SA的传播有关。因此，SIM 问题不是与顺序无关的。这对解决这个问题提出了挑战。

  首先，我们讨论 SA =∅ 时 SIM 的特殊情况。在这种情况下，我们可以提前确定每条边的状态。使用蒙特卡罗方法估计影响力传播的简单方法。更具体地说，我们首先对一些确定性图进行采样。确定性图的生成如下。给定图 G = (V, E, P) 和集合 ˆ SA，我们构造一个新的传播概率 Q = {q(u,v) : (u,v) ∈ E}，其中

用 = (V, E, Q) 表示具有边概率分布 Q 的图。对于确定性图 g ∼ ，每条边 (u,v) 的存活概率为 q(u,v)，阻塞概率为 1 − q(紫外线）。那么，对于确定性图g，影响扩​​散fg(SB)就是SB可以到达的节点数。给定一组确定性图 G，f (SB) 可以通过 Σ g∈G( fg(SB)/|G|) 来近似。显然，这种方法无法提供理论保证，难以处理大规模社交网络。

在本文中，我们使用 RIS [7] 技术来估计我们的目标函数。这个想法是受到RR集（RR-set）的启发。在图 = (V, E, Q) 下生成随机 RR 集 R，如下所示： 1) 对确定性图 g ∼ 进行采样； (2)随机选择节点v； 3）将g中所有能到达v的节点收集到R中。

引理 1 [25]：令 R 为 的 RR 集的集合。给定一个种子集 SB，如果 SB ∩ R =∅，我们说 SB 覆盖 R ∈ R。那么，f (SB) = n·E[SB 覆盖 R]，其中 E[·] 是预期算子。

根据上面的引理，我们知道我们的问题可以通过最大覆盖问题来解决[30]。该问题要求 k 个节点覆盖最大的尺寸给定的集合。如算法 1 所示，贪心算法可以返回最大覆盖问题的 (1 − 1/e) 近似解。给定一组 RR-sets R，我们重复选择可以覆盖 R 中最多 RR-sets 的节点 v。在每次迭代中，我们从 R 中删除 v 覆盖的所有 RR-sets。该过程停止，直到选择了 k 个节点。算法1的时间复杂度为O(k Σ R∈R |R|)。

  给定一组SB，设ISB为指示函数。即，如果 SB ∩ R =∅，则 ISB (R) = 1，否则 ISB (R) = 0。然后，对于给定的一组 RR-集合 R，我们可以通过 (1/|R|) · Σ R∈R ISB ( R) 来估计 f (SB)。当 RR- 的大小时，估计更加接近。集足够大。

引理2 [25]：令OPT 为SA =∅ 时SIM 问题的最优值。最大覆盖算法可以返回 (1 − 1/e − ε) 近似解，概率至少为 1 − δ，如果

此外，还有一些方法可以估计 R 的大小。例如，Tang 等人。提出了 TIM、TIM+ [7] 和 IMM 算法 [25]。此外，还提出了一些有效的算法，例如 SSA、DSSA [26] 和 OPIM-​​C [27]。我们可以使用这些方法来完成我们的算法。实际上，如果我们在(3)中使用k代替OPT，它可以提供RR集大小的上限，因为|SB|=k。

B. Case When ˆ SA =∅

我们提出了两种方法来解决这个 SIM 问题。一种近似算法利用 SA 策略。另一种是使用 RIS 技术和 SRR 集的启发式算法。

1）三明治近似：如定理2所示，SIM问题的目标函数是次模的。一种简单的方法是迭代选择边际增益最大的节点，直到所选节点的大小为 k。该方法可以返回 (1 − 1/e) 近似解[22]。然而，很难计算边际增益 v f (SB) = f (SB ∪{v}) − f (SB)

算法 2 给出了通过蒙特卡罗方法计算 f (SB) 的过程，模拟数为 r 。LetNin​​(u) = {v|(v, u) ε E} 且 Nout(u) ={v|(u, v) ε E}。在每次迭代中，我们首先生成一个实现 gA ∼ = (G, V , PA) 和一个队列 Q ={SB}。然后，我们使用广度优先搜索（BFS）模拟 B 活动节点的可能大小。请注意，当 w 提前处于 A 激活状态时，传播概率从 pB(u,w) 变为 p+ B(u,w)。设 dis(w, SB) 为 SB 到 w 的最小距离，用于模拟级联 B。此外，disgA (w, SA) 表示确定性图 gA 中 SA 到 w 的最小距离。对于随机数 α ε [0, 1], 如果 α ≤ pB(u,w)，则 w 可以受 u 影响。此外，如果 dis(w, SB)> disgA (w, SA) 且 α ≤ p+ B (你，w）。

BFS 的时间复杂度为 O(k(n + m))，计算 f (SB) 的总运行时间为 O(k(n + m)r )。使用蒙特卡罗方法，我们应该计算边际每次迭代时每个节点的增益。显然，这很耗时。因此，我们应该找到一种高效的算法。由于产品 B 每条边上概率的不确定性，我们无法使用 RIS 技术来估计目标函数。

为了解决 SIM，我们设计了一种基于 SA 策略的方法 [20]。该方法可以根据其子模下界和上界提供数据相关的近似解。接下来，我们开始构建目标函数的上限和下限，如下所示。给定 G = (V , E, P) 和 SA，令 VA 为包含 SA 可以到达的所有节点的节点集合。此外，我们构造一个新的传播概率 Q+ ={q+(u,v) : (u,v) ∈ E}，其中

令 R+ 为图 + = (V , E, Q+) 下的随机 RR 集。那么，f +(SB) = n · E[SB 覆盖 R+] 就是目标函数的亚模上界。类似地，令 R− 为 − = (V , E, PB) 下的随机 RR 集。我们有 f −(SB) = n · E[SB 覆盖 R−] 是亚模下界。

  在算法3中，上界的近似解如下获得。我们使用[25]中的方法估计 f + 的 OPT 下限。然后，我们创建 RR 集 R+ 的集合，其中|R+|由 (3) 计算，其下界替换 OPT。根据算法1，得到近似解Su。类似地，我们有下界 f − 的近似解 Sl。时间复杂度计算解 Sl 和 Su 的时间分别为 O(k Σ R∈R− | R|) 和 O(k Σ R ∈ R+ |R|)。设 So 是 f 的任意方法的解。在这里，我们估计每个节点 v ∈ V 的 f (v) 并选择 f 最大值的 k 个节点作为我们的原始解。 SA就是在这三个解中选择目标函数f的最佳解。也就是说，我们选择 SB = arg maxS∈{Sl,So,Su} f (S) 作为最终结果。选择最佳解SB的时间复杂度为O(k(n + m)r )。

定理3：设S*为原问题的最优解。至少有 1 − 2δ 概率，算法 3 可以推导出

近似解。证明：设 S* u 和 S* l 为最大化下界和上界的最优解

由于算法 3 返回一个解 SB = arg maxS∈{Sl,So,Su} f (S)，我们有

2）启发式算法：如前所述，由于产品B每条边上的概率的不确定性，我们不能使用RIS技术来估计目标函数。此外，我们考虑固定B级联的扩散概率。

  我们假设扩散概率为 p+ A(u,v) 当且仅当 v 在扩散过程中可以是 A 活跃的。也就是说，即使 v 在 B 活跃之后又是 A 活跃，我们仍然认为边 (u,v) 上的概率是 p+ A(u,v)。因此，我们定义一个随机 SRR 集并使用算法 4 对其进行计算。类似于RR 集，随机 SRR 集包含基于此假设的随机选择节点的可达节点。

  为了获得随机 SRR 集，我们首先确定 A 级联的结果。给定种子集 SA 和随机节点 v，算法 4 首先发现节点可以是 A-active。更具体地说，它利用前向 BFS 来查找从节点 SA 可以到达的节点。然后，算法 4 的目标是根据 A 级联的结果找到节点可以达到 v。如果u是A活跃的，则w可以以概率p+(w​​，u)被添加到SRR集合T中。如果u不是A活跃的，则w可以以概率p(w，u)被添加到SRR集合T中。在这里，我们使用后向 BFS 生成 SRR 集合 T。

 此外，我们得出以下引理。

引理 3：令 T 为随机 SRR 集。 f + 1 (SB) = n · E[SB 覆盖 T ] 是任何集合 SB 的目标函数的子模上限。

证明：根据定义，f (SB)/n 是所选节点 v 被 SB 激活为 B 活跃的概率。也就是说，从 SB 中的一个节点到节点 v 存在一条可达路径。注意，SB 覆盖 T 意味着从 SB 中的一个节点到节点 v 存在一条可达路径，无需级联顺序。因此，f + 1 是 f 的上限。

此外，f + 1 是子模。给定集合 S1 ⊆ S2 ⊆ V 和节点 v ∈ V \ S2，( f +(S1 ∪{v}) − f +(S1)/n) 是 v 可以覆盖 T 但 S1 不能覆盖 T 的概率。所以，( f +(S1 ∪{v}) − f +(S1)/n) ≥ ( f +(S2 ∪{v}) − f +(S2)/n) 并且引理如下。

使用RIS技术，我们可以估计n·E[SB 覆盖T ]并获得最大化n·E[SB 覆盖T ]的近似解。我们将该解视为 f 的解。

C. Case When SA =∅and ˆ SA =∅

    此外，我们可以使用当 ˆ SA =∅ 时的算法来解决当 SA =∅ 和 ˆ SA =∅ 时的情况。更具体地说，我们使用图 G = (V, E, P) 作为初始图 G = (V, E, P)，其中 PA = PA； ˆ PB ={ˆ pB(u,v) : (u,v) ∈ E} 且 ˆ pB(u,v) = p+ B(u,v) 如果 v ∈ ˆ SA 并且 ˆ pB(u,v) = pB(u,v) 否则； ˆ P+ B = P+ B。请注意，当每条边 (u,v) 的 pB(u,v) = 0 时，f − 将为 0。这里，pB(u,v) = 0 意味着如果节点不是 A-active，则该节点不能是 B-active。我们只能利用它的上界来获得 ( f (Su)/ f +(Su))·(1−1/e−ε) 的近似解。

V. E XPERIMENTS

  接下来，我们使用我们提出的算法和其他启发式方法进行了几次实验。相比之下，这些实验支持我们方法的有效性和效率。

A. Experimental Settings

1）数据集：我们基于三个真实网络进行实验：

1）Netscience [31] 捕获了从事网络理论和实验的科学家之间的共同作者； 2) HepTh [32] 是来自电子打印 arXiv 的引用网络。如果论文 i 引用论文 j ，则存在从 i 到 j 的边；3）Stanford [32]是从斯坦福大学网站生成的。每个节点代表页面，每条边代表页面之间的超链接。对于无向图，我们使用两个反向的有向边来表示每个无向边。这些网络的统计数据如表1所示。

2）影响概率：我们的问题存在三个影响概率。更具体地说，PA和PB分别是产品A和B的影响概率。 P+ B 是考虑其补充产品 A 的影响时 B 的影响概率。对于 PA 和 PB，我们从 [0, 0.1] 中均匀采样每个元素 pA(u,v) 和 pB(u,v)。根据[21]中的方法，我们令 p+ B(u,v) = 1 − (1 − pB(u,v))β ，其中β>1 为补充参数。除非另有说明，我们设置 β = 2。

3）种子的选择：我们应该在扩散过程之前固定种子集SA，我们使用两种方法给出集SA，如下所示。

1）我们使用IMM算法选择20个有影响力的节点[25]。一般来说，公司会选择有影响力的人物作为他们的初始用户来推广他们的产品2）我们随机选择200个节点。事实上，有些用户会自发地采用某种产品。为了便于参考，我们将上述两种情况分别称为case-1和case-2。

4）算法：应用IM算法时，每条边的影响概率是固定的。然而，在我们的问题中，级联 B 的概率可能会发生变化。据我们所知，没有现有的算法可以应用于SIM问题，我们主要考虑如下列出的几种算法。

1）SA：算法3中提出了该方法。我们参考IMM[25]来求解上下界。 2）SRR：该算法是算法4生成的SRR集的最大覆盖。 3）随机：随机选择k个节点，视为基线。 4）出度：该策略是选择出度最大的k个节点。 5）PageRank：PageRank得分最大的k个节点作为解[33]。我们让误差值和阻尼系数分别为10−6和0.85。 6）影响力最大化的线性算法（LAIM）：这是大规模社交网络中IM的线性时间算法[8]。这里，我们设置参数 γ = 4，并让每条边 (u,v) 的级联 B 的影响概率为 pB(u,v)，而不考虑级联 A 的影响。

5）设置：对于SA和SRR算法，我们固定ε = 0.5和δ = 1/|V |。为了确保实验的公平性，我们使用 10 000 次蒙特卡洛模拟来估计我们的目标函数。所有实验均在具有 3.6 GHz、四核处理器和 8 GB 内存的计算机上运行。

B. Experimental Results

  1）不同预算k的性能：首先，对于不同的预算k，我们评估从不同算法获得的不同种子集SB的影响力分布。如图所示。如图 3 和 4 所示，我们提出的算法（即 SA 和 SRR）对于情况 1 和情况 2 均优于其他算法。我们的算法在 HepTh 和斯坦福网络中表现尤其出色。这是因为在大型网络中目标函数值的差异更加明显。同时，case-1和case-2的结果相似。当三个网络中的预算 k 增加时，影响力扩散也会增加。并且SA和SRR的结果非常接近。这些意味着我们方法的效率、

2）SA策略的近似比：SA算法可以导出依赖于数据的近似比。为了显示这个近似比率，我们给出了上限、原始函数和下限以及 SA 算法返回的集合 SB 的结果。同样，我们在两种情况下进行实验。如图所示。 5和6，这三个函数的结果非常接近不管预算是多少 k.以 HepTh 为例。对于任何固定的 k，在情况 1 中，上限与原始函数的比率约为 0.96。原函数与下界的比值也约为0.96。同时，对于任何固定 k，在情况 2 中，比率均约为 0.85。根据图。从图 5 和图 6 可以看出，HepTh 网络和斯坦福网络中 case-2 的比率均大于 case-1。这是因为在HepTh和Stanford网络中，20个有影响力的节点可以比200个随机节点影响更多的节点。

 

3）不同集合^ SA的性能：下面，我们重点关注给出不同集合^ SA时的性能。为了反映 ˆ SA 的影响，我们只运行算法当SA处于情况1时。首先，我们分别在Netscience和HepTh中随机选择1000和10000个节点作为SA。如图7所示，产品B的影响力扩散仍然随着预算k的增加而增加。此外，我们将图 7 与图 3 进行比较。对于任何固定的 k，图 7 中的结果都大于图 3 中的结果。这表明 ˆ SA 可以强制最终的影响扩散。此外，我们固定 k = 25，并使用图 8 显示不同大小的 SA 的性能。当 k = 25 时 SA 和 SRR 返回的结果分别比 k = 5 高约 50%。

4）不同参数β下的表现：如表二所示，我们记录了产品B在不同补充参数β下在Netscience上的影响力分布。对于固定的 k，影响力扩散随着 β 从 2 增加到 6。这意味着补充产品可以增加影响力扩散。此外，我们观察到，当 k = 25 时的增量大于 k = 5 时的增量。更具体地说，当 k = 5 时，结果增加了 10，β 从 2 到 6。而当 k = 25 时，结果增加了 23这是因为更多的种子节点会影响更多的节点。

5）运行时间：我们只考虑SA和SRR算法的运行时间，因为其他算法都是启发式的。此外，我们还测试了当 ˆ SA = 0 时的运行时间。 表 III 表 III k = 5 时的运行时间（秒） 表 IV HEPTHINCASE-1 的运行时间（秒）显示了当 k 时 SA 和 SSR 算法的运行时间= 5（在三个网络上）。我们观察到，当网络规模增加时，运行时间会增加。同时，case-1的运行时间与case-2接近。对于HepTh 和Stanford，SA 算法的运行时间比SRR 算法长。这主要是因为SA算法需要处理原函数、下界和上界。最终，将原始目标函数最大化的结果。此外，RR集合的生成比SRR集合的生成更简单。因此，两种算法在Netscience中的运行时间没有太大差异。表 IV 显示了通过改变预算 k 的 HepTh 的运行时间。当使用 SA 和 SRR 算法时 k 增加时，运行时间会增加。

6）不同影响概率下的性能：与其他设置不同，对于每条边（u，v），我们分别从Netscience中的[0, 0.05]和[0, 0.2]中采样影响概率pB（u，v）。实验中，pA(u,v)仍然从[0, 0.1]中采样并保持恒定且β = 2。如表V和VI所示，实验结果表明，当pB(u的取值范围较大时，结果会增大) ，v) 增加。例如，当 k = 25 时，当 pB(u,v) ε[0, 0.05] 时，影响力分布约为 40；当 pB(u,v) ε[0, 0.2] 时，影响力分布约为 115。

VI. CONCLUSION

  本文将经典 IC 扩展至多种产品，并将其称为 SIC。遵循这个模型，我们研究一个自然问题，即 SIM 问题。给定补充产品的分布，问题旨在找到k个节点以最大化其自身的影响力传播。我们证明这个问题是 NP 困难的，并且计算目标函数是 #P 困难的。幸运的是，目标函数是子模函数。然而，由于补充产品的影响，RIS方法不能直接用于估计目标函数。基于SA方法，我们获得了依赖于数据的近似解。此外，我们定义了 SRR 集并提出了基于它们的算法。最后，为了展示我们方法的有效性，我们将我们的策略与三个网络上的一些启发式算法进行比较。未来我们会尝试基于这个模型来考虑从竞争到互补的关系。我们可以用另一个模型来研究这个问题。