スモールワールドルーティング

ネットワーク理論 では、スモールワールド ルーティングとは、スモールワールド ネットワークのルーティング方法を指します。このタイプのネットワークは、任意の 2 つのノード間に比較的短いパスが存在するという点で特殊です。ただし、ネットワーク全体に関する詳細情報が不明な場合、ネットワーク内の個々のルーティング ノードの観点からこれらのパスを決定することは困難な問題になる可能性があります。

スモールワールドにおけるルーティングの問題に対するほぼすべての解決策には、貪欲ルーティングの適用が含まれます。この種のルーティングは、パス上の任意のノードが宛先に最も近いと思われる次のノードを選択できる相対参照ポイントに依存します。つまり、貪欲になる何かがなければなりません。たとえば、これは地理的な場所、IP アドレスなどです。ミルグラムの元のスモールワールド実験の場合、参加者は最終受信者の場所と職業を知っていたため、それらのパラメータに基づいてメッセージを転送できました。^{[引用が必要]}

貪欲ルーティングは、明らかな参照ベースがない場合にはうまく機能しません。これは、たとえば、基礎となるネットワーク内の宛先の場所に関する情報が利用できないオーバーレイ ネットワークで発生する可能性があります。友人同士のネットワークは、この問題の具体的な例です。このようなネットワークでは、すでに近隣関係にあるノードに関する基礎情報のみを知っているという事実によって信頼が確保されます。^{[引用が必要]}

この場合の 1 つの解決策は、ノードに何らかの人工的なアドレスを課すことです。このアドレスは、貪欲なルーティング方法で効果的に使用できます。Freenetプロジェクトの開発者による 2005 年の論文では、友人同士のネットワークでこれを実現する方法について説明しています。これらのネットワークは、多くの場合、現実世界または知り合いの関係の結果として、スモール ワールド特性を示すという仮定を考慮すると、埋め込まれたクラインベルグスモール ワールド グラフを復元できるはずです。これは、任意のノードとその近隣ノード間のすべての距離の積を最小化する目的関数に基づいて、ランダムにノードのペアを選択し、場合によってはそれらを交換することで実現されます。 ^{[引用が必要]}

このソリューションに伴う重要な問題は、局所的最小値の可能性です。これは、ノードが局所的な近傍のみを考慮して最適な状況にあり、遠くのノードとのスワップによって生じるより高い最適性の可能性を無視している場合に発生する可能性があります。上記の論文では、著者は、最適ではないスワップが小さな確率で行われるシミュレーテッド アニーリング法を提案しました。この確率は、スイッチを行う価値に比例していました。もう 1 つの可能なメタヒューリスティック最適化方法は、スワップの決定にメモリを追加するタブー検索です。最も単純な形式では、過去のスワップの限られた履歴が記憶され、それらが可能なスワップ ノードのリストから除外されます。^{[引用が必要]}

参照ベースを構築するこの方法は、ネットワーク全体についての知識を持たない個々のノードのレベルでのみ決定を下すことができる分散設定にも適用できます。必要な変更は、ランダム ノードのペアを選択する方法だけです。分散設定では、各ノードが定期的にランダム ウォーカーを送信し、スワップ対象として検討するノードで終了するようにすることでこれを行います。^{[引用が必要]}

クラインバーグのネットワークモデルは、貪欲なスモールワールドルーティングの有効性を示すのに効果的です。このモデルは、nxn のノードグリッドを使用してネットワークを表現し、各ノードは無向エッジで近隣のノードに接続されます。「スモールワールド」効​​果を与えるために、ネットワークに長距離エッジがいくつか追加され、距離が遠いノードよりも近いノードが優先される傾向があります。エッジを追加すると、ランダムな頂点が別のランダムな頂点 w に接続される確率は に比例します。ここで はクラスタリング指数です。^[1]${\displaystyle v}$${\displaystyle 1/d(v,w)^{q}}$${\displaystyle q}$

貪欲アルゴリズムは、長距離エッジを使わずに、グリッド上のランダムな頂点から時間内にナビゲートできることは容易にわかります。保証された接続を近隣にたどることで、目的地の方向に一度に 1 単位ずつ移動できます。これは、クラスタリング コンポーネントが大きく、「長距離」エッジが非常に近いままになる場合にも当てはまります。このモデルでは、弱いつながりを利用しないだけです。 の場合、長距離エッジはランダムに均一に接続されます。つまり、長距離エッジは分散検索に効率的に使用するには「ランダムすぎる」ということです。Kleinberg は、このモデルの最適なクラスタリング係数は 、つまり逆二乗分布であることを示しました。^[2]${\displaystyle v\rightarrow w}$${\displaystyle O(n)}$${\displaystyle q}$${\displaystyle q=0}$${\displaystyle q=2}$

なぜそうなるのかを説明すると、最初のノードの周りに半径 r の円を描くと、その円はノード密度を持ちます。ここで、n は円領域内のノードの数です。この円がさらに拡大されるにつれて、任意のノードとのランダムリンクを持つ確率は に比例したままであるため、指定された領域内のノードの数は に比例して増加します。つまり、元のノードが指定された距離離れた任意のノードと弱いつながりを持つ確率は、実質的に距離とは無関係です。したがって、 では、長距離エッジがすべての距離にわたって均等に分散され、最終目的地に効果的に到達できると結論付けられます。^{[引用が必要]}${\displaystyle n/(\pi r^{2})}$${\displaystyle r^{2}}$${\displaystyle 1/r^{2}}$${\displaystyle q=2}$

DHTに基づく構造化されたピアツーピアシステムの中には、限られたノード数でピアツーピアネットワーク内で効率的なルーティングを可能にするために、クラインバーグのスモールワールドトポロジーのバリエーションを実装しているものが多い。^[3]

• ソーシャルネットワーク – 社会的行為者の集合体から構成される社会構造
• スモールワールドネットワーク – ほとんどのノードが少数のステップで到達可能なグラフ
• ワッツ・ストロガッツモデル – ランダムなスモールワールドグラフを生成する方法リダイレクト先の簡単な説明を表示するページ