JAIST Repository
https://dspace.jaist.ac.jp/Title

次数相関を有するネットワークの頑健性とその最適構造の解明

Author(s)水高, 将吾Citation

科学研究費助成事業研究成果報告書: 1‑9Issue Date

2020‑05‑29

TypeResearch Paper

Text version

publisher

URL

http://hdl.handle.net/10119/16729

RightsDescription

若手研究, 研究期間：2018〜2019, 課題番号
：18K13473, 研究者番号：70771062, 研究分野：統計物理

Japan Advanced Institute of Science and Technology

１版

様式

Ｃ−１９、Ｆ−１９−１、Ｚ−１９ （共通）

科学研究費助成事業

研究成果報告書
令和２ 年

５ 月 ２９ 日現在

機関番号： １３３０２
研究種目： 若手研究
研究期間： 2018 〜 2019
課題番号： １８Ｋ１３４７３
研究課題名（和文）次数相関を有するネットワークの頑健性とその最適構造の解明

研究課題名（英文）Robustness of correlated networks and their optimal structures

研究代表者
水高将吾（Mizutaka, Shogo）

北陸先端科学技術大学院大学・先端科学技術研究科・助教

研究者番号：７０７７１０６２
交付決定額（研究期間全体）：（直接経費）

2,500,000 円

研究成果の概要（和文）：本研究では、頑健な（脆弱な）ネットワーク構造と次数相関の関係を明らかにするため、次の研究を行なった。1. (u, v)‑フラワーと呼ばれるモデルネットワーク上のボンドパーコレーションを解析的に取り扱い、転移点のモデルパラメータ依存性を調べることで、ネットワーク頑強性と長距離構造の関係を明らかにした。2. (u, v)‑フラワーと同等の隣接次数相関をもつネットワーク上のパーコレーションを母関数法を用いて解析し、臨界特性を調べた。その結果新奇な臨界特性を確認した。3. パーコレーション過程によって発現する次数相関を解析した。

研究成果の学術的意義や社会的意義
本研究では、最大負次数相関ネットワーク上のパーコレーション問題を扱い、その頑健性を解析的に評価した。
ネットワーク上のパーコレーション問題が故障や攻撃に対するネットワークの頑健性の数理モデルとして用いられるため統計物理学的興味に加え工学的応用面でも重要な結果を与えている。また、ネットワークからノードやエッジをランダムサンプリングしたときに、連結成分に次数相関が発現することを解析的に示した。これは連結成分の抽出という操作によって大きなバイアスが生じることを意味しており、実ネットワークのサンプリング問題のデザインに注意を払う必要であることを示している。
研究成果の概要（英文）：To clarify the relationship between the optimal structure of robust (orfragile) networks and degree correlations, the following studies have been performed: 1. Bond
percolation on a model network called (u, v)‑flower has been analytically treated and the model
parameter dependence of the percolation transition point has been investigated.; 2. Percolation on a
network with the same nearest‑neighbor degree correlation as (u, v)‑flower has been analyzed using
the generating function method to investigate the critical properties; 3. The degree correlations innetworks generated by the percolation process have been analyzed.

研究分野： 統計物理
キーワード： 複雑ネットワーク

ネットワーク科学

パーコレーション

相転移臨界現象

※科研費による研究は、研究者の自覚と責任において実施するものです。そのため、研究の実施や研究成果の公表等については、国の要請等に基づくものではなく、その研究成果に関する見解や責任は、研究者個人に帰属されます。

