小记：Submodular 函数与社交网络

论 2017 CTST D1T3 的背景

Posted on

Contents

ProblemSolutionBackgroundPostscript

2017 年的 CTST 上有一道看起来有些奇特的题目，当年这道题由于放送事故被整成了错题，导致没有起到任何区分度。我原本也没有太在意这样的一个题目，直到这学期某位老师给我们讲课的时候讲到了一些关于社交网络传播的内容，经过一些思考之后，我发现老师讲的内容里面正好蕴含了上面这道题目的背景。遂（在大半个学期之后）记录之。

#Problem

S={1,2,…,2017} S = \{1, 2, \ldots, 2017\}，f:2S→[0,+∞)f: 2^S \to [0, +\infty) 满足

  1. f(∅)=0f(\emptyset) = 0

  2. ∀ A,B⊆S\forall\ A, B \subseteq S, f(A∪B)+f(A∩B)≤f(A)+f(B)f(A \cup B) + f(A\cap B) \leq f(A) + f(B)

  3. A⊂B⊂S⟹f(A)≤f(B)A \subset B \subset S \Longrightarrow f(A) \leq f(B)

  4. ∀k,j∈S\forall k, j \in S,

    f({1,2,…,k})≥f({1,2,…,k−1}∪{j})f(\{1, 2, \ldots, k\}) \geq f(\{1, 2, \ldots, k - 1\} \cup\{j\})

    求证对任意 SS 的三元子集 TT,

    f(T)≤2719f({1,2,3})f(T) \leq \frac{27}{19}f(\{1, 2, 3\})

#Solution

∀ a,b,c∈S\forall\ a, b, c \in S,

f(a,b,c)≤f(a)+f(b)+f(c)≤3f(1)53f(a,b,c)≤f(a,b,c)+2f(1)≤f(1,a,b,c)+2f(1)≤f(1,a)+f(1,b)+f(1,c)≤3f(1,2)199f(a,b,c)≤f(a,b,c)+2f(1,2)≤f(1,2,a,b,c)+2f(1,2)≤f(1,2,a)+f(1,2,b)+f(1,2,c)≤3f(1,2,3)\begin{aligned} f(a, b, c) &\leq f(a) + f(b) + f(c) \\ &\leq 3f(1) \\ \frac53 f(a, b, c) & \leq f(a, b, c) + 2f(1)\\ &\leq f(1, a, b, c) + 2f(1)\\ & \leq f(1, a) + f(1, b) + f(1, c) \\ & \leq 3f(1, 2) \\ \frac{19}9 f(a, b, c) &\leq f(a, b, c) + 2f(1, 2)\\ &\leq f(1, 2, a, b, c) + 2f(1, 2) \\ &\leq f(1, 2, a) + f(1, 2, b) + f(1, 2, c)\\ &\leq 3f(1, 2, 3) \end{aligned}

Q.E.D

PS: 从解答来看，这题作为 TST P3 也太水了。而由于当年的放送事故，也不知道这个题目的实际难度如何。

#Background

道理我懂，可是这个题和社交网络有什么关系？

这还要从老师所提出的一个问题讲起：如果我们希望在社交网络上传播一个信息，但是我们资源有限，只能把这个消息交给社交网络中的 kk 个人，然后让这些人来传播消息。我们应该如何做才能让这个消息在 TT 时间内能够传播给最多的人。

首先为了描述社交网络中信息的传播，我们要对这件事情建立起适当的模型。这里我们选择用加权有向图来进行建模：

我们用有向图 GG 来表示一个社交网络，GG 的节点表示社交网络中的人。两个节点 x,yx, y 之间可能连有有向边 vv，这条边带有一个权重 w(v)w(v) ，表示当 uu 持有这条消息时，在下一个时刻将这个消息传播给 vv 的概率。

为了方便描述，对于任何一个顶点的子集 VV，我们用一个随机集合 St(V)\mathcal{S}_t(V) 表示时间 tt 后传播的顶点的集合。于是问题变成了，求

arg max⁡V:∣V∣=kE(ST(V))\argmax_{V: |V| = k} \mathbb{E}(\mathcal{S}_T(V))

