大数据传播模型笔记

次模性

传播模型的次模性（Submodularity of propagation models）通常指的是在影响力最大化等传播问题中，影响力函数具有次模性特征。次模性是一种集合函数性质，它类似于“递减增益”的概念，意思是：在已经有较大基础（即已经影响了一部分节点）的情况下，增加一个新节点带来的边际影响会比在较小基础上增加该节点带来的影响要小。

对于传播模型中的次模性，具体可以理解为：

1. 递减增益：当我们增加节点来扩展信息或影响时，新的节点对信息传播范围的边际增益随着已影响节点的增多而减少。例如，影响力最大化问题中的目标是通过选择一个节点集，最大化通过社交网络传播的影响力。如果已经有一大部分节点受到了影响，那么再新增的节点可能带来的增量传播效果会递减。

2. 形式定义：给定一个集合函数 ( f(S) ) ，它是次模的当且仅当对于任意的两个集合 ( S \subseteq T ) 和任意的元素 ( x \notin T )，满足以下条件：
   这表示在更大的集合 ( T ) 中加入 ( x ) 时带来的增益小于或等于在较小集合 ( S ) 中加入 ( x ) 时的增益。

3. 实际意义：在社交网络、病毒传播或信息扩散等模型中，次模性意味着我们可以通过贪心算法来近似求解问题。贪心算法每次选择对当前影响力增益最大的节点，次模性保证了贪心算法可以给出接近最优的解。

传播模型次模性的这种特性，使得在大规模网络中求解影响力最大化问题变得更加高效且有理论保证。

---

本文章使用limfx的vscode插件快速发布