Consider the model for the diffusion of a new behavior through a social network. Recall that for this we have a network, a behavior B that everyone starts with, and a threshold q for switching to a new behavior A — that is, any node will switch to A if at least a q fraction of its neighbors have adopted A. Consider the network depicted in Figure 19.29; suppose that each node starts with the behavior B, and each node has a threshold of q = 2/5 for switching to behavior A.
(a)Now, let e and f form a two-node set S of initial adopters of behavior A. If other nodes follow the threshold rule for choosing behaviors, which nodes will eventually switch to A? 
(b) Find a cluster of density 1−q = 3/5 in in the part of the graph outside S that blocks behavior A from spreading to all nodes, starting from S, at threshold q. 
(c) Suppose you're allowed to add one node to the set S of initial adopters, which currently consists of e and f. Can you do this in such a way that the new 3-node set causes a cascade at threshold q = 2/5 ? Provide an explanation for your answer, either by giving the name of a third node that can be added, together with an explanation for what will happen, or by explaining why there is no choice for a third node that will work to cause a cascade.

Figure 19.29:

 

Transcribed Image Text:

g h U m - D k f I d n i j Figure 19.29: A social network in which a new behavior is spreading. g h U m - D k f I d n i j Figure 19.29: A social network in which a new behavior is spreading.