## Properties of Social Networks - Intro to Algorithms

• 0:00 - 0:04
Well, this is a lot of boxes to check for one quiz
• 0:04 - 0:08
but I don't think it's that hard to think about so let's go through this.
• 0:08 - 0:13
In a clique, each node is connected to each of the other nodes.
• 0:13 - 0:18
So the degree is linear in the number of nodes but think about path links.
• 0:18 - 0:20
Every node is connected to every other node.
• 0:20 - 0:24
So the path you can always get directly from one node to any other node.
• 0:24 - 0:31
A very, very small world but it's a small world because everybody knows everybody.
• 0:31 - 0:34
And we know that that's not what our world is like.
• 0:34 - 0:39
Now if you go to a small private school you may have exhibit exactly this kind of effect.
• 0:39 - 0:43
All right, next let's think about a ring. What happens in a ring?
• 0:43 - 0:46
Well, the degree in a ring is always 2. All the nodes have a degree of 2.
• 0:46 - 0:53
So it's a constant degree, but what about a path link? What's the longest path link in a ring?
• 0:53 - 0:57
Well, some of the nodes are really nearby but some of them you have to go all the way
• 0:57 - 1:01
to the other side to get to them and that could be as big as the number of nodes N
• 1:01 - 1:05
divided by 2 because it's the opposite side.
• 1:05 - 1:08
After you get further and further and further, you start to get closer again.
• 1:08 - 1:14
So the path link is actually linear in this case. Balanced tree is really interesting.
• 1:14 - 1:19
So the degree here, well a node might have a parent and two children.
• 1:19 - 1:22
This is a balanced binary tree in particular.
• 1:22 - 1:30
The root node has a degree of 2 and all the leaves have a degree of 1, so it's never more than 3.
• 1:30 - 1:34
No matter how many nodes were in the graphs so the degree is constant.
• 1:34 - 1:36
But let's look at the path link.
• 1:36 - 1:40
Any node can get to any other node by going up to the root
• 1:40 - 1:42
and then back down to the other node you want to get to.
• 1:42 - 1:46
Getting up to the root takes logarithmically not many steps.
• 1:46 - 1:49
And then going back down also takes logarithmically not many steps.
• 1:49 - 1:53
So it's like two log n but that's actually a pretty short path for a big graph.
• 1:53 - 1:56
It's not that many hops you have to make to get to where you're going.
• 1:56 - 1:58
All right finally let's look at our friend the hypercube.
• 1:58 - 2:05
In a hypercube, each node is numbered with log n bits and it's connected to all the other
• 2:05 - 2:09
nodes in the network that have names that differ by at most one bit.
• 2:09 - 2:11
There's at most logarithmically many of those.
• 2:11 - 2:17
So each node in the hypercube is connected to log n and other nodes.
• 2:17 - 2:19
The degree is a big data of log n.
• 2:19 - 2:24
Now what about path link. If I want to get from one node to any other node, what do I need to do?
• 2:24 - 2:29
• 2:29 - 2:32
So let's imagine we want to get from some node and here's its label 010
• 2:32 - 2:37
to some other node and here's its label 111.
• 2:37 - 2:44
We know in one hop we can go from 010 to 110.
• 2:44 - 2:48
And then in one more hop we can go from 110 to 111.
• 2:48 - 2:53
In fact, to go from any node in the hypercube to any other node in the hypercube,
• 2:53 - 2:58
all you have to do is go through the bit positions one at a time and to reverse
• 2:58 - 3:03
the corresponding edge if the source and the target differ in that bit position.
• 3:03 - 3:10
So in at most log n hops we can go from any position in this hypercube to any other position.
• 3:10 - 3:13
So again pretty short paths.
タイトル：
Properties of Social Networks - Intro to Algorithms
Video Language:
English
Team:
Udacity
プロジェクト：
CS215 - Intro to Algorithms
Duration:
03:13
 Udacity Robot edited 英語(米国) subtitles for Properties of Social Networks - Intro to Algorithms Gundega edited 英語(米国) subtitles for Properties of Social Networks - Intro to Algorithms Amara Bot added a translation

# English subtitles

## 改訂 Compare revisions

• API
Udacity Robot
• Gundega
• Amara Bot