[SOLVED] CS-7280-O01

10/30/22, 5:19 PM L10: Monotone andtion: Network Science CS-7280-O01
L10: Monotone andon
Now that we know how to optimize, at least approximately, monotone and submodular functions, we can go back to the problem of maximizing network
https://gatech. instructure. com/courses/265324/pages/l10-monotone-and-submodular-function?module_item_id=2520836 1/3

Copyright By Assignmentchef assignmentchef

10/30/22, 5:19 PM L10: Monotone andtion: Network Science CS-7280-O01
diffusion. Suppose that S is one or more initially active nodes, and g(S) is the resulting cascade of active nodes. Is the cascade function g(S) monotone and submodular?
The fact that the cascade size is monotone is obvious: if we increase the number of initially active nodes, we cannot decrease the size of the cascade.
It is also possible to show that the cascade size is a submodular function, for both the Linear Threshold and the Independent Cascade model. Let us focus on the latter here.
With the Independent Cascade model, we can first randomly choose for every edge of the network whether it is live or blocked, based on its activation probability.
The set of live edges for such a specific random assignment can then be used to determine the set of active nodes at the end of the cascade.
The important point is that a node w will be part of the cascade if and only if there is a path of live edges from the initially active node(s) to w.
To prove the submodularity of the cascade size, we need to show that the number of NEW nodes that become active after we add a node v in the set of active nodes is larger for S than for its superset T.
Please refer to the above diagram. S is a subset of T, and g(S) and g(T) are the corresponding sets of active nodes.
There are two cases:
The new nodes that become active after the activation of v are neither in g(S) nor in g(T).
The new active nodes are in g(T) but not in g(S).
Note that it cannot be that the new active nodes are in g(S) but not in g(T).
So, more nodes are activated when v is added to S compared to when v is added
The previous argument holds for the random assignment of live edges we started from.To show that the expected value of the cascade size is also submodular, we need to use the fact that: if a set of functions are submodular, then
https://gatech. instructure. com/courses/265324/pages/l10-monotone-and-submodular-function?module_item_id=2520836 2/3

10/30/22, 5:19 PM L10: Monotone andtion: Network Science CS-7280-O01
any non-negative linear combination of those functions is also submodular (non- negative because the scaling coefficients are probabilities). Recall that this was the food-for-thought question at the previous page.
https://gatech. instructure. com/courses/265324/pages/l10-monotone-and-submodular-function?module_item_id=2520836 3/3

CS: assignmentchef QQ: 1823890830 Email: [email protected]