logistic is not submodular

1 files changed, 16 insertions, 0 deletions

diff --git a/notes/extensions.tex b/notes/extensions.tex
index ef73bf4..78cb336 100644
--- a/notes/extensions.tex
+++ b/notes/extensions.tex
@@ -29,4 +29,20 @@ Therefore, $\mathbb{E}[X_{n+1} | X_n] = A^T X_n$ and $\mathcal{G} = \sum_i A^i
 $\mathbb{E}[X_0X_0^T] = \frac{1}{m} I_m$ and it follows that $$\mathcal{G} =
 \frac{1}{m} \sum_{i=1}^T A^i (A^T)^i$$
 
+\section{Submodularity of Generalized Linear Cascades}
+
+For which link functions is the resulting influence function submodular? We know
+it to be true for the IC and LT model, what about the Logistic cascade model?
+
+The answer is no. If we take the example of three nodes $(A, B, C)$ with the
+possiblity to influence a remaining node D with respective edge weights: $a$,
+$b$, and $c$, then we see that the following equality must be verified:
+$$2\sigma(a+b) \geq \sigma(a+b+c) + \sigma(a)$$
+
+We see that for $a=.5$, $,b=.5$, and $c=1$, the equality is violated.
+Interestingly however is that if we let the scale parameter of the sigmoid go to
+infinity, we recover the LT model which is submodular. In fact, by slowly
+increasing the scale parameter, it becomes harder to find values of $a, b, c$
+which violate the inequality. We therefore have a parameterized function which
+is `close to submodular'.
 \end{document}