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

Title

攻撃に対して頑健なネットワーク構造の解明と効
率的な頑健性向上手法の提案

Author(s)中条, 雅貴CitationIssue Date

2023‑03

Type

Thesis or Dissertation

Text version

ETD

URL

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

RightsDescription

Supervisor:林 幸雄, 先端科学技術研究科, 博士

Japan Advanced Institute of Science and Technology

博士論文

攻撃に対して頑健なネットワーク構造の解明と効率的な頑健性向上手法の提案

中条雅貴

主任研究指導教員

林

北陸先端科学技術大学院大学
融合科学共同専攻
博士(融合科学)

令和 5 年 3 月

幸雄

金沢大学

Abstract
Our society is supported by a wide variety of large and complex networks, such as the Internet (WWW),
SNS, electric power, transportation, water supply, and international trading systems. These real-world networks
commonly have a scale-free property, which is characterized by power-law degree distributions. Unfortunately,scale-free networks are extremely vulnerable against malicious attacks. Thus, it is important to reveal robust
networks against attacks and obtain effective methods for strengthening the robustness of the existing networks.
In previous studies, for improving the network robustness of connectivity against attacks, several methods
have been proposed so far by enhancing a degree–degree correlation. As a highly robust structure against
attacks, an ”onion-like structure” with the positive degree–degree correlation have been discussed. Recently,
apart from the degree-degree correlation, it has been noticed that the robustness against attacks and loops
in networks may be strongly correlated with each other. Therefore, as a new perspective for improving therobustness, we focus on the loops, especially the size of Feedback Vertex Set (FVS), which is the minimum node
set whose removal makes the network no loops.
For improving the robustness against attacks, we propose two types of loop-enhancing rewirings, which are
expected to increase the size of FVS. We consider two types of rewiring with and without keeping the degree
distribution because we also investigate the effect of the degree modification on the robustness. Then, weapplied our proposed and conventional methods to some real-world network data and evaluated the improvement
in robustness. From the results with keeping degree distributions, our method increases the robustness tothe same or more than the state-of-the-art methods based on the degree-degree correlation. In addition, we
confirm that our method has the largest increase in the size of FVS. From the results without keeping degree
distributions, we find that every our and conventional methods significantly increase both the robustness andthe size of FVS, compared to the methods with keeping degree distributions. From these results, the robustness
is strongly correlated with the size of FVS more than the conventional degree–degree correlation. Moreover,the modification of degree distributions significantly improves both the robustness and the size of FVS.
As a method for improving the robustness without keeping degree distributions, we investigate link addition
methods. In previous studies of link addition methods, two different effective strategies for choosing pairs ofunconnected nodes to add links have been considered: the minimum degree and the longest distance strategies.
Thus, we propose several kinds of link addition methods with selecting nodes by degree and distance, forinvestigating the contributions of degrees and distances in improvements of the robustness. Through numericalsimulation, the minimum degree strategy is the most effective for improving the robustness in both synthetic
and real-world networks. As an exception, only in the small number of added links, the longest distancestrategy is the best. Conversely, the shortest distance strategy rarely contributes to improving the robustness,even combined with the minimum degree strategy. Thus, enhancing longer loops is essential for improving therobustness.
Based on the significantly increase of the robustness by modifying degree distributions, we investigate robust
networks in varying degree distributions. First, we consider the continuously changing degree distributions
ranging from power-law to exponential or narrower ones. Numerical results show that the smaller variances ofdegree distributions lead to higher robustness and the size of FVS in this first range. Second, we consider arandom regular graph with the minimum degree variance and the perturbed networks in their comprehensive
discrete or random perturbations. In this second range, we find the random regular graphs have the highest
robustness against attacks, and find a tendency for smaller degree variance to have higher robustness.
In summary, we emphasize the important points to further improve the robustness against attacks. Enhancing
long loops strongly improves the robustness against attacks, more than the conventional degree-degree correlation. For adding links, the minimum degree strategy is the most effective for improving the robustness. We
suggest that the random regular graph with the minimum degree variance has optimal robustness.
keywords: Network robustness against attacks, Enhancing loops, Link addition methods, The minimum
degree strategy, The minimum variance of degree distributions.

目次
1
1.1
1.2
2
2.1
2.2
2.3
2.4

緒言

研究の背景と目的 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
本論文の構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
複雑ネットワークの攻撃に対する頑健性の先行研究

複雑ネットワークの基礎概念 . . . . . . . . . . . . . . . . . . . . . . . .

2.4.5

ループによる玉ねぎ状ネットワーク . . . . . . . . . . . . . . . . . .

17

ネットワークに対する攻撃手法 . . . . . . . . . . . . . . . . . . . . .

20

次数相関による玉ねぎ状ネットワーク . . . . . . . . . . . . . . . . .

Feedback Vertex Set と Dismantling Set の等価性 . . . . . . . . . .

頑健性向上のための新たな視点としての「ループ」

14
18
21
22

. . . . . . . . . . . .

22

最小 Feedback Vertex Set の近似解法 . . . . . . . . . . . . . . . . . . .

23

ループ強化リワイヤリング法の提案 . . . . . . . . . . . . . . . . . . . . .

28

次数保存ループ強化リワイヤリング . . . . . . . . . . . . . . . . . .

30

3.3.2

確率伝搬法による最小 Feedback Vertex Set の近似的解法 . . . . . .
次数変化ループ強化リワイヤリング . . . . . . . . . . . . . . . . . .

実際のネットワークデータを用いた頑健性向上の評価 . . . . . . . . . . .

3.4.1
3.4.2
3.4.3

23
28
31

比較手法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

ループ強化リワイヤリングによる頑健性指標と最小 FVS サイズの向上

36

現実のネットワークデータ . . . . . . . . . . . . . . . . . . . . . . .

32

頑健性と最小 FVS サイズ、次数相関の関係性 . . . . . . . . . . . . .

37

まとめ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

3.4.4
3.4.5
3.5

13

ループ強化リワイヤリングによる頑健性向上

3.3.1
3.4

11

攻撃に対する頑健性指標 . . . . . . . . . . . . . . . . . . . . . . . .

レジリエンスの観点から . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.2.1
3.3

9

13

2.4.4

3.2

9

攻撃に対して頑健なネットワーク構造 . . . . . . . . . . . . . . . . . . . .

現実ネットワークの攻撃に対する脆弱性 . . . . . . . . . . . . . . . . . .

2.4.3

3.1

7

10

2.4.2

3

4

スケールフリー性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.4.1

2.5

4

次数変化リワイヤリングによる次数分布の変化

1. . . . . . . . . . . .

39

4
4.1
4.2

次数と距離によるリンク追加による頑健性向上

次数が変化する頑健性向上手法であるリンク追加法

4.2.3

4.5
4.6

5
5.1
5.2
5.3

53

スケールフリーネットワークでのリンク追加法による頑健性の向上 . .

実際のネットワークデータにおけるリンク追加法による頑健性の向上 . . .
まとめ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
変化する次数分布における頑健なネットワーク構造

61
67
72
74
74

連続的に変化する次数分布における攻撃に対する頑健性指標 . . . . . . . .

78

連続的に変化する次数分布を持つネットワークの生成法 . . . . . . . . . .

75

連続変化する次数分布における Localized Attacks に対する頑健性指標 82
逆優先的選択モデルによる鎖状構造が頑健性に与える影響

ランダムレギュラーグラフとその摂動ネットワーク

ランダムレギュラーグラフに対する離散的摂動. . . . . .

84. . . . . . . . . . . .

86. . . . . . . . . . . .

87

ランダムレギュラーグラフに対するランダム摂動 . . . . . . . . . . .

頑健性指標とパーコレーションしきい値 . . . . . . . . . . . . . . . . . .

89
92

Newman-Ziff アルゴリズム . . . . . . . . . . . . . . . . . . . . . . .

94

頑健性の比較 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

95

5.5.1

ランダムレギュラーグラフとその摂動ネットワークにおける攻撃に対する

5.6.1

6

53

次数分布の均質さと攻撃に対する頑健性 . . . . . . . . . . . . . . . . . .

5.4.2

5.7

48

ループの無いネットワークでのリンク追加法による頑健性向上 . . . .

次数と距離によるリンク追加法による頑健性向上の評価 . . . . . . . . . .

5.4.1

5.6

46
50

5.3.2

5.5

46

45

比較のためのネットワークモデル . . . . . . . . . . . . . . . . . . . . . .

5.3.1
5.4

組織論における長距離交際 . . . . . . . . . . . . . . . . . . . . . . .

次数と距離によるリンク追加法の枠組みの提案 . . . . . . . . . . . . . . .

4.6.2
4.8

44
44

最小次数戦略と最長距離戦略の類似性 . . . . . . . . . . . . . . . . . . . .

4.6.1
4.7

43

最小次数戦略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
最長距離戦略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.2.2

4.4

. . . . . . . . . . . .

頑健性向上のためのリンク追加法の先行研究 . . . . . . . . . . . . . . . .

4.2.1

4.3

43

RR グラフとその摂動グラフにおける異なる種類の攻撃に対する頑健性指標 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

まとめ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
結言

105

2

6.1
6.2
6.3

研究成果の要約. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

今後の課題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
むすび . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

3

1 緒言

1.1 研究の背景と目的

現代社会において、我々は非常に大規模かつ複雑なつながりの中で暮らしている。例えば、インターネットを通じて、世界のありとあらゆる地域、文化、言語を持った人々とリ
アルタイムにやりとりすることが可能である。ほんの 10 年ほど前まではパソコンからイ

ンターネットに接続する必要があったものが、今や多くの人がスマートフォンからいつでもどこでも手軽にインターネットを使用することができる。さらに、近年では、会議や面接、講義などのさまざまな事がインターネットを経由したオンラインでするようになりつつあり、インターネットは現代社会に必要不可欠なインフラとなっている。このように現代社会に不可欠なインターネットであるが、必ずしも安定な接続が確保できているかと言われればそうではない。近年では、多くの通信事業者で通信障害が起こっており、延べ数千万人が影響を受けるような大規模通信障害も起こっている。これらの多くは人為的ミス
や設備故障が原因となっているので、原因さえ分かれば復旧することは可能であるが、それでも普及まで数時間単位でかかることがある。

大規模化かつ複雑なつながりとして、インターネット以外の日常生活に不可欠なインフラにおいても潜在的な機能停止の可能性があることは多い。特に災害による影響は大きく、被害が及ぶ範囲が広く、かつ復旧に数ヶ月や数年かかるものもある。例えば、2010 年に起きたアイスランドのエイヤフィヤトラヨークトルという火山の噴火は 3 月から 6 月まで三ヶ月もの間続きヨーロッパ上空に火山灰を放出することで航空運送を大混乱に陥れた [1]。この噴火により一日で 80% ものフライトがキャンセルになり 120 万人もの乗客が影響を受けることになった。一番噴火が激しかった時期は、一日あたり 4 億ドルもの逸
失利益になったと報告されている。さらに広い範囲の航空路線の機能停止により、代替路となった海上輸送や陸上輸送にも混乱が広がることになった。このように現代社会が大規模で複雑につながっていることは良い側面ばかりでなく、一部の混乱が全世界に伝播していくような悪い側面もある。

現代社会を構成しているつながりを、点 (ノード) とその間の辺 (リンク) からなるネッ

トワーク構造として抽象化すると、共通した一定の性質があることが判明している。このような自然もしくは人工的に構成された現実ネットワークの共通性を明らかにする試みが精力的に進められており、総称して「複雑ネットワーク」もしくは「ネットワーク科学」と呼ばれている。上記のようなインターネットや輸送網のみでなく、ソーシャルネットワー

4クや企業間取引関係、脳のニューロンのネットワークなど幅広い分野を対象としている。
特に、多くの現実ネットワークはごく一部分のノードにリンクが集中している非常に不平等なトポロジー構造をしており、その集中部分によってネットワーク全体の機能が維持されている事が分かっている。具体的には、各ノードにつながっているリンク数（次数) の分布がべき乗則に従うようなスケールフリー性を持っている。このような構造は、一様ランダムな故障に対しては機能が維持されやすいため頑強だが、集中部分を狙ったような悪意のある攻撃に対しては脆弱であり、バラバラに分断してしまう恐れがある [2, 3]。2000
年にインターネットがこのような弱点部分を持っている事が明らかになり「インターネッ

トのアキレス腱」と呼ばれるようになった。残念ながら、インターネットだけではなく、多くの現代社会に不可欠なネットワークが「アキレス腱」を持っているため、現代社会は潜在的に多くの弱点を抱えているとも言える。そこで、現代社会を安定的に機能維持する
ためには、弱点を持たない、つまり悪意ある攻撃に対して頑健なネットワークを実現することが必要になる。

先行研究によって、悪意ある攻撃に対して頑健なネットワークを得る試みが少数ながら進められている。特に攻撃に対して高い頑健性を持つネットワークとして、「玉ねぎ状構造」が知られている [4–6]。玉ねぎ状構造については 2.4.2 節で詳細に説明するが、ある固定した次数分布において、リンク両端が同じぐらいの次数を持つほど頑健になることが知られている。そのため、同じような次数を持つノードをつなぎ合わせることで、ネットワークを頑健にする手法が提案されている [7, 8]。このように攻撃に対して頑健なネット

ワークは、リンク両端の次数の相関係数 (次数相関) との関連性から研究されている。しかしながら、次数相関から頑健性を考える場合ではいくつか問題点がある。まず次数相関が高すぎるネットワークは、むしろ攻撃に対して脆弱になることが知られている [4, 5, 9]。
このことから次数相関ではない他の指標が攻撃に対する頑健性と強い関係があるのではな
いかと考えられる。さらに次数分布が変化する場合は、攻撃に対する頑健性と次数相関の間の関係性がよく分かっていない。そこで、次数相関以外の方針によって、攻撃に対して頑健なネットワークを得る試みが必要と考えられる。

特に、次数分布が変化するような場合では、攻撃に対してどのようなネットワーク構造が頑健なのかはまだよく分かっておらず、また頑健性を向上する手法がほとんど明らかになっていない。そこで我々は、新たな頑健性向上の方針として「ループ強化」を考えた。
詳細は 2 章で説明するが、近年「ループ」は頑健性と非常に強い相関関係にあることが明らかにされつつある。そのため、ループを強化することで、頑健性を大幅に向上できるのではないかと考えることができる。そこで 3 章では、頑健性向上のためのループ強化リワ

イヤリング法を提案している。提案手法や詳細な結果は 3 章で説明するが、次数分布が変5化する場合でもループ強化によって頑健性は大幅に向上することが分かった。さらに、頑健性を大幅に向上する次数変化リワイヤリングでは、次数分布の分散が小さくなっていることを発見した。

この考え方を発展させて、次数分布を変化させながら、攻撃に対する頑健性を効率的に向上するようなリンク追加法を考えることができる。詳細は 4.1 節で説明するが、先行研究から効率よく頑健性を向上する戦略が二種類提案されている。一つは最小次数戦略と呼ばれるもので、ネットワークの中でも一極集中していない周辺の部分に新たなリンクを加えるという戦略である [10–13]。このようにリンクを加えると、ネットワークの集中部分が攻撃された際に、周辺部分でつながりを保持することができる。このように最小次数戦
略では、攻撃に対する頑健性を効率的に向上させる事ができる。もう一つは最長距離戦略と呼ばれるもので、ネットワーク内で最も離れている二点の間をつなげるという戦略である [14]。このように最も離れた部分をつないぐことで、中心にある集中部分が攻撃を受けた際に、つながりを保持するための長い迂回路をあらかじめ形成しておける事になる。詳細は 4.2 節でさらに説明するが、この二戦略の関係性などはあまりよく分かっていない。
さらなる頑健性向上のためのリンク追加法を明らかにするには、これらの二戦略それぞれの貢献を明らかにする必要がある。

次数分布が変化する場合の最も頑健なネットワーク構造はよく分かっていないが、いく

つかのピンポイントな次数分布を持つランダムなネットワークでは攻撃に対する頑健性が調べられている。5.1 節でより詳細な説明をするが、例えば次数分布がべき乗則に従うス
ケールフリーなネットワークは、ポアソン分布に従う Erdős-Rényi ランダムグラフ [15]よりも攻撃に対して脆弱であることが明らかになっている [2, 3]。これらのランダムなネットワークでの比較から、次数分布が平均値に集中しているような狭い分布であるほど、攻撃に対して頑健なのではないかと示唆されている。しかしながら、どの程度の範囲
で次数分布の均質さと頑健性の関係が成り立っているのかなどは、まだあまりよく分かっていない。

上記のような背景に基づき、攻撃に対して頑健なネットワーク構造の解明と、更なる頑健性向上手法の提案をするために、本研究では次の三点を具体的な目的とする。

1. 従来の研究で着目されてきた次数相関ではなく、「ループの強化」に着目して、攻撃に対する頑健性を分析する。

2. ループ強化に基づいて、効率的に頑健性を向上する新たな手法を提案する。

3. 従来ほとんど分かっていなかった次数分布が変化する場合における、攻撃に対して頑健なネットワーク構造を明らかにする。

6

1.2 本論文の構成

本論文では、全体を六章で構成している。第一章の序論に続いて、第二章では複雑ネッ

トワークの基本的な概念と、攻撃に対する頑健性の先行研究について述べる。第三章において、頑健性向上のためのループ強化に基づくリワイヤリング法を提案する。第四章では、次数と距離の組合せによるリンク追加法を提案する。第五章で、連続的に変化する次数分布における攻撃に対する頑健性と、最も均質なランダムレギュラーグラフとその周辺
における頑健性について調査する。

第二章では、複雑ネットワークの基本的な概念としてネットワークの定義と現実のネッ

トワークに共通して見られるスケールフリー性について述べる。さらに、スケールフリー
なネットワークが攻撃に対して脆弱であることと、現実のネットワークも同様に攻撃に対してバラバラに分断されてしまうことを述べる。その後、次数相関によって得られた攻撃に対して頑健なネットワークの知見をまとめる。さらに、近年新たに着目されているルー
プと頑健性の関係性をいくつか述べる。

第三章では、従来の次数相関ではなく、新たな頑健性向上手法としてループ強化リワイ

ヤリング法を提案する。まず、攻撃に対する頑健性と関連するループ強化の指標である最小 Feedback Vertex Set(FVS) が厳密解を得ることが困難であることを述べて、確率伝播
法により近似的に求める手法を述べる。これらの議論を踏まえて、ループ強化として最小FVS サイズを増加させるリワイヤリング法を提案する。提案手法を実際のネットワーク

データに施した結果から、提案したループ強化リワイヤリングが、既存の次数相関による手法と同等かそれ以上にまで頑健性を向上することを示す。さらに、次数相関よりも、最小 FVS サイズの方がより頑健性と強い相関関係にあることを示して、今後の頑健性の向上にはループ強化が重要であることを議論する。

第四章では、頑健性向上に効果的とされてきた最小次数戦略と最長距離戦略のそれぞれの効果を明らかにして、次数と距離の二段階によるリンク追加法の枠組みを提案する。まず、最小次数戦略と最長距離戦略について述べた後、そのリンク追加先として選択されるノード対の類似性について議論する。そして「次数」と「距離」の二段階によるリンク追加法の枠組みから六種類のリンク追加法を提案する。この六手法による頑健性の向上を比較することで、多くの場合は最小次数戦略が最も効果的であることを示す。さらに最小FVS サイズの変化を調べることで、短いループが形成される場合には最小 FVS サイズが多くても頑健でない場合があることを示す。

第五章では、ループの強化によって次数分布が類似した変化をしていたことを踏まえ

7

て、いくつかの次数分布と攻撃に対する頑健性の関係性を明らかにする。特に、連続的に変化する次数分布を持つネットワークを生成するための Growing Network モデルと逆優

先的選択モデルについて、これらのモデルで生成されたネットワークでの攻撃に対する頑健性を調べることで、べき乗からカットオフ付きべき乗、指数、さらに狭い次数分布の範囲では、次数分布が均質になるほど頑健性が高くなることを示す。次に、逆優先的選択モ
デルでは生成できない、次数分布が最も均質なランダムレギュラーグラフとその摂動ネッ

トワークについて述べる。網羅的な離散的摂動として二峰性ネットワークについて述べ、さらにより多峰なランダム摂動としてリンクをランダムに追加・削除するものを述べる。
ランダムレギュラーグラフとその摂動ネットワークでの頑健性を比較することで、ランダ
ムレギュラーグラフが最も高い頑健性を持つことを示す。
第六章では、結論として以上の成果をまとめる。

8

2 複雑ネットワークの攻撃に対する頑健性の先行研究
2.1 複雑ネットワークの基礎概念

まず初めに複雑ネットワークの基本的な事項と用語をまとめる。図 1 に示すように、

ネットワークとは点 (ノード) と二点を結ぶ辺 (リンク) から構成されたもので、数学におけるグラフ理論のグラフと同じものを表す。ノード集合 V とリンク集合 E から構成されるものをネットワーク G = (V, E) と表記する。また、ネットワーク内のノード i とノード j を結ぶリンクを (i, j) と表記する。

図1

四つのノードと三本のリンクで構成されたネットワークの例。

グラフ理論では様々な種類のネットワークが考えられているが、本稿ではネットワークの繋がり方のみを考えたいので、以下の条件を満たす無向で重み無しの単純グラフのみを対象にする。まず、リンク (i, j) には重みや向きがないものとする。つまり、リンク (i, j)と (j, i) は区別せずに同じリンクを示す。また、ある二つのノードの間に複数本のリンクをつなぐ多重リンクや、両端を同一ノードとする自己ループを持たないとする。さらに、ネットワークには、どのリンクとも繋がっていない孤立ノードは無いものとする。図 2 に多重リンクと自己ループ、孤立ノードの例を示す。これらを持たない単純ネットワークを対象としている。

このような単純な点と辺のつながりとみなすことで、多くの現実のネットワークにいく

つかの共通する統計的性質があることが 2000 年前後に明らかにされた [16, 17]。このよ

うな現実のネットワークで見られる性質について研究する分野の総称を「複雑ネットワー
ク」もしくは「ネットワーク科学」という。それ以前にも数学では、ネットワーク内の二つのノード間に確率的にリンクを形成する Erdős-Rényi ランダムグラフが研究されてい9図2

多重リンクと自己ループ、孤立ノードの例. これらを含んでいないネットワーク

のみを考える。

た [15]。しかしながら、現実のネットワークに共通して見られる性質は、Erdős-Rényi ラ
ンダムグラフが持たない性質であることが分かっている。このため、現実のネットワークの多くは一様ランダムに形成されたものではなく、何かしらの共通する原理や仕組みがあるのでは無いかと多分野の研究者に注目され、精力的に研究がされるようになった。

2.2 スケールフリー性

多くの現実のネットワークに共通する性質として代表的なものに「スケールフリー性」がある [17]。スケールフリー性は、一部のノードは非常に多くのリンクが集中して接続されている一方で、大半のノードは少数のリンクのみにしか接続されていないような不均一な構造をしていることを意味している。よく知られているスケールフリーなネット

ワークとして WWW がある [18]。WWW のリンク関係では、一部のサイトは数百万以上のリンクを受けているのにも関わらず、大半のサイトは少数のリンクしかされていな

い。他にも SNS のフォローフォロワー関係 [19] や航空網 [20]、男女間の性交渉ネット
ワーク [19, 21] など様々な現実のネットワークがこのような不均一な構造をしている。

特に、次数分布がべき乗則に従っていることをスケールフリー性をいう。「次数」は、各ノードに繋がっているリンクの本数で、ノード i の次数を ki と表記する。そして、ある
ネットワークにおいて次数 k を持つノードの個数の比率を示すものを次数分布 P (k) という。多くの現実のネットワークの次数分布は、次のべき乗則に従っている [17]。

P (k) ∝ k −γ .

(1)

現実ネットワークでは、べき指数が 2 < γ < 3 となっている場合が多い。このような、べき乗分布を両対数スケールでプロットすると一直線になり、その傾きがべき指数になる。そのため、次数分布を両対数スケールでプロットすることで、スケールフリー性を目で見ることができる。図 3 に航空網データ AirTraffic [19] を可視化したものと、次数

10

図3

航空網データ AirTraffic を (A) 可視化したものと (B) 次数分布. ノードは次数が高いほど大きく表示されている。また次数分布は両対数スケールになっている。

分布をプロットする。図 3A の可視化から現実の航空網のネットワークは、リンクが集中している中心部と極端に少ない周辺部があることが分かる。また図 3B から、次数分布が次数 k ≥ 2 では直線的になっていることが分かる。この航空網データでは平均次数が#k$ ≈ 4.2 であるのに対して、最大次数 kmax = 37 と非常に大きい値となっている。このように多くの現実のネットワークはスケールフリー性を持っており、平均次数に対して極端に大きい次数を持つハブノードが存在していることが知られている。

2.3 現実ネットワークの攻撃に対する脆弱性

日本の航空網では、多くの航空会社の拠点となっている羽田空港や関西国際空港がハブ空港と呼ばれており、ネットワークにおけるハブノードとなっている。このようなハブ

ノードは航空輸送において非常に重要な点となっており、多くの利用客がハブノードを使用することになる。逆に、天候不良やテロ攻撃、大規模災害などの理由でハブとなっている空港が機能停止してしまった場合、被害は非常に甚大なものとなってしまう。このようにスケールフリーなネットワークは不均一な構造をしていることから、一部の集中している部分を狙った攻撃に対して繋がり方が脆弱であることが知られている [2]。

特に、多くの現実ネットワークは全体がひとつながりであることを前提に運用されているため、繋がり方が脆弱であることは重大な問題になる。例えば、インターネットがバラバラに分断されたとすると、どこのページにもアクセスできなくなってしまう。また、航11空網や鉄道網などの輸送ネットワークが分断されてしまった場合、移動することが不可能
もしくは困難になってしまう。このように、特に現代社会のインフラは全連結であることを前提に機能しているため、攻撃に対して繋がり方がどのように変化するのかについて調査されている。

2003 年 8 月にアメリカで起こった大停電を受けて、北米の電力網のノード除去に対する連結性の頑健性が数値的に調べられている [22]。結果として、主要な変電所に影響を与えるような攻撃によって、その機能が大きく低下することを明らかにしている。さらに都市鉄道網として、2014 年の中国の上海軌道交通の鉄道網ネットワークの攻撃に対する連結性が調べられており、次数順攻撃と媒介中心性順攻撃という二つの攻撃手法に対して連結性が脆弱であることが分かっている [23]。また、2011 年から 2012 年にかけての世界的な航空輸送ネットワークにおいて、いくつかの異なる攻撃手法を比較することで、結果として媒介中心性順攻撃が最も効果的に最大連結成分サイズを減少させることが明らかになっている [24]。さらに、航空網におけるフルサービスキャリア (FSC) とローコス

