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

ネットワーク理論 において、スモールワールドルーティングとは、スモールワールドネットワーク向けのルーティング手法を指します。このタイプのネットワークは、任意の2つのノード間に比較的短い経路が存在するという特徴があります。しかし、ネットワーク全体に関する情報が他にない場合、ネットワーク内の個々のルーティングノードにとって、これらの経路を特定することは困難な問題となる可能性があります。

スモールワールドにおけるルーティング問題の解決策は、ほぼすべて貪欲ルーティングの適用を伴います。この種のルーティングは、パス上のどのノードも、宛先に最も近いと思われる次のノードを選択できる相対的な基準点に依存します。つまり、貪欲になる対象となる何かが存在する必要があります。例えば、地理的な位置、IPアドレスなどが考えられます。ミルグラムのオリジナルのスモールワールド実験では、参加者は最終受信者の位置と職業を知っていたため、それらのパラメータに基づいてメッセージを転送することができました。

明確な参照ベースがない場合、貪欲ルーティングは容易には機能しません。これは、例えば、基盤となるネットワークにおける宛先の位置に関する情報が利用できないオーバーレイネットワークで発生する可能性があります。フレンドツーフレンドネットワークは、この問題の典型的な例です。このようなネットワークでは、既に隣接しているノードに関する基盤情報しか知らないという事実によって信頼が保証されます。

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

この解決策における重要な問題は、局所最適解に陥る可能性です。これは、ノードが局所的な近傍のみを考慮した最適な状態にあり、遠方のノードとの交換によってより高い最適性が得られる可能性を無視している場合に発生する可能性があります。上記の論文では、著者らは、最適ではない交換を小さな確率で実行するシミュレーテッドアニーリング法を提案しました。この確率は、交換を行うことの価値に比例します。もう1つのメタヒューリスティック最適化手法として、タブーサーチがあります。これは、交換決定に記憶機能を追加します。最も単純な形式では、過去の交換の履歴を限定的に記憶し、交換可能なノードのリストから除外します。

この参照ベース構築方法は、ネットワーク全体の状況を把握していない個々のノードレベルでのみ意思決定が行われる分散環境にも適用可能です。必要な変更点は、ランダムなノードペアを選択する方法のみです。分散環境では、各ノードが定期的にランダムウォーカーを送信し、交換対象となるノードで停止させることでこれを実現します。

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

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