ネットワーク理論に入門する！

ネットワーク理論について知りたい。

network_theory.pdf (mashykom.com)

始めましょうか。

• 序
  • ネットワークの多種多様な領域に広がっている。
  • 4つの類
    • 社会経済的
    • 情報
    • 技術的
    • 生物学的
• ネットワークの基礎概念と社会ネットワークの特徴
  • ネットワークの例
    • 友人関係のネットワーク
    • 個人・団体のノードとする、2部グラフ
  • ネットワークの定義
    • ノードと各ノードを接続するリンクの集合
    • ウォーク
      • リンクによって連結しているノードの点列
    • パス
      • ウォークの中のノードが全て相異なる
    • サイクル
      • 起点終点が同じ点列
    • （ノードAの）隣人集合
      • ノードAに連結するリンクを持つ全てのノードの集合
    • 次数
      • その点の隣人集合の要素数
    • 正則グラフ
      • 全てのノードが同一数の次数を持つネットワーク
    • 完備ネットワーク
      • 各ノードが他の全てのノードと連結している。
    • コンポーネント
      • 構成要素
      • 部分ネットワークで、全てのノードが連結している最大の部分集合
    • 測地距離（最短距離）
      • 2つのノードを結ぶ最短ぱすの距離
    • 直径
      • ネットワーク上の任意の2つのノード間の最短距離の最大値
    • パスの平均距離
      • 各ノード間の最短距離の平均
  • 中心化と群集化の諸概念
    • 各ノードの重要性を測る計数の、中心化度
      • 4種の定義
      • 次数
        • 次数を可能な最大次数で割った値
      • 近接性
        •  
      • 中継性
        • 
      • 隣人
    • クラスタリング係数（群集化係数）
      • ノードAの2人の隣人間のリンクの数/ノードAの隣人の2人の組み合わせ
      • これを各ノードで求めると、ネットワーク全体のクラスタリング係数を求められる
    • クリーク（派閥）
      • 包含関係に関して最大の部分完備ネットワーク
  • 現実社会でのネットワークの特徴
    • ランダム・ネットワーク
      • リンクがある確率はp
      • クラスタリング係数はp（自明）
      • ベルヌーイ分布
      • ノード数がふえると、ポアソン分布になる
• ネットワークの基本モデル
  • Erdös and Renyi型ランダムネットワーク
    • ノード数ｎでリンク数ｍのネットワーク
  • リンク数を多くしていくと、巨大クラスターが出来る。
    • これが、パーコレーションと関連している話
    • ネットワークにおけるリンク数が1を超えると、巨大クラスターが生まれる
    • ネットワークの連結性が、リンクの形成確率pによって変化する。
  • 配列モデル
    • 次数の分布
    • 隣人同士の間に相関関係がない
• スモールワールド・モデルとスケールフリー・モデル
  • スモールワールド・モデル
    • 小さな密なクラスターがそれぞれ疎に繋がっている。
    • 群集化係数が０より大きい、ネットワーク内各ノード間のパスの距離が短い
  • スケールフリー・モデル
    • ハブの存在が、ネットワークのトポロジーを決める。
• 結び