地理社交网络中基于多目标组合优化的空间感知影响力联合最大化

2022-02-11金鹏飞常雪芹房子荃

计算机研究与发展 2022年2期

金鹏飞常雪芹房子荃李淼

1(浙江大学计算机科学与技术学院杭州 310027) 2(华为技术有限公司华为云架构业务部广东深圳 518129)

随着地理定位技术与移动社交服务的发展，融合位置信息的地理社交网络(如Foursquare、Gowalla、美团网、街旁网等)成为广受用户欢迎的一类社交媒体平台.据统计，截至2020年，美团平台上的活跃商家个数以及年度交易用户总量已分别增长至680万和5.1亿；与此同时，2020年度Foursquare通过旗下的签到业务已在全球190个国家与地区累计收集了9 500万个不同类别的兴趣点信息.地理社交网络有效地连接了用户的线上信息与线下行为，便捷的线下服务与相对低廉的线上广告成本，也使得更多商家将地理社交网络作为一类有效的市场推广途径.

面向社交网络“病毒式”营销(viral marketing)，影响力最大化(influence maximization, IM)问题旨在从社交网络中寻找并激活

个具有高影响力的用户节点(影响力种子)，利用社交用户间“口口相传”(word of mouth, WOM)的特性，触发影响力在用户间的连锁式传播，从而使影响力传播最大化.近年来，得益于5G与物联网技术的发展，基于位置的广告营销呈现出极大的商业潜力.据权威部门预测，2021年位置营销服务将在北美市场创造约1 375亿美元的收益.对应基于位置的营销研究，地理社交网络中的空间感知影响力最大化问题已成为IM领域一个重要的研究分支.区别于传统IM问题在社交网络全图中实现最大化传播，空间感知IM问题考虑了用户在物理世界中的空间属性，使影响力在一部分位置相关的用户群体中达到最佳的传播效果.Li等人最早在基于位置的社交网络中研究了位置感知影响力最大化(location-aware influence maximization, LAIM)问题，给定一个查询范围，LAIM问题尝试从社交网络中寻找

个种子节点，使影响力在查询范围内的用户中达到最大传播规模.然而，在LAIM问题中，用户如何设定合理的查询范围是一个潜在的难题.具体而言，假如用户设定的查询范围过小，大量空间邻近用户将因在查询范围之外而无法成为营销推广对象；若查询范围设定过大，则相当一部分被激活的用户将处于查询范围的边缘区域，受空间移动的限制，这部分用户无法真正成为线下活跃用户.为解决此问题，Wang等人提出距离感知影响力最大化(distance-aware influence maximization, DAIM)问题，认为距离查询位置更近的用户将更有可能被营销活动所吸引，因而具有更高的推广价值.基于此，DAIM对各用户分配了不同的价值权重，以指导空间距离加权下的影响力种子选择.

值得注意的是，当前有关空间感知IM问题的研究，都只将固定位置处的单一空间对象作为推广目标.这一设定仅能在有限的空间范围内吸引较少的客户，故不利于商家最大化地拓展其市场潜力.为实现利益最大化，商家需要有多个营销目标，如连锁店公司对旗下的多家门店进行联合推广.考虑到大型连锁公司旗下庞大的门店规模(如星巴克在中国大陆的门店规模总计约为5 000家，2020年新增门店259家)，受广告篇幅与费用的限制，商家将无法在单条广告中穷尽所有门店信息.如何从所有门店中优先推选出一部分最具潜力的门店作为线上推广主体，并搭配有效的社交营销策略以实现商家利益的最大化是本文研究的重点.图1进一步展示本文的研究动机.

Fig. 1 An example of location based social advertising for multiple promotion targets图1 基于位置的多目标营销场景示例

图1展示了某城市中心新开设的3家星巴克门店(

)

为方便统计，规定单一的某家门店仅能对其附近3 km范围内(图中兴趣点图标周围圆形阴影区域)的用户产生影响，同时商家发布广告的内容篇幅最多容纳2家门店信息，且营销的费用预算为1(影响力种子个数为1).在此条件下，若选择门店

作为营销推广目标，用户

作为发起线上影响力传播的种子，则影响力传播过程将激活7名用户，其中4名(

)位于推广位置的邻近区域，故此次营销的实际收益为4；若选择门店

作为推广目标，并改变影响力种子为用户

，则影响力传播的总体规模为6，但由于传播过程中所有用户均与推广门店位置邻近，故该策略下商家营销的实际收益将上升为6.

