MKSE150   Homework 5

Answers

Text book exercise 19.8.4
(a) 6,7,11
(b) 4,9,16 is another set.
(c) Remove the edges among 2,6,7,11 to get the clusters.
(d) Because if there are only two initial adopters, then in one of the above clusters there won't be one, which mean nodes in that cluster will never adopt A.

Text book exercise 19.8.5
Yes, we can. Suppose q is the threshold for choosing A. We must have: dqa+d(1-q)x > d(1-q)b + dqx, simplifying this results in q>(b-x)/(a+b-2x).

Text book exercise 19.8.6
No, the game will not be adopted by all students. Because all the early adopters live in fourth floor, therefore no student in the third floor will ever have at least half (here 2) of her friends playing the game, so none of third floor residents will ever join it.

Programming Component

Here is one solution to the programming problem:

	public static Vector<Integer> selectSeedNodes(InfluenceGraph ig, int budget) {
		Vector<Integer> adopters= new Vector<Integer>(budget);
		Set<Integer> nodelist= ig.influentials();
		int trials= 100000/(budget*nodelist.size());
		System.out.println("network size: "+nodelist.size()+"; will use "+trials+" trials");
		for (int iter=0; iter<budget; iter++) {
			int bestNode= 0;
			double bestPerf= -1;
			for (Integer node : nodelist) {
				if (adopters.contains(node)) continue;
				Set<Integer> EA= new HashSet<Integer>(adopters);
				EA.add(node);
				List<Integer> sims= ig.runInfections(EA,trials);
				double perf= mean(sims);
				if (perf>bestPerf) { bestPerf= perf; bestNode= node; }
			}
			//System.out.println("bestPerf="+bestPerf+" node="+bestNode);
			adopters.add(bestNode);
		}
		return adopters;
	}