トキャリア (LCC) の路線の種類による戦略の違いに着目することで、それぞれのネット
ワークの攻撃に対する頑健性が議論されている [25]。FSC のハブ空港の方が LCC の拠点空港よりもネットワークの中心となっていることから、LCC の路線ネットワークの方がより攻撃に対して頑健であることを明らかにしている。このように現代社会のさまざまなインフラにおいて、攻撃に対する連結性の脆弱性が明らかにされている。そのため、攻撃に対する脆弱性を克服した頑健なネットワークを実現することが、安定的に機能維持する社会システムの構築に向けて重要な課題となっている。

12

2.4 攻撃に対して頑健なネットワーク構造
2.4.1

攻撃に対する頑健性指標

ネットワークの繋がり方は、リンクを辿って到達可能なノードの最大集合である「連結成分」によって考えられ、その中でも最も多くのノードが含まれているものを「最大連結成分」という。図 4 にネットワークがノードを一つずつ除去していく攻撃によって、つながりが減少していく様子を示す。

図4

攻撃によって最大連結成分サイズが減少していく様子. 左からノードを一つずつ除去している。

攻撃に対して頑健なネットワークを考えるために様々な頑健性指標が提案されているが、本稿では主に攻撃による最大連結成分サイズの変化による頑健性指標 R を主に用いる [4]。ここで頑健性指標 R は

N

1 !
R=
S(Q),
N

(2)

Q=1

で定義される。ここで N はノード数で S(Q) は攻撃によってノードが Q 個除去された時の最大連結成分に含まれているノード割合である。つまり、ノードを一つずつ順番に取り除いて (Q = 1, 2, ..., N )、その S(Q) を平均したものである。R は 1/N から 0.5 までの範囲をとり、R 値が大きいほど頑健になる。この R 値は、全ての最大連結成分が崩壊した S(Qc ) = 1/N になる臨界点 Qc が同じであったとしても、崩壊の急峻さで異なる値を取ることができる。図 5 に、異なる三つの攻撃による最大連結成分サイズの崩壊を示す。

13

図5

攻撃に対する最大連結成分サイズの減少. 一つのネットワークに対して三種類の攻撃方法 (BP、HDA、CI) を適用した結果を示している. R 値は各線の下側領域面積に相当する.

図 5 では、赤線の BP 攻撃が最も急峻に最大連結成分比を減少させていることが分かる。上記の R 値は各線と X、Y 軸で囲まれた領域の面積に対応しているため、三手法では BP 攻撃に対する頑健性指標 RBP が最も低い値になっている。一方で、S(Qc ) = 1/Nとなる臨界点は三手法であまり差が見られない。そのため、我々は頑健性の指標として、崩壊の急峻さを比較できる R 値を用いる。本稿では主に典型的な攻撃である、次数が高いノードから順番に除去する次数順攻撃 [2, 4] を考える。

2.4.2

次数相関による玉ねぎ状ネットワーク

次数順攻撃に対する頑健性指標 Rhub を用いて、次数順攻撃に対して頑健なネットワー

ク構造が議論されている。特に、次数分布 P (k) を一定としながら、頑健性指標 Rhub を最大化する山登り法によるリワイヤリングが提案されている [4]。
山登り法による頑健性最適化のリワイヤリング

1. ランダムに二つのリンク (i, j) と (k, l) を選択する。

2. 既存リンク (i, j) と (k, l) を除去して、新規リンク (i, k) と (j, l) を追加する。
3. 2. で頑健性指標 Rhub が増加したら、そのまま 1. に戻る。

4. 増加しなかった場合は 2. を元の状態に戻してから 1. に戻る。
14

このリワイヤリングをくり返して行うことにより頑健性指標 Rhub が増加していく。また、ここで全てのノード i, j, k, l は一本のリンクの追加と一本のリンクの削除をしている
ため次数は一定になっている。このリワイヤリングによって、インターネットや電力網

ネットワークが攻撃に対して頑健になることが数値的に示されている。さらに、このようなスケールフリーなネットワークに適用した結果から「玉ねぎ状構造」と呼ばれる構造

が、攻撃に対して頑健になることが明らかにされている。玉ねぎ状構造とは、近い次数のノード同士がリンクで結びついたような構造のことを呼ぶ。高次数ノードを中心にして低次数になるほど端になるように配置した同心円状の可視化で、玉ねぎのようなリンクの接続がされているように見えることから玉ねぎ状構造と呼ばれている。図 8 に玉ねぎ状ネッ
トワークを示す。玉ねぎのように同心円状の層のようにリンクが配置されていることが分かる。

図6

玉ねぎ状ネットワークの持つ構造. 同心円状に配置した時に、同半径のノード間にリンクが構築されて玉ねぎのように見える。

次数が近いもの同士が結びついていると、攻撃に対して頑健になることは、高次数ノードから除去することを考えれば理解できる。次数順攻撃では高次数ノードから除去を進めるが、この時高次数ノードに接続されているリンクも除去される。逆に、低次数ノードを両端に持つリンクは、このような攻撃によって除去されにくいため残ることになる。そのため、低次数ノード同士が結びついているような場合は、攻撃に対してリンクが残りやすくなるため、攻撃に対して頑健になることが分かる。

さて、次数が近いもの同士が繋がっていることを定量的に示す指標として次数相関 r がある [26]。次数相関 r は全てのリンク両端ノードの次数で Pearson の相関係数を計算す15

るもので、""
2
4M e (ke k " e ) − [ e (ke + k " e )]
r=
(3)
"
"
2,
2M e (ke2 + k " 2e ) − [ e (ke + k " e )]"で定義される。ここで M はリンク数、 e は全てのリンクに対して和をとることを示

し、ke , ke" はあるリンク両端のそれぞれの次数を示す。次数相関 r は −1 から 1 までの値をとる。玉ねぎ状ネットワークは明確な定義はないが、多くの場合で頑健性指標 Rhubと次数相関 r の値で判断されている。代表的な生成モデルである Barabási-Albert モデル [17] によって生成されたスケールフリーネットワークでは Rhub ≈ 0.23 と r ≈ 0 であるのに対して、玉ねぎ状ネットワークは Rhub > 0.3 と r > 0.2 となっている場合が多い [6]。また、次数相関 r を最大化するような山登り法によるリワイヤリングも提案されている [27]。この次数相関を増やすようなリワイヤリングを適用したとしても、頑健性指標 Rhub は向上することになる。

図 7 WuHolme [8] を適用した前後のネットワークの可視化。(A)Barabaśi-Albert

モデルによる N = 200 ノードと M = 600 リンクのスケールフリーなネットワークと(B)WuHolme 適用後のネットワーク。赤色リンクは両端のノードが同じ次数を持つもの、(A) では 16 本だったのに対して (B) では 175 本に増加している。

このように、頑健性指標 Rhub と次数相関 r の相関関係から、攻撃に対して最適なネッ

トワーク構造が研究されてきた。例えば、理論的な研究として次数相関のあるネットワー
クでのパーコレーション過程を解析することで、正の次数相関を持つ場合に攻撃に対して頑健になることが明らかにされている [5]。また、山登り方では計算量が非常に大きくなるという問題があったため、全体のリンクを同時に張り替えることで正の次数相関を16持った玉ねぎ状ネットワークを得る手法が、Wu と Holme (2011) によって提案されている [8]。この手法は頑健性を非常によく改善することができることが分かっており、頑健性向上のベースラインとしてみなすことができる。図 7 に Wu と Holme による手法によるネットワーク構造の変化を可視化する。適用したことで、より同次数ノード同士が繋がるように変化していることが分かり、また次数相関も r = −0.08 から 0.06 まで上昇している。

ただし、いくつか課題も存在している。山登り法によるリワイヤリングによって次数相関の最大化をした時に、次数相関が r > 0.4 と極端に大きくなってしまうと、むしろ頑健性は低下することが知られている [4, 5, 9]。これは各次数を持つノード同士が結びついたことによって、異なる次数ノードの間を結ぶリンクが少なくなることで、分断が起きやす
くなったことが考えられる [9]。また次数相関は、次数分布が一定の場合では頑健性と相関関係があることが分かっているが、次数分布が変化する場合についてはよく分かっていない。次数分布は頑健性に大きく影響を与えることが分かっているため、更なる頑健性の向上を目指す場合は、次数の変化を含めて考える必要がある。

2.4.3

ループによる玉ねぎ状ネットワーク

これまでは次数相関によって頑健性が考えられてきたが、近年、ネットワーク内の「ループ」が頑健性と相関関係があるのではないかと注目されつつある。そこで玉ねぎ状ネット
ワークを生成する新たな手法として、仲介によってループを形成していく方法が提案されている [6]。この仲介による成長法によっても、高い頑健性指標 Rhub と次数相関 r の両方をもつ玉ねぎ状ネットワークを構築することができる。さらに、この生成された玉ねぎ状

ネットワークの次数分布は、べき乗ではなく指数の裾野を持った分布となっている [28]。
これらの結果から、従来の次数相関ではなく、新たに「ループ」を強化することで、攻撃に対して頑健な玉ねぎ状ネットワークが構築できることが明らかになった。

仲介による生成法では、ネットワークに新規ノードを追加して、既存ノードにリンクを張るということをくり返すことで、ネットワークを構築する手法である。図 8 のように、新規ノードが接続する既存ノードを選択する際に、ループもしくは迂回路が形成されるように離れたノードを選択する。ランダムに一つのノードを選択して、その選択したノードから数ホップ離れたノードを選択し、その両方に対してリンクを張る。これを繰り返すことで、離れたノードを仲介することで、多くの迂回路が形成されることで、攻撃に対して頑健な玉ねぎ状ネットワークを生成することができる。また、この玉ねぎ状ネット
ワークでは、次数順攻撃に対する頑健性指標 Rhub とループ形成に不可欠な最小ノード集

合 Feedback Vertex Set(FVS) サイズに強い相関関係があることが分かっている。そのた

17

図8

仲介による玉ねぎ状ネットワークの生成手法。新規ノード (白ノード) はランダ

ムにノードを選択して (赤ノード)、そこから数ホップ離れたノードを選択する (青ノード)。新規ノードはその両方にリンクを接続する。これによって迂回路となるループが形成されることになる (青点矢印)。

め、頑健性向上のためのループ強化の指標として FVS サイズが注目されている。

2.4.4 Feedback Vertex Set と Dismantling Set の等価性

ループの中でも、特にネットワークをループ無にする際に必要なノード集合である

Feedback Vertex Set(FVS) は、攻撃に対する頑健性に強く関わるループの指標となっている。具体的には図 9 の赤丸のようなノード集合を指す。

Braunstein et al., (2016) によって最小 FVS と Dismantling Set の比率の等価性が明らかになっている [29]。まず、ネットワーク G においてループ無にする際に必要な最小ノード集合 (FVS) の割合を θFVS (G) として、ネットワーク G において最大連結成分のサイズを定数 C 以下にする際に必要な最小ノード集合 (C-Dismantling Set) の割合を

θdis (G, C) とする。さて、ネットワーク G がループのない木とすると、次の不等式が成り立つ。

θdis (G, C) ≤ここで、木でないネットワーク G では、

1
.
C +1

θdis (G, C) ≤ θFVS (G) +
18

1
C +1

(4)

(5)

図9

最小 FVS に含まれるノード. 左の赤丸が最小 FVS に含まれるノード。右は除去後にループ無しとなったネットワークを示す。左のネットワークで、最小 FVS サイ
ズは 2 となっており、1 つのノードの除去だけではループ無しにできない。

となる。これはネットワーク G において最小 FVS を得た後に、その最小 FVS に含まれるノードを全て除去した木で Dismantling Set を得たものである。逆に、最小 FVS に対する不等式を導くこともできる。まず、ネットワーク G において C-Dismantling を行

うと、長さ C 以下のサイクルは残ることになる。残った長さ C 以下のサイクルの個数

nC (G) を除去すれば最小 FVS となるので、次の不等式が得られる。
θFVS (G) ≤ θdis (G, C) +

nC
.
N

(6)

ここで次数分布 P (k) に従うランダムグラフを考えると、

θFVS (P (k)) = lim E[θFVS (G)],N →∞θdis (P (k)) =lim

N →∞,C→∞E[θdis (G, C)].

(7)
(8)

E はランダムグラフのアンサンブル平均を意味する。N → ∞, C → ∞ において 1/C + 1
は 0 になるので、式 (5) はθdis (P (k)) ≤ θFVS (P (k))(9)

となる。次数分布 P (k) の二次モーメントが発散しないと仮定すると、N → ∞ において

nC /N が 0 となる。よって式 (6) はθFVS (P (k)) ≤ θdis (P (k)).

(10)となる。よって、最終的に θFVS (P (k)) = θdis (P (k)) となり、最小 FVS と Dismantling

Set の割合が等価になる。これらの等価性は、最小 FVS サイズがネットワークの最大連
結成分サイズを減少させる攻撃と深い関連があることを意味している。

19

2.4.5

ネットワークに対する攻撃手法

ここまで典型的な攻撃として、高次数ノードから除去する次数順攻撃のみに絞って議論を進めてきた。しかしながら、図 5 のように、R 値はノードを一つずつ取り除くような攻撃であれば計算可能で、異なる攻撃手法で比較することもできる。そこで、表 1 に代表的なネットワークへの攻撃方法についてまとめる [30]。

表では下に行くほど強力になっており、一番下のループ除去による BP 攻撃 [31] が現状で最も強い手法である。BP 攻撃は、最小 FVS サイズに含まれる確率 qi0 が高いノードから順に除去していく攻撃手法であり、図 5 のように他の攻撃手法よりも最大連結成分

比を急峻に崩壊させることができる。表の次数順から BP 攻撃までは、どれも特定のノードを狙った攻撃であり、次数順攻撃と BP 攻撃の中間のような手法となっている。そのため、本稿では典型的な次数順攻撃と、最も強力な BP 攻撃のみを使用する。

次数順や BP などの弱点を狙った攻撃ではなく、地震や津波などの空間的な大規模災

害のモデルとして、ある地点を中心とした範囲攻撃 Localized Attack (LA) [32] がある。

LA は、次数順や BP 攻撃などとは異なる性質を持っていると考えられるが、まだ良く分

かっていない部分が多く、現在研究が進められている段階である。LA と次数順や BP 攻撃を組合せた手法などを考えることでより現実的な被害や攻撃をモデル化することができると考えられるが、本稿では LA を異なる種類の攻撃として比較するだけに留める。LAと BP 攻撃に対する頑健性は 5.3 章と 5.6.1 章で扱っている。
標的

表1

種々の攻撃手法

基本手法

派生手法

一様

ランダム [2]ハブ

次数順 [2, 4]

知人の免疫化 [33]CIl [35]

CIp [36]

周辺
中心性
拡散

LA [32]

媒介中心性 [34] など

CI − TML [37]コア

CoreHD [38]ループ

2-corek-coreBP [31]

BPD [39]20

2.5 レジリエンスの観点からシステム工学や環境工学の観点からも、予期していなかったようなテロ攻撃や地震や津波などの災害などの擾乱に対して、安定的に機能し、また早急に復活できるようなレジリ

エントな社会システムや環境システムを目指す試みが進められている [40]。レジリエンスには様々な定義が存在するが、基本的には内外部の擾乱に対して「しなやかに復活できる
ような機能」のことを指す。元々は生態学で用いられていた用語であり、気候変動や人為的要因で生態系が変化した時に、その生態系が変化しながらも生物種の絶滅などはせずに安定して維持されるような性質を意味している。この性質をインフラなどの工学的なシス
テムや社会システムに適用した場合、固く頑丈でもある許容値を超えると二度と復活できないような硬いシステムではなく、必ずしも元に戻る訳ではないが想定以上の擾乱に対しても、しなやかに機能を復活することができるような丈夫なシステムを目指すことになる。

このようなレジリエンスなシステムを目指すためには、従来の Safety-I から Safety-II

への移行が必要とされている [41]。Safety-I とは「物事が悪い方向へ向かわない状態」で定義される安心を目指すもので、あらかじめ決められた許容量を超えた失敗や事故によって失敗が発生することを示す。このような安全の定義は簡略化しすぎであり、事前に予想できていないような状況には上手く対処することができない。そこで Safety-II として「物事が正しい方向へと向かうことを保証する」を安全の定義として考えられている。

Safety-II では成功や失敗などの結果によらず物事は同じ方法で起こると考えて、変わりうる状況下で成功する能力を伸ばすことに注力する。これを実現するためにはシステムの動作や環境が発展、各種の機能の相互関係を理解する必要して、事前に対策する必要によ
り予期に努める必要がある。このように Safety-II に従ってレジリエンスを高めるためには、システムの振る舞いの理解と、それによる事前対策が必要になる。

そこで我々は、従来の脆弱なネットワーク構造から攻撃に対してしなやかな構造に変化させることを目指す。そのために、攻撃に対して最適な頑健性を持っているネットワーク
構造を明らかにすることで、どのように変化すれば頑健になるのかを示す。これはレジリ
エンスを高めるために必ずしも元に戻る訳ではないことと、攻撃を受ける事前に対策することが必要であることを踏まえている。

21

3 ループ強化リワイヤリングによる頑健性向上
3.1 頑健性向上のための新たな視点としての「ループ」

これまでの研究では、次数相関が正になるようにネットワークを変化させることで、頑健なネットワークを得る試みが進められてきた [4, 6, 8, 42]。一方で、近年、次数相関とは異なるアプローチとして「ループ」が着目されつつある。Braunstein et al., (2016) は攻撃に関するノード集合 Dismantling Set とループに関するノード集合 Feedback Vertex

Set(FVS) が、ランダムグラフでのアンサンブルにおいて、その比率が等価であることを示した [29]。また、Hayashi (2018) は仲介により比較的長いループを形成するように成長するネットワーク生成モデルを提案して、頑健なネットワークが生成されることを明らかにしている [42]。この成長モデルで生成されたネットワークにおいても、最小 FVS サ
イズと攻撃に対する頑健性は非常に強い相関関係があることが数値的に示されている。

本章では、与えられた脆弱なネットワークに対して、ループを強化することで頑健性を向上するリワイヤリング法を提案する。最小 FVS サイズと頑健性の強い相関関係から、
最小 FVS サイズを増加させることで頑健性を向上できるのではないかと考えた。しかしながら、最小 FVS の厳密解を得ることは NP 困難な組合せ最適化問題のため、大規模なネットワークでは計算量の面から非常に難しい。そこで、統計物理学の Cavity 法を活用

した確率伝播法によって得られる、各ノード i が最小 FVS に属する周辺化確率 qi0 を用いる [39]。この周辺化確率 qi0 を用いたループ強化リワイヤリング法を提案して、頑健性が既存手法と同等かそれ以上にまで向上できることを数値シミュレーションにより明らかにする。

まず攻撃に対する頑健性と最小 FVS の関係を基にして、確率伝播法による最小 FVSの近似解法について説明する。その後、最小 FVS に属する周辺化確率 qi0 を用いたループ
強化リワイヤリングを提案する。さらに、提案したループ強化リワイヤリングと既存の次数相関による手法を実際のネットワークデータに施すことで、頑健性指標と最小 FVS サ
イズの変化を比較する。

22

3.2 最小 Feedback Vertex Set の近似解法

最小 FVS を得ることは NP 困難な組合せ最適化問題としてよく知られているため、近似アルゴリズムが提案されている。特に、近似アルゴリズムは厳密解ではなく、理論で保証された範囲に含まれる近似解を得るためのアルゴリズムである。最小 FVS 問題では二近似アルゴリズムが提案されており、厳密解のサイズの二倍以内の近似解を得ることができる [43]。このような近似アルゴリズムを使用することで、大規模ネットワークであっても FVS を求めることができる。ただし、この二近似アルゴリズムでは厳密解の二倍もの大きさの解が得られることになるため、精度が低い。特に、ループが強化されたネットワークでは FVS サイズが半数に近くなることが考えられ、このような場合では二近似アルゴリズムを使用することができない。

このような計算機科学分野ではなく、統計物理学の手法によって最小 FVS 問題を解く試みがある [39]。この手法は統計物理学のイジングモデルに着想を得て、各ノードに

FVS に関する状態があると設定して、その自由エネルギー最小化に基づいて FVS を得るものである。これは、ループの持たない木では厳密解を得ることができるが、それ以外では得られた解の理論的な保証はない。しかし、経験的には高速かつ高精度に FVS を得ることができることも分かっているため、我々は統計物理学による近似手法を用いる。

3.2.1

確率伝搬法による最小 Feedback Vertex Set の近似的解法

2.4.4 節で示した最小 FVS サイズと Dismantling Set サイズの等価性を踏まえると、

ネットワークの攻撃に対する頑健性の向上に最小 FVS が活用できるのでは無いかと考えることができる。しかしながら、厳密な最小 FVS を得ることは組み合わせ最適化問題でNP 困難であることが知られている [44]。そのため、計算量の問題でノード数の多い大規

模なネットワークで最小 FVS を得ることは非常に難しい。そこで、厳密解ではなく近似的な解を高速で得るための手法がいくつか提案されている。その中でも、Zhou (2013) は統計物理学の Cavity 法に基づいた確率伝播法によるメッセージ伝播アルゴリズムを提案している。このアルゴリズムは BP 攻撃でも使用されており、非常に高速でかつ高精度で解を得ることができる。本節では、確率伝播法による最小 FVS 解法について述べる。

厳密に最小 FVS を解くことは難しいため、このアルゴリズムではリンク両端のノード同士の関係性に落とし込むことで、全体の制約を局所的な制約に単純化を行う。全体で根付き木 (もしくは森) を構成するように、各ノードの状態と隣接しているノード間の状態の制約を作る。無向グラフ G = (N, V ) において、各ノード i が状態変数 Ai を持つとす23

る。ノード i の隣接ノード集合 ∂i に含まれるノード j として、状態変数を次のいづれかの状態になるとする。

0
Ai = i


j

(非占有)
.
(木の根)
(占有, 親はノード i)(11)

簡単のために図 10 に可視化して示す。ここではノード i が Ai = 0 を白丸、Ai = i を青丸、Ai = j を青丸と青矢印で示している。

図 10

各ノードの状態を示した図。白丸が非占有、青丸が木の根、青丸と青矢印が占有で、隣接ノードに親を持つノード。

近似的な最小 FVS を求めるために、占有と根の状態のノードが木構造になるようにしたい。そこで、隣接している二つのノード i, j 状態を次のような制約に設定する。

1. Ai = Aj = 0, (両方が非占有)

2. Ai = 0 and 0 < Aj *= i, (i は非占有、j は i 以外に親を持つか根)

3. Aj = 0 and 0 < Ai *= j, (j は非占有、i は j 以外に親を持つか根)
4. Ai = j and 0 < Aj *= i, (i の親は j 、j は i 以外に親を持つか根)
5. Aj = i and 0 < Ai *= j, (j の親は i、i は j 以外に親を持つか根)

これらの関係を図 11 に示す。2 と 3、4 と 5 の制約はノード i, j で対称になっていることに注意。すべてのリンク両端がこれらの制約を満たした場合、根と占有状態のノードは図12 のような一つのループだけを許すような根つき木の構成になる。ここで白丸の非占有ノードを除去した時に得られるネットワークは、各連結成分につき一つのノードを除去することで木構造にすることができる。よって、これらの制約を満たすような状態の集まりの中で、非占有 (Ai = 0) になる確率が高いノードを最小 FVS に属する確率が高いノードとして考えることにする。

ここで一様ランダムにノードを選択した時に、そのノード i が状態変数 Ai を持つ周

24

図 11

リンク両端のノードの状態が満たすべき制約の図。白丸が非占有、青丸が木の

図 12すべてのリンク両端のノードが制約を満たした場合の一例。左下の占有と根根、青丸と青矢印が占有で、隣接ノードに親を持つノード。

ノードの構成では、矢印が一周するループが生じている。白丸が非占有、青丸が木の根、青丸と青矢印が占有で、隣接ノードに親を持つノード。

辺化確率 qiAi を考える。ノード i の状態変数 Ai は隣接ノード j ∈ ∂i の状態に強く影響を受けるが、逆に隣接ノード j もノード i の状態に影響を受けるため、その部分で繰り返しの効果が起きてしまう。そこで、統計物理学での平均場近似の手法として知られる

Bethe-Peierls 近似を適用する。今対象としているノード i を除去したものを cavity グラ

フと呼び、その cavity グラフでは隣接ノード j は互いに非連結になっていると仮定する。

25

すると、隣接ノード集合がとる状態の同時確率 P\i (Aj : j ∈ ∂i) は、互いに独立なのでP\i (Aj : j ∈ ∂i) ≈

'

A

j
qj→i

(12)

j∈∂i

j
となる。ここで qj→i
はノード i が除去された cavity グラフにおいてノード j が状態 Aj

Aを持つ周辺化確率となっている。

jcavity グラフへのノード i の再挿入を考えることで qiAi と qj→iの関係を理解できる。

A

再挿入したノード i が根になる時を図 13 に示す。cavity グラフにおいて隣接ノード j が非占有もしくは根である場合、再挿入したノード i は根 Ai = i になることができる。根ノード同士は隣接することができないが、図 13 のように catiy グラフで根状態だった隣接ノードが占有状態に変化することで制約を保つことができる。しかしながら、占有状態
として他に親を持つノードがある場合は、制約を満たすことができない。そのため、ノードi が Ai = i になるためには、cavity グラフにおいて全ての隣接ノード j が Aj = 0

もしくは Aj = j である必要がある。次に、再挿入したノードが占有状態になる場合とし

図 13 Cavity グラフに再挿入した時のノード状態。cavity グラフにおいて隣接ノードが占有状態である場合は、ノード i は根になれない。白丸が非占有、青丸が木の根、青丸と青矢印が占有で、隣接ノードに親を持つノード。

て、ある隣接ノード l が親になる時を考える。まず、ノード l は占有もしくは根の状態である必要がある。ノード l 以外の隣接ノードは上記の議論と同様に考えることができるたj
め、非占有もしくは根の状態であれば良い。これらの議論から qiAi は qj→iを用いて以下Aのように表現することができる。

qii =ex ' 0j(qj→i + qj→i
)
zi

(13)

j∈∂i

qil =