在图1示例中，本质是求解一组推广目标与影响力种子集合的最优搭配，从而使商家在基于位置的营销中获得最大化的收益.本文将该问题称为基于多目标组合优化的空间感知影响力联合推广(location-aware joint influence promotion, LA-JIP)问题.相比于传统IM问题以及空间感知的IM问题变种，LA-JIP问题的求解有着更多的挑战：1)在不同位置组合下，用户权重的衡量将更为复杂，且评估影响力传播过程中所获得的收益本身是一个#P难题，如何对影响力传播收益进行高效而准确的评估是解决LA-JIP问题的关键；2)LA-JIP问题涉及对推广目标的位置与影响力种子的联合选取，该问题本身为一个NP难问题，且目标函数不满足子模特性，故传统的贪心策略将无法直接对该问题实现理论精度保障下的求解；3)LA-JIP是一个多目标组合优化问题，由于不同优化目标间彼此关联性强，故难以针对某一目标设计有效的剪枝方式以加速问题的精确求解.综上所述，本文工作的主要贡献有4个方面：

1) 面向真实应用，首次研究了地理社交网络中基于多目标组合优化的空间感知影响力联合推广问题LA-JIP，通过发现门店推广位置与影响力种子的最优组合搭配，以实现商家利益最大化的营销推广；

2) 基于反向影响力采样技术，提出了在用户影响力加权条件下的影响力传播收益上下界推导方法，以有效地评估多目标组合下的营销推广效益；

3) 提出了满足结果精度收敛的迭代处理算法，通过多轮的结果迭代优化，该算法能够在一定的理论精度保障下对LA-JIP问题进行高效的近似求解；

4) 在多个真实数据集上对所提问题及技术方法的有效性进行了验证.实验结果表明相比传统IM或DAIM问题，LA-JIP能够有效地提升空间感知影响力推广收益；此外，所提出的迭代处理算法相比传统贪心策略下的基准算法，结果质量提高10%～50%、算法运行效率快1～2个数量级.

1 相关工作

影响力最大化问题最早可追溯至对“病毒式营销”和“口碑效应”的研究.Domingo和Richardson首次将影响力最大化分析引入社交领域，并指出了该问题在舆情预警与市场营销中的重要性.随后，Kempe等人首次从算法角度将影响力最大化定义为一个组合优化问题，在独立级联(independent cascade, IC)模型与线性阈值(linear threshold, LT)模型下证明了该问题的NP难复杂性，并基于问题的子模特性在贪心策略下提出了精度为(1-1/e)的近似算法，但该算法需涉及大量耗时的蒙特卡罗模拟来对节点影响力进行评估，因而算法时间复杂度极高，不适用于大规模社交网络.此后，一些研究者提出了启发式方法以识别高影响力的用户节点，这类方法尽管在效率上有较大提升，但其求得结果的精度缺乏理论保证.后续大量研究工作致力于提出满足理论精度保证的高效近似算法，以支持大规模社交网络图下的IM问题求解.针对这一目标，大量高效的影响力采样策略被提出.其中基于反向影响力采样技术的算法被证明不仅具有理论精度保障，而且满足渐线性的时间复杂度，因而成为当下最为有效的一类IM问题处理方法.这类算法的核心是采样足够规模的随机反向影响力可达集，从而对高影响力节点展开有效的分析与选择.后续基于该方向的一系列拓展工作，集中解决了如何在不改变结果精度的前提下尽可能地减少随机反向可达集的采样规模，以最大化地提升算法的处理效率.

近年来随着移动社交服务的兴起，地理社交网络中的空间感知影响力最大化问题引起了学术界的广泛关注.Li等人最先研究了空间感知影响力最大化的问题原型，该工作借鉴了“口碑营销”的思想，通过从全局社交网络中寻找

个种子节点，以触发影响力在给定空间查询范围内的最优传播效果.进一步地，Wang等人在文献[9]中提出了距离感知的影响力最大化(distance-aware influence maximization, DAIM)问题，给定一个地理位置坐标，DAIM根据用户与查询位置间距离的远近，对不同位置处的用户推广效益进行加权处理，最终使所选种子的影响力能够在邻近用户群体中产生最优的推广效果.类似DAIM，文献[23]综合考虑了社交影响力传播过程中的时间有效性，研究了目标用户影响力最大化问题，该工作基于反向影响力采样的思想提出了基于加权反向可达采样树的近似算法，实现了理论精度保障下的问题求解.受LAIM启发，文献[24]研究了地理社交影响力最大化拓展(geo-social influence spanning maximization, GISM)问题,给定查询区域

