複雑ネットワークゼータ関数

複雑ネットワークやグラフの次元については、さまざまな定義が与えられています。たとえば、メトリック次元は、グラフの分解セットに基づいて定義されます。次元は、グラフに適用されたボックスカバー法に基づいて定義されることもあります。 ^{[1]ここでは、}複雑ネットワークゼータ関数に基づく定義について説明します。^[2] これは、距離による体積のスケーリング特性に基づく定義を一般化したものです。^[3]最適な定義はアプリケーションによって異なります。

通常、次元は、たとえば線上の点のような密な集合について考えます。グラフのような離散的な設定では、次元は、サイズが無限大に近づくため、大規模システムの限界でのみ意味を持ちます。たとえば、統計力学では、異なる次元の規則的な格子上に位置する離散的な点を考慮します。このような研究は任意のネットワークに拡張されており、次元の定義をこれらのケースをカバーするように拡張する方法を検討することは興味深いことです。次元の定義を任意の大規模ネットワークに拡張する非常に単純で明白な方法は、距離 (グラフ内の 2 つのノードを接続する最短経路) が増加するにつれて、ボリューム (指定されたノードから指定された距離内にあるノードの数) がどのように増加するかを検討することです。物理学で発生する多くのシステムでは、これは確かに有用なアプローチです。この次元の定義は、連続システムのハウスドルフ次元の定義と同様に、強力な数学的基盤に置くことができます。数学的に堅牢な定義では、グラフのゼータ関数の概念を使用します。複雑ネットワーク ゼータ関数とグラフ サーフェス関数は、大規模なグラフを特徴付けるために導入されました。これらは言語分析のパターンの研究にも適用されています。このセクションでは、関数の定義を簡単に確認し、定義から導かれる関数の特性のいくつかについてさらに詳しく説明します。

ノードからノードまでの距離、つまり最初のノードから2番目のノードまでを結ぶ最短経路の長さをで表します。 ノードからノードまでの経路がない場合はとなります。 この定義では、複雑ネットワークのノードは距離空間内の点になります。^[2]この定義の単純な一般化を検討することができます。たとえば、重み付きエッジを検討することができます。 グラフ表面関数 は、ネットワークのすべてのノードについて平均した、特定のノードからちょうど の距離にあるノードの数として定義されます。 複雑ネットワークのゼータ関数は次のように定義されます 。${\displaystyle \textstyle r_{ij}}$${\displaystyle \textstyle i}$${\displaystyle \textstyle j}$${\displaystyle \textstyle r_{ij}}$${\displaystyle \textstyle \infty}$${\displaystyle \textstyle i}$${\displaystyle \textstyle j}$${\displaystyle \textstyle S(r)}$${\displaystyle \textstyle r}$${\displaystyle \textstyle \zeta _{G}(\alpha )}$

${\displaystyle \zeta _{G}(\alpha ):={\frac {1}{N}}\sum _{i}\sum _{j\neq i}r_{ij}^{-\alpha },}$

ここで、はグラフのサイズで、ノードの数で測定されます。がゼロのとき、すべてのノードは前の式の合計に等しく寄与します。つまり、は であり、 のときは発散します。指数が無限大に近づくとき、合計はノードに最も近い隣接ノードからのみ寄与を得ます。他の項はゼロに近づきます。したがって、 はグラフの平均次数に近づくにつれて になります。 ${\displaystyle \textstyle N}$${\displaystyle \textstyle \alpha}$${\displaystyle \textstyle \zeta _{G}(0)}$${\displaystyle \textstyle N-1}$${\displaystyle \textstyle N\rightarrow \infty }$${\displaystyle \textstyle \alpha}$${\displaystyle \textstyle \zeta _{G}(\alpha )}$${\displaystyle \textstyle <k>}$${\displaystyle \textstyle \alpha \rightarrow \infty }$

${\displaystyle \langle k\rangle =\lim _{\alpha \rightarrow \infty }\zeta _{G}(\alpha ).}$

