ネットワークの密度と平均経路長

最初に扱うグラフレベルの指標は、グラフの密度です。これは、頂点同士の取り得るすべての辺のうち、実際にネットワークグラフに存在する辺の割合を指します。グラフの頂点がどの程度よく結び付いているかを示す指標です。

ネットワークの結び付きの度合いを示すもう1つの指標が平均経路長です。これは、ネットワーク内のすべての頂点対について、最短経路の長さの平均を求めて計算します。任意の頂点対の最長の最短経路長は、ネットワークグラフの直径と呼ばれます。ここでは元のグラフ g の直径と平均経路長を計算します。