,GISM综合考虑区域

中用户的总体激活情况以及

中各个子区域内部用户的激活比率，使影响力能够在尽可能多的子区域间有更均衡的传播效果，GISM在区域性的政客竞选中有着重要的应用价值.此外，Zhong等人面向DAIM问题探讨了高效的锚点采样技术.Wang等人在社交媒体数据流上对LAIM问题展开了探索.Shi等人在文献[27]中通过对地理社交网络中兴趣点签到数据的分析，探索了地理位置驱动下影响力最大化问题.于亚新等人在考虑竞争的地理社交网络中研究了避免种子重叠的多方影响力博弈问题.面向多标准决策优化，Wang等人探讨了不同种子选取策略下的Pareto结果集高效求解方法，通过权衡营销过程中的代价与收益，为商家提供全面的营销决策支持.值得注意的是，上述的所有工作仅局限于通过改变影响力种子的选取策略来实现空间感知的影响力推广，而忽略了推广目标本身在空间属性方面所具有的优化潜能，这也是本文研究工作与现有工作的最大不同之处.

2 问题定义

本节首先介绍问题的相关预备知识，其次对问题进行形式化定义与难度分析，最后基于贪心策略提出一种启发式方法作为求解问题的基准算法.表1列出了文中常用的符号及其含义.

Table 1 Symbols and Description

2.1 预备知识

对社交网络中影响力传播过程的分析需借助特定的传播模型.目前学术界对影响力传播模型的研究主要集中于：独立级联(independent cascade, IC)模型、线性阈值(linear threshold, LT)模型以及触发模型，读者可查阅文献[30]对各模型的相关细节进行深入的了解.本文使用IC模型来对社交网络上影响力传播过程进行建模.

IC模型是一种概率模型.在IC模型中，社交网络中的每个节点仅能有2种状态：激活状态(active)或者未激活状态(inactive).只有处于激活状态的节点才会对其邻居节点产生影响.基于此，独立级联模型将影响力的传播过程抽象为以下多个轮次的随机过程：

1) 在初始时刻

，种子集

中的用户被激活，社交网络中其他节点为未激活状态，影响力从

出发向周边节点进行传播；2) 在时刻

，上轮中被新激活的用户

以概率

(

)对所有未激活的出边邻居

进行激活尝试，用户间的激活尝试仅进行一次，且不同用户间的激活尝试彼此独立(

对

的激活不受其他节点的影响)

若

被成功激活，则

将保持激活状态直至传播结束

令

表示时刻

新激活的用户集；3) 在时刻

+1，

中用户(上轮中新激活的用户)继续执行2)中步骤

上述过程重复执行，直到社交网络中不存在可被激活的节点时，影响力传播过程结束

假设传播结束的时刻为

,则此时

=∅

(1)

(2)

2.2 问题定义与复杂度分析

(3)

定理1.

LA-JIP问题为NP难问题.

证毕

定理2.

在多目标组合推广场景中，计算种子在特定推广对象下的影响力收益为#P难问题.证明.当式(2)中权重衰减速率参数

=0时，社交网络中所有用户权重将统一为1，此时影响力收益将转化为传统IM问题中的影响力规模.由于计算影响力规模为#P难问题，故计算影响力收益同样为#P难问题

证毕

2.3 基准算法

考虑到当前有关IM问题的大多数工作倾向于使用贪婪策略来实现对问题的近似最优求解，为此本文继承这一思想，提出一类启发式算法对LA-JIP问题进行直观的求解.基准算法的基本思路在于使用贪婪策略，通过一轮循环来选取指定个数的种子与位置目标的集合配对，具体流程如算法1所示.该算法根据种子与推广位置的个数进行循环计算.在每次循环中，对不同用户(位置)在当前

*组合下的影响力收益增幅进行计算(行③⑤)，并选取当前拥有最大影响力收益增幅的用户(位置)加入集合

*)中(行④⑥).由于LA-JIP问题需要对2组集合的搭配进行优化，且集合内部与集合间元素都存在相关性，故算法1循环内部需交替地执行当前最优种子与位置的选取，以实现对2组集合元素的同步优化.值得注意的是，由于首次循环中算法考察当前最优的位置需借助已有种子的影响力传播情况，因此我们规定种子的选择步骤应优先于位置的选择.

