狠狠撸

第14回AIツール入門講座
「Google Colaboratoryによる
ネットワーク分析入門」
5. ネットワーク生成モデル
スケールフリー、スモールワールドなどのネットワーク生成モデ
ルについて説明します。

実ネットワークと人工ネットワーク
? 実ネットワーク
? 現実世界やSNSなどから観測
? 似たようなものを作るのが困難
? 人工ネットワーク
? モデルに基づいて生成
? 数学的な解析が比較的容易
モデル
化検証

人工ネットワークの例
? 次数分布の比較
ランダム
グラフ
スケール
フリー
グラフ
完全
グラフ
空手
クラブ
X軸:次数
Y軸:頻度

スケールフリーグラフ
? 成長：頂点が新たに追加され、減ることはない
? 優先的選択：新たに追加される頂点は、次数の高い頂点と高い
確率で辺で結ばれる
に基づく生成モデル
? X軸とY軸を対数目盛にした両対数グラフで
次数分布が直線になる

スケールフリーグラフの例
? 頂点数1000
? 新たな頂点は、既存の頂点と3本の辺でつながる
平均次数:6
両対数グラフ
で直線

スモールワールドグラフ
? 「6次のつながり」
? 友達の友達の…と6回たどると、任意の2人の米国人がつながる
? 頂点の数に比べて、頂点間の距離は驚くほど小さい
? クラスタ係数が大きく、かつ平均頂点間距離が短いグラフの生
成モデル

クラスタ係数と平均頂点間距離
? (円周上の近傍とつながる)規則的なグラフの辺をつなぎ変える
平均頂点間距離
クラスタ係数

Introduction of network analysis with Google Colaboratory -- Network Models