ネットワーク上のフラクタル次元

フラクタル解析は、コンピュータシステム、脳、ソーシャルネットワークなど、自然システムと人工システムの両方に存在する複雑なネットワークの研究に役立ち、ネットワーク科学の分野のさらなる発展を可能にします。

多くの実際のネットワークには、スケールフリー特性とスモールワールド特性という2 つの基本的な特性があります。ネットワークの次数分布がべき乗法則に従う場合、ネットワークはスケールフリーです。ネットワーク内の任意の 2 つのノードを非常に少ないステップ数で接続できる場合、ネットワークはスモールワールドであると言われます。

スモールワールド特性は、ネットワークの平均直径がゆっくりと増加し、ノードの総数が増加するという数学的に表現できる。 ${\displaystyle N}$

${\displaystyle \left\langle l\right\rangle \sim \ln {N}}$

ここで、2 つのノード間の最短距離です。 ${\displaystyle l}$

同様に:

${\displaystyle N\sim e^{\left\langle l\right\rangle /l_{0}}}$

ここで、 は特性長さです。 ${\displaystyle l_{0}}$

自己相似構造の場合、上記の指数関係ではなく、べき乗関係が予想されます。この事実から、スモールワールドネットワークは長さスケール変換の下では自己相似ではないと思われます。

タンパク質の溶媒アクセス可能な表面領域で自己相似性が発見されました。^{[1] [2]タンパク質は球状の}折り畳まれた鎖を形成するため、この発見はタンパク質の機能性の特徴的な動的長さスケールを確立するために使用できるため、タンパク質の進化とタンパク質のダイナミクスに重要な意味を持ちます。^[3]

フラクタル次元は、ボックスカウンティング法やクラスター成長法などの方法を使用して計算できます。

与えられたネットワークをカバーするために必要な 線形サイズのボックスの数を とし ます。フラクタル次元は次のように表されます。 ${\displaystyle N_{B}}$${\displaystyle l_{B}}$ ${\displaystyle d_{B}}$

${\displaystyle N_{B}\sim l_{B}^{-d_{B}}}$

これは、大きさのボックス内の頂点の平均数が${\displaystyle \left\langle M_{B}\left(l_{B}\right)\right\rangle }$${\displaystyle l_{B}}$

${\displaystyle \left\langle M_{B}\left(l_{B}\right)\right\rangle \sim l_{B}^{d_{B}}}$

異なるボックス サイズでの の分布を測定するか、異なるボックス サイズでの の分布を測定することで、分布のべき乗法則フィッティングによって フラクタル次元を取得できます。${\displaystyle N}$${\displaystyle \left\langle M_{B}\left(l_{B}\right)\right\rangle }$ ${\displaystyle d_{B}}$

1つのシードノードがランダムに選択される。最小距離が与えられれば、シードノードから最大で離れたノードのクラスターを形成できる。クラスターがネットワーク全体をカバーするまで、多数のシードを選択してこの手順を繰り返す。その後、次元は次のように計算できる。 ${\displaystyle l}$${\displaystyle l}$${\displaystyle d_{f}}$

${\displaystyle \left\langle M_{C}\right\rangle \sim l^{d_{f}}}$

ここで、はクラスターの平均質量であり、クラスター内のノードの平均数として定義されます。 ${\displaystyle \left\langle M_{C}\right\rangle }$

ネットワークは一般に別の空間に埋め込まれていないため、これらの方法をネットワークに適用するのは困難です。ネットワークのフラクタル次元を測定するために、再正規化の概念を追加します。

ネットワークの自己相似性を調べるには、再正規化によるボックス カウンティング法を使用できます。各サイズl _Bについて、ネットワークがカバーされるまでボックスがランダムに選択されます (クラスター成長法の場合と同様)。ボックスはすべて距離l  <  l _Bで分離されたノードで構成されます。つまり、ボックス内のすべてのノード ペアは、最大でl _{B の}リンクの最小パスで分離されている必要があります。次に、各ボックスをノードに置き換えます (再正規化)。再正規化されていないボックス間に少なくとも 1 つのリンクがある場合、再正規化されたノードは接続されます。この手順は、ネットワークが 1 つのノードに崩壊するまで繰り返されます。これらのボックスにはそれぞれ有効質量 (ボックス内のノードの数) があり、これを使用して上記のようにネットワークのフラクタル次元を測定できます。

このプロットは、ワールドワイドウェブ上のボックスサイズの関数として実行される再正規化における次数分布P ( k ) の不変性を示しています。ネットワークは、固定ボックスサイズl _Bに適用された複数の再正規化に対しても不変性があります。この不変性は、ネットワークが複数の長さスケールで自己相似であることを示唆しています。

ネットワークのフラクタル特性は、その基礎となるツリー構造に見ることができます。この見方では、ネットワークはスケルトンとショートカットで構成されています。スケルトンは、最高の媒介中心性を持つエッジによって形成される特別なタイプのスパニングツリーであり、ネットワーク内の残りのエッジはショートカットです。元のネットワークがスケールフリーの場合、そのスケルトンもべき乗法則の次数分布に従いますが、次数は元のネットワークの次数とは異なる場合があります。フラクタルスケーリングに従うフラクタルネットワークの場合、各スケルトンは元のネットワークと同様のフラクタルスケーリングを示します。スケルトンをカバーするボックスの数は、ネットワークをカバーするために必要な数とほぼ同じです。^[4]

フラクタルネットワークとその骨格は、

${\displaystyle \left\langle M_{B}\left(l_{B}\right)\right\rangle \sim l_{B}^{d_{B}}}$、

ネットワークはフラクタルかどうか分類することができ、フラクタル次元を求めることができる。例えば、WWW、人間の脳、代謝ネットワーク、H . sapiensのタンパク質相互作用ネットワーク（PIN） 、S . cerevisiaeのPINはフラクタルネットワークであると考えられる。さらに、測定されたフラクタル次元は、それぞれのネットワークのものである。一方、インターネット、アクターネットワーク、人工モデル（例えば、BAモデル）はフラクタル特性を示さない。^{[5] [6]}${\displaystyle d_{B}=4.1,{\mbox{ }}3.7,{\mbox{ }}3.4,{\mbox{ }}2.0,{\mbox{ and }}1.8}$

複雑なネットワーク やグラフの次元の最適な定義は、アプリケーションによって異なります。たとえば、メトリック次元は、グラフの解決セットの観点から定義されます。上記の距離で定義された「質量」のスケーリング特性に基づく定義^[7]や、複雑なネットワークのゼータ関数 に基づく定義^[8]も研究されています。