様式 Ｃ−１９、Ｆ−１９−１、Ｚ−１９（共通）１．研究開始当初の背景
従来の物理学で扱われる複雑構造がユークリッド空間に埋め込まれているのに対し、近年高い関心を集めている複雑ネットワークと呼ばれる系には、ユークリッド距離が定義されておらず、トポロジカルな性質が系の複雑さを支配している。系を構成する離散要素(ノード)と、それらの間の関係(エッジ)が定義できれば、どのような系であれネットワークとみなすことができる
ため、インター ネット、人間関係、神経網など、極めて広い領域に渡る複雑系をネットワークとして記述することができる。複雑ネットワークにおいては、ユークリッド距離が定義されないため各ノードの結合数には制約がない。このことに起因して、各ノードが有するエッジ本数(次数)には大きな揺らぎが許され、現実の多くのネットワークは次数分布がベキ関数に従うスケールフリー性を有していることが知られている。さらに、結合数である次数が大きく揺らぐために、次数相関 と呼ばれる格子系にはみられない新奇な相関が発現する。次数相関は端的には、任意抽出したエッジ両端のノードが有する次数間の結合確率で表現され、これにより表現される次数相関は隣接次数相関と呼ばれる。任意抽出したエッジ両端の次数が近い傾向が強い性質
を正の次数相関、両端次数の差が大きい傾向を負の次数相関と言う。隣接次数相関の強さはピアソン相関係数やスピアマン相関係数によって指標化される。
ほぼ全ての現実ネットワークが次数相関を有していることから、隣接次数相関がネットワークの有する性質にどのような影響を与えるかについて、これまで研究がなされている。特に、ネットワーク上のパーコレーション問題は、現実ネットワークが故障や攻撃にどの程度耐えられるかという頑健性の数理モデルとして用いられるため、統計物理学的観点のみならず工学的応用の面でも注目を集めている。従来の隣接次数相関と頑健性の関係解明に関する研究においては、主に相関係数とパーコレーション転移点の関係が論じられており、正の次数相関がネットワークを頑強化させることが知られている。どのような構造がネットワークを頑強化（あるいは脆弱化）させるかをより深く理解する必要がある。また、次数相関を有するネットワーク上のパーコレーション転移は、格子系のものや無相関ネットワークのものと違った臨界的振る舞いを示しうることも報告されている。
エッジ両端のノードの次数によってのみ表現される隣接次数相関は次数相関のうち最も低次のものを扱っているに過ぎない。現実ネットワークにおいては、エッジで直接つながっていない
ノード間の次数の間にも相関(長距離次数相関)があることがこれまでのいくつかの研究で指摘されている。ここで、ネットワークにおける距離はノード間を結ぶ最小エッジ本数で定義される。
その意味で、隣接次数相関は距離 1 の長距離次数相関と言える。しかしながら、高次相関である長距離次数相関がネットワークの構造頑強性に与える影響に関してはこれまで一切の議論がなされたことがなく、最も頑強(あるいは脆弱)なネットワーク構造は現在のところ明らかにされていない。
２．研究の目的
従来のネットワークの次数相関と構造頑健性の間の関係解明の問題は、隣接次数相関の枠組みの中で議論されてきた。しかしながら、現実ネットワークはより高次の長距離次数相関を有している。このことは、これまでのネットワークの頑健性の研究が、取りうるネットワーク構造で定義される全集合の部分集合の最適化問題にとどまっていたことを意味する。従来考えられてきたネットワーク集合よりも大きな集合の下で、与えられたネットワークが最も頑強(脆弱)となるネットワーク構造を解明することが求められる。そのため、本研究ではまず、長距離次数相関の有無や強度がネットワークの頑強性に影響することを示す。次いで、長距離次数相関を持つ場合とそうでない場合のネットワークの頑強性、パーコレーション転移を比較することで長距離次数相関の重要性を確認する。また、パーコレーション過程によって生じる次数相関に関して論じる。
３．研究の方法
本研究では与えられたネットワークのノード（エッジ）がある確率で占有するサイト（ボンド）パーコレーションを扱う。確率がある閾値を超えるとネットワークサイズに比例した巨大連結成分が出現する。この臨界閾値（パーコレーション転移点）を評価することでネットワークの頑強性を評価する。またパーコレーション転移点近傍での臨界挙動を調べる。ネットワークモデル
は(u, v)‑フラワーとそれに関係したランダムネットワーク及び、コンフィグレーション・ネットワークを用いる。また、一部の課題では多層ネットワークという複数のネットワークが層状につながっているネットワークを用いた。主な解析手法として、平均場近似、生成母関数法、繰り込み群方程式によって解析的に取り扱い、それらの結果はモンテカルロ・シミュレーションによる数値実験により検証した。