算法1.

基准算法(Baseline).

输出：推广位置集

*、影响力种子集

①

*←∅,

*←∅；② while |

*|<

且|

*|<

*选择当前影响力收益增幅最大的用户*

④ if |

*|<

then

*←

*∪{

}；

*选择当前影响力收益增幅最大的位置*

⑥ if |

*|<

then

*←

*∪{

}；

⑦ end while

⑧ return

*，

算法1以一种较为直观的方式对LA-JIP进行了求解，但由于LA-JIP的非子模特性，该方法无法保证其返回的结果在严格意义下拥有(1-1/e)的近似度.

Fig. 2 The example of non-submodularity in LA-JIP图2 LA-JIP问题非子模特性证明示例

定理3.

LA-JIP问题的目标函数不满足子模特性.

证毕

3 多轮次迭代算法

由于基准算法无法提供明确的理论精度保证，故本节提出一套基于迭代的处理框架以支持精度收敛的LA-JIP问题求解.首先介绍反向影响力采样技术及影响力无偏估计策略的原理；其次基于鞅不等式(martingale inquality)设计针对影响力传播收益的上下界评估方法；最后基于上述技术对迭代算法的运行流程展开介绍，并给出结果置信度分析.

3.1 反向影响力采样技术

对影响力传播的评估涉及期望的求解，该问题实际为#P难问题，在大规模社交网络图中将产生巨大的计算开销.为了解决这一挑战，反向影响力采样(reverse influence sampling, RIS)是一类加速影响力评估的有效方法.RIS技术的核心在于构建一组采样结果集，即随机“反向可达集合”(random reverse reachable set, RR set)，并基于RR set对种子的影响力进行无偏估计(unbiased estimation).随机反向可达集合(RR set)可通过以下步骤生成：

RR set的构建细节与优化技术可查看文献[17-19,22].

(4)

(5)

(6)

3.2 影响力收益上下界评估方法

本节利用一类有效的概率统计方法：鞅不等式(martingale inquality)来量化影响力收益无偏估计值与影响力收益真实值之间的差异.

定义3

给定一组随机变量序列

,…,

，若E[|

|]<+∞，E[

,…,

-1]=

-1，则称该随机变量序列为鞅

(7)

(8)

(9)

(10)

(11)

证明：

exp(-ln(1

/δ

))=

，

证毕

证明:

证毕

1 位置集与种子集明确时影响力收益上下界评估

(12)

(13)

式(12)和(13)在推广位置与影响力种子组合内容已知的情况下对影响力收益上下界进行评估

以下将在位置集与种子集组合不确定的情况下，推导出所有潜在组合可获得的最大影响力收益上界

2 潜在位置与种子组合下的影响力收益上界推导

(14)

(15)

证明

根据影响力收益的定义(定义2)，有

则有

证毕

(16)

3.3 LA-JIP多轮迭代处理算法

基于3.2节中影响力收益上下界评估方法，迭代算法的执行流程如算法2所示.

算法2.

迭代算法.

输出：推广目标位置集

*、影响力种子集

①

*←∅，

ratio

←0；

③ while

ratio

<1-1

④ if (Round=1)

⑥ else

⑨ end if

Greedy_MultiLoc为算法2中重要功能函数，其被算法2反复调用以实现不同轮次下对当前最优位置集的更新，其伪代码如算法3所示

算法3.

Greedy_MultiLoc算法.

输出：推广目标位置集

①

*←∅；② while |

*|<

④

*←

*∪{

}；

⑤ end while

⑥ return

接下来进行结果置信度分析

假设算法2中while循环的最大迭代次数为

由于每轮迭代中，影响力收益上下界评估将产生2

的出错概率，故算法在所有轮次下累计出错的概率为2

因此，将以1-2

的置信概率获得指定精度下的近似结果

通常情况下，设定参数

|，由于算法2在实际执行过程中的迭代次数远小于|

|，因而1-2

≈1，即算法能够以较高的置信度获得(1-1

)下的近似求解

4 实验评估

4.1 数据集与测试环境

为验证本文研究内容及所提技术方法的有效性，本节使用2组真实的地理社交网络数据集：Brightkite和Gowalla进行实验评估.数据集可通过Stanford大学的SNAP项目在线获取.在Brightkite和Gowalla中，分别有11.4%和45.6%的用户无位置坐标，对于这部分用户，根据其朋友位置坐标的均值对其进行位置分配.处理后的数据集信息如表2所示:

