スケールフリーネットワーク

バラバシ・アルバート・モデルを用いて生成した15万頂点・平均次数6のネットワークの次数分布（青点）。分布は2つのガンマ関数の比で与えられる解析的形（黒線）に従い、これは冪乗則で近似される。

テンプレート:ネットワーク科学 スケールフリーネットワーク（テンプレート:Lang-en-short）とは、少なくとも漸近的には次数分布が冪乗則に従うような（ネットワークである。すなわち、他のノードと k 個の接続を持つノードの割合 P(k) は、k が大きいところで

$P(k)\sim k^{\mathit{-}𝜸}$

のように振る舞う。$\gamma$ は典型的には $2<\gamma <3$ の範囲にあるパラメータである（この範囲では $k^{\mathit{-}𝜸}$ の第二モーメント（スケールパラメータ）は無限大だが第一モーメントは有限）。ただし、まれにこの範囲外になることもある。「スケールフリー」という名前は、次数分布のあるモーメントが定義されないため、ネットワークが特徴的なスケール（「サイズ」）を持たないという事実によって説明できる。

実在するネットワークにおける冪乗則的な次数分布を説明する機構として、選好的接続と適応度モデルが提案されてきた。超線形選好的接続や第二近隣選好的接続のような代替モデルは一時的にスケールフリーネットワークを生成するように見えるが、ネットワークが非常に大きくなると次数分布は冪乗則から逸脱する。

歴史

科学論文間の引用の研究において、デレック・プライスは1965年に、論文が受ける引用数がパレート分布ないし冪乗則に従う裾の重い分布となることを示した。1976年の後の論文で、プライスは引用ネットワークにおける冪乗則の発生を説明する機構を提案し、それを「累積的優位」（cumulative advantage）と呼んだ。しかし、これらはいずれも引用をスカラー量として扱っており、新しいクラスのネットワークの基本的特徴としては扱っていなかった。

スケールフリーネットワークへの関心は1999年、ノートルダム大学のバラバーシ・アルベルト・ラースローとレカ・アルベルトによる研究で始まった。彼らはWorld Wide Webの一部のトポロジーをマッピングし、「ハブ」と呼んだ一部のノードが他よりもはるかに多くの接続を持ち、ネットワーク全体としてもノードへのリンク数が冪乗則分布になることを見出した。続く論文でバラバーシとアルベルトは、冪乗則がWWW固有の性質ではなくいくつかの実在ネットワークにも見られる特徴であることを示し、冪乗則的な次数分布を示すネットワークのクラスを記述する用語として「スケールフリーネットワーク」を提唱した。

バラバーシとアルベルトは冪乗則分布の出現を説明する生成機構を提案し、これを「選好的接続」と呼んだ。この機構の解析解は2000年に Dorogovtsev、Mendes、Samukhin によって、また独立に Krapivsky、Redner、Leyvraz によって提示され、その後数学者のベラ・バラバシによって厳密に証明された。

概観

「スケールフリー」の概念がネットワークの文脈で最初に導入されたとき、それは主に特定の性質、すなわち変数 $k$ が $f(k)\propto k^{-\gamma }$ と表される冪乗則分布を指していた。この性質は連続的なスケール変換 $k\to k+ϵk$ の下で形を保つというものであり、統計的場の理論におけるくりこみ群の手法との類似を想起させる。

ただし重要な違いがある。統計的場の理論では「スケール」は多くの場合系のサイズに関するものである。一方ネットワークの領域では、「スケール」 $k$ は接続性の尺度であり、一般にはノードの次数、すなわちそこに接続されたリンクの数によって定量化される。高次数のノードをより多く含むネットワークは、より高い接続性を持つとみなされる。

冪乗則的な次数分布により、高次数ノードの出現頻度について「スケールフリー」な主張を行うことができる。たとえば「平均的な接続性の3倍の接続性を持つノードは、平均的な接続性のノードの半分の頻度で現れる」と言える。「平均的な接続性」を何とするかの具体的な数値は、100であれ100万であれ本質的ではない。

