[SOUND] In this video I'm going to give you an idea that you might want to explore for your capstone project. You're of course not obligated to use this idea. It's just really to seed your imagination and see if maybe you want to go down this path. So what we're going to talk about in this video is information flow in a social network. So by the end of this video you'll be able to describe how to model information flow and adaptation within a social network. And you'll actually have enough information to write a simulation to simulate that information flow. So, let's get started. And let's talk about what we mean by information flow. So, we're going to focus on the task of making important decisions in this video. So, there are a lot of important decisions that you have to make. Like for example, who to vote for, for President. Or maybe what brand of cereal to buy, all of these things are important decisions in your life. So, this model could be for any of these important decisions. But for the purpose of this video here, in this example, I'm going to focus on one very important decision, which is the decision of which IDE to use. So, throughout this course, in the specialization, we've used Eclipse but that's not the only Java IDE and, in fact, there's a competing Java IDE called NetBeans that's also very popular and we've seen many of you saying that you use this IDE in the forums. So, that's an important decision. How you should decide whether to use Eclipse or NetBeans and, moreover, how does your decision affect the decision of those, of your friends that you're connected to say in a social network. That's what we're going to focus on. So let's take a look at a piece of a social network. So here's a piece of our social network, say Facebook network and let's imagine for the moment that everybody in this network uses Eclipse, so the nodes are colored purple. So right now our network is kind of stable. Nobody has any reason necessarily to decide to use NetBeans. But let's say one day user number 25 comes along and they see the light, and they decide, I'm going to use NetBeans. I no longer use Eclipse for some external reason. So they go ahead and switch to NetBeans. And now a bunch of questions come up. Are others going to also switch to NetBeans, or are they all going to keep using Eclipse? What properties of the networks might affect the switch? And what will be an equilibrium state once maybe a few people switch? So these are all questions we can explore by modeling these decision flows and information flows in this social network. So let's talk about how. We'll introduce, so first of all, before I introduce the formal model, let me just tell you that the choice of whether to switch will depend on a couple of things. One, it will depend on the intrinsic reward, or how good the ultimate choice you made is. So maybe Eclipse is just a better editor than NetBeans, and so it's better to use Eclipse than NetBeans. So that will affect your decision. But it will also affect your decision how many people around you are using which IDE. If all of your friends are using Eclipse, then it's probably to your best interest to keep using Eclipse, because you're going to get some support from them. Conversely, if they're all using NetBeans, then maybe you should switch to NetBeans. So the proportion of your social connections that are using one versus the other is also going to influence your decision. So let's not turn this into a formal model. Let's say that for each node, for each pair of nodes in the graph, V and W. We say that if both V and W, if they're connected and they both use NetBeans then they get some reward A. All right. And if they're connected and they both use eclipse then they got some reward B. And if they use different IDEs, well then they get no reward. We'll just say that you only get a reward if you're using the same IDE as your friends. So now we ask the question of, using this model, when should a person change their behavior? So when should they select NetBeans versus when should they select Eclipse? Let's introduce some more terms. So let's say that p is the fraction of a person's neighbors or friends who are using NetBeans. Then (1-p) is the fraction of their friends that are using Eclipse, because in this world, we'll assume that everybody uses one or the other. Then d is the total number of friends that a person has. So, If we want to weight the benefits of choosing Netbeans against the benefits of staying with Eclipse, we can just write out the reward that you expect to get in each of these situations. So the reward you get for switching to Netbeans is p which is the fraction of your friends that are using Netbeans, times d, the total number of friends that you have times a, which is the intrinsic reward for using NetBeans with both of your friends using it. For staying with Eclipse it's a reward of 1-p, which is the fraction that's using Eclipse times d, your number of friends, times b, the reward for staying with Eclipse. So, with that, we can set up a situation where we can reason that a person should switch to NetBeans if that reward for using NetBeans is greater than the reward for staying with Eclipse, which you see there. So, if p times d times a is greater than (1-p) times d times b. And with a bit of algebra we can rearrange the terms and come up with the inequality you see there at the bottom, which is that we should switch, a person should switch if p > b /(a+b). So if you think that inequality for a minute, it makes sense. Basically you should make the switch if enough of your friends use this other technology that it kind of overcomes the goodness of the technology that you happen to be using already. All right, so let's now look at how this plays out in practice. So, let's look at in this network, again, 25 made the switch for some other reason. It's outside our model, it just decided I am going to use NetBeans. So, 65 now says, well, should I switch to NetBeans? Let's take a look under our model. Well, let's see. P is one third. Because only one of 65's three friends use NetBeans. And b over a plus b is one half. So p is not greater than one half. And so, 65 will not switch. And, in fact, if you look at this network. And we can do this inequality for all the nodes in the network. Nobody is going to be incentivized to switch to NetBeans. So, everybody stays with what they've got. Let's change things just a little bit, let's introduce one additional person who switches to NetBeans and now let's look at how information and decisions propagate through this network. So now does 65 switch? Well p is two thirds now, now two thirds of 65s friends are using net beans. And b over a plus b is still the same, so now two thirds is greater than one third and that will cause 65 to switch. Now we're going to think about this in a kind of generational model where each generation, nodes or people in the network, decide to switch or not. So in this first generation we see that 65 makes the switch. Now the question is, does anybody else switch in this first generation? Does anybody else switch right away? Well if you do out the math you will see that in fact nobody else switches right away. It's only 65 that makes that switch because nobody else has enough of a friends incentive to make that switch. So in that first generation, 65 makes a switch. But now the network looks a little bit different. And we can run this sweep again to see if there are any other nodes in this next generation that are going to switch because now 23 is going to be influenced not only by 25 and 18, but also by 65, who is now using NetBeans. So let's take a look. At if we do out that inequality we will see that 23 now has enough of it's friends influencing it that it will also make the switch to NetBeans. Now we can sit here and ask will anybody else switch? Well no. Because now nobody else has sufficient numbers of friends to overcome the inherent goodness that they feel using eclipse. So we've reached an equilibrium state. Nobody else is going to to switch to using NetBeans. Let's consider now a slightly different version of the problem. So before we had two nodes that were seated using NetBeans and in the very first example we just had one node, 25, that started using NetBeans, and we saw that nobody switched. But that was when the relative weights of NetBeans and Eclipse were relatively the same, they were both equal to one. But let's now make using NetBeans inherently more attractive than using Eclipse. I'm not really saying anything about the values of these two IDE's, I like them both. But let's just imagine that NetBeans is somehow an inherently better IDE. Is this going to now change how information flows through this network? Well let's take a look, ask the question does 65 switch? Well, p is still equal to one third, only one of 65s friends uses net beans. But now when we look at b over a plus b, we see that it's one fourth. All right, so relatively NetBeans is kind of stronger, Eclipse is less strong. So one-third is greater than one-fourth and 65 will make the switch. Does anybody else switch right away? So in that first generation. We want you to look at this network and try to see. All right, so you found out that nobody else was sufficiently motivated to make the switch yet, but now we color 65 blue, and seen the next generation who switches. So does 18 switch this time around? P is equal to one half, 2/4, b over a plus b is equal to 1 over 4, so yes, 18 is going to switch. And if you look at 23, you'll see that 23's actually in the same situation, so both of those nodes will switch in this next generation. There we go, they're both using NetBeans. Now here's where we reached our equilibrium before. What's going to happen now? Is anybody else going to switch under these new conditions? Hopefully you were able to identify that actually both 50 and 44 will make the switch and we can see why here. For 50 p is equal to 1/3. And then, b/(a+b) is equal to, as usual, 1/4. So 50 will switch. 44 is in the same situation, and it will also make the switch. They will both switch to NetBeans, and then in that final iteration we'll see that now 32 is completely surrounded by people using NetBeans, and 32 will also switch its mind and use NetBeans. So here's our new equilibrium state, it looks very different from the equilibrium state before. So that's kind of in a nutshell what this project is going to, what you can do in this area with a capstone project. The basic algorithm I've showed you is essentially run a number of generations, and in each generation, apply this model to figure out which nodes switched their decisions. You make all the changes and then you keep running iterations until there's equilibrium, or until you just don't feel like running anymore generations and you want to examine the network as it is. All of the stuff that I've presented to you, comes from this great book, that you can see here, that Mia has talked to you about before. And it's got a whole bunch more ideas that it can seed you in your exploration of the capstone project. So you might vary which nodes you seed with information, you might bury the values of a and b, you might examine different subgroups with a different network structure, so take sub steps of the Facebook data that we're giving you and see what happens as information flows. You might run a visualization tool. All of these would be great ideas to explore for your Capstone project and we hope that we've given you some ideas for exploration.