'
ex
0
0
k
(1 − ql→i)(qk→i+ qk→i)zik∈∂i\l

26

(14)

1
,
zi

qi0 =

(15)

ここで x は逆温度を示すパラメータ。また正規化定数 zi は

zi = 1 + e x

'

j
0
(qj→i
+ qj→i) + ex

j∈∂i

!

j∈∂i

0
(1 − qj→i
)

'

0
k
(qk→i
+ qk→i),(16)k∈∂i\jで得ることができる。平均場近似を使った繰り返しの数値計算をするために、さらにこれ
Aiを自己無撞着な式にする。qi→jはノード j が除去された cavity グラフにおいてノード i

が状態 Ai となる確率であることだった。そこで i → j としてノード j の効果を取り除く
ことで以下のような方程式にすることができる。
i
qi→j
=

l
qi→j
=

ex
zi→j

ex
zi→j

'

0
(1 − ql→i)

また正規化定数は'k∈∂i\j(17)k∈∂i\j0k(qk→i+ qk→i) + ex

'

0
m
(qm→i
+ qm→i)(18)m∈∂i\l,j0
qi→j=zi→j = 1 + ex

j
0
(qk→i
+ qk→i
)

1
zi→j

!

k∈∂i\j,0(1 − qk→i
)

(19)

'

0
m
(qm→i
+ qm→i), (20)m∈∂i\j,kとなる。これらの式は自己無撞着となっているため、繰り返し計算を行うことでそれぞれの周辺化確率を計算することができる。ここで、ノード i が非占有状態になる周辺化確率

qi0 が高いノードから順番にループがなくなるまで除去を行う。この除去したノードの集合を最小 FVS と見なすことができる。得られた最小 FVS が最小であるという保証はない。しかしながら、得られた最小 FVS サイズと厳密な最小 FVS サイズは、他の手法と比較しても非常に精度が良いことが経験的に分かっている。これらの議論を踏まえて、qi0をノード i が最小 FVS に属する確率と見なすことで、ループを強化することを提案する。

27

3.3 ループ強化リワイヤリング法の提案

本章では Zhou (2013) による確率伝播法で計算された各ノード i が最小 FVS に属する

周辺化確率 qi0 を用いて、最小 FVS サイズを増やすようなループ強化リワイヤリング法を提案する。リワイヤリングでは与えられたノード数とリンク数は一定として、リンクの繋ぎ方のみを変更する。

ループ強化リワイヤリング法として、次数を保存する手法と変化させる手法の二種類を考える。次数分布はネットワークの頑健性に強い影響を与えるため、その変化によって頑健性が大きく変化してしまうと、ループ強化による効果と混ざってしまう可能性がある。
そのため、次数変化の有無で二種類を用意することで、次数変化の効果とループ強化の効
果を分けて議論を行う。これまでの次数相関による頑健性向上手法では、主に次数を保存する手法が中心に提案されてきた。次数が変化する場合に、次数相関を向上させることで頑健性が改善されるかは未だ不明である。一方で、Braunstein et al.,(2016) らの議論を踏まえると、次数が変化する場合でもループ強化であれば頑健性を向上することができると考えられる。そのため、次数変化の有無で二種類のループ強化リワイヤリング法を提案する。

ループ強化として最小 FVS サイズを増加させるために、今まで最小 FVS に含まれていなかったノードを新たにループに含めることで、最小 FVS サイズを増加させることができるのではないかと考えた。そこで、最小 FVS に属する周辺化確率 qi0 の小さいノード同士を結ぶことで、新たなループが形成されて、最小 FVS に新たなノードを加えることができるのではないかと考えた。qi0 の小さいノードは最小 FVS になりにくいノードであり、ネットワークでも部分的に木構造のようなループにあまり含まれていないようなものである。そこで「qi0 の小さいノード同士を結ぶこと」によるループ強化リワイヤリングを
提案する。

3.3.1

次数変化ループ強化リワイヤリング

まず次数が変化するようなループ強化リワイヤリングを提案する。次数変化を許す場合は、そのまま qi0 の小さいノード対を選択して新規リンクを追加すればよい。ただし、リンク数を一定にする必要があるため、他の既存リンクを除去する必要がある。そこで追加の逆として qi0 の大きいノードを両端に持つリンクを除去することを考える。このようなリンクの除去は最小 FVS サイズを低下してしまう可能性がある。しかしながら qi0 の大
きいノードは多くのループに含まれていることが予想されるため、一本の既存リンクの除28

去の影響は受けにくいと考えた。これらの議論を踏まえて、次数変化ループ強化リワイヤ
リングを以下の手順にまとめる。

次数変化ループ強化リワイヤリング (BP Non-Preserving)

1. 最大 qi0 , qj0 を両端に持つリンク (i, j) を除去する。

2. 最小 qk0 , ql0 の非連結ノード対 (k, l) にリンクを追加する。

3. ネットワーク構造が変化したため全ノードの qi0 を再計算して 1. に戻る。

図 14a に模式図を示す。青色の qi0 値が小さいノードが連結されていることが分かる。

図 14

提案したループ強化リワイヤリングの模式図。(a) 次数変化ループ強化リワイ

ヤリング（b）次数保存ループ強化リワイヤリングを示す。赤色が高い qi0 値を持つノードで、青色のノードが低い qi0 値を持つノード。

29

3.3.2次数保存ループ強化リワイヤリング

次数を保存したままリワイヤリングをするために、Chan and Akoglu (2016) の枠組みに従って、次のような三段階のリワイヤリングを考える。

Step1: 新規リンク (i, j) を追加する。

Step2: 既存リンク (i, k) と (j, l) を除去する。
Step3: 新規リンク (k, l) を追加する。

この枠組みでは、まず Step1 で非連結のノード対 (i, j) を決めて、その隣接で非連結のノード対 (k, l) を決めるという手順になっている。これによって各ノードは既存リンクが一本除去されて、新規リンクが一本追加されることになるため次数は変化しない。

この枠組みに従って、qi0 の小さいノード同士を結ぶようにノードを選択していく。ただし、この枠組みでは Step2 において既存リンク除去があるため、そこで連結成分の分断が起きないように注意する必要がある。特に qi0 の小さいノードは低次数であることや、部分的に木構造に含まれていることが多いため、一本のリンクの除去でも連結でなくなってしまう危険性が非常に高い。そのためノード i, j として qi0 の小さいノードを選択してしまうと、逆に頑健性が低下してしまう可能性がある。これを回避するために、Step1 のノード i, j として qi0 , qj0 が最も大きいノードを選択することにする。そして、ノード k, l

として、それぞれの隣接ノード集合の中で qk0 , ql0 が最も小さいものをノード k, l として選択する。このように選択することで連結性をなるべく保ったまま、Step3 において qk0 , ql0が小さいノード k, l を連結することができる。図 14(b) に模式図を示す。青色の qk0 , ql0 が小さいノード k, l が連結していることが分かる。よって、次数保存ループ強化リワイヤリ
ングを以下の手順にまとめる。

次数保存ループ強化リワイヤリング (BP Preserving)

1. 最大 qi0 , qj0 の非連結ノード対 i, j を選択する。

2. それぞれの隣接で最小 qk0 , ql0 の非連結ノード対 k, l を選択する。

3. 新規リンク (i, j), (k, l) を追加して、既存リンク (i, k), (j, l) を除去する。
4. ネットワーク構造が変化したため全ノードの qi0 を再計算して 1. に戻る。

30

3.4 実際のネットワークデータを用いた頑健性向上の評価

提案したループ強化リワイヤリングと既存手法を実際のネットワークデータに適用することで、頑健性向上の評価を行う。さらに、最小 FVS サイズと頑健性指標の相関関係を調べて、実際のネットワークデータにおける相関関係を示す。比較として、次数順攻撃による頑健性指標 Rhub を用いる [4]。また、ループが強化されていることを確かめるために最小 FVS サイズの変化を比較する。ここで最小 FVS は厳密解ではなく、確率伝播法

によって得られた近似的な解を用いる [39]。また、これまでの研究で着目されてきた次数

相関の変化についても調査する [26]。特に、次数が変化する場合に、頑健性指標と次数相関がどのような関係にあるかは明らかになっていなかったため、これらの相関関係を調査
する。

3.4.1

比較手法

比較手法として、次の三手法を用いる。(1) 提案手法の qi0 の部分を次数に置き換えた手法(Degree)、(2) Wu-Holme の次数相関を正にする手法 (WuHolme) [8]、(3) スパニン

グツリーの個数を増加させる手法 (SP) [45]。(1) は qi0 値を用いて選択した効果があるのかどうかを確かめるために比較する。(2) の手法はネットワークの全リンクを近い次数をもつノードが連結するように張り替える手法であり、次数相関による手法として非常に良く頑健性を向上することが分かっている。ただし、提案手法のようにリワイヤリングを繰り返す手法ではなく、全リンクを一斉に張り替える手法のため、リワイヤリング回数での比較ができない。また、次数分布は必ず保存することになる。そのため WuHolme による
手法は、次数保存における頑健性向上のベースラインとして考える。

(3) で扱われれているスパニングツリー数はループに関係しており、ループを増加させるリワイヤリングの一種とみなすことができる。スパニングツリー (全域木) は全ノードと一部のリンクから構成される木であり、この全域木に含まれないリンクはループと一対一に対応しているため fundamental cycle と呼ばれている [46]。そのためスパニング
ツリー数が多いほど、ループとの対応関係から、ループが多くなると考えることができる。そこでスパニングツリー数を増やす手法を、最小 FVS ではないループを増やすリワ
イヤリングとみなして比較を行う。Chan and Akoglu (2016) らは、スパニングツリー数

がネットワークに対応するラプラシアン行列の積で表せられることから、行列摂動論から固有値の変化を評価することでスパニングツリー数が大きくなるようにリワイヤリングをする手法を提案している [45]。

31

3.4.2

現実のネットワークデータ

実際のネットワークデータに適用することで、それぞれの手法の頑健性向上を比較する。いくつかの異分野のデータとして、次の三種類のネットワークを用いる。これらは異分野のネットワークであるが、次数分布が裾野の長い分布になっており、また全連結になっている。それぞれのネットワークの指標を表 2 に示す。

インフラ系ネットワークの航空網データ (OpenFlight) は、Openflights.org のデータを基にしたもので空港から空港へのフライトのデータとなっている。この航空網ネット

ワークはスケールフリーなネットワークであり、平均次数 #k$ = 10.8 に対して最大次数kmax = 242 のハブノードがある。また、次数相関 r ≈ 0.05 となっており、ほとんど無相関でランダムなネットワークである。また直径 D = 14 と少し大きめで、ネットワークの端と端の間が少し遠くなっている。

人間関係ネットワークのメールのやりとり関係 (Email) はスペインのルビーラ・イ・ビ

ルジーリ大学における教員や大学院生のメールのやり取りのデータである。このメール

ネットワークはスケールフリーなネットワークであり、平均次数 #k$ = 9.6 に対して最大

次数 kmax = 71 のハブノードがある。また、次数相関 r ≈ 0.09 となっており、若干正よりであるが、ほとんど無相関となっている。また直径 D = 8 と短く、各ノード間の距離が短いスモールワールド性を持っている。

生物系ネットワークのイースト菌ネットワーク (Yeast) はイースト菌でのタンパク質-

タンパク質相互作用のネットワークである。タンパク質相互作用ネットワークはスケールフリーなネットワークであり、平均次数 #k$ = 5.6 に対して最大次数 kmax = 64 のハブノードがある。上の二つのネットワークと比べて、平均次数が小さく、疎なネットワークとなっている。また、次数相関 r ≈ −0.1 となっており、少し負の次数相関を持っており、異なる次数のノードがつながっている傾向が少しだけある。また直径 D = 11 と短く、各ノード間の距離が短いスモールワールド性を持っている。
表2

現実ネットワークのデータ. 左からネットワークの名前、ノード数、リンク数、

次数相関、最小次数、平均次数、最大次数、直径、参考文献を示す。

N

M

r

Min k

<k>

Max k

D

Refs.

OpenFlights

2905

15645

0.049

1

10.8

242

14

[19, 20]

E-mail

1133

5451

0.078

1

9.6

71

8

[47]

Yeast

2224

6609

-0.105

1

5.9

64

11

[48]

Network32

図 15 OpenFlight でのリワイヤリングによる頑健性指標 Rhub 、最小 FVS サイズ、次数相関の変化。(a, c, e) は次数保存のリワイヤリングによる結果、(b, d, f) は次数変化のリワイヤリングでの結果。緑線が提案したループ強化リワイヤリングでの結果
で、頑健性指標と最小 FVS 共にベースラインと同等かそれ以上に向上している。

33

図 16 Email でのリワイヤリングによる頑健性指標 Rhub 、最小 FVS サイズ、次数相関の変化。(a, c, e) は次数保存のリワイヤリングによる結果、(b, d, f) は次数変化のリワイヤリングでの結果。緑線が提案したループ強化リワイヤリングでの結果で、頑健性指標と最小 FVS 共にベースラインと同等かそれ以上に向上している。

34

図 17 Yeast でのリワイヤリングによる頑健性指標 Rhub 、最小 FVS サイズ、次数相関の変化。(a, c, e) は次数保存のリワイヤリングによる結果、(b, d, f) は次数変化のリワイヤリングでの結果。緑線が提案したループ強化リワイヤリングでの結果で、頑健性指標と最小 FVS 共にベースラインと同等かそれ以上に向上している。

35

3.4.3

ループ強化リワイヤリングによる頑健性指標と最小 FVS サイズの向上

図 15 に OpenFlight に適用した結果、図 16 に Email に適用した結果、図 17 に Yeastに適用した結果一覧を示す。各図において左側が次数保存、右側が次数変化となっている。また、横軸にリワイヤリング数、縦軸は上から頑健性指標 Rhub 、最小 FVS サイズ、
次数相関となっている。提案したループ強化リワイヤリング (BP) での結果を緑線、提案

手法の qi0 を次数に置き換えた手法 (Degree) を紫線、次数相関による手法 (WuHolme) を
赤点線、スパニングツリー数による手法 (SP) を水色線で示す。

まず、各図左側の次数保存の手法による頑健性と最小 FVS サイズの結果を議論する。

図 15c から、OpenFlight の最小 FVS サイズでは、提案したループ強化リワイヤリング(緑線) が他の手法よりも最小 FVS サイズを増加していることが分かる。このことから
qi0 の小さいノード同士を結ぶことによるループ強化リワイヤリングが、最小 FVS サイズを効果的に増加することができていると確認できる。さらに図 15a から、OpenFlight

での頑健性指標では、提案したループ強化リワイヤリング (緑線) がベースラインである

WuHolme(赤点線) とほとんど同等にまで向上していることが分かる。これらの結果は、提案したループ強化リワイヤリングが最小 FVS サイズを効果的に増加することができて、さらに次数順攻撃に対して非常に頑健にすることができていることを示している。また、
図 16c の Email の最小 FVS においても、提案手法は最小 FVS サイズを最も増加させる

ことができた。さらに、図 16a の Email の頑健性では、提案手法はベースラインよりも頑健性指標を向上しているという結果が得られている。一方で、図 17c の最小 FVS サイ

ズでは、最小 FVS サイズは WuHolme の手法よりも小さい値になっている。しかしながら、図 17a の Yeast での結果でも同様に、提案手法はベースラインと同等程度にまで頑健性を改善しているため、このような場合でもループ強化による手法は頑健性を大きく改善できることが分かる。これらの異なる三種類のネットワークでの結果から、提案した次
数保存のループ強化リワイヤリングは最小 FVS サイズを増加することができて、さらにベースラインと同等かそれ以上にまで頑健性を向上することができることが分かった。

図 15ac から、次数保存において提案手法の qi0 を次数に置き換えた手法 (紫線) は、頑健性指標や最小 FVS サイズは向上するもののベースラインや提案手法ほどには向上しない

ことが分かる。このため、提案手法で qi0 を使用したことが、頑健性の向上や最小 FVS サ
イズの増加に寄与したことが分かる。また、スパニングツリー個数による手法(水色線)

は頑健性や最小 FVS サイズをほとんど向上しなかった。このことから、頑健性を考える
場合にはループに関する指標の中でも、特に最小 FVS が鍵となっていると考えられる。

次に、各図右側の次数変化する場合の頑健性と最小 FVS サイズの結果を議論する。ま36

ず、WuHolme の手法 (赤点線) は次数保存のみの手法のため、次数変化する場合 (図の右側) でも次数保存でのベースラインを記載している。そのため、次数保存と次数変化の結果はベースライン (赤点線) で比較することができる。図 15b から OpenFlight において、提案したループ強化リワイヤリング (緑線) はベースラインと比べると非常に頑健性指標を向上していることが分かる。次数保存の WuHolme による手法では Rhub = 0.174 であるのに対して、次数変化の提案手法では Rhub = 0.404 と大幅な改善をしている。また、
図 16d から最小 FVS サイズも同様に大幅な向上を示していることが分かる。WuHolmeによる手法が |FVS| = 698 であるのに対して、提案手法は |FVS| = 1549 となっている。

OpenFlight は 2905 ノードのため、53% ものノードが最小 FVS に含まれるように変化している。図 16bd や図 17bd の他のネットワークでも同様に、ベースラインと比較すると提案手法は頑健性指標と最小 FVS サイズ共に大幅に向上していることが分かる。一方で、他の次数変化する手法 (紫線と水色線) と比較した場合、ほとんど値に差はなかった。図 15bd,16bd,17bd のいずれにおいても、次数変化による三手法は頑健性指標と最小FVS サイズはほとんど同じような値を取りながら変化している。特に、次数保存ではあまり頑健性を改善できていなかったスパニングツリーによる手法 (水色線) も、次数変化をする場合では大きく頑健性指標と最小 FVS サイズを向上していることが分かる。これ

らの結果から、次数が変化する場合でもループ強化によって頑健性を向上することができ
るが、次数の変化による頑健性の変化が大きいため、他手法との差が小さいということが分かった。

以上の議論をまとめると、提案した次数保存ループ強化リワイヤリングはベースラインと同等かそれ以上にまで頑健性と最小 FVS サイズを向上することができた。また、次数変化ループ強化リワイヤリングにおいては、次数保存のベースラインから大幅に頑健性と最小 FVS サイズを共に向上することができた。しかしながら、次数分布の変化によって大幅に頑健性が変化するため、他の次数変化する手法と比べると大きな差は見られなかった。これらの結果から、ループ強化リワイヤリングによって頑健性が改善することが分かり、さらに次数が変化する場合でもループ強化が有用であることが明らかになった。

3.4.4

頑健性と最小 FVS サイズ、次数相関の関係性

リワイヤリングでの結果から頑健性指標と最小 FVS サイズ、次数相関の間の相関関係について議論する。まず、次数保存での結果を比較する。図 15ac の OpenFlight の頑健性指標と最小 FVS サイズにおいては、それぞれの線の順序が非常に似ていることが分かる。しかしながら、図 15e の次数相関は明らかに異なっており、次数に置き換えた手法(紫線) が最も次数相関を向上していた。図 17ace の Yeast での結果でも同様の傾向が見37

られ、次数に置き換えた手法が最も高い次数相関となっている。これは qi0 を次数に置き換えたことで、小さい次数を持つノード同士が連結することで次数相関が向上したと考えられる。しかしながら、そのような高い次数相関が必ずしも頑健性の向上にはならないことが、これらの結果から明らかになった。一方で、図 16e の Email では、提案手法とベースラインが最も高い次数相関となっている。このような振る舞いの違いはネットワーク構造に由来するものであると考えることができるが、その原因はよく分かっていない。しかしながら、この三種類のネットワークのいずれにおいても、頑健性指標と最小 FVS サイ

ズはよく似た変化を示しており、その相関関係が強いことが分かる。相関関係の強さを定量的に評価するために、OpenFlight でのリワイヤリングにおける頑健性指標と次数相関、
最小 FVS サイズの相関係数を表 3 に示す。OpenFlight においては、次数相関よりも最小 FVS サイズの方がより頑健性指標と強く相関していることが分かる。

表 3 OpenFlight における Rhub と次数相関、Rhub と最小 FVS サイズの相関係数

次数保存
次数変化

Rhub と次数相関

Rhub と最小 FVS サイズ

0.53

0.98

0.76

0.97

次に次数変化する場合のそれぞれの相関関係を議論する。図 15bd の OpenFlight の頑健性指標と最小 FVS サイズにおいては、それぞれの線が非常に似たような変化をしている。しかしながら、図 15f の次数相関では異なる変化をしており、次数に置き換えた手法(紫線) が最も次数相関を向上していた。このことは、次数が変化する場合は、正の次数相関になったとしても頑健性はあまり改善しないことを示している。さらに驚くべきことに、次数変化ではスパニングツリー個数による手法 (水色線) が負の次数相関に変化していることが分かる。このことから次数変化を許す場合には、次数相関が負になったとしても攻撃に対して頑健なりうることが明らかになった。図 16bdf と図 17bdf の他のネットワークでも同様の傾向があり、頑健性指標と最小 FVS サイズではどの手法もほとんど類似した変化をしているが、スパニングツリーによる手法 (水色線) のみは負の次数相関に変化している。これらの結果から、次数変化がある場合においても頑健性指標と最小FVS サイズは非常に強い相関関係にあること、一方で次数相関と頑健性の相関関係は弱くなることが明らかになった。表 3 の OpenFlight での次数変化する場合の相関係数においても、頑健性と最小 FVS サイズが 0.98 なのに対して次数相関は 0.53 とかなり小さい値になっている。

38

これらの結果をまとめると、次数変化の有無に関わらず頑健性と最小 FVS サイズは非常に強い相関関係にあることが分かった。一方で、これまで考えられてきた次数相関と頑健性は最小 FVS サイズよりも相関関係としては弱く、また次数の変化がある場合には負の次数相関でも非常に強い頑健性が実現できることが明らかになった。

3.4.5

次数変化リワイヤリングによる次数分布の変化

これまでの結果から、次数変化する場合には頑健性が大幅に改善すること、次数変化の手法の間に大きな差がないことが分かっている。そこで、今回比較した次数変化の三手法がどのように次数分布を変化させているのかを示すことで、次数分布の変化と頑健性の向上の関係性を議論する。図 18-20a に OpenFlight、Email、Yeast におけるリワイヤリン

グ後の次数分布を示す。それぞれの図において次数分布は両対数軸で示しており、初期の次数分布 (オレンジ点) がべき乗分布のため直線的になっている。

図 18 OpenFlight での次数変化リワイヤリングによる次数の変化。(a) 8000 回のリ

ワイヤリング後の次数分布を示す。オレンジ点が初期の次数分布、紫点が次数に置き換えた手法、緑点が提案手法、水色点がスパニングツリーによる手法。(b) リワイヤリン

グによる最大次数と最小次数の変化。各色の上側の線が最大次数、下側の線が最初次数に対応している。

39

図 19 Email での次数変化リワイヤリングによる次数の変化。(a) リワイヤリング後の次数分布を示す。オレンジ点が初期の次数分布、紫点が次数に置き換えた手法、緑点が提案手法、水色点がスパニングツリーによる手法。(b) リワイヤリングによる最大次数と最小次数の変化。各色の上側の線が最大次数、下側の線が最初次数に対応している。

図 18a から、OpenFlight の次数分布がすそ野の広いべき乗分布 (オレンジ点) から、平均次数 10.8 付近に集中した狭い次数分布に変化していることが分かる。このような傾向は次数変化の三手法の全てで共通しており、多くのノードが平均次数に近い次数を持っているような変化をしている。よりその傾向が顕著に見れるのが図 19a の Email であり、スパニングツリー数による手法 (水色点) は次数 10 と 9 の二つ種類の次数だけしか存在していない極端に均質な次数分布となっている。表 2 から Email の平均次数は 9.6 のため、その付近に集中していることが分かる。また、提案手法と次数に置き換えた手法も同様であり、どちらも次数 9 のノードが最も多く存在していた。図 20 の Yeast でも同様の傾向が見られて、Yeast の平均次数が 5.9 に集中した次数分布に変化している。

このように三種類の全てのネットワークにおいて、次数分布が広いべき乗分布から平均次数に集中した分布に変化していることが分かった。そこで、各手法によってどれぐらい集中しているのかを比較するために、リワイヤリング数に対する最小次数と最大次数の変化を図 18-20b に示す。図 18 の OpenFlight では、提案手法 (緑線) が最も高次数を残し40

図 20 Yeast での次数変化リワイヤリングによる次数の変化。(a) リワイヤリング後の次数分布を示す。オレンジ点が初期の次数分布、紫点が次数に置き換えた手法、緑点が提案手法、水色点がスパニングツリーによる手法。(b) リワイヤリングによる最大次数と最小次数の変化。各色の上側の線が最大次数、下側の線が最初次数に対応している。

ており、スパニングツリーの個数による手法 (水色線) が最も集中した次数分布に変化していることが分かる。また、図 19 の Email でも同様の傾向にあり、スパニングツリーの個数による手法 (水色線) が急激に最大次数を小さくしていることが分かる。また、図 19の Yeast でも同様に、提案手法が最も緩やかであり、スパニングツリーの個数による手法
が最も集中的になっている。

これらの結果から、次数変化するリワイヤリングは次数分布を均質に変化させることで頑健性と最小 FVS サイズを大幅に向上していたことが明らかになった。次数の変化を許す場合には、平均次数に集中した狭い次数分布に変化させることで、攻撃に対して頑健にすることができると示唆される。図 15-17f において、スパニングツリーの個数による手法では次数相関が負でも高い頑健性を達成していたが、この場合図 18-20a から平均次数

周辺の次数しか存在しない極端に集中した次数分布になっていることが分かる。つまり、極端に集中した次数分布においては、次数相関が負であることよりも、次数分布が均質であることの影響を大きく受けて非常に攻撃に対して頑健になると考えられる。

41

3.5 まとめ

本章では、攻撃に対する頑健性を向上する新たな手法として、ループ強化リワイヤリングを提案した。提案したループ強化リワイヤリングでは、確立伝播法によって得られる最小 FVS に含まれる確率 qi0 が小さいノード同士を繋ぐことで、新たなループを形成する

ことで最小 FVS サイズを増加させている。また、次数分布の変化が頑健性に強く影響を与えることが予想されたため、次数変化の有無で二種類のリワイヤリングを提案した。提案手法と既存手法を、三種類の実際のネットワークデータに適用することで、最小 FVS