特徴

ランダムネットワーク (a) とスケールフリーネットワーク (b)

ランダムネットワークとスケールフリーネットワークの複雑ネットワーク次数分布

スケールフリーネットワークの最も顕著な特徴は、平均を大きく上回る次数を持つ頂点が相対的に多いことである。最も高い次数を持つノードはしばしば「ハブ」と呼ばれ、それぞれのネットワークにおいて特定の役割を果たしていると考えられているが、これは分野に大きく依存する。ランダムネットワークでは最大次数（予想される最大ハブのサイズ）は k_max~ log N とスケールし、N をネットワークサイズとすると非常に遅い依存性しか示さない。対照的にスケールフリーネットワークでは最大ハブは k_max~ ~N^1/(γ−1) とスケールし、ハブがネットワークサイズに対して多項式的に増加することを示す。

スケールフリーネットワークの重要な特徴は高い次数不均一性 κ = <k²>/<k> であり、これはネットワーク頑健性から疫病伝播、ネットワーク同期に至るまで、ネットワークベースの多くの過程を支配する。ランダムネットワークでは κ = <k> + 1 となり、この比はネットワークサイズ N に依存しないが、スケールフリーネットワークでは κ~ N^{(3−γ)/(γ−1)} となりネットワークサイズとともに増加する、すなわち次数不均一性が増大することを意味する。

クラスタリング

スケールフリーネットワークのもう一つの重要な特徴は、クラスタリング係数の分布がノード次数の増加とともに減少することである。この分布もまた冪乗則に従う。これは低次数ノードが非常に密な部分グラフに属し、それらの部分グラフ同士がハブを介して相互接続されていることを意味する。ノードを人、リンクを人と人の知り合い関係とする社会的ネットワークを考えると、人はコミュニティ、すなわち全員が全員を知っている小集団（完全グラフとみなせる）を形成する傾向があることが容易に理解できる。さらに、コミュニティの成員はコミュニティの外部の人々ともいくつかの知り合い関係を持つ。しかし一部の人々（セレブリティや政治家など）は多数のコミュニティに接続しており、そうした人々はスモール・ワールド現象の原因となるハブとみなせる。

現在のところ、スケールフリーネットワークのより具体的な特性は、それを作り出す生成機構によって異なる。たとえば選好的接続によって生成されたネットワークは典型的には高次数頂点をネットワークの中央に配置し、それらを相互接続してコアを形成し、次第に低い次数のノードがコアと周縁の間の領域を構成する。この場合、頂点の大部分をランダムに除去してもネットワーク全体の連結性への影響はほとんどなく、こうしたトポロジーがセキュリティ上有用である可能性を示唆する一方、標的型攻撃は連結性を急速に破壊する。高次数頂点を周縁に配置するその他のスケールフリーネットワークは、これらの性質を示さない。同様に、スケールフリーネットワークのクラスタリング係数も他のトポロジーの詳細によって大きく異なり得る。

免疫化

インターネットや社会的ネットワークのような現実的なネットワークを表すスケールフリーネットワークを効率的に免疫化する方法は広く研究されてきた。そのような戦略の一つは最大次数ノードの免疫化、すなわち標的型（意図的）攻撃への対応であり、この場合は臨界確率 p$c$ が比較的高く、免疫化が必要なノード数が少なくて済む。 しかし多くの現実的なケースでは大域構造が利用可能でなく、最大次数ノードが未知であることも多い。

ランダムグラフの性質はグラフ変換の下で変化したり不変であったりする。たとえば Mashaghi A. らは、ランダムグラフをその辺双対グラフ（または線グラフ）へ変換する操作が、ほぼ同じ次数分布を持ちながら次数相関と有意に高いクラスタリング係数をもつグラフのアンサンブルを生むことを示した。したがってスケールフリーグラフはこの種の変換の下でもスケールフリーのままである。

例

