## Description

Question

11 Add a supernode to the anonymized personal Facebook network, described with Personal-May8-

12 Anonymous.gephi, which could be downloaded from Connex → Resource, so that the supernode

13 has a connection to any other node in the network. Treat this network as an undirected network.

14 Assume that you want to promote a product in the network and you have a budget to change

15 x number of nodes in the network to adopt the product (e.g., by giving out the product for free).

16 Assume that the threshold for diffusion is q across the whole network.

17 1. (50%, 50%) Design and implement a brute-force-search algorithm to test whether or not the

18 budget is enough to cause a complete cascade. (Input of the algorithm: the values of x and

19 q, output of the algorithm: a set of initial adopters if the budget is feasible, or no solution

20 if the budget is impossible to cause a complet cascade). If q = 0.2, what is the minimum

21 budget required for a complete cascade? If q = 0.6, what is the minimum budget required for

22 a complete cascade?

23 2. (50%, 40%) It is clear that brute-force-search algorithm is not scalable. Design and implement

24 a heuristic algorithm to provide an approximate solution to the above problem.

25 3. (0%, 10%) Run your heuristic algorithm multiple times. For each run, replace some of your

26 heuristically-selected initial adopters with randomly selected nodes. Will this randomization

27 improve the algorithm w.r.t. the chance of returning a correct answer?

1