Return to Video

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
    So we didn't talk about this before but it's actually kind of neat.
  • 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

English subtitles

改訂 Compare revisions