スケールフリーであることが判明したネットワークの例:

• 共同研究ネットワークを含む一部の社会的ネットワーク。広く研究されている2つの例は、映画出演者のコラボレーションと数学者による論文共著。
• インターネット、World Wide Webのウェブグラフ、ソフトウェアモジュール依存グラフなど、多くの種類のコンピュータネットワーク
• 銀行間決済ネットワークなど一部の金融ネットワーク
• タンパク質間相互作用ネットワーク
• 意味ネットワーク
• 航空路ネットワーク

高温超伝導体にもスケールフリーなトポロジーが見出されている。高温超伝導体の性質 — 電子が量子物理の法則に従い摩擦なく完璧に同期して流れる化合物 — は、一見ランダムな酸素原子のフラクタル的配置と格子歪みに関係しているように見える。

生成モデル

スケールフリーネットワークは偶然だけでは生じない。Erdős と Rényi（1960）は、各ステップで2つのノードを一様ランダムに選びその間にリンクを挿入するグラフ成長モデルを研究した。これらのランダムグラフの性質はスケールフリーネットワークで見られる性質とは異なるため、この成長過程のためのモデルが必要となる。

スケールフリーネットワークの一部に対する最もよく知られた生成モデルは、バラバーシとアルバートの（1999年）「金持ちはより金持ちに」生成モデルであり、ここでは各新規Webページが既存のWebページへのリンクを、一様ではなく現在の被リンク数（in-degree）に比例する確率分布で作る。この過程により、多くの被リンクを持つページは通常のページよりも多くの被リンクを引き付けることになる。これは冪乗則を生成するが、結果として得られるグラフは小さな密なコミュニティの存在といった他の性質において実際のWebグラフとは異なる。より一般的なモデルやネットワーク特性が提案され研究されてきた。たとえば Pachon ら（2018）は、選好的接続機構と最新ノードのみへの一様選択という2つの異なる接続ルールを考慮に入れた「金持ちはより金持ちに」生成モデルの変種を提案した。レビューについては Dorogovtsev とMendes の書籍を参照。テンプレート:要出典 超線形選好的接続や第二近隣接続のような機構は一時的にスケールフリーなネットワークを生成するが、ネットワークが大きくなるにつれて冪乗則から逸脱する。

Webリンクに対してやや異なる生成モデルが Pennock ら（2002）によって提案されている。彼らは大学や上場企業、新聞、科学者などの特定の話題に関心を持つコミュニティを調べ、Webの主要なハブを除外した。この場合リンクの分布はもはや冪乗則ではなく正規分布に近いものとなった。これらの観察に基づき、著者らは選好的接続と、リンクを獲得する基礎確率とを混合した生成モデルを提案した。

もう一つの生成モデルは Kumar ら（2000）が研究したコピーモデルであり、新しいノードが既存のノードをランダムに選び、そのノードのリンクの一部をコピーする。これも冪乗則を生成する。

バラバシ・アルバート・モデルにおける冪乗則分布の出現を説明する主要な要素は2つある: 成長と選好的接続である。 「成長」とは、長期間にわたり新しいノードが既存のシステム、ネットワークに参加する成長過程を意味する（10年間で数十億のページに成長したWorld Wide Webのように）。「選好的接続」とは、新しいノードが既に他者とのリンクを多数持つノードに接続することを好むことを意味する。したがって既に多くのリンクを持つノードにますます多くのノードがリンクする確率が高くなり、最終的にそのノードはハブとなる。 ネットワークに応じてハブは同質配向的（assortative）にも異質配向的（disassortative）にもなり得る。同質配向性は、接続性の高い/有名な人々同士が互いによく知り合う傾向がある社会的ネットワークで見られる。異質配向性は、技術的（インターネット、World Wide Web）および生物学的（タンパク質相互作用、代謝）ネットワークで見られる。

