This being said, there are not only uniform distributed networks just like we have the Erdos Renyi networks. There are other ways to even grow networks. So for example, what happened at Erdos Renyi networks that I had talked about now. We had a stable number of nodes, number of nodes were given an n. We threw the number of links in m links. We just threw in uniform distributed over with a certain probability, a stable probability, a node would grow a link. So that's what we had until now. Now, I can also change the number of nodes. I can increase the number of nodes, is another mechanism of growing a network, and I can start that very simply by adding nodes with uniform likelihood. So I would start with a certain number of nodes and a fully-connected network, and then I add new nodes with a certain number of links and these links connect to these existing nodes with uniform likelihood. So for example, imagine there's the cool table in high school and a certain number of people sits on this table, and a new kid comes in, and this new kid during this lunch break can make three connections and these connections then are with uniform likelihood a third with equal probability kind of reaching out to these existing nodes, the kids on the cool table. So and then another one comes in and the same thing happens. Can you say already something about the dynamics for example, over time who will have more nodes? The people who were there first or the people who come in later as a general tendency? Who will accumulate more nodes? Well yeah, the older nodes will have more links because it's uniform likelihood is, there's an equal probability that I would connect to by just random chance. Let's say the five kids that were there first at the cool table they will accumulate more whereas the person who just came in has actually no connection made to him or herself because he just came in. If you've been there before him maybe received if you connections, but on an average the older will have more connects. We can make some predictions about how these kinds of networks evolve. Now, these connections don't have to be with uniform likelihood and actually in reality it almost never happens with uniform likelihood. Because what we find in reality if we look at social networks particularly but that also happens in other networks, neural network, or infrastructure networks. That some nodes have many more links than others. Actually what we you often find is that exponentially few nodes have exponentially many connections, and exponentially many nodes if exponentially few. So there are many nodes, really many that have done like one or two connections only and they have few nodes who have a lot of connection. So and that's often called the fat tail distribution. It's a power law that's the technical term of this statistical distribution. Now, the mechanism how you create such an unequal power load distribution that's a really skewed distribution income. For example, income in our society is also distributed according to the same effect. They have exponentially few people in society that have exponentially much income, a lot of income, and exponentially many people in society that have exponentially little income so that's also power law called the Pareto distribution, if you have economics you might have heard of it. This is the same logic. So how is that created, it's created by preferential attachment in a network. The result is this scale free network, the results are called scale free. Because if you have a power law yes, they are scale free, it doesn't do. If you zoom in and out it has to do with fractals we don't have time to go into that, you can imagine it with fractals that's where the term comes from of a scale-free networks. So it means, independent from the scale that you will get the network, it looks very similar, itself similar. Preferential attachment means that the likelihood that you connect with somebody is proportional to the number of existing degrees. So that means, the person who already has a lot of connections, it's much more likely to receive another connection. There's a preferential attachment to the person with a lot of connections already, and we often see that in reality to go back to my example of the cool table in high school, the most popular kid that's on this cool table has already a lot of connections and you like drawn to this person too. People are drawn to the most popular kid. So the person who has a lot already will get more. Almost like a biblical term, the rich get richer, that's what preferential attachment is and the poor get poorer, so those who have given it and those who have nothing take it away, where you have little take it away. So that's the idea of preferential attachment also called Ewald's rule, and how we can do that more formally, you don't trust your intuition more formally that's what it looks like. If you're like me and you don't trust your intuition, I will walk you quickly through the formalism but if your intuition is fine if you understood that that's also fine right. So there are new nodes. Every new node adds m links, certain number of links to existing nodes. So at time t every time that happens at a timestamp, there will be t times m links. The total number of degrees is t times m times two because there basically two degrees per link, and the probability of touching and attaching to a notice than j. So that's the number of degree divided by two times t times m. So that's the formalism of how you can grow these kind of networks. So let's grow some scale free preferential attachment networks. I start here with two nodes, so there are only two nodes, and Preferential Attachment says that the likelihood that a new node if a new node comes in and a new node comes in and connects, we say now the connection is one then new nodes comes with one link, we just defined could come with two links, but in this case we just defined comes with one link. So there's an equal likelihood it connects to each one of them. Because each one of them is equally likely. So let's do that as throwing a new link or when you connects to that one, and we threw in another link and it connected to the middle one. So what we have now is the middle node and I show you where that by increasing the size a little bit, the middle node now has three connections. So it's three times more likely, it's proportional is three times more likely to get a connection now then the other three that means the other three can still get a new node comes in. Somebody could connect to like an outsider, but with more likelihood it will connect to the one who has the highest connection. So it's proportional, three times could be or there could be another rule of how proportional it is, and we can see here in this graph, this graph is very important. Keep on watching this graph, we can see that there is actually one node with this way goes the number of degrees. So one node with three degrees, and three nodes with only one degree. So on the x-axis is the number of degree. One node with three and three nodes with one. That's how you read this graph. So let's keep on going then and throwing another node, and then connected to an outsider. What I said is still the chance that connects to an outsider, or now it connected again to the main hub we can see there's one outside and actually also, gained some probability of being connected. Now the main app keeps on connecting and keeps on collecting, keeps on accumulating, and gets bigger and bigger and bigger it gets, the rich get richer right. Those who have give them, and that's what actually happens. There too little hubs outside, they also make some friends, they popular and sometimes somebody connects to them. But if you look at the graph actually, what also happens on the graph is that there are many very few nodes who have a lot of degrees, and most nodes actually have only one connection. Most are penance, penance remember there is technical term of you just have one connection to it. So most node actually pendants, there are some other sub hubs smaller hubs that are in there, but they are very few nodes, actually it's one big node, one big hub. One popular kid that actually keeps on accumulating and becomes more popular and more popular and more popular. So at the end of V now if 200 nodes, you see that most of these 200 nodes actually have only one degree, and this one node in the center and has more than 70 degrees. So that's the richest one and actually started with a path dependency. It started right from the beginning when just this node was lucky to receive more nodes, and more connections, and remember the beginning there were only two. Each one of them could have been in and then came a third. Each one of these three could have been a but then at the end is started to set it in a path dependency which then determined this outcome, and that's what often happens in this kind of mechanism. So let's do that again to see, let me start again with our two nodes, add another one we have now here like a hub already that we can see. But we have several hubs, that I see we have one in the middle and then there are some other hubs growing around there. So in this case now, we have one, two, three, four hubs. We rolled the dice and it might have been unlikely that the most popular kid gets the connection, but there's still a probability and that's what happened in this case, and we have several hubs. Now, the average degree distribution look at our graph, is still this power law. So there's still this very much inequality where we have very few it might not be one in this case, might be three, four, five hubs that have a lot of connections over 20, 30, 40 connections maybe, and there are many, most nodes actually we still have one. You can see that in the graph there just penance, and they just have one connection. So you get a different network structure. That's not a random network, is not random and a sense of the uniformly random as their probability and how we connect to them. But we get these hubs, these hubs that actually connect to many, and we have a extremely unequal degree distribution. A degree distribution is a uniform but distributed according to a power-law exponentially few. Exponentially few nodes, here we have a few with exponentially many connections, and exponentially many nodes is our pendants with exponentially few connections. So if you take for you who are interested in and work with logarithms, if you take the logarithms of both, you get the straight line and has the lower graph. You can see here, you get this basically a straight line on a log-log plot between the degree and the number of nodes. So you get a straight line in a log-log plot which is the signature of a power law a scale free distribution. Now for you that are interested why this word scale free is because if you would keep on growing growing this network you will get a very big network. If you look at it you get some hubs, then if you zoom in for example, take one of your favorite sub-clusters here, some of your favorite sub hubs and you zoom in on that, you will see a self-similar structure. Also there will be one big hub with a smaller hub and a smaller hub, and then you zoom in again depending how big your network is, and you will see the same. Some big, some small, also independent from your scale, the network will always look like that, that's why it's called a scale-free and scale-free networks are grown by preferential attachment.
