
Well, this is a lot of boxes to check for one quiz

but I don't think it's that hard to think about so let's go through this.

In a clique, each node is connected to each of the other nodes.

So the degree is linear in the number of nodes but think about path links.

Every node is connected to every other node.

So the path you can always get directly from one node to any other node.

A very, very small world but it's a small world because everybody knows everybody.

And we know that that's not what our world is like.

Now if you go to a small private school you may have exhibit exactly this kind of effect.

All right, next let's think about a ring. What happens in a ring?

Well, the degree in a ring is always 2. All the nodes have a degree of 2.

So it's a constant degree, but what about a path link? What's the longest path link in a ring?

Well, some of the nodes are really nearby but some of them you have to go all the way

to the other side to get to them and that could be as big as the number of nodes N

divided by 2 because it's the opposite side.

After you get further and further and further, you start to get closer again.

So the path link is actually linear in this case. Balanced tree is really interesting.

So the degree here, well a node might have a parent and two children.

This is a balanced binary tree in particular.

The root node has a degree of 2 and all the leaves have a degree of 1, so it's never more than 3.

No matter how many nodes were in the graphs so the degree is constant.

But let's look at the path link.

Any node can get to any other node by going up to the root

and then back down to the other node you want to get to.

Getting up to the root takes logarithmically not many steps.

And then going back down also takes logarithmically not many steps.

So it's like two log n but that's actually a pretty short path for a big graph.

It's not that many hops you have to make to get to where you're going.

All right finally let's look at our friend the hypercube.

In a hypercube, each node is numbered with log n bits and it's connected to all the other

nodes in the network that have names that differ by at most one bit.

There's at most logarithmically many of those.

So each node in the hypercube is connected to log n and other nodes.

The degree is a big data of log n.

Now what about path link. If I want to get from one node to any other node, what do I need to do?

So we didn't talk about this before but it's actually kind of neat.

So let's imagine we want to get from some node and here's its label 010

to some other node and here's its label 111.

We know in one hop we can go from 010 to 110.

And then in one more hop we can go from 110 to 111.

In fact, to go from any node in the hypercube to any other node in the hypercube,

all you have to do is go through the bit positions one at a time and to reverse

the corresponding edge if the source and the target differ in that bit position.

So in at most log n hops we can go from any position in this hypercube to any other position.

So again pretty short paths.