0:00

Okay folks. So our next topic is again taking these growing random network models.

Â Now we've got a version which is fairly

Â rich and spans a whole series of different degree distributions.

Â Let's have a look at some data,

Â see how this work out.

Â And if you recall what we had in terms of the degree distribution

Â was that we ended up with an equation for the degree distribution which looks like this.

Â And what that does is if we - it's easy to do this in the log-log world,

Â take log of each side and well we're actually bring the F over here,

Â then take a log of each side.

Â What we're going to end up with this log of 1 minus the distribution function is

Â proportional to c minus x log d of a plus m times x.

Â Okay. So what's the difficulty with actually fitting this kind of equation?

Â We could just look at,

Â you know, frequency of degrees,

Â regress that off of log of a function of degrees and then try and estimate what the x is.

Â The difficulty is that the x here is

Â entering in both parts so the x is telling us something about the a.

Â So we've got this a coming in in several places right?

Â So a is the parameter we want to estimate how much is uniformly at random.

Â How much is being formed via preferential attachment.

Â The a is entering here.

Â It also enters this x term.

Â So what we've got is we've got c minus two over one minus a log

Â of d plus am two over one minus a, right?

Â So we've got several places where a is entering both here and here.

Â And so what we going to do is,

Â what we'll do is, search over a's.

Â We'll search over a's until we minimize the distance between

Â the degree distribution generated

Â by this particular a and the actual the degree distribution.

Â Okay? So we'll try and select an a to minimize

Â that distance between the actual distribution and the models distribution.

Â So when we search over a's, to do that,

Â and let me say a little bit about how one can

Â search so you can do the the program search by different methods.

Â One is you can just plug in a bunch of different a's and for each one that'll give you

Â a degree distribution and then try and see to what extent the actual data,

Â you know, what's the distance between each frequency distribution in

Â the data and the actual ones here?

Â Sum those up, square them and try and minimize that.

Â Alternatively what you can begin to do is guess an a over here

Â and then do a regression that'll give

Â you an expression here that gives you a new estimate for a,

Â plug it back in here.

Â Regress again, and so forth.

Â You can actually show that that is a contraction.

Â It's a well-behaved mathematical process.

Â It'll converge to the right a. I don't want to go through a proof of that but that's

Â an alternative technique so one is just brute force

Â put down a bunch of a's between zero and one,

Â search over a grid see how each one,

Â how close does it come to matching the data,

Â so you can look at

Â the actual frequency distributions compared to the true frequency distributions.

Â Right? So what we're going to end up with is,

Â so what we've got is true frequencies for each degree,

Â we've got for each a we've got a frequency,

Â we can look at these things, sum them up,

Â square them and say try and choose the a that

Â minimizes the sum of the squared distances between

Â the actual distribution and the one for a and just choose a to minimize this.

Â So for each a we get an expression plug it in.

Â Calculate all those numbers and then minimize that.

Â Or you can do this iterative process where you guess and a,

Â do a regression and get a new x that gives you

Â a new a estimate and iterate and that'll give you another way to do this.

Â Okay. So what do you end up with?

Â Let's look at some plots.

Â So here we've got different datasets.

Â This is one where we're looking at citations of the original Small Worlds paper.

Â And what do you end up with?

Â You end up with a at about 0.56 and

Â the fit of that is about 98% so you're doing very well in terms of

Â actually calculating the variations of

Â the actual variation in

Â the frequency distribution that is matched by this model is about 98%.

Â So there's about a 2% error when you look at the f of d's minus

Â a of d's compared to the overall squares of f of d's.

Â So you're doing very well here.

Â When you look at different ones this is the prison inmates dataset that we looked at,

Â we talked about before McCrae's dataset.

Â Here you get a, the best fit is a equals one.

Â So it looks like it's pretty much uniformly at random and R-squared of about 94%.

Â So again a fairly tight fit.

Â That one looks like it's being matched fairly well by uniformly at

Â random and in fact there's a number of ones that come out at one.

Â So if you do there's another one, Amateur Radio operators,

Â so for people that don't know before the Internet people

Â used to use short wave radios and talk to each other so instead of having

Â chat rooms you could get on the radio and then just search

Â to find somebody else who might be

Â also broadcasting on the radio, you could talk to them.

Â These were amateur radio operators.

Â There's a dataset that looks at these

Â again a equals one uniformly at random fairly good fit.

Â The high school romance that we looked at, Bearman, Moody,

Â and Stovel's data, the degree distribution there.

Â Again very well fit uniformly at random.

Â So looks better, like more like uniformly random here the R-squared is .99.

Â So a remarkably strong fit to

Â uniformly at random model that says something about high school romances, in any case.

Â So you know these are just a couple of notes on these fits.

Â Some of these are actually even more curved than with a equals one.

Â And in those cases it could be that instead of having

Â this growing network model if you go back to the

Â static uniformly at random model you can even do a better fit.

Â So those are fit better even by not including some of the growth.

Â So the growth isn't a major factor in those.

Â The citations networks, you know,

Â some of the things is it has too many with degree zero to fit.

Â And then part of what's happening in the model is

Â the model starts with everybody having some degree and it's not

Â taking into account the fact that some citations are directed and