全てのノードの平均を取る必要性は、ノードの上限の概念を使用することで回避でき、これにより、形式的に無限のグラフに概念を適用するのがはるかに簡単になります。^[4]定義は、ノードの距離の重み付き合計として表現できます。これにより、ディリクレ級数関係が得られます。

${\displaystyle \zeta _{G}(\alpha )=\sum _{r}S(r)/r^{\alpha }.}$

この定義は、いくつかのプロセスとそれらの次元への依存性を研究するためのショートカット モデルで使用されてきました。

${\displaystyle \textstyle \zeta _{G}(\alpha )}$は、の場合、 、の減少関数です。ノードの平均次数（グラフの平均配位数）が有限である場合、 、 の値は 1 つだけ存在し、その値で複雑ネットワークゼータ関数は無限から有限に遷移します。これは複雑ネットワークの次元として定義されています。既存のグラフにエッジを追加すると、ノード間の距離が減少します。これにより、 が内側に引っ張られるため、複雑ネットワークゼータ関数の値が増大します。新しいリンクがシステムの遠隔部分を接続する場合、つまり、距離がグラフサイズ として有限のままではない量だけ変化する場合は、次元が増加する傾向があります。距離がノルムを 使用して定義される正規の離散d次元格子の場合、${\displaystyle \textstyle \alpha}$${\displaystyle \textstyle \zeta _{G}(\alpha _{1})>\zeta _{G}(\alpha _{2})}$${\displaystyle \textstyle \alpha _{1} <\alpha _{2}}$${\displaystyle \textstyle \alpha}$${\displaystyle \textstyle \alpha _{transition}}$${\displaystyle \textstyle S(r)}$${\displaystyle \textstyle N\rightarrow \infty }$${\displaystyle \textstyle \mathbf {Z} ^{d}}$${\displaystyle \textstyle L^{1}}$

${\displaystyle \|{\vec {n}}\|_{1}=\|n_{1}\|+\cdots +\|n_{d}\|,}$

遷移は で発生します。 複雑ネットワークゼータ関数を使用した次元の定義は、単調性（サブセットはそれを含むセットよりも低い次元または同じ次元を持つ）、安定性（セットの和集合は、和集合を形成するコンポーネントセットの最大次元を持つ）、リプシッツ不変性^{[5] など}の特性を満たします。ただし、関係する操作により、グラフサイズがに近づくにつれて、ノード間の距離が有限量だけ変更されるという条件付きです。 複雑ネットワークゼータ関数を計算するアルゴリズムが提示されています。^[6]${\displaystyle \textstyle \alpha =d}$${\displaystyle \textstyle N}$${\displaystyle \textstyle \infty }$

1次元の正則格子の場合、グラフ表面関数はのすべての値に対してちょうど2です（2つの最も近い隣接点、2つの次の隣接点、など）。したがって、複素ネットワークゼータ関数はに等しく、 は通常のリーマンゼータ関数です。格子の特定の軸を選択し、選択した軸に沿った許容範囲の距離の断面を合計すると、以下の再帰関係が導き出されます。 ${\displaystyle \textstyle S_{1}(r)}$${\displaystyle \textstyle r}$${\displaystyle \textstyle \zeta _{G}(\alpha )}$${\displaystyle \textstyle 2\zeta (\alpha )}$${\displaystyle \textstyle \zeta (\alpha )}$

${\displaystyle S_{d+1}(r)=2+S_{d}(r)+2\sum _{i=1}^{r-1}S_{d}(i).}$

組合せ論から、正則格子の表面関数は次のように 書ける^[7]。

${\displaystyle S_{d}(r)=\sum _{i=0}^{d-1}(-1)^{i}2^{d-i}{d \choose i}{d+r-i-1 \choose d-i-1}.}$

与えられた指数で累乗された正の整数の合計を表す次の式は、のより高い値に対する表面関数を計算するのに役立ちます。 ${\displaystyle \textstyle k}$${\displaystyle \textstyle d}$

