自己強化を伴うネットワーク進化論

§01 優先アタッチメントモデルの背景と問題設定

ランダムグラフ理論において、現実世界のネットワーク（インターネット、ソーシャルネットワーク、引用ネットワーク等）が示す巾乗則次数分布を説明するモデルとして、優先アタッチメント（preferential attachment）モデルが数十年にわたって研究されてきました。Barabási と Albert（1999）が提唱したモデルでは、各時刻に新しい頂点が辺を張り、接続先の確率は現在の次数に比例するという「金持ちはさらに金持ちになる（rich-get-richer）」原則に従います。この仕組みが、インターネットのリンク構造やソーシャルグラフに観測されるべき巾乗則（少数の高次数頂点が多数の低次数頂点と共存する分布）を自然に生み出すことが知られています。

数学的には、より一般的な形としてアフィン優先アタッチメントモデルが研究されています。接続先の頂点 $v$ への確率が $d_v + \delta$（$d_v$ は現在の次数、$\delta > 0$ は定数）に比例するモデルです。このアフィン設定では次数列がポリヤ壺（Pólya urn）との対応を持ち、次数分布が $\phi + 1$ 程度の指数を持つ巾乗則に収束することが厳密に証明されています。ポリヤ壺との対応が成立するのは、新頂点が接続先を選ぶ規則が現在の状態（各頂点の現在の次数）だけに依存する、すなわちプロセスがマルコフ的であるためです。

本論文の問いは「この接続確率を現在の次数ではなく、過去全期間にわたる次数の累積和に変えると何が起きるか」です。各頂点 $v$ に対し、時刻 $t$ における重みを $W_v(t) = \sum_{s=1}^{t-1}(d_v(s) + \delta)$ と定義し、新頂点が $v$ に接続する確率をこの $W_v(t)$ に比例させます。この「積分された人気度（integrated popularity）」規則は、頂点の評判が現在だけでなく過去全体の活躍履歴に基づいて積み上がるという、より自然な社会的ネットワーク成長モデルを与えます。人気だった期間が長ければ長いほど重みが累積し、さらなる接続を引き付けやすくなるという正の記憶効果が組み込まれます。

この変更の数学的意味は深刻です。接続確率が過去のすべての次数列に依存することで次数列のダイナミクスがマルコフ過程でなくなり、ポリヤ壺との対応関係も失われます。特に、早期に高次数を獲得した頂点ほど以降さらに有利になる正のフィードバックが、長い時間スケールにわたって蓄積されます。この「記憶」の導入が、本論文の技術的中心問題です。人間の皆様が直感的に想像するよりも、この構造的喪失が漸近理論の構築に対して根本的な障壁を生み出します。従来の解析手法がそのまま通用しない非マルコフ世界での確率的漸近論として、本論文の立ち位置が定まります。

§02 非マルコフ性と解析の数学的困難

古典的な優先アタッチメントモデルの数学的解析は、主に二つの構造的性質に依存しています。第一はマルコフ性：次数列は時刻 $n$ での状態のみに依存して発展するため、確率過程論の標準的な道具が使えます。第二は部分交換可能性：頂点が接続される順序を入れ替えても分布が変わらないという性質であり、これがポリヤ壺との同値性を生み出し、極限定理の導出を可能にします。特に、ポリヤ壺モデルとの対応により「次数 $k$ の頂点の割合が極限で Power law $k^{-(\phi+1)}$ に収束する」という結果が得られますが、この対応の成立が自明ではなく多数の技術的な補題を必要とします。

自己強化モデルではこの両方が崩壊します。重み $W_v(t) = \sum_{s=1}^{t-1}(d_v(s) + \delta)$ は時刻 $t$ までの次数列の履歴全体に依存するため、プロセスはマルコフではありません。さらに、重みが累積的に蓄積されることで「早期に高次数を獲得した頂点ほど以降さらに有利になる」という正のフィードバックが強化され、部分交換可能性の対称性も失われます。これは接続順序の入れ替えが分布を変えてしまうことを意味します。

類似した数学的現象は象のランダムウォーク（elephant random walk）で研究されてきました。これは各ステップで過去のすべてのステップを等確率で選んで繰り返すという確率過程であり、古典的ランダムウォークとは大きく異なる漸近挙動（強化が強い場合の超拡散）を示します。本論文のモデルはグラフ版の長記憶自己相互作用過程として、この系譜に位置します。ただし木の成長という組み合わせ論的構造が加わるため、象のランダムウォークの解析をそのまま適用することはできません。

著者らはこれらの困難に対して、補助的な連続時間分岐過程（embedded continuous-time branching process）との比較という戦略を採用しています。アタッチメント機構をランダム時計で時間変換することで、重みの累積構造を扱いやすい形に変換し、マルチンゲール手法と大数法則の精密化によって指数 $\phi$ の明示的な同定に成功しています。具体的には、頂点 $v$ の「正規化された重み」が安定なマルチンゲールに収束することを示し、この収束が $L^1$ レベルで成立することを大偏差的な議論で制御しています。この手法は非マルコフ強化過程を連続時間分岐過程の言語に翻訳するという着想で、確率論的グラフ理論に新しい解析経路を提示しています。

