1. Consider the grid graph in the below figure. All nodes will be activated according to the Deterministic Linear Threshold model with the threshold function ??(u) =2. That is an inactive node at round ?? will be activated in the round ?? + 1 if and only if it is adjacent to at least 2 active nodes.
![917_Deterministic Linear Threshold model.png](https://secure.tutorsglobe.com/CMSImages/917_Deterministic%20Linear%20Threshold%20model.png)
a) Find the largest number of nodes that can be activated in the end by selecting only one node into the seed set (influence maximization in deterministic threshold with ?? = 1).
b) Find the largest number of nodes that can be activated in the end by selecting two nodes into the seed set (influence maximization in deterministic threshold with ?? = 2).
2. Implement the greedy algorithm for the influence maximization under the independent cascade model. The input is a directed graph ?? = (??, ??) in which each edge (u,v) exists with a probability 0 ≤ puv ≤ 1, and a number ?? ≤ |??| . The output is a seed set of ?? vertices that can be selected to maximize the expected number influenced (activated) nodes in the end. The greedy algorithm selects in each step a node v that maximizes the gain Δ??(v) = ??(?? + {v}) -??(??).
Input: The file "graph.txt" includes multiples lines in which the first line contains three integers n,m, and k that correspond to the number of nodes, the number of edges, and the size of the seed set, respectively. Each of the following m lines contain three numbers u, v, and ??uv separated by spaces, to denote an edge from u to v with a probability of existence ??uv. Nodes are numbered from 1 to n.
The output file "im.txt" contains exactly 2 lines in which the first line contains ?? vertices found by the greedy algorithm and the second line contains the expected number of influenced nodes in the end.