0:20

Okay, Let's say a session between one and two,

Â one and three, one and four, one and five. Then a session between two and three going

Â through this path, like two and four and two and five, And so on. There are all

Â together ten possible sessions among these five nodes.

Â And there are five links five directional links.

Â We can look at the degree distribution here.

Â The degree distribution for this graph is very simple is three two, two, two one.

Â Okay, of course this is extremely small example to illustrate our point.

Â But this enables us to write the matrices and optimization in a single slide.

Â Alright so let's look at call this graph G1.

Â Okay let's look at S of G1 and P of G1. The smaller S of G1 is easy to compute

Â because the sum of the DIDJ's for all the IJ's are connected.

Â For example notice 1,2 are connected so the first term is D1 plus D2.

Â And there are all together five terms here.

Â D1 + D3 + D1. + D5 + D2 + times D4 + D3 + D4.

Â Okay, that's all associated for the left graph.

Â We'll talk about the right graph in a minute.

Â So, you can add this up. For example, the first term is three times

Â two. Okay.

Â With all the terms and then you get a number 23.

Â Now, how do find the big'S' of'G1'. We need to know what kind of graph with a

Â no degree distribution of 3,2,2,2,2,1. Would give you the largest small s.

Â Why if you look at all these terms, you see that the best way to do that is to

Â make a simple swap, okay? Instead of three connect to four and one

Â connect to five, one should connect to four, because then we get a term of three

Â multiply two, instead of three multiply one.

Â Okay? So switch one to five to one to four.

Â And then switch three to four to three to five.

Â You can verify that, in this right hand graph G2 called.

Â It has the exact same no degree distribution 3,2,2,2,1.

Â Again, it's not exactly Pareto but it suffices to illustrate our point of

Â tradeoff between S of G and P of G, Okay?

Â And then you can carry out the computation for small s of G2 is 24.

Â And therefore big S of G1 is, is small s divided by the maximum as you can get out

Â of all the graphs with this degree distribution, which is 24.

Â So, it's 23 out of 24. And clearly, big S G2 is 24 out of 24, is

Â one So, one is less than one the other is one.

Â Therefore this graph, g1 is less likely to be joined at random than G2.

Â Just like internet is less likely to be drawn than preferential attachment type of

Â topology. So now the question is what about

Â performance. P of G1 and P of G2.

Â Let's run this exercise for P of G1. P of G2 is very similar.

Â 4:04

So we just calculated the likelihood already.

Â Now here's the performance. So first of all, we have to write out this

Â routing matrix, R, which is five by ten because there are ten possible sessions,

Â Okay? And the variables is basically X1, X2 dot, dot, dot, down to X10.

Â And there are five, links, five nodes here, okay?

Â So R is five by ten. Let's say the first, session is the

Â session of session one. Is the session that goes from node one to

Â node two. And therefore it's simply one, one, zero,

Â zero, zero is this call. Because the first session goes through

Â nodes one and two, and no other nodes, okay?

Â And the second session, which is let's say, one goes to three.

Â 5:46

So this session the fifth column is the session number five going from node two to

Â node three. And the path will traverse the following

Â the three nodes eleven. The first three nodes one, two, three.

Â So the entries in these columns are 1,1,1,0,0.

Â So you can fill out the rest. And now, with this routing matrix

Â constructed, we say, this matrix multiply, our variable should be less than.

Â The total bandwidth available per router, and out of these five nodes.

Â Let's say the BKs are exactly the same as the degree.

Â They don't have to be, just to make the numbers simpler.

Â And therefore, they are three, two, two, two, one, basically.

Â So the total bandwidth a number of packets can process is just is directly

Â proportional to their node degrees. So per degree, basically, assuming has a

Â unit capacity of processing. So, subject to this constraint,

Â 7:07

Okay? And, the definition that each x is really

Â row times the demand. And the supply so we can make up some data

Â for these y values, okay? For example, we can just say the y vector

Â is five, two, four, four, two and therefore, for each session, there're ten

Â of them, you can look at what are the sources destination, multiply the number

Â and then you get another constraint. So, constraint one, constraint.

Â Two subject to these two constraints, maximize the summation of x I in this, the

Â objective function for performance. If you solve this very simple linear

Â optimization problem, you get the following answer.

Â The following answer, X star, is some vector actually doesn't matter.

Â Row star actually doesn't matter. It turns out to be 0.033, but that's not

Â key. The key is that the maximized the sum of

Â these end to end sessions throughput, that is the performance, with this graph G1 is

Â 3.73 certain unit, let's say, gigabits per second.

Â 8:28

. Now we can carry out exact same procedure

