1. Consider the network depicted in Figure 1; suppose that each node starts with the behavior B, and each node has a threshold of q = 1/2 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 greater than 1 - q = 1/2 in the part of the graph outside S that blocks behavior A from spreading to all nodes, starting from S, at threshold q.

Figure 1: Starting from nodes e and f, the new behavior A fails to spread to the entire graph.

2. Consider the model from Chapter 19 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.

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?

Figure 19.28: Starting from nodes c and d, the new behavior A fails to spread to the entire graph.

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.

4. Consider the model from Chapter 19 for the diffusion of a new behavior through a social network.

Suppose that initially everyone is using behavior B in the social network in Fig- ure 19.30, and then a new behavior A is introduced. This behavior has a threshold of q = 1/2: any node will switch to A if at least 1/2 of its neighbors are using it.

(a) Find a set of three nodes in the network with the property that if they act as the three initial adopters of A, then it will spread to all nodes. (In other words, three nodes who are capable of causing a cascade of adoptions of A.)

(b) Is the set of three nodes you found in (a) the only set of three initial adopters capable of causing a cascade of A, or can you find a different set of three initial adopters who could also cause a cascade of A?

(c) Find three clusters in the network, each of density greater than 1/2, with the property that no node belongs to more than one of these clusters.

(d) How does your answer to (c) help explain why there is no set consisting of only two nodes in the network that would be capable of causing a cascade of adoptions of A? (I.e., only two nodes that could cause the entire network to adopt A.)

Figure 19.29: A social network in which a new behavior is spreading.

6. A group of 20 students living on the third and fourth floors of a college dorm like to play on-line games. When a new game appears on campus, each of these students needs to decide whether to join, by registering, creating a player account, and taking a few other steps necessary in order to start playing.

When a student evaluates whether to join a new on-line game, she bases her decision on how many of her friends in this group are involved in the game as well. (Not all pairs of people in this 20-person group are friends, and it is more important whether your friends are playing than whether many people in the group overall are playing.)

To make the story concrete, let's suppose that each game goes through the following "life cycle" within this group of students:

(a) The game has some initial players in the group, who have discovered it and are already involved in it.

(b) Each other student outside this set of initial players is willing to join the game if at least half of her friends in the group are playing it.

(c) Rule (b) is applied repeatedly over time, as in our model from Chapter 19 for the diffusion of a new behavior through a social network.

Suppose that in this group of 20 students, 10 live on the third floor of the dorm and 10 live on the fourth floor. Suppose that each student in this group has two friends on their own floor, and one friend on the other floor. Now, a new game appears, and five students all living on the fourth floor each begin playing it.

The question is: if the other students use the rule above to evaluate whether to join the game, will this new game eventually be adopted by all 20 students in the group? There are three possible answers to this question: yes, no, or there is not information in the set-up of the question to be able to tell. Say which answer you think is correct, and explain.

7. Some friends of yours have gone to work at a large on-line game company, and they're hoping to draw on your understanding of networks to help them better understand the user population in one of their games.

Each character in the game chooses a series of quests to go on, generally as part of a group of characters who work together on them; there are many options for quests to choose from, but once a character goes on a quest with a group, it can generally last for a couple of weeks.

Your friends working at the game company have also mapped the social network of the game, and they've invented what they find is a useful way of classifying each player's friends: a reinforced friend is one with whom the player has at least one other friend in common, and an unreinforced friend is one with whom the player has no other friends in common. For example, the figure below shows the friends of a player A: players B, C, and D would count as reinforced friends, while player E would be an unreinforced friend.

Now, your friends are particularly interested in what causes players to choose partic- ular quests instead of others; and they are also interested in how players learn about particular methods of cheating along the way - general tricks outside the rules of the game that make it easier to accumulate points, usually regardless of which particular quest they're on. To do some market research on this, they've anonymously surveyed players of the game, asking them two questions:

(a) How did you first learn about the current quest that you're taking part in?
(b) How have you learned about ways of cheating in the game?

To their surprise, the answers to these questions were quite different. For (a), 80% of respondents said that they first found out about the current quest they're on from

Figure 19.31: A small portion of the social network in an online game.

a reinforced friend, while for (b), 60% of respondents said that they found out about ways of cheating from an unreinforced friend.

Your friends thought you might be able to shed some light on these findings. Why did the answers to these two questions turn out differently? Is the difference specific to this particular game, or could it be predicted from general principles of social networks? In 1-2 paragraphs, describe how particular ideas from the book can shed light on why the answers to these questions turned out the way they did.

Text Book: Networks, Crowds, and Markets: Reasoning About a Highly Connected World By David Easley and Jon Kleinberg.