Influence Maximization

影响力传播模型 社交网络上影响力最大化问题需要借助相应的影响力传播模型，影响力传播模型的选择 LC IT模型（独立级联模型和线性阈值模型） WC（权重级联模型） HD（热传播模型） SIR（传染病模型） MIA模型（路径相关） 投票模型 巴斯模型 影响力最大化算法 目前有的几个影响力最大化的算法 基于目标函数的子模性质的算法（一般是贪心算法和贪心算法的改进） A note on maximizing a submodular set function subject to a knapsack constraint 这个文章主要是把问题扩展了，认为选择每个节点是有不同的代价的，而不同于传统的问题，传统的问题中，每个节点的选择大家都是一样的，因此，在总代价一定的情况下，那么问题就是选择固定个数的节点即可，但是如果每个节点的选择代价不一样，在总代价一定的情况下，选择的节点的个数就不一样 Cost-effective outbreak detection in networks （CELF算法） Celf ++ : optimizing the greedy algorithm for influence maximization in social networks（CELF++算法） 这个文章就是大名鼎鼎的CELF算法，利用子模性质和边际效益递减对贪心算法进行优化，同理还有CELF++算法也是大致相同的思路 基于中心性的启发式算法 Efficient influence maximization in social networks W.Chen （DegreeDiscount算法） 这个算法也是启发式算法，主要在于，每当选择一个节点后，认为这个节点不会再被影响，因此，它的邻居节点地度-1 A potential-based node selection strategy for influence max- imization in a social network （TM算法） 这个算法也是一种启发式算法，它是以节点地潜在地影响力作为启发的因素去选择初始的节点，同时设置了一个参数c，分为两个阶段，第一个阶段启发式的选择潜在影响力最大的若干个节点，第二阶段用贪心算法对这些第一阶段选择的种子节点进行筛选，当参数c为0，也就是没有第一阶段，那么算法就变成了传统的贪心算法。算法的缺点也很明显，首先参数c的选择依赖于经验判断，其次是启发式，准确率没有保证，再次也需要使用贪心算法，因此时间复杂度很高 ...

The Independent Cascade Model (IC Model) IC模型，即独立级联模型。 $v$表示图$G=（V,E)$中的一个节点（用户），$v$可以被它的传入邻居（incoming neighbor）以一个影响概率$p_{u,v}$的情况下独立激活。 在时间步为0的时候，给定一个种子集（seed set）$S$,即$k$个已经是激活着的节点。 在时间步$t$时，每一个激活状态的节点$u$将会以一定的概率$p_{u,v}$来激活每一个和它连接的未激活节点$v$。时间步$t$之后，如果$v$依然是未激活状态，那么$v$将无法再次被$v$激活。结束一次上述过程后，$u$保持激活状态并且失去激活其他节点的能力。当网络$G$中没有其他节点可以被激活时，扩散过程结束。 值得注意的是，当$S$是原始的激活节点集，那么上述随机激活过程完成后，所得到的影响分布（Influence Spread）是所期望的激活节点数。 The Linear Threshold Model (LT Model) LT模型，即线性阈值模型。基本思想是，如果一个未被激活的节点有足够的传入邻居是激活状态的，那么该节点可以被激活。 形式上， 在图$G$中每条边$e=(u,v) \in E$有一个权重$b_{u,v}$。 我们定义$\mathcal{N}_I (v)$表示节点$v$的传入节点， 满足$\sum_{u \in \mathcal{N}_I (v)} b_{u,v} \leq 1$, 即所有$v$的传入节点与$v$组成的边的权重只和小于1。 另外，每个节点$v$具有一个阈值$\theta_v$。 LT模型首先为每个节点$v$的阈值$\theta_v$在$[0,1]$上均匀随机采样。在时间步0时，设置$S$中的节点状态为激活，其他节点为未激活，然后迭代的更新每个节点的状态。 在时间步$t$时，所有$t-1$时刻是激活状态的节点依旧保持激活状态，与此同时，其他未激活的节点$v$, 如果任意一个节点$v$的激活传入邻居总权重的值至少为$\theta_v$,那么将$v$激活。 当没有节点将要被激活时，传播结束。