平均経路長

平均パス長、または平均最短パス長は、ネットワーク トポロジの概念であり、ネットワークノードのすべての可能なペアの最短パスに沿った平均ステップ数として定義されます。これは、ネットワーク上の情報または大量転送の効率の尺度です。

平均パス長は、クラスタリング係数および次数分布とともに、ネットワークトポロジの 3 つの最も堅牢な尺度の 1 つです。例としては、ある Web サイトから別の Web サイトに移動するクリックの平均回数や、まったく知らない人と連絡を取るために平均して経由しなければならない人数などが挙げられます。これは、ネットワークの直径と混同しないでください。ネットワークの直径は、最長の測地線、つまりネットワーク内の任意の 2 つのノード間の最長最短パスとして定義されます( 「距離(グラフ理論) 」を参照)。

平均パス長は、簡単にネゴシエートできるネットワークと複雑で非効率的なネットワークを区別するものであり、平均パス長が短いほど望ましいとされています。ただし、平均パス長は、パス長が最も可能性の高い長さであることを意味します。ネットワーク自体には、非常に遠く離れたノードがいくつかある場合もあれば、互いに隣接するノードが多数ある場合もあります。

頂点の集合を持つ重みなし有向グラフを考えます。 と の間の最短距離を とします。からに到達できない場合は と仮定します。この場合、平均パス長は次のようになります。 ${\displaystyle G}$${\displaystyle V}$${\displaystyle d(v_{1},v_{2})}$${\displaystyle v_{1},v_{2}\in V}$${\displaystyle v_{1}}$${\displaystyle v_{2}}$${\displaystyle d(v_{1},v_{2})=0}$${\displaystyle v_{2}}$${\displaystyle v_{1}}$${\displaystyle l_{G}}$

${\displaystyle l_{G}={\frac {1}{n\cdot (n-1)}}\cdot \sum _{i\neq j}d(v_{i},v_{j}),}$

ここで、は の頂点の数です。 ${\displaystyle n}$${\displaystyle G}$

インターネットのような実際のネットワークでは、平均経路長が短いと、情報の迅速な転送が容易になり、コストが削減されます。代謝ネットワークにおける物質移動の効率は、平均経路長を調べることで判断できます。電力網ネットワークでは、平均経路長が最小化されると損失が少なくなります。

実際のネットワークのほとんどは平均パス長が非常に短いため、非常に短いパスを通じて全員が全員とつながっている 小さな世界という概念につながります。

その結果、現実のネットワークのモデルのほとんどは、この条件を念頭に置いて作成されます。現実のネットワークを説明しようとした最初のモデルの1つは、ランダムネットワークモデルでした。その後、ワッツとストロガッツのモデルが続き、さらに後にはBAモデルから始まるスケールフリーネットワークが登場しました。これらすべてのモデルには共通点が1つありました。それは、平均パス長が非常に短いと予測したことです。^[1]

平均パス長はシステムのサイズに依存しますが、それに応じて大幅に変化することはありません。スモール ワールド ネットワーク理論では、平均パス長は log n に比例して変化すると予測されています。ここで、n はネットワーク内のノードの数です。