勾配ネットワーク

ネットワーク科学において、勾配ネットワークは、無向「基質」ネットワークの有向サブネットワークであり、各ノードには関連するスカラーポテンシャルと、その近傍で最小（または最大）のポテンシャルを持つノードを指す1つのアウトリンクがあり、これは基質ネットワーク上のノード自体と近傍のノードの和集合として定義されます。 ^[1]

輸送は基質グラフと呼ばれる固定ネットワーク上で行われます。基質グラフにはN 個のノードとエッジの集合があります。ノードiが与えられた場合、G 内のその隣接ノードの集合を S _i ⁽¹⁾ = {j ∈ V | (i,j)∈ E} で定義できます。${\displaystyle G=G(V,E)}$${\displaystyle V=\{0,1,...,N-1\}}$${\displaystyle E=\{(i,j)|i,j\in V\}}$

また、ノード集合V上に定義されたスカラーフィールドh = { h ₀ , .., h _{N −1 }を考えてみましょう。これにより、すべてのノードiにはスカラー値}h _iが関連付けられます。

ネットワーク上の勾配∇h i _: ∇h i ₍ i, μ(i))${\displaystyle =}$ 、すなわちiからμ(i)へ の有向辺。ここでμ ( i )∈S _i ⁽¹⁾ ∪{i}であり、h _μは最大値を持ちます。 ${\displaystyle {h_{j}|j\in S_{i}^{(1)}\cup {i}}}$

勾配ネットワーク : ∇ ∇${\displaystyle G=}$${\displaystyle G}$ ${\displaystyle (V,F)}$ ここで、 F はG上の勾配エッジの集合です。

一般的に、スカラー場は、ネットワーク上のフロー、外部ソース、シンクにより時間に依存します。したがって、勾配ネットワーク∇は動的になります。^[3]${\displaystyle G}$

勾配ネットワークの概念は、ToroczkaiとBassler（2004）によって初めて導入されました。^{[4] [5]}

一般的に、情報、車、電力、水、力などのエンティティを輸送するために進化することが多い現実世界のネットワーク（引用グラフ、インターネット、細胞代謝ネットワーク、世界規模の空港ネットワークなど）は、グローバルに設計されているのではなく、ローカルな変化を通じて進化し成長します。たとえば、インターネット上のルーターが頻繁に混雑し、それが原因でパケットが失われたり遅延したりする場合、相互接続された複数の新しいルーターに置き換えられます。^[2]

さらに、この流れはスカラーの局所的な勾配によって生成されるか、影響を受けることが多い。たとえば、電流は電位の勾配によって駆動される。情報ネットワークでは、ノードの特性によって、ノードからその隣接ノードへの情報の伝達方法にバイアスが生じる。この考えから、ネットワーク上に分布するスカラー場の勾配によって流れが駆動される場合、勾配ネットワークを使用してネットワークのフロー効率を研究するアプローチが生まれた。^{[2] [3]}

最近の研究^{[どの研究？ ] [更新が必要]では、}ネットワークトポロジと輸送の流れの効率との関係を調査しています。 ^[2]

勾配ネットワークでは、ノード i の入次数k _i ⁽ⁱⁿ⁾はi を指す勾配エッジの数であり、入次数の分布は です。${\displaystyle R(l)=P\{k_{i}^{(in)}=l\}}$

基質Gがランダムグラフで、各ノードのペアが確率Pで接続されている場合（つまり、エルデシュ・レーニランダムグラフ）、スカラーh _{i はiid（独立同一分布）であり}、R(l)の正確な表現は次のように与えられる 。

${\displaystyle R(l)={\frac {1}{N}}\sum _{n=0}^{N-1}\mathrm {C} _{l}^{N-1-n}[1-p(1-p)]^{N-1-n-l}[p(1-p)^{n}]^{l}]}$^[3]

およびの極限では、次数分布はべき乗則になる。 ${\displaystyle N\to \infty }$${\displaystyle P\to 0}$

${\displaystyle R(l)\approx l^{-1}}$

これは、この限界において、ランダムネットワークの勾配ネットワークがスケールフリーであることを示しています。^[3]

さらに、基質ネットワークGがバラバシ・アルバートモデルのようにスケールフリーである場合、勾配ネットワークもGと同じ指数を持つべき乗則に従います。^[2]

基盤ネットワークのトポロジがネットワークの混雑レベルに影響を与えるという事実は、簡単な例で説明できます。ネットワークが星型構造の場合、中央ノードは他のノードからのすべてのフローを処理する必要があるため、フローが混雑します。ただし、ネットワークがリング型構造の場合、すべてのノードが同じ役割を果たすため、フローの混雑は発生しません。

フローがネットワーク内の勾配によって生成されるという仮定の下では、ネットワーク上のフロー効率は、次のように定義される妨害係数 (または輻輳係数) によって特徴付けることができます。

${\displaystyle J=1-\langle \langle {\frac {N_{\text{receive}}}{N_{\text{send}}}}\rangle _{h}\rangle _{\text{network}}=R(0)}$

ここで、N_受信は勾配フローを受信するノードの数、N_送信は勾配フローを送信するノードの数です。J の値は0から 1 の間です。は混雑がないことを意味し、最大の混雑に対応します。極限では、エルデシュ・レーニイランダムグラフの場合、混雑係数は次のようになります。 ${\displaystyle J=0}$${\displaystyle J=1}$${\displaystyle N\to \infty }$

${\displaystyle J(N,P)=1-{\frac {\ln N}{N\ln({\frac {1}{1-P}})}}\left[1+O({\frac {1}{N}})\right]\rightarrow 1.}$

この結果は、ランダムネットワークがその限界内で最大限に混雑していることを示しています。対照的に、スケールフリーネットワークの場合、Jは任意のNに対して定数であり、スケールフリーネットワークは最大限に混雑する傾向がないことを意味します。^[6]

通信ネットワークにおける一つの問題は、輻輳を制御し、正常かつ効率的なネットワーク機能を維持する方法を理解することである。^[7]

Zonghua Liuら（2006）は、ネットワーク内の次数の高いノードでは輻輳が発生する可能性が高く、少数のノード（例えば3％）のメッセージ処理能力を選択的に強化する効率的なアプローチは、すべてのノードの能力を強化するのと同等の性能を発揮することを示した。^[7]

Ana L Pastore y Pionttiら（2008）は、緩和ダイナミクス^{[説明が必要]}がネットワークの混雑を軽減できることを示した。^[8]

Pan et al. (2011)は、エッジにノードポテンシャル間のスカラー差のべき乗の重みが与えられる方式におけるジャミング特性を研究した。^{[9] [説明が必要]}

NiuとPan（2016）は、勾配場とローカルネットワークトポロジーの間に相関関係を導入することで混雑を軽減できることを示した。^{[10] [説明が必要]}

• ネットワークダイナミクス
• ネットワークトポロジ
• 量子複雑ネットワーク