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.
