Hello again. So we're back and now we're going to start talking about network formation in more detail. And we'll start by talking about random network formation. And, just to sort of summarize where we've been and, and where we're going to put this in all in a little bit of perspective. We've, we've talked, a bit about the prevalence of networks you know, that their important in many context, but, even though their very complex they have particular characteristics that we can measure and talk about small average path length, high clustering, degree distributions they have different shapes. things like homophily we talked, we haven't really talked about assortativity but that's something which, will come up at some points which, which actually means that higher degree nodes tend to be connected to other high degree nodes. We'll see that in some of the models that we come up with. we've talked about a variety of centrality influenced prestige measures. this, you know, there, there's always room for study of methods. Which are the right methods? Which are the wrong methods? How should we be really measuring and, and keeping track of net, networks. So that more or less took us through the first part of the course. So, gave us some idea of backgrounds and fundamentals. Definitions and so forth to work with and now what we're doing is starting to look in more detail at network formation. And we started by asking, you know, some of these questions in the context before measuring path link and so forth we looked at the Erdős–Rényi random networks. And here what we're going to do is break things into two different a, approaches. One is sort of random network models that'll be akin and, and enrichments of Erdős–Rényikinds of models. And the other will be strategic network models where instead of things, links happening at random what'll happen is we'll have nodes actually choosing the links they're going to form. And they'll choose them to, to benefit themselves. These will be game theoretic kinds of models of self interested individuals forming relationships and seeing how that impacts network formation. So that's the, the main part of the course that we're transitioning into now. And when we start to think about the kinds of, of things that that we want to be asking, and we're asking which networks form. We'll get two different kinds of answers here. Okay, so we've got the random graph models are going to tell us a little bit about how. And the idea here is that, they give us a process. And if we want to understand, you know, why random networks have short average path length and we understand that there's a tree structure underneath them and that structure helps explain how it's easy to reach from any other node to any other node in a relatively short number of hops. the economic or game theoretic kind of strategic models will answer why. Okay. It might tell us why would we see a stree, a tree structure. Not the fact that a tree structure does give you this property. But why would we end up havening these kinds of shorter paths. And more generally, we're going to want to keep track of, of how these things depend on context. And so what we're going to do is we're going to take these things, in turn. We'll start with, looking at random graph models in more detail. Then we'll come back to some economic and game theoretic models, and we'll also talk about some hybrid models. Okay. So, in terms of the static random network models. why do we want to start with those? for two reasons. One is that they'll going to be a very useful benchmark. And again I've sort of emphasized this a little bit before but I wanted to repeat it. by, by looking at what would happen if things were just happening purely at random then we can look at what we do observe and differentiate that from what happens at random. or get some understanding of what, why it has similar features to what happens at random. So these benchmarks will tell us, you know, what component structures do we expect to see at random? What kind of diameters do we see at random? What kind of degree distributions do we see at random? What kind of clustering might we see at random? And so the, comparing things back to those uniform at random models will allow us to, to do some comparisons. Also, this'll give us some basic ideas of tools and properties and, and how these kinds of things are worked with, and how we might be able to work with them more generally. Okay, so what we're going to start with is the Erdős–Rényi random networks and, and look at their properties in a little more detail. and again if you remember these networks, these were the GMP model, or basically we've got n nodes and each nook as a probability p of forming and the degree of distribution in that kind of network was a binomial, which is well approximated by a poisson distribution for large and relatively small p. so again, when we're dealing with these kinds of networks, part of the challenge is that every network actually has some probability of forming. And so how do you make sense of that? What we do is begin to prove theorems for large networks. So if n is large then with a probability close to one certain kinds of things are going to be true. Now in the way in which people begin to specify what might be true or what might not be true is by specifying what are known as properties. So in order to make this precise, let, let me just bring in a little bit of notation. So let's let G of N denote all the possible networks that could be put on a, a set N of nodes, okay, all undirected so we just have this B01 relationships either there or not and no direction to it, no weights and then a property is just going to be a subset of, of networks. So a n is a subset of g n. It just specifies, here's the, the networks that have the property the ones not in a n don't have the property, so it's just a list of, here are the networks that have a particular feature that we might be interested in. So just in terms of examples if you want to have the property that network has no isolated nodes then the property is just represented by saying, it's all the networks such that the neighbouhood of every node is nonempty. So evey node has a nonempty neigbourhood. That's a property. another property would be that the network is connected. so for instance that the path link between i and j is finite for all pairs of, of nodes. we could also have a property that the average path length is less than log n. the, the diameter is less than, log n. So that would be another property. Okay? So each one of these is a, is just specified in terms of here are the networks that have this, here are the networks that don't. That's, that's the mathmatical way of representing a property of a network. now an important class of properties are what known, what, what is known as monotone properties. And so what is a monotone property? A monotone property is one such that if some network satisfies that property and we add extra links. So, we just increase the links in a network so that g is a subset of the links in g prime, then g prime also satisfies the property. Okay? So it just means adding extra things satisfies, keeps us satisfying a property. you can go back and check every one of the properties we just talked about. is a monotone property, okay. Now something that wouldn't be a monotone property would be something like saying that there's an even number of links, right. So if I add an extra link, now it turns odd, it's no longer satisfying the property. So there could be somethings such aren't going to be monotone. But a lot of the properties you might be interested in so You know, it being connected. Well if I had more links it's still connected. so, you know, not having isolated nodes if I add more links it doesn't have isolated nodes. So that, that's a monotone property. That the path length is shorter than a certain amount. If I add extra lengths it still has a shorter path length. So these are nice properties that will be easier to work with. they don't sort of blink on and off, as we change the, the blink pattern. Okay, so what we'll be interested in then is limiting properties. So one way to, to keep track of these things is then to talk about large n, and then, so we can, for instance look at a sequence of, of Erdos-Renyi Poisson, or GNP random graphs, and then have some probability, and then talk about what happens as a function of the size of the graph. So this is one way of representing properties, and now we can take a look at some of those properties, and understand what might be true or, or not true, of those. So when do we have these things, and when don't we? And just to preview ideas, one of the really nice things about the Erdos-Renyi setting and the GNP graphs, and part of the reason I think their work was so well known is that there are very sharp thresholds for which properties do or don't, are, aren't satisfied. So if we talk about how much does the average degree have to be, the average degree, if it's above some level, then a property will be sure, almost surely true as, as you get to large n, and if it's, i-, i-, if the degree is smaller than a certain level, it might not be true. And so the idea here is that, that we'll have, nice thresholds which will sharply distinguish, when are properties true and when are properties not true, so we'll take a look at that next.
