参考资料：

Li, Yuchen, Ju Fan, Dongxiang Zhang, and Kian-Lee Tan. “Discovering your selling points: Personalized social influential tags exploration.” In Proceedings of the 2017 ACM International Conference on Management of Data, pp. 619-634. ACM, 2017.

Borgs, Christian, Michael Brautbar, Jennifer T. Chayes, and Brendan Lucier. “Influence maximization in social networks: Towards an optimal algorithmic solution.” CoRR, abs/1212.0884 (2012).

Kempe, David, Jon Kleinberg, and Éva Tardos. “Maximizing the spread of influence through a social network.” In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 137-146. ACM, 2003.

1. Motivation & Application

文中定义了基于社交网络（Social Network, SN）的一种新操作：Personalized Social Influence Exploration (PITEX)。即对于特定用户而言，查询其能够达到最大影响力的标签集（Tag Set）。此操作在SN普遍的今天，具有很多潜在的用途：

1. 领导人竞选时需要利用社交网络（SN）分析了解其卖点。例如下图所示，每个候选人可以通过发送带有特定标签集（Tag Set）的tweet借由其follower向整个社交网络传播影响。候选人可以通过分析各个标签集造成的影响差异决定其政治立场以及演讲内容等等。
   

2. 社交媒体营销。即通过分析产品特征影响力确定营销策略。

3. 科研人员希望找到对学术界最具贡献的方向。

2. Problem Definition & Notation &Hardness

常用的Notation如下表所示：

简单地说，问题输入是一个社交网络（SN）的有向图结构G$G$，基于主题（topic, z$z$）的节点v1$v_1$对节点v2$v_2$影响力p(e|z)$p(e|z)$（e$e$的起点为v1$v_1$，终点为v2$v_2$），以及相应主题z$z$包含某一标签集w$w$的概率p(w|z)$p(w|z)$。应用于tweet数据中，p(e|z)$p(e|z)$表示用户v1$v_1$发表了关于主题z$z$的推特后，对follower v2$v_2$的影响概率（包括转发、接受观点等）；而p(w|z)$p(w|z)$则是任意用户发表主题z$z$相关的推特，会带有相应#hashtag w$w$的概率。PITEX问题初始输入的一个例子如下图所示：

基于上诉输入，我们可以估计用户u$u$使用标签集W$W$的影响力E[I(u|W)]$E[I(u|W)]$。首先计算各个节点间的影响概率：

基于上诉影响概率，再采用独立传播（independent cascade IC）模型，我们可以估计用户u$u$使用标签集W$W$的影响力。在IC模型中，每个节点具有**以及未**两种状态，每一步新**的节点会基于影响概率p(e|W)$p(e|W)$ **其未被**的相邻节点，直到没有节点再被**。初始状态时**初始节点u$u$，我们使用I(u|W)$I(u|W)$表示结束时被**的节点数，并定义影响力为其期望值E[I(u|W)]$E[I(u|W)]$。

综上，我们引入问题的正式定义：(Personalized Social Influential Tags Exploration (PITEX)) Given a social network G$G$, a PITEX query consists of a target user u$u$ who is initially activated and a number k$k$, and it aims to find a k$k$-size tag set W$W$ that maximizes u$u$’s expected influence spread. 即找到对于用户u$u$，找到大小不超过k$k$，影响力最大的标签集W∗$W^{\ast }$，使得影响力最大：W∗=argmax|W|≤kE[I(u|W)]$W^{\ast }=\arg \underset{|W|\le k}{max}E[I(u|W)]$

问题难度是NP-hard to approximate，因为包括一个subset selection问题，和一个基于概率估计影响力问题。

3. Straightforward Solution

一个最简单直接的解决方案就是遍历每一个可能标签子集W$W$，估计其影响力E[I(u|W)]$E[I(u|W)]$，然后选取影响力最大的标签子集W∗$W^{\ast }$。 可以看到对应于原问题中的两个部分（subset selection，influence estimation），解决方案中包括遍历子集（enumeration）以及影响力估计两个部分，后续分别对这两个部分做优化。

4. Optimization about Enumeration: Best-Effort Exploration

遍历所有子集的复杂度是指数级的，所以需要一种有效的剪枝手段。Best-Effort Exploration通过计算包含某一标签子集W$W$的任意标签子集W′ s.t.W⊂W′$W^{\prime }s.t.W\subset W^{\prime }$的影响概率上界p+(e|W),s.t.p+(e|W)≥p(e|W′) ∀W′$p^{+}(e|W),s.t.p^{+}(e|W)\ge p(e|W^{\prime })\mathrm{\forall }{W}^{\prime }$，得到包含某一标签子集W$W$的任意标签子集W′ s.t.W⊂W′$W^{\prime }s.t.W\subset W^{\prime }$的影响力上界。若所有包含W$W$的标签子集的影响力都小于其影响力上界小于当前最大值，则无需遍历所有包含W$W$的标签子集。关于计算影响概率上界p+(e|W)$p^{+}(e|W)$的LEMMA如下：