しかし、ネットワークの成長（新しいノードの追加）はスケールフリーネットワークを作るための必要条件ではない（ Dangalchev参照）。一つの可能性（Caldarelli ら 2002）は、構造を静的なものとみなし、関係する2頂点の特定の性質に従って頂点間にリンクを引くことである。これらの頂点の性質（適応度 fitness）の統計的分布を指定すると、状況によっては静的なネットワークもスケールフリーな性質を発達させることが分かる。

一般化スケールフリーモデル

スケールフリーな複雑ネットワークのモデリングでは研究が爆発的に拡大した。バラバーシとアルバートの手法は、いくつもの変種と一般化および以前の数学的成果の刷新によって受け継がれた。

今日の用語では、複雑ネットワークの任意の指標が冪乗則分布を持つならば、それは一般的にスケールフリーネットワークとみなされる。同様に、この特徴を持つ任意のモデルはスケールフリーモデルと呼ばれる。

特徴

多くの実在ネットワークは（ほぼ）スケールフリーであり、それゆえ記述するためにスケールフリーモデルが必要となる。Price の方式では、スケールフリーモデルを構築するために2つの材料が必要である:

1. ノードの追加または除去。通常はネットワークを成長させる、すなわちノードの追加に集中する。

2. 選好的接続: 新しいノードが「古い」ノードに接続される確率 $\mathrm{\Pi }$。

一部のモデル（ Dangalchevや下記の適応度モデル参照）はノード数を変えることなく静的に動作できることに注意。また「選好的接続」モデルがスケールフリーネットワークを生み出すという事実は、実世界のスケールフリーネットワークの進化の根底にある機構がこれであることの証明ではないことにも留意すべきである。実際のシステムでは異なる機構が働いていても、やはりスケーリングが生じる可能性がある。

例

スケールフリーネットワークの性質を生成しようとする試みがいくつかなされてきた。以下に例を挙げる:

バラバシ・アルバート・モデル

バラバシ・アルバート・モデルはPrice モデルの無向版であり、線形の選好的接続 $\mathrm{\Pi }(k_i)=\frac{k_i}{\sum _j{k}_j}$ を持ち、各時間ステップで1つの新しいノードを追加する。

（なお、実在ネットワークにおける $\mathrm{\Pi }(k)$ のもう一つの一般的特徴は $\mathrm{\Pi }(0)\ne 0$、すなわち新しいノードが孤立ノードに接続される非ゼロの確率が存在することである。したがって一般に $\mathrm{\Pi }(k)$ は $\mathrm{\Pi }(k)=A+k^{\alpha }$ の形を持ち、$A$ はノードの初期魅力である。）

2レベルネットワークモデル

Dangalchev（参照）は、選好的接続において対象ノードの各近傍の重要性を考慮することにより2-Lモデルを構築した。2-Lモデルにおけるノードの魅力は、それにリンクされたノードの数だけでなく、それらの各ノードのリンク数にも依存する。

$\mathrm{\Pi }(k_i)=\frac{k_i+C\sum _{(i,j)}{k}_j}{\sum _j{k}_j+C\sum _j{k}_j^2},$

ここで C は0から 1の間の係数である。

2-Lモデルの変種である k2 モデル（第一および第二近隣ノードが対象ノードの魅力に等しく寄与する）は、一時的なスケールフリーネットワークの出現を実証する。k2 モデルでは、次数分布はネットワークが比較的小さい間はほぼスケールフリーに見えるが、ネットワークが大きくなるとスケールフリー領域からの有意な逸脱が生じる。この結果、異なる次数を持つノードの相対的魅力が時間とともに変化し、この特徴は実在のネットワークでも観察されている。

非線形選好的接続

テンプレート:See also バラバシ・アルバート・モデルは、ノード $i$ に接続される確率 $\mathrm{\Pi }(k)$ がノード $i$ の次数 $k$ に比例すると仮定する。この仮定は2つの仮説を含む。第一に、$\mathrm{\Pi }(k)$ は $k$ に依存すること（$\mathrm{\Pi }(k)=p$ であるランダムグラフとは対照的）。第二に、$\mathrm{\Pi }(k)$ の関数形が $k$ について線形であること。

