2.6: Random Networks

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.

Social and Economic Networks: Models and Analysis

Познакомьтесь с преподавателями

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.