サイズと頑健性指標の向上を比較した。次数保存において、提案したループ強化リワイヤ
リングは、最小 FVS サイズを大幅に増加することが分かった。特に、航空網とメール関係ネットワークでは、提案手法が最も最小 FVS サイズを増加している。さらに頑健性指標においても、提案手法は次数相関によるベースラインと同程度にまで向上することが分かった。メール関係ネットワークとイースト菌ネットワークでは、提案手法が最も頑健性指標を向上している。これらの結果から、次数保存においては、提案したループ強化リワ
イヤリングは最小 FVS サイズと頑健性の両方を大幅に向上することが分かった。

次数変化の場合では、提案手法は次数保存のベースラインと比較して大幅に最小 FVS

サイズと頑健性指標を向上することが分かった。ただし、次数変化の提案手法と既存手法の間では大きな差が見られず、全ての手法が同様に大幅の向上をしていた。これは、次数分布の変化が大幅に最小 FVS サイズと頑健性の向上に影響を与えるため、ループ強化の効果が相対的に小さくなったことが考えられる。例えば、OpenFlight で次数保存と次数変化で比較すると、次数保存のベースラインの二倍近くまで次数変化の提案手法は頑健性指標を向上していた。そこで、次数分布の変化と頑健性向上の関係を確かめるために、次数変化リワイヤリング後の次数分布の変化を比較した。結果から、どの次数変化リワイヤ
リングによっても平均次数周辺に集中するような狭い分布に変化していることが分かった。つまり、べき乗の広い分布から均質な次数分布に変化することで、最小 FVS サイズと頑健性の両方が大幅に向上すると考えられる。

さらに、リワイヤリングで得られたネットワークにおいて頑健性指標と最小 FVS サイ

ズ、次数相関の相関関係を調査した。次数保存と次数変化のどちらにおいても、頑健性は次数相関よりも最小 FVS サイズと強い相関関係にあることが分かった。特に、次数変化の場合では、次数相関が負になった場合でも高い頑健性を持つことがあるという驚くべき結果が得られた。これらの結果から、頑健性の向上のためには、これまで考えられてきた
次数相関よりも、最小 FVS によるループ強化がより重要であることが示唆される。

42

4 次数と距離によるリンク追加による頑健性向上
4.1 次数が変化する頑健性向上手法であるリンク追加法

本章では、攻撃に対する頑健性を向上するためのリンク追加法を提案する。まずは、頑健性向上のためのリンク追加法とリワイヤリングの違いを説明して、リンク追加法の必要性を述べる。3 章ではループ強化リワイヤリングとして、ノード数とリンク数が一定のままで頑健性を向上する手法を提案した。このようなリワイヤリングでは平均次数が一定になるため、新たな資源の追加が不必要というメリットがある。例えば、航空路線網にリワ
イヤリングを適用してネットワーク構造を変化させる場合、フライトの発着点を変更するだけでよく新たなフライトを作成する必要はない。一方で、リワイヤリングでは多くの既存リンクを除去する必要があるため、初期のネットワーク構造が残らないというデメリッ
トがある。航空路線網であれば、今まで扱っていたフライトがなくなることを意味しており、実際には経済的な問題などで変更できない可能性が高い。さらに、電力網や鉄道網などの空間に埋め込まれたようなネットワークでは、そもそも既存リンクの除去に大きなコストがかかってしまうという問題点がある。そこで、与えられたネットワーク構造を保ちながら、新たなリソースとしてリンクを追加することでより頑健にする手法が、実際のネットワークの頑健化に向けて必要になると考えられる。そこで、本章では頑健性の効率的な向上のためのリンク追加法を提案する。

リワイヤリングと異なり、リンク追加法ではノード数は一定のままだがリンク数は増加することになる。追加リンク数が増えるほど平均次数は増加していくので、頑健性も向上していくことに注意が必要になる。特に、リンク追加をくり返すことで最終的に得られる全てのノードが互いに繋がった完全グラフは、どのような攻撃に対しても最適な頑健性を持つことになる。そこで今回は、初期リンク数の数倍程度の追加リンク数の範囲で、より頑健性が向上するような手法を調査する。

本章では、先行研究で特に効果的とされている「最小次数戦略」と「最長距離戦略」の寄与をそれぞれ検討することで、頑健性向上のための効率的なリンク追加法の解明を目指す。リンク追加のためのノード対の選択方法として、最小次数戦略と最長距離戦略がそれぞれ効果的であることが分かっている。しかしながら、これらの二戦略がどのような条件でより効果的に頑健性を向上するのかなど、その関係性は未だ明らかになっていない。そこで、まずこれらの二戦略で選択されたノード対が互いに類似している場合があることを示して、最小次数戦略と最長距離戦略が頑健性に与える効果が重複する傾向があることを43

指摘する。そして、これらの効果をできるだけ区別するために「次数」と「距離」の二基準によるリンク追加法の枠組みを提案する。提案したリンク追加法をネットワークモデルと実際のネットワークデータに適用することで、多くの場合で最小次数戦略によるリンク
追加が最も頑健性を向上させることを数値的に明らかにする。

まず、先行研究によるリンク追加法について詳細に述べた後、最小次数戦略と最長距離戦略のそれぞれの重複について議論する。その後、「次数」と「距離」の二基準によるリンク追加法の枠組みを提案する。提案した枠組みによるリンク追加法を、ネットワークモ
デルと実際のネットワークデータに適用することで、頑健性の向上を比較する。

4.2 頑健性向上のためのリンク追加法の先行研究

最も基本的な手法として、一様ランダムに追加先を選択するランダムリンク追加法が考えられている [10, 28]。このようなランダムリンク追加法でも、平均次数が増加していく

ためスケールフリーなネットワークや地理的ネットワークの頑健性を向上することができ
ることが数値シミュレーションで示されている。しかしながら、これまでの研究から、同じ追加リンク数でもより頑健性を向上するようなリンク追加法が提案されており、特に効果的なリンク追加法として「最小次数戦略」と「最長距離戦略」の二つがある。

4.2.1

最小次数戦略「最小次数戦略」とは、最小次数を持った非連結ノード対にリンク追加する手法である [10–13]。スケールフリーなネットワークにおいて、同じ追加リンク数ではランダムリ

ンク追加よりも最小次数戦略がより頑健性を向上することが数値的に示されている [10]。
また 3 章の次数変化するリワイヤリングでは、最小次数が増加することで均質な次数分布に変化して、より頑健性が向上していた。そのため、最小次数戦略は次数分布を均質にすることで頑健性を向上しているとみなすことができる。最小次数戦略によるリンク追加法
は以下のようになる。

最小次数戦略によるリンク追加

1. 最小次数ノード集合を選択する。

2. 1. の集合の中で非連結なノード対 (i, j) をランダムに選択する。

3. 1. の集合から選択できない場合は、第二最小次数ノード集合を選択候補に入れる。
4. 新規リンク (i, j) を追加する。
5. 1. に戻る。

44

注意点として 2. の際に最小次数ノード集合から非連結ノード対が選択できない可能性がある。例えば、リンクの追加をくり返したことで最小次数ノードが一つだけになった場合

や、互いに連結しているノードのみになった場合などが考えられる。その場合には 3. のように次に小さい次数を持っているノード集合から選択する。

より複雑な構造を持つネットワークにおいても最小次数戦略は効果的に頑健性を向上す

ることが知られている。例えば、いくつかのネットワークが互いに組み合わさったような相互依存ネットワークや多重ネットワークにおいても、最小次数戦略が頑健性向上に有効であることが数値的に示されている [49]。さらに、相互依存関係にある電力網や通信網において、ランダムな故障や次数順攻撃によって起きるカスケード故障に対する頑健性の向上にも最小次数戦略は効果的である [50]。

4.2.2

最長距離戦略「最長距離戦略」とは、ネットワーク内で最も離れている非連結ノード対にリンク追加する手法である [14]。これは攻撃などでネットワークの中心となっている高次数ノードが除去された時に、そのバックアップとなるような別の経路を形成するというコンセプトで提案されている。このような長距離戦略によるリンク追加法は、スケールフリーなネット
ワークにおいて、ランダムリンク追加法や最小次数戦略によるリンク追加法よりも頑健性が向上することがあることが数値的に示されている。最長距離戦略によるリンク追加法
は、以下の手順となる。

最長距離戦略によるリンク追加

1. 全てのノード組合せの最短経路を求める。

2. 全てのノード組合せの中で最短経路が最も長いノード対 (i, j) を選択する。
3. 新規リンク (i, j) を追加する。
4. 1. に戻る。

2. において複数のノード対が候補になった場合は、そこからランダムに選択する。また、最長距離のため選択されたノード対 (i, j) は必ず非連結となっている。

バックアップとなる別経路を形成するという最長距離戦略の考え方は、ループ強化リワ

イヤリングと非常に似ている。しかしながら、これまでループの距離が頑健性に与える影
響はあまり研究されていない。特殊な例として、地理上に埋め込まれたネットワークでは空間上の制約により小さい局所的なループを形成するため、ループの長さに関連する研究がされている。例えば、パーコレーション理論の解析により、短いループを多数持

つ地理上ネットワークはランダムな故障に対して連結性が脆弱であることが分かってい45

る [51, 52]。また、地理上ネットワークでは、長いリンクを追加することで、攻撃に対する頑健性を向上させることができることが数値的に示されている [53]。これらの知見から、より長い距離にリンクを追加することで、長距離のループが形成されて、頑健性が向上することが予想できる。そこで本章では、この長距離リンクが頑健性に与える影響を議論するために、距離の基準によるリンク追加法の枠組みを提案する。

4.2.3

組織論における長距離交際

長距離の関係の重要性は、組織論の観点からも議論されてきた [54, 55]。代表例として、

1997 年のアイシン火災からの早期復旧がある。トヨタ自動車は、自動車の部品であるプ

ロポーショニングバルブの約 90% を火災が起きた工場で生産していた。火災によって工場は全焼してしまったため、この部品の供給が全工場で停止してしまい、自動車生産の全面的な停止になる事態になる緊急事態に陥ってしまった。そこで、この部品を他工場で代替生産することになったのだが、この時に長距離の関係が活用された。トヨタには自主研と呼ばれる、複数のサプライヤーが一緒に勉強するような会を日頃から開催していた。この会によって、サプライヤー同士が結びついて、横の遠いつながりが構築されていたため、部品の早期代替生産が可能になったと考えられている。このように、組織論の観点からも長距離による代替経路が重要であることが分かっている。

4.3 最小次数戦略と最長距離戦略の類似性

最小次数戦略と最長距離距離戦略、それぞれで選択されたノード対が類似している場合があることを議論する。図 21A に類似している場合、図 21B に異なっている場合の模式的な図を示す。類似している場合の例として、ループのない木のネットワークを考える。
図 21A の青色のノードのように、木の末端には次数 1 の葉ノードが存在する。このような木において、最小次数戦略でノード対を選択する場合、最低次数をもつ葉ノードの中からランダムにノード対が選択されることになる (図 21A の赤色リンク)。また、木において葉ノードはネットワークの末端にあるため、ランダムに選択した場合でも距離が長くなる傾向がある。一方で、長距離戦略でノード対を選択する場合、末端同士が選択されることになるため、最も離れた葉ノードが選択される (図 21A の緑色リンク)。このように、ループの無い木では、最小次数戦略と最長距離戦略の両方が葉ノードを選択することにな
り、類似したノード対を選択することになる。ただし、この場合では最長距離戦略は最小次数ノード集合から、最長距離のノード対を選択することになる。

ループのあるネットワークでは必ずしも類似したノード対を選択する訳ではない。それ

46

図 21

最小次数戦略と最長距離戦略によるリンク追加。(A) 最小次数戦略と最長距離戦略は、ループの無い木では類似したノードを選択し、(B) ループを持つネットワーク

上では異なるノードを選択する。赤色のリンクが最小次数戦略、緑色のリンクが最長距離戦略によるものを示す。青色は葉ノードを示す。

ぞれの戦略が全く異なるノード対を選択するという極端な例を図 21B に示す。このネットワークでは、最大次数を持ったノードが両端に存在して、その間を低次数ノードで繋いでいる構造をしている。そのため最小次数戦略では、間を繋いでいる低次数のノード対を選択することになり (図 21B の赤色リンク)、最長距離戦略では両端に存在している最大次数ノード対を選択することになる (図 21B の緑色リンク)。このようにループがある場

合では、必ずしも二つの戦略は類似したノード対を選択するわけではない。初期の平均次数が大きいネットワークや追加リンク数が多くなるほど、よりループが存在することになる。そのため、平均次数やネットワークのループの有無によって、それぞれの戦略が頑健性の向上に与える影響が変化すると考えられる。そこで本章では、複数の次数分布を持ったループの無いネットワーク、平均次数を変えたスケールフリーなネットワーク、実際のネットワークデータで比較を行う。

47

4.4 次数と距離によるリンク追加法の枠組みの提案

これまでの議論から、リンク追加による頑健性向上のために最小次数戦略と最長距離戦

略が効果的であること、二戦略によって選択されたノード対が類似する場合があることが分かった。そこで、最小次数戦略と最長距離戦略のそれぞれが頑健性の向上に与える影響を調べるために「次数」と「距離」の二段階によるリンク追加手法の枠組みを提案する。
図 22 に二段階によるリンク追加先選択の手順を示す。

一段階目では「次数」による選択として、全ノードを選択する場合と最小次数ノード集合を選択する場合の二種類を考える。本来であれば、比較のために高次数側も考慮する必要があるが、次数順攻撃は高次数ノードから順に除去するので、その間にリンクを追加したとしても頑健性をほとんど改善できない。そのため、今回は高次数ノードへのリンク追加は省略する。

二段階目では「距離」による選択として、一段階目で選択したノード集合の中から最短距離もしくはランダム、最長距離の非連結ノード対を選択する。ここで最短距離と最長距
離は、非連結ノード対の最短経路ホップ数の中で最も短いものと最も長いものを意味している。このような一段階目の二種類と二段階目の三種類から、合計六種類のリンク追加法
を考えることができる。それぞれの命名を表 4 にまとめる。

図 22

次数と距離の基準による二段階のリンク追加先選択。Step1 では次数による選択を行い、Step2 では Step1 のノード集合から距離による選択を行う。

48

表4

最短距離
ランダム
最長距離

次数と距離の二段階による六種類のリンク追加法の命名.

全ノード

最小次数

(ShortAdd)(min-k ShortAdd)

最短距離追加最小次数-最短距離追加

ランダム追加(RandAdd 法) [10, 28]
最長距離追加(LongAdd) [14]最小次数追加(min-k RandAdd) [10–13]
最小次数-最長距離追加(min-k LongAdd)

表 4 において、いくつかのリンク追加法は既存手法と同じものになっているため、それを整理しておく。まず、一段階目が全ノードで二段階目がランダムであるランダム追加 (RandAdd) はランダムリンク追加法 [10, 28] と同じである。RandAdd は次数と距離によらない一様ランダムなリンク追加となっている。また、一段階目が最小次数で二段階目がランダムである最小次数追加 (min-k RandAdd) は最小次数戦略によるリンク追加
法 [10–13] と同じである。さらに、一段階目が全ノードで二段階目が最長距離である最長
距離選択 (LongAdd) は最長距離戦略によるリンク追加法 [14] と同じである。

提案した二段階のリンク追加法の選択の順序を逆にすることも考えられる。その場合は、一段階目に「距離」から選択して、二段階目に「次数」から選択することになる。この場合、特に最長距離を持つノード対集合を選択すると、その候補集合に含まれるノード対の個数は非常に少なくなってしまう。そのため、二段階目の選択肢が限定的なものになってしまい「次数」による選択の効果が小さくなることが予想される。一方で、スケー
ルフリーなネットワークでは最小次数を持つノードが多いことを考えると、一段階目に「次数」から選択することでより多くのノードが候補集合として含まれることになる。このため、提案手法では一段階目を「次数」、二段階目を「距離」とする二段階のリンク追加法を提案した。

49

4.5 比較のためのネットワークモデル

提案した次数と距離の二段階による六種類のリンク追加法をネットワークに適用して、頑健性の向上の比較を行う。最小次数戦略と最長距離戦略の類似性の議論から、ループの有無によってそれぞれの戦略で選択するノード対が変化することが考えられる。そこで、リンク追加法を比較するためのネットワークを生成するモデルとして、べき乗の次数分布を持つネットワークを生成する Barabási-Albert モデル [56] とその拡張である Growing

Network モデル [57–59] と逆優先的選択モデル [60] を述べる。これらの手法によって、次数分布を連続的に変化させながらループの無い木のネットワークを生成することができる。

Barabási-Albert モデルは非常に有名なネットワーク生成法で、次数が高いノードほど優先して接続されるという優先的選択によってべき乗の次数分布を持つネットワークを生成する手法である。具体的なアルゴリズムは以下のようになる。

Barabási-Albert モデル

1. ネットワークに新規ノード t を追加する。

2. ノードの次数に比例した接続確率 pi ∝ ki で既存ノード i を選択する (優先的選択)。
3. 新規リンク (t, i) を追加する。

4. 2-3. をノード t の次数が m になるまでくり返す。
5. 1. に戻る。

このような優先的選択により、べき乗の次数分布を持ったネットワークを生成することができる。また、ここでは初期ネットワークは互いに接続した二つのノードとする。m を変化させることで平均次数を変化させることができて、特に m = 1 の場合はループの無い
ネットワークとなる。

Barabási-Albert モデルでは、べき乗の次数分布のネットワークしか生成することができない。そこで、接続確率 pi を変えることで、べき乗以外の次数分布を持ったネット

ワークを生成する手法として Growing Network モデルと逆優先的選択モデルが提案されている。Growing Network モデルでは接続確率を pi ∝ kiν , (ν ≥ 0) とする。ν = 1 では

Barabási-Albert モデルとなり、ν = 0 ではランダム成長モデルとなる。ランダム成長モ

デルでは、リンクの接続先を次数によらず決めることになり、その次数分布は指数分布となる。0 < ν < 1 では次数分布は、べき乗分布と指数分布の間の分布となり、それをカットオフ付きべき乗分布という。パラメータ ν を 1 から 0 に変化させることで、次数分布50はべき乗から指数分布へと連続的に変化することになる。図 23a にパラメータ ν を変化させた場合の次数分布の変化を示す。両対数軸であることに注意すると、パラメータ ν を小さくするとより狭い分布へと変化していることが分かる。

逆優先的選択は、優先的選択を逆転させたもので、低次数ノードほど優先的に接続するようにした手法である。そこで接続確率 pi ∝ ki , β ≤ 0 とする。β = 0 ではランダム成−β長モデルと同じのため、次数分布は指数分布となる。パラメータ β が大きくなるほど、次数分布は指数分布からより狭い分布へと変化していく。図 23b にパラメータ β を変化させた場合の次数分布の変化を示す。片対数軸であることに注意すると、パラメータ β が大きくなることでより狭い分布に変化していることが分かる。

図 23 Growring Network モデルと逆優先的選択モデルによる次数分布の変化。(a)ν = 1 ではべき乗分布、ν = 0 では指数分布となっている。(b) β = 0 では指数分布となっている。N = 10000 ノードと m = 3 のネットワークでの結果を示す。

Growing Network モデルと逆優先的選択モデルと組合わせることで、べき乗分布からカットオフ付きべき乗分布、指数分布、さらに狭い分布へと連続的に次数分布を変化させながらネットワークを生成することができる。さらに m = 1 とすることで、それぞれの次数分布を持ったループの無い木のネットワークを生成することができる。これらによって生成されたネットワークにおいてリンク追加法による頑健性の向上を比較する。

注意点として、このような新規ノードの追加を繰り返す生成手法では、生成過程に依存

した局所的な構造が現れることがある。例えば、逆優先的選択では β を非常に大きい値

51

にしてしまうと、ハシゴのように連なった鎖状構造が出てきてしまう [60]。このような局所構造は頑健性に影響を与えてしまう可能性があるため、局所構造を除去したランダム化

ネットワークでも比較を行う。ランダム化は、コンフィギュレーションモデル [61, 62] によって行う。ただし、今回の結果からはランダム化の有無に関わらず同様の傾向を得ることができた。

ランダム化のためのコンフィギュレーションモデル [61, 62] について述べる。コンフィ

ギュレーションモデルは、次数分布を保存したままネットワークをランダム化することで局所的な構造を除去する手法である。図 24 に模式的に示す。まず、全てのリンクを半分に分断して、ノードが半分のリンク (スタブ) で接続された状態にする。次に、ランダムに二つのスタブを選択して、それらを再接続してリンクにする。ただし、ここで多重リンク
や自己ループが起きないように注意する。このスタブの接続を繰り返し行い、全てのスタ
ブをリンクに再接続することでネットワークを生成する。一般的なコンフィギュレーショ
ンモデルでは全体が連結である必要はないが、本稿では連結性の頑健性について評価した

いため、生成されたネットワークが全連結になるようにリワイヤリングする必要がある。
ここでは、バラバラの連結成分から二本のリンクを選択して、互いが繋がるようにリワイ
ヤリングを行う。これを全連結になるまでくり返し行う。

図 24

コンフィギュレーションモデルの模式図

ループのないネットワークとして、Growing Network モデルと逆優先的選択モデルで生成した、べき乗分布からカットオフ付きべき乗分布、指数分布、さらに狭い分布へと連続的に変化していく範囲の次数分布を持ったネットワークと、それらをコンフィグレー

ションモデルによってランダム化したもので比較を行う。また、ループを持つネットワー

クとして Barabási-Albert モデルで生成されたスケールフリーネットワークを用いて、平均次数とノードサイズの影響を議論する。

52

4.6 次数と距離によるリンク追加法による頑健性向上の評価

ネットワークモデルに対して、提案した枠組みによる六種類のリンク追加法を施して、頑健性の向上を比較する。比較では、典型的な攻撃として次数順攻撃による頑健性指標

RHDA [4] と、現状で最も強力な攻撃として BP 攻撃による頑健性指標 RBP を用いる [31]。
BP 攻撃は??節で詳細を説明している。また、リンク追加法における攻撃に対する頑健性とループ強化との関係を調べるために、確率伝播法による最小 FVS サイズを求める [39]。
攻撃に対する頑健性とは異なるネットワーク指標として、ネットワーク効率 E と直径

D でも比較を行う。ここでネットワーク効率 E は、ネットワーク内のノードが離れれば離れるほど通信の効率が低下することから提案されている [63]。そこで、次にように定義
される。

E=

! 1
1
,
N (N − 1) i,j dij

ここで dij はノード i, j の間の最短経路のホップ数、

"

(21)

i,j は全てのノード対の組合せで和をとること示す。この E の値が大きいほど、ネットワーク内の最短経路のホップ数が小さくなるため、効率が良くなる。スケールフリーなネットワークでは、頑健性とネットワー

ク効率はトレードオフの関係があることが数値的に示されている [64]。一方で、成長していく玉ねぎ状ネットワークでは、高い頑健性とネットワーク効率が共存している [42]。また、頑健性は考慮せずに、ネットワーク効率だけを向上するリンク追加法も提案されている [13, 65]。そこで、提案した頑健性向上のためのリンク追加法が効率にどのような影響を与えるのかを調査する。また、直径 D は、ネットワークの全てのノード対で最も最短経路が長いもののホップ数で定義される。そのため、直径 D が長いほど最短経路に長いものがあるため、効率は悪くなる。ネットワークの効率に関係する指標の一つとして、リンク追加法による直径 D の変化も調査する。

4.6.1

ループの無いネットワークでのリンク追加法による頑健性向上

まずループの無い木のネットワークに、六種類のリンク追加法を適用した結果を示す。

パラメータ β = 5 の逆優先的選択モデルとパラメータ ν = 0 と 1 の Growing Network モ
デルで m = 1 とすることでループの無い木のネットワークを生成する。生成されたネッ

トワークはそれぞれ指数分布より狭い分布、指数分布、べき乗分布の次数分布を持つ。また、生成したネットワークをコンフィギュレーションモデルによってランダム化したネッ
トワークでの結果も示す。以下、ネットワークは 1000 ノードとして、また全ての指標は

53

100 試行した平均値で示す。

提案した六種類のリンク追加法による結果は、一段階目で全ノードを選択したものを点線、最小次数ノード集合を選択したものを実線で示す。二段階目で最短距離、ランダム、
最長距離で選択したものを青色、赤色、緑色で示す。また各図の ABC に、それぞれ β = 5の逆優先的選択モデル、ν = 0 と ν = 1 の Growing Network モデルでの結果を示す。

図 25 と図 26 にリンク追加法による次数順攻撃による頑健性指標 RHDA の変化を示す。

これらの図では全てのリンク追加法によって頑健性指標は上昇していることが分かる。そのため同じ追加リンク数でより頑健性を向上する手法について考える。図 25ABC では

min-k LongAdd と min-k RandAdd(緑実線と赤実線) が最も RHDA を向上していることが分かる。この二手法はほとんど同じような変化をしており、RHDA の値にほとんど差が見られない。また、図 26ABC からコンフィギュレーションモデルを適用した後の結果でも同様の傾向があることが分かる。これらの結果からループの無いネットワークにおいては、最小次数戦略が非常に頑健性の向上に効果的であることが明らかになった。ただし、最小次数を選択していたとしても短距離ノード対にリンクを追加していた場合は頑健性の向上が小さいことが、min-k ShortAdd(青実線) の結果から分かる。

