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.
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.