5. Optimization about Influence Estimation

直接计算概率的影响力是#P-hardness，过于expensive。故本文采用基于采样的算法对影响力进行估算。基于采样的算法首先计算为了达到某种要求（例如错误率小于ϵ$ϵ$的概率至少是1−δ−1(|Ω|k)−1$1-{\delta }^{-1}(\begin{array}{c}|\mathrm{\Omega }|\\ k\end{array}{)}^{-1}$）所需要的采样数θW${\theta }_W$，然后基于生成的样本实例，估计在给定概率图G=(V,E,p(e|W))$G=(V,E,p(e|W))$中节点u$u$的影响力。

5.1. Existing State-of-Art Sampling Strategies

已有的state-of-art算法中包括Monte Carlo Sampling (MC)和Reverse Reachable Set Sampling (RR Set)。详细内容请参考相关论文：

Kempe, David, Jon Kleinberg, and Éva Tardos. “Maximizing the spread of influence through a social network.” In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 137-146. ACM, 2003.

Borgs, Christian, Michael Brautbar, Jennifer T. Chayes, and Brendan Lucier. “Influence maximization in social networks: Towards an optimal algorithmic solution.” CoRR, abs/1212.0884 (2012).

后文的改进大多基于RR set的采样算法，这里做简单介绍：对于特定节点u$u$和标签集W$W$，通过去除所有p(e|W)=0$p(e|W)=0$的边，可以得到所有可能被u,W$u,W$影响的节点集RW(u)$R_W(u)$。采样算法在生成每个样本实例gi$g_i$的过程中，首先从RW(u)$R_W(u)$中以相同概率选取一个节点vi∈RW(u)$v_i\in R_W(u)$，然后以1−p(e|W)$1-p(e|W)$的概率去除每一条边，生成一个G$G$的子图gi$g_i$。 使用1[u→vi]=1$1[u\to v_i]=1$表示子图中u$u$可以到达vi$v_i$，则节点u$u$使用标签集W$W$的影响力估计为E[I(u|W)]=∑θWi=11[u→vi]⋅|RW(u)|/θW$E[I(u|W)]=\sum _{i=1}^{{\theta }_W}1[u\to v_i]\cdot |R_W(u)|/{\theta }_W$。关于θW${\theta }_W$计算的LEMMA如下：

5.2. Lazy Propagation Sampling

上诉传统采样算法中需要对图中的每条边进行若干次的伯努利分布采样，计算其是否保留c(e)∼p(e|W)$c(e)\sim p(e|W)$，其中c(e)$c(e)$为随机生成的0−1$0-1$随机数。实际使用的社交网络（SN）中，p(e|W)$p(e|W)$往往是稀疏的（即大多数情况p(e|W)$p(e|W)$较小）。而在p(e|W)$p(e|W)$较小的情况下，大多数采样结果并不会**该条边，相应的随机数生成计算显得并不必要。

简单的说，此部分优化是基于概率p$p$较低时，计算几何分布（geometric distribution）的消耗低于计算伯努利分布的消耗。具体地，Lazy Propagation Sampling通过采样若干次的几何分布，模拟多次伯努利分布采样的结果。几何分布是计算n$n$次伯努利采样中前k−1$k-1$次失败，第k$k$次成功的概率。经过若干次的几何分布采样，可以得到在n$n$次伯努利采样中，该边在哪几次采样中被**，从而模拟了n$n$次伯努利分布采样的结果。

5.3. Offline Index-Based Influence Estimation

上诉在线算法中，对于每次E[I(u|W)]$E[I(u|W)]$的估计都需要生成θW${\theta }_W$个样本实例。这对于在线查询来说消耗过大，不能满足即时查询的需要。offline index-based的算法通过线下构建索引的方式，将被所有u,W$u,W$组合共用的操作提前于线下进行，并存储中间结果（Index）；线上查询时接续剩余计算，得到查询结果，从而缩减了线上查询的时长。

5.3.1. RR-Graph Index Structure

此部分实际是RR Set算法应用于非确定（static）概率图中的变形，RR Set的详细内容请参考相关论文：

Borgs, Christian, Michael Brautbar, Jennifer T. Chayes, and Brendan Lucier. “Influence maximization in social networks: Towards an optimal algorithmic solution.” CoRR, abs/1212.0884 (2012).

注意到在RR online sampling算法中，每次采样实例的终点vi$v_i$是随机采样的，且可以与起点u$u$无关（RW(u)$R_W(u)$的存在更多是出于剪枝减少冗余计算的目的）。在不给定起点u$u$的情况下，我们仍然可以随机均匀采样vi$v_i$，然后生成相应的子图gi$g_i$；再对特定u$u$计算其在每个子图gi$g_i$中能否到达终点vi$v_i$，进而估计影响力。RR set算法利用上诉思想，可以同时估计static概率图中所有节点的影响力。