４．研究成果
本研究による成果は以下の通りである：(1) ハブ間距離がパーコレーション転移点に与える影響(u, v)‑フラワーと呼ばれるフラクタル性を有するネットワークモデルは、その構造がパラメータ u, v によって決定する。u+v=一定の下で、(u, v)‑フラワーの次数分布関数は保存され、u の値の大きさによって、そのハブノード間の距離が制御される。(u, v)‑フラワーは再起的な入れ子構造からなるため、隣接の次数相関を超えた長距離の次数相関を有する。このネットワークモデル上のパーコレーション問題を世代 n におけるルートノード間の接続確率 Pn に関する繰り込み方程式として表現し、熱力学極限を解析した。ハブノード間の距離が近いほどボンドパーコレーションの転移点は大きな値になることを明らかにした。このことは、ハブノード間距離が大きいほどネットワークは頑健であることを意味する。隣接次数相関のみを考えた場合は（ハブ間が直接接続している傾向が強い）正次数相関がネットワークを頑健化することを考えると、本結果は長距離相関を考えることで初めて示された結果である。本結果に関してはさらに研究を進め、適当な論文誌へ公表する予定である。
(2) (u, v)‑フラワーの隣接次数相関を保存したランダムネットワークの頑強性と臨界性(u, v)‑フラワーからランダムにエッジを二本選びエッジ端のノードを入れ替えるスワップ操作を十分に行うことで(u, v)‑フラワーと同じ次数分布関数をもつランダムネットワークを作ることができる。また、エッジ両端の次数ペアが同じとなるエッジをスワップすることにより、(u,v)‑フラワーの隣接次数相関を保存した隣接次数相関ネットワークを実現できる。２つのランダム化されたネットワークと(u, v)‑フラワーのパーコレーション転移を比較することで、同じ次数分布関数のもとで次数無相関、隣接次数相関、長距離次数相関をそれぞれもつネットワークのパーコレーションを議論した。特に、隣接次数相関ネットワークに関して、生成関数法を用いて解析的にパーコレーション臨界特性を調べた。その結果、(u, v)‑フラワー様の隣接次数相関を有するネットワーク上のパーコレーション臨界特性が、無相関ネットワーク上のものとも(u,v)‑フラワー上のものとも違う新奇な臨界的振る舞いであることが明らかとなった。また、解析結果の正当性を有限サイズスケーリングを用いた大規模数値シミュレーションによって確かめた。(u, v)‑フラワー様の隣接次数相関は最大負次数相関を実現することがわかっており、本研究により、隣接次数相関の意味での最適構造の頑健性・臨界特性が明らかにされたこととなる。
本結果については学会で発表を行い、欧文誌から論文が出版されている。
(3) パーコレーション過程により生じるネットワークの次数相関評価
ネットワーク上のパーコレーション過程は、未知のネットワークから無作為にノードあるいはエッジを選び出しネットワークを観測するサンプリング問題と考えることができる。一般に、サンプリング方法によって、サンプリングバイアスが生じることが指摘されている。この研究では、次数無相関なコンフィギュレーション・ネットワークを母体としたパーコレーション過程を考え、生成される巨大連結成分のみの構造に着目した。生成関数法を用いることにより、巨大連結成分の次数相関を解析的に特徴付け、「次数無相関なコンフィギュレーション・ネットワークはその次数分布によらず、巨大連結成分は負次数相関を持つ」ことを数学的に証明した。本結果の正当性は数値シミュレーションによって確かめられている。本研究により、母体がランダムであってもパーコレーション過程によって抽出される連結成分には次数相関があることが示され、ランダムサンプリングから連結成分に着目することでバイアスが生まれることが示された。本
研究については国内外の学会で発表を行い、欧文誌から論文を出版している。また、より現実のネットワーク構造に近づけた、次数相関と三角形を含むネットワーク上のパーコレーション問題も扱い、同様の結果がロバストに観測されることを示した。本結果については現在欧文誌で査読中である。さらに、次数無相関なコンフィギュレーション・ネットワークから生成される巨大連結成分に関しては長距離次数相関が解析できることがわかった。本結果については論文を準備中である。また、巨大連結成分の長距離次数相関が分かったことにより、長距離次数相関を持ったネットワークモデルの提案につながると考えている。これについては現在も研究を続けている。
(4) 強相関ネットワークのパーコレーションの解析的取り扱い
これまでにいくつかのグループが強相関ネットワーク上のパーコレーション転移の数値シミュレーションを行なっている。大規模数値シミュレーションが困難なこともあり、それぞれの結果が一致していない現状にある。そのため、理論的な取り扱いが求められている。従来の次数相関ネットワークのパーコレーションを解析的に取り扱う解析手法の適用が困難なため、新たな手法が必要となる。本研究では、上記のネットワーク上のパーコレーションを扱うために層状ネットワークのフレームワークを援用し、問題を定式化した。
臨界特性の解析に現在取り組んでおり、今後研究を続けていく必要がある。５．主な発表論文等〔雑誌論文〕 計3件（うち査読付論文
１．著者名
Mizutaka Shogo

3件／うち国際共著0件／うちオープンアクセス0件）
４．巻
88

２．論文標題
Simple Model of Fractal Networks Formed by Self‑Organized Critical Dynamics

５．発行年
2019年

３．雑誌名
Journal of the Physical Society of Japan

６．最初と最後の頁
14002

掲載論文のDOI（デジタルオブジェクト識別子）
https://doi.org/10.7566/JPSJ.88.014002

査読の有無

オープンアクセス

国際共著

有オープンアクセスではない、又はオープンアクセスが困難

−

１．著者名
Mizutaka Shogo、Hasegawa Takehisa

４．巻

２．論文標題Disassortativity of percolating clusters in random networks

５．発行年
2018年

３．雑誌名
Physical Review E

６．最初と最後の頁
062314;1‑7掲載論文のDOI（デジタルオブジェクト識別子）
https://doi.org/10.1103/PhysRevE.98.062314

査読の有無

オープンアクセス

国際共著

98

有

オープンアクセスではない、又はオープンアクセスが困難

−

