0:00

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.

Â