Hello. As we have seen before, the degree of a node in an undirected graph is the number of neighbors that it has. But sometimes we're not interested in the particular degree of a specific node. We're interested in seeing how the degrees of all the nodes are distributed across the whole network. And so for example, here in this network we see that many of the notes have degree two, some have degree three and only one of them has degree four and one has degree one. And so sometimes you like to see how these are distributed over the network. And when we do, we look at the networks degree distribution, which is the probability distribution of the degrees over the entire network. And so if we let P of K, where K is the degree distribution of this network, we'll find that P of k has the following values. P of one would be one or nine because only one node node has degree one out of all nine nodes. P of two will be four over nine because there are four nodes that have degree two over the nine nodes. And then P of three is three over nine or one third because three nodes have degree three. We can plot the degree distribution of a network using network acts in the following way. First we use the function degrees, which returns a dictionary where the keys are nodes and the values are the degree of the ndes. And then we construct a list of sort of degrees. So this would just have the degrees of all the nodes in the network in a sorted list. And then we construct a histogram that tells us how many notes of a particular degree we have. And then we can just plot a bar plot of these histogram. And so if we do that for this network, this is what that hissed a gram looks like. So we see that as we had seen before, most of the nodes have degree two, then some of them have degree three and very few of them have degrees one and four. And this allows us to see how these degrees are distributed over the network. Now, sometimes we're working with directed graphs instead of undirected graphs. And then in that case we would be interested in the in-degree or the out-degree of the nodes. And so usually we look at the in-degree. And in this case, if we look at the in-degrees, this is how they're distributed. And if we look at the in-degree distribution, say PN of K that degree distribution would have these values. So we have Pin of zero it's two or nine because two notes have degree zero. P in of one is four or nine because four of the notes have in degree one and so on. And we can also visualize the in degree distribution in the same way that we did for the degree distribution and the undirected graph. But now we use the in-degree function rather than the degree function and everything else is the same. And we can visualize the in-degree distribution of this network. So one interesting question to ask is what does the degree distribution look like for real networks? And so let me show you three examples. Here are the degree distributions of three different networks. And let me tell you what the networks are. So network A is a network of two hundred and twenty five thousand actors connected when they appear in a movie together. B is a network of the World Wide Web. So It has about three hundred and twenty five thousand documents that are connected by you URLs. And then see as a network of the U Power Grid. So it's a network of about five thousand generators connected by transmission lines. And so there are two things to notice about these degree distributions. The first thing is that they're all in log scale, meaning that the X axis and the Y axis are both on a log scale rather than linear scale. And then the second thing to notice is that for at least part of these distributions, they tend to look like straight lines for all three cases. And so when you put those two things together, when you have a degree distribution on a log log scale and it looks kind of straight line, then we say that this degree distribution is looks kind of power law. A power law degree distribution would have the form P of K equals C times K to the negative alpha. Where CN alpha constant and the alpha values for these three distributions that we have here are 2.34 A 2.1 for B and 4 C. Okay, these details are not so important, at least for this course. But the thing to know about power law degree distributions is that they tend to have most of the nodes with very small degree. But you have a few nodes that accumulate a very large degree. So for example, if we look at the degree distribution for a network A we have that most actors have a very small degree. So they've appeared in movies with a very small number of other actors. But a few actors actually appear in a movie with many, many actors. Some appear in at least one movie with almost one thousand actors. So you can notice that when you look at this degree distribution, these actors have accumulated a degree that's very large. Almost one thousand. Whereas most actors actually have a very small degree. And that's typical of power law degree distributions. So one of the things we try to ask when we see something like this is, what could explain this property that we observed happening in many different networks? And the way we try to answer this question is by coming up with models that generate networks that make a few assumptions about how these networks get formed and then they give rise to whatever properties we observed. So in this case the question would be can we come up with a model that generates a network that has power law like degree distribution? One of the models that achieves this property is called a preferential attachment model. And so let me tell you how the preferential attachment model works. First we started with just two nodes that are connected by an edge. And then at each time step we're going to add a new node and the new node is going to connect to a single existing node. And so the sort of special sauce in the model comes when you decide which note to pick out of the existing nodes. And so the way that this new node is going to pick an existing node to attach to it's going to choose it at random but it's going to choose it with probability proportional to the nodes current degree. So the probability of connecting to a node u that has degree Ku is going to be Ku divided by the sum of all the degrees of all the other nodes. So let's run an example of this model. Again, we started with these two notes connected by an edge. And then at each time step we're going to add a new node. So note three is going to come in and it's going to attach to a single node either node one and node two. But it's going to do so with probability proportional to their degree. Well right now node one and two both have degree of one. So the probability of choosing one and two is fifty fifty for node three. And so let's say he chooses note two. Now node four comes in, but now node two has degree of two and nodes one and three have degree one. And so the probability of attaching to node two is point five and the probability of attaching to node one or three is point two five. And so node four attaches to node three, which, it had a lower probability that could happen. So it attaches to node three. Now, node five comes in and we have to re compute all the probabilities. Well now nodes two and three both have degree two and nodes one and four have degree one. So notes two and three are going to have a higher probability of attaching and so that's 0.334, nodes two and three and 30.174, nodes one and four. And so let's say five attaches to node two. And we continue this node six again, we compute the probabilities. Node two has the highest degree. So we will have the highest probability of getting that new attachment. And so six let's say attaches to two. Now seven comes in. We re compute the probabilities. Again, now node two has an even higher degree, so it hasn't even higher probability of getting that new node. Second is node three that has a degree of two with probability of getting that new note edge at a point to and seven attaches to two. Node eight comes in. We re compute the probabilities. Node two probability becomes even larger, but this note eight attaches to node three and so on. You can see how this continues. And the thing to notice here is that as node two started to get larger and larger degree, its probability of getting a new edge became larger and larger as well. So there is this sort of rich get richer phenomenon, where as the nodes get larger, get larger and larger degree they also start to become more likely to increase their degree. And so what we can prove about this particular mechanism is that it gives rise to a power law. It approaches a power law as the number of notes gets larger. And so it matches the kind of degree distribution that we see in this real networks. And so this type of modeling technique allows us to explain or at least have some hypothesis for what kind of mechanism could given rise to this shape of the distribution that we observed. And so for example, if we believe that a very popular actor that has appeared with many other actors in movies has a higher likelihood of getting an additional actor to co appeared in a movie than a maybe less popular actor that has not appeared with many other actors in movies. Then this is the kind of mechanism that could be explaining the sort of very skewed power law distribution that we observed. In network X you can use the function Barabbas Albert graph which is named after the researchers that came up with this model with input primers. And then M, where N is the number of nodes and M is the number of new nodes that an arriving node would attach to. In our example the way we define it. This M prime would be one because we said that every new node would attach to only a single existing node. But you can generalize this and have it so that every note attaches to M existing nodes. And that M will not change the fact that you still get a power law degree distribution. So you can use this function in network X to create networks that follow these preferential attachment model. And so let's create one here with a million notes and an M. Of one. So every note attaches to a single existing node. And now let's slot the degree distribution. That's in the same way that we did before. Except that now I'm not using a bar plot. I'm using a scatter plot and now I'm setting the scales the wide scale and X scale to be log. So we can see that straight line that gets formed on the log log scale for the degree distribution. And so here it is. We see that it forms the straight line that characterizes the power law degree distribution. So in summary we have the degree distribution of a graph is the probability distribution of the degrees over the entire network. And in many real networks that we see this degree distribution tends to look sort of like a power law. Because it looks sort of like a straight line on a log log scale. And we also discussed that models of networks generation allows us to identify mechanisms that give rise to patterns that we observe in real networks. So in this case we observed that many real networks tend to have this power law digger distribution. And then we covered a model that gives rise to this particular property which allows us to have some insight about the kinds of things that could be given rise to these properties in real networks. And in this case this was the preferential attachment model that produces these networks with power law degree distribution. And in network X you can use this function Barabbas Albert graph to construct networks that have end nodes and where every single node attaches to M existing nodes following the preferential attachment model. And that's all for today. I hope to see you next time.