非線形選好的接続では $\mathrm{\Pi }(k)$ の形が線形でなく、最近の研究により次数分布が関数 $\mathrm{\Pi }(k)$ の形状に強く依存することが実証されている。

Krapivsky、Redner、Leyvrazは、非線形選好的接続ではネットワークのスケールフリー性が破壊されることを実証した。ネットワークのトポロジーがスケールフリーとなる唯一のケースは、選好的接続が漸近的に線形である場合、すなわち $k_i\to \mathrm{\infty }$ のとき $\mathrm{\Pi }(k_i)\sim a_{\mathrm{\infty }}{k}_i$ となる場合である。この場合、速度方程式は

$P(k)\sim k^{-\gamma }\text{ with }\gamma =1+\frac{\mu }{a_{\mathrm{\infty }}}.$

を導く。このようにして次数分布の指数は2から $\mathrm{\infty }$ の間の任意の値に調整できる。テンプレート:要説明

階層的ネットワークモデル

階層的ネットワークモデルは設計上スケールフリーであり、高いノードクラスタリングを持つ。

反復的な構成により階層的ネットワークが導かれる。5ノードの完全連結クラスタから出発し、4つの同一の複製を作り、各クラスタの周縁ノードを元のクラスタの中央ノードに接続する。これにより25ノードのネットワーク（N = 25）が得られる。 同じ過程を繰り返すことで、元のクラスタの4つの複製をさらに作ることができ、各々の4つの周縁ノードが第一ステップで作られたノードの中央ノードに接続する。これにより N = 125 となり、この過程は無限に続けられる。

適応度モデル

このアイデアは、2頂点間のリンクがすべての頂点ペアに等しい確率 p でランダムに割り当てられるのではなく、各頂点 j に内在的な適応度（fitness） x_j が存在し、頂点 i と j の間のリンクが確率 $p(x_i,x_j)$ で作られるというものである。 World Trade Web の場合、各国の適応度としてGDPを用いることで、すべての性質を再構成できる。その際

$p(x_i,x_j)=\frac{\delta x_i{x}_j}{1+\delta x_i{x}_j}.$

を用いる。

双曲幾何グラフ

テンプレート:Main ネットワークが基礎として双曲幾何を持つと仮定すると、空間ネットワークの枠組みを利用してスケールフリーな次数分布を生成できる。この異質な次数分布は単に基礎となる双曲幾何の負の曲率と計量的性質を反映している。

辺双対変換による所望の性質を持つスケールフリーグラフの生成

低い次数相関とクラスタリング係数を持つスケールフリーグラフから出発し、辺双対変換を適用することで、はるかに高い次数相関とクラスタリング係数を持つ新しいグラフを生成できる。

一様選好的接続モデル（UPAモデル）

UPAモデルは選好的接続モデルの変種（Pachon らによる提案）であり、「金持ちはより金持ちに」システムを重視する選好的接続機構（確率 1−p）と、最新のノードに対する一様選択（確率 p）という2つの異なる接続ルールを考慮に入れる。この修正は次数分布のスケールフリー挙動の頑健性を研究する上で興味深い。漸近的な冪乗則次数分布が保存されることは解析的に証明されている。

スケールフリー理想ネットワーク

ネットワーク理論の文脈において、スケールフリー理想ネットワークとは、スケールフリー理想気体の密度分布に従う次数分布を持つランダムネットワークである。競争的クラスタ成長過程をネットワークに適用するとき、これらのネットワークは複雑ネットワーク上の情報理論により社会的集団のサイズ分布を解明することで、都市規模分布や選挙結果を再現できる。スケールフリー理想ネットワークのモデルでは、『六次の隔たり』として知られる現象の原因がダンバー数であることを実証できる。

新しい特徴