どの図においても他の実線と比べて min-k ShortAdd は RHDA の向上が小さくなっている。次数を考慮しない距離のみによるリンク追加法の結果 (点線) では、RHDA の向上が大きい方から LongAdd(緑点線)、RandAdd(赤点線）、ShortAdd(青点線) となっている。そのため追加するリンクが離れたノード対を繋ぐほど頑健性は向上することが分かる。特に、ShortAdd(青点線) は六手法の中で最も頑健性の向上が小さくなっており、短距離のリンク追加が頑健性の向上にあまり寄与しないことが分かる。

多くの場合では LongAdd は min-k LongAdd や min-k RandAdd と比べると RHDAの向上は小さい。しかしながら例外的に、追加リンク数が少ない場合には、LongAdd が
最も RHDA を向上する場合がある。例えば、図 25B の追加リンク数が 380 本以下の部分

や図 25C の 530 本以下では LongAdd が最も RHDA を向上している。図 25A では少し分かりにくいが、追加リンク数が 170 本以下では最も RHDA を向上している。このような傾向はコンフィギュレーションモデル後の結果でも見ることができる。これらの結果か
ら、追加リンク数が非常に少ない場合には、最小次数戦略よりも最長距離戦略がより頑健性の向上に寄与することが明らかになった。

次に図 27 と図 28 にリンク追加法による BP 攻撃による頑健性指標 RBP の変化を示す。BP 攻撃の方が次数順攻撃よりも激しいため RBP の値は RHDA の値と比べると少し小さくなっている。ただし得られた結果は、次数順攻撃に対する頑健性 RHDA とほとん
ど同じ傾向にある。まず、図 27ABC と図 28ABC において min-k LongAdd と min-k

54

図 25

リンク追加法による次数順攻撃に対する頑健性指標。(A) β = 5 の逆優先的選択モデル、(B) ν = 0 と (C) ν = 1 の Growing Network モデルでの結果。横軸は追加リンク数を示す。

図 26

リンク追加法による次数順攻撃に対する頑健性指標。それぞれコンフィギュ

レーションモデルを適用した (A) β = 5 の逆優先的選択モデル、(B) ν = 0 と (C)ν = 1 の Growing Network モデルでの結果を示す。横軸は追加リンク数を示す。

RandAdd(緑実線と赤実線) が最も RBP を向上している。また、短距離リンクの追加は、
BP 攻撃に対する頑健性の向上においても寄与が小さい。図 27ABC と図 28ABC では
min-k ShortAdd と ShortAdd(青実線と青点線) はどちらも RBP の向上が小さくなって
いる。

55

図 27

リンク追加法による BP 攻撃に対する頑健性指標。(A) β = 5 の逆優先的選択

モデル、(B) ν = 0 と (C) ν = 1 の Growing Network モデルでの結果。横軸は追加
リンク数を示す。

図 28

リンク追加法による BP 攻撃に対する頑健性指標。それぞれコンフィギュレー

ションモデルを適用した (A) β = 5 の逆優先的選択モデル、(B) ν = 0 と (C) ν = 1の Growing Network モデルでの結果を示す。横軸は追加リンク数を示す。

ループの無いネットワークへのリンク追加法による頑健性向上への寄与をまとめる。多くの場合では min-k LongAdd と min-k RandAdd が最も頑健性指標を向上しており、最小次数戦略がより頑健性の向上に効果的であることが明らかになった。ただし短距離リンクの追加は頑健性の向上への寄与が小さく、最小次数戦略であっても最短距離へリンク追加する場合は頑健性の向上が小さくなってしまう。さらに、追加リンク数が極端に少ない
場合には、最小次数戦略よりも最長距離戦略がより頑健性の向上に効果的であることが分
かった。

56

図 29 と図 30 に最小サイズの変化を示す。これまでの頑健性指標の結果とは異なり min-k ShortAdd(青実線) が最も最小サイズを増加していることが分かる。min-k

ShortAdd は最も近い葉ノードの間にリンクを追加することになるので、ネットワークの末端に小さなループを形成することになる。このような末端の三角形は最小サイズの増加には寄与するが、頑健性の向上には繋がらないことが分かる。そのため、このような短距離ループが形成される場合には、最小サイズと頑健性指標が必ずしも相関関係にないということが明らかになった。一方で min-k ShortAdd を除くと min-k RandAdd と min-k

LongAdd(赤実線と緑実線) がより最小サイズを増加させている。これは 3 章の議論から、最小次数にリンク追加することで次数分布が均質になって最小サイズが増加したと考えられる。つまり min-k RandAdd と min-k LongAdd は頑健性と最小サイズの両方を向上させることができることが分かる。

図 29

リンク追加法による最小サイズの変化。(A) β = 5 の逆優先的選択モデル、(B)ν = 0 と (C) ν = 1 の Growing Network モデルでの結果。横軸は追加リンク数を示す。

表5

ループの無いネットワークにおいて最も RHDA 、RBP 、最小サイズを向上した手法の一覧

RHDA
RBP
|FVS|

Figs. 25,26
Figs. 27,28
Figs. 29,30

β=5

ν=0

ν=1

min-k RandAdd

min-k RandAdd

min-k RandAdd

min-k LongAdd

min-k LongAdd

min-k LongAdd

min-k RandAdd

min-k RandAdd

min-k RandAdd

min-k LongAdd

min-k LongAdd

min-k LongAdd

min-k ShortAdd

min-k ShortAdd

min-k ShortAdd

57

図 30

リンク追加法による最小サイズの変化。それぞれコンフィギュレーションモデ

ルを適用した (A) β = 5 の逆優先的選択モデル、(B) ν = 0 と (C) ν = 1 の Growing

Network モデルでの結果を示す。横軸は追加リンク数を示す。

表 5 にループの無いネットワークに対して最も頑健性もしくは最小サイズを向上した手法をまとめる。次数順攻撃と BP 攻撃の両方に対して min-k RandAdd と min-k

LongAdd が最も頑健性を向上していた。一方で、最小サイズは min-k ShortAdd が最も増加させていた。

次に、ループの無いネットワークにおいてリンク追加法が直径 D とネットワーク効

率 E に与える影響を調査する。図 31 と図 32 にリンク追加法による直径 D の変化を示す。図より明らかに min-k ShortAdd と ShortAdd(青実線と青点線) が直径 D を減らしていないことがわかる。これらの手法は最短距離のノード対にリンクを追加するため、直径の減少率が小さいと考えられる。一方で、それら以外の四手法はどれも非常に近い値となっており、どの手法も直径 D を急減していることが分かる。特に図 31BC では

LongAdd(緑点線) が最も直径 D を減少させている。LongAdd は最長距離のノード対にリンク追加するため、このように急減していると考えられる。一方で、距離を考慮しない

min-k RandAdd や RandAdd(赤実線と赤点線) でも同様の減少が見られている。

図 33 と図 34 にリンク追加法によるネットワーク効率 E の変化を示す。ネットワーク

効率 E でも直径 D と同様に短距離へのリンク追加はあまり向上に寄与していないことが分かる。各図において、min-k ShortAdd と ShortAdd はどちらも他手法と比較して向上
が小さくなっている。つまり、短距離のリンクの追加がネットワークの最短経路に与える影響が小さいことを示している。一方で、他手法はどれも大きくネットワーク効率 E を改善していることが分かる。その中でも特に RandAdd が最もネットワーク効率 E を向

58

図 31

リンク追加法による直径 D の変化。(A) β = 5 の逆優先的選択モデル、(B)ν = 0 と (C) ν = 1 の Growing Network モデルでの結果。横軸は追加リンク数を
示す。

図 32

リンク追加法による直径 D の変化。それぞれコンフィギュレーションモデル

を適用した (A) β = 5 の逆優先的選択モデル、(B) ν = 0 と (C) ν = 1 の Growing

Network モデルでの結果を示す。横軸は追加リンク数を示す。

上しているが、差自体はそこまで大きくない。このことから頑健性を効率的に向上するリ

ンク追加法 (min-k RandAdd や min-k LongAdd) は、ランダムリンク追加法と同程度まではネットワーク効率 E を向上することができるということが分かった。

59

図 33

リンク追加法によるネットワーク効率 E の変化。(A) β = 5 の逆優先的選択モ

デル、(B) ν = 0 と (C) ν = 1 の Growing Network モデルでの結果。横軸は追加リンク数を示す。

図 34

リンク追加法によるネットワーク効率 E の変化。それぞれコンフィギュレー

ションモデルを適用した (A) β = 5 の逆優先的選択モデル、(B) ν = 0 と (C) ν = 1の Growing Network モデルでの結果を示す。横軸は追加リンク数を示す。

表 6 にループの無いネットワークにおけるリンク追加法の直径 D とネットワーク効

率 E への寄与をまとめる。直径 D では最長距離戦略による LongAdd が最も効果的に減少させていた。一方で最短距離リンクへの追加をする min-k ShortAdd と ShortAdd は
直径をあまり減少させなかった。ネットワーク効率 E ではランダムリンク追加法である

RandAdd が最も向上していた。ただし、頑健性を効率的に向上する min-k RandAdd や
min-k LongAdd も非常によくネットワーク効率 E を向上している。一方でネットワー
ク効率 E の向上でも min-k ShortAdd と ShortAdd は寄与が小さいことが分かった。

60

表6

ループの無いネットワークにおいて最も直径 D もしくはネットワーク効率 E を向上した手法の一覧

4.6.2

β=5

ν=0

ν=1

D

Figs. 31,32

LongAdd

LongAdd

LongAdd

E

Figs. 33,34

RandAdd

RandAdd

RandAdd

スケールフリーネットワークでのリンク追加法による頑健性の向上

ループの無いネットワークでの議論から min-k RandAdd と min-k LongAdd がより頑健性の向上に寄与することが分かった。そこで平均次数 #k$ や初期ノード数 N がリンク追加法による頑健性向上に与える影響についてを調査する。ここではパラメータ ν = 1の Growing Netwok モデルで生成されるスケールフリーなネットワークで比較を行う。
図 35 に N = 500、1000、5000 と m = 1、2 のスケールフリーなネットワークにリンク追加した後の RHDA を示す。ここで m = 1 のスケールフリーネットワークは木である。
ここで平均次数は近似的に #k$ ≈ 2m となることに注意。それぞれ平均次数 #k$ やノード
数 N が異なるため、横軸は初期リンク数に対する追加リンク数の割合となっている。

まずノード数 N の影響を議論する。図 35ACD はそれぞれ m = 1 での N = 500、

1000、5000 での結果を示している。各図を比較すると、追加リンク割合に対して同じよ

うな変化をしており、大きく異なっている部分が無いことが分かる。また、図 35BDF はそれぞれ m = 2 での N = 500、1000、5000 での結果を示している。こちらも同様に、ノード数 N が変化した場合でも、それぞれの手法による頑健性の向上にはほとんど変化が見られなかった。これらの結果から、同じ追加リンク割合であればノード数の影響は無視できるほど小さいことが分かった。

一方で、初期の平均次数 #k$ はリンク追加による頑健性向上に大きな影響を与えることが分かった。図 35 の右列が m = 1、左列が m = 2 に対応している。これらを比較すると明らかな違いとして m = 2 では min-k ShortAdd(青実線) が非常に良く RHDA を向上していることが分かる。ループの無いネットワークで最も RHDA を向上していた min-k

RandAdd と min-k LongAdd(緑実線と赤実線) と同程度かそれ以上にまで向上している。
つまり、ループがある場合は、距離に関わらず最小次数ノード対にリンク追加することが最も頑健性向上に効果的であることを示している。ループがある場合でも ShortAdd(青点線) は RHDA をあまり向上しないことからも、平均次数が高い場合には最小次数戦略

が、より頑健性向上に効果的になると分かる。特に、min-k ShortAdd は木では末端に局所的なループを形成していたのに対して、平均次数が多くループがあるネットワークでは

61

図 35

スケールフリーネットワークでのリンク追加法による次数順攻撃に対する頑健性の変化。ACD は m = 1、BDF は m = 2 での結果。また上から AB は N = 500、CD は N = 1000、EF は N = 5000 での結果を示す。横軸は初期リンク数に対する追加リンク数割合となっている。

62

葉ノードがないため末端でのループ形成をしなくなる。この局所的な小さいループの形成をしないことで、最小次数戦略による次数分布の均質化によって頑健性が大きく向上する
ようになったと考えられる。

初期ネットワークが木の場合でも、追加リンク割合が非常に大きくなった場合には平均次数が増えることで最小次数戦略がより効果的になると考えられる。例えば、図35AC では初期リンク数の 4 倍程度までリンクを追加すると、min-k ShortAdd が min-k

RandAdd や min-k LongAdd と同程度にまで RHDA を向上するようになっている。先ほどの議論と同様に、平均次数が増加するほど最小次数戦略がより頑健性向上に効果的になることと合致する。またさらに追加リンク割合が非常に多くなり平均次数が上昇する

ほど、各手法間の頑健性向上の差が小さくなることが分かる。例えば、図 35A では既存リンク数の 10 倍ほどの追加リンクをした場合には ShortAdd 以外の手法がほとんど同じ

RHDA となっている。これは平均次数が増加する効果が頑健性の向上に大きく寄与するた
め、次数分布や距離の効果が相対的に小さくなるためと考えられる。

図 36

スケールフリーネットワークでのリンク追加法による次数分布の分散の変化。

初期ネットワークは N = 1000 ノードで (A)m = 1 と (B)m = 2。横軸は追加リンク数となっている。

ここまでの議論から最小次数戦略による次数分布の均質化が頑健性の向上に効果的であることが明らかになってきた。そこで実際に各リンク追加法がどのように次数分布を変化させていくのかを調べる。図 36 に各リンク追加法による次数分布の分散の変化を示す。
また図 37 に各リンク追加法による次数分布の変化を、1000 追加リンク数ごとに示す。図

63

図 37

スケールフリーネットワークでのリンク追加法による次数分布の変化。Lon-

gAdd は低次数ノードにリンクを追加する傾向があり、 ShortAdd は高次数ノードにリンクを追加する傾向がある。 (A) ShortAdd、(B) min-k ShortAdd、(C)
RandAdd、(D) min-k RandAdd、(E) LongAdd、(F) min-k LongAdd での結果を示す。初期ネットワークは N = 1000 ノードと m = 2。全て両対数軸となっている。

64

36AB はそれぞれ m = 1 と m = 2 での結果を示しているが、ほとんど同じ傾向にあることが分かる。まず最小次数戦略による三種類のリンク追加法は最小次数ノードを必ず選択するため、次数分布の変化は全く同じになる。そのため図 36 では全ての実線が重なっており、図 37BDF はほとんど同じように変化している。一方で、次数を考慮しない距離のみによるリンク追加法では、分散が小さい方から LongAdd、RandAdd、ShortAdd となっている。最小次数戦略と同様に LongAdd も分散を小さくして、次数分布を均質にしていることが分かる。これは図 37E の次数分布の変化でも示す通り、LongAdd は次数の小さいノードに対してリンクを追加する傾向があることが分かる。図 37E では低次数側がより図中の右側にシフトしていることが分かる。これは最小次数戦略と最長距離戦略の類似性の議論と同様に、ネットワークの周辺部に低次数ノードが存在することが原因と考えられる。つまり、今まで関連性が議論されてこなかった二戦略の間に、類似した次数分布の変化があることが数値的に明らかになった。

一方で、図 37A から、ShortAdd は高次数ノードにリンクを追加する傾向があることが分かる。低次数側はあまり変化していないのに対して、高次数側が図中の右側にシフトしている。また図 36 からも ShortAdd のみ分散がどんどん増加していることが分かる。
このように ShortAdd が高次数ノードを選択するのは、以下の理由があるためと考えられる。ShortAdd では最短距離のノード対を選択するので、あるノードの隣接でかつ非連結なノード対が選択されることになる。つまり、ShortAdd ではリンクを辿った先にあるノードが選択されやすいことになる。ランダムにリンクを一本選択して、その先のノードを片方選択する場合、各ノードが選択される確率が次数に比例することが知られている。
そのため ShortAdd でも次数が多いノードほど選択されやすくなり、高次数ノードにリンクが追加されることになると考えられる。

次はリンク追加法によって選択されたノード対がどのような距離を持っているのかを示す。図 38 に各リンク追加法で選択されたノード対の間の最短経路ホップ数を示す。距

離のみで選択する三手法を左列、最小次数による三手法を右列に示す。まず図 38 左の距離のみで選択する三手法は選択方法がそのまま反映されており、長いほうから順番にLongAdd、RandAdd、ShortAdd となっている。特に ShortAdd は追加本数によらず距離は一定となっている。一方で LongAdd によってリンクを追加することで、最長距離がより小さくなっていることが分かる。このように LongAdd は長距離のリンク追加をしているため、図 31,32 のように直径 D を最も小さくしている。

図 38 右の最小次数による三手法でも同様に、大まかには距離の長い順で min-k Lon-gAdd、min-k RandAdd、min-k ShortAdd となっている。ただし、図 38 右の最小次数による三手法では min-k LongAdd と min-k ShortAdd がギザギザの変化をしているこ

65

図 38

スケールフリーネットワークでのリンク追加法によって選択されたノード対の距離。初期ネットワークは N = 1000 ノードで (A)m = 1 と (B)m = 2。横軸は追加
リンク数となっている。

とが分かる。これは一段階目で選択した最小次数ノード集合のサイズがリンク追加をくり返すことで小さくなることで起きている。最小次数ノードの個数が減ると、二段階目の距離による選択の候補が限定されてしまうため、min-k LongAdd ではより距離が短くなり、

min-k では距離が長くなってしまう。ところが最小次数戦略によるリンクの追加によって最小次数の値が変化した場合は、次のステップから一段階目で選択する最小ノード集合が増えることになる。すると、今まで候補になかったノードが選択肢として新たに含まれて、二段階目の距離の選択肢が増加する。例えば min-k LongAdd では最小次数の値が変化するまでは距離が短くなっていき、変化した時に距離が長くなっている。

スケールフリーネットワークでの結果をまとめる。まずリンク追加法による頑健性の向上には、ノード数はほとんど影響しなかった。一方で、平均次数は非常に大きな影響を与66

えることが分かった。特に、ループのあるネットワークでは、最小次数戦略であれば非常に短距離のリンク追加でも効果的に頑健性を向上することが分かった。また最長距離戦略

は次数の小さいノードを選択する傾向があることが数値的に示された。これらの結果は、より最小次数戦略による次数分布を均質にする効果が頑健性の向上に重要であることを意味している。

4.7 実際のネットワークデータにおけるリンク追加法による頑健性の向上
実際のネットワークデータとして、技術的ネットワーク、社会的ネットワーク、生物学的ネットワークに分類される航空会社のネットワーク (AirTraffic) [19]、電子メールのやりとり (Email) [47]、イースト菌のタンパク質間相互作用 (Yeast) [66] を用いる。ここで航空網データは表 2 の OpenFlight ではなく、表 7 の AirTraffic を使用している。提案したリンク追加法では距離の計算を繰り返し行う必要性があるため、ノード数の小さいネッ
トワークを使用した。
表7

現実ネットワークのデータ。左からネットワークの名前、ノード数、リンク数、

次数相関、最小次数、平均次数、最大次数、直径、参考文献を示す。メールとイースト
菌のデータは表 2 に記載している。

Network

N

M

r

Min k

<k>

Max k

D

Refs.

AirTraffic

1226

2408

-0.015

1

3.9

34

17

[19]

図 39 にそれぞれのネットワークデータでのリンク追加法による次数順攻撃による頑健性指標 RHDA の変化を示す。まず図 39ABC の全てにおいて min-k RandAdd と min-k

LongAdd(赤実線と緑実線) が最も RHDA を改善している。また m = 2 のスケールフリー
ネットワークでの結果と同様に追加リンク数が増加するほど min-k ShortAdd(青実線) がより RHDA を向上していることが分かる。図 39C のイースト菌ネットワークでは min-k

ShortAdd は min-k RandAdd と min-k LongAdd よりも RHDA の向上が小さいが、図39AB の航空網とメールやりとりネットワークでは同等かそれ以上にまで RHDA を向上している。これらの結果から実際のネットワークにおいても、最小次数戦略がより頑健性の向上に効果的であることが明らかになった。

ただし図 39C のイースト菌ネットワークでは、追加リンク数が 500 本以下の範囲はLongAdd(緑点線) が最も RHDA を向上している。また図では読み取れないが航空網とメールやりとりネットワークにおいても、100 本以下の非常に少ない追加リンク数であれば LongAdd が最も RHDA を改善していた。つまり、実際のネットワークであっても非常

67

図 39

リンク追加法による次数順攻撃に対する頑健性指標。(A) AirTraffic、(B)

Email (C) Yeast での結果。横軸は追加リンク数を示す。

に極端に追加できるリンクが限られる場合では、最長距離戦略が有効になりうることが分かった。

次に図 40 に各ネットワークデータでのリンク追加法による BP 攻撃による頑健性指標

RBP の変化を示す。BP 攻撃に対する頑健性でも、次数順攻撃とほとんど同様の傾向が見られている。図 40ABC の全てで min-k RandAdd と min-k LongAdd が最も RBP を向上している。また、追加リンク数が増えるほど min-k ShortAdd が大幅に RBP を向上している。これらの結果から、実際のネットワークデータの BP 攻撃への頑健性の向上においても最小次数戦略がより効果的であることが分かる。

図 40

リンク追加法による BP 攻撃に対する頑健性指標。(A) AirTraffic、(B) Email(C) Yeast での結果。横軸は追加リンク数を示す。

68

図 41 にネットワークデータでのリンク追加による最小サイズの変化を示す。実際のネットワークデータにおいても min-k ShortAdd が最も最小サイズを増加させていた。
ただし、扱っているデータはループがあるネットワークのため、末端に局所的なループを形成しているのではないと考えられる。このような場合、最小サイズが頑健性にどのような影響を与えるのかはよく分かっていない。図 40AB や図 41AB では追加リンク数が非常に多くなった場合に、

min-k ShortAdd が若干ではあるものの頑健性を最も向上している。このように非常に平均次数が高くなった場合に最小サイズを増加させたことが頑健性の向上に影響を与える可能性はあるが、明確な関係性はよく分かっていない。ただ、得られた結果として実際のネットワークデータでは min-k ShortAdd が頑健性と最小サイズの両方を非常によく向上していることが分かった。

図 41

リンク追加法による最小 FVS サイズの変化。(A) AirTraffic、(B) Email (C)Yeast での結果。横軸は追加リンク数を示す。

表 8 に実際のネットワークデータに対して最も頑健性もしくは最小サイズを向上した手法をまとめる。航空網とメールやりとりネットワークでは、次数順攻撃と BP 攻撃の両方に対して min-k RandAdd と min-k LongAdd、min-k ShortAdd が最も頑健性を向上していた。一方で、イースト菌ネットワークでは、min-k RandAdd と min-k LongAdd
が最も頑健性を向上していた。最小サイズでは、全てのネットワークにおいて min-k

ShortAdd が最も増加させていた。

69

表8

実際のネットワークデータにおける RHDA 、RBP 、最小サイズを最も向上したリ

ンク追加法の一覧。

RHDA

RBP

|FVS|

Fig. 39

Fig. 40

Fig. 41

AirTraffic

Email

Yeast

min-k RandAdd

min-k RandAdd

min-k RandAdd

min-k LongAdd

min-k LongAdd

min-k LongAdd

min-k ShortAdd

min-k ShortAdd

min-k RandAdd

min-k RandAdd

min-k RandAdd

min-k LongAdd

min-k LongAdd

min-k LongAdd

min-k ShortAdd

min-k ShortAdd

min-k ShortAdd

min-k ShortAdd

min-k ShortAdd

次に、実際のネットワークデータに対してリンク追加法が直径 D とネットワーク効

率 E に与える影響を調査する。図 42 にリンク追加法による直径 D の変化を示す。図42ABC の全てにおいて LongAdd が最も直径 D を減少させている。また、頑健性をよく向上する三手法の中でも min-k RandAdd と min-k LongAdd は LongAdd に近い程度にまで直径 D を減らしていた。さらに、図 31 と 32 のループの無いネットワークでは直径をあまり減らしていなかった min-k ShortAdd が、図 42AB では直径 D を RandAdd 程度まで減少させている。一方で、図 42C では min-k ShortAdd は ShortAdd と同じぐらいになっており直径 D をあまり減らしていない。これらの結果から、実際のネットワー

クデータであれば最小次数戦略をすることで短距離のリンク追加であっても直径 D が減少する可能性があることが分かった。

図 43 にリンク追加法による実際のネットワークデータのネットワーク効率 E の変化を示す。図 43ABC の全てにおいて RandAdd が最もネットワーク効率 E を向上していることが分かる。図 43AB の航空網とメールやりとりネットワークでは、頑健性を良く向上する min-k RandAdd と min-k LongAdd は RandAdd と同程度にまでネットワーク効
率 E を向上していた。ただし、図 43C のイースト菌ネットワークでは、min-k RandAddと min-k LongAdd は ShortAdd よりも低い値になっており、ネットワーク効率 E の向上に強い効果はなかった。一方で、min-k ShortAdd はネットワーク効率 E の向上への寄与が非常に小さいことが分かる。図 43ABC のどのネットワークにおいても min-k

ShortAdd はネットワーク効率 E の向上が最も小さかった。

70

図 42

リンク追加法による直径 D の変化。(A) AirTraffic、(B) Email (C) Yeast で

図 43

リンク追加法によるネットワーク効率 E の変化。(A) AirTraffic、(B) Emailの結果。横軸は追加リンク数を示す。

(C) Yeast での結果。横軸は追加リンク数を示す。

表 9 に直径 D とネットワーク効率 E を最も向上したリンク追加法をまとめる。直径 D

では LongAdd が最も効果的に減少させていた。ネットワーク効率 E では RandAdd が最も向上していた。頑健性を効率的に向上する最小次数による三手法では min-k RandAddと min-k LongAdd は直径 D とネットワーク効率 E の両方を向上させていた。しかしながら、min-k ShortAdd は直径 D は減少はさせていたものの min-k RandAdd と min-k

LongAdd ほどではなく、またネットワーク効率 E の向上も小さかった。このことから直径 D やネットワーク効率 E を考慮しながら頑健性の向上をする際には min-k RandAdd
や min-k LongAdd が活用できると考えられれる。

71

表9

実際のネットワークデータで直径 D とネットワーク効率 E を最も向上したリンク追加法

AirTraffic

Email

Yeast

D

Figs 42LongAdd

LongAdd

LongAdd

E

Figs 43

RandAdd

RandAdd

RandAdd

4.8 まとめ

本章では、攻撃に対する頑健性を効率的に向上するリンク追加法を明らかにするために、先行研究で特に有効とされていた最小次数戦略と最長距離戦略のそれぞれの効果を調査した。そこで、次数と距離による選択の効果をできるだけ区別するために、次数と距離の二段階によるリンク追加法の枠組みを提案する。提案した枠組みでは一段階目で次数、二段階目で距離によって追加リンク先を選択する。一段階目では全ノードと最小次数ノード集合を選択する二種類を考えて、二段階目では最短距離、ランダム、最長距離の三種類で選択する。この枠組みに従うと、それぞれの組合せによって計六種類のリンク追加法を作ることができる。これらのリンク追加法をネットワークに適用して頑健性向上の比較をすることで、次数と距離の効果を調べた。

最小次数戦略と最長距離戦略は、ループの無いネットワークでは類似した葉ノードを選択することが考えらえる。また、次数分布は頑健性向上に強く影響するため、いくつかの次数分布を持ったネットワークで比較を行う。そこで Growing Network モデルと逆優先的選択モデルによって生成した、べき乗分布、指数分布、さらに狭い分布に従う次数分布を持つループの無いネットワークを用いた。これらのループの無いネットワークでは、

min-k RandAdd と min-k LongAdd の二手法が最も頑健性を向上していた。これらの結果から、頑健性を向上するためには最小次数戦略が特に効果的であることが分かった。ただし、最小次数を選択する手法であっても短距離のリンクを追加する min-k ShortAdd では頑健性の向上が小さくなっている。また例外的に、追加リンク数が極端に少ない場合には LongAdd が最も頑健性を向上していた。よって、追加リンク数が少ない場合では最長距離戦略が効果的であることも明らかになった。さらに、ループのあるスケールフリーなネットワークで比較して、ノード数と平均次数の影響を調べた。得られた結果から、ノー
ド数はほとんどリンク追加による頑健性の向上に影響しないことが分かった。一方で、平
均次数は大きくなるほど、最小次数戦略がより頑健性を向上することが分かった。特にmin-k ShortAdd は平均次数が大きくなるほど、より頑健性を向上するように変化するという結果が得られた。また、実際のネットワークデータにおいても、最小次数戦略による72

三手法は、非常に頑健性を向上していた。これらの結果から、多くの場合で最小次数戦略
がより頑健性の向上に効果的であることが分かる。

また、リンク追加法による頑健性と最小サイズの関係性を調べた。今回比較した全てのネットワークで min-k ShortAdd が最も最小サイズを増加していた。一方で、ループの無いネットワークでは min-k ShortAdd はあまり頑健性を向上しておらず、最小サイズと頑健性が必ずしも相関関係にないことが明らかになった。特にループの無いネットワー
クでは min-k ShortAdd は局所的なループを形成することによって、最小サイズは増加
するが頑健性は向上しないと考えられる。

頑健性とは異なるネットワーク指標として、ネットワーク効率と直径のリンク追加

法による変化も調査した。すると、頑健性を効率的に向上するリンク追加法の min-k

RandAdd と min-k LongAdd は効率と直径の両方をランダムリンク追加法と同じぐらいまで向上することが分かった。一方で最小次数戦略であっても min-k ShortAdd は効率と直径の向上が小さくなっており、これは最小サイズと同様に局所的なループが最短経路を小さくしないからと考えられる。このため効率性や直径を考慮しながら頑健性を向上する場合は、最小次数戦略であっても min-k RandAdd や min-k LongAdd がより効果的であることが明らかになった。

73

5 変化する次数分布における頑健なネットワーク構造
5.1 次数分布の均質さと攻撃に対する頑健性

ここまでループを強化することで攻撃に対する頑健性を向上する手法を提案してきた。

特に、ループの強化によって次数分布が均質に変化することで、頑健性が大幅に向上することが分かっている。2.4.3 章で述べたように、仲介によってループが強化されることで生成された玉ねぎ状ネットワークは、裾野の広いべき分布ではなく、より狭い指数の裾野を持つ次数分布を持っていた。また、3 章の次数変化するループ強化リワイヤリングでは、次数分布が平均次数に集中するような狭い分布に変化することで、攻撃に対する頑健性と最小 FVS サイズの両方が大幅に向上したことが明らかになっている。さらに 4 章のリンク追加法においても、最小次数戦略によって次数分布の分散が減少して均質化することで、攻撃に対する頑健性を向上していた。これらの結果から、本章ではループの強化を基にして、次数分布の均質さと攻撃への頑健性の関係に着目する。

ループの強化による攻撃に対する頑健性の大幅に向上では、次数分布が均質になるという共通点があった。これらの結果から、次数分布が均質なほど、攻撃に対して頑健である
ことが予想される。特に、次数分布の分散が最小である、全てのノードが同次数を持っているレギュラーグラフが最も頑健なのではないかと示唆されている。

ところが、これまでの研究では、ピンポイントな次数分布での頑健性のみのが比較されてきた。例えば、べき乗の次数分布を持つスケールフリーネットワークは、指数の次数分布を持つ Erdős-Rényi ランダムグラフ [15] よりも攻撃に対して連結性が脆弱であることが分かっている [2]。一方で、ランダムな故障に対してはスケールフリーネットワークの方が Erdős-Rényi ランダムグラフよりも頑健である。また m 種類の次数をもつ次数分布を考えたマルチモーダルネットワーク群での故障と攻撃の両方に対する頑健性が調査されている。ここで故障と攻撃に対するパーコレーションしきい値の和を最大化することを考えた場合、二種類の次数のみを持つバイモーダルネットワークが最も高い頑健性を持つことが示されている [67]。さらに Ma et al.,(2015) ではレギュラーグラフと Erdős-Rényi

ランダムグラフ [15]、Watts-Strogatz モデル [16]、Barabási Albert モデル [56] の次数

順攻撃に対する頑健性を比較している。これらのネットワークの中では、最も次数分布が均質なレギュラーグラフが最も頑健であることが数値的に示されている。さらに次数順攻撃に対する頑健性をヒューリスティックに最大化するリワイヤリングによって、次数分布がより狭い分布に変化することが分かっている [68]。ただし、得られた次数分布は数種類

74

の次数を持ったものになっており、完全なレギュラーグラフまでにはなっていなかった。
これらの先行研究からも次数分布が狭く均質な分布であるほど、攻撃に対する頑健性が向上する傾向があると考えられ、さらに最も均質な次数分布を持つレギュラーグラフが最も高い攻撃に対する頑健性を持つのでは無いかと予想することができる。しかしながら、
上記のような個別の次数分布では頑健性が調査されているが、次数分布が連続的に変化するような場合にどのような変化をするのかは分かっていない。また、頑健性を最大化する
リワイヤリングでも完全なレギュラーグラフになっていないことから、レギュラーグラフ
周辺でどのような頑健性になっているかはよく分かっていない。

そこで本章では、次数分布の均質さと攻撃に対する頑健性の関係性について明らかにすることを目的とする。まず、連続的に変化する次数分布において頑健性がどのように変化するのかを数値的に調査する。Growing Network モデルと逆優先的選択によって、べき乗から指数、さらに狭い次数分布を持つネットワークを生成して、それらのネットワーク
での頑健性指標を調べる。得られた結果から、コンフィギュレーションモデルによってランダム化した場合には、次数分布の分散が小さくなるほど頑健になることを示す。また、
さらに非常に高い頑健性を持つことが予想されるレギュラーグラフと、その周辺の摂動グ
ラフで頑健性指標を調べる。結果として、摂動としての周辺ではレギュラーグラフが最も高い頑健性を持っていることを示す。これらの結果から次数分布が均質なほど攻撃に対して頑健であることを明らかにして、さらにレギュラーグラフが最も最適な頑健性をもつ可能性が高いことを示す。

5.2 連続的に変化する次数分布を持つネットワークの生成法

まず連続的に変化する次数分布で攻撃に対する頑健性がどのような変化するのかを明らかにするために Growing Network モデル [57–59] と逆優先的選択 [60] を用いる。4.4

章で説明したように、これらは Barabási Albert モデル [56] を拡張した手法で、それぞれ接続確率を pi ∝ kiν (ν ≥ 0)、pi ∝ ki (β ≥ 0) としたものであった。4 章では m = 1−βのループの無いネットワークを考えたが、本章では m = 2、3、4 としたものを用いる。

Growing Network モデルにおける次数分布の変化は m = 1 で解析されているが、図 23のように m ≥ 2 にした場合でも同様に成り立っている。

これらの二手法を組合わせることで、図 23 のようにべき乗からカットオフ付きべき乗、指数、さらに狭い次数分布へと連続的に変化させながらネットワークを生成することができる。図 44 にそれぞれのモデルで生成したネットワークの次数分布の分散が、パラメータでどのように変化するのかを示す。図 44a から Growing Network モデルでは ν が75

図 44 (a) Growing Network モデルと (b) 逆優先的選択モデルによって生成された

次数分布の分散。10000 ノードのネットワークでの結果を示す。黒線、紫線、黄線はそ
れぞれ m = 2、3、4 を示す。ν が小さくなるほど分散は減少して、β が大きくなるほ
ど分散が減少している。横軸はそれぞれのパラメータ ν 、β を示す。

小さくなるほど、分散が小さくなっていることが分かる。一方で図 44b から逆優先的選択モデルでは β が大きくなるほど、分散が小さくなっていることが分かる。しかしながら、分散はゼロにはなっておらず一定値からは減少していない。m = 2、3、4 の逆優先的選択モデルでは分散の最小値はそれぞれ 0.0048、0.002、0.0034 となっている。これはβ → ∞ でも逆優先的選択モデルでは分散ゼロの完全グラフにはならないことを意味している。β → ∞ では新規ノードは必ず最小次数ノードに接続することになるが、このような場合は大半のノードは次数 2m を持つことになる。ただし、全てのノードが次数 2m を持つことは無く、必ず次数 2m 以下のノードが存在することになるため完全グラフにはな
らない [60]。

図 44a から Growing Network モデルでは m が大きいほど分散が大きくなっている。

一方で図 44b から逆優先的選択モデルでは β = 70 までは m が大きいほど分散が大きくなっているが、それよりも β が大きい場合には順序が入れ替わっている。この理由はよく分かっていないが、縦軸が対数であることに注意するとその差は 10−3 程度と非常に小さいものとなっている。また、Growing Network モデルと逆優先的選択モデルでは ν = 0と β = 0 で接続確率が同じになるため、各 m について図 44ab の ν = 0 と β = 0 は同値

76になっている。

大きい β の逆優先的選択モデルによって生成されたネットワークは、図 45a のような鎖状構造を持つ [60]。ただし、本章では次数分布の変化が頑健性に与える効果について議論したいため、このような生成過程による構造は除去する。そこで 4.4 章で述べたコン
フィギュレーションモデル [61, 62] を用いてランダム化することで、このような構造を除去する。図 45b にコンフィギュレーションモデルを適用した後のネットワークを可視化する。図から明らかに鎖状構造がなくなったことが分かる。

図 45

逆優先的選択モデルによって生成されたネットワークの可視化。 (a) N = 200

ノードと m = 4、β = 200 の逆優先的選択モデルによる鎖状構造のネットワーク、(b)コンフィギュレーションモデルによってランダム化されたネットワーク。

逆優先的選択モデルで鎖状構造が現れることは、β → ∞ で新規ノードが最小次数ノードに追加することになることから考えられる [60]。この時、ある時刻 t に追加された新規ノードは、それ以前の時刻 t − 1, t − 2, ..., t − (m − 1) に追加されたノードにリンクを接続することになる。なぜなら、新規ノードは各ノードに対して最大で一本のリンクを接続するため、時刻 t で追加されたノードは時刻 t + δt では最大で次数 m + δt にしかなることができない。そのため時刻 t では、時刻 t − 1、t − 2、...、t − (m − 1) で追加されたノードは、最大でも次数 m、m − 1、...、2m − 2 しか持つことができない。これによって、追加された時系列が近いノード同士が接続されることになり、図 45a のように連なった鎖状構造が形成される。

77

5.3 連続的に変化する次数分布における攻撃に対する頑健性指標

Growing Network モデルと逆優先的選択モデルで生成されたネットワークにおける次数順攻撃による頑健性指標 Rhub と BP 攻撃による頑健性指標 RBP 、最小 FVS サイズを比較する。まず最初にコンフィギュレーションモデルによってランダム化した後のネットワークでの結果を示して次数分布の変化と頑健性の関係性を述べる。以下、全ての結果は100 平均した値を示す。

表 10 は Growing Network モデルで生成したネットワークをコンフィギュレーション

モデルでランダム化した後の Rhub と RBP の値を示す。m = 2、3、4 と ν = 0、0.5、1 のGrowing Network モデルで生成した N = 10000 ノードのネットワークを使用している。
表 10

N = 10000 の Growing Network モデルで生成したネットワークをコンフィ

ギュレーションモデルに適用した後の頑健性指標。

Rhub

RBP

m

ν=0

0.5

1

ν=0

0.5

1

2

0.17090.14390.09887

0.16140.13540.0921330.25640.2316

0.18950.24750.22340.180440.30780.28660.25160.30000.27870.2424

表 10 から ν が小さくなるほど Rhub と RBP の両方が大きくなっている。図 44 から νが小さくなるほど分散が小さくなっていたことを思い出すと、Growing Network モデル
では次数分布の分散が小さくなるほど頑健性が向上することが分かる。

表 10 において ν が同じ場合には m が大きいほど Rhub と RBP がそれぞれ大きくなっている。つまり平均次数が大きいほど、どちらの攻撃に対しても頑健となっている。また同じ m と ν で Rhub と RBP の値を比較すると RBP の方が少しだけ小さい値になっている。このことは次数順攻撃よりも BP 攻撃の方がより激しい攻撃であることを示している。

次に図 46 に逆優先的選択モデルで生成したネットワークにコンフィギュレーションモ

デルでランダム化した後の次数分布の分散に対する Rhub と RBP を示す。ネットワーク

はパラメータ β = 0, 10, ..., 200 として生成している。図 46ab では、分散が小さくなるほ
ど Rhub と RBP は増加していることが分かる。これらの結果から、逆優先的選択モデル

78

図 46

次数分布の分散に対する (a) 次数順攻撃と (b)BP 攻撃に対する頑健性指標。逆

優先的選択モデルで生成したネットワークをコンフィギュレーションモデルに適用したものの結果を示す。赤、緑、青線として N = 100、1000、10000 ノードでの結果を示す。ネットワークは m = 3 とパラメータ β = 0, 10, ..., 200 で生成している。

で生成される次数分布においても、分散が小さくなるほど頑健性が向上することが分かった。ただし図 46ab の青線 (N = 10000) では、分散が 10−2 以下ではほとんど頑健性は変化しておらず収束しているようになっている。つまり、分散があまりに小さくなった場合には頑健性指標に明確な差が見られないので、この結果からではレギュラーグラフなどのより均質なネットワークについては分からない。

これらの結果をまとめると、Growing Network モデルと逆優先的選択モデルによって生成される次数分布の範囲では、次数分布の分散が小さくなるほど攻撃に対してより頑健になることが分かった。

79

図 47 Growing Network モデルで生成したネットワークにコンフィギュレーション
モデルを適用した後の最小 FVS 割合に対する頑健性指標。黒丸、紫星、橙六角はそれぞれ m = 2、3、4 での結果を示す。また各点の色の濃度は次数分布の分散の値に対応しており、濃いほど分散が小さいことを示す。ネットワークは N = 1000 ノードと

ν = 0, 0.1, ..., 1 で生成している。

表 11 Growing Network モデルと逆優先的選択モデルで生成されたネットワークにコンフィギュレーションモデルを適用した後の頑健性指標と最小 FVS 割合の相関係数。ネットワークは N = 1000 ノードと ν = 0, 0.1, ..., 1 もしくは β = 0, 10, ..., 200で生成している。

m

Growing Network モデル
Corr(Rhub , FVS)

Corr(RBP , FVS)

2

0.99993
4

逆優先的選択モデル

Corr(Rhub , FVS)

Corr(RBP , FVS)

0.9986

0.99870.99880.99990.99970.99970.99900.99990.99940.99970.998880

次に、これらの次数分布の範囲で頑健性指標と最小 FVS サイズの相関関係について調べる。図 47 に Growing Network モデルで生成したネットワークにコンフィギュレー

ションモデルを適用した時の、最小 FVS に含まれるノード割合と Rhub もしくは RBP の相関関係を示す。各 m において最小 FVS 割合と頑健性指標が直線的に並んでいることがわかり、非常に強い相関関係があることが分かる。表 11 にこれらの相関係数を示す。
どの m に対しても最小 FVS 割合と頑健性指標の相関係数が 0.99 以上となっていることが分かる。また、図 11 では各点の色の濃淡が次数分布の分散に対応しており、色が濃いほど次数分布の分散が小さいことを示している。すると、各 m において最小 FVS サイ
ズと頑健性指標が大きいほど、次数分布の分散が小さくなっている。これらの結果から

Growing Network モデルで生成される次数分布では、分散が小さいほど最小 FVS サイズと頑健性指標の両方が向上されることが明らかになった。

図 48

逆優先的選択モデルで生成したネットワークにコンフィギュレーションモデ

ルを適用した後の最小 FVS 割合に対する頑健性指標。黒丸、紫星、橙六角はそれぞれ m = 2、3、4 での結果を示す。また各点の色の濃度は次数分布の分散の値に対応しており、濃いほど分散が小さいことを示す。ネットワークは N = 1000 ノードとβ = 0, 10, ..., 200 で生成している。

81

図 48 に逆優先的選択モデルで生成したネットワークにコンフィギュレーションモデル

を適用した時の、最小 FVS 割合と頑健性指標を示す。この場合でも同様に、各 m において最小 FVS 割合と頑健性指標は直線的に並んでいることがわかる。また表 10 から逆優

先的選択モデルの場合でも相関係数は非常に高い。さらに各点の濃淡が示すように、逆優
先的選択モデルで生成される次数分布でも、分散が小さくなるほど最小 FVS サイズと頑健性指標の両方が向上していることが分かる。

これらの結果をまとめると、Growing Network モデルと逆優先的選択モデルで生成される連続的な次数分布の範囲では、分散が小さくなるほど頑健性指標と最小 FVS サイズの両方が向上することが分かった。さらに、この範囲では頑健性と最小 FVS サイズが相関係数 0.99 以上と非常に強い相関関係にあることが数値的に示された。

5.3.1

連続変化する次数分布における Localized Attacks に対する頑健性指標

ここまでは、典型的な次数順攻撃と現状最も強力な BP 攻撃に対する頑健性について調査した。さらに、地震や津波をモデルとした範囲攻撃である Localized Attacks (LA) [32]に対する頑健性指標 RLA について調査する。2.4.5 章で述べたように、次数順攻撃と BP

攻撃は弱点を狙った標的型のノード除去法であるが、LA は一つのノードを中心とした範囲によるノード除去であり、異なる種類の攻撃であることを強調しておく。

GN モデルと逆優先的選択モデルで生成したネットワークにコンフィギュレーションモ

デルを適用した時の、最小 FVS 割合と LA に対する頑健性指標 RLA を図 49 に示す。次
数順攻撃や BP 攻撃での結果と同様に、どちらの図においても最小 FVS 割合が大きくなるほど、頑健性指標 RLA も大きくなっている。また、各点の濃淡から、次数分布の分散が小さくなるほど、最小 FVS 割合と頑健性指標 RLA が向上している。これらの結果から、LA に対する頑健性においても、次数順攻撃や BP 攻撃と同様の傾向があることが分かった。

一方で、次数順攻撃や BP 攻撃と比べると、RLA の値は GN モデルで 0.35 以上、逆優

先的選択モデルで 0.4 以上と非常に大きな値となっている。このことからも LA は比較的緩やかな攻撃方法であることが分かる。また、図 49 では m が大きくなるほど、傾きがな
だらかになっている。これは、平均次数が大きいネットワークは、そもそも LA に対して高い頑健性を持っているため、最小 FVS 割合の変化による効果が相対的に小さくなっているのではないかと考えられる。

これらの結果から、標的型攻撃ではない範囲型攻撃に対しても、次数分布の分散が小さくなることで、最小 FVS 割合が増加し、頑健性が向上することが明らかになった。

82

図 49 Growing Network モデルと逆優先的選択モデルで生成したネットワークにコンフィギュレーションモデルを適用した後の最小 FVS 割合と LA に対する頑健性指標。黒丸、紫星、橙六角はそれぞれ m = 2、3、4 での結果を示す。また各点の色の濃度は次数分布の分散の値に対応しており、濃いほど分散が小さいことを示す。ネット
ワークは N = 1000 ノードで (a) GN モデルは ν = 0, 0.1, ..., 1、(b) 逆優先的選択モ
デルは β = 0, 10, ..., 200 で生成している。

83

5.3.2

逆優先的選択モデルによる鎖状構造が頑健性に与える影響

最後にコンフィギュレーションモデルの適用の有無で、頑健性がどのように変化するのかを確かめる。コンフィギュレーションモデルは、特に逆優先的選択モデルで現れるような特殊な鎖状構造を除去するために適用していた。そこで図 50ABC に、逆優先的選択モ
デルで生成されたネットワークにコンフィギュレーションモデルを適用する前後の Rhubを示す。図 50 では点線が適用前、実線が適用後の結果を示している。まず適用後の結果(実線) では、これまでの議論と同様に β が大きくなるほど Rhub が向上していることが分かる。

図 50 のコンフィギュレーションモデルを適用する前のネットワークでは β に対してRhub は上下に変化している。代表例として、図 50A の m = 2 の N = 10000 ノード (青点線) では β = 25 で Rhub = 0.29 まで向上した後に、β = 60 で Rhub = 0.15 まで減少している、その後若干増加して β = 130 以上では Rhub = 0.24 となっている。図 50B のm = 3 でも同様の上下の変化が見られる。また、ノード数が増えるほど Rhub の極小点となる β が大きい値になっていることが分かる。N = 100、1000、10000 ノードに対して

m = 2 では β = 20、45、55 で極小となっている。また、m = 3 では β = 35、60、85 が極小点となっている。一方で、図 50C の m = 4 では最後の増加が見られない。このような頑健性の変化が起こる理由はよく分かっていない。β が大きくなるにつれて、次数分布は均質に変化していき、かつ同時に鎖状構造が形成されていく。この次数分布が均質化することは頑健性を向上するような効果があるが、鎖状構造の形成は逆に頑健性を低下させるような働きをする。特に、鎖状構造はノードの除去により分断されやすい構造となっている。そのため β が大きくなり、頑健性の変化に相反する効果が同時に進んだことで、上下の変化ができたのではないかと考えられる。β が十分大きくなると、次数分布が変わらないようになり、また鎖状構造の形成も完了するため、頑健性の変化がなくなっている。
図 50ABC のどの点線においても、β ≥ 130 では頑健性指標はほとんど変化していない。

84

図 50

逆優先的選択モデルによって生成されたネットワークでの次数順攻撃に対する頑健性指標の変化。 赤、緑、青線はそれぞれ N = 100、1000、10000 ノードでの結果を示す。点線と実線はそれぞれコンフィギュレーションモデルを適用する前後の結果を示す。各図は (a)m = 2、(b)m = 3、(c) m = 4 となっている。

85

5.4 ランダムレギュラーグラフとその摂動ネットワーク

Growing Network モデルや逆優先的選択モデルで生成される、べき乗からカットオフ

付きべき乗、指数、さらに狭い分布までの連続的な次数分布の範囲では、次数分布の分散が小さくなって均質になるほど攻撃に対する頑健性が向上することが明らかになった。一方で、逆優先的選択モデルで β → ∞ という極限を取ったとしても、最も均質なネットワークであるランダムレギュラーグラフを生成することはできない。次数分布が均質なほ
ど頑健であることから、ランダムレギュラーグラフは攻撃に対して最適な頑健性を持つことが期待される。そこでランダムレギュラーグラフとその周辺の摂動ネットワークの頑健性指標を比較することで、より均質なネットワークでの次数分布と頑健性の関係を明らかにする。

ランダムレギュラーグラフは全てのノードが同じ次数 d を持っているネットワークであり、その次数分布は次のようになる。

P (k) = δk,d =(10(k = d).
otherwise(22)

ここで δk,d はクロネッカーのデルタと呼ばれる関数である。この時、次数分布の分散は 0であることから、ランダムレギュラーグラフが最も均質なネットワークとなっている。さて、次数分布の分散が小さいほど攻撃に対して頑健となることから、このランダムレギュ
ラーグラフが最適な頑健性を持つことが示唆されている。そこでランダムレギュラーグラ
フとその摂動ネットワークを考えることで、次数分布の分散が最小の周辺での頑健性について明らかにする。摂動ネットワークとして、離散的摂動とランダム摂動の二種類を考える。まず最初に離散的摂動として、二種類の次数のみを持つバイモーダルネットワークについて説明する。ここではランダムレギュラーグラフが一種類の次数のみであったのに対して、バイモーダルネットワークは二種類の次数を持つことから、離散的摂動とみなす。
次にランダム摂動として、ランダムレギュラーグラフに対して、一様ランダムなリンクの削除と追加をするもの説明する。これらの二種類の摂動ネットワークとランダムレギュ

ラーグラフでの頑健性指標を比較することで、ランダムレギュラーグラフが最も高い頑健性を持つことを数値的に示す。

86

5.4.1

ランダムレギュラーグラフに対する離散的摂動

ランダムレギュラーグラフの離散的摂動として、二種類の次数 d1 < d2 で構成された平均次数 d のバイモーダルネットワークを考える。平均次数 d が一定だとしても、d1 と d2の組合せは複数考えることができる。ただし、ランダムレギュラーグラフと比較するために平均次数 d は整数値と仮定しているため、∆d = d2 − d1 ≥ 2 は満たす必要がある。

平均次数 d とノード数 N 、リンク数 M が与えられた時、バイモーダルネットワークのそれぞれの次数 d1 < d2 に対応するノード数 N1 と N2 は以下のように導出できる。ノード数とリンク数から、

N = N1 + N2 ,M=であるため、(23)

d×N
d1 × N1d 2 × N2
=
+
,
2
2
2

(24)

N1 =

d2 − d
N,
∆d

(25)

N2 =

d − d1N.
∆d(26)となる。ここで N1 と N2 は正の整数である必要があるので、N は ∆d で割り切れる必要がある。表 12 と表 13 で示す通り、次数組合せは (d1 , d2 ) = (d − 1, d + ∆d − 1), (d −2, d + ∆d − 2), ..., (d − ∆d + 1, d + 1) となる。ただし、d1 = 1 で d2 = N − 1 の星形ネッ
トワークは明らかに攻撃に対して脆弱であるため、ここでは省略する。
表 12

平均次数 d = 4 のバイモーダルネットワークの次数 d1 と d2 、次数分布の分散

σ 、次数 d1 のノード割合 N1 /N の一覧。
2

∆d

d1

d2

σ2

N1 /N

2

3

5

1

1/2

3

3

5

2

2/3

2

6

2

1/3

3

7

3

3/4

2
..
.

6

4
..
.

2/4

d−1=3

∆d + d − 1∆d − 1(∆d − 1)/∆d

4

∆d

d−2=2

∆d + d − 2872(∆d − 2)(∆d − 2)/∆d表 13

平均次数 d = 6 のバイモーダルネットワークの次数 d1 と d2 、次数分布の分散

σ 、次数 d1 のノード割合 N1 /N の一覧。
2

∆d

d1

d2

σ2

N1 /N

2

5

7

1

1/2

3

5

8

2

2/3

4

7

2

1/3

5

9

3

3/4

4

8

4

2/4

3

7

3

1/4

5

10

4

4/5

4

9

6

3/5

3

8

6

2/5

2
..
.

7

4
..
.

1/5

d−1=5

d + ∆d − 1∆d − 1(∆d − 1)/∆dd−3=3d + ∆d − 3

4

5

∆d

d−2=4
d−4=2

d + ∆d − 22(∆d − 2)(∆d − 2)/∆dd + ∆d − 44(∆d − 4)(∆d − 4)/∆d

3(∆d − 3)(∆d − 3)/∆d

表 12 と表 13 では、一定のノード数 N と平均次数 d = 4 と 6 において 2 ≤ d1 ≤ d − 1と d + 1 ≤ d2 ≤ N − 2 の範囲で実現可能な全ての次数組合せを示している。特に、ランダ
ムレギュラーグラフ周辺の全ての次数組合せを示している。またバイモーダルネットワー
クの生成には、次の次数分布に従ったコンフィギュレーションモデルを使用している。

P (d1 ) =

N1
,
N

(27)

P (d2 ) =

N2
.
N

(28)

コンフィギュレーションモデルを使用しているため、生成されたバイモーダルネットワー
クはランダムなものになっており、純粋な次数分布の影響のみを議論することができる。
さらにバイモーダルネットワークでは、次数分布の分散が簡単に計算することができ88る。式 25 と式 26 から次数分布の分散 σ 2 は以下のように導出できる。

σ 2 = #k 2 $ − #k$2
1
= (d21 × N1 + d22 × N2 ) − d2
N)*1
2 d2 − d2 d − d1=
d1
N + d2N − d2N∆d∆dd21 (d2 − d) + d22 (d − d1 )=− d2
d2 − d1= (d2 − d)(d − d1 ).

(29)

ここで次数 d1 もしくは d2 が平均次数 d に近いほど分散 σ 2 は小さくなる。さらに、バイモーダルネットワークで分散が最小なのは d1 = d − 1 と d2 = d + 1 の σ 2 = 1 であることが分かる。また ∆d = d2 − d1 を式 29 に代入すると、

σ 2 = (d2 − d)(d − d1 )= (d1 + ∆d − d)(d − d1 )= (d − d1 )∆d − (d − d1 )2 ,(30)となる。図 51 と図 52 に分散 σ 2 と次数の差 ∆d の関係を示す。図より d1 を固定すると分散 σ 2 と次数の差 ∆d が比例関係にあることが分かる。また、式 30 から次数 d1 が小さ
いほど σ 2 が大きくなる。図 51 や図 52 においても d1 = 2(緑線) や d1 = 3(赤線) でより

分散 σ 2 が大きくなっている。ただし、式 25 と式 26 から ∆d は N で割り切れる必要が
ある。

5.4.2

ランダムレギュラーグラフに対するランダム摂動

ランダムレギュラーグラフに対するランダム摂動として、一様ランダムにリンクの追加と削除をすることを考える。まず既存リンクを除去する割合を 0 ≤ p ≤ 1 として、一様ランダムに pM 本の既存リンクの削除をする。その後、除去した本数と同じだけ一様ラン

ダムに新規ノードを追加する。このようにすることで、平均次数 d を保ちながら次数分布を変化させることができる。p = 0 では次数分布は P (k) = δk,d のままとなり、p = 1 では全リンクを除去した後で一様ランダムにリンク追加するため Erdős-Rényi ランダムグ

ラ [15] となり、次数分布はポアソン分布となる。0 < p < 1 の範囲では、次数分布は次のようになる。

P (k) =!

k1 +k2 =k) *dλk2 −λe .
(1 − p)k1 pd−k1
k1
k2 !
89

