# 優先的選択 ## 定義 優先的選択(preferential attachment)とは、成長するネットワークにおいて新規に追加される頂点・辺が、既存頂点の次数(または in-degree)に比例した確率でその頂点へ接続する成長メカニズムである。既存次数が高い頂点ほど新規接続を獲得しやすく、社会学ではこの性質をマシュー効果(Matthew effect、「持てる者はますます与えられる」)と呼ぶ。Derek de Solla Priceは1965年、引用ネットワーク(論文間の被引用)の成長にこの考えを適用し累積優位性(cumulative advantage)と名付けた。後にAlbert-László BarabásiとRéka Albertが無向ネットワーク版のモデルを提案した際にこれを優先的選択と呼び直し、以後この名称が定着した([[@2003__SIAMReview__The structure and function of complex networks - Chapter 7 Models of network growth]])。 優先的選択が線形(既存次数にちょうど比例)であるとき、成長モデルの定常次数分布はべき乗則の裾を持つ。付着確率を非線形化したり、頂点固有の魅力度(フィットネス)を導入したりすると、べき乗則以外の振る舞い(引き伸ばされた指数関数、凝縮現象、winner-takes-all)も生じうる([[@2003__SIAMReview__The structure and function of complex networks - Chapter 7 Models of network growth]])。 ## 未解決の問い - 優先的選択が線形であるという仮定は、Jeong et al.とNewman自身による2件の実証研究(引用網・Internet・俳優/科学者共同研究網、科学共同研究網)に基づくのみであり、より広範な系での検証は示されていない(p.34)。 - 付着確率が次数のべき(k^γ, γ<1)に従う一般化モデルでは、指数を支配する方程式に解析解が存在せず数値解に依存する(p.34)。 ## 未編纂の観察 - Priceモデル(有向、付着確率∝k+k0、k0=1)とBarabási–Albertモデル(無向、付着確率∝k)は、優先的選択を辺の有向性の違いで実装した2つの代表モデルである。Priceの指数α=2+1/mはk0の値に依存しないため事後的に正当化できるが、Barabási–Albertモデルはk0=0に固定されており挙動が対照的である(Source: [[@2003__SIAMReview__The structure and function of complex networks - Chapter 7 Models of network growth]])。 - 付着確率をk+k0(k0は負も可)に一般化するとα=3+k0/mとなり、負のk0は実データで観測されるα<3を説明しうる。付着確率をk^γに一般化すると、γ=1で通常のべき乗則、γ<1で引き伸ばされた指数関数、γ>1で「凝縮」現象(単一頂点が有限割合の辺を独占)、γ>2で全頂点と接続する「gel node」が非ゼロ確率で生じる(Source: [[@2003__SIAMReview__The structure and function of complex networks - Chapter 7 Models of network growth]])。 - フィットネスモデル(Bianconi and Barabási)は各頂点に固有の魅力度η_iを与え、付着確率をη_i×k_iに比例させる。フィットネス分布の台が有限ならべき乗則を保つが、無限台なら単一頂点が有限割合の辺を独占する「winner takes all」現象が生じる(Source: [[@2003__SIAMReview__The structure and function of complex networks - Chapter 7 Models of network growth]])。 - 実Webデータでは、Barabási–Albertモデルが予測する「頂点の年齢と次数の相関」が観測されない(Adamic and Huberman)。これは優先的選択自体を否定するものではないが、Webの力学が単純な線形優先的選択モデルより複雑であることを示唆する(Source: [[@2003__SIAMReview__The structure and function of complex networks - Chapter 7 Models of network growth]])。 - 優先的選択なしにランダムな両端接続だけで頂点を追加するCallaway et al.型モデルでも、次数分布は指数型になるものの成分構造に興味深い相転移(m=1/8で巨大成分が出現)が生じる。優先的選択はべき乗則次数分布の説明に十分だが必要条件ではない(Source: [[@2003__SIAMReview__The structure and function of complex networks - Chapter 7 Models of network growth]])。 - [コピー・モデル] Networks, Crowds, and Markets ch.18 の rich-get-richer モデルは、既存頂点への直接付着ではなく「ランダムに選んだ既存ページ i を経由してその接続先をコピーする」という間接的な機構で優先的選択と数学的に等価な結果を導く。確率 p で一様ランダムな既存ページへ、確率 1-p で in-link 数に比例する確率でページを選ぶという定式化は、Priceモデルの有向・出次数一定という設計(k0=1相当)と構造的に近い。導出されるべき指数は 1+1/(1-p) であり、p→0(コピーが支配的)で下限の 2 に漸近し、p→1(一様ランダムが支配的)で無限大に発散する。この下限 2 への漸近は、既存節が触れる Priceモデルの α=2+1/m や一般化モデルの α=3+k0/m とは別の切り口(コピー確率 p というパラメータ)から同じ「線形優先的選択の指数は 2 が自然な下限」という性質を再確認するものであり、両モデルの整合性を支持する(Source: [[@2010__CambridgeUP__Networks, Crowds, and Markets - Chapter 18 Power Laws and Rich-Get-Richer Phenomena]], [[@2003__SIAMReview__The structure and function of complex networks - Chapter 7 Models of network growth]])。 - [実証的裏づけ] Salganik, Dodds, Watts の音楽ダウンロード実験(ch.18 §18.4)は、同一初期条件から出発した並行世界間で rich-get-richer 力学の結果(人気順位)が大きくばらつくことを実証しており、既存節が理論面で述べる優先的選択モデルの経路依存性・予測不能性に対する実験的傍証として位置づけられる。ただし実験はWebリンクではなく音楽ダウンロード数を対象としており、既存節の主な出典(引用網・WWW)とは異なるドメインでの検証である点に留意する(Source: [[@2010__CambridgeUP__Networks, Crowds, and Markets - Chapter 18 Power Laws and Rich-Get-Richer Phenomena]])。 ## 関連 - 実体: [[Derek de Solla Price]]、[[Albert-László Barabási]]、[[Réka Albert]] - 章: [[@2003__SIAMReview__The structure and function of complex networks - Chapter 7 Models of network growth]] - ソース: [[@2010__CambridgeUP__Networks, Crowds, and Markets - Chapter 18 Power Laws and Rich-Get-Richer Phenomena]] ## 出典 - [[@2003__SIAMReview__The structure and function of complex networks - Chapter 7 Models of network growth]]