01. Introduction and the Bowtie Structure of the Web

Introduction

• ネットワーク
  • world economy, human cell, roads, brain, internet, friends & family, media & information, society
  • あれもこれもグラフ！ グラフ無しではこれらを理解できない！
• ネットワークに関してやること
  • empirical: ネットワークの構造等について解析する
  • mathematical models: モデルを作る
  • algorithms: 解析するために
• それによって何をしたいか？
  • 性質，モデル，ネットワークがなぜそのようになるかを理解し，そして予測する
• なぜネットワークなのか？
  • data availability：データが手に入る
  • universality：あれもこれもグラフ
  • shared vocabulary between fields：どの学問でもグラフが出てくる
  • impact
• 例
  • 病気の伝染を理解したい．
  • ウェブの構造や情報を理解したい．
  • ニュースの伝搬を理解したい．

Structure of the Web Graph

[Broder et al., 2000]

• WCC: 91% が WCC，indeg >10 を全部取り除いても WCC は 50%
• SCC: largest SCC が 50%
• 以上より，Bow-tie structure of the web だ
  • ＞○＜ ←こんな感じらしい