Table 2 Statistics of the Datasets

实验测试的算法均使用C++语言编写，并在g++13编译器下编译优化.所有实验在配备有Intel i-7 2.9 GHz主频CPU，64 GB内存的PC机上运行，安装的操作系统为Ubuntu 14.04.

4.2 实验设定

1) 传播概率设定.参考当前IM研究领域中广泛使用的方法，本文采用加权级联(weighted cascade)模型对社交网络图边上影响力传播概率进行分配：

(

)=1

(

)|，其中|

(

)|表示用户

在社交网络中的入度

3) 影响力收益值评估.为客观评估不同算法所求结果的质量，实验对种子影响力传播过程进行10 000次蒙特卡罗(Monte Carlo, MC)模拟，并将此过程中被激活用户权重和的均值作为种子影响力收益.

4) 参数设定.为评估不同参数设置对算法的影响，我们在不同参数设定下对算法性能进行评估.各参数设定值的范围如表3所示，每行中黑体数字表示各参数的默认设定值.在评估参数性能时，我们仅改变其中某个参数的值，而固定其余参数为默认设定值.

Table 3 Parameter Settings

4.3 有效性评估

为了验证本文研究内容在空间感知影响力联合推广中的有效性，本节将LA-JIP策略下产生的影响力收益情况与下述策略进行对比：

3) Baseline策略.本文所提算法1(基准算法)，即解决问题的启发式算法；

4) LA-JIP策略.本文所提算法2(多轮迭代处理算法)，即求得的结果有理论精度保障的近似算法.

Fig. 3 The distribution of the users located in Dallas图3 达拉斯市区范围内用户分布情况

Fig. 4 The performance comparison of influence promotion for bars by different strategies图4 酒吧类兴趣点集合下不同策略的影响力推广效果对比

Fig. 5 The performance comparison of influence promotion for markets by different strategies图5 商场类兴趣点集合下不同策略的影响力推广效果对比

设置

=2，

=10，测试上述推广策略的执行效果.对不同策略返回的结果(推广位置集+种子集)执行蒙特卡洛模拟评估其影响力传播情况，使用百度地图API对传播中激活用户的位置进行可视化展示.由于各类兴趣点组下策略间的性能差异大体相同，本节仅对酒吧、商场这2类兴趣点集合下的结果进行展示(图4与图5).由图中结果可知，IM+DBSCAN策略在空间感知影响力推广中的效果最差，该策略激活用户的空间分布十分离散且与推广位置间无明显邻近关系；DAIM策略由于考虑了用户权重，故影响力传播相对推广位置有明显的空间聚合趋势.然而，由于该策略忽略了对推广位置的优化，推广位置个体间仍存在较多的影响力重叠，整体推广效果依旧不佳；Baseline策略由于在贪婪策略中对种子集与位置集进行了同步优化，故相比仅分开优化2组集合的IM+DBSCAN策略，影响力推广效果有明显的提升.

但由于Baseline策略无理论精度保障，因此优化性能并不稳定，在某些输入情况下Baseline策略的效果将劣于DAIM策略.作为对比，LA-JIP策略在各类兴趣点集合下始终中展现了全局最优的特点，且相比Baseline策略，LA-JIP策略整体性能更加稳定，产生的影响力分布情况相对推广目标的位置分布也更具空间聚合性.此外，由于LA-JIP策略进一步优化了推广位置的空间布局，因此LA-JIP相比DAIM减少了更多内部的影响力重叠，故在多目标组合下有更优影响力全局推广效果.

4.4 算法性能评估

本节在Brightkite和Gowalla两组数据集上，对基准算法(baseline, BA)、迭代算法(iterative, IT)的处理性能进行全面评估.实验比较了算法在不同种子个数、推广目标位置个数、侯选位置集合大小下的性能变化趋势.本文以算法的响应时间和所求结果的影响力传播收益作为衡量算法性能的2项指标.本文对每组实验重复5次测试，并取平均值作为最终结果.

4.4.1 种子个数对性能的影响