${\displaystyle \sum _{i=1}^{r}i^{k}={\frac {r^{k+1}}{(k+1)}}+{\frac {r^{k}}{2}}+\sum _{j=1}^{\lfloor (k+1)/2\rfloor }{\frac {(-1)^{j+1}2\zeta (2j)k!r^{k+1-2j}}{(2\pi )^{2j}(k+1-2j)!}}.}$

正の整数を与えられたべき乗で累乗した和を表す別の公式は、 ${\displaystyle \textstyle k}$

${\displaystyle \sum _{k=1}^{n}{\bigl (}{\begin{smallmatrix}n+1\ k\end{smallmatrix}}{\bigr )}\sum _{i=1}^{r}i^{k}=(r+1)((r+1)^{n}-1).}$

${\displaystyle \textstyle S_{d}(r)\rightarrow O(2^{d}r^{d-1}/\Gamma (d))}$ として。${\displaystyle \textstyle r\rightarrow \infty }$

いくつかの格子の複素ネットワークゼータ関数を以下に示します。

${\displaystyle \textstyle d=1}$  :${\displaystyle \textstyle \zeta _{G}(\alpha )=2\zeta (\alpha )}$

${\displaystyle \textstyle d=2}$  :${\displaystyle \textstyle \zeta _{G}(\alpha )=4\zeta (\alpha -1)}$

${\displaystyle \textstyle d=3}$  : )${\displaystyle \textstyle \zeta _{G}(\alpha )=4\zeta (\alpha -2)+2\zeta (\alpha }$

${\displaystyle \textstyle d=4}$  :${\displaystyle \textstyle \zeta _{G}(\alpha )={\frac {8}{3}}\zeta (\alpha -3)+{\frac {16}{3}}\zeta (\alpha -1)}$

${\displaystyle \textstyle r\rightarrow \infty }$ : (遷移点付近の場合)${\displaystyle \textstyle \zeta _{G}(\alpha )=2^{d}\zeta (\alpha -d+1)/\Gamma (d)}$${\displaystyle \alpha }$

ランダム グラフは、いくつかの頂点を持つネットワークで、各ペアは確率 で接続され、そうでなければペアは切断されます。ランダム グラフの直径は 2 で、確率は無限大 ( ) では 1 に近づきます。これを確認するには、2 つのノードと を考えます。または とは異なるノードの場合、が と の両方に同時に接続されていない確率は です。したがって、どのノードもと の間に 長さ のパスを提供しない確率は です。これは、システム サイズが無限大になると 0 になるため、ほとんどのランダム グラフでは、ノードは最大で長さ のパスによって接続されています。また、平均頂点次数は になります。大規模なランダム グラフの場合、ほぼすべてのノードは任意のノードから 1 または 2 の距離にあり、は、は であり、グラフのゼータ関数は ${\displaystyle \textstyle N}$${\displaystyle \textstyle p}$${\displaystyle \textstyle N\rightarrow \infty }$${\displaystyle \textstyle A}$${\displaystyle \textstyle B}$${\displaystyle \textstyle C}$${\displaystyle \textstyle A}$${\displaystyle \textstyle B}$${\displaystyle \textstyle C}$${\displaystyle \textstyle A}$${\displaystyle \textstyle B}$${\displaystyle \textstyle (1-p^{2})}$${\displaystyle \textstyle N-2}$${\displaystyle \textstyle 2}$${\displaystyle \textstyle A}$${\displaystyle \textstyle B}$${\displaystyle \textstyle (1-p^{2})^{N-2}}$${\displaystyle \textstyle 2}$${\displaystyle \textstyle p(N-1)}$${\displaystyle \textstyle S(1)}$${\displaystyle \textstyle p(N-1)}$${\displaystyle \textstyle S(2)}$${\displaystyle \textstyle (N-1)(1-p)}$

${\displaystyle \zeta _{G}(\alpha )=p(N-1)+(N-1)(1-p)2^{-\alpha }.}$