n ノードと冪乗則指数 $\gamma >3$ を持つスケールフリーネットワークにおいて、次数が $\log n\times {\log }^{\ast }n$ より大きい頂点で構成される誘導部分グラフは、概確実に ${\gamma }^{\prime }=2$ のスケールフリーネットワークである。

スケールフリー指標

理論的レベルでは、スケールフリーの抽象的定義への改良が提案されてきた。たとえば Li ら（2005）は、潜在的により正確な「スケールフリー指標」を提示した。手短に言えば、G を辺集合 E を持つグラフとし、頂点 $v$ の次数（$v$ に接続する辺の数）を $\mathrm{deg}(v)$ と書き、

$s(G)=\sum _{(u,v)\in E}\mathrm{deg}(u)\cdot \mathrm{deg}(v).$

と定義する。これは高次数ノードが他の高次数ノードに接続されているときに最大化される。次に

$S(G)=\frac{s(G)}{s_{max}},$

を定義する。ここで s_max は G と同一の次数分布を持つすべてのグラフの集合にわたる s(H) の最大値である。これにより0から1の間の指標が得られ、小さい S(G) を持つグラフ G は「スケールリッチ」（scale-rich）、S(G) が1に近いグラフ G は「スケールフリー」となる。この定義は「スケールフリー」という名前に含まれる自己相似の概念を捉えている。

冪乗則指数の推定

スケールフリーネットワークの冪乗則指数 $\gamma$ の推定は、典型的には少数のランダムに抽出したノードの次数を用いた最尤推定によって行われる。しかし一様抽出では冪乗則次数分布の重要な裾の重い部分から十分な標本が得られないため、この方法は大きなバイアスと分散をもたらしうる。近年、友情のパラドックスの結果として次数分布の裾から来る可能性がより高い「ランダムフレンド」（すなわちランダムリンクのランダム端点）を抽出することが提案された。理論的には、ランダムフレンドを用いた最尤推定は一様抽出に基づく古典的手法と比べてより小さいバイアスと分散をもたらす。

すべてのネットワークがスケールフリーなわけではない

社会的・生物学的・技術的システムにおけるスケールフリー性の広範な存在は、すべての実在ネットワークがスケールフリーであることを意味しない。むしろ、結晶質または非晶質材料中の原子間の結合を記述する材料科学に現れるネットワークのように、この性質を共有しない重要なネットワークがいくつかある。これらのネットワークでは各ノードが化学によって決まる同一の次数を持つ。また、線虫 C. elegans の神経ネットワークや、送電線で接続された発電機と開閉器からなる電力網は、指数関数的な次数分布を持つことが示されている。さらに、実世界のネットワークの中にはスケールフリー性の強弱があり、社会的ネットワークは弱くスケールフリーな傾向があるのに対し、一部の技術的・生物学的ネットワークは強くスケールフリーになり得る。

関連項目

• テンプレート:仮リンク
• テンプレート:仮リンク
• テンプレート:仮リンク
• テンプレート:仮リンク
• スケール不変性
• 複雑ネットワーク
• テンプレート:仮リンク
• テンプレート:仮リンク
• テンプレート:仮リンク

参考文献（追加）

• テンプレート:Cite journal
• テンプレート:Cite journal
• テンプレート:Cite book
• テンプレート:Cite journal
• テンプレート:Cite journal
• Caldarelli G. "Scale-Free Networks" Oxford University Press, Oxford (2007).
• テンプレート:Cite journal
• テンプレート:Cite journal
• テンプレート:Cite journal
• テンプレート:Cite book
• テンプレート:Cite journal
• テンプレート:Cite journal
• テンプレート:Cite book
• テンプレート:Cite journal
• テンプレート:Cite arXiv
• テンプレート:Cite conference
• テンプレート:Cite news
• テンプレート:Cite journal
• テンプレート:Cite book
• テンプレート:Cite journal
• Robb, John. Scale-Free Networks and Terrorism, 2004.
• テンプレート:Cite journal
• テンプレート:Cite journal
• テンプレート:Cite journal