(31)

d=4
175
150
125

2

100
75
50
25
0
0

20

40

60

80

d

図 51

N = 1260 ノードと平均次数 d = 4 のバイモーダルネットワークでの次数の差∆d と次数分布の分散 σ 2 の関係性。緑線と赤線は、それぞれ d1 = 2 と 3 の結果を示す。式 30 から次数の差と分散は比例関係にあるため、各線は一直線となっている。

d=6
350
300
250

2

200
150
100
50
0
0

20

40

60

80

d

図 52

N = 1260 ノードと平均次数 d = 6 のバイモーダルネットワークでの次数の差∆d と次数分布の分散 σ 2 の関係性。緑、赤、紫、茶線は、それぞれ d1 = 2、3、4、5の結果を示す。式 30 から次数の差と分散は比例関係にあるため、各線は一直線となっ
ている。

90

ここで k1 と k2 はあるノードにおいて除去されなかったリンク数と追加されたリンク数、

λ = 2dp である。図 53 と図 54 に平均次数 d = 4 と 6 のランダムレギュラーグラフにランダム摂動を適用した後の次数分布を示す。p が増加するほど、極端に均質な次数分布か

ら広い次数分布へと変化していることが分かる。確率が p = 0.005 や 0.01 と非常に小さ
くても、次数分布は五種類程度の次数を持った分布になっている。

