# Detecting Evolving Patterns of Self-Organizing Networks by Flow Hierarchy Measurement > [!abstract] 概要 > 階層は、進化する自己組織化した生態・生物・技術・社会のネットワークに広く現れるが、階層の検出と比較は難しい。 > 本論文では、向きのある自己組織化ネットワークがどの程度フロー階層を示すかを定量的に評価する指標と手法を示す。 > フロー階層は、ネットワークで広く観察されるが理論上は見過ごされてきた階層の形である。 > 生態・神経生物・経済・情報処理の各ネットワークは、比較対象となるランダムネットワークより一般に階層的であることを示す。 > さらに、Linux カーネルの進化を通じて階層度が増加したことを発見し、進化過程における階層の出現についての Herbert Simon の初期の仮説を裏づける。 > これらの結果を合わせると、階層は現実世界の進化するネットワークの中心的な組織特性であり、階層の測定は自己組織化ネットワークの構造上の体制と進化パターンを理解する道を開くことを示唆する。 > 本手法により、異なるネットワーク間、および 1 つのネットワークの異なる進化段階間で階層を客観的に比較し、異なるネットワークの進化パターンを比較できる。 > 有向ネットワークで表せるさまざまな複雑系に適用できる。 ## 論文情報 - 著者: [[Jianxi Luo]]、[[Christopher L. Magee]](MIT Engineering Systems Division) - 媒体: MIT ESD Working Paper ESD-WP-2010-01(2010 年 6 月)。ファイル名の媒体略号は Complexity である。 - キーワード: 自己組織化ネットワーク、進化パターン、フロー階層 ## 概要 有向ネットワークの階層を「循環に含まれないリンクの割合」という単純な量で測るフロー階層指標を提案し、リンク隣接行列の冪乗で計算する手順を示す。食物網、産業の取引網、神経回路、OS のカーネルの呼び出し網を同規模のランダムネットワークと z スコアで比べ、いずれも有意に階層的だと報告する。Linux カーネルでは歴史的な版を通じて階層度が上昇しており、[[Herbert A. Simon]] の「進化のなかで階層が現れる」という仮説を定量的に支持するとする。 ## 問題設定 複雑系は階層をとることが多い。設計者のいる人工物では階層は複雑さを管理する手段であり、設計者のいない食物網・神経回路・オープンソースソフトウェア・産業の取引網では、階層は進化の結果として現れる。スモールワールド性やべき乗則の次数分布と並ぶ大域的な特徴として重要だが、実ネットワークでは階層の型が複数あり、しかも純粋な形では現れないため、検出と比較が難しい。 著者らは階層を次の 2 型に分ける。 - 包含階層(containment hierarchy): ノードを群、群の群へと入れ子に分ける。木や樹形図で表せ、有向・無向のどちらのネットワークにも見つかる。近年のネットワーク科学の階層研究は主にこちらを扱う。 - フロー階層(flow hierarchy): 有向ネットワークだけに関わり、資源のフローの向きが層の順序を決める。食物網ではエネルギー、ソフトウェアでは情報、産業の取引網では中間財が流れる。 論文が対象とするのは後者であり、理論上ほぼ見過ごされてきた点を問題とする。実ネットワークにはレベルを飛ばすリンク、同一レベル内のリンク、逆向きのリンクが混在するため、レベルの割り当てを前提にした判定は恣意的になり、階層の有無そのものが曖昧になる。 ## 提案手法 中心となる原理はネットワークの方向性、すなわち局所的なフローが全体として 1 つの向きに従うことである。この原理から、循環に含まれないリンクの割合を階層度 h とする。 $h = \frac{\sum_{i=1}^{L} e_i}{L}$ ここで L はリンク数、e_i はリンク i が循環に含まれれば 0、含まれなければ 1 である。重み付きネットワークでは、循環に含まれないリンクの重みの和を全重みで割った h_w を使う(本論文は重みなしのみを扱う)。ノードの割合で数える代替指標は、層構造をもつ図 1D で全ノードが循環に含まれ 0 になるため層状の階層を捉えられず、リンクで数えるこの指標のほうが明快で計算も容易だとする。 ![[_attachments/2010__Complexity__Detecting-Evolving-Patterns-of-Self-Organizing-Networks-by-Flow-Hierarchy-Measurement/fig01-example-networks.png]] *Figure 1: 5 種の例示ネットワーク(A 純粋な木、B 混合木、C レベル飛ばし・層内リンク、D 層、E 循環)。破線は循環に含まれるリンク* 図 1 は 5 つの例である。A の純粋な木と B の混合木はすべてのリンクが隣接レベル間を結び h = 1 になる。C はレベルを飛ばすリンクや層内リンクを含むが全体の向きは保たれ h = 1 になる。D は層内に循環があり h = 0.40、E は逆向きのリンクが循環を作り h = 0.57 になる(表 1)。 Table 1: 図 1・図 2 の例示ネットワークの階層度 | ネットワーク | 図 1A | 図 1B | 図 1C | 図 1D | 図 1E | 図 2A | 図 2B | |---|---|---|---|---|---|---|---| | 階層度 | 1 | 1 | 1 | 0.40 | 0.57 | 0.33 | 1 | ![[_attachments/2010__Complexity__Detecting-Evolving-Patterns-of-Self-Organizing-Networks-by-Flow-Hierarchy-Measurement/fig02a-random-low-hierarchy.png]] ![[_attachments/2010__Complexity__Detecting-Evolving-Patterns-of-Self-Organizing-Networks-by-Flow-Hierarchy-Measurement/fig02b-random-high-hierarchy.png]] *Figure 2: 同じ規模(N=100、L=400)で階層度が異なる 2 つのランダムネットワーク(左が A、右が B)* 図 2 は、ノード数 100・リンク数 400 で同じ規模のランダムなネットワークが、階層度 0.33 と 1 という大きく異なる値をとりうることを示す。可視化だけでは両者の差を客観的に見分けにくく、指標が必要になる。 指標は流体の流れの体制に喩えられる。全リンクが循環に含まれない h = 1 は層流、一部が循環に含まれるのは遷移流、全リンクが循環に含まれる h = 0 は乱流に当たる。レイノルズ数が流れの体制を特徴づけたように、階層度が離散システムの構造上の体制を特徴づけうると著者らは述べる。 ![[_attachments/2010__Complexity__Detecting-Evolving-Patterns-of-Self-Organizing-Networks-by-Flow-Hierarchy-Measurement/fig03-flow-regimes.png]] *Figure 3: 72 ノード・176 リンクのネットワークを 4 通りの向きにした例(A h=1、B h=1、C h=0.716、D h=0)* 図 3 は 72 ノード・176 リンクの同一ネットワークを 4 通りの向きにした例で、A・B は h = 1、C は h = 0.716、D は h = 0 である。青いリンクはレベルを飛ばす、または同一レベル内を結ぶが全体の方向性は壊さない。赤い部分は循環に含まれる。 大規模ネットワーク向けの計算手順は次のとおりである。まずノード隣接ネットワークを、リンクをノードとするリンク隣接ネットワークに変換する。リンク i の終点がリンク j の始点に直接つながるとき行列の要素 x_ij を 1 とする。この行列を p 乗し、要素 (i, j) が初めて非零になる p をリンク距離 d_ij とする。d_ij はリンク i の終点からリンク j の始点まで一方向に進むときに通るノード数の最小値である。 ![[_attachments/2010__Complexity__Detecting-Evolving-Patterns-of-Self-Organizing-Networks-by-Flow-Hierarchy-Measurement/fig04-link-network.png]] *Figure 4: 元のノード隣接ネットワーク(A)と等価なリンク隣接ネットワーク(B)* ![[_attachments/2010__Complexity__Detecting-Evolving-Patterns-of-Self-Organizing-Networks-by-Flow-Hierarchy-Measurement/fig05-link-distance-matrix.png]] *Figure 5: リンク隣接行列の冪乗によるリンク距離行列の導出(M1 から M6)* 図 4 の 7 リンクの例を図 5 の冪乗で処理すると、最終的な距離行列の対角成分 d_ii はリンク i を含む最短の循環長を与える。d_ii が空ならリンク i は循環に含まれず、e_i = 1 になる。この例では d だけが空で、h = 1/7 になる。深さ優先探索など別のアルゴリズムでも距離行列を求められると注記されている。 ## 新規性 - フロー階層を、包含階層と区別される独立した階層の形として位置づけ、その測定を初めて体系化した。 - 階層の程度を、レベルの事前割り当てを要さず、循環に含まれるリンクの割合という 1 つの数で定量化する。 - ランダムネットワーク群に対する z スコアで、異なる規模・密度のネットワークを比較する枠組みを与えた。 - Simon が仮説とした進化のなかでの階層の出現を、ソフトウェアの長期の版履歴で定量的に検討した。著者らはこの種の定量的証拠は測定手段の欠如から報告されてこなかったと述べる。 ## 実験設定 - ランダム基準: N 個のノードから L 本の有向リンクを無作為な対に割り当てる有向ポアソンランダムネットワークを生成する。同じ対への複数リンクと自己リンクは認めない。各点は 1,000 個のネットワークの平均である。 - 実ネットワーク 8 種: Bridge Brook Lake 食物網、北東米国棚食物網、日本の自動車部門・電子部門の供給業者網、線虫 C. elegans の神経の結合網、ショウジョウバエ D. melanogaster の発生の転写ネットワーク、Linux カーネルと Apple の Darwin(Mac OS X)カーネルの呼び出し網。 - ソフトウェアの呼び出し網はアーキテクチャ解析ツール Understand C++ で抽出し、関数 B に依存する関数を含むソースコード A に向けて B から A へのリンクを張る。産業網ではファーム A がファーム B から調達するとき B から A へリンクを張る。 - 比較指標: 同じ N と L のランダムネットワーク 1,000 個の平均 h_rand と標準偏差 σ_rand から、z = (h_real - h_rand) / σ_rand を求める。 - 進化の分析: Linux カーネルの版 0.01 から 2.3.0 まで(約 1991 年から 2000 年)の呼び出し網について、階層度、z スコア、平均次数 k、Newman の固有ベクトル法によるモジュール性(有向・無向)を追跡する。 ## 実験結果 ランダムネットワークの性質を図 6 に示す。ネットワークの規模 N は h にほとんど影響せず(6A)、平均次数 k = L/N が増えると h は大きく減る(6B)。k が最小のとき h は厳密に 1、k が十分大きいと h は 0 に近づく。ランダムでも h が 0 とは限らないため、z スコアが「雑音」を超えた階層の目印になる。また N の小さいランダムネットワークで、同じ k の大きなネットワークの h を推定できる。 ![[_attachments/2010__Complexity__Detecting-Evolving-Patterns-of-Self-Organizing-Networks-by-Flow-Hierarchy-Measurement/fig06-random-network-hierarchy.png]] *Figure 6: ランダム有向ネットワークの階層度(A ノード数 N 別、B 平均次数 k 別)* Table 2: 実ネットワークと同規模のランダムネットワークの階層度 表 2 は実ネットワークの結果である。 | ネットワーク | 種別 | N | L | k | h_real | h_rand | σ_rand | z スコア | |---|---|---|---|---|---|---|---|---| | Bridge Brook Lake | 食物網 | 25 | 104 | 4.160 | 0.9809 | 0.0213 | 0.0338 | 28.39 | | NE US Shelf | 食物網 | 79 | 1378 | 17.443 | 0.8273 | 0 | 0 | 無限大 | | 日本の自動車部門 | 産業の取引網 | 679 | 2437 | 3.589 | 0.9988 | 0.0601 | 0.0114 | 82.34 | | 日本の電子部門 | 産業の取引網 | 227 | 648 | 2.855 | 0.5957 | 0.1338 | 0.0310 | 14.90 | | C. elegans | 生物 | 280 | 2170 | 7.750 | 0.1171 | 0.0009 | 0.0018 | 64.56 | | D. melanogaster | 生物 | 107 | 301 | 2.813 | 0.3289 | 0.1308 | 0.0444 | 4.46 | | Darwin XNU-123.5 | ソフトウェア | 646 | 4351 | 6.735 | 0.4872 | 0.0024 | 0.0021 | 230.86 | | Linux Kernel 1.1.70 | ソフトウェア | 287 | 1385 | 4.826 | 0.8065 | 0.0159 | 0.0082 | 96.41 | 8 種すべてで、同じ N と k のランダムネットワークより有意に階層的である。同種のネットワークでも差は大きく、自動車部門は電子部門より有意に階層的で、著者らは企業の戦略・行動や技術環境の違いが反映されうるとする。一方、生物・産業・ソフトウェアといった系の種別で階層度が分かれる明確な証拠はない。 Linux カーネルの版の履歴では、階層度と z スコアが全体として増加した。最初の版 0.01 は 1 人が作ったが、その後多数の貢献者がサブルーチンを加えて階層度は一時低下し、オープンソースとして成長・安定・成熟する期間の大半で階層度は上昇した。平均次数 k も増加しており、k の増加は本来 h を下げるので、階層化の傾向を補強する。有向・無向のモジュール性は同じ期間に傾向が不明確で、むしろやや減少した。 ![[_attachments/2010__Complexity__Detecting-Evolving-Patterns-of-Self-Organizing-Networks-by-Flow-Hierarchy-Measurement/fig07-linux-evolution.png]] *Figure 7: Linux カーネルの長期進化(A 階層度とモジュール性、B z スコア、C 平均次数)* ## 考察 著者らは、実ネットワークが階層的であることから、フロー階層が進化する自己組織化ネットワークの中心的な組織特性である可能性を示唆する。進化の程度がネットワークの階層度の根本的な決定因子かもしれず、Linux の結果は Simon の「階層は安定であるため、さまざまな進化過程で必然的に現れる」という仮説を量的に支持する。一方で、階層度が進化のなかで必ず増減すると主張するのが目的ではないと明言する。 モジュール性はネットワーク進化の追跡には有用性が限られる、とも述べる。自己組織化ネットワークのモジュール性が進化でどう変わるべきかについては理論的にも観察的にも示唆がないためである。 未解決として、フロー階層が機能上の性能に何を意味するか、階層が個々のノードの挙動と相互作用からどう現れるかが挙げられる。レイノルズ数が流体力学に果たした役割になぞらえ、この指標が複雑なネットワークシステムの設計と管理に価値をもつ可能性を述べるが、さらなる研究が要るとする。 ## 強み / 弱点・課題 強み: - 指標が単純で、レベルの割り当てを前提とせず、規模の異なるネットワークを z スコアで比較できる。 - 食物網から OS カーネルまで異なる領域の実データに同じ指標を適用している。 - Linux カーネルの版履歴で、階層の出現という長年の仮説を定量的に扱った。 弱点・課題: - 進化の分析は Linux カーネル 1 系統だけで、Simon の仮説を一般に確認したとは言えない。他のネットワークの時系列は示されていない。 - 階層度は循環に含まれるかどうかの二値に基づく。1 本の逆向きリンクで大きな強連結成分ができるため、疎密や循環の大きさへの感度に限界がある。密なネットワークでは h_rand が 0 に潰れる(NE US Shelf では σ_rand も 0 で z スコアが無限大になる)。 - 重み付きの指標 h_w は式のみで、実験は重みなしに限られる。 - 階層度が高いことの機能上の意味、および階層がどのような局所規則から現れるかは答えていない。 - 産業部門間の差の解釈にはドメイン知識が要り、論文内では仮説の域を出ない。 ## 関連 - 概念: [[階層的複雑性]] / [[複雑ネットワーク]] / [[準分解可能システム]] / [[モジュール性]] / [[自己組織化]]