为了研究这个问题，我们转而研究函数 f(V)=E(ST(V)) f(V) = \mathbb{E}(\mathcal{S}_T(V)) 的性质。显然，下面几条性质是显然被满足的：

  1. f(∅)=0f(\emptyset) = 0
  2. A⊂B⊂S⟹f(A)≤f(B)A \subset B \subset S \Longrightarrow f(A) \leq f(B)

而另外一条性质看起来也很有嫌疑：

  1. ∀ A,B⊆S\forall\ A, B \subseteq S, f(A∪B)+f(A∩B)≤f(A)+f(B)f(A \cup B) + f(A\cap B) \leq f(A) + f(B)

如果你对于这条性质的成立感到怀疑的话，我们可以先把这个式子变形一下来看一下它到底是什么意思：

记 X=AX = A, Y=A∩BY = A\cap B, C=B\AC = B \backslash A，那么上面的性质等价于

X⊆Y⟹f(X∪C)−f(X)≤f(Y∪C)−f(Y)X \subseteq Y \Longrightarrow f(X \cup C) - f(X) \leq f(Y\cup C) - f(Y)

这个式子，从某种意义上来说，表示的是 “边界效应递减”。也就是说，当目前已经拥有的资源越多的时候，获得一个新的资源所带来的收益就越小。当把这个效应带入到我们目前的模型当中来的时候，可以发现，这样的效应是很符合我们的期望的 —— 已经知道这个消息的人越多，新加入一个人所带来的收益就越小。

当然这一点是需要严格的数学证明的， 但是对于我们当前的模型来说，这个证明是容易的，因而留给读者。我们更关心的是这样一个性质能够带来什么。在此之前，我们需要阐明一下我们的标题：submodular 函数（次模函数）就是指满足上面这个式子的函数。而如果再加上性质1， 2 的话，这个函数就被称为 “非负单调 submodular 函数”。有了这个拗口的名词之后，我们的问题可以简化为：如何求一个非负单调 submodular 函数在集合元素个数一定时候的最大值？

遗憾的是，这个问题没有有效的算法来解决，因为它是 NP-complete 的。证明留给读者。提示：取一个特例，将这个问题转化为 Set cover problem，而这是一个著名的 NP-complete 问题。

既然没法精确地解决，我们可以考虑使用万能的贪心算法：从 V=∅V = \emptyset开始，我们每次选取一个 w∉Vw \not \in V 的 ww，使得 f(V∪w)f(V\cup w) 最大，直到有 kk 个元素未知。记这样得到的集合为 VgreedyV_{greedy}，不妨记 Vgreedy={1,2,…,k}V_{greedy} = \{1, 2, \ldots, k\}，那么就有 ∀ r∈Vgreedy,j∈V(G)\forall\ r \in V_{greedy}, j\in V(G)：

f({1,2,…,r})≥f({1,2,…,r−1}∪{j})f(\{1, 2, \ldots, r\}) \geq f(\{1, 2, \ldots, r - 1\} \cup\{j\})

现在我们已经离那道 CTST 题目很接近了。首先我们将那道 CTST 题目推广一下，我们把 3 改成 kk，把 2719\frac{27}{19}改成 kkkk−(k−1)k−1\frac{k^k}{k^k - (k - 1)^{k - 1}}，用完全相同的手法不难证明命题仍然成立。那么根据题目的结论，我们就有，对于任何一个 kk 元集 VV：

f(Vgreedy)≤kkkk−(k−1)k−1f(V) f(V_{greedy}) \leq \frac{k^k}{k^k - (k - 1)^{k - 1}} f(V)

注意到 kkkk−(k−1)k−1≤ee−1≈1.582\frac{k^k}{k^k - (k - 1)^{k - 1}} \leq \frac{e}{e - 1} \approx 1.582，这也就是说，相比起最佳策略，贪心策略不会坏到哪里去：最好的策略也不可能比它更好 0.60.6 倍。

#Postscript

鸽了大半个学期，终于期末把这玩意写了，有点奇妙。