図 53

N = 10000 ノードと平均次数 d = 4 のランダムレギュラーグラフにランダム摂動を適用した後の次数分布。次数分布は p = 0 で次数 4 のみとなっており、p = 1 ではポアソン分布になっている。

図 54

N = 10000 ノードと平均次数 d = 6 のランダムレギュラーグラフにランダム摂動を適用した後の次数分布。次数分布は p = 0 で次数 6 のみとなっており、p = 1 ではポアソン分布になっている。

91

5.5 頑健性指標とパーコレーションしきい値

本章では頑健性の比較のために、次数順攻撃による頑健性指標 RTA [4] と攻撃に対する

パーコレーションしきい値 fc [3, 69] で比較を行う。なお、ここでは次数順攻撃として次数の再計算をしない攻撃を考えることにする。

パーコレーションしきい値 fc は攻撃によってネットワークの連結性が無くなった時に除去されずに残っているノードの割合である。攻撃によって fc より多く除去された場合、

N → ∞ でネットワークに O(N ) サイズの連結成分が存在しなくなる。ここでしきい値

fc を減らした場合、攻撃に必要なノード数が増えることになるため、頑健になる。そこで比較のために、次数分布の母関数を用いたパーコレーションしきい値の推定方法を用いてしきい値 fc を計算する [3, 69]。まず平均次数 d と次数分布 P (k) に対して次の確率分布

Q(k) を定義する。

Q(k) = (k + 1)

P (k + 1)
.
d

(32)

これはランダムに一本のリンクを選択して、その先にあるノードを一つ選択した時に、次数 k のノードが選択される確率になっている。

ここで次数の上位 (1 − f ) ％に含まれているノードを除去する攻撃を考える。この攻撃による除去の後にネットワークに残っている次数で最大のものを kcut とする。さらに、
次数 kcut を持っていたにも関わらず除去されたノードの割合を ∆f とする。すると、ランダムに選択したノードが攻撃によって除去されない確率は

f=

kcut
!

k=kminP (k) − ∆f P (kcut ).

(33)となる。ここで kmin はネットワークに含まれている最小次数である。同様に考えて、ランダムに選択したリンクが攻撃によって除去されない確率は

fˆ =

kcut
!

k=kminQ(k − 1) − ∆f Q(kcut − 1),(34)となる。除去前の P (k) と Q(k) に対応する除去後の分布を P̂ (k) と Q̂(k) とすると次のように書くことができる [3, 70]。

f P̂ (k) =kcut!

k! =kmin

) "*
)
*
!
k ˆk
k
cut
k
−k
P (k )f (1 − fˆ)− ∆f P (kcut )fˆk (1 − fˆ)kcut −k (35)
k
k
"

92

fˆQ̂(k) =

kcut
!

) "*
)
*
!
k ˆk
k
−
1
cut
k
−k
Q(k )
f (1 − fˆ)− ∆f Q(kcut )fˆk (1 − fˆ)kcut −1−k .
kk"

k! =kmin

すると P̂ (k) と Q̂(k) の母関数 F0 (x) と F1 (x) は次にようになる。

F0 (x) =!

P̂ (k)xk

(36)

(37)

k

k

