ただのメモ

他の人に見せても良い方のメモ

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

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

network_theory.pdf (mashykom.com)

始めましょうか。

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