Â for this graph G2, Okay?

Â And then you're going to get a different number.

Â It turns out that the performance for G2 graph is 3.03.

Â Gigabit per second which is clearly smaller than 3.73 significantly.

Â And the reason is quite clear, because in order make that most highly connected node

Â to be sort of in the center of this very small graph, your actually creating a

Â performance bottleneck in supporting throughput.

Â So now if I plot the location of G1G2 in the P performance versus S likelihood,

Â nominalized likelihood graph, I see that they follow the same trend as the Internet

Â versus preferential attachment, except this is a much, much smaller example.

Â So we get a very small dynamic range, but none the less, you see a qualitative trade

Â off between performance and likelihood. So that is our small example.

Â And we are going to conclude this part of the lecture.

Â 9:49

In the advanced material we'll say a lot more about both preferential attachment

Â and constraint optimization as generative models of scale-free networks.

Â And there's a very rich and interesting background.

Â The history goes all the way back to, Zips.

Â And then to Pareto and Yudi. Who basically discovered that for many

Â phenomena, whether it's the size of the city, or the frequency of appearance of

Â words in languages. Many distributions.

Â The [inaudible]. Most popular, by histogram tallying item.

Â Often shows up with a frequency that is one over K.

Â Now, clearly, that is our scale free phenomenon.

Â It doesn't matter what K is, the chance of it shows up is one over K.

Â 10:48

So there's no specific characteristic scale, just like parietal distribution, as

Â you can see parietal in the history of this evolution.

Â And then, back in the 1950s there was this debate to say all these are observations.

Â The question is, how do you explain the observation.

Â And there was a debate between Menderbroat and Simon.

Â And that debate is very similar to the debate about ten years ago in early 2000

Â between profound attachment and cost string optimization.

Â Except the context of course, in 1950s was not internet router topology.

Â 11:30

And very briefly speaking, Before going to mass material preferential

Â attachments says that when new nodes added to a graph, they are more likely to be

Â connected to those with a lot of connections already.

Â So the rich gets richer more connected gets even more connected.

Â Conceptually this is said the self organizing growth mechanism of the graph

Â leads to paralogical distribution And mathematically, just, turns out that

Â sampling, by density leads to a difference equation.

Â We'll see that in advanced material whose solution gives you equilibrium that

Â satisfies a power law. In contrast,

Â Constraint optimization generates power law distribution in very different ways,

Â so that the graph topology is really designed with some objective functions,

Â and some constraints in mind. And yet, resulting topology can also show

Â power law. Conceptually it said that power law is the

Â natural outcome of constraint optimization.

Â With objective driven by economics, for example in constraints driven by

Â technology, mathematically says that either entropy maximization, or what's

Â called iso-elastic utility maximization and the linear constraints.

Â We're going to see these in the advanced material part of the reading for this

Â lecture. Either of them, among many others would

Â give rise to a power law. So there lies, the main differences

Â between preferred attachment, and constraint optimization.

Â So the question is which one to use? Well, it depends on which one gives you

Â the predictive power that you need on other properties.

Â Not the power law distribution anymore, because they both generate that.

Â Other properties of the graph, such as robustness to a target attack of highly

Â connected nodes. Would that break the network?

Â Would that break just the edge? Whichever, generate a model can also have

Â a predict on other properties that you care about, should be the one that you

Â use. And there lies an interesting story on the

Â pitfall of generated models. In 2000 There were so much talk about the

Â internet having an Achilles heel. It turns out that if you look at empirical

Â data, you go talk to At and t or Cisco-Juniper you'll realize that, that's

Â just now supported by factual data. It highlights the importance of

Â fortification of any self consistent theory through empirical data of the field

Â that you are talking about. It also highlights the risk of over

Â generalizing something called a network science, which is a fuzzy and mostly, a

Â meaning less term, unless you provide some concrete meaning to it By overgeneralizing

Â it to some universally true property it actually loses domain-specific

Â functionality models. And thereby often loses predictive power

Â and even lead to confusing misleading conclusions.

Â Such as the non-existence of this Achilles heels So we have seen generative models.

Â Reverse engineering of network apology, small whirls and scale free, and later

Â we'll also look at reverse engineering of network protocols.

Â We have also seen. The interplay between topology, say a

Â graph and the corresponding matrices, versus functionalities.

Â Whether there's navigation or search. Routing or robustness to a specific kind

Â of attacks. And, the interplay between these two

Â dimensions of what we call a network whether socio-economic or tech network

Â will continue to show up in the rest of the course.

Â As we conclude this point. The midpoint of this twenty questions

Â about our net (for) life.

Â