１．著者名
Mizutaka Shogo、Hasegawa Takehisa

４．巻

２．論文標題Percolation on a maximally disassortative network

５．発行年
2020年

３．雑誌名
EPL (Europhysics Letters)

６．最初と最後の頁
46003〜46003

掲載論文のDOI（デジタルオブジェクト識別子）
doi.org/10.1209/0295‑5075/128/46003

査読の有無

オープンアクセス

国際共著

128

有

オープンアクセスではない、又はオープンアクセスが困難〔学会発表〕 計18件（うち招待講演 4件／うち国際学会
１．発表者名Shogo Mizutaka, Takehisa Hasegawa

7件）

２．発表標題Long‑range degree correlations of fractal clusters in random networks

３．学会等名The 8th International Conference on Complex Networks and their Application（国際学会）
４．発表年
2019年

−１．発表者名
Shogo Mizutaka

２．発表標題Intrinsic long‑range degree correlation of random nwtwroks near criticality

３．学会等名Roles of Heterogeneity in Non‑equilibrium collective dynamics（招待講演）（国際学会）
４．発表年
2019年
１．発表者名Shogo Mizutaka, Takehisa Hasegawa

２．発表標題Degree correlations of percolating clusters in random networks

３．学会等名Statphys27（国際学会）
４．発表年
2019年
１．発表者名Shogo Mizutaka, Takehisa Hasegawa

２．発表標題Negative degree correlations of percolating clusters in random networks

３．学会等名Critical and collective effects in graphs and networks 2019（国際学会）
４．発表年
2019年
１．発表者名Shogo Mizutaka

２．発表標題Degree correlations of percolating clusters in uncorrelated random networks

３．学会等名The 4th Workshop on Self‑Organization and Robustness of Evolving Many‑Body Systems（招待講演）（国際学会）
４．発表年
2019年

１．発表者名
Shogo Mizutaka

２．発表標題Fractal network formation based on self‑organized critical dynamics

３．学会等名Workshop on dynamical processes on networks（招待講演）（国際学会）
４．発表年
2018年
１．発表者名Shogo Mizutaka

２．発表標題Fractal networks formed by self‑organized critical dynamics and its universality class３．学会等名NetSci2018（国際学会）
４．発表年
2018年
１．発表者名水高将吾

２．発表標題複雑ネットワークの構造的性質〜次数相関、フラクタル性とその連関〜

３．学会等名量子・古典における複雑系の物理と普遍性（招待講演）
４．発表年
2020年
１．発表者名水高将吾、長谷川雄央

２．発表標題Negative degree correlations of percolating clusters in random networks

３．学会等名ネットワーク科学セミナー2019
４．発表年
2019年

１．発表者名
森 萌、水高 将吾、長谷川 雄央

２．発表標題Correlated bimodal network上の相乗効果を持つ感染症モデルの振舞い

３．学会等名ネットワーク科学セミナー2019
４．発表年
2019年
１．発表者名水高将吾

２．発表標題
ランダムグラフの最大連結成分の統計：次数相関３．学会等名
水戸数学情報数理研究会2019
４．発表年
2019年
１．発表者名水高将吾、長谷川雄央

２．発表標題最大負次数相関がパーコレーションの臨界特性に与える影響

３．学会等名日本物理学会2019春季大会
４．発表年
2019年
１．発表者名長谷川雄央、水高将吾

２．発表標題
ランダムネットワークにおける最大連結成分の統計

３．学会等名ランダム系と量子系の出会い
４．発表年
2018年

１．発表者名
水高将吾、長谷川雄央

２．発表標題パーコレーション問題における最大連結成分の負次数相関性

３．学会等名日本物理学会2018秋季大会
４．発表年
2018年
１．発表者名長谷川雄央、水高将吾

２．発表標題クラスター性のあるネットワークの連結成分の統計的性質

３．学会等名日本物理学会2018秋季大会
４．発表年
2018年
１．発表者名岩瀬優太、長谷川雄央、水高将吾

２．発表標題ランダムウォークで重み付けられたネットワークのバックボーン

３．学会等名日本物理学会2018秋季大会
４．発表年
2018年
１．発表者名水高将吾、長谷川雄央

２．発表標題パーコレーティングクラスターの次数相関３．学会等名ワンディワークショップ ネットワーク構造の数理
４．発表年
2018年

１．発表者名
水高将吾

２．発表標題パーコレーティングクラスターの次数相関の解析

３．学会等名ネットワーク科学セミナー（早稲田大学）
４．発表年
2018年
〔図書〕

計0件

〔産業財産権〕〔その他〕−
６．研究組織氏名（ローマ字氏名）（研究者番号）

長谷川雄央

研
究
協 (Hasegawa Takehisa)
力者

所属研究機関・部局・職（機関番号）

備考