Â might never be hitting some articles.

Â Interestingly, if we go back to

Â the Notre Dame World Wide Web that

Â has sort of generated a lot of interest in the power law.

Â When you look at the best fitted series it actually has a at

Â .36 so a little more than a third of the links are being formed uniformly at random.

Â Now when you actually plot out,

Â now instead of just binning the things a

Â very fine binning of the actual degrees the R-Squared is .97.

Â And interestingly this still looks,

Â in a log-log plot it looks fairly close to a line.

Â Right. But it's saying that the actual fit has some curvature.

Â And one thing that's very important to understand about

Â these kinds of things is that a lot of the data,

Â when you do a log-log plot,

Â you know, most of your data is actually in a smaller part of the graph.

Â Right. So the log of the frequency is changing the relative weights.

Â And so what you actually see in your eye is,

Â you know, capturing the long tail.

Â And so this looks fairly linear but there actually can be a lot of curvature that you've

Â missed because the log

Â straightens things out and it's very difficult for your eye to detect that.

Â And so what this tells us is if we actually

Â want accurate understandings of what's really going on in

Â these things just eyeballing these things is not going

Â to give us a good idea of what the true distributions look like.

Â When you actually fitted distribution,

Â the distribution here looks like it's sort of two thirds preferential attachment but one

Â third uniformly at random is

Â a much better fit than just a pure preferential attachment model.

Â And so you know there there might be other things going on whereas you know

Â pages accumulate some of their links

Â through some other process other than preferential attachment.

Â And that's an important caveat to these things.

Â So when we understand power law is one thing we should understand is there are

Â fat tails but not necessarily purely linear relationships.

Â And when you fit them it's very difficult to let your eyes do things in a log-log plot.

Â You can get a very different distribution if you're careful about it statistically.

Â All right, so we end up here,

Â you know, just to emphasize that eyeballing log-log plots can be misleading.

Â So fat tails, yes.

Â An actual power distribution, no.

Â Here we're finding about two thirds of a power distribution and

Â one third of uniform at random seems to be a better fit of this.

Â Okay.

Â One other thing in terms of fitting this kind of model into data.

Â There are other things that the Friends of Friends model allows us to do.

Â So you know it does give us

Â a variety of degree distribution so we can span different degree distributions.

Â And it ties the degree distribution to the way that links were

Â formed in terms of having some meeting friends of friends.

Â But to emphasize some other things things that were missing from

Â the original models including a straight preferential attachment model is you

Â still don't get clustering you're just forming links at random and the chance that two

Â of my friends were already connected to each

Â other begins to vanish as time becomes large.

Â When you actually do things by this Friends of Friends model then what you end up doing

Â is connecting to people in ways that form triangles.

Â So let me just sort of give you an illustration of that

Â so you understand it's an important idea.

Â And so the idea,

Â recall here when we've got these nodes,

Â so we've got a new node and let's say suppose we have some existing nodes

Â and let's suppose that those existing nodes were already connected to each other.

Â Right. So this network and the way in which the node form some attachments

Â was first found one uniformly at random it found

Â this node and then it attached to one of its friends.

Â So the fact that the attachment was via this search process of

Â finding a friend of a friend means that we've actually formed a triple here.

Â And so we ended up with two of this nodes friends

Â being friends with each other partly because the way

Â it found people was through finding friends of friends.

Â So we get natural clustering directly through this process and that's different

Â than what happens in the peer preferential attachment model

Â or the uniformly at random model.

Â So the fact that you're doing things through network search gives clustering directly.

Â So the clustering is going to depend on this

Â a parameter but we'll find clustering in the data.

Â Second thing is diameter is naturally going to be

Â small partly because you've already got either you

Â know you've got random network formation

Â so you've either got something that looks uniformly at random or

Â preferential which even has a lower diameter than dash-ready kinds of networks.

Â Another thing and one thing we haven't talked about yet in much detail but you

Â will observe in a lot of networks is what's known as assortativity.

Â Okay and what does assortativity mean?

Â Let's think of the older nodes.

Â The older nodes are more likely to be

Â connected to each other because when they were born and young

Â the formation process was only between the ones that were existing at

Â that time period and so older nodes are more likely to be connected to other older nodes.

Â And so what we and up with is a correlation in the age of

Â nodes in connections which also means that they are

Â the ones that have a higher degree are going to tend to be connected

Â to other ones that have high degree and ones that have

Â lower degree are going to have

Â more connections to ones with lower degree because they're forming

Â ones later on their forming their links later on and

Â so will tend to have more links to younger nodes too.

Â And so what we'll end up with is

Â a degree distribution that exhibits some correlation in degrees.

Â More of a high degree node's friends will be

Â high degree and more low degree's nodes will be low degree.

Â So we get a series of other things coming out directly.

Â This is something which is going to come out of any of these growing systems.

Â So this comes out of the growth.

Â This just comes out of the fact that we've got random network.

Â And this part, the clustering,

Â comes out of the friends of friends part.

Â Right. So we've got the growth that's giving us assortativity,

Â the randomness gives us small world diameter,

Â and the clustering part,

Â the other part of small worlds is coming from the friends of friends of the process.

Â So we're going to get three extra things.

Â