Okay so now, degrees in Preferential Attachment.
Let's figure out the degree distribution. We can do the same kind of calculation we
did before. Which are the nodes with degree less than
35 at some time. Well, we just solve for this curve.
Which are the ones that has the degree exactly 35.
It's going to be all the ones that are younger than that.
So born after that time period, whatever that time was.
And then we can figure what's the fraction that have that?
So we'll be able to figure out our distribution function Fof d, the same
technique we used before. But now with just a slightly different
equation that we're using to solve that same system.
So remember you're degree at time t is m times t over i to the half.
So the nodes with degree less than 35, are going to be the ones for which this
function is less than 35. So 35, has to be bigger than our m here
is 20, t equals 100. So, if you solve that out, and solve that
for i, you get that i has to be bigger than 32.7.
So now, this is 32.7 as opposed to the 42 something that we had before.
So, what's the fraction that have degree less than 35 at this time.
Well, it's going to be 100 minus 32.7 over 100, and then we can solve that out.
[BLANK_AUDIO] Right, so so roughly something like 68% of the nodes are
going to have that property. so when we look at this, just solving it,
generically. Again we've got this equation.
the ones that have degree less than d are going to be the ones where this, equation
is less than d. And therefore these are the i's that are
greater than t times m squared over d squared.
And now then to solve for f this, right, so we've got the, the fraction these are
the i's beyond some level. So going back we're want to find the,
what's the fraction of i's above some degree d.
Well we're just going to take the t minus these i's over t, that'll give us the F,
right. So F is just t minus this compared to t,
which works out to be 1 minus m squared over d squared.
So we have a very simple equation for the degree distribution.
So our degree distribution looks like 1 minus m over d squared.
And if you take the derivative of that and look at what's the density function
for the distribution generated by preferential attachment.
It's 2m squared over d cubed. So, this is proportional to d to the
minus 3, right? So, we've got 2m squared, so this is our
constant, times d to the minus 3. So, now we have a power law, we have
exactly something which looks like a power law.
And indeed when we take logs of each side we get the log of f of d looks like log
of 2m squared minus 3 log of d. So we've got a nice linear equation in,
in log, log plots. Which is exactly the, power law that we
were looking for. And in particular here, one thing that's
sort of interesting, when you look at the coefficient that came out, it's exactly
3. so why 3?
well, that came from the fact that the change in degree, over time had a 2 in
the denominator. And then when we do integration and so
forth we came out with a 3. but basically that's, is, is coming from
the fact that there's a certain number of links present in this society.
And if you want to vary this, you can actually produce different variations on
this coefficient. And the way that you can produce
different variations on this coefficient is just having the number of links being
formed at any point in time. either grow or shrink over time.
So you can have the population, the number of newborn nodes not be a constant
one per period but changing over time. And that'll allow you to control this,
this variable here. So, so a slightly richer variation of
Preferential Attachment can adjust that. There's actually an exercise in the book
I wrote that shows you how to do that. But basically the idea here is that you
can get different variations here by just changing the rate at which the system
grows. But the important thing is that the fact
that the older nodes are gaining, things that are richer, faster and faster time,
meant that, that we end up wth these fat tails and power law.
Okay, so we've, we've gone through a couple of different growing systems.
What we'll do next is try and enrich this a little bit more to span between these
sort of uniform at random and Preferential Attachment, and then that
will allow us to actually take these degree distributions.
And take them to data, and see which ones actually match the data.
So which is, is the actual Preferential Attachment a good match for the, for the
world wide web data? does, which ones match the romance
networks etcetera. So can we find variations on these models
that actually match the observed data.