不同于经典的影响力估计问题，PITEX中的p(e)$p(e)$是随标签集W$W$变化的，所以不同的标签集对对应于不同的概率图。本文通过基于概率上界maxWp(e|W)$\underset{W}{max}p(e|W)$采样，然后线上验证的方法，使得采样实例子图对不同的标签集共享。

综上，RR-Graph算法的线下构建Index过程如下（基于p(e)=maxWp(e|W)$p(e)=\underset{W}{max}p(e|W)$删边，然后保留所有可能到达终点v$v$的节点V(v)$V(v)$与边E(v)$E(v)$，以及相应边上的随机数c(e)$c(e)$）：

1. Generate sample graphs GRRv=(V(v),E(v))$G_v^{RR}=(V(v),E(v))$ starting from uniformly sampled vertex v$v$
2. Generate a random number c(e)∈[0,1]$c(e)\in [0,1]$ for all e∈E$e\in E$;
3. V(v)⊆V$V(v)\subseteq V$ contains verticesthat reach v$v$ in G$G$ after removing all edges such that maxWp(e|W)<c(e)$\underset{W}{max}p(e|W)<c(e)$;
4. E(v)⊆E$E(v)\subseteq E$ contains edges with both ends in V(v)$V(v)$ and associated with c(e)$c(e)$.

下图是几个GRRv$G_v^{RR}$子图的例子，其中原图G$G$与问题定义中的输入例子相同，maxWp(e|W)=maxzp(e|z)$\underset{W}{max}p(e|W)=\underset{z}{max}p(e|z)$，阴影节点为随机采样终点v$v$：

由于是基于概率上界maxWp(e|W)$\underset{W}{max}p(e|W)$采样，算法无法如RR Set一样直接通过包含u$u$的子图数估计u$u$的影响力。在线上计算过程中，对于特定的u,W$u,W$，算法需要验证在每个子图GRRv$G_v^{RR}$中u$u$能否到达v$v$，进而估计影响力。算法定义 ”u$u$能够在GRRv$G_v^{RR}$中到达v$v$“ 如下：

文中推导了RR-Graph算法所需要的采样数θ$\theta$，结论如下：

对比于原在线采样算法，基于RR-Graph Index的线下算法不需要生成随机数，子图的大小通常也远小于原图，从而减少了线上操作的时间。

5.3.2. Effective Pruning Techniques

在RR-Graph Index-based算法中，在线部分需要遍历每个子图GRRv$G_v^{RR}$验证u$u$能否到达终点v$v$。考虑p(e|W)$p(e|W)$大多数情况下远小于maxWp(e|W)$\underset{W}{max}p(e|W)$，在线验证到达性的部分仍然包括许多冗余操作。

本文通过验证子图的u−v$u-v$割（cut）的连通性进行剪枝。具体地，寻找一个u−v$u-v$之间的割，若割中的所有边都被删除（即p(e|W)<c(e)$p(e|W)<c(e)$），则u$u$必然无法到达v$v$，从而无需遍历整个子图。

割的选择构建直接影响上诉剪枝的有效性，论文作者直觉上认为p(e)$p(e)$与c(e)$c(e)$相近的时候更有可能有效剪枝。但按照某种标准寻找割的过程仍然需要遍历图（与出发点不符）。本文直接比较u$u$的出边和v$v$的入边分别构成的两个割，选取其中更可能进行有效剪枝的割进行验证剪枝。

5.3.3. RR-Graphs Delay Materialization

上诉RR-Graphs Index需要存储大量的GRRv$G_v^{RR}$子图，对于|G|$|G|$,|W|$|W|$较大的情况，存储index的时间与空间过大。Delay Materialization不存储子图，而是存储包含各个节点u$u$的子图数；在线操作过程中对子图重新生成；从而减少了存储子图的时间与空间。

为了maintain theoretical gaurantees，需要保证在线生成的子图和直接保存的线下子图同分布（包括包含u$u$的子图的数量，以及随机数c(e)$c(e)$的分布）。具体算法如下：

6. Experiment Results

首先验证算法的收敛性，发现文中最终优化结果，线下RR-Graph系列，的收敛性质与MC相近：

算法的准确性是通过理论保证，大部分优化针对在线查询的平均消耗时间，结果如下图所示。发现线下GG-Graph+Pruning的方式最有效，delay materialization会略微增加消耗时间，但效率仍然很高。

关于索引创建的时间空间消耗，发现delay materialization降低的效果显著，结果如下图所示。其中时间的减少主要是因为存储读写时间的缩减：