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