cut
!
1 !
∆f
=
P (k " )(fˆx + 1 − fˆ)k −P (kcut )(fˆx + 1 − fˆ)kcut ,f !
f
k =kmin!
F1 (x) =Q̂(k)xk

(38)

k

k

−1

cut
!
1
=
fˆ !

!
∆f
Q(k " )(fˆx + 1 − fˆ)k −Q(kcut − 1)(fˆx + 1 − fˆ)kcut −1 .
ˆfk =kmin −1

すると、最大連結成分に含まれているノード割合は

s = f (1 − F0 (u)),(39)

で求めることができる。ここで u は u = F1 (u) の解となっており、数値的に得ることができる。ここで u < 1 を満たす解が存在することが、最大連結成分が現れる条件 (s > 0)となっているので、パーコレーションしきい値 fc は次の条件式で得ることができる。

F1" (1) =

kcut
−1
!

k " Q(k " )k! =kmin −1

kcut!
k(k − 1)P (k)kcut (kcut − 1)P (kcut )
=
− ∆f
= 1.
#k$
#k$

(40)

k=kmin条件式 40 を満たす kcut と ∆f から式 33 より fc を求める。ただし、この fc はコンフィ

ギュレーションモデルによってランダム化したネットワークでしか使用することができない。これらの式 33 から式 40 をランダムレギュラーグラフと、その離散的摂動とランダム摂動を適用したネットワークで計算してパーコレーションしきい値 fc の比較を行う。

93

5.5.1 Newman-Ziff アルゴリズム

再計算しない次数順攻撃に対する頑健性指標 RTA を効率的に計算する手法として、

Newman-Ziff(NZ) アルゴリズムが提案されている [71]。NZ アルゴリズムでは、素集合

データ構造を扱うのための Union-Find アルゴリズムを適用することで、次数順攻撃に対する最大連結成分サイズを計算する。

まず素集合データ構造と Union-Find アルゴリズムについて説明する。素集合データ構

造とは互いに共通要素を持たない集合の集まりであり、全体をオーバーラップが無いように分割したものである。また各素集合は、代表要素を一つ持っている。これらの素集合の操作を効率的にするものが Union-Find アルゴリズムである。名称の通り、二つの集合を連結する操作 (Union) と各要素が含まれる集合の代表要素を探す操作 (Find) を行う。

各素集合は、代表要素の根ノードを中心とした有向木として実装される。根でないノードは一つの親ノードを持っており、親ノードを辿ると根ノードまで到達することができる。このように再帰的に親ノードを辿る操作を Find として実装する。また、二つの素集

合 A, B を連結する Union は A の根ノードを B の根ノードの親ノードにするように実装する。基本的な操作は以上であるが、木の経路圧縮や Union の親ノードの選択方法など、
さらに高速化するための実装テクニックが多数存在している。

Union-Find アルゴリズムを用いて攻撃に対する最大連結成分サイズを計算するものが

NZ アルゴリズムである。NZ アルゴリズムでは、まず最初にノードの除去順リスト M を作成する。ここで次数の再計算をしないので、M は次数の降順になる。Union-Find アルゴリズムでは除去ではなく連結 (Union) をするため、除去順リスト M の後ろ側からノードをネットワークに挿入することを考える。挿入されたノードが、既に挿入されたノードとリンクしていた場合、Union をしてその連結成分に加える。この Union の処理時に、根ノードは素集合 (連結成分) に所属しているノード数を計算する。これを繰り返すことで、連結成分サイズを計算することができる。

Newman-Ziff アルゴリズム

1. 除去リスト M の後ろから一つのノードを挿入する。

挿入されたノードは、自身のみが含まれている素集合として扱う。

2. 挿入されたノードと既存ノードの間にリンクがある場合、各素集合を Union する。
3. Union の際に、根ノードに素集合に含まれているノード数を格納する。

4. 全根ノードに格納された値で最大のものが、最大連結成分サイズとなる。
5. 1. に戻る。

94

5.6 ランダムレギュラーグラフとその摂動ネットワークにおける攻撃に対する頑健性の比較

ランダムレギュラーグラフと摂動ネットワークで、次数順攻撃による頑健性指標 RTAと攻撃に対するパーコレーションしきい値 1 − fc の比較を行う。以下、分かりやすさのためにパーコレーションしきい値は 1 − fc と表記する。1 − fc が増えるほど頑健性も向上することになる。ネットワークは N = 6300 ノードと平均次数 d = 4 と 6 のものを用いる。ここで平均次数 d = 4 と 6 の両方でランダムレギュラーグラフを生成することができるため N = 6300 ノードとしている。離散的摂動としてのバイモーダルネットワー
クでは次数 d1 と d2 が 2 ≤ ∆d ≤ 10 であるもので比較を行う。バイモーダルネットワー

クとして実現可能な次数組合せで、最も分散が小さいものから網羅的になっている。また

ランダム摂動は、除去と追加の割合を p = 0.005、0.01、0.1、0.25、0.5、0.75、1 とする。
図 55 と図 56 にそれぞれ平均次数 d = 4 と 6 での次数分布の分散 σ 2 に対する頑健性指標 RTA を示す。両方の図で、明らかにランダムレギュラーグラフ (赤丸) が最も高い RTAを持っていることが分かる。このことから、次数分布の分散が小さいようなランダムレ

ギュラーグラフの周辺であっても、分散が最も小さいランダムレギュラーグラフが最も高い頑健性を持つことが分かった。ランダム摂動 (緑六角) では、次数分布の分散が小さくなるほど RTA が高くなっている。一方で、離散的摂動 (青三角) では、大まかな傾向としてはあるものの、必ずしも分散が小さいほど RTA が高くはならないという結果が得られた。これらの結果をまとめると、レギュラーランダムグラフの摂動を考えた周辺では、必ずしも分散が小さいほど頑健性が高くなる訳ではないものの、最も均質なランダムレギュ
ラーグラフが最も高い頑健性を持っていることが分かった。

図 57 と図 58 にそれぞれ平均次数 d = 4 と 6 での次数分布の分散 σ 2 に対するパーコ

レーションしきい値 1 − fc を示す。パーコレーションしきい値 1 − fc での結果は頑健性指標 RTA での結果とかなり類似している。まず、どちらの図でも明らかにランダムレ

ギュラーグラフ (赤丸) が最も高いしきい値 1 − fc を持っている。さらにランダム摂動(緑六角) では、次数分布の分散が小さくなるほど 1 − fc が高くなっている。まとめると

パーコレーションしきい値 1 − fc においても、ランダムレギュラーグラフは最も高い頑健性を持っていることが分かった。頑健性指標 RTA での結果と異なっている点として、離散的摂動 (青三角) では RTA よりも 1 − fc の方がより横並びになっている点が多くなっている。例えば図 57 では分散 2 ≤ σ 2 ≤ 6 の範囲で 1 − fc ≈ 0.32 となっているものが五点もある。この結果からバイモーダルネットワークでは、次数分布の分散がパーコレー

95

図 55

平均次数 d = 4 での次数分布の分散 σ 2 に対する頑健性指標 RTA 赤丸、青三

図 56

平均次数 d = 6 での次数分布の分散 σ 2 に対する頑健性指標 RTA 赤丸、青三角、緑六角がランダムレギュラーグラフ、離散的摂動、ランダム摂動の結果を示す。

角、緑六角がランダムレギュラーグラフ、離散的摂動、ランダム摂動の結果を示す。

96

図 57

平均次数 d = 4 での次数分布の分散 σ 2 に対するパーコレーションしきい値

1 − fc 赤丸、青三角、緑六角がランダムレギュラーグラフ、離散的摂動、ランダム摂動の結果を示す。

図 58

平均次数 d = 6 での次数分布の分散 σ 2 に対するパーコレーションしきい値

1 − fc 赤丸、青三角、緑六角がランダムレギュラーグラフ、離散的摂動、ランダム摂動の結果を示す。

97

ションしきい値へ与える影響が少ないことが考えられる。

ここまでの結果からランダムレギュラーグラフがその周辺で最も高い頑健性を持っていることが分かり、さらにランダム摂動でも次数分布の分散が小さい方がより攻撃に対して頑健になることが分かった。一方で、バイモーダルネットワークでは次数分布の分散が変化しても頑健性が変化していない場合が見られた。そこで、バイモーダルネットワークが攻撃に対してどのように最大連結成分サイズが変化しているのかを確かめる。

図 59

平均次数 d = 4 で次数 d1 = 2 のバイモーダルネットワークにおける攻撃による最大連結成分の比率の変化。横軸 f は除去されずに残っているノードの割合を示す。
茶色線が同じ平均次数のランダムレギュラーグラフでの結果。紫、赤、緑、橙、青線がそれぞれ d2 = 5、6、7、8、9 での結果。

まず平均次数 d = 4 で次数 d1 = 2 の場合を考える。図 59 に攻撃による最大連結成分

サイズの変化を示す。次数 d1 が固定の場合は次数 d2 が増加するほどより次数分布の分散は大きくなる。そのため図からも d2 が大きくなると、より右側で最大連結成分の比率がS(q) ≈ 0 となっている。またこの図では各線の下側面積が RTA の値に対応している。すると、d2 が大きくなるほど RTA は小さくなっていることが分かる。このことから d1 = 2
では、次数分布の分散が小さくなるほど頑健性が大きくなることが分かる。

次に同じ平均次数 d = 4 で次数 d1 = 3 の場合を考える。同様に、図 60 に攻撃による最大連結成分サイズの変化を示す。次数 d1 = 3 においても d2 ≤ 7 の範囲では d2 が大きくなると、より右側で最大連結成分の比率が S(q) ≈ 0 となっている。一方で 7 ≤ d2 では
それ以上右側に行かずに、線が重なっていることが分かる。このことから d1 と d2 の値が

98

図 60

平均次数 d = 4 で次数 d1 = 3 のバイモーダルネットワークにおける攻撃による最大連結成分の比率の変化。横軸 f は除去されずに残っているノードの割合を示す。
茶色線が同じ平均次数のランダムレギュラーグラフでの結果。紫、赤、緑、橙、青線がそれぞれ d2 = 5、6、7、8、9 での結果。

大きくなると、分散と頑健性が連動しなくなることがあることが分かった。さらに、各線の下側面積から RTA の値を考えた場合でも、7 ≤ d2 では線が重なっているため、差が小さくなっている。また、7 ≤ d2 の各線は二段階の変化をしているようにも見ることができる。このような最大連結成分の変化が見られる理由はよく分かっておらず、今後の研究課題となる。しかしながら、少なくとも、ランダムなネットワークにおいて次数分布の分散と攻撃に対する頑健性が必ずしも一致しない場合が存在することが判明した。

99

5.6.1 RR グラフとその摂動グラフにおける異なる種類の攻撃に対する頑健性指標

ここまでの結果から、次数順攻撃に対してはランダムレギュラーグラフが最も頑健になることが分かった。そこで、次数順攻撃ではない他の攻撃に対する頑健性について、ランダムレギュラーグラフとその摂動グラフで調査した。2.4.5 章で説明した、現状最も強力な BP 攻撃 [31] と地震や津波のモデルの範囲攻撃 Localized Attacks (LA) [32] で頑健性指標を比較する。

図 61 と 62 に平均次数 d = 4 と 6 における BP 攻撃に対する頑健性指標 RBP をそれぞれ示す。BP 攻撃でも次数順攻撃と同様に、ランダムレギュラーグラフが最も高い頑健性を持っている。また、離散摂動とランダム摂動において、次数分布の分散が小さいほど頑健性が高くなる傾向があった。これらの結果から、最も強力な BP 攻撃に対しても、ランダムレギュラーグラフが最も高い頑健性を持っていることが明らかになった。

図 63 と 64 に平均次数 d = 4 と 6 における LA に対する頑健性指標 RLA をそれぞれ示す。LA では最初に一つのシードノードを選択して、その距離が近い方からノードを一つずつ除去していく。ここでシードノードは 100 回ランダムに選択している。得られた結果から LA においても、ランダムレギュラーグラフが最も高い頑健性を持っていることが分かった。また、摂動グラフでは次数分布の分散が小さいほど、より頑健になるという傾向が得られた。これらの結果から LA に対する頑健性でも、次数順攻撃や BP 攻撃と同様の傾向があることが分かった。つまり、LA のような範囲攻撃でも、次数分布の分散が小さいほどより頑健になることを示唆している。これは LA の理論解析で得られた傾向と類似している [72]。

100図 61 BP 攻撃への頑健性指標 RBP と次数分布の分散 σ 2 . 平均次数 d = 4. 赤丸、青三角、緑六角がランダムレギュラーグラフ、離散的摂動、ランダム摂動の結果を示す。

図 62 BP 攻撃への頑健性指標 RBP と次数分布の分散 σ 2 . 平均次数 d = 6. 赤丸、青三角、緑六角がランダムレギュラーグラフ、離散的摂動、ランダム摂動の結果を示す。

101

図 63 LA への頑健性指標 RLA と次数分布の分散 σ 2 . 平均次数 d = 4. 赤丸、青三角、緑六角がランダムレギュラーグラフ、離散的摂動、ランダム摂動の結果を示す。

図 64 LA への頑健性指標 RLA と次数分布の分散 σ 2 . 平均次数 d = 6. 赤丸、青三角、緑六角がランダムレギュラーグラフ、離散的摂動、ランダム摂動の結果を示す。

102

5.7 まとめ

本章では、均質なネットワークほど攻撃に対して頑健であるという知見から、次数分布が変化する場合における頑健なネットワーク構造について明らかにした。先行研究による

特定の次数分布に対する頑健性の解析や 3 章での次数変化するループ強化リワイヤリング法での結果、4 章での最小次数戦略によるリンク追加法での結果から、べき乗分布のようなすそ野の広い次数分布よりも狭く平均次数の周辺に集中した次数分布を持つネットワー
クの方が攻撃に対して頑健であることが示唆されていた。しかしながら、次数分布が連続的に変化する場合には頑健性がどのような振る舞いをしているのか分かっていなかった。
そこで Growing Network モデルと逆優先的選択モデルを用いて、べき乗からカットオフ
付きべき乗、指数、さらに狭い分布へと連続的に変化する次数分布を持ったランダムなネットワークを生成して、これらのネットワークでの頑健性指標を比較した。得られた結果から、次数分布の分散が小さくなるほど、次数順攻撃と BP 攻撃の両方に対してより頑健になることが明らかになった。さらに、これらの範囲の次数分布では頑健性指標と最小FVS サイズが相関係数 0.99 以上と非常に強い相関関係にあることも分かった。これらの結果から、べき乗からカットオフ付きべき乗、指数、さらに狭い次数分布を持つランダム
なネットワークでは、次数分布の分散が狭くなるほど、攻撃に対する頑健性と最小 FVS

サイズの両方が向上していくことが分かった。ただし、ランダムではない場合、特に逆優
先的選択モデルの生成過程によって生じる特殊な鎖状構造が存在する場合には、次数分布の分散が小さくなったとしても頑健性は必ずしも向上しないという結果も得られた。実は、実際のネットワークデータは完全なランダムではなく、コミュニティ構造などで知られるように局所的な構造を持っているものは多く存在する。そのため、次数分布だけでなく、さらに局所的な構造が頑健性に与える影響を明らかにすることが今後の研究課題となる。

逆優先的選択モデルで生成される次数分布は、パラメータ β によって指数分布からさらに狭い分布と変化していく。ただし β → ∞ と極限を取ったとしても、次数分布の分散はある一定値でとどまりゼロにはならない。そのため、次数分布の分散が最小値をとるラ
ンダムレギュラーグラフや、その周辺で頑健性がどのようになっているのかは、逆優先的
選択モデルによる比較では分からない。そこで、最も均質なレギュラーグラフとそれに摂動を加えたネットワークで頑健性を比較する。ここでは離散的摂動としてのバイモーダル
ネットワークと、ランダム摂動としてのランダムなリンク除去・追加を適用したネット

ワークを用いた。特に、バイモーダルネットワークの中でも最も次数分布の分散が小さい103

方から順番に網羅的になるように生成して、比較を行った。得られた結果から、ランダム

レギュラーグラフが最も高い頑健性を持っていることが数値的に明らかになった。また、
ランダム摂動によるネットワークでも、次数分布の分散が小さくなるほど頑健性が高くなることが分かった。これらの結果から、この範囲においても次数分布の分散が小さくなる
ほど頑健性が高くになる傾向があり、また分散最小のランダムレギュラーグラフが最も高い頑健性を持つことが数値的に示された。この結果は、次数分布が変化する場合に、ランダムレギュラーグラフが攻撃に対して最適な頑健性を持つ可能性が非常に高いことを示している。

ただし、離散的摂動として比較したバイモーダルネットワークでは少しだけ異なる結果が得られた。全体的には、次数分布の分散が小さくなるほど頑健性が高いという傾向自体は見られた。ただし、いくつかのネットワークでは、次数分布の分散が異なっていても頑健性指標の値がほとんど同じものが存在していた。攻撃に対する最大連結成分サイズの変化を確かめたところ、次数 d1 と d2 が共に大きくなるとその変化が小さくなることが分かった。また、二段階のような減少の仕方をしていることが分かった。このような変化を示している理由はよく分かっていないが、少なくともランダムなネットワークであっても必ずしも次数分布の分散と攻撃に対する頑健性指標が連動しない場合があることが明らか
になった。

104

6 結言

6.1 研究成果の要約

本研究は、攻撃に対して頑健なネットワーク構造の解明と、効率的な頑健性向上手法の提案を目的として、筆者のおこなってきた研究成果をまとめたものである。以下、各章を要約する。

第一章では、現代社会に不可欠な大規模で複雑なネットワークは攻撃に対して脆弱な構造をしていることを述べた。その後、背景として攻撃に対して頑健なネットワーク構造の必要性と課題を整理した。そして、本研究の目的を述べて、構成を記述した。

第二章では、複雑ネットワークの基本的な概念を述べた後、スケールフリーなネット

ワークと現実ネットワークの攻撃に対する脆弱性についてまとめた。その後、攻撃に対して頑健なネットワークとして、次数相関による玉ねぎ状ネットワークがあることを述べた。

第三章では、攻撃に対する頑健性とループ強化の関係について議論した後、頑健性向上のためのループ強化リワイヤリング法を提案した。いくつかの実際のネットワークデータに適用して、従来の次数相関による手法と比較した結果、提案したループ強化リワイヤリ
ング法は頑健性を従来手法と同等かそれ以上にまで改善することを数値的に示した。そして、従来の次数相関では考えられていなかった、次数分布が変化する場合でも、ループ強化は頑健性を大幅に向上できることを示した。さらに、次数分布が変化する場合には、次数相関が負であっても、高い頑健性を持ちうることを示して、さらに相関係数の比較から
頑健性は次数相関よりもループの方が強い関係にあることを示した。最後に、次数変化する場合のループ強化リワイヤリングでは、次数分布が均質になるように変化していることを確かめた。

第四章では、次数分布が変化する場合の頑健性向上のための効果的なリンク追加法について議論した。まず、先行研究で有効とされてきた最小次数戦略と最長距離戦略が、ループのないネットワークでは類似したノード対を選択することを議論した。その後、次数と距離の二段階によるリンク追加法の枠組みを提案して、それぞれが頑健性の向上に与える
影響について議論した。ループのないネットワークに適用した結果から、最小次数戦略が最も頑健性を向上するのに効果的であることが分かった。ただし、最小次数であっても、非常に近いノード同士を結ぶ手法はあまり頑健性を向上しなかった。言いかえると、局所的な短いループは頑健性をあまり向上せずに、むしろ大局的な長いループを強化すること105

が、より頑健性の向上に効果的であることが分かった。また、例外的に追加リンク数が極端に少ない場合は、最長距離戦略が頑健性向上に有効であることが明らかになった。さらに、ループのあるネットワークで比較した結果から、平均次数が多くなるにつれて最小次数戦略がより効果的になることが明らかになった。この場合では、最小次数であれば、最短距離ノードであっても頑健性を大幅に向上していた。実際のネットワークデータにおいても最小次数戦略が非常に有効であるという結果が得られた。リンク追加の場合では、必ずしも最小 FVS サイズと頑健性が一致していない場合があることが分かった。特に、短いループを形成するような場合では、最小 FVS サイズが大きくても頑健でない場合があることが判明した。

第五章では、ランダムネットワークにおける次数分布の均質さと攻撃に対する頑健性の関係性を解明した。まず、連続的に変化する次数分布を生成するモデルとして Growing

Network モデルと逆優先的選択モデルに二種類を用いて、べき乗からカットオフ付きべき乗、指数、さらに狭い分布の範囲の次数分布を持ったランダムなネットワークでの頑健性について調査した。その結果から、次数分布の分散が小さくなるほど、攻撃に対する頑健性と最小 FVS サイズの両方が向上することが分かった。また、逆優先的選択モデルによる鎖状構造を持つランダムでないネットワークでは、必ずしもこの関係性が成り立たないことを確かめている。次に、逆優先的選択モデルでは生成することができない、最も均質なランダムレギュラーグラフとその周辺での頑健性について調査した。ランダムレギュ
ラーグラフの周辺として、離散的摂動とランダム摂動を考えた。離散的摂動として二峰性ネットワークを考えて、分散が最小のものから網羅的に生成することを議論した。より多峰なランダム摂動では、ランダムレギュラーグラフに一様ランダムにリンクの追加と削除を繰り返すものを考えた。これらの摂動ネットワークとランダムレギュラーグラフでの攻撃に対する頑健性での比較から、レギュラーランダムグラフが最も高い頑健性を持つことが明らかになった。

6.2 今後の課題

本研究の今後の課題について述べる。

第三章では、攻撃に対する頑健性とループの関係から、ループ強化リワイヤリングを提案した。しかしながら、頑健性とループの関係性は極限での割合の等価性しか分かっていないため、どの範囲であれば相関関係があるのかは必ずしも明らかでない。第四章と第五章での結果も踏まえると、短いループが多く形成されているような場合では頑健性が向上
しないことが考えられる。そこで例えば次数相関やコミュニティ構造などのより高次の構106

造がある場合に、ループと頑健性がどのような関係にあるのかを明らかにすることが課題として挙げられる。また、提案手法でも次数変化するループ強化リワイヤリングでは、他の次数変化するスパニングツリー数や次数によるリワイヤリングとの差がほとんど無かった。しかしながら、次数分布が変化した場合でも、頑健性と最小 FVS サイズは強く相関している。このことから、より最小 FVS サイズを増やすような次数変化リワイヤリ

ングが可能かもしれないと予想できる。我々が提案した確率 qi0 を小さいノード同士を結びつけるという方針でないものを考案することで、最小 FVS サイズを増加させる次数変化リワイヤリングが実現可能かもしれない。そこで、より大局的なループに注目した最小FVS サイズを増加させる手法の提案が今後の課題となる。

第四章では、次数と距離によるリンク追加法について議論した。我々はリンク追加法による頑健性の評価を数値シミュレーションによって行った。また、これまでの研究でも、リンク追加法は主に数値シミュレーションでその頑健性の向上が調べられている場合が多い。そのため、理論的な解析があまりされおらず、今後の課題として挙げられる。また、リンク追加の結果では、短距離へのリンク追加によって最小 FVS サイズが増加するが、頑健性が向上しない場合があった。得られた結果からも、なるべく長いループを形成することが、攻撃に対する頑健性の向上には効果的であると考えられる。しかしながら、どのぐらいの長さを評価する数理モデルや理論が未だ少ないため、このループの長さと頑健性の関係性解明は今後の課題となっている。

第五章では、ランダムなネットワークにおける次数分布の分散と攻撃に対する頑健性について議論した。今回はランダムレギュラーグラフの離散的摂動としてバイモーダルネッ
トワークを考えた。ただ、二峰性ネットワークではそこまで小さい次数分布の分散を実現することができなかった。そこで、次数の種類を拡張した三峰性や四峰性のネットワーク
で比較することで、よりランダムレギュラーグラフの周辺として網羅的に比較することが考えられる課題としてある。ただ、そのように増やしたとしても次数組合せの網羅性に限界があるため、ランダムレギュラーグラフが最適な頑健性を持つことの理論的解析が更なる課題として考えられる。また、逆優先的選択モデルでの鎖状構造を持つネットワークのように、ランダムでないネットワークでは次数分布の影響が相対的に小さくなることがあると分かる。そのため、ランダムでないネットワークでは、どのような構造が高い頑健性を持つのかを明らかにすることが今後の課題として考えられる。非常に特殊な局所構造を持った場合に、最適な頑健性を持つ可能性があるかもしれない。

本論文では、全体を通して代表的な次数順攻撃や最悪の場合の BP 攻撃などの弱点となっている特定の箇所を狙った攻撃に対する頑健性を考えてきた。しかしながら、実際には現実のネットワークは、故障のように一様ランダムに起こるノード除去や、災害のよう107

なネットワークの特定範囲に含まれるノードの除去などの様々な種類の擾乱にさらされている。特に、ランダムな故障への頑健性は昔から議論されているが、災害のような範囲除去に対して頑健なネットワークはまだあまりよく分かってない。そのため、故障や攻撃ではない他のノード除去に対して頑健なネットワーク構造を明らかにすることが、今後の課題として考えられる。

本論文では、トポロジーを変化させることで、攻撃に対する頑健性を最大化することだけに着目してきた。しかしながら、実際のネットワークの頑健化では他の考慮するべき事
象やトレードオフが存在している。より現実的な問題設定にするためには、以下のような考慮するべき事象が考えられる。

• 次数が増加すると、メンテナンスなどのコストが増えることになるため、次数増加がノードへの負担となる。

• 距離の長いリンクほど設置のコストが大きくなるため、リンクの距離が負担となる。
• 大規模なネットワークを全体から考えるのは現実的には難しいため、局所的な情報のみを使用して分散的に構造を変化することが必要になる。

• 生物系や社会系ネットワークでは、ネットワーク構造を意図したように変化させる
こと自体が困難になるため、その系の特性を活かした変化の手法が必要になる。

• 鉄道網では新幹線や在来線、私鉄、地下鉄が相互に組み合わさっているように、多くの現実ネットワークには異なる種類のノードとリンクが存在する。そこで、ノードやリンクが異なる性質を持つことを前提に、頑健性を考慮する必要がある。

• 電力網とインターネットなど異分野のネットワークは相互に依存しているため、広い依存関係を含めた多層ネットワーク構造での頑健性を考える必要がある。

6.3 むすび

本論文では、複雑ネットワークの攻撃に対する頑健性を向上する手法や、頑健なネット

ワーク構造について研究を進めてきた。ループ強化リワイヤリングや頑健性向上についての効率的なリンク追加法の解明など、頑健なネットワークの構築のための新たな知見を得ることができた。しかしながら、ランダムネットワークとは言えない実際のネットワーク
を対象とすると、様々な特殊な構造が含まれるため、実応用に向けてはまだまだ解決すべ
き多くの課題があると感じている。本研究での成果が少しでも現代社会の頑健化に貢献できることを期待している。

108

謝辞

本論文をまとめるにあたり北陸先端科学技術大学院大学 先端科学技術研究科 融合科学

共同専攻 林幸雄 教授には丁寧なる御指導と、御教授賜りました。ここに慎んで感謝の意を表します。また、論文をまとめるに際し、北陸先端科学技術大学院大学 先端科学技術研
究科 融合科学共同専攻 小谷一孔 教授、金沢大学大学院 新学術創成研究科 坂本二郎 教授には、有益な御討論、御助言を賜りました。ここに記し、深く感謝致します。また、統計物理学による理論解析の方面から有益な御助言を頂いた茨城大学大学院 理工学研究科 (理学野) 数学・情報数理領域 長谷川雄央 教授と北陸先端科学技術大学院大学 知識科学系 水高将吾 助教に心から感謝致します。さらに、本研究の途上において貴重な御意見、御協力を頂いた林研究室に所属している博士後期課程の LIAO Fuxuan さんと KIM Jaeho さんに感謝の意を表します。また、学会や研究会において多くの先生方、研究者方に様々な御指導を頂きましたことに厚く御礼申し上げます。

109

参考文献
[1] Peter Brooker. Fear in a handful of dust: aviation and the icelandic volcano.
Significance, 7(3):112–115, 2010.
[2] Réka Albert, Hawoong Jeong, and Albert-László Barabási. Error and attack
tolerance of complex networks. Nature, 406(6794):378–382, 2000.
[3] Reuven Cohen, Keren Erez, Daniel Ben-Avraham, and Shlomo Havlin. Breakdown of the internet under intentional attack.

Physical Review Letters,

86(16):3682, 2001.
[4] Christian M Schneider, André A Moreira, José S Andrade, Shlomo Havlin, andHans J Herrmann. Mitigation of malicious attacks on networks. Proceedings of
the National Academy of Sciences, 108(10):3838–3841, 2011.
[5] Toshihiro Tanizawa, Shlomo Havlin, and H. Eugene Stanley. Robustness of onionlike correlated networks against targeted attacks. Phys. Rev. E, 85:046109, Apr
2012.
[6] Yukio Hayashi and Naoya Uchiyama. Onion-like networks are both robust andresilient. Scientific Reports, 8(1):1–13, 2018.
[7] R. Xulvi-Brunet and I. M. Sokolov. Reshuffling scale-free networks: From random
to assortative. Phys. Rev. E, 70:066102, Dec 2004.
[8] Zhi-Xi Wu and Petter Holme. Onion structure and network robustness. PhysicalReview E, 84(2):026106, 2011.
[9] Masaya Murakami, Shu Ishikura, Daichi Kominami, Tetsuya Shimokawa, andMasayuki Murata. Robustness and efficiency in interconnected networks withchanges in network assortativity. Applied Network Science, 2(1):6, 2017.
[10] Alina Beygelzimer, Geoffrey Grinstein, Ralph Linsker, and Irina Rish. Improving
network robustness by edge modification. Physica A: Statistical Mechanics andits Applications, 357(3-4):593–612, 2005.
[11] Yue Zhuo, Yunfeng Peng, Keping Long, and Yinkai Liu. On allocating redundancy links to improve robustness of complex communication network. In 2009
Asia Communications and Photonics conference and Exhibition (ACP), volume
2009-Supplement, pages 1–7, 2009.
[12] Jichang Zhao and Ke Xu. Enhancing the robustness of scale-free networks. Jour110

nal of Physics A: Mathematical and Theoretical, 42(19):195003, apr 2009.
[13] Li Li, Qing-Shan Jia, Xiaohong Guan, and Hengtao Wang. Enhancing the robustness and efficiency of scale-free network with limited link addition. KSII
Transactions on Internet and Information Systems (TIIS), 6(5):1333–1353, 2012.
[14] Vincenza Carchiolo, Marco Grassia, Alessandro Longheu, Michele Malgeri, andGiuseppe Mangioni. Network robustness improvement via long-range links. Computational Social Networks, 6(1):1–16, 2019.
[15] Paul Erdős and Alfréd Rényi. On random graphs i. Publicationes Mathematicae(Debrecen), 6:290–297, 1959.
[16] Duncan J Watts and Steven H Strogatz. Collective dynamics ofsmall-world

networks. nature, 393(6684):440–442, 1998.
[17] Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286(5439):509–512, 1999.
[18] Albert-László Barabási and Márton Pósfai. Network science. Cambridge university press, Cambridge, 2016.
[19] Jérôme Kunegis. Konect: The koblenz network collection. In Proceedings ofthe 22nd International Conference on World Wide Web, WWW ’13 Companion, pages 1343–1350, New York, NY, USA, 2013. Association for Computing
Machinery.
[20] Tore Opsahl, Filip Agneessens, and John Skvoretz. Node centrality in weighted
networks: Generalizing degree and shortest paths. Social Networks, 32(3):245–
251, 2010.
[21] Fredrik Liljeros, Christofer R Edling, Luis A Nunes Amaral, H Eugene Stanley,
and Yvonne Åberg. The web of human sexual contacts. Nature, 411(6840):907–
908, 2001.
[22] Réka Albert, István Albert, and Gary L Nakarado. Structural vulnerability of
the north american power grid. Physical Review E, 69(2):025103, 2004.
[23] Daniel Jian Sun, Yuhan Zhao, and Qing-Chang Lu. Vulnerability analysis ofurban rail transit networks: A case study of shanghai, china. Sustainability,7(6):6919–6936, 2015.
[24] Oriol Lordan, Jose M Sallan, Pep Simo, and David Gonzalez-Prieto. Robustnessof the air transport network. Transportation Research Part E: Logistics andTransportation Review, 68(1):155–163, 2014.
111

[25] Oriol Lordan, Jose M Sallan, Nuria Escorihuela, and David Gonzalez-Prieto.
Robustness of airline route networks. Physica A: Statistical Mechanics and its
Applications, 445(1):18–26, 2016.
[26] Mark EJ Newman. Assortative mixing in networks. Physical Review Letters,
89(20):208701, 2002.
[27] Ramon Xulvi-Brunet and Igor M Sokolov. Evolving networks with disadvantaged
long-range connections. Physical Review E, 66(2):026118, 2002.
[28] Yukio Hayashi and Jun Matsukubo. Improvement of the robustness on geographical networks by adding shortcuts. Physica A: Statistical Mechanics and its
Applications, 380:552–562, 2007.
[29] Alfredo Braunstein, Luca Dall’Asta, Guilhem Semerjian, and Lenka Zdeborová. Network dismantling. Proceedings of the National Academy of Sciences,
113(44):12368–12373, 2016.

[30] 幸雄 林, 俊弘 谷澤, 朋見 鬼頭, and 洋 岡本. Python と複雑ネットワーク分析 : 関係
性データからのアプローチ. Number 2 in ネットワーク科学の道具箱. 近代科学社,

2019.

[31] Salomon Mugisha and Hai-Jun Zhou. Identifying optimal targets of network
attack by belief propagation. Physical Review E, 94(1):012305, 2016.
[32] Shuai Shao, Xuqing Huang, H Eugene Stanley, and Shlomo Havlin. Percolationof localized attack on complex networks. New Journal of Physics, 17(2):023049,
2015.
[33] Reuven Cohen, Shlomo Havlin, and Daniel Ben-Avraham. Efficient immunization strategies for computer networks and populations. Physical review letters,
91(24):247901, 2003.
[34] Linton C Freeman, Stephen P Borgatti, and Douglas R White. Centrality invalued graphs: A measure of betweenness based on network flow. Social networks,
13(2):141–154, 1991.
[35] Flaviano Morone and Hernán A Makse. Influence maximization in complex networks through optimal percolation. Nature, 524(7563):65–68, 2015.
[36] Flaviano Morone, Byungjoon Min, Lin Bo, Romain Mari, and Hernán A Makse.
Collective influence algorithm to find influencers via optimal percolation in massively large social media. Scientific reports, 6(1):1–11, 2016.
[37] Sen Pei, Xian Teng, Jeffrey Shaman, Flaviano Morone, and Hernán A Makse.
112

Efficient collective influence maximization in cascading processes with first-ordertransitions. Scientific reports, 7(1):1–13, 2017.
[38] Lenka Zdeborová, Pan Zhang, and Hai-Jun Zhou. Fast and simple decycling anddismantling of networks. Scientific Reports, 6(1):37954, 2016.
[39] Hai-Jun Zhou. Spin glass approach to the feedback vertex set problem. European
Physical Journal B, 86(11):455, 2013.

[40] 古田 一雄 and 菅野 太郎. レジリエンス工学の誕生と展望. システム／制御／情報,
60(1):3–8, 2016.

[41] Erik Hollnagel. Safety-i から safety-ii へ : レジリエンス工学入門 (¡特集¿レジリエ
ンスへの潮流). オペレーションズ・リサーチ : 経営の科学, 59(8):435–439, 08 2014.

[42] Yukio Hayashi.

A new design principle of robust onion-like networks self-organized in growth. Network Science, 6(1):54–70, 2018.
[43] Vijay V Vazirani. Approximation algorithms (springer science & business media,
2013.
[44] Richard M Karp. Reducibility among combinatorial problems. In Complexity ofcomputer computations, pages 85–103. Springer, 1972.
[45] Hau Chan and Leman Akoglu. Optimizing network robustness by edge rewiring:a general framework. Data Mining and Knowledge Discovery, 30(5):1395–1425,
2016.
[46] Béla Bollobás. Modern graph theory, volume 184. Springer Science & BusinessMedia, New York, 2013.
[47] Roger Guimera, Leon Danon, Albert Diaz-Guilera, Francesc Giralt, and Alex
Arenas. Self-similar community structure in a network of human interactions.
Physical Review E, 68(6):065103, 2003.
[48] Dongbo Bu, Yi Zhao, Lun Cai, Hong Xue, Xiaopeng Zhu, Hongchao Lu, Jingfen
Zhang, Shiwei Sun, Lunjiang Ling, Nan Zhang, et al. Topological structure
analysis of the protein–protein interaction network in budding yeast. Nucleic
acids research, 31(9):2443–2450, 2003.
[49] Yui Kazawa and Sho Tsugawa. Effectiveness of link-addition strategies for improving the robustness of both multiplex and interdependent networks. Physica
A: Statistical Mechanics and its Applications, 545:123586, 2020.
[50] Tao Wang, Heming Cheng, and Xiaoxia Wang. A link addition method basedon uniformity of node degree in interdependent power grids and communication
113

networks. Physica A: Statistical Mechanics and its Applications, 560:125112,
2020.
[51] Liang Huang, Lei Yang, and Kongqing Yang. Hollowing strategies for enhancing
robustness of geographical networks. Europhysics Letters, 72(1):144, 2005.
[52] Liang Huang, Kongqing Yang, and Lei Yang. Enhancing robustness and immunization in geographical networks. Physical Review E, 75(3):036101, 2007.
[53] Zhengcheng Dong, Meng Tian, Ruoli Tang, Xin Li, and Jingang Lai. Improving
the robustness of spatial networks by link addition: more and dispersed links
perform better. Nonlinear Dynamics, 100(3):2287–2298, 2020.
[54] Toshihiro Nishiguchi and Alexandre Beaudet. The toyota group and the aisin
fire. Sloan management review, 40(1):49–60, 1998.

[55] 敏宏 西口. 遠距離交際と近所づきあい : 成功する組織ネットワーク戦略. NTT 出
版, 2007.

[56] Albert-László Barabási, Réka Albert, and Hawoong Jeong. Mean-field theory forscale-free random networks. Physica A: Statistical Mechanics and its Applications, 272(1):173–187, 1999.
[57] Paul L Krapivsky, Sidney Redner, and Francois Leyvraz. Connectivity of growing
random networks. Physical Review Letters, 85(21):4629–4632, Nov 2000.
[58] Paul L Krapivsky and Sidney Redner. Organization of growing random networks.
Physical Review E, 63(6):066123, May 2001.
[59] Paul L Krapivsky and Sidney Redner. A statistical physics perspective on web
growth. Computer Networks, 39(3):261–276, 2002.
[60] Fuxuan Liao and Yukio Hayashi. Emergence of robust and efficient networks ina family of attachment models. Physica A: Statistical Mechanics and its Applications, 599:127427, 2022.
[61] Duncan S. Callaway, John E. Hopcroft, Jon M. Kleinberg, M. E. J. Newman,
and Steven H. Strogatz. Are randomly grown graphs really random? PhysicalReview E, 64(4):041902, Sep 2001.
[62] Michele Catanzaro, Marián Boguñá, and Romualdo Pastor-Satorras. Generationof uncorrelated random scale-free networks. Physical Review E, 71(2):027103,
Feb 2005.
[63] Vito Latora and Massimo Marchiori. Efficient behavior of small-world networks.
Phys. Rev. Lett., 87:198701, Oct 2001.
114

[64] Toshihiro Tanizawa. Structural robustness and transport efficiency of complex
networks with degree correlation. Nonlinear Theory and Its Applications, IEICE,
4(2):138–147, 2013.
[65] William R Paiva, Paulo S Martins, and André F de Angelis. Unsupervised
strategies to network topology reconfiguration optimization with limited link
addition. In Complex Networks XI, pages 51–59. Springer, 2020.
[66] Hawoong Jeong, Sean P Mason, A-L Barabási, and Zoltan N Oltvai. Lethality
and centrality in protein networks. Nature, 411(6833):41–42, 2001.
[67] Toshihiro Tanizawa, Gerald Paul, Shlomo Havlin, and H. Eugene Stanley.
Optimization of the robustness of multimodal networks. Physical Review E,
74(1):016125, Jul 2006.
[68] Liangliang Ma, Jing Liu, Boping Duan, and Mingxing Zhou. A theoretical estimation for the optimal network robustness measure r against malicious nodeattacks. EPL (Europhysics Letters), 111(2):28003, 2015.
[69] Mark EJ Newman, Steven H Strogatz, and Duncan J Watts. Random graphswith arbitrary degree distributions and their applications. Physical review E,64(2):026118, 2001.
[70] Reuven Cohen, Keren Erez, Daniel ben Avraham, and Shlomo Havlin. Resilienceof the internet to random breakdowns. Phys. Rev. Lett., 85:4626–4628, Nov 2000.
[71] Mark EJ Newman and Robert M Ziff. Fast monte carlo algorithm for site orbond percolation. Physical Review E, 64(1):016706, 2001.
[72] Xin Yuan, Shuai Shao, H Eugene Stanley, and Shlomo Havlin. How breadthof degree distribution influences network robustness: comparing localized andrandom attacks. Physical Review E, 92(3):032122, 2015.

115

業績リスト

1. 学術論文 (全て査読付き)[1] Masaki Chujyo, and Yukio Hayashi, “Adding links on minimum degree and longest distancestrategies for improving network robustness and efficiency.” PLOS ONE 17(10) pp. 1-20
(2022). https://doi.org/10.1371/journal.pone.0276733[2] Masaki Chujyo, and Yukio Hayashi, “A loop enhancement strategy for network robustness.”
Applied Network Science 6, 3 (2021). https://doi.org/10.1007/s41109-020-00343-6

2. 国際会議での発表[1] Masaki Chujyo and Yukio Hayashi, “Optimal network robustness in continuously changing
degree distributions”, The 11th International Conference on Complex Networks and their
Applications, Nov. 8-10, 2022, Palermo Italy. [査読付きプロシーディングあり](ポスター発表)[2] Masaki Chujyo, and Yukio Hayashi, "Improvement of the robustness against attacks incontinuously varying degree distributions", The 10th International Conference on Complex
Networks and their Applications, Nov. 30-Dec. 2, 2021, Madrid Spain. (オーラル発表)[3] Masaki Chujyo, and Yukio Hayashi, "Maximizing network robustness of connectivity byedge additions based on the largest eigenvalue of the non-backtracking matrix.", Networks
2021: A Joint Sunbelt and NetSci Conference, Jul. 5-10, 2021, Online. (ポスター発表)[4] Masaki Chujyo, and Yukio Hayashi, "Rewirings by enhancing loops improve network
robustness" International School and Conference on Network Science, Jan.20-23, 2020,
Tokyo. (ポスター発表)[5] Masaki Chujyo, and Yukio Hayashi, "Significant improvement of network robustness byenhancing loops through rewiring" Book of Abstracts, The 8th International Conference on
Complex Networks and their Applications, BookOfAbstracts, pp.569-571, Dec.10-12, 2019,
Lisbon Portugal. (オーラル発表)

3. 国内シンポジウム・研究会・大会等での発表[1] 中条雅貴 林幸雄, “攻撃に対するネットワーク頑健性向上のためのリンク追加法”,
日本物理学会 2022 年秋季大会, 14pH1101-16, 2022 年 9 月. (オーラル発表)[2] 中条雅貴 林幸雄, “固有値を用いたパーコレーションしきい値の最適化”,
ネットワーク科学研究会 2022, 2022 年 8 月. (ポスター発表)[3] 中条雅貴 林幸雄, “連続変化する次数分布における複雑ネットワークの攻撃耐性”,
日本物理学会 第 77 回年次大会, 17pPSL-26, 2022 年 3 月. (ポスター発表)[4] 中条雅貴 林幸雄, “連続的に変化する次数分布上の頑健性とループの関係”,
ネットワーク科学研究会 2021, 2021 年 12 月. (ポスター発表)[5] 中条雅貴 林幸雄, “Feedback Vertex Set を用いたループ強化によるネットワーク頑健性の向上”, 第 16 回ネットワーク生態学シンポジウム, 2021 年 3 月.
(ポスター発表)[6] 中条雅貴 林幸雄, “ループ強化によるネットワーク頑健性の向上”,
ネットワーク科学セミナー2020, 2020 年 12 月. (学生オーラル発表)[7] 中条雅貴 林幸雄, “Feedback Vertex Set を用いたネットワーク頑健性の向上”,
第 41 回 IBISML 研究会, 2020 年 10 月. (オーラル発表)[8] 中条雅貴 林幸雄, “ループに着目したネットワーク頑健性の強化”,
電子情報通信学会 2020 年総合大会, N-2-3, 2020 年 3 月. (オーラル発表)