Return to Video

03-04 Properties of Social Networks

  • 0:00 - 0:04
    たくさんチェックボックスがありますが
  • 0:04 - 0:08
    それほど難しくはないので早速チェックしていきましょう
  • 0:08 - 0:13
    クリークではすべてのノードがつながっているので
  • 0:13 - 0:18
    次数は線形です パスのリンクはどうでしょうか
  • 0:18 - 0:20
    各ノードがつながっているので
  • 0:20 - 0:24
    パスもすべて直接つながっています
  • 0:24 - 0:31
    誰もがお互いを知っているとても狭い世界です
  • 0:31 - 0:34
    現実の世界とはかけ離れていますが
  • 0:34 - 0:39
    小規模の私立学校なら
    このような効果が見られるかもしれません
  • 0:39 - 0:43
    続いてリングはどうでしょうか
  • 0:43 - 0:46
    リングの次数は常に2です
  • 0:46 - 0:53
    すべてのノードの次数が2なので定数となります
    パスのリンクはどうでしょう
  • 0:53 - 0:57
    ノードは近いものもあれば遠いものもあるので
  • 0:57 - 1:01
    リンクはノードnの半分の数になる可能性があります
  • 1:01 - 1:05
    一番遠いノードはリングの反対側になるからです
  • 1:05 - 1:08
    それ以降のノードはまた近くなってきます
  • 1:08 - 1:14
    この場合のパスは線形になります
    平衡木はとても興味深いですよ
  • 1:14 - 1:19
    ツリーのノードは親や子を持っているかもしれません
  • 1:19 - 1:22
    これは平衡二分木(平衡バイナリツリー)で
  • 1:22 - 1:30
    ルートの次数は2そしてすべてのリーフは1なので
    次数が3より大きくなることはありません
  • 1:30 - 1:34
    グラフにどれだけノードがあっても次数は定数です
  • 1:34 - 1:36
    パスのリンクに移りましょう
  • 1:36 - 1:40
    どのノードも1度ルートに上ってまた下りることで
  • 1:40 - 1:42
    他のノードに移動できます
  • 1:42 - 1:46
    ルートに上っても対数的なあまり多くないステップで
  • 1:46 - 1:49
    ルートから下りた場合も同じです
  • 1:49 - 1:53
    なので2 log nですが大きなグラフとしてはパスが短く
  • 1:53 - 1:56
    ホップ数もあまりいりません
  • 1:56 - 1:58
    最後はハイパーキューブです
  • 1:58 - 2:05
    ハイパーキューブの各ノードには
    log nビットの番号がついており
  • 2:05 - 2:09
    最大1ビットの番号が異なるノードとつながっています
  • 2:09 - 2:11
    多くても対数的な数だけあります
  • 2:11 - 2:17
    ハイパーキューブの各ノードは
    log n個の他のノードとつながっているので
  • 2:17 - 2:19
    次数はlog nのビッグ・シータです
  • 2:19 - 2:24
    次はパスです あるノードから
    別のノードに行くにはどうすればいいでしょう
  • 2:24 - 2:29
    これについてはお話ししていませんでしたが
    面白いですよ
  • 2:29 - 2:32
    ここがラベル010のノードと仮定して
  • 2:32 - 2:37
    ここからラベル111のノードに行く場合を考えましょう
  • 2:37 - 2:44
    ご存じのとおり1ホップで010から110へ移動できて
  • 2:44 - 2:48
    もう1ホップで110から111へ行けます
  • 2:48 - 2:53
    しかしハイパーキューブでのノード間の移動は
  • 2:53 - 2:58
    ビット位置を1つずつ調べて
  • 2:58 - 3:03
    ビット位置が異なる場合は
    一致するエッジを通ればいいのです
  • 3:03 - 3:10
    そのため最大でもlog nのホップ数で
    どの位置にでも移動できるので
  • 3:10 - 3:13
    ここもパスはかなり短くなります
タイトル:
03-04 Properties of Social Networks
Video Language:
English
Team:
Udacity
プロジェクト:
CS215 - Intro to Algorithms
Duration:
03:13

Japanese subtitles

改訂