影响力最大化与关键传播者

“谁最能促进传播”有两种不同问法：单个节点作为种子能传多远（关键传播者识别），以及选一组 $K$ 个种子使总传播范围最大（影响力最大化）。前者是排序问题，后者是组合优化问题——一组最好的种子不等于单个最好的 $K$ 个节点。

单个节点：中心性指标

• 度：最直观，但两个度相同的节点可能一个在核心、一个在边缘。
• k-壳（k-核）分解：反复删除度小于 $k$ 的节点，节点被删除时所处的层次为其核数 $k_s$。Kitsak 等（2010，Nature Physics）在多个真实网络上发现，单个种子的 SIR 传播范围更取决于它所在的 k-壳层，而不是度或介数：位于边缘的枢纽往往传播得并不远。
• 扩散中心性（diffusion centrality，Banerjee 等 2013 在小额信贷扩散研究中提出）：$DC=\left[\sum_{t=1}^{T}(qA)^t\right]\mathbf 1$，统计在 $T$ 步内、每步以概率 $q$ 传递的信息从该节点出发的期望到达次数。$T=1$ 时退化为度（乘以 $q$）；$T\to\infty$ 且 $q$ 大于 $1/\Lambda_{\max}$ 时其排序趋近特征向量中心性；$q$ 小于 $1/\Lambda_{\max}$ 时与 Katz 中心性相关。它把“传播能走几步”显式放入中心性中。Banerjee 等发现，最初获知小额信贷信息的村民的扩散中心性能预测各村最终的参与率。
• 动力学敏感的指标：最优的单节点排序依赖传播强度。远低于阈值时只有直接邻居重要（度最好）；接近阈值时传播能走很远，特征向量类指标（或非回溯中心性）更好；远高于阈值时几乎所有种子都能引发大暴发，排序意义下降。

一组种子：子模性与贪心算法

记 $\sigma(S)$ 为种子集合 $S$ 的期望传播范围。Kempe、Kleinberg 与 Tardos（2003）证明，在独立级联与线性阈值模型下 $\sigma$ 满足：

• 单调性：$S\subseteq S'\Rightarrow\sigma(S)\le\sigma(S')$；
• 子模性（边际收益递减）：对 $S\subseteq S'$ 和任意 $v$，$\sigma(S\cup\{v\})-\sigma(S)\ge\sigma(S'\cup\{v\})-\sigma(S')$。

直观理由：把每条边“通/不通”的随机性预先抽好（活边图），$\sigma(S)$ 就是 $S$ 能到达的节点数的期望，而“集合覆盖”函数天然是子模的。由 Nemhauser–Wolsey–Fisher 定理，每步加入边际增益最大的节点的贪心算法满足 $\sigma(S_{\text{greedy}})\ge(1-1/e)\,\sigma(S^*)$。实际计算中 $\sigma$ 要用蒙特卡洛估计，代价很高；利用子模性的“懒惰评估”（只重算堆顶候选的边际增益，常称 CELF）可以大幅加速。

集体影响（collective influence，Morone 与 Makse 2015）从渗流角度处理同一问题：找最少的节点使其删除后巨分支消失（对应免疫），或使其激活后传遍全网（对应影响）。在局部树状近似下，问题化为非回溯矩阵谱半径的最小化，得到启发式指标

$$CI_\ell(i)=(k_i-1)\sum_{j\in\partial\mathrm{Ball}(i,\ell)}(k_j-1),$$

$\partial\mathrm{Ball}(i,\ell)$ 是与 $i$ 距离恰为 $\ell$ 的节点集合。算法每次删除 CI 最大的节点并更新。他们发现最优影响者集合比以往启发式中心性给出的小得多，其中包含许多被忽视的低度节点——它们本身度不高，但被层层枢纽包围。

代码示例“影响力最大化”构造了一个由稠密大社团（枢纽都在其中）和 7 个小社团组成、社团间只有极少桥的网络：按度、k-核或 CI 取前 10 名，种子全部挤在大社团中，期望传播范围（约 590）甚至不如随机选种（约 716）；贪心算法把种子分散到各社团，传播范围约 840（代码）。