本文在Brightkite和Gowalla两组数据集下测试不同的种子个数(5,10,15,20,25)对BA与IT算法性能的影响，结果如图6所示.从图6结果可知，IT算法能够在BA算法基础上进一步提升10%～50%的影响力传播收益，且运行效率有1～2个数量级的提升.这验证了本文第3节中所提方法的有效性.此外，随着种子个数的增多，所有算法的响应时间及影响力传播收益均呈现增长趋势.这是因为较多的种子能触发更大的影响力传播范围，从而提高了影响力在用户中传播所能获得的收益；这同时也增加了算法在评估种子影响力过程中的开销.值得注意的是，所有算法在Gowalla数据集下均获得了比Brightkite数据集下更高的影响力收益.这是因为Gowalla相比Brightkite拥有更大的社交网络以及更为稠密的用户空间分布，因而Gowalla数据集下产生的种子能够激活更多高权重的用户，从而利于影响力在传播过程中积累到更多收益.这一对比结果体现了迭代算法在大规模社交图下实现空间感知影响力推广的性能优势.

Fig. 6 The effect of varying k on performance图6 种子个数k变化对算法性能的影响

4.4.2 推广目标位置个数对性能的影响

Fig. 7 The effect of varying m on performance图7 推广目标位置个数m变化对算法性能的影响

图7展示了推广目标位置个数对算法性能的影响.在不同的位置个数设定下，迭代算法的性能均明显优于基准算法，且在更大规模的Gowalla数据集上迭代算法较基准算法的性能优势更为明显.随着推广目标位置个数的增多，各算法取得的影响力收益均呈现增长趋势.这是因为推广位置的增加将使更多用户因邻近空间对象而拥有更大的推广权重，因而影响力传播过程将获得更大的收益.值得注意的是，当推广位置较多时(|

|≥4)，基准算法与迭代算法间性能分化趋势更为明显，这进一步体现了迭代算法在多目标组合优化处理中的优势.

4.4.3 侯选位置集合大小对性能的影响

图8展示了候选位置集合大小的变化对算法性能的影响.在不同规模的候选位置集合下，迭代算法的性能均明显优于基准算法.此外，随着候选位置集合的增大，各算法所得结果的影响力收益呈现先增加后逐渐趋于稳定的趋势.这是因为当候选位置集合规模较小时，加入更多的位置可使算法构建出与影响力空间分布更为拟合的推广目标位置分布.然而，当候选位置集增加至一定规模后，集合中的大量位置之间将存在较多的影响力重叠，从而使得影响力传播收益的增幅呈现减缓趋势.

Fig. 8 The effect of varying on performance图8 候选位置集合大小变化对算法性能的影响

4.5 对ε参数设定的评估

Fig. 9 Evaluate parameter ε in Brightkite dataset图9 Brightkite数据集下评估参数ε

Fig. 10 Evaluate parameter ε in Gowalla dataset图10 Gowalla数据集下评估参数ε

本节进一步探索迭代算法中对精度误差参数

的合理设定.图9～10展示了迭代算法在Brightkite数据集以及Gowalla数据集下基于不同精度误差参数

的运行结果(影响力收益、响应时间、RR set采样规模).从图9中结果可知，当

值较小时(

<0.20)，进一步减小ε对算法返回的结果精度提升效果并不明显；相反，还将导致算法的响应时间急剧增长，并在处理过程中耗费大量的内存开销(大量RR set被采样产生并作为中间结果常驻内存).当精度误差参数设定较大时(

≥0.20)，算法时间空间上的开销都明显降低，但结果精度损失却下降明显.权衡算法的求解效率与返回结果的质量，本文将

=0.20作为迭代算法的默认精度误差参数.

5 总结

本文研究了地理社交网络中基于多目标组合优化的空间感知影响力联合推广问题(LA-JIP).该问题考虑了影响力在位置相关用户中的推广差异，通过构建推广目标位置与影响力种子间的最优搭配，实现全局利益最大化的商家营销推广.为了有效地解决LA-JIP问题，本文拓展了现有的反向影响力采样技术，提出了有理论保障的影响力收益上下界评估方法，并基于此通过多轮迭代对问题进行了高效的近似求解.最终，在真实的数据集下实验结果验证了本文所提出的技术能有效地提升多目标组合下空间感知影响力推广.在未来工作中，我们将考虑引入更多的地理空间因素(如营销点的空间分布密集、营销位置相对各用户的

近邻排序等)来设计更为合理的用户权重度量函数，以使LA-JIP问题适应更多复杂的应用场景.此外进一步优化提升本文提出的近似算法的理论精度也是未来努力的方向之一.

作者贡献声明

：金鹏飞负责提出问题研究的动机与思路、算法设计方案、实验方案并撰写论文；常雪芹负责算法方案实现、实验测试、结果评估并协助撰写论文；房子荃与李淼提出指导意见并修改完善论文.