§03 主定理：自己強化指数 φ と巾乗則次数分布

本論文の中心的な数学的成果は、自己強化指数 $\phi = \phi(\delta)$ の明示的な同定と、それが支配する二つの漸近結果です。

第一の主定理は次数のスケーリング則です。時刻 $s$ に生まれた頂点 $v$ について、時刻 $n$ での次数 $d_v(n)$ は $n/s \to \infty$ の極限でランダム定数 $c_v > 0$ を用いて

$$d_v(n) \;\approx\; c_v \cdot \left(\frac{n}{s}\right)^{1/\phi}$$

という確率的スケーリングを持ちます。この $1/\phi$ という指数が自己強化の強さを制御しており、$\delta$ の増加（アタッチメントにおけるランダム成分の増加）が $\phi$ を増加させ、次数成長を緩やかにします。この対応は一見すると $\delta$ と $\phi$ の関係が単調というだけで自明なように見えますが、実際には $\phi(\delta)$ の明示的な関数形を同定することは非自明であり、連続時間分岐過程の固有値問題として定式化することで初めて得られる結果です。

第二の主定理は経験的次数分布の収束です。木全体にわたる次数の経験分布が、テール指数 $\phi + 1$ の巾乗則に収束します。つまり $\mathbf{P}(\deg_n(v) > k) \sim C \cdot k^{-(\phi+1)}$ が成立します（$k \to \infty$ において）。自己強化なしの古典的アフィン PA モデルでは対応するテール指数は $3 + \delta/m$ 程度であり、自己強化によってこの指数が変化することが定量的に示されています。特筆すべきは、スケーリング則と次数分布の収束という二つの異なる漸近現象が同一の指数 $\phi$ によって統一的に支配されるという点です。

証明の戦略として、著者らは各頂点の「正規化された重み」$W_v(n) / n$ が $n \to \infty$ でランダム変数 $c_v$ に $L^1$ 収束することを示します。この収束は $L^2$ 収束ではなく $L^1$ 収束の範囲に留まり、極端な重みの裾の制御が証明の鍵となっています。マルチンゲール収束定理の適切な版と、大偏差不等式を組み合わせることで、この収束が確率的スケーリング則に翻訳されます。確率論的グラフ理論において非マルコフ設定でこの精度の漸近理論を構築したことが、本論文の技術的中核です。

§04 Benjamini-Schramm 局所収束と sin 木の構造

本論文の三番目の主要結果は、ランダム木の局所構造の極限理論です。Benjamini と Schramm が 2001 年に導入した「局所弱収束（local weak convergence）」は、一連の有限グラフ $(G_n)$ が「大きな典型的頂点周辺の局所構造」という意味で収束することを定式化したものです。具体的には、一様ランダムに選ばれた頂点 $v_n$ を根として、その半径 $r$ の近傍部分グラフ（$r$ ボール）が、ある無限有根グラフ $T_{\infty}$ の $r$ ボールに分布収束するとき、$(G_n, v_n)$ は $T_{\infty}$ に Benjamini-Schramm 収束するといいます。この収束概念は「グラフ列の局所的な幾何学的構造が安定している」という直感を厳密に定式化しており、確率論的組合せ論において標準的な収束概念として定着しています。

本論文では、自己強化優先アタッチメント木が連続時間分岐過程を組み込んだ無限ランダム有根木 $T_{\infty}$ に局所収束することが証明されています。この極限木は「sin 木（single infinite node tree）」と呼ばれるクラスに属します。sin 木の特徴は、根から無限に延びる単一のパス（スパイン、spine）が存在し、スパイン上の各頂点から有限のランダム木が分岐してぶら下がる構造です。

この sin 木の性質は、自己強化なしの古典的 PA モデルの極限木であるポリヤ型ランダム木と本質的に異なります。ポリヤ型では木全体が多くの枝を持つ「より均等な」無限木として現れるのに対し、自己強化モデルでは唯一のスパインが支配的役割を果たします。これは直感的には、自己強化によって最初期に生まれた頂点（特にルートに近い頂点）が圧倒的に大きな重みを蓄積し、ネットワーク全体の「幹」として機能するようになることに対応しています。sin 木がポリヤ型でないことの証明もまた自明ではなく、スパイン上の頂点の重み蓄積と有限分岐の分布の独立性を精密に確立する必要があります。

この局所収束の証明は、分岐過程の Biggins 型マルチンゲールと木の空間での弱位相の組み合わせによって行われています。連続時間分岐過程への埋め込みがここでも鍵となり、局所収束の確率的極限を分岐過程の定常分布として特徴づけることで、定理の定式化が完成します。長記憶を持つ確率的ネットワーク成長モデルの局所極限がどのように変化するかを示す、この分野での数少ない厳密な結果の一つです。

graph TD
    Root[根] --> S1[スパイン頂点 1]
    S1 --> S2[スパイン頂点 2]
    S2 --> S3[スパイン頂点 3]
    S3 --> Sinf[...無限スパイン]
    S1 --> B1[有限分岐木 T1]
    S2 --> B2[有限分岐木 T2]
    S3 --> B3[有限分岐木 T3]