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

Title

ループ強化に基づく逆優先選択とメッセージ伝搬法の情報拡散や攻撃耐性に対する強固な効果

Author(s)廖, 福軒

CitationIssue Date

2023-09

Type

Thesis or Dissertation

Text version

ETD

URL

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

RightsDescription

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

Japan Advanced Institute of Science and Technology

博士論文

ループ強化に基づく逆優先選択とメッセージ
伝搬法の情報拡散や攻撃耐性に対する
強固な効果

LIAO FUXUAN

主任研究指導教員 林幸雄

北陸先端科学技術大学院大学 金沢大学
融合科学共同専攻
博士（工学）
令和５年９月A common topological structure, known as scale-free (SF), is observed in many social, technological,
and biological networks. SF networks have efficient short paths between nodes but are highly vulnerable
to intentional attacks targeting hubs with high degrees. This combination of efficient paths andextreme vulnerability creates a double-edged sword. Additionally, SF networks can be generated using
a preferential attachment rule, such as the Barabasi and Albert (BA) model, where new nodes are linked
to existing nodes with a probability proportional to their degree.
Due to the presence of hub nodes, many researchers believe that these hub nodes possess stronger
dissemination capabilities, often referred to as influential nodes. Identifying influential nodes
as seeds in real networks is an important problem with wide-ranging applications. However,conventional heuristic methods do not account for the overlap phenomenon. To address this issue andprevent overlapping of spreading, we propose a new method that combines statistical physics approaches
and multi-hop coverage. We also introduce a faster epidemic model that eliminates the need forstochastic behavior averaging. Computer simulations demonstrate that our method outperforms
conventional methods in terms of stronger spreading power per seed.
Furthermore, Self-organization of robust and efficient networks is important for the future designsof communication or transportation systems, because both characteristics are not coexisting in many
real networks. As one of the candidates for the coexisting, the optimal robustness of onion-likestructure with positive degree-degree correlations has recently been found, and it can be generated
by incrementally growing methods based on a pair of random and intermediation attachments with theminimum degree selection. We introduce a continuous interpolation by a parameter β<=0 between random
and the minimum degree attachments to investigate the reason why the minimum degree selection isimportant. However, we find that the special case of the minimum degree attachment can generate highlyrobust networks but with low efficiency as a chain structure. Furthermore, we consider two
intermediation models modified with the inverse preferential attachment for investigating the effectof distance on the emergence of robust onion-like structure. The inverse preferential attachments
in a class of mixed attachment and two intermediation models are effective for the emergence of robust
onion-like structure. However, a small amount of random attachment is necessary for the network
efficiency, when β is large enough. Such attachment models indicate a prospective direction to the
future growth of our network infrastructures.

Keywords:
Network science, Self-organization, Minimum degree attachment, Influence maximum problem,
Statistical physics approach目次
第 1 章 緒言1

1.1

研究の背景と目的 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2

論文の構成

6

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

第 2 章 ネットワークの基本的な用語や既存の解析指標及び近似解法

2.1

基本的な用語と概念. . . . . . . . . . . . . . . . . . . . . . . . . .

7

ネットワーク科学の基本的な用語 . . . . . . . . . . . . . . .

7· 主な解析指標 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.2.1

次数（Degree） . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.2.2

三角形数とクラスタリング係数 . . . . . . . . . . . . . . . .

9

2.2.3

ネットワーク上のパーコレーション . . . . . . . . . . . . . . 12

2.2.4

近接中心性（closeness centrality） . . . . . . . . . . . . . . 12

2.2.5

媒介中心性（betweenness centrality）

2.2.6

次数相関 (Degree-degree correlations) . . . . . . . . . . . . . 15

2.2.7

頑健性（Robustness） . . . . . . . . . . . . . . . . . . . . . 15

2.2.8

通信効率（Eﬃciency） . . . . . . . . . . . . . . . . . . . . . 17

2.1.1
2.2

2.3

7

Feedback Vertex Set (FVS). . . . . . . . . . . . 13

. . . . . . . . . . . . . . . . . . . . . . 18

第 3 章 最小頂点被覆問題 (Minimum Vertex Cover)

20

3.1

最小頂点被覆問題とは . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.2

コンピューター科学における２-近似アルゴリズム . . . . . . . . . . 23

3.3

統計物理のアプローチ Survey Propagation 法

3.4

初期値やラウンド数の非依存性 . . . . . . . . . . . . . . . . . . . . 27

3.5

Survey Propagation(SP) による最小頂点被覆と 2-近似法による最小. . . . . . . . . . . . 25頂点被覆の近似解の比較 . . . . . . . . . . . . . . . . . . . . . . . . 30
第 4 章 影響力最大化問題における複数の種の探索

4.1

32

IMP とは . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2

4.2

4.3

4.1.1

独立カスケード（IC）モデル . . . . . . . . . . . . . . . . . 32

4.1.2

線形閾値（LT）モデル . . . . . . . . . . . . . . . . . . . . . 36

4.1.3

LT モデルと IC モデルの違い . . . . . . . . . . . . . . . . . 40

拡散処理と高速化計算 . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.2.1

従来の SIR モデル . . . . . . . . . . . . . . . . . . . . . . . . 41

4.2.2

高速化 SIR モデル . . . . . . . . . . . . . . . . . . . . . . . . 42

4.2.3

従来の SIR モデル vs 高速 SIR モデル . . . . . . . . . . . . . 43

従来の IMP に対するヒューリスティック手法 . . . . . . . . . . . . . 46

第 5 章 IMP への近似手法の提案

51

5.1

提案する組み合わせ法 . . . . . . . . . . . . . . . . . . . . . . . . . 51

5.2

提案手法と従来の手法の比較結果 . . . . . . . . . . . . . . . . . . . 54

5.3

本章のまとめ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

第 6 章 頑健性かつ効率的なネットワークを生成するアタッチメントモデルの
族

6.1

6.2

62

Scale-Free 性と優先的選択 BA モデル . . . . . . . . . . . . . . . . . 62
6.1.1

Scale-Free(SF) 性 . . . . . . . . . . . . . . . . . . . . . . . . 62

6.1.2

優先的選択（Preferential Attachment）と BA モデル . . . . 63

逆優先的選択（Inverse Preferential Attachment）と玉ねぎ状ネット
ワーク（Onion-like Network） . . . . . . . . . . . . . . . . . . . . . 67

6.2.1

玉ねぎ状ネットワーク（Onion-like Network） . . . . . . . . 68

6.2.2

玉ねぎ状ネットワークにおける最小次数結合の要因 . . . . . 69

6.2.3

少量のランダムアタッチメントの必要性と効率的な経路. . 806.3

k −β アタッチメントを用いた改良された p-モデル . . . . . . . . . . 84

6.4

IPA モデル上の IMP のシミュレーション結果 . . . . . . . . . . . . 94

6.5

本章のまとめ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

第 7 章 結言102

7.1

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

7.2

今後の課題

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

図目次
1.1

三点の関連性。青色は既知の部分を示し、緑色は私の提案部分を示す。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1

三つのノード（黒丸）と二本のリンク（黒線）で構成された単純無向グラフの例。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2

4

8

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

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

8

2.3

クラスタリング係数の例 . . . . . . . . . . . . . . . . . . . . . . . . 11

2.4

近接中心性の例。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.5

次数順攻撃に対する最大連結成分サイズの減少。 一つのネットワー
クに対して Hub 攻撃を適用した結果を示している。 R 値は各線の下側領域面積に相当する。 . . . . . . . . . . . . . . . . . . . . . . . 17

3.1

VC の例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3.2

貪欲アルゴリズム VC の例 . . . . . . . . . . . . . . . . . . . . . . . 23

3.3

SP 法で 3 つの異なる状態を確率的に決定する方法。0、∗、1 は、白色、灰色の、黒色の丸で表される。下部のノード i の状態は、上部の隣接ノード ∂i の状態によって決定される。(a) ∂i に白色の丸がない
場合、下部のノード i は被覆する必要がなく、白色（状態 0）になる。

(b) ∂i に白色の丸が 1 つある場合、下部のノード i は灰色（ジョーカー状態）になりる。(c) ∂i に白色の丸が 2 つ以上ある場合、下部のノード i は常に被覆される状態（状態 1）で黒色になる。 . . . . . 25

3.4

木の中の VC を見つけるための割り当て法 [1]。 . . . . . . . . . . . 31

4.1

Step 0、ノード 8 とノード 9 が最初の活性ノードである。 . . . . . . 33

4.2

Step 1、ノード 1 と 6 が成功して活性化されたと仮定する。 . . . . 34

4.3

Step 2、ノード 1 と 6 が活性化された。 . . . . . . . . . . . . . . . . 35

4

4.4

Step 3、ノード 4 の隣接ノードはどれも活性化されていないと仮定する。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.5

Step 0、ノード 8 とノード 9 が最初の活性化ノードである。 . . . . 36

4.6

Step 1、ノード 5 が活性化する。 . . . . . . . . . . . . . . . . . . . 37

4.7

Step 2、ノード 6 が活性化する。 . . . . . . . . . . . . . . . . . . . 38

4.8

Step 3、ノード 7 と 1 が活性化する。 . . . . . . . . . . . . . . . . . 38

4.9

最終段階 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4.10 SIR モデルのフローチャート . . . . . . . . . . . . . . . . . . . . . 42
4.11 従来の SIR モデルと高速 SIR モデルにおける、三つの状態 S、I、Rの割合の時間変化を示す。 . . . . . . . . . . . . . . . . . . . . . . . 45

4.12 k-core 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.13 k-shell 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.14 A set of vertexes in 2-ホップ from a vertex w in the process of LC.

49

5.1

(a) 重なり合う状況と、(b) 重なりを避ける状況。 . . . . . . . . . . 51

5.2

l-ホップ被覆の概念を説明する図解。 . . . . . . . . . . . . . . . . . 52

5.3

LastFM の高速 SIR モデルにおける累積感染数 R(t) の時間発展を示す図。λ = 2 で、l = 1、2、4 の場合を比較している。 . . . . . . . . 56

5.4

各種のペア (i, j) 間の距離 di,j の分布を 2-または 4-ホップ被覆（l =2, 4）。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.5

LastFM の高速 SIR モデルにおいて、収束時間 tc における累積感染
数を、感染パラメータ λ を 2 から 10 まで変化させた場合の図。 . . 59

6.1

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

6.2

BA モデルを生成の見取り図 . . . . . . . . . . . . . . . . . . . . . . 65

6.3

玉ねぎ状ネットワークの生成

6.4

SF ネットワークと玉ねぎ状ネットワーク次数分布の比較 . . . . . . 69

6.5

分布の裾野を緑の線に e−βklogk で推定。紫の点と緑の線は、k −β ア

. . . . . . . . . . . . . . . . . . . . . 68

タッチメントによって成長するネットワークの次数分布とその推定値を表している。時間ステップごとの追加リンク数は m = 2 である。 73

5

6.6

分布の裾野を緑の線に e−βklogk で推定。紫の点と緑の線は、k −β ア
タッチメントによって成長するネットワークの次数分布とその推定値を表している。時間ステップごとの追加リンク数は m = 2 である。 74

6.7

β → ∞ の最小次数アタッチメントによるリンクの結合先。黒い線
は、新しいノードから既存の m ノードへの最小次数アタッチメント
によるリンクの結合を示している。右から左に 3 つの部分がある。
右側の最初の部分では、m − 1 個の既存のノードのうち次数が最小の m, m + 1, ..., 2m − 2 に新しいノードが結合される。最小次数アタッチメントのためである。2 番目の部分（中央）では、残りの 1 つのリンクが次数 2m − 1 のノードに結合される。∆t 個の次数が 2m未満のノードが存在するため、次数が 2m − 1 の最も古いノードの追加時間は t − ∆t となる。 t − 1 − ∆t 個のノードのうち、第 3 部分（左側）には、次数が 2m のノードが t − 1 − ∆t 個存在する。これらのノードの追加順序と、時間 t におけるノードの次数の関係は、下から 2 行目と 3 行目に示されている。 . . . . . . . . . . . . . . . . . 77

6.8

k −β アタッチメントによって生成されたネットワークにおけるノードサイズ N に対する指標：r、R、E 。m=2 の場合で、リンク/時間
ステップ。紫色 (十字印)、緑色 (正方形印)、シアン (丸印)、黒 (三角形印)、オレンジ (逆三角形印) の線は、それぞれ β = 0、1、10、50、および 100 に対応する。 . . . . . . . . . . . . . . . . . . . . . . 78
6.9

k −β アタッチメントによって生成されたネットワークにおけるノードサイズ N に対する指標：r、R、E 。m=2 の場合で、リンク/時間
ステップ。紫色 (十字印)、緑色 (正方形印)、シアン (丸印)、黒 (三角形印)、オレンジ (逆三角形印) の線は、それぞれ β = 0、1、10、50、および 100 に対応する。 . . . . . . . . . . . . . . . . . . . . . . 79

6

6.10 ランダムと k −β アタッチメントの混合アタッチメントによるネット
ワークにおける、ノードサイズ N = 5000 で m = 2（左）と m = 4（右）の場合の、混合確率 p に対する効率の変化。ここで、p はラン
ダムアタッチメントの割合を示している。 紫色の線 (十字印)、緑色の線 (正方形印)、茶色の線 (五角形印)、水色の線 (丸印)、黒色の線 (三角形印)、オレンジ色の線 (逆三角形印)、赤色の線 (ダイヤモンド印) は、それぞれ β = 0, 1, 4, 10, 50, 100、および β → ∞ を表している。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

6.11 k −∞ アタッチメントにおける平均経路長 ⟨L⟩ とノード数 N の関係を示したグラフ。縦軸のスケールは (a)〜(d) で異なることに注意。
ここで、p はランダムアタッチメントの割合を示し、m = 2（右）および m = 4（左）での結果を示している。 . . . . . . . . . . . . . . 82

6.12 成長過程を示す図として、(a) 〜 (c) に、異なるランダム結合の数を持つ修正された p-model [2] を示す。図 (d) に示されているように、M-MED モデルは、MED モデル [3, 4] の最小次数選択ではな
く、k −β attachment で修正されている。距離 d と µ + 1 は、p-modelsと MED モデルの場合、ランダムに選択されたノードからのホップ数で測定される。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

6.13 p-model0 における 3 つの基本的な指標 r（上）、R（中）、E （下）をパラメータ β に対してプロットしたグラフ。サイズ N = 5000 で、
時間ステップあたりのリンク数 m は 4 本。

. . . . . . . . . . . . . 89

6.14 p-model1 における 3 つの基本的な指標 r（上）、R（中）、E （下）をパラメータ β に対してプロットしたグラフ。サイズ N = 5000 で、
時間ステップあたりのリンク数 m は 4 本。

. . . . . . . . . . . . . 90

6.15 p-model2 における 3 つの基本的な指標 r（上）、R（中）、E （下）をパラメータ β に対してプロットしたグラフ。サイズ N = 5000 で、
時間ステップあたりのリンク数 m は 4 本。 . . . . . . . . . . . . . . 91

6.16 M-MED における 3 つの基本的な指標 r（上）、R（中）、E（下）をパラメータ β に対してプロットしたグラフ。サイズ N = 5000 で、
時間ステップあたりのリンク数 m は 4 本。 . . . . . . . . . . . . . . 92

7

6.17 成長するネットワークにおける 4 つの修正モデルの次数分布は、m =4 で似たような分布を持っている。各々の (a) (b) (c) (d) において、
p-model0、p-model1、p-model2、M-MED モデルで似たような分布がある。分布の裾は、半対数プロットで指数分布として線形である。

β → ∞ の緑の線（三角形印）とオレンジの線（逆三角形印）の傾きは、β = 1 の紫の線（十字印）とシアンの線（アスタリスク印）の傾きよりも急である。したがって、大きな次数は β が増加するにつれて制限される。つまり、ハブは存在しない。 . . . . . . . . . . 93

6.18 SF ネットワークと IPA ネットワークの比較 . . . . . . . . . . . . . 95
6.19 β は１の時、l = 2, 3, 4 で、SF ネットワーク上各 IMP 解法のシミュ
レーション結果。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

6.20 β は-10 の時、l = 2, 3, 4 で、IPA ネットワーク上各 IMP 解法のシ
ミュレーション結果。 . . . . . . . . . . . . . . . . . . . . . . . . . 97

6.21 β は-20 の時、l = 2, 3, 4 で、IPA ネットワーク上各 IMP 解法のシ
ミュレーション結果。 . . . . . . . . . . . . . . . . . . . . . . . . . 98

6.22 β は-50 の時、l = 2, 3, 4 で、IPA ネットワーク上各 IMP 解法のシ
ミュレーション結果。 . . . . . . . . . . . . . . . . . . . . . . . . . 99

6.23 β は-100 の時、l = 2, 3, 4 で、IPA ネットワーク上各 IMP 解法のシ
ミュレーション結果。 . . . . . . . . . . . . . . . . . . . . . . . . . 100

7.1

Polblogs の高速 SIR モデルにおける累積感染数 R(t) の時間発展を示す図。λ = 2 で、l = 2、3、4 の場合を比較している。 . . . . . . 106

7.2

Polblogs の高速 SIR モデルにおいて、収束時間 tc における累積感染
数を、感染パラメータ λ を 2 から 10 まで変化させた場合の図。 . . 107

7.3

Airtraﬃc の高速 SIR モデルにおける累積感染数 R(t) の時間発展を示す図。λ = 2 で、l = 2、3、4 の場合を比較している。 . . . . . . 108

7.4

Airtraﬃc の高速 SIR モデルにおいて、収束時間 tc における累積感
染数を、感染パラメータ λ を 2 から 10 まで変化させた場合の図。 . 109

7.5

Hamster の高速 SIR モデルにおける累積感染数 R(t) の時間発展を示す図。λ = 2 で、l = 2、3、4 の場合を比較している。 . . . . . . 110

7.6

Hamster の高速 SIR モデルにおいて、収束時間 tc における累積感染
数を、感染パラメータ λ を 2 から 10 まで変化させた場合の図。 . . 111

8

7.7

Gnutella の高速 SIR モデルにおける累積感染数 R(t) の時間発展を示す図。λ = 2 で、l = 2、3、4 の場合を比較している。 . . . . . . 112

7.8

Gnutella の高速 SIR モデルにおいて、収束時間 tc における累積感染
数を、感染パラメータ λ を 2 から 10 まで変化させた場合の図。 . . 113

7.9

GRQC の高速 SIR モデルにおける累積感染数 R(t) の時間発展を示す図。λ = 2 で、l = 2、3、4 の場合を比較している。 . . . . . . . . 114

7.10 GRQC の高速 SIR モデルにおいて、収束時間 tc における累積感染
数を、感染パラメータ λ を 2 から 10 まで変化させた場合の図。 . . 115

7.11 Hepth の高速 SIR モデルにおける累積感染数 R(t) の時間発展を示す図。λ = 2 で、l = 2、3、4 の場合を比較している。 . . . . . . . . 116

7.12 Hepth の高速 SIR モデルにおいて、収束時間 tc における累積感染数
を、感染パラメータ λ を 2 から 10 まで変化させた場合の図。 . . . . 117

7.13 PGP の高速 SIR モデルにおける累積感染数 R(t) の時間発展を示す
図。λ = 2 で、l = 2、3、4 の場合を比較している。 . . . . . . . . . 118

7.14 PGP の高速 SIR モデルにおいて、収束時間 tc における累積感染数
を、感染パラメータ λ を 2 から 10 まで変化させた場合の図。 . . . . 119

表目次
3.1

Maaya 上の VC 初期値変更。 . . . . . . . . . . . . . . . . . . . . . 27

3.2

Hamster 上の VC 初期値変更。 . . . . . . . . . . . . . . . . . . . . 27

3.3

OpenFlight 上の VC 初期値変更。 . . . . . . . . . . . . . . . . . . . 28

3.4

Polblogs 上の VC 初期値変更。 . . . . . . . . . . . . . . . . . . . . 28

3.5

Maaya 上の VC ランダム処理。 . . . . . . . . . . . . . . . . . . . . 28

3.6

Hamster 上の VC ランダム処理。 . . . . . . . . . . . . . . . . . . . 28

3.7

OpenFlight 上の VC ランダム処理。 . . . . . . . . . . . . . . . . . . 29

3.8

Polblogs 上の VC ランダム処理。 . . . . . . . . . . . . . . . . . . . 29

3.9

逆温度パラメータ y が異なる場合について、最小 VC に関する SP
法、BP 法と 2-近似アルゴリズムによる推定値の | V C | を比較する。
太字の数値は最小 VC における最良の結果を表している。 . . . . . 30

3.10 LastFM における異なるラウンド数 T での SP 法による | V C |。ノード数 N = 7624。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.1

従来の SIR モデルにおいて、拡散時間が 2 から 7 のサンプルにおける、最も低い累積感染数と最も高い累積感染数のギャップを示す。 . 44

4.2

高速と従来の SIR モデルにおける収束までの差と計算時間について（CPU：i7-11800H、メモリ：16GB）。 . . . . . . . . . . . . . . . . 44

5.1

8 つのソーシャルネットワークの基本的なトポロジー特徴。 . . . . 54

5.2

提案手法と従来の 6 つの手法による従来の SIR モデルと高速 SIR モ
デルで選択された各種ノードの感染力。N × R(tc )/Ns は、種ノード
あたりの感染力を示し、R(tc ) は収束時間 tc での累積感染を示す。 . 58

6.1

N = 5000 個のノードを持つ初期完全グラフから、m = 2, 4 の場合に生成された、β → ∞ の最小次数アタッチメントによる直径の推定値 N/∆t と実測値。 . . . . . . . . . . . . . . . . . . . . . . . . . 75

10

6.2

修正された p-モデルと MED モデルにおけるβ値の影響により、玉
ねぎ状ネットワークが現れる。MED-rand と MED-kmin は、それぞれ β = 0 と β = ∞ の特殊な例である。RA と D-D は、ランダムア
タッチメントと複写モデルを表す。 . . . . . . . . . . . . . . . . . . 88

7.1

パラメータの組合せ. . . . . . . . . . . . . . . . . . . . . . . . . . 105

第 1 章 緒言

1.1

研究の背景と目的

2000 年前後、現実の複雑なネットワークの繋がりをデータ解析することで、多くの現実のネットワークに共通の繋がり構造を持つことが明らかになった [5, 6]。
このような現象を研究する分野は、「複雑ネットワーク」または「ネットワーク科学」と呼ばれている。歴史的には 20 世紀に、Erdős-Rényi によって、単純な点と線として抽象化した 2 つのノードが一定の確率で結合されるランダムグラフ [7] が研究された。しかしながら、多くの現実のネットワークは、このようなランダム
グラフにおける次数分布が Poisson 分布に従う特徴は持っていない。そこで、コン
ピューターによる大規模なデータ解析を用いて、現実のネットワークに共通する繋がり構造として Scale-Free(SF) 性が発見されてから、様々な分野で 21 世紀初頭
から精力的に研究が行われるようになった。ここで、次数（Degree）とは、ある
ノード i の次数 ki はノード i に繋がるリンクの数で、ネットワークにおいて次数k を持つノードの個数の割合を示すものを次数分布 P (k) という。SF 性とは、ネッ
トワーク内のノードの次数分布が以下のべき分布に従うことを指す。

P (k) ∝ k −γ .

(1.1)

現実のネットワークでは、べき指数が 2 < γ < 3 となっている場合が多い [7]。
べき乗則に従う分布を分かりやすく言い換えると、ごく少数のハブノードが非常に多いリンクを持ち、大多数のノードはごく少数のリンクしか持っていない繋がり構造を指す。このネットワーク構造は、上記のランダムグラフと比較して、一様
ランダムノード故障に対しての連結性により強い頑健性がある。なぜなら、ランダムにいくつかのノードやリンクを削除しても、ハブは残る確率が高く、このネッ
トワークはその連結性と伝達機能を維持することができる。この SF ネットワーク
構造の存在性は、ソーシャルネットワーク [8]、インターネット [9]、タンパク質相
互作用ネットワーク [10] など、多くの実際の応用例で広く確認されている。

1

ハブノードの存在により、多くの研究者はこれらのハブノードがより強力な拡散能力を持てと考える。ところで、ネットワーク上の伝達機能を考えた影響最大
化 (IMP) は、情報拡散をモデル化したときに、多くのノードに情報が拡散するよ
うに、拡散の起点となる拡散の種のノード集合を求める問題となる [11]。例として、バイラルマーケティングが挙げられ、少数の人に商品の無料サンプルを渡す
ことで、その商品の噂が口コミを通して多数の人に伝わることが期待できる [12]。
拡散力を持つ局所的なネットワークの特性（ハブ）を利用して、単一または複数の種を見つける方法を設計しているが、これらの手法には、二つの種間の距離を考慮してなく、拡散の重なり現象が発生する。そこで、我々は、拡散の重なり問題を考慮して、IMP 問題を解決するための新しい方法を見つけることを望んでいる。しかしながら、IMP は NP 困難な問題であり、そのため正確な解を迅速に見つけることは困難である。IMP 問題は頂点被覆 (VC) 問題と相互変換することができる。これは、IMP 問題を解決するために VC 問題のアルゴリズムを使用することができることを意味する [13]。VC 問題には、コンピュータ科学の 2-近似アルゴリズムや統計物理学の Survey Propagation(SP) 法など、多くの近似解法が存在する。特に、統計物理学の SP 法は、VC 問題の解を見つける際に高い効率と優れた精度を持つことが証明されていた [14]。つまり、一つ目の課題として、ループと拡散の重なりを着目して、情報科学のマルチホップ被覆と、統計物理学的なメッセージ伝搬による近似解法を融合して、新たな方法を提案する [Liao2]。種間の距離を長くすることで、拡散の重なり問題を回避させる。更に、実験の過程で、私たちは従来の感染モデルでは，平均化するため多くの時間を要することを発見した。そこで、計算時間を短縮するために、ネットワーク科学における集団的影響
力（Collective inﬂuence）から着想を得た高速計算法を提案する [Liao2]。
更に、SF ネットワークは二つノード間にハブを経由するなどして効率的な最短経路が存在するが、巨大な次数を持つハブノードへの意図的な攻撃に対しては極めて脆弱で、経路の効率と極端な脆弱性の組み合わせは、諸刃の剣と言える。また、SF ネットワークは Barabasiasi and Albert (BA) モデル [6] のように、新しいノードからリンクされたノードがその次数に比例した確率で選択されるような、優先的選択の利己的ルールによって生成される。もし、ハブがなくなった場合、ネット
ワークはどのように変化するのかについて、我々は、成長するネットワークにおいて、強い頑健性と高い通信効率という重要な特性の両方を備える、利己的でな

2

い逆優先的選択（IPA）による、より良いアタッチメント法を考察する [Liao1]。
一方、次数相関ではなく、ループと頑健性のより本質的な関係が明らかにされつつある。特に、ノード除去により最大連結成分サイズがある一定値以下になる
最小ノード集合 Dismantling Set を見つける問題は、除去によりループ無となる最小ノード集合 Feedback Vertex Set (FVS) を見つける問題と漸近的に等価になることが証明されている [15]。直感的にも、ループの無い木構造は攻撃に対して脆弱であることが分かる。さらに、ループ除去に必要なノード数 (FVS サイズ) が多い
ネットワークほど、攻撃に対して頑健であると考えられる [16]。また、ノード数が増加して成長する玉葱状ネットワークにおいて、FVS サイズと頑健性指標に強い相関関係があることが数値的に示されている [16]。玉ねぎ状ネットワークは、次数の大きい順に中心から周リンクに同心円上にノードを配置すると、正の次数相関を強くする、同程度の次数を持つノードが結合することで玉葱状に可視化されることからそう呼ばれる。次数分布を固定した時、次数相関が正の値を持つ玉葱状
ネットワークが最適な頑健性を持つことが明らかになっているが、ランダム、仲介、距離、逆優先選択が玉葱状ネットワークの出現に支配的であるかは、明らかにされていない。そのため、私たちはパラメータの変化に応じてネットワークの成長方法が変化するモデル（k −β attachment）を提案した [Liao1]。最終的に、逆優先選択が玉ねぎ状ネットワーク形成の主要な要因であることが判明した。また、

IPA によって生成される Regular-like ネットワークの拡散能力も研究する価値がある。そのため、私たちは SF ネットワークと IPA ネットワークを IMP 上で比較する実験を行い、以下の結論に達した：ハブを持つ SF ネットワークは、ノードの次数分布がより集中し、ネットワークはより脆弱である。一方、IPA ネットワーク
はより均等な次数分布を持ち、より頑健性がある。
上記のような背景に基づき、本研究では次の三点を具体的な目的としている。また、それら三点の関連性を図 1.1 に示す。

3

図 1.1: 三点の関連性。青色は既知の部分を示し、緑色は私の提案部分を示す。

4

問 1: IMP 問題に対して、拡散の種として影響力のあるノードを見つけることは、
広い応用範囲に関わる重要な問題である。従来のヒューリスティックな手法
では、ループと拡散の重なりを考慮しない。そこで、ループと拡散の重なりに着目して、統計物理学的アプローチ（ループ強化）とマルチホップ被覆（重なり解消）を組み合わせた新しい手法を提案する。より強力な拡散力を持つ
種ノードを見つけるためには、拡散の重なりを回避することが重要であることが明らかになる。更に、従来の拡散処理では、多くの試行（平均化）が必要であるが、計算時間を短縮するために、統計物理のメッセージ伝搬に基づいて、新たな高速化計算で平均化不要として、数倍の速度向上が実現される。
この成果は IMP の問題解決に新たなアプローチと手法を提供し、多くの応用分野が応用できる。例えば、グローバルな流行病の拡大を防止するための問題 [17] など。
問 2: 次数分布の幅が狭いほど頑健性が高くなると考えられ、分布を底上げする逆優先選択は重要な役割を果たす。頑健性の向上への逆優先選択の有効性を示すために、ランダムと最小次数のアタッチメントの間に連続補間を導入し、頑健性、次数相関、通信効率、複数の種攻撃をそれぞれ比較する。逆優先選択
が頑健性と通信効率の向上に重要であることを示す。また、ランダムと IPAモデルの混合アタッチメントを提案して、ランダムアタッチメントが通信効
率と平均経路長に与える影響を調べる。これらの結果は、高い頑健性と通信効率を持つのネットワークの発見において、新たな視点を提供する。
問 3: 玉葱状ネットワークを生成するために、色々な手法が多く提案されてきた(MED-Rand/Kmin)。玉葱状構造の生成に重要な要因を見い出すために、従来の玉葱状ネットワーク生成法を部分変更して、次数相関及び頑健性と通信効率に関する指標を比較する。玉葱状構造の生成に対して、結合距離より逆
優先選択は主な要因であることが分かる。これらは、玉ねぎ状ネットワークの生成に対する理解を深め、利己的な優先的選択の Rich get Richer 原理を得るというルールではなく、少量のランダムな結合がノードに等しく出会いの機会を提供することを意味する。

5

1.2

論文の構成

本論文の構成を以下に示す。
本論文では、全体を六章で構成している。
第一章の緒言に続いて、第二章では、複雑ネットワークの基本的な概念としてネットワークの定義について述べる。さらに、主な解析指標として、次数、クラスタリング係数、パーコレーション、近接中心性、媒介中心性、次数相関、頑健性、通信効率について説明する。その後、Feedback Vertex Set を概説する。
第三章では、最小頂点被覆問題の定義を説明する。そして、コンピューター科
学のアプローチからの２-近似アルゴリズムと統計物理のアプローチからの Survey

Propagation（SP）法を説明する。さらに、SP 法の同時計算を提案した後、SP 法と 2-近似アルゴリズムで提案した最小頂点被覆の大きさを予備実験として比較する。
第四章では、影響力最大化問題（IMP）に関して代表的な、独立カスケード（IC）
モデルや線形閾値（LT）モデルについて説明する。従来のサンプル数を必要とす
る SIR モデルと比較するため、メッセージ伝搬方程式から着想した高速 SIR モデ
ルを提案する。また、IMP 問題のヒューリスティック手法について説明する。
第五章では、IMP を解決するための提案手法と従来の手法の比較結果を示す。
第六章では、広く知られた Scale-Free トポロジー構造及び逆優先的選択（Inverse

Preferential Attachment）と玉ねぎ状ネットワーク（Onion-like Network）の関係を明らかにする。さらに、k −β アタッチメントを用いた改良された p-モデルを提案し、玉ねぎ状ネットワークの主要因を明らかにする。
第七章では、結論として以上の成果をまとめる。

6

第 2 章 ネットワークの基本的な用語や既存の解析指標及び近似
解法
まず、2.1 節において本研究で扱うネットワークの基本的な用語や解析指標を紹介する。2.2 節では既存の主な解析指標を説明する。2.3 節で 最小 Feedback Vertex

Set と二種類の近似解法を説明する。

2.1

基本的な用語と概念

2.1.1

ネットワーク科学の基本的な用語

本研究で議論するネットワークは、図 2.1 に示すように、グラフ G=（V,E）における、ノード（ノード）の集合 V（G）=｛1, 2, 3｝と、ノードを繋ぐリンク（リンク）の集合 E（G）=｛eij ｝ から構成される。ここで、ネットワーク内のノー
ド i とノード j を結ぶリンクを (i, j) と表記する。
但し、リンクの両端が 同じノードに繋がる自己ループ (self loop)、２つのノード間に複数のリンクが存在する多重リンク (multiple links) は認めない単純グラ
フ（simple graph）とする。また、リンクの向きを考慮する場合は有向グラフ (di-graph:directed graph)、考慮しない場合は無向グラフ (undirected graph) と呼ばれるが、本論文で扱うネットワークは、全て無向グラフである。さらに、ネットワー
クには、どのリンクとも繋がっていない孤立ノードは無いものとする。図 2.2 に多重リンクと自己ループ、孤立ノードの例を示す。これらを持たない単純ネットワー
クを対象としている。本論文ではグラフ理論におけるノードとリンクを、ノードとリンクと呼ぶことで統一的に表記する。

7

図 2.1: 三つのノード（黒丸）と二本のリンク（黒線）で構成された単純無向グラ
フの例。

図 2.2: 多重リンク、自己ループ、孤立ノードの例。 これらを含んでいないネット
ワークのみを考える。

8

2.2

· 主な解析指標

一般に、ネットワークを分析する際、様々な指標を用いる。以下、本論文で扱う解析指標として，次数、次数相関、頑健性、通信効率指標について述べる。

2.2.1

次数（Degree）

N 個のノードと M 本のリンクからなるネットワークにおいて、あるノード i の
次数 ki は、ノード i に繋げるリンクの数 ki として定義される。

ki =

N
∑

Aij .

(2.1)

j=1

ここで、Aij は隣接行列で、ノード i と j の間に、リンクが存在する場合は Aij = 1、存在しないの場合は Aij = 0 と定める。リンクの両端には二つノードがあるため、∑N次数を全てのノードで合計すると、 j=1 kj = 2M となる。ネットワークを分析する上では, ある次数 k を持つノードの存在確率 P(k) として次数分布（degree

distribution）[6] を議論することが多い。なぜなら、後述するように、その分布がどのような形をしているかによって、ネットワークの性質が大きく異なるからで
ある。

2.2.2

三角形数とクラスタリング係数

三角形数（Triangle Count）は、グラフ中の各ノードが 1 ホップのノードと直接的に三角形を形成できる数で定義される。三角形は、3 つのノードで構成される集合において、それぞれが他の 2 つのノードと直接結合している関係にある。全てのノードに対して三角形カウントアルゴリズムを実行することで、データセット
全体のある種の集約状態を評価できる。
クラスタリング係数（Clustering Coeﬃcient）は、グラフのクラスタリングの程度を測定するために使用される。クラスタリング係数には、局所クラスタリン
グ係数（Local Clustering Coeﬃcient）とグローバルクラスタリング係数（Global

9Clustering Coeﬃcient）の 2 種類がある。あるノードの局所クラスタリング係数は、そのノードの近傍ノード同士が相互に結合されている度合いを示す。あるノードのクラスタリング係数が高いほど、そのノード周囲のノード同士の関係性が高い
ことを示し、グループの集約度が高いことを示す。その最大値は 1 であり、ある
ノードの周囲のすべての点同士が関係性を持っている場合である。
三角形数の計算式は、1 つのノードから 1-ホップの隣接ノード同士の間でリンクが存在することで定義される。
T riangles = rv .

(2.2)

ここで、rv は、ノード v の隣接の任意の 2 つのノードのペア数を表す。
局所クラスタリング係数の計算式は三角形のカウントに依存して、以下で定義される。

LCCv =2rv,
dv (dv − 1)

(2.3)

dv はノード v の次数を表す。グローバルクラスタリング係数の計算式は以下で定
義される、

GCC =

ClosedT riplets,
T otalT riplets

(2.4)

ここで、

ClosedT riplets = 3 ∗

∑

rv ,

(2.5)

d(dv − 1)
.
2

(2.6)

v∈G

T otalT riplets =∑v∈G

例えば、図 2.3(a) では T riangle = 0、LCCv = 0、(b) では T riangle = 3、LCCv = 0.3、(c) では T riangle = 5、LCCv = 0.5、(d) では T riangle = 10、LCCv = 1 となる。

10

(a)

(b)

(c)

(d)

図 2.3: クラスタリング係数の例

112.2.3

ネットワーク上のパーコレーション

ランダムな木状のネットワークについて、次数相関がない場合、そのようなネットワークには巨大な連結成分が存在することが示され、全体が繋がるランダムな占有ノードの割合としてのパーコレーション閾値は次の式で与えられる [18]。

pc =1g1′ (1)=⟨k⟩⟨k 2 ⟩ − ⟨k⟩

.

(2.7)

ここで、g1′ (1) は余剰次数分布に対応する母関数であり、⟨k⟩ はネットワークの平∑kamx
均次数、⟨k 2 ⟩ は k=kmin k 2 P (k)、kmin と kmax はそれぞれ最小と最大の次数である。
クラスタリングが低い、すなわち 0 < C << 1 のネットワークの場合は、上記の臨界点は（1 − C ）− 1 によってスケーリングされるため、以下に近似される [18]：

pc =

1
1
.
′
1 − C g1 (1)(2.8)

上式は、ある次数分布に対して、クラスタリングがより大きなパーコレーション
閾値をもたらすことを示している。言い換えると、その大きな閾値は、固定されたリンク数に対して、クラスタリング構造がネットワークの連結性を弱体化させることに相当する。但し、高いクラスタリングを持つネットワークの場合は、中心核と周リンクの core–periphery 構造を引き起こす可能性があるため、core と peripheryが異なる臨界点でパーコレートする可能性があり、上記の近似的な処理は適用されない [19] ことに注意されたい。

2.2.4

近接中心性（closeness centrality）

連結されたネットワークにおいて、あるノードの近接中心性は、中心性の尺度の一つであり、そのノードと他のノードとのホップ数で測った最短経路の長さの合計の逆数として計算される。したがって、あるノードがより中心的であるほど、他のすべてのノードに近くなる。
近接中心性は、Bavelas（1950）によって距離の逆数として定義される [20, 21]。

12

Cc (x) = ∑1.
y∈V d(y, x)(2.9)

ここで、d(y, x) はノード x と y の最小ホップ数で測った距離（最短経路の長さ）を表す。上記は標準化されていない近接中心性である。通常、その標準化された形式に言及し、最短経路の合計ではなくその平均値を表すような前の式に N − 1 をかけた以下の形式が広く用いられている。

C(x) = ∑N −1.
y∈V d(y, x)(2.10)

例として図 2.4 では、各ノードの横に書かれた数字は、そのノードと赤い四角い
ノードとの間の最短経路の長さに基づいており、そのノードからの距離を表す。緑色のリンクは、赤い四角形のノードと赤い円形のノードとの間の最短経路のうちの 1 つを示す。したがって、赤い四角形のノードの近接中心性は 5/(1+1+1+2+2)= 5/7 となる。

図 2.4: 近接中心性の例。

2.2.5

媒介中心性（betweenness centrality）

まず説明前に、媒介数（Betweenness）とは何かを知る必要がある。媒介数は、
リンク介数とノード介数の 2 種類に分類される。
リンク介数は、ネットワーク内のあるリンクが、すべての最短経路の中で現れる回数を指す。つまり、このリンクがどの程度の最短経路の一部であるかを表す。
通常、リンク介数が高いリンクほど重要であると考えられている。なぜなら、こ13

れらのリンクは異なるノード間の情報伝搬においてより重要な役割を果たすからである。
ノード介数とは、ネットワーク内のあるノードが全ての最短経路で出現する頻度のことであり、最短経路においてそのノードが中継点としてどのくらい機能するかを表す。通常、ノード介数が高いノードは重要度が高いと考えられている。な
ぜなら、これらのノードは異なるノード間の情報伝搬においてより重要な役割を果たしているからである。
媒介数は、対応するノードまたはリンクがネットワーク全体でどのような役割や影響力を持っているかを反映する重要なグローバル指標であり、現実的な意味を持っている。社会関係ネットワークや技術ネットワークでは、媒介数の分布特性が、例えば、対応する生産関係における異なる人員、リソース、および技術の地位を反映する [22, 23]。これは、重要なリソース、技術、および人材を発見し、保護するために重要である。
媒介中心性は、1977 年に Freeman によって提案され [22]、情報フローに対するグラフ上の影響力が大きいノードを見つけることができ、値が大きいほどそのノードが情報フローに与える影響も大きいことを示す。あるノードの媒介中心度は、ネッ
トワーク内の各ノード対の最短経路数を分母とし、その中で、ノードを通過する
最短経路数を分子として合計する。

Cb (vi ) =∑gij (vi ).
gij
i̸=j̸=v ,i<j(2.11)i

ここで、 gij はノード i からノード j への最短経路の数を表し、 gij (vi ) はノード

i からノード j へのノード vi を通る最短経路の数を表す。
次数中心性に似た性質を持つ、媒介中心性の値はネットワークのサイズに依存する。しかし、ネットワークのサイズに関係なく、相対値を計算するためにはネッ
トワークサイズの影響を排除する必要があり、最大媒介中心性を計算することが一般的である。この時、ノード vi が任意のノード対 (vi , vj ) の全ての最短経路に含まれる場合、そのノードの媒介中心性は最大値 1 になる。したがって、最大媒14

介中心性は、

( )
∑
2 n−1
gij (vi )(n − 1)(n − 2)2
Cb (vi ) =
=
1=
=
.
gij
2
2
i̸=j̸=v ,i<ji̸=j̸=v ,i<j∑i(2.12)iとなるので、標準化された媒介中心性は以下で定義される。

Cb′ (vi ) =2.2.6

2Cb (vi ).
(n − 1)(n − 2)

(2.13)

次数相関 (Degree-degree correlations)

次数相関とは、隣接するノード間の次数の相関のことであり、Pearson の次数相関をリンク両端のノードの次数に対して適用することで、以下の式で定義する

[24]。

∑
ij (Ai,j − ki kj /2M )ki kjr=∑ij (ki δi,j − ki kj /2M )ki kj(2.14)

ここで、δi,j は Kronecker のデルタであり、i ＝ j のときに 1、 i ̸= j のとき 0 になる。また、式変形することで次式（2.4）が得られる [24]。

r=
ここで,

S1 =

∑
i

ki , S 2 =∑S1 Se − S22
S1 S3 − S22

ki2 , S3 =i∑iki3 , Se =(2.15)∑

Ai,j ki kj(2.16)ijである。
上式で計算される次数相関 r の範囲は [-1,1] となる、ｒが負値のときは、次数が異なるノード同士が隣接しやすいことを示し、ｒが正値のときは、次数が同じノード同士が隣接しやすいことを示す。

2.2.7

頑健性（Robustness）

ネットワークへの攻撃に対する結合耐性を評価する指標として、以下のような頑健性指標 R が広く用いられている [25]。頑健性指標 R は、ノードを順に除去し15

たとき，ネットワークの連結性がどの程度まで保存されているかを評価する。具
体的には、除去率 q ％のノードを除去した場合、最大連結成分比 S(q) /N の総和を
頑健性指標 R として評価する（q ％のノードを削除して、ネットワークが様々な島に分断されたしても、その中で一番大きい島が最大連結成分である）。以下に頑健性指標 R の定義式（2.6）を示す。

R=(

1
∑

S(q) /N )/N(2.17)

q=1/N

ここで、N はネットークの全体のノード数で、S(q) はノード除去率 q の時の最∑1
大連結成分 (GC:Ginat Component) の大きさで、 q=1/N は除去率の割合 1/N から 2/N, 3/N, ..., N/N = 1 までの和を表す。S(q)/N が最大連結成分比になり，除去率 q の範囲は [0,1] である。 つまり、ノードを一つずつ順番に取り除いて、その S(q)/N を平均したものである。除去ノードの攻撃法として，次数が高いノード（ハブ）から順に除去する、ハブ攻撃 [25] がよく使われている。図 2.5 に、Hub 攻撃による最大連結成分サイズの崩壊の例を示す。

16

図 2.5: 次数順攻撃に対する最大連結成分サイズの減少。 一つのネットワークに対して Hub 攻撃を適用した結果を示している。 R 値は各線の下側領域面積に相当
する。

2.2.8

通信効率（Eﬃciency）

通信効率（Eﬃciency）は、ネットワークにおいて 2 つのノード間の最短経路長の逆数の和で定義される [26]。通信効率が高いほど、ネットワーク内のノード同士が効率的に情報を伝達できることを示す。具体的には、通信効率は以下の式で定
義される。

E=

∑ 1
1
,
N (N − 1) i̸=j Lij(2.18)

ここで、N はノード数、Lij はノード i と j の間の最短経路長を表す。通信効率は、
ネットワークの構造をより深く理解するために広く用いられる指標の 1 つである。

17

2.3

Feedback Vertex Set (FVS)

あるグラフ G ＝（V,E）から、一部のノードを削除した、残りのグラフ G′ において、ループが存在しない状態まで、削除したその最小除去ノード集合は Feedback

Vertex Set（FVS）と呼ばれる。しかしながら、FVS を探すのは NP 困難な組み合
わせ問題 [13] であり、多項式時間で解くアルゴリズムが存在しない。そこで、厳密に最適解を求めるのが非常に困難であるため、近似アルゴリズムが適用される。
例えば、コンピューター科学における 2-近似アルゴリズムがある。これは、Vijay

V. Vazirani が 2001 年に書籍「近似アルゴリズム」に紹介された方法で、最適解の高々2 倍の近似値が求められる [27]。
下記の Algorithm 1 は、「近似アルゴリズム」[27] から転載した手順を示す。ここで、入力はグラフ G と重み関数 ω であり、出力は FVS に相当した F0 である。

Algorithm 1 Approximation Algorithm of Feedback Vertex Set
Input: Given an undirected graph G=(V,E) and a function ω assigning nonnegative weights to its vertices.
Output: F0
1: H ← G, ωprime ← ω, i ← 0
2: for all H is not acyclic do′}
3:c ← minu∈H { δωH(u)(u)
4:Gi ← H, ti ← cδGi , ω ′ ← ω ′ − ti5:H ← the subgraph of Gi induced by vertices u with ω ′ (u)⟩0
6:i←i+1
7: end for
8: Fk ← ∅9: i = k, ...., 1extend Fi to a feedback vertex set Fi−1 of Gi−1 by adding a minimal
set of vertices from Vi−1 − Vi
10: return F0 .
一方、Algorithm 2 は、統計物理 Cavity 法に基づく Belief Propagation (BP)法である [28]。

18

Algorithm 2 Belief Propagation Algorithm of Feedback Vertex Set
Input: Given an undirected graph G=(V,E)
Output: F0
1: H ← G
2: qi ← the probability of node becoming FVS node.
3: for all H is not acyclic do
4:candidate←a node who has the biggest qi
5:
G′ ←delete the candidate from H
6:
H← G′
7:
i←i+1
8: end for
9: return F0 .

19

第 3 章 最小頂点被覆問題 (Minimum

Vertex Cover)
本章の 3.1 節は、最小頂点被覆問題を定義する。3.2 節は、それに対する２-近似アルゴリズムについて、3.3 節は、統計物理のアプローチからの Survey Propagation（SP）法を説明する。3.4 節は、SP 法における初期値やラウンド数の非依存性を数
値例を用いて示す。3.5 節は、SP 法と 2-近似法で推定した最小頂点被覆の大きさ
を予備実験として比較する。以下、3.1 節と 3.2 節ではグラフ理論の流儀にならい、ノードとリンクを頂点と辺と呼ぶ。

3.1

最小頂点被覆問題とは最小頂点被覆問題 (最小 VC) は、グラフ理論において重要な概念の 1 つであり、あるグラフ G ＝（V,E）において全てのリンクのうち少なくとも片方のノードが被覆されるノードの集合を指す。つまり、その集合に含まれるノードが全てのリンクを被覆しているということである。この概念は、最適化問題の 1 つとしても扱われ、最小 VC は NP 困難問題として知られている [14]。最小 VC は、様々な分野で応用されており、例えば、バイオインフォマティクス [29]、ソーシャルネット
ワーク分析 [30] などに利用されている。
無向グラフ G = (V, E) の頂点被覆 V ′ は、(u, v) ∈ E ならば u ∈ V ′ 又は v ∈ V ′を満たす V の部分集合である。つまり、頂点被覆 V ′ は、すべてのリンクの少なくとも一方の端点が V ′ に含まれ、このような集合は G のリンクを被覆すると言われる。図 3.1 は、いくつかの頂点被覆 V ′ が赤で印された 2 つの頂点被覆の例を示し
ている。

20

図 3.1: VC の例

21

最小 VC
最小 VC とは、与えられたグラフにおいて、最小の |V ′ | となる頂点被覆 V ′ を見つける最適化問題である。
入力 グラフ G
出力 G が頂点被覆 k を持つ場合、最小の数 k
もし問題が決定問題の場合、それは頂点被覆問題 (Vertex Cover Problem) と呼ばれる。
入力 グラフ G と正の整数 k
出力 G がサイズが k 以下の頂点被覆を持つか？
上記の頂点被覆の決定問題は NP 完全問題であり、Karp の 21 の NP 完全問題の 1つである [13]。厳密に最適解を求めるのが非常に困難であるため、近似アルゴリズ
ムが適用される。以下、3.2 節と 3.3 節で述べる二つの近似法を試し、予備実験として 3.4 節にて比較してみた。

22

3.2

コンピューター科学における２-近似アルゴリズム

リンクの両端点を順に頂点被覆に追加し、グラフから削除することを繰り返す
ことで、近似比 2 の解を得ることができる。
まず、貪欲アルゴリズムによって最大マッチング M を見つけ、M に含まれるリンクの両端点から構成される頂点被覆 C を作成する。ここで、マッチングとは、お互いに端点を共有しないリンクの集合で、その最大リンク数である。以下の図3.2 では、最大マッチング M は赤で、頂点被覆 C は青で示されている。

図 3.2: 貪欲アルゴリズム VC の例
この方法で構築された集合 C は頂点被覆であり、リンク e が C によって被覆されていないとすると、M ∪ {e} はマッチングであり、e ∈/ M であり、これは M が極大であるという仮定に矛盾する。さらに、e = {u, v} ∈ M である場合、最適な頂点被覆を含む任意の頂点被覆は u または v （または両方）を含まなければならず、そうでない場合、リンク e は被覆されない。つまり、最適な頂点被覆は M 内の各リンクの少なくとも 1 つの端点を含み、全て片方の端点の場合を考えると、集合 C は最適な頂点被覆の 2 倍以下になることが分かる。
上記は、Vijay V. Vazirani が 2001 年に書籍「近似アルゴリズム」で紹介した方法で、最適解の高々2 倍の近似値が求められる [27] のてある。

23

Algorithm ３は、「近似アルゴリズム」[27] から転載した手順を示す。入力はグラフ G であり、出力は VC に相当した C である。

Algorithm 3 Approximation Algorithm of Vertex Cover Problem
Input: Given an undirected graph G=(V,E) .
Output: C
1: C = ∅, E ′ = E
2: for all E ′ ̸= ∅ do3:
E ′ の任意のリンク (u, v) を考える。
4:
C = C ∪ {u, v}
5:
E ′ から u または v に隣接する全てのリンクを取り除く。
6: end for7: return C.

24

3.3

統計物理のアプローチ Survey Propagation 法

このアルゴリズムは、統計物理学の Cavity 法に基づく Survey Propagation (SP)という方法 [14] で、各ノード i は 3 つの状態を持つ。1 は被覆された状態、0 は被覆されなかった状態、そして、∗ は時々被覆されたりされなかったりする状態（ジョーカー状態）である。ジョーカー状態 ∗ は状態 0 と 1 の間に位置することに注意されたい。ジョーカー状態を導入することによって拡張された探索空間を調整できる。
これが SP と呼ばれる理由である。図 3.3 に示すように、これらの確率は、それぞ
(1)

(0)

(∗)

れ状態 1 を表す π̂j→i 、状態 0 を表す π̂j→i 、ジョーカー状態 ∗ を表す π̂j→i で表記される。

図 3.3: SP 法で 3 つの異なる状態を確率的に決定する方法。0、∗、1 は、白色、灰色の、黒色の丸で表される。下部のノード i の状態は、上部の隣接ノード ∂i の状態
によって決定される。(a) ∂i に白色の丸がない場合、下部のノード i は被覆する必要がなく、白色（状態 0）になる。(b) ∂i に白色の丸が 1 つある場合、下部のノード i は灰色（ジョーカー状態）になりる。(c) ∂i に白色の丸が 2 つ以上ある場合、下部のノード i は常に被覆される状態（状態 1）で黒色になる。
最小 VC を推定するメッセージ伝搬について説明するにあたり、4.2 節にて後述
する情報伝搬における SIR モデル [31] とは異なることに注意する必要がある。各
ノード i に対して、メッセージ伝搬の方程式 [14] は以下のように与えられる。
(0)

π̂i
(∗)

π̂i

= Ci−1= Ci−1 e−y

∑

∏
j∈∂i
(0)

(0)

(1 − π̂j→i ),

π̂j→i

∏
j ′ ∈∂i\j

j∈∂i

25

(3.1)
(0)

(1 − π̂j ′ →i ),

(3.2)


(1)

π̂i

= Ci−1 e−y 1 −∏(0)

(1 − π̂j→i ) −

j∈∂i

∑



∏

(0)

π̂j→i

(1 − π̂j ′ →i ) ,
(0)

(3.3)

j ′ ∈∂i\jj∈∂i

ここで、∂i\j はノード i の最近傍ノード集合で、ノード j を含めないものを表す。また、e−y は VC のサイズを最小化するためのペナルティ因子であり、y は逆
温度パラメータである。規格化定数は、全てのメッセージの積の逆数として与えられる。

[
Ci = e−y∏1 − (1 − e )y](0)(1 − π̂j→i )

.

(3.4)

j∈∂i

また、各リンク i → k に対して、確率は以下の式で与えられる。
−1π̂i→k = Ci→k
(0)

∏

(0)

(1 − π̂j→i ),(3.5)

j∈∂i\k
Ci→l = e−y 1 − (1 − ey )∏(1 − π̂j→i ) .
(0)

(3.6)

j∈∂i\k式 (3.3) から式 (3.6) は、N 個のノードのランダム置換順に左リンクから右リンクへの T 回のラウンドの繰り返しによって計算される。ある程度の収束後、Decimation(1)として [14]、π̂i が最大のノード i が VC として選択される。その後、ノード i が除かれ、上記を再計算する、以下の処理が行われる。
(1)

ステップ 1 式 (3.3)〜(3.6) により、ノード i の確率 π̂i を計算し、最小 VC を推定する。
(1)

ステップ 2 Decimation として、π̂j が最も高いノード j が VC ノードとして選択される。選択されたノード j と孤立したノード (Degree は 0 のノード) がネッ
トワークから削除される。頂点被覆集合の数は |V C| ← |V C + 1| と更新される（最初は |V C|= 0 と設定されている）。
ステップ 3 すべてのノードがネットワークから削除されるまで、ステップ 1 とス
テップ 2 を繰り返す。最終的に、複数の VC ノードのサイズは |V C| として
得られる。

26

3.4

初期値やラウンド数の非依存性

上記のアルゴリズムでは、各ラウンド数 T で、全てのノードが更新されるまでに、ランダムな順番で一つずつ更新される。以下では、ランダムな初期値とラウンド数 T を変更して、推定された | V C | にどのような影響を与えるかを数値的に調べた結果を示す。表中 b—a—c に対して、a は違う Rand 及びラウンド数 T から得られた結果の同じ部分のノード個数、b と c は違う部分のノード個数である。全ての表から VC の個数は大体同じである。表 3.1 から表 3.4 までに、初期値 Randを変更して、| V C | はほとんど同じである。また、各初期値から探す VC ノード
は大体同じである。表 3.5 から表 3.8 までに、ラウンド数 T を変更する。しかし、| V C | はほとんど同じである。また、各ラウンド数 T から探す VC ノードも大体同じである。すなわち、この統計物理学の VC アプローチはうまく収束した、ラウンド及び初期値は最終的な結果に影響を与えない。

Rand1
Rand1
Rand2
Rand3
Rand4
Rand5
Rand6

Rand2
15—147—15

Rand3
Rand4
Rand5
Rand6
6—156—6 15—147—15 5—157—5 15—147—15
16—146—16 5—157—5 15—147—15 5—157—5
14—148—14 5—157—5 16—146—16
15—147—15 6—156—6
13—149—13

VC
162
162
162
162
162
162

表 3.1: Maaya 上の VC 初期値変更。

Rand1
Rand1
Rand2
Rand3
Rand4
Rand5
Rand6

Rand2
Rand3
Rand4
Rand5
Rand6
46—419—47 54—411—55 67—398—69 43—422—42 45—420—44
45—421—45 64—402—65 48—418—46 47—419—45
57—409—58 55—411—53 53—413—51
62—405—59 63—404—60
31—433—31
表 3.2: Hamster 上の VC 初期値変更。

27

VC
465
466
466
467
464
464

Rand1
Rand1
Rand2
Rand3
Rand4
Rand5
Rand6

Rand2
Rand3
Rand4
Rand5
Rand6
60—472—60 50—482—49 61—471—62 61—471—62 60—472—60
59—473—58 58—474—59 58—474—59 56—476—56
55—476—57 57—474—59 62—469—63
56—477—56 63—470—62
58—475—57
表 3.3: OpenFlight 上の VC 初期値変更。

Rand1
Rand1
Rand2
Rand3
Rand4
Rand5
Rand6

Rand2
Rand3
Rand4
Rand5
Rand6
3—354—3 3—354—3 3—354—3 4—353—4 5—352—5
5—352—5 3—354—3 3—354—3 4—353—4
3—354—3 5—352—5 5—352—5
4—353—4 4—353—4
1—356—1

VC
357
357
357
357
357
357

表 3.4: Polblogs 上の VC 初期値変更。

5

T
5
10
20
50
100
200

10
6—156—6

20
50
100
7—155—7 6—156—6 6—156—6
4—158—4 5—157—5 6—156—6
6—156—6 6—156—6
6—156—6200
6—156—6
7—155—7
6—156—6
5—157—5
6—156—6

VC
162
162
162
162
162
162

表 3.5: Maaya 上の VC ランダム処理。

T
5
10
20
50
100
200

5

10
20
50
100
200
46—419—47 54—411—55 67—398—69 43—422—42 45—420—44
45—421—45 64—402—65 48—418—46 47—419—45
57—409—58 55—411—53 53—413—51
62—405—59 63—404—60
31—433—31
表 3.6: Hamster 上の VC ランダム処理。

28

VC
465
466
466
467
464
464

VC
532
532
531
533
533
532

T
5
10
20
50
100
200

5

10
20
50
100
200
61—471—61 57—475—56 63—469—63 58—474—57 58—474—58
67—465—66 62—470—62 51—481—50 61—471—61
61—470—62 61—470—61 64—467—65
55—477—54 61—471—61
56—475—57
表 3.7: OpenFlight 上の VC ランダム処理。

T
5
10
20
50
100
200

5

10
5—352—520
50100
6—351—6 4—353—4 5—352—5
4—353—4 5—352—5 5—352—5
5—352—5 5—352—5
3—354—3

表 3.8: Polblogs 上の VC ランダム処理。

29

200
5—352—5
5—352—5
5—352—5
3—354—3
5—352—5

VC
357
357
357
357
357
357

VC
532
532
531
532
531
532

3.5

Survey Propagation(SP) による最小頂点被覆と2-近似法による最小頂点被覆の近似解の比較

予備実験として、現実のネットワークである LastFM を用いた数値シミュレー
ションを通じて、3.2 節の 2-近似法と 3.3 節の SP 法による最小 VC の近似解を比較し、SP 法が最小 VC をより正確に推定できることを示す。ここで、LastFM は 2020
年 3 月に公開 API から収集された、アジア諸国の LastFM ユーザーのソーシャル
ネットワークである。ノードはユーザーであり、リンクは彼らの間の相互フォロー関係である [32]。
表 3.9 に示されるように、SP 法による解はほぼ最適であり、一方で 2 近似法[33] による解は最適解のほぼ 2 倍の大きさと考えられる。SP 法は統計物理学的アプローチであり、2 近似法は最大 2 倍の大きさを保証するコンピュータ科学的アプローチであることを思い出されたい。さらに、SP 法と比較するために、Belief

Propagation(BP) アルゴリズム [28] を適用して、Feedback Vertex Set から VC に還元してみた。但し、FVS を除去した後、ネットワークの残りは部分木になるので、図 3.4 に示すように、よく知られた方法 [1] を適用して、木を奇数層と偶数層に分割し、サイズが小さい偶数層または奇数層のどちらかを VC として選択する。
表 3.9 に示されるように、SP 法によって推定された |V C| は BP 法によって推定された |V C| よりもわずかに優れている。逆温度パラメータを y = 7 とした場合、最小 VC の結果は最小サイズのものである。さらに、表 3.10 に示されるように、

T = 50 ラウンドが最小 VC の最良の結果を得ている。したがって、以降では、SP法を y = 7 および T = 50 で適用する。
ITP y|VC| by SP|VC| / N|VC| by BP|VC| / N|VC| by 2-approx|VC| / N

0
3520
0.462
3520
0.462

0.5
3510
0.460
3514
0.461

1
3517
0.461
3516
0.461

2
3510
0.460
3519
0.461
5498
0.721

3
3508
0.460
3515
0.461

5
3511
0.461
3523
0.462

7
3507
0.460
3524
0.462

10
3511
0.461
3522
0.462

表 3.9: 逆温度パラメータ y が異なる場合について、最小 VC に関する SP 法、BP
法と 2-近似アルゴリズムによる推定値の | V C | を比較する。太字の数値は最小 VCにおける最良の結果を表している。

30

11
3514
0.461
3519
0.462

12
3508
0.460
3517
0.641

図 3.4: 木の中の VC を見つけるための割り当て法 [1]。

Round T
|VC| by the SP|VC| / N

5
3511
0.461

10
3512
0.461

20
3519
0.462

50
3508
0.460

100
3516
0.461

200
3516
0.461

表 3.10: LastFM における異なるラウンド数 T での SP 法による | V C |。ノード数
N = 7624。

31

第 4 章 影響力最大化問題における複数の種の探索本章の 4.1 節では、影響力最大化問題（IMP）に関する独立カスケード（IC）モデ
ルや線形閾値（LT）モデルについて紹介する。これらを既知であれば、読み飛ばしても差し支えない。4.2 節では、多くのサンプル数を必要とする従来の SIR モデルに対して、高速 SIR モデルを提案する。4.3 節では、従来の IMP 問題のヒューリス
ティック手法について説明する。ここで SIR とは、Susceptible-Infected-Recovered
モデルを指す [31]。

4.1

IMP とはIMP は、ソーシャルネットワーク上で口コミ情報などの拡散の影響力が最大化されるように、ノードの部分集合である Ns 個の種ノードを見つける最適化問題であり、Ns ≥ 1 は定数である。この問題には、ウィルス性マーケティング [34, 35]、
脳活性化 [36]、コミュニティの情報伝播 [37]、噂のブロック [38]、そして接触ネッ
トワークにおけるグローバルな流行病の拡大を防止するための問題 [17] など、多くの応用分野がある。IMP では、ある種ノード個人から情報伝播をシミュレートするために拡散モデルが用いられる [11]。拡散モデルには以下の独立カスケード（IC）モデルや線形閾値（LT）モデルがある [39]。

4.1.1

独立カスケード（IC）モデル

IC モデルは、情報拡散モデルの一つであり、ノード u, v 間に対して伝染確率 Pu,vを、相互作用の頻度、地理的近接性、または過去の感染履歴などに基づいて割り当てられる。各ノード u は感染すると、次の時間ステップでそのリンク (u, v) に関連付けられた確率 Pu,v に基づいてその隣接ノード u を感染させる能力を持つもの

32とする。独立カスケードモデルのダイナミクスでは、時間ステップ t ごとに、t − 1
時刻で新たに感染したノードの集合 S t−1 に対して、各 v ∈ S t−1 が確率 Pu,v で未活性の隣接ノード ∂u を感染させる [39]。Kempe らは、IC モデルの下で IMP を、

NP 完全の Set Cover 問題の一般的なケースと見なすことができることを示している [11]。また、特に、全てのリンク (u, v) で一定確率 Pu,v = β の時、4.2 節の SIR
は IC モデルの特別例である。
図 4.1、ネットワーク中のすべてのノードに対して、 Pw,v =0.5 であると仮定する。つまり、ノードが活性化すると、50% の確率でその隣接ノードが活性化する。
まず、ノード 8 とノード 9 が最初の活性化ノードであると仮定する。ノード 8 と 9から始まり、IC モデルは Pw,v =0.5 の値に基づいて、それらの隣接ノードを活性化する。図 4.2 から 4.4 は、IC モデルの条件下で情報拡散がどのように進展していく
か示している。以下、より詳しくその動作を説明する。
図 4.1 の Step1 では、ノード 8 とノード 9 は、隣接するノード 5、6、7 を活性化しよ

図 4.1: Step 0、ノード 8 とノード 9 が最初の活性ノードである。
うとする。ノード 5 とノード 7 のみが成功して活性化され、ノード 6 は活性化に失敗したとする。ノード 5 と 7 が活性化された場合、それらの隣接ノードを Pw,v =0.5の確率で続けて活性化を行い、ノード 1 と 6 が活性化に成功したと仮定する。
次に、ノード 6 のすべての隣接ノードが既に活性化しているため、図 4.3 の Step233

図 4.2: Step 1、ノード 1 と 6 が成功して活性化されたと仮定する。
では、ノード 1 の隣接ノードのみを考慮する。IC モデルに従い、ノード 3 とノード

4 は 50% の確率で活性化して、ノード 4 のみが成功的に活性化されたと仮定する。
図 4.4 の Step3 では、最近活性化されたノード 4 の隣接ノードが考慮される。ノード 4 の隣接ノードはどれも活性化されていないと仮定する。このように、ノード

1、4、5、6、7、8、9 が活性化されたときに、ネットワーク内の情報拡散プロセスは
停止する。

34

図 4.3: Step 2、ノード 1 と 6 が活性化された。

図 4.4: Step 3、ノード 4 の隣接ノードはどれも活性化されていないと仮定する。

35

4.1.2線形閾値（LT）モデル

LT モデルでは、任意のノード u ∈ V に対して、受信リンク (u, v) の合計重みが∑1 以下になるように、 u∈∂v b(u, v) ≤ 1 とする。モデルのダイナミクスは以下のよ
うに定義される。各ノード v は、[0,1] の区間で一様ランダムに閾値 θv を選択する。
次に、Ht − 1 は時刻 t − 1 またはそれ以前に活性化されたノードの集合、各非活性∑ノード v は、 ∂v∩Ht − 1 b(u, v) ≥ θv であれば活性化する [39]。ここで、∂v は v の
隣接ノードの集合である。LT モデルにおける IMP は NP 困難である [11]。ネット
ワークが有向グラフであると仮定し、bu,v ̸= bv,u は異なる役割を持つ。簡略化する
ため、 (bu,v ) = 1/kv ，(bv,u ) = 1/ku と仮定し、各ノードのしきい値を 0.5 とする。
ノード 8 とノード 9 が最初の活性化ノードであると仮定する。図 4.5 は、LT モデ
ルの条件下で情報拡散がどのように進展していくかを示している。
このプロセスの最初のステップでは、ノード 5 は 2 つの隣接ノードが活性化して

図 4.5: Step 0、ノード 8 とノード 9 が最初の活性化ノードである。
いるため、ノード 5 に向かう重み b8,5 +b9,5 =1/3+1/3=2/3 である。2/3 は閾値 0.5より大きいため、ノード 5 が活性化になる。
図 4.7 の Step2 では、ノード 6 の 2 つの隣接ノードであるノード 5 とノード 9 が活性化状態であるため、ノード 6 が活性化される。

36

図 4.6: Step 1、ノード 5 が活性化する。
図 4.8 の Step3 では、隣接ノードの重みの合計が閾値 0.5 より高くなるため、ノード 7 とノード 1 が活性化される。ノード 1、5、6、7、8、9 が活性化されると、残りのネットワークのノードはすべて活性化の条件を満たせなくなるため、情報拡散プロセスは停止する。

37

図 4.7: Step 2、ノード 6 が活性化する。

図 4.8: Step 3、ノード 7 と 1 が活性化する。

38

図 4.9: 最終段階

39

4.1.3

LT モデルと IC モデルの違い

IC モデルと LT モデルは、拡散能力や拡散方式などの特徴を一定程度反映している [39]。両モデルにはランダム性が導入されている。LT モデルアルゴリズムは、
情報拡散を開始する前に、ノードにランダムに閾値を選択する。一方、IC モデル
では、ノードが隣接するノードを活性化する確率 Pw,v である。しかしながら、両者には以下のように明らかな違いがある。
線形閾値 (LT) モデル• 受信者主導 (receiver-centered) で、あるノードのすべての隣接ノードを観察し、そのノードの次数と総次数の割合がある閾値以上ならば活性化できるかどうかを決定することを意味する。

• ノードの活性化は、ノードのすべての隣接ノードに依存してる。
• LT モデルで閾値が一旦与えられると、ネットワーク内の情報拡散プロセスも確定する。
独立カスケード (IC) モデル• 送信者主導（sender-centered approach）で、ノードが活性化された後、そのノードは隣接するすべてのノードを活性化しようとする。

• 1 つのノードが独立してそのすべての隣接ノードを活性化する（必ずしもすべてが活性化されるわけではない）。

• 情報伝播のプロセスは、確率的に変化するため、ネットワーク内の情報伝播プ
ロセスは不確定になる。

40

4.2

拡散処理と高速化計算

一般的に SIR 感染モデル [31] は複数のランダム状態の初期値からの伝搬を平均化するために多くの試行が必要である。そこで、計算時間を短縮するために、本節は CI [40] のメッセージ伝搬方程式から着想して、新たな高速 SIR モデルを提案
する。

4.2.1

従来の SIR モデル

一般的に、SIR 感染モデル [31] は、複数の種からの拡散処理を行うために適用され、感染症の流行予測 [41] や、予防・制御策の評価 [42] などに役立つ。このモデ
ルは、Susceptible（感受性保持者）、Infected（感染者）、Recovered（回復者）の3 つの状態を考慮している。感受性保持者は、まだ感染していない人々を指し、感染者はすでに感染している人々を指す。回復者は、病気から回復した人々を指し、彼らは再度感染することができない。SIR モデルは、感染者が感染を広げる速度（感染率 β ）と回復者が感染拡大を止める速度（回復率 γ ）を考慮している。

SIR モデルでは、各ノードが感受性保持者（S）、感染者（I）、および回復者（R）の 3 つ状態に分類される。各時間ステップにおいて、感染拡大プロセスでは、感染しているノードは確率 β で隣接ノードの状態を S から I に変更し、回復確率 γ で自身の状態を I から R に変更する。感受性保持 S は感受性保持 S と感染 I の積に比例して確率 β で感染 I になる。一方、回復率 γ で回復者になる。回復者は再度同じ病気に感染しない免疫を持つものとする。図 4.10 の時間発展を非線形常微分方程式で記述すれば、dS(t)= −βS(t)I(t),dtdI(t)= βS(t)I(t) − γI(t),dtdR(t)= γI(t),
dt

(4.1)
(4.2)
(4.3)

となる。
ここで、S(t) は時間 t における感受性保持者の数、I(t) は感染者の数、R(t) は回復者の数、一定数 N = S(t) + I(t) + R(t) は総人口の数、β は感染率、γ は回復

41率を表す。式（4.1）、（4.2）、（4.3）の和は

d(S(t) + I(t) + R(t)) = 0,
dt

(4.4)

となり、この式は全人口の変化率がゼロであることを示しており、感染症が広がる期間において、人口全体の総和が変化しないことを意味する。感染者が増える
一方で、感受性保持者と回復者が減少するため、これらの変化率の和がゼロになる。この式は、SIR モデルの基本的な性質を表している。
ここでは、確率的 SIR モデルの平均的な振る舞いについて考える [31]。拡散プロ
セスは、各時間ステップで、感染したノードは、例えば確率 β = λ ⟨k⟨k⟩2 ⟩ [43] で、その近隣ノードの状態を S から I に変更し、自身の状態を I から R に回復確率 µ = 1
で変更する。ここで、 ⟨k⟨k⟩2 ⟩ は 2.2.3 節で説明したのパーコレーション値である。通常、複数の種からの拡散を行うために従来の SIR モデルが適用されるが、例え同じ種集合からでも、確率 β の確率的振る舞いのサンプリングの平均化には多数の試行が必要である。つまり、ネットワークのサイズが非常に大きい場合、従来のSIR モデルでは平均化に多くの時間が必要になる。

図 4.10: SIR モデルのフローチャート

4.2.2

高速化 SIR モデル

上記の計算時間を短縮するために、CI [40] のメッセージ伝搬方程式から着想して、以下の方程式を考慮する。

[
PiI (t + 1) = PiS (t) 1 −∏](1 − βPjI (t)) ,

(4.5)

j∈∂i

PiR (t + 1) = PiR (t) + PiI (t),

42

(4.6)

PiS (t + 1) = 1 − PiI (t + 1) − PiR (t + 1).

(4.7)

ここで、PiI (t + 1)、PiR (t + 1)、PiS (t + 1) は、それぞれ時刻 t + 1 におけるノード

i の状態 I、R、S の確率を表す。すでに平均化された確率値 PiI (t)、PiR (t)、PiS (t)は、時間ステップによって更新される。これを高速 SIR モデルと呼ぶ。これらのメッセージ伝搬方程式 (4.5)(4.6)(4.7) はすでに平均化された確率変数に基づいているため、確率的な振る舞いを平均化するために多数のサンプルが不必要となる。

4.2.3

従来の SIR モデル vs 高速 SIR モデル

この項は、従来の SIR モデルと高速 SIR モデルによる計算時間を予備実験として比較する。高速 SIR モデルと従来の SIR モデルは似たような拡散挙動を示す。
図 4.11 においては、パーコレーション閾値 λ ⟨k⟨k⟩2 ⟩ （λ = 1）で、感染率 β = 0.12 の条件下で、種のサイズ Ns が 885（l = 2）、516（l = 3）、407（l = 4）の 3 つのそれぞれに対して調べている。これらの l の値は、異なるサイズ Ns の種を与え、割合は、それぞれ Ns /N = 0.12（l = 2）、0.07（l = 3）、0.05（l = 4）である。ここ∑N∑N
で、S(t) = i=1 PiS (t)/N 、I(t) = i=1 PiI (t)/N 、R(t) = 1 − S(t) − I(t) で定義する。
図 4.11(a)(b)(c) では、I(t) は単調増加してから、単調減少、最終的には 0 に収束する。R(t) は単調増加し、0.4 に収束する。S(t) は単調減少し、0.6 に収束する。円、四角、三角形印の黒い線は従来の SIR モデルの状態 S、I、R の確率を表す。円、四角、三角形印の赤い線は、高速 SIR モデルの状態 S、I、R の確率を表す。種のサイズが異なるにもかかわらず、高速 SIR と従来の SIR の各状態 S、I、R の赤と黒の線はほぼ一致している。さらに、R(t) は (a) で 0.4、(b) で 0.37、(c) で 0.35 に収束し、t > tc （tc ：収束時間で、すべての感染したノードが回復したときに定義される）である。さらに、l が増加するにつれて、tc も徐々に増加する（tc = 5（a）、

tc = 7（b）、tc = 8（c））。I(t) = 0 のため、S(t) + R(t) = 1 である。各状態 S、I、
R の高速 SIR と従来の SIR の赤と黒の線がほぼ一致しているにもかかわらず、高速 SIR は（平均化が必要ないため）サンプル数倍速くなる。
また、収束時間 tc の前（初期の感染拡大期）には、高速 SIR と 従来の SIR の赤色と黒色の線にはわずかに違いがある。図 4.11 の t = 2 から t = 7 までの赤色線と黒色線の差は、従来の SIR モデルのサンプルの中で最も高い R(t) と最も低い R(t)の間に隙間があるためである（表 4.1 参照）。言い換えると、差が現れる理由は、

43

最低値のため従来の SIR モデルで I(t) と S(t) が過小評価されていることである。
最低値と最高値の R(t) の間の差は大きくないが、ネットワークサイズ N = 7624のため、感染ノードの累積数 N × R(t) は十分大きくなる。さらに、表 4.2 には、高速 SIR モデルが従来の SIR モデルの 30 倍速いことが示されており、1000 サンプ
ルは約 30× T-rounds (T = 50) に相当する。速度向上率（AVG-SIR の計算時間/
高速 SIR の計算時間）は 20 から 30 までである。

tlowest R(t)highest R(t)average R(t)variance of R(t)20.11608
0.11608
0.11608030.22258
0.242780.23283
1.5401e-06

40.31269
0.346930.32923
4.1998e-06

50.36791
0.404240.38586
4.5865e-06

60.39178
0.42195
0.407074.2386e-06

70.398210.42799
0.41360
4.2224e-06

表 4.1: 従来の SIR モデルにおいて、拡散時間が 2 から 7 のサンプルにおける、最も低い累積感染数と最も高い累積感染数のギャップを示す。

DiﬀerenceCalculation time (Sec)AVG
Need the averaging of stochastic behavior
602.28630

MPEquations for already average
20.06478

表 4.2: 高速と従来の SIR モデルにおける収束までの差と計算時間について（CPU：i7-11800H、メモリ：16GB）。

44

(a)size of seed=885 at l=2(b)size of seed=516 at l=3(c)size of seed=407 at l=4

図 4.11: 従来の SIR モデルと高速 SIR モデルにおける、三つの状態 S、I、R の割合の時間変化を示す。

45

4.3

従来の IMP に対するヒューリスティック手法

IMP に対する、従来のヒューリスティック手法について説明する。
High Degree
High degree (HD) 法は、次数が高い順に k 個のノードを影響力のある種として選択する [44, 45]。この方法は、最も近い隣接ノード数に関する局所的なトポロジー
情報のみを必要として、シンプルで効率的に種を見つけることができる。

k-coreネットワーク内で密に連結された核として、k-core は少なくとも互いに K 値以上のノードに結合されている部分グラフを指す。

k-core に含めるには、その部分グラフ内で少なくとも自身のノード以外の K 個の他ノードにリンクしている必要があるが、グループ外で他のいくつかのノードに結合しているかは関係ない。
例えば、その部分グラフが、その部分グラフ内の少なくとも他の 2 個のノードに結合しているすべての対象を含んでいる場合、その部分グラフは 2 コアになる。
同様に、その部分グラフがその部分グラフ内の少なくとも 3 個の他のノードにリンクしているすべてのノードを含んでいる場合、その部分グラフは 3 コアになる。

3 コア内のすべてのノードは、3 コアの他のすべてのメンバーへのリンクを少な
くとも 3 個持っている必要がある。そのような対象は必然的に、3 コアの他のすべてのメンバーへのリンクを少なくとも 2 個持っている必要がある。言い換えれば、3 コアは 2 コアのサブセット (2 コアに含まれる) になる。より一般的には、

k-core は、階層的に生成され、0 コアには 1 コアが含まれ、 1 コアには 2 コアが、2 コアには 3 コアが含まれている (以下同様)。K の値 が増加すると、コアサイズ
は小さくなるが、核内の連結度は高まる [46]。
以下の図 4.12 は、単純なネットワークの k-core の分解図を示しており、より濃い灰色で示された 0 コア、1 コア、2 コア、および 3 コアの階層化された集合を示す。図 4.12 の場合、3 コアは、実際には 2 つの別個のグループで構成されていることに注意されたい。
一方、k-shell は k-core の分解方法と同様に描出できる。但し、k-shell は k-core −46

図 4.12: k-core 分解(K-1)-core として求められる。
以下は k-shell 分解の具体的な手順である。

Step0: 時刻 t=0 に次数が K ＝１の葉ノードを再帰的に削除して、削除した部分
は 1-shell になる。

Step1: 毎時刻 t=1,2,3,4... に次数が K ＝ｔ+１より小さいノードを再帰的に削除
して、削除した部分は k-shell になる。

Step2: 全部ノードを削除するまで Step1 を繰り返す。
下の図 4.13 では色分けされた３つの shell に分解される。

図 4.13: k-shell 分解

47

k-core 法を種ノードの選択に適用する際、種ノードはその Shell 数 ks の値によってランク付けされる。その値は k-shell 分解を通じて計算され、葉ノードがなくな
るまで繰り返す。実際、k-shell 分解では、すべてのノードが１の ID をもつどれかの shell に分割される。一般に、周リンクノードと比較して、コアノードはより大きな拡散を伴う傾向がある。したがって、最大の ks を持つコア内のノードを種ノードとして定義する。

48

Local Centrality and Local Structure Centrality

HD 法はシンプルで効率的であるが、大域的なネットワークの性質を無視している。例えば、ハブの近傍が葉ノードである場合、ハブは弱い拡散力となり、効率が低い。一方、媒介中心性（Betweenness）と近接中心性（Closeness）は大域的な情報を考慮するが、計算がやや複雑である。そこで、Local Centrality(LC) は、局
所性と計算にかかる時間とのトレードオフを考慮している [47]。LC は以下のように定義される。

QLC (u) =2∑∑| ∂Ball(w, R) |,(4.8)

w∈∂u k=0

CLC (v) =

∑

Q(u),

(4.9)

u∈∂v

ここで、∂u はノード u の近傍ノード集合を示し、∂Ball(w, R) は図 4.14 に示すよ
うにノード w から R ホップ離れたノードの集合を示す。| | は集合の大きさを表す。
種として、CL (v) の値が大きい順にノード v が選択される。なお、LC は近接中心性と同様に広がりの強さを与えることが知られている [47]。
また、Local Structure Centrality(LSC) は、LC の拡張である [48]。LSC は、調整

図 4.14: A set of vertexes in 2-ホップ from a vertex w in the process of LC.
可能なバランスパラメータ 0 ≤ α ≤ 1 で 2.2.2 節に述べた局所クラスタリング係数49

Cw [5] と LC の線形補間によって以下のように定義される。
QLSC (u) = α

2∑∑| ∂Ball(u, k) | +(1 − α)Cw ′ ,(4.10)

w′ ∈∂Ball(u,2)

k=0

CLSC (v) =

∑

Q(u),

(4.11)u∈∂v

ここで、∂Ball(u, 2) はノード u の 2 番目に近い近傍のノードの集合を表す。また、[48] で述べられている、α = 0.7 と設定する。
Collective Inﬂuence
Collective inﬂuence (CI) は、以下のようにして IMP の最小集合を見つけることを目的としている [40]。まず、非線形メッセージパッシング方程式を考える、





∏

vi→j = ni 1 −(1 − vk→i ) ,(4.12)k∈∂i\j

ここで、∂i\j は i の隣接ノード集合 ∂i のうち j を除いたものである。vi→j が全て 0
ではない時、vi→j = 1 となり i から j に伝搬することを表す。次に、除去ノードをどのように選ぶかに関する n = (n1 , ..., nN ) と除去率 q に依存した上記の式の反複写像における原点の安定性の条件は、式の左リンクの線形近似における Jacobian
]
[
∂vi→j
行列 ∂vk→l の最大固有値によって決定される。つまり、最大固有値が 1 未満の場
合、影響を与えるノード集合 i : ni = 0 を削除することによって、拡散が停止する。
すなわち、最も少ない除去ノード集合は、ネットワークを分断させ、言え変えると、それらは情報拡散に必要不可欠なものとして CI を定める。そのため、貪欲ア
ルゴリズムを使用して固有値を最小化することで、各ノード i に対して CI を導出する [49]。

∑CIR (i) = (ki − 1)

(kj − 1),

(4.13)

j∈∂Ball(i,R)

ここで、R はノード i からホップ数 R までの半径を表している。最も高い CIR (i)が種として選択される。ノード i を削除した後、ネットワーク内の残りのノードi′ ∈ V について、CIR (i′ ) が再計算される。この手法は、ネットワーク全体ではな
く、半径 R のボール内の局所的なトポロジー構造のみを必要とする。

50

第 5 章 IMP への近似手法の提案
本章 5.1 節では、IMP を解決するための提案手法について説明する。5.2 節では、
提案手法と従来手法 [44, 45, 46, 47, 48, 40] の比較結果を示す。5.3 節では、本章のまとめを述べる。

5.1

提案する組み合わせ法

従来のヒューリスティック手法（[44, 45, 46, 47, 48, 40]）などは複数の種を見つけるために適用できるが、拡散の重なり現象を考慮していない。図 5.1 (a) に示されているように、中心的なノードが近くにある場合、高次数法（HD）[44, 45] は複数の種を見つけるのに適していない。なぜなら、その拡散領域が重複するからである。この重複を避けるために、統計物理学的アプローチと l-ホップ被覆に着想を得た近似を考える。

(a)Close case(b)Distant case

図 5.1: (a) 重なり合う状況と、(b) 重なりを避ける状況。
重なりがなく拡散力が大きい複数の種を見つけることは、l-ホップ被覆（l が 1 より大きい）を使用した最小集合被覆拡張をすることができる。また、集合被覆問題
は頂点被覆（VC）問題に帰着することができる [13]。本研究におけるアイデアと51

して、コンピュータ科学の l-ホップ被覆と最小 VC の統計物理アプローチ [14] を、
情報拡散のより高速なシミュレーションを通じて組み合わせる。ここで、l-ホップ
被覆とは、種が l ホップ先のノードに感染することを想定する。l = 1 の特殊な場合として、セット被覆、支配集合、VC 問題は 1-ホップ被覆に相当する。
その組み合わせ方法の概要は以下の通りである。まず、種数 Ns は、各種間の距離
が l ホップ以上である l-ホップ被覆によって決定される。比較のため、Ns は l=1、2、3、4 に対応する固定値とする。次に、l-ホップ被覆を説明する。図 5.2 に示されているように、ノード i を VC の最初の候補として選択する。ノード i とその l-ホップ近傍を削除した後、残りのネットワークから VC の 2 番目の候補として、ノード

j が選択される。その後、上記の手順を、ネットワークにノードが存在しなくなるまで繰り返す。

図 5.2: l-ホップ被覆の概念を説明する図解。
拡張された l-ホップ被覆における最小 VC の詳細は以下の通りである。
ステップ 1 式 (3.3)〜(3.6) を用いて N 個のノードのランダム置換順の T ラウンド
(1)の更新反復後、各ノード i の確率 π̂i を求める。
ステップ 2 Dismation では、最も高い π̂j (1) を持つノード j が種として選択される。

l-ホップ被覆に含まれる ∂Ball(j, l − 1) を考え、選択されたノード j とその52

∂Ball(j, l − 1) がネットワークから削除される。種の数は、N s ← Ns + 1（最初に Ns = 0 と設定）と更新される。
ステップ 3 ステップ 1 と 2 をすべてのノードがネットワークから取り除かれるまで繰り返す。最終的に、複数の種の数は Ns として得られる。

53

5.2

提案手法と従来の手法の比較結果

提案手法で選択された複数の種と、従来の HD、k-core、LC、LSC、CI 法によって選択された複数の種の情報拡散力を表 5.1 中の 8 つのソーシャルネットワークで比較した。なお、提案手法と従来手法は同じ種サイズ Ns の場合で情報拡散力を比較する。CI3 が他の従来手法を上回るため、それをベースラインとして考える。

Data set

|V |

|E|

LastFM
AirTraﬃc
Hamster
Polblogs
Gnutella
GRQC
HepTh
PGP

7624 278060
1226
2408
1788 12476
1222 16714
6299 20776
4158 13422
8638 24806
10680 24316

Diameter D

⟨k⟩
⟨k2 ⟩

Ns at l = 2

l=3

l=4

15
17
14
8
9
17
18
24

0.06
0.07
0.02
0.01
0.06
0.06
0.06
0.06

885
192
116
58
534
544
1115
1508

516
129
53
17
233
378
761
1055

407
78
12
3
147
306
625
795

表 5.1: 8 つのソーシャルネットワークの基本的なトポロジー特徴。
ソーシャルネットワークの 1 つである LastFM の典型的な結果を述べる。図 5.3は、4.2.3 項で定義した累積感染者数の時間発展 R(t) を示す。図 5.3(a) に示される
ように、複数の種ノードが l-ホップ被覆抜きの通常の最小 VC 法によって種ノードを選択した場合の紫の線（正方形印）は、茶色 (ダイヤモンド印) の線（CI2 ）とシアン (五角形印) の線（CI3 ）よりも低い値を示している。これは、複数のホップの被覆を考慮せず、重複を回避できない最小 VC 法は、いくつかの従来法に比べて、複数の種の選択において拡散効果が低いことを示唆している。
一方、図 5.3(b)(c) に示されるように、茶色 (ダイヤモンド印) の線（CI2 ）、シアン色 (五角形印) の線（CI3 ）、オレンジ色 (逆三角形印) の線（LC）、赤色 (十字印)の線（LSC）は、緑色 (円形印) の線（HD）および青色 (三角形印) の線（k-core）
よりも高い。CI、LC、および LSC は、種の最近傍だけでなく、次近傍やその次の近傍なども考慮するため、HD や k-core より拡散力が高いことが指摘されているが、これらの結果はそれと矛盾しない。Ns はそれぞれ、3517、885、407 であり、それらに対応する Ns /N は、それぞれ 0.46、0.12、0.05 である。

54

特に、高速 SIR モデルの場合、紫色 (四角形の印) の線 (提案手法) は、緑 (円形の印) の線 (HD)、青 (三角形の印) い線（k-core）、オレンジ色 (逆三角形の印) の線 (LC)、赤い (十字印) 線 (LSC)、茶色 (ダイヤモンド印) の線 (CI2 )、およびシアン (五角形の印) の線 (CI3 ) より最も高いことがわかる。図 5.1(b) に示されているように、提案手法で選ばれた種は互いに離れているため、種同士の影響範囲が重複しないことによって、高い拡散力を持つという結果を得たと考えられる。
さらに、収束時間 tc 以降、図 5.3(b) の紫色 (正方形の印) の線と他の線の差は、大きくなっている。一方、種数が少なくなるほど、1 つの種あたりの拡散力は大きくなる。ここで、tc の値は 10 以上である。l が増加するにつれて、tc も増加する
が、種数は減少する。これらの結果に対する具体的な原因は下の図 5.4 を用いて議
論する。

55

(a)size of seed=3517 at l = 1(b)size of seed=885 at l = 2(c)size of seed=407 at l = 4

図 5.3: LastFM の高速 SIR モデルにおける累積感染数 R(t) の時間発展を示す図。
λ = 2 で、l = 1、2、4 の場合を比較している。

56

図 5.4 は、2-ホップまたは 4-ホップ被覆で選んだ２つの種 i, j のホップ数距離 di,jの分布を示している。2 本の紫色の線のピークが他色の線のピークよりも右にある
ため、提案手法で選択された種は、従来手法で選択された種よりもお互いにより遠くに位置していることを意味する。2 つの種間のより大きな距離は拡散の重なりを減らすため、当研究で採用した手法が従来の手法より効果的であると言える。また、塗りつぶされた正方形印で示される紫色の線のピーク（距離 d = 6）は、正方形印で示される紫色の線のピーク（距離 d = 5）よりも右にある。これは、l（ホップ数）が増加するにつれて、種間の距離が増加することを示している。但し、表5.2 でも後述するように、大きな l には限界があることに注意する必要がある。

図 5.4: 各種のペア (i, j) 間の距離 di,j の分布を 2-または 4-ホップ被覆（l = 2, 4）。
また、異なる拡散率 β = λ ⟨k⟨k⟩2 ⟩ (λ=2、4、6、8) について、提案手法によるが複数の種の拡散力を調べた。なお、感染率がパーコレーション閾値 β = ⟨k⟨k⟩2 ⟩ [43] を上回ることは、現実的に妥当である [50]。なぜなら、感染率がパーコレーション閾値

β = ⟨k⟨k⟩2 ⟩ [43] を上回る時のみ、感染は持続的に行われるが、そうでないと、すぐに停止してしまう。図 5.5 に示されているように、横軸は感染パラメータ λ を示して
おり、2 から 10 の範囲（β は 0.12 から 0.6 の範囲）になっている。なお、λ=2 の場合は図 5.3 に対応する。縦軸の R(tc ) は、収束時間 tc での累積感染数を示している。
図 5.5(a) においては、拡散の重なり現象のために（l=1 は多ホップ被覆を考慮して57

いない）、紫色の四角い印の線が最高ではない。l > 1 の場合、紫の四角い印の線（提案手法）は他の手法より常に高くなる。しかし、図 5.5(b)(c) において、λ の値が増加するにつれて、提案手法（紫色の正方形の線）と他の方法との差が徐々に小さくなっていくことが分かる。というのは、感染率が増加すると、種がより多くのノードを感染させるためである。
さらに、表 5.2 から、提案手法によって選ばれた 1 つの種あたりの情報拡散力(N × R(tc )/Ns ) が、従来手法によって選ばれたものよりも大きいことが分かる（l値ごとに各最良の性能は、太字で強調されている）。特に、被覆距離 l が増加する
につれて、提案手法で選択された種ごとの拡散力が大きくなる。したがって、より大きな被覆距離 l で選択された種は、l が増加するにつれてより良い拡散力を持
つが、l はネットワークの直径 D − 1 よりも小さい範囲内に制限されている。ここで、D は、ノード間の最短経路の最大距離と定義されるネットワークの直径である。l が D − 1 を超えると、最初の種が選択された後にすべてのノードが削除されるので、複数の種ではなくなる。

l-ホップ# of seed
Our methodHD
k-core
LC
LSC
C I2
C I3

1
3517
1.322
1.216
1.197
1.197
1.210
1.382
1.389

N × R(tc )/Ns in AVG-SIR
2
885
3.562
2.853
2.671
2.999
3.000
3.011
2.989

4
407
6.579
5.484
5.213
5.702
5.713
5.559
5.683

1
3517
1.341
1.242
1.217
1.199
1.221
1.411
1.419

N × R(tc )/Ns in 高速 SIR
2
885
3.601
2.879
2.748
3.008
3.010
3.007
3.028

4
407
6.622
5.685
5.580
5.770
5.785
5.782
5.808

表 5.2: 提案手法と従来の 6 つの手法による従来の SIR モデルと高速 SIR モデルで選択された各種ノードの感染力。N × R(tc )/Ns は、種ノードあたりの感染力を示し、R(tc ) は収束時間 tc での累積感染を示す。

58

(a)size of seed=3517 at l = 1(b)size of seed=885 at l = 2(c)size of seed=407 at l = 4

図 5.5: LastFM の高速 SIR モデルにおいて、収束時間 tc における累積感染数を、
感染パラメータ λ を 2 から 10 まで変化させた場合の図。

59

残りの 7 つの現実的なネットワークの結果は付録に表示されている。

60

5.3

本章のまとめ重なりがなく拡散力のある複数の種ノードを効果的に見つけるために、私たちは IMP 問題を近似的に解決する新しい方法を提案した。その鍵となるアイデアは、コンピューター科学の最小 VC と l-ホップ被覆を統計物理学的アプローチに組み合わせ、拡散の重なりを避けることである。また、従来の SIR モデルよりも多くのサンプルを必要としない高速 SIR モデルを提案している。そのため、サンプル数/T ラウンド数 T に比例して通常の SIR モデルよりも高速となる。よって、このより速い SIR モデルを使用して、拡散プロセスを迅速にシミュレーションすることを可能にしている。蓄積された感染の時間発展の結果から、提案手法は、サイズが異なる社会ネットワークに対して、他の従来手法よりも優れた性能を発揮できると言える。

61

第 6 章 頑健性かつ効率的なネット
ワークを生成するアタッチメ
ントモデルの族
本章 6.1 節では、広く知られた Scale-Free トポロジー構造を説明する。6.2 節では、提案する逆優先的選択（Inverse Preferential Attachment）と従来の玉ねぎ状
ネットワーク（Onion-like Network）の関係を説明する。6.3 節では、k −β アタッ
チメントを用いた改良された p-モデルを説明する。6.4 節は、IPA モデル上の IMPのシミュレーション結果を示す。6.5 節では、本章のまとめである。
ところで、以下、リンクの結合によって成長するネットワーク生成に共通している。すなわち、各時間ステップで、新しいノードが一つ追加され、自己ループと多重リンクを禁止しながら、BA モデル [51] と同様に既存の m 個ノードに結合
する。

6.1

Scale-Free 性と優先的選択 BA モデル

6.1.1

Scale-Free(SF) 性

SF ネットワークの特徴の１つは、平均次数よりもはるかに高い次数を持つノードが存在することである。最も高い次数を持つノードは通常、「ハブ（hub）」と呼
ばれ、ネットワーク内で特別な役割を果たすと考えられている。SF 性は、ネット
ワークの攻撃に対処する能力と密接に関係している。もしノード攻撃がランダムに発生し、多数のノードが小さな次数を持っている場合、Hub ノードはほとんど影響を受けない。選択的に主要な Hub ノードを取り除くと、ネットワークは孤立した複数の部分グラフに分かれる。そのため、Hub ノードは SF ネットワークの利点であると同時に、欠点である。Cohen[52, 53] らや Callaway[54] らは、パーコレー

62

ション理論を用いてこれらの特性を解析している。Cohen[52] は、N → ∞ の SF
ネットワークの一様ランダム故障に相当する臨界浸透閾値が pc → 0 であることを証明した。これは、平均次数が k̄ の Erdős–Rényi グラフと対照的で、Erdős–Rényi
グラフでは、臨界値は pc = 1/k̄ となる。

SF ネットワークのもう一つの重要な特徴は、ノードの次数が増加するにつれて減少するクラスタ係数分布である。この分布もべき乗則に従う [55]。これは、次数が低いノードが密な部分グラフに属しており、これらの部分グラフが Hub ノード
を介して相互に結合されていることを示している。
一方で、異なる生成メカニズムに基づく SF ネットワークの詳細な特性は異なる。
例えば、優先的選択によって生成されたネットワークでは大部分のノードをランダムに削除しても、ネットワーク全体の連結性にはあまり影響を与えない。これは、この種のトポロジーがセキュリティの向上に役立つということを示しているが、いくつかのターゲット攻撃はすぐにその連結性を破壊することができる。
一方、ほとんどの SF ネットワークにおいて、ノード間の平均距離（小世界ネット
ワークなど）は、規則的な格子グラフに比べて非常に小さい。Cohen と Havlin[56]は、2 < γ < 3 のべき指数の SF ネットワークでは、非常に小さな半径 d ∼ ln(ln(N ))となることを示した。実際には、N が大きい SF ネットワークの半径は、ほぼ定数と見なすことができる。多くの現実世界のネットワークは、SF ネットワークであると考えられている。例えば、インターネットや World Wide Web、金融ネット
ワーク [57, 58]、Semantic networks[59] などである。
図 6.1 に SF ネットワークを可視化したものと、次数分布を示す。図 6.1A の可視化から SF ネットワークは、リンクが集中しているハブと低次数ノードがあることが分かる。また図 6.1B から、次数分布が両対数プロットで直線的になっていることから、それがべき乗則に従うことが分かる。

6.1.2

優先的選択（Preferential Attachment）と BA モデル

最も知られている SF ネットワークの生成モデルは、Barabási と Albert（1999）[51] による利己的な Rich get richer 原理によるモデルで、入次数に比例する非均一63図 6.1: 航空網データ AirTraﬃc を (A) 可視化したものと (B) 次数分布. ノードは次数が高いほど大きく表示されている。また次数分布は両対数スケールになっている。
な確率に基づいて生成される。このモデルは、1965 年に Price が累積優位と名付けた [60] が、現在の名前（BA モデル）は、Barabási によって再発見された後に注目を集めたことによる。例えば、より多くの入次数を持つウェブページは、一般的なウェブページよりも多くのリンクを集める傾向がある。

BA モデルにおいて、SF 性をもつ重要な要因は、優先的選択とネットワーク成長の２つである。優先的選択により新ノードから次数が大きい既存ノードを繋げ
ると、時間が経つにつれて古株の次数がより大きくなる。成長と優先的選択による、ノード数の増大に伴って，次数が大きいノードはより大きくなり、巨大なリンク数を持って、Hub と呼ばれる結合が集中したノードが発生する。以下は BA モ
デルによるネットワーク構築のアルゴリズムである。
図 6.2 は、BA モデルにおいて、緑ノードは追加するノード、青ノードの次数は大きく、結合されやすい。ここで、ノード i の選択確率は以下で定義される [51]。

pi = ∑kin∈N knStep0: 時刻 t=0 に初期ネットワークを構築する。Step1 で追加されるリンク数 m
64

から、初期ネットワークは少なくとも m 以上のノードを持つ。そこで、本研究では m+1 の完全グラフを初期ネットワークとする。

Step1: 毎時刻 t=1,2,3,4... 新しいノードから既存ノードに PA に従ってｍ本リンクを追加する。既存ノード i の確率選択は式（2.6）に従う。但し、毎時刻で各ノードの多重リンクは禁止され、式 (2.6) の確率選択が再試行される。

Step2: 構築したいノード数 N に達するまで Step1 を繰り返す。

図 6.2: BA モデルを生成の見取り図

BA モデルによって生成されるネットワークの顕著な特徴は、べき乗次数分布を持つことである。以下、その理論解析 [51] を手短かに述べる。p(k, ti , t) を、時刻

ti にノード i が追加され、時刻 t で次数がちょうど k になる確率と定義する。BA
ネットワークでは、新しいノードがネットワークに追加されるとき、ノード i の次数が 1 増加する確率は k/2t であり、そうでなければノードの次数は変化しない。
このことから、以下のマスター方程式と呼ばれる再帰式が得られる:

p(k, ti , t + 1) =kk−1p(k − 1, ti , t) + (1 − )p(k, ti , t).
2t
2t

(6.1)

BA ネットワークの次数分布は次のようになる：
1∑
p(k, ti , t))t→∞ ttp(k) = lim (

i

65

(6.2)

以下の再帰式：

k−1

p(k − 1), k ≥ m + 1,
p(k) = k + 22, k = m,m+2
により、BA の SF ネットワークの次数分布が得られる。

p(k) =

2m(m + 1)∼ k −3k(k + 1)(k + 2)

これは、BA ネットワークが 3 のべき指数を持つことを示している。

66

(6.3)

6.2

逆優先的選択（Inverse Preferential Attachment）と玉ねぎ状ネットワーク（Onion-like Network）

残念ながら、SF ネットワークは、巨大な次数を持つハブのノードへの意図的な攻撃に対して非常に脆弱である [61]。一方で、ハブを経由するなどして、任意の 2つのノード間には効率的な短い経路が存在しやすい。効率的な経路と極端な脆弱性の組み合わせは、二重の刃の剣となる。したがって、私たちは、成長するネッ
トワークにおいて、従来のものよりも強い頑健性と高いネットワーク通信効率の両方の重要な特性を備えた、より良いアタッチメント法を見つけることを目指す[6, 61, 51]。
過去数十年間、成長するネットワークにおいて多様なアタッチメント法が提案されてきた。例えば、ランダムアタッチメントと優先的アタッチメントを混合した
アタッチメント法が議論されてきた [62, 63]。他の混合アタッチメントとしては、優先的アタッチメントと調整可能なクラスタリングの組み合わせも研究されている [64]。成長ネットワーク（GN:Growing Network）モデルにおいて [65, 66, 67]、
次数が k であるノードが、k υ に比例する確率でリンク先として選択される。その際、υ の値によって、υ = 0、0 < υ < 1、υ = 1、υ > 1 のそれぞれに対して、指数関数、指数カットオフを持つべき乗則、SF となるべき乗則、排他的な星状ネッ
トワークなど、次数分布が連続的に変化する。また、複写モデルでは、ランダムに選択されたノードの最近傍に結合する複製またはコピーによって、近似解析で導かれたべき乗則分布が生成される [68, 69]。しかしながら、次数 k を持つノードが選択される確率が k −β に比例する逆優先結合は、β = 1 の特殊な場合を除いてはほとんど考慮されていない [70, 71]。 特に、次数分布の解析を超えて、逆優先ア
タッチメントについて、ネットワーク通信効率と頑健性は、ほとんど議論されていない。
一方、正の次数相関を持つ玉ねぎ状構造が、与えられた次数分布下で次数順の意図的攻撃に対して最適な頑健性を持つことがわかっている [72, 25]。このような構造は、同じ次数のノードが、中心から周リンクに向かって次数の減少する同心円状に配置される場合に視覚的に表現される。次数相関を大きくするいくつかの
リワイヤリング法が提案されている [72, 73] が、これらの方法は既存のリンクを破67

棄するため、現実のネットワークへの適用が困難である。一方、ショートカットの追加と協調的部分コピーを適用する逐次的な成長法 [74] や仲介を利用する方法も提案されている [3, 4]。それらで生成された玉ねぎ状ネットワークにおいては、
頑健性と通信効率の両方が共存することが数値的に示されている [3]。しかしながら、ランダム、仲介、逆優先のどれが玉ねぎ状ネットワークの出現にとってに主要因をなるがは十分理解されていない。

6.2.1

玉ねぎ状ネットワーク（Onion-like Network）

近年、数値シミュレーションと理論解析により、玉ねぎ状ネットワークが発見された [4]。このようなネットワークは次数の大きい順に中心から周リンクに同心
円上にノードを配置すると、正の次数相関を強くする同程度の次数を持つノードが結合することで玉葱状に可視化されることから玉ねぎ状と呼ばれる。以下、玉ねぎ状ネットワークによるネットワーク構築のアルゴリズムを述べ [4]、図 6.3 はその Step1,Step2 を説明するものである。

図 6.3: 玉ねぎ状ネットワークの生成

Step0: 時刻 t=0 に初期ネットワークを構築する。Step1 で追加されるリンクの数m から、初期ネットワークは少なくとも m 以上のノードを持つ。そこで、本研究では m+1 の完全グラフを初期ネットワークとする。

68

Step1: 毎時刻 t=1,2,3,4... にｍ本リンクをもつ新しいノード 1 個を既存ネット
ワークに追加する。

Step2: 追加する時、既存ノードをランダムに一個選んで、新しいノードと選んだノードを結合する。更に、ランダム選択ノードから一定な仲介数 µ を経た(µ + 1) ホップ先の最小のノードと繋げる。毎時刻で各ノードの多重リンクは禁止される。

Step3: ノード数 N に達するまで Step1, Step2 を m2 回繰り返す。
図 6.4(a)(b) において、BA モデルによる SF ネットワークと上記の Step 1,2,3 による玉ねぎ状ネットワークの次数分布を比較する。図 6.4(a) の両対数の直線部分
から、スケールフリーネットワークはべき乗次数分布に従う。一方、図 6.4(b) の
縦軸のみ片対数の直線部分から、上記で生成した玉ねぎ状ネットワークは指数分
布に従うことがわかる 。

スケールフリーネットワーク

玉ねぎ状ネットワーク

図 6.4: SF ネットワークと玉ねぎ状ネットワーク次数分布の比較

6.2.2

玉ねぎ状ネットワークにおける最小次数結合の要因

我々は、以下のように強固な玉ねぎ状ネットワークを生成するために、ノードのランダム選択と最小次数選択に焦点を当てる。一方、正の相関として知られる次数相関を持つ玉ねぎ状ネットワークを生成するために、ランダム選択と intermediation（MED）選択のペアに基づく逐次的な成長法が提案されている [3, 4]。そこで、最小次数選択とランダム選択のいずれかで、MED モデルのタイプを MED-kmin ま69

たは MED-rand と呼ぶ [4]。

MED-kmin
各 MED-kmin ペアにおいて、片方のリンクの結合先は一様ランダムに選択され、もう一方のリンクの結合先は、ランダムに選ばれたペアのノードから、仲介ホップ
数 µ で最小次数のノードが選択される。µ ホップの仲介とは、µ + 1 番目の隣に結合することを指す。また、数値シミュレーションにより、µ ≥ 3, 4 ホップのノードへの反復的な結合により、比較的長いループが形成され、頑健性が向上することが示されている [2]。もしネットワークにループが少ない場合、ノードを取り除くことで木構造になってしまう可能性があるため、ノードに対する攻撃が行われると、
ネットワークは容易に分断されてしまう。この現象は、Dismatling と Decycling 問
題の同等性によって支持されている [4]。

MED-rand
MED-rand の場合は、最小次数のノードの代わりに、ランダムに選択されたペアのノードから µ + 1 番目の近傍にあるノードが一様ランダムに選択される。古い
ノードは大きな次数を持つ傾向があるから、ランダムアタッチメントで、正の次数相関を持つ大きな次数のノード同士を結びつける可能性が高い。一方、最小次数のノードへのアタッチメントは、小さな次数のノード間での正の次数相関の向上に貢献する。なぜなら、その第二のアタッチメントによって、µ + 1 近傍の最小次数ノードとネットワーク全体で最小次数 m の新しいノードとの結合が確立され、小さな次数のノード間の正の次数相関関係を向上させることになる。但し、第二のアタッチメントの効果が弱いため、MED-rand では、MED-kmin のような玉ね
ぎ状のネットワークは形成されない [4]。
本研究では、k −β アタッチメント (0 < β < ∞) によって、β = 0 でランダムア
タッチメント、β → ∞ で最小次数アタッチメントの補間として、玉ねぎ状ネット
ワークが生じることを示す [Liao1]。ここで、関連する議論が第 6 章の MED に至るまで、距離の影響はアタッチメントに含まれていない（MED-kmin の距離効果を調整するパラメーター µ を含む修正については、第 6 章で議論されることに注意されたい）。
まず、k −β -アタッチメントによる次数分布を導出する。後述するが、β が大きくなるにつれて最大次数が制限され、β → ∞ での最小次数アタッチメントでは後述
する特殊なチェーン構造が得られることがわかる。この構造は、長距離経路が存70在するため、ネットワークの効率が低下する原因となる。次に、次数相関 r、連結の頑健性指標 R、ネットワークの通信効率 E について数値的に調査し、どの β の値が k −β アタッチメントによって効率的で堅牢な玉ねぎ状ネットワークを生成するのに貢献するかを明らかにする。

k −β アタッチメントとして、ランダムなアタッチメントと最小次数アタッチメンk−βト（β = 0, ∞ で）の間のパラメーター的な補間として、既存ノード i を確率 ∑ i −βで選び、0 < β < ∞ で k

−β

j kj

アタッチメントを考慮する。各時刻で新しいノードから m 本のリンクを追加する。一般的に、次数 ki の確率関数 f (ki ) によって選択されたノード i に対して非線形なアタッチメントを行った場合、次数分布 P (k) は[75] の式 (9) から次のように導かれる。

P (k)

=

k
∏
⟨f ⟩
m × f (κ − 1),⟨f ⟩ + m × f (Kmin ) κ=K +1 ⟨f ⟩ + m × f (κ)

(6.4)

min

⟨f ⟩

def

=

K
max
∑

f (k) × P (k),(6.5)

k=Kmin

ここで、Kmin と Kmax は最小と最大次数である。f (k) = k −β の場合、m = Kmin ≤k ≤ Kmax < ∞ として、以下のように書き換えられる。
[
P (k) = exp log
[
= exp

{

k
∏
⟨f ⟩
m × f (κ − 1)⟨f ⟩ + m × f (Kmin ) κ=K +1 ⟨f ⟩ + m × f (κ)

}]
,

(6.6)

]
}
log(m) + log((κ − 1)−β ) − log(⟨f ⟩ + m × κ−β ) + C , (6.7)
min

k
∑

{

κ=Kmin +1⟨f ⟩は定数である。式 (6.7) の右リンクでは、右リンクの
ここで、C = log ⟨f ⟩+m×f(Kmin )
−β
定数項 C や log(m) と log(⟨f ⟩+m×Kmin) > log(⟨f ⟩+m×κ−β )、 Kmin +1 ≤ κ ≤ kは支配的ではないため、[∫]
exp−βlog(κ − 1)dκ = exp [−β(k − 1)log(k − 1) − 1] ∼ e−βklogkのように、定数因子を無視して近似される。

71

(6.8)

図 6.5 と 6.6 は、β = 1, 4, 10 および m = 2, 4 の場合について、log(N × P (k)) と

klogk の最小二乗法による良好なフィッティングを示している。図 6.5、6.6 では、より大きな β に対して最大次数が減少し、β → ∞ の場合には 2m によって上限が設定される。また、k ≥ 1 において、k と klogk の間に単調増加の関係がある。
次に、β → ∞ の場合、最小次数アタッチメントとして特別なチェーン構造が生じることを明らかにする [Liao1]。時刻 t のアタッチメントでは、新しいノードは時刻

t−1、t−2、...、t−(m−1) に追加された既存のノードに結合し、その次数は最小の
m, ..., 2m − 2 である。各時刻 t において、新たなノードは t − 1, t − 2, ..., t − (m − 1)に追加された既存ノードに最小次数優先で繋げるため、次数は最小値 m, ..., 2m − 2になる。多重リンクが禁止されているため、次数は各時刻で一つずつしか増加せず、合計 m 個のリンクのうち、2m − 2 より小さい次数で 2m − 1 になる。図 6.7 は、議論を簡単にするために、次数が 2m − 1 の最も古いノードを選択するという特殊なケースを示している。次数が 2m であるノードは、2m − 1 の次数を持つノードが複数存在するため、もうリンクを取得しない。上記の議論と図 6.7 から、これを確認する。時刻 t における次数の合計 Mt について、以下の式が成り立つ [Liao1]。

Mt = 2M0 + 2mt,

(6.9)

= 2m(N0 + t − ∆t) + (2m − 1)(∆t − m)((m + 1) + (2m − 2 + 1))(m − 1)
+
+ m,
2

(6.10)(6.11)

ここで、M0 と N0 は初期（t = 0）ネットワークにおけるリンク数とノード数を示す。∆t は、現在の時点と次数が 2m 未満の最も古いノードの挿入時刻の差を表している。したがって、∆t は時間の長さではなく、ノードの数を表す。式 6.11 の右
リンクにおいて、2m(N0 + t − ∆t) と (2m − 1)(∆t − m) はそれぞれ、次数が 2m と

2m − 1 のノードの総和を表している。3 番目の項 ((m+1)+(2m−2+1))(m−1)
は、m + 12
から 2m − 2 + 1 までの等差数列の和を表している。最後の項は新しいノードの次数 m である。式 (6.11) を解くと、∆t = 2mN0 − 2M0 −m(m − 1).
2

(6.12)

初期完全グラフの場合、N0 = m + 1、M0 = m(m+1)
を式 6.12 に代入すると、以下2の定数項が得られる。

72

(a) m = 2, β = 1(b) m = 2, β = 4(c) m = 2, β = 10

図 6.5: 分布の裾野を緑の線に e−βklogk で推定。紫の点と緑の線は、k −β アタッチ
メントによって成長するネットワークの次数分布とその推定値を表している。時間ステップごとの追加リンク数は m = 2 である。

73

(a) m = 4, β = 1(b) m = 4, β = 4(c) m = 4, β = 10

図 6.6: 分布の裾野を緑の線に e−βklogk で推定。紫の点と緑の線は、k −β アタッチ
メントによって成長するネットワークの次数分布とその推定値を表している。時間ステップごとの追加リンク数は m = 2 である。

74

∆t =

m(m + 3)> m.
2

(6.13)

式 (6.13) からわかるように、2m − 1 の次数を持つノードの数は ∆t − (m − 1) > 1となる。したがって、2m − 1 の次数を持つ複数のノードが存在することがわかる。
最小次数アタッチメントによって生成されるネットワークは、長時間経過後に多くの t − 1 − ∆t ノードが次数 2m を持つため、ほとんど正則グラフでと言える。さらに、このネットワークが、∆t の間隔を持つチェーン構造であることを強調する。
チェーン構造の場合、最長の最短経路の長さ（ネットワークの直径）は、N/∆t と推定される。表 6.1 は、実測値が推定値 N/∆t に非常に近いことを示している。わずかな違いは、図 6.7 の特別な場合の推定において最も古いノードではなく、測定においては次数 2m − 1 のノードがランダムに選択されることに起因すると考えられる。0 < β < ∞ に対して、β が大きくなるほど長さが長くなる。β=0 の場合はランダムアタッチメントの場合である。

m2
4Practical
1001
365

Estimated N/∆t
1000
357

∆t
5
14

表 6.1: N = 5000 個のノードを持つ初期完全グラフから、m = 2, 4 の場合に生成された、β → ∞ の最小次数アタッチメントによる直径の推定値 N/∆t と実測値。

k −β アタッチメントによって、効率的かつ頑健な玉ねぎ状ネットワークを生成するために、どのような β の値が貢献しているか、次数相関 r[76, 77]、頑健性指標

R[72]、および通信効率 E[26] を調べる。
図 6.8（a）と図 6.9（a）は、k −β アタッチメントによる成長ネットワークにおけるサイズ N に対する β = 0, 1, 10, 50, 100、および β → ∞ の次数相関 r を示している。赤色のダイヤモンド印の線 (β → ∞) は、紫の十字印の線 (β = 0)、緑の四角
印の線 (β = 1)、シアンの丸印の線 (β = 10)、黒の三角印の線 (β = 50)、オレンジの逆三角印の線 (β = 100) よりもより強い次数相関 r を示している。したがって、より大きな β の場合、より高い次数相関 r が得られる。同じ色の線や印を比較すると、m = 4 の図 6.9 (a) の次数相関 r は、m = 2 の図 6.8 (a) よりも高くなって75

いる。ここでは、図 6.8(b) および図 6.9(b) に示されているように、同じ色の線または印で比較すると、m = 2 の図 6.8(b) よりも、m = 4 の図 6.9(b) の方が頑健性
指標 R が高いことがわかる。さらに、図 6.8(a) においては、次数相関 r の線は β
を 0 から ∞ に変化させるにつれて単調に増加する。一方、図 6.8(b) においては、
次数相関 r の線は β を 0 から 10 に変化させるにつれて増加し、10 から 50 に変化
させるにつれて減少し、50 から ∞ に変化させるにつれて再び増加する。また、図6.8 (b) と 図 6.9 (b) において、頑健性指標 R は、β が 0 から 10 に変化するにつれて増加し、10 から 50 に変化するにつれて減少し、50 から 100 に変化するにつれて再び増加する。β が 100 を超えると、頑健性指標 R は一定値に近づく。図 6.8(c) と図 6.9(c) において、通信効率 E は β を 0 から ∞ に変化させるにつれて単調に減少している。次数相関 r と頑健性指標 R がこのように変化する理由は、正確にはわ
かっていない。但し、以前に議論されたように、チェーン構造がそれらに影響を与える可能性がある。特に、m = 4 の場合の図 6.9(a)(b) における β → ∞ の赤い線
は、比較的高い次数相関 (r > 0.2) と頑健性 (R > 0.3) を持つ、玉ねぎ状のネットワークとして振る舞うことを示している。強すぎる次数相関は、R の値を減少させ頑健性を弱める傾向がある [25]。r と R が玉ねぎ状のネットワークであるための正確な条件は存在しないため、r > 0.2 および R > 0.3 として考えている。なぜなら、同じ N および m に対して BA モデルは玉ねぎ状ネットワークではなく、r ≈ 0
および R < 0.23 であるからである [3, 4]。図 6.8 と 6.9 (c) から、β が ∞ に近づく
につれて、効率 E の値（赤い線）が、β = 0、1、10、50、100（紫、緑、シアン、黒、オレンジの線）よりも低くなっている。低い効率の原因は、図 6.7 や表 6.1 で述べたように、チェーン構造に起因すると考えられる。

76

図 6.7: β → ∞ の最小次数アタッチメントによるリンクの結合先。黒い線は、新しいノードから既存の m ノードへの最小次数アタッチメントによるリンクの結合を示している。右から左に 3 つの部分がある。右側の最初の部分では、m − 1 個の既存のノードのうち次数が最小の m, m + 1, ..., 2m − 2 に新しいノードが結合される。最小次数アタッチメントのためである。2 番目の部分（中央）では、残りの 1 つのリンクが次数 2m − 1 のノードに結合される。∆t 個の次数が 2m 未満のノードが存在するため、次数が 2m − 1 の最も古いノードの追加時間は t − ∆t となる。 t − 1 − ∆t 個のノードのうち、第 3 部分（左側）には、次数が 2m のノードが t − 1 − ∆t 個存在する。これらのノードの追加順序と、時間 t におけるノードの次数の関係は、下から 2 行目と 3 行目に示されている。

77

(a) Assortativity(b) Robustness(c) Eﬃciency

図 6.8: k −β アタッチメントによって生成されたネットワークにおけるノードサイ
ズ N に対する指標：r、R、E 。m=2 の場合で、リンク/時間ステップ。紫色 (十字印)、緑色 (正方形印)、シアン (丸印)、黒 (三角形印)、オレンジ (逆三角形印) の線
は、それぞれ β = 0、1、10、50、および 100 に対応する。

78

(a) Assortativity(b) Robustness(c) Eﬃciency

図 6.9: k −β アタッチメントによって生成されたネットワークにおけるノードサイ
ズ N に対する指標：r、R、E 。m=2 の場合で、リンク/時間ステップ。紫色 (十字印)、緑色 (正方形印)、シアン (丸印)、黒 (三角形印)、オレンジ (逆三角形印) の線
は、それぞれ β = 0、1、10、50、および 100 に対応する。

79

6.2.3

少量のランダムアタッチメントの必要性と効率的な経路

ランダムと k −β アタッチメントの混合アタッチメントにおいて、平均経路長がO(logN ) となり、ネットワークの通信効率 E が向上すること調べる。6.2.2 項で述
べた、β = 100 での実測と、m = 2（m = 4）に対する推定によって、725.5 と 1000
（m=4 では 365 と 103）と、似たような値が得られ、β が十分大きい場合、チェーン構造に近づくため、直径は O(N ) になる。以下の混合アタッチメントでは、新しいノードが各時刻で追加されるが、リンクの結合先は、確率 p でランダムアタッチ
メントで選択され、確率 1 − p で k −β アタッチメントで選択される。但し、β = 0の場合は純粋なランダムアタッチメントである。
図 6.10 において、緑色（四角形印）、茶色（五角形印）、青緑色（丸印）の線（β = 1, 4, 10）は、比率 p が大きくなるにつれて効率が増加する傾向があることを示している。黒（三角形印）、オレンジ（逆三角形印）、赤（ダイヤモンド印）の線（β = 50, 100、と β → ∞）は、横軸に対して劇的に効率が向上することを示していることに注目する。この現象は、鎖状構造が現れることに対応している。同
じ色の線や印を比較すると、図 6.10(b) の m = 4 の場合、図 6.10(a) の m = 2 の場合よりも、玉ねぎ状ネットワークの形成によりより多くのリンクを使用しているため、効率が高くなっている。最短経路の平均長は算術平均と調和平均の関係
で ⟨L⟩ ≈ 1/E で与えられる。例えば、効率 E=0.1、0.2、0.25 は、それぞれ平均経
路長が 10、5、4 ホップに対応する。通信効率 E が低くなるほど、平均経路長 ⟨L⟩が増加する傾向がある。図 6.11(a)、(c) または (b)、(d) において、赤色（星印）、紫色（十字印）、緑色（正方形印）、シアン色（丸印）、オレンジ色（三角印）、黒色（逆三角印）、青色（菱形印）の各線が、p = 0（上部）から p=0.001、0.0025、

0.005、0.05、0.25、および 0.5（下部）に増加するにつれて平均経路長 ⟨L⟩ が減少することが示されている。特に、純粋な k −∞ アタッチメントの場合、p = 0 に対して急速に増加する (赤色の) 曲線が得られるため、6.2.2 項で言及したようなチェーン構造のため、これらの結果は logN に比例しない。しかしながら、平均経路長がO(N ) と O(logN ) の間で連続的に遷移するため、正確な臨界値 pc は不明である。
図 6.11 (c) (d) で示されるように、O(logN ) の直線状のものよりも長い平均経路長を示すものがあるので、pc は 0.0025 から 0.005 の間にあると推定される。また、同じ色の線や印と比較して、図 6.11 (d) の m = 4 の場合の平均経路長は、より多くの追加リンクを使用するため、図 6.11 (c) の m = 2 の場合よりも短くなっている。β = ∞ だけでなく、他の値（β = 100）でも、図 6.11 の類似した結果が得ら

80

(a) m = 2(b) m = 4

図 6.10: ランダムと k −β アタッチメントの混合アタッチメントによるネットワー
クにおける、ノードサイズ N = 5000 で m = 2（左）と m = 4（右）の場合の、混合確率 p に対する効率の変化。ここで、p はランダムアタッチメントの割合を示している。 紫色の線 (十字印)、緑色の線 (正方形印)、茶色の線 (五角形印)、水色の線 (丸印)、黒色の線 (三角形印)、オレンジ色の線 (逆三角形印)、赤色の線 (ダイヤ
モンド印) は、それぞれ β = 0, 1, 4, 10, 50, 100、および β → ∞ を表している。

81

(a) p = 0, m = 2(b) p = 0, m = 4(c) p > 0, m = 2(d) p > 0, m = 4

図 6.11: k −∞ アタッチメントにおける平均経路長 ⟨L⟩ とノード数 N の関係を示したグラフ。縦軸のスケールは (a)〜(d) で異なることに注意。ここで、p はランダム
アタッチメントの割合を示し、m = 2（右）および m = 4（左）での結果を示している。

82

れ、臨界値は 0.0025 ≤ pc ≤ 0.005 となる。そのため、ランダムアタッチメントが混合アタッチメントにおける効率的な経路の出現に必要であることがわかる。

83

6.3

k −β アタッチメントを用いた改良された p-モデル

本節、k −β アタッチメントによる p-モデルの改良版を提案する。元々の p-モデル [2] は、MED モデル [3, 4] に似ているため、両方のモデルで、ランダムに選択されたノードから距離 d または µ + 1 ホップ離れたノードがリンクの行き先として選択される。これを距離アタッチメントと呼ぶ。MED モデルと p-モデルの本質的な違いは、MED モデルでは距離アタッチメントが決定論的であるが、p-モデルでは確率的である。既存のノードから d または µ + 1 ホップ離れたノードの候補集合にノードがいくつかある場合、元の p-モデルと MED-rand では、その中から一つが一様ランダムに選択される。p-モデルが玉ねぎ状のネットワークを生成できるかどうかは明確ではない。そのため、候補ノードのランダム選択を、確率 k −β での選択に変更して、玉ねぎ状ネットワークの出現を調べることにする。

p-モデルの改良版では、結合ノード i はその次数 ki と距離 d の二倍に応じたの確率で選択される。以前に示したように、m = 4 の場合には玉ねぎ状ネットワークが生成されるため、今回は m = 4 の場合のみを考慮する。図 6.12 は、p-model0、

p-model1、p-model2、および M-MED モデルにおける成長過程を示している。ここで、接尾辞の数字 0、1、2 は、ランダムなアタッチメントは 0 本の仮想的な選択を行う場合、１本のランダムなアタッチメントを行う場合、および 2 本のランダムおよび距離（または仲介）のアタッチメントのペアを行う場合をそれぞれ意味する。M-MED モデルは、k −β アタッチメントを持つ MED モデルを改良したものであり、p-model2 と比較するために導入されている。m/2 のペアを基にした

p-model2 と同様の構成に基づき、α > 0、β > 0、d = µ + 1 ≥ 1 は与えられたパラメータである。

84

(a) p-model0(b) p-model1(c) p-model2(d) M-MED model

図 6.12: 成長過程を示す図として、(a) 〜 (c) に、異なるランダム結合の数を持つ
修正された p-model [2] を示す。図 (d) に示されているように、M-MED モデルは、MED モデル [3, 4] の最小次数選択ではなく、k −β attachment で修正されている。距
離 d と µ + 1 は、p-models と MED モデルの場合、ランダムに選択されたノードか
らのホップ数で測定される。

85

p-model0 新しいノードからの m 本のリンクについて、既存のノードの中から一様ランダムに選択される。各リンクについて、以下の 2 つのステップの選択がある。まず、仮想的に選択されたノードから距離 d の候補ノード集合を

d−α に比例する確率で選択する。次に、候補ノード集合から ki−β に比例する確率でノード i が選択される。候補集合にノードが 1 つしかない場合は、そのノードが選択される。

p-model1 最初にアタッチされるノードは既存のノードの中から一様ランダムに選択される。その後、p-model0 においては仮想選択は行わず、元の p-model[2] と同様に、k −β アタッチメントによる修正を行いながら、他の m − 1 本のリンクについても同様のプロセスを繰り返す。

p-model2 新しいノードから出る m/2 ペアのランダムと仲介アタッチメントのリンクのうち、1 つのリンク先は既存ノードの中から一様ランダムに選択される。その後、残りのリンク先について、ランダムに選択した仲介ノードから距離 d にあるノードの候補集合が、d−α に比例する確率で選ばれる。そして、それぞれのリンクのために、候補集合内のノード i が ki−β に比例する確率で選ばれる。

M-MED model p-model2 と同様に、m/2 のペアノードが選択されるが、ランダムに選択する代わりに、それぞれのランダムに選択されたノードから定数距
離 µ + 1 の候補ノードの集合が決定される。この集合に対して、M-という修飾子が付け、ランダム選択の代わりに k −β アタッチメントが適用される。

86

以下の議論では、異なるランダムアタッチメントの数が、玉ねぎ状ネットワー
クの発生に与える影響を調べるために、p-model0 と p-model1 と比較する。同様に、距離 d = µ + 1 が玉ねぎ状ネットワークの発生に与えると考えられる影響を調べるために、p-model2 と M-MED と比較する。図 6.13（a）は、α = 0.1 と 1 の場合（十字と三角形の印を持つ紫色と緑色の線）、β が 0 から 10 に増加するにつれて、p-model0 での次数相関が急速に増加し、β > 10 以降は安定することを示している。α = 3 においては（逆三角形のシアンの線）、ランダムに選ばれたノードの最も近い隣接ノードに結合する、という弱い次数相関が現れる。この場合は複写モデル [68] に対応する。複写モデルは、常に仮想的なランダム選択ノードの最も近い隣接ノードに、リンクの数を（一定の m ではなく）変化させながら結合し、SF ネットワークを生成する [78] 方法である。また、図 6.13 と 6.14（a）に示されているように、p-model1 の α=0.1 と 1 の場合（十字と三角形の印を持つ紫色と緑色の線）の分類係数は、p-model0 の場合よりも低くなる。また、図 6.14（a）において α = 3（逆三角形の印を持つシアンの線）と α=0.1 と 1（十字と三角形の印を持つ紫色と緑色の線）の間にはほとんど差がない。したがって、距離 d の効果
は、次数相関の増加において主要な影響を与えない。さらに、図 6.13（b）に示す
ように、α = 0.1 および 1（紫色および緑色の線で、十字と三角形の印が付いている）の場合、β < 10 では頑健性指標 R が急速に増加するが、α = 3（逆三角形の印が付いているシアンの線）の場合はわずかに頑健性指標 R が弱くなる。これらのネットワークは、玉ねぎ状の構造として、高い次数相関と頑健性を持っている。
次に、p-model2 と M-MED モデルの次数相関 r、頑健性指標 R、効率 E について議論する。ここで、α = 3 または µ = 0、α = 1 または µ = 2、α = 0.1 またはµ = 5 は、それぞれ近、中、遠の仲介に対応する。p-model2 と M-MED モデルの
図 6.15 と 6.16 (a) は、同じ色の線や印と比較して、近、中、遠の仲介に対する次数相関が同様に高いことを示している。さらに、p-model2 と M-MED モデルにはほとんど差がない。µ + 1 の距離が次数相関、頑健性、効率にあまり影響を与えないことに注意する必要がある。表 7.1 は、修正された p-model と MED モデルにおける β 値の出現をまとめたものである。β > 0 の場合、すべての修正モデルが玉ねぎ状の構造になる。
さらに、図 6.17 (a)、(b)、(c)、(d) は、p-model0、p-model1、p-model2、および M-MED モデルにおける次数分布を示している。半対数プロットで指数関数分87布として表される分布の分布の裾野は直線的である。β → ∞ に対して、緑色の三角形印とオレンジ色の逆三角形印の傾きが、β = 1 に対する紫色の十字印と青緑色の星印の傾きよりも急である。したがって、大きな次数のノードが存在しない
ため、β が増加するにつれて大きな次数が制限され、強い頑健性となる。

p-model0
p-model1
p-model2
M-MED model

RA: β = 0
Not O nion-like(D-D: SF at α → ∞)Not Onion-like
Not Onion-like
Not Onion-like(MED-rand)0<β<∞

kmin: β → ∞Ratio of RA

Onion-likeOnion-like0

Onion-likeOnion-likeOnion-likeOnion-likeOnion-like(MED-kmin)

1/m
0.5

Onion-like

0.5

表 6.2: 修正された p-モデルと MED モデルにおけるβ値の影響により、玉ねぎ状
ネットワークが現れる。MED-rand と MED-kmin は、それぞれ β = 0 と β = ∞ の特殊な例である。RA と D-D は、ランダムアタッチメントと複写モデルを表す。

88

(a) Assortativity, p-model0(b) Robustness, p-model0(c) Eﬃciency, p-model0

図 6.13: p-model0 における 3 つの基本的な指標 r（上）、R（中）、E （下）をパラ
メータ β に対してプロットしたグラフ。サイズ N = 5000 で、時間ステップあたりのリンク数 m は 4 本。

89

(a) Assortativity, p-model1(b) Robustness, p-model1(c) Eﬃciency, p-model1

図 6.14: p-model1 における 3 つの基本的な指標 r（上）、R（中）、E （下）をパラ
メータ β に対してプロットしたグラフ。サイズ N = 5000 で、時間ステップあたりのリンク数 m は 4 本。

90

(a) Assortativity, p-model2(b) Robustness, p-model2(c) Eﬃciency, p-model2

図 6.15: p-model2 における 3 つの基本的な指標 r（上）、R（中）、E （下）をパラ
メータ β に対してプロットしたグラフ。サイズ N = 5000 で、時間ステップあたりのリンク数 m は 4 本。

91

(a) Assortativity, M-MED(b) Robustness, M-MED(c) Eﬃciency, M-MED

図 6.16: M-MED における 3 つの基本的な指標 r（上）、R（中）、E （下）をパラ
メータ β に対してプロットしたグラフ。サイズ N = 5000 で、時間ステップあたりのリンク数 m は 4 本。

92

図 6.13 と 6.14(b) において、同じ色の線や印と比較して、m = 2 の (a) よりも、より多くのリンクを追加して玉ねぎ状のネットワークを形成するため、効率が高くなっている。

(a) p-model0(b) p-model1(c) p-model2(d) M-MED

図 6.17: 成長するネットワークにおける 4 つの修正モデルの次数分布は、m = 4
で似たような分布を持っている。各々の (a) (b) (c) (d) において、p-model0、pmodel1、p-model2、M-MED モデルで似たような分布がある。分布の裾は、半対数プロットで指数分布として線形である。β → ∞ の緑の線（三角形印）とオレンジの線（逆三角形印）の傾きは、β = 1 の紫の線（十字印）とシアンの線（アスタリスク印）の傾きよりも急である。したがって、大きな次数は β が増加するにつれて制限される。つまり、ハブは存在しない。

93

6.4

IPA モデル上の IMP のシミュレーション結果

Regular-like ネットワークの拡散力を調べるために、SF ネットワークとなる BA
モデルと β < 0 の IPA モデルで生成した [Liao3] ネットワークを使って拡散処理のシミュレーションを行った。図 6.19 と図 6.20、6.21、6.22、6.23 を比較することで、どの IMP 方法を使っても、図 6.19 の R(∞)SF 値は他の図よりも高い。従って、下の式が成立。

R(∞)SF > R(∞)β=−10 ≈ R(∞)β=−20 ≈ R(∞)β=−50 ≈ R(∞)β=−100(6.14)NSSF < NSβ=−10 ≈ NSβ=−20 ≈ NSβ=−50 ≈ NSβ=−100(6.15)

ここの R(∞)SF は、SF ネットワークの累感染が収束する十分大きい時間（t → ∞）までの累積感染数である。そこで、

R(∞)β=−10R(∞)β=−20
R(∞)β=−50
R(∞)β=−100
R(∞)SF>≈≈≈NSSF
NSβ=−10NSβ=−20NSβ=−50NSβ=−100(6.16)

式 (6.16) から、SF ネットワークに対して、ある種の平均感染能力は IPA モデルよりも強力であると言える。更に、図 6.19 の緑色 (Degree 法)、青色 (k-shell 法)、黄色 (LC 法) の線が他の図よりも明らかに上にあることが分かる。図 6.18 のような、SF ネットワークが非均等な次数分布と集中的な拡散力を持ち、結合耐性は極端に脆弱である。IPA ネットワークが均等な分布と分散的な拡散力を持ち、結合耐性は非常に強い。
一方、従来の中心性で種ノードを決める IMP 解法 [44, 45, 46, 47, 48, 40] との比較において、提案手法を用いて（四角形印を付けた線）得られた種の感染能力が一番高いことを図 6.19 から図 6.23 は示している。その理由として、提案手法は拡散の重なり問題を回避させ、従来法を凌駕する結果が得られたと考えられる。

94

図 6.18: SF ネットワークと IPA ネットワークの比較

95

(a)l = 2(b)l = 3(c)l = 4

図 6.19: β は１の時、l = 2, 3, 4 で、SF ネットワーク上各 IMP 解法のシミュレー
ション結果。

96

(a)l = 2(b)l = 3(c)l = 4

図 6.20: β は-10 の時、l = 2, 3, 4 で、IPA ネットワーク上各 IMP 解法のシミュレー
ション結果。

97

(a)l = 2(b)l = 3(c)l = 4

図 6.21: β は-20 の時、l = 2, 3, 4 で、IPA ネットワーク上各 IMP 解法のシミュレー
ション結果。

98

(a)l = 2(b)l = 3(c)l = 4

図 6.22: β は-50 の時、l = 2, 3, 4 で、IPA ネットワーク上各 IMP 解法のシミュレー
ション結果。

99

(a)l = 2(b)l = 3(c)l = 4

図 6.23: β は-100 の時、l = 2, 3, 4 で、IPA ネットワーク上各 IMP 解法のシミュ
レーション結果。

100

6.5

本章のまとめパラメータ β ≥ 0 による逆優先選択として、ランダムアタッチメントと最小次数アタッチメントを補間する k −β アタッチメントを用いて、強く頑健性な玉ねぎ状ネットワークを生成できることを示した。特に、β > 0 が大きい場合、k −β ア
タッチメントが高い次数相関と頑健性を持つ玉ねぎ状ネットワークを生成する。しかしながら、β → ∞ では効率的でない O(N ) の最長経路（直径として）を持つ
チェーン構造が得られる。そのため、ランダムアタッチメントと k −β アタッチメン
トの混合を考え、平均経路長が O(logN ) になるよう、効率的な経路の出現にはわ
ずかなランダムアタッチメントが必要であることが分かった。また、k −β アタッチ
メントを用いた玉ねぎ状ネットワークの性質について、p-model [2] および MED

model [3, 4] を改良して、k −β アタッチメントと距離 d = µ + 1 の効果を調べた。得
られた結果から、広範囲の β > 0 で k −β アタッチメントを用いて玉ねぎ状ネット
ワークを生成でき、ランダムに選ばれたノードからの距離はあまり影響を与えな
いことも分かった。これらの結果は、玉ねぎ状ネットワークの生成に関する理解を深めることに貢献する。また、6.4 節についても、IPA モデル上の IMP のシミュ
レーション結果を示した。IMP に対する、提案手法は従来法よりより良い結果が
得られた。

101

第 7 章 結言

7.1

研究成果の要約

本研究は、拡散の重なりを回避できるの IMP 問題に対する近似解法の提案と、
これまで最適耐性を持つと考えられてきた玉ねぎ状ネットワーク形成する要因の解明を目的として、筆者のおこなってきた研究成果をまとめたものである。以下、各章を要約する。
第一章では、現代社会において欠かせない大規模かつ複雑なネットワークの繋がり構造が攻撃に対して脆弱な問題について指摘した。そこで、頑健なネットワー
ク構造の必要性と IMP 問題について説明し、本研究の目的を述べ、各章の構造を示した。
第二章では、複雑ネットワークの基本的な概念を述べた後、主な解析指標である、次数、三角形数とクラスタリング係数、ネットワーク上のパーコレーション、
近接中心性と媒介中心性、次数相関、頑健性、通信効率について述べた。
第三章では、最小頂点被覆問題の定義を説明した後、コンピューター科学アプ
ローチからの２-近似アルゴリズムとより良い統計物理のアプローチからの SP 法を説明し、SP 法の同時計算を提案し、SP と 2-近似法による最小頂点被覆を予備実験として比較した。
第四章では、影響力最大化問題（IMP）に関する、独立カスケード（IC）モデル
や線形閾値（LT）モデルについて紹介した。そして、従来拡散処理では、多くの試行（平均化）が必要であるが、計算時間を短縮するために、統計物理のメッセージ
伝搬に基づいて、ネットワーク科学における集団的影響力（Collective inﬂuence）
から着想を得た高速計算法を提案した。この高速計算法は平均化が不要で、従来法に比べて数倍速くなることを示した。
第五章では、次数相関ではなく、ループと頑健性のより本質的な関係が明らかにされつつある。しかしながら、従来のヒューリスティックな手法は、ループと拡散の重なりを考慮しない。そこで、ループと拡散の重なりを着目して、情報科学

102

のマルチホップ被覆と、統計物理学的なメッセージ伝搬による近似解法を融合して、新たな方法を提案した。種間の距離を長くすることで、拡散の重なり問題を回避させた。提案手法と従来手法の比較結果を示し、提案手法は拡散の重なり問題を回避させ、従来法を凌駕する結果が得られたと考えられる。
第六章では、次数分布を固定した時、リンク両端のノードの次数の相関係数が正の値を持つ玉葱状ネットワークが最適な頑健性を持つことが明らかになっているが、玉葱状ネットワークを生成するために、色々な手法が多く提案されてきた(MED-Rand/Kmin) ことに着目する。特に、ループ強化を促す、次数分布の幅が狭いほど頑健性が高くなると考えられ、分布を底上げする最小次数（逆優先）選択
は重要な役割を果たすと考え、逆優先選択の有効性を明らかにした。そして、ランダムアタッチメントと最小次数のアタッチメントの間に連続補間を導入し、頑健性、次数相関、効率性、複数の種攻撃を比較することで、逆優先選択が頑健性と効率性の向上に重要であることを示した。玉葱状構造の生成に対して、結合距離より逆優先選択は重要な要因であることが分かった。一方、我々は、分断されやすいチェーン構造を避けるために、ランダムアタッチメントと k −β アタッチメントの混合を考え、平均経路長が O(logN ) になるよう、効率的な経路の出現にはわず
かなランダムアタッチメントが必要であることが分かった。また、k −β アタッチメ
ントを用いた玉ねぎ状ネットワークの性質について、p-model および MED modelを改良して、k −β アタッチメントと距離 d = µ + 1 の効果を調べた。得られた結果
から、広範囲の β > 0 で k −β アタッチメントを用いて玉ねぎ状ネットワークを生成でき、ランダムに選ばれたノードからの距離はあまり影響を与えないことも分
かった。

7.2

今後の課題

本研究の今後の課題について述べる。IMP に対する提案手法は、マルチホップ
被覆において、重なりを避けるためにの最適なホップ数はまだ解決されていない。
今後の研究では、この問題を考慮し、IMP に最も効果的なホップ数を示す最適な数値を探ることが考えられる。優先的選択における Rich get Richer 原理の代わりに、少量のランダムなアタッチメントがノードに等しく結合の機会を提供する。一方、最小次数アタッチメントは、小さな次数を持つ貧弱で有用性の低いノードに結合するための役立つ機会を提供して、ネットワークに対する頑健性を高めるこ103

とに繋がる。このような結論は、将来のシステムで強い頑健性と高い通信効率を兼ね備えたより良いネットワークの実現に役立つ可能性がある。

104

付録
図 7.1 から 7.14 から分かるように、紫色の線は常に最も高い位置にある。これは、私たちが提案した手法が、ネットワークでも累積感染数 R(t) 値が高く優れた伝搬効果を持っていることを意味している。下の表はパラメータの組合せである。

図
図 7.1
図 7.2
図 7.3
図 7.4
図 7.5
図 7.6
図 7.7
図 7.8
図 7.9
図 7.10
図 7.11
図 7.12
図 7.13
図 7.14

ネット名
Polblogs
Polblogs
Airtraﬃc
Airtraﬃc
Hamster
Hamster
Gnutella
Gnutella
GRQC
GRQC
Hepth
Hepth
PGP
PGP

λ値
2
2∼10
2
2∼10
2
2∼10
2
2∼10
2
2∼10
2
2∼10
2
2∼10

β値
0.12
0.12∼0.6
0.12
0.12∼0.6
0.12
0.12∼0.6
0.12
0.12∼0.6
0.12
0.12∼0.6
0.12
0.12∼0.6
0.12
0.12∼0.6

横軸
t
λ
t
λ
t
λ
t
λ
t
λ
t
λ
t
λ

表 7.1: パラメータの組合せ

105

縦軸
R(t)
R(tc )
R(t)R(tc )
R(t)R(tc )
R(t)R(tc )
R(t)R(tc )
R(t)R(tc )
R(t)R(tc )

(a)l = 2(b)l = 3(c)l = 4

図 7.1: Polblogs の高速 SIR モデルにおける累積感染数 R(t) の時間発展を示す図。
λ = 2 で、l = 2、3、4 の場合を比較している。

106

(a)l = 2(b)l = 3(c)l = 4

図 7.2: Polblogs の高速 SIR モデルにおいて、収束時間 tc における累積感染数を、
感染パラメータ λ を 2 から 10 まで変化させた場合の図。

107

(a)l = 2(b)l = 3(c)l = 4

図 7.3: Airtraﬃc の高速 SIR モデルにおける累積感染数 R(t) の時間発展を示す図。
λ = 2 で、l = 2、3、4 の場合を比較している。

108

(a)l = 2(b)l = 3(c)l = 4

図 7.4: Airtraﬃc の高速 SIR モデルにおいて、収束時間 tc における累積感染数を、
感染パラメータ λ を 2 から 10 まで変化させた場合の図。

109

(a)l = 2(b)l = 3(c)l = 4

図 7.5: Hamster の高速 SIR モデルにおける累積感染数 R(t) の時間発展を示す図。
λ = 2 で、l = 2、3、4 の場合を比較している。

110

(a)l = 2(b)l = 3(c)l = 4

図 7.6: Hamster の高速 SIR モデルにおいて、収束時間 tc における累積感染数を、
感染パラメータ λ を 2 から 10 まで変化させた場合の図。

111

(a)l = 2(b)l = 3(c)l = 4

図 7.7: Gnutella の高速 SIR モデルにおける累積感染数 R(t) の時間発展を示す図。
λ = 2 で、l = 2、3、4 の場合を比較している。

112

(a)l = 2(b)l = 3(c)l = 4

図 7.8: Gnutella の高速 SIR モデルにおいて、収束時間 tc における累積感染数を、
感染パラメータ λ を 2 から 10 まで変化させた場合の図。

113

(a)l = 2(b)l = 3(c)l = 4

図 7.9: GRQC の高速 SIR モデルにおける累積感染数 R(t) の時間発展を示す図。
λ = 2 で、l = 2、3、4 の場合を比較している。

114

(a)l = 2(b)l = 3(c)l = 4

図 7.10: GRQC の高速 SIR モデルにおいて、収束時間 tc における累積感染数を、
感染パラメータ λ を 2 から 10 まで変化させた場合の図。

115

(a)l = 2(b)l = 3(c)l = 4

図 7.11: Hepth の高速 SIR モデルにおける累積感染数 R(t) の時間発展を示す図。
λ = 2 で、l = 2、3、4 の場合を比較している。

116

(a)l = 2(b)l = 3(c)l = 4

図 7.12: Hepth の高速 SIR モデルにおいて、収束時間 tc における累積感染数を、
感染パラメータ λ を 2 から 10 まで変化させた場合の図。

117

(a)l = 2(b)l = 3(c)l = 4

図 7.13: PGP の高速 SIR モデルにおける累積感染数 R(t) の時間発展を示す図。
λ = 2 で、l = 2、3、4 の場合を比較している。

118

(a)l = 2(b)l = 3(c)l = 4

図 7.14: PGP の高速 SIR モデルにおいて、収束時間 tc における累積感染数を、感染パラメータ λ を 2 から 10 まで変化させた場合の図。

119

発表論文・口頭発表

発表論文[Liao1] Liao Fuxuan, Yukio Hayashi, Emergence of robust and eﬃcient networks
in a family of attachment models, Physica A: Statistical Mechanics and its Applications 599,(127427) 2022 .
[Liao2] Liao Fuxuan, Yukio Hayashi. Identify multiple seeds for inﬂuence maximization by statistical physics approach and multi-hop coverage. Applied Network
Science 7, (52) 2022.

国際会議
Liao Fuxuan, Yukio Hayashi, Collective computation to ﬁnd optimal multiple
seeds for inﬂuence maximization in multi-hop coverage, The 7th Combinatorics
and Graph Theory Conference(Online), May. 27-29.2022.
Liao Fuxuan, and Yukio Hayashi, Strongly Robust Onion-like Networks generated in a Family of Attachment Models, Networks 2021: A Joint Conference ofSunbelt and NetSci(Online), July. 5-10, 2021.
Liao Fuxuan, and Yukio Hayashi, A new relation of k-shell and feedback vertex
set, International School and Conference on Network Science, Tokyo Japan, Jan.
11-13, 2020.
Liao Fuxuan, and Yukio Hayashi, Identifying a crucial role for robustness andspreading in complex network”, The 8th International Conference on Complex

120

Networks and their Applications, Book of abstracts pp.569-571, Lisbon Portugal,
Dec. 21-23, 2019.

国内会議
Liao Fuxuan, 林 幸雄,
析

頑健性と拡散性に影響を与えるネットワーク指標の分, 電子情報通信学会 2020 年総合大会, N-2-3, 広島, 2020 年 3 月, 口頭発表.
[Liao3] Liao Fuxuan, 林 幸雄,

影響力最大化問題に対する種の感染力に影響する要因 , 電子情報通信学会 2023 年総合大会, N-2-1, 東京, 2023 年 3 月, 口頭発表.

121

参考文献
[1] Hao Chen and Jürgen Jost. Minimum vertex covers and the spectrum of
the normalized laplacian on trees.

Linear Algebra and Its Applications,437(4):1089–1101, 2012.
[2] Lazaros K Gallos, Shlomo Havlin, H Eugene Stanley, and Nina H Feﬀerman.
Propinquity drives the emergence of network structure and density. Proceedings of the National Academy of Sciences USA, 116(41):20360–20365, 2019.
[3] Yukio Hayashi. A new design principle of robust onion-like networks selforganized in growth. Network Science, 6(1):54–70, 2018.
[4] Yukio Hayashi and Naoya Uchiyama. Onion-like networks are both robust
and resilient. Scientiﬁc Reports, 8(1):1–13, 2018.
[5] Duncan J Watts and Steven H Strogatz. Collective dynamics of small-world
networks. Nature, 393(6684):440–442, 1998.
[6] Albert-László Barabási and Réka Albert. Emergence of scaling in random
networks. Science, 286(5439):509–512, 1999.
[7] Paul Erdős and Alfréd Rényi. On random graphs i. Publicationes Mathematicae (Debrecen), 6:290–297, 1959.
[8] Piotr Fronczak.

Scale-Free Nature of Social Networks, pages 2300–2309.

Springer New York, New York, NY, 2018.
[9] Albert-László Barabási. Scale-free networks: a decade and beyond. science,
325(5939):412–413, 2009.
[10] Albert-Laszlo Barabasi and Zoltan N Oltvai. Network biology: understanding
the cell’s functional organization. Nature reviews genetics, 5(2):101–113, 2004.
122

[11] David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread ofinﬂuence through a social network. In Proceedings of the Ninth ACM SIGKDDInternational Conference on Knowledge Discovery and Data Mining, pages
137–146, 2003.
[12] Robert V Kozinets, Kristine De Valck, Andrea C Wojnicki, and Sarah JS
Wilner. Networked narratives: Understanding word-of-mouth marketing in
online communities. Journal of marketing, 74(2):71–89, 2010.
[13] Richard Manning Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85–103. Springer, 1972.
[14] Martin Weigt and Haijun Zhou. Message passing for vertex covers. PhysicalReview E, 74(4):046110, 2006.
[15] Alfredo Braunstein, Luca Dall’Asta, Guilhem Semerjian, and Lenka Zdeborová. Network dismantling. Proceedings of the National Academy of Sciences, 113(44):12368–12373, 2016.
[16] Masaki Chujyo and Yukio Hayashi. Adding links on minimum degree andlongest distance strategies for improving network robustness and eﬃciency.
Plos one, 17(10):e0276733, 2022.
[17] Zhiou Xu, Xiaobin Rui, Jing He, Zhixiao Wang, and Tarik Hadzibeganovic.
Superspreaders and superblockers based community evolution tracking in dynamic social networks. Knowledge-Based Systems, 192:105377, 2020.
[18] Yakir Berchenko, Yael Artzy-Randrup, Mina Teicher, and Lewi Stone. Emergence and size of the giant component in clustered random graphs with agiven degree distribution. Physical Review Letters, 102:138701, Mar 2009.
[19] Ming Li, Run-Ran Liu, Linyuan Lü, Mao-Bin Hu, Shuqi Xu, and Yi-Cheng
Zhang. Percolation on complex networks: Theory and application. Physics
Reports, 907:1–68, 2021. Percolation on complex networks: Theory and application.
[20] Alex Bavelas. Communication Patterns in Task‐Oriented Groups. The Journal of the Acoustical Society of America, 22(6):725–730, 06 2005.
123

[21] G Sabidussi. The centrality index of a graph. Psychometrika 31, page 581–603,
1966.
[22] Linton C Freeman. A set of measures of centrality based on betweenness.
Sociometry, pages 35–41, 1977.
[23] Paramita Dey, Subhayan Bhattacharya, and Sarbani Roy. A survey on the roleof centrality as seed nodes for information propagation in large scale network.
ACM/IMS Transactions on Data ScienceArchiveVol, 2(3), aug 2021.
[24] Mark Newman. Networks: An Introduction. Oxford University Press, 03 2010.
[25] Toshihiro Tanizawa, Shlomo Havlin, and H. Eugene Stanley. Robustness ofonionlike correlated networks against targeted attacks. Physical Review E,
85(4):046109, Apr 2012.
[26] Vito Latora and Massimo Marchiori. Eﬃcient behavior of small-world networks. Physical Review Letters, 87(19):198701, 2001.
[27] Vijay V Vazirani. Approximation algorithms, volume 1. Springer, 2001.
[28] Hai-Jun Zhou. Spin glass approach to the feedback vertex set problem. The
European Physical Journal B, 86(11):1–9, 2013.
[29] Rodney G Downey, Michael R Fellows, and Ulrike Stege. Parameterized
complexity: A framework for systematically confronting computational intractability. Contemporary Trends in Discrete Mathematics, 49:49–99, 1997.
[30] Ning Chen. On the approximability of inﬂuence in social networks. SIAM
Journal on Discrete Mathematics, 23(3):1400–1415, 2009.
[31] Romualdo Pastor-Satorras, Claudio Castellano, Piet Van Mieghem, andAlessandro Vespignani. Epidemic processes in complex networks. Reviewsof Modern Physics, 87(3):925–979, Aug 2015.
[32] Benedek Rozemberczki and Rik Sarkar. Characteristic Functions on Graphs:
Birds of a Feather, from Statistical Descriptors to Parametric Models. In
Proceedings of the 29th ACM International Conference on Information andKnowledge Management (CIKM ’20), page 1325–1334. ACM, 2020.
124

[33] Reuven Bar-Yehuda and Shimon Even. A local-ratio theorem for approximating the weighted vertex cover problem. In Analysis and Design of Algorithms
for Combinatorial Problems, volume 109 of North-Holland Mathematics Studies, pages 27–45. North-Holland, 1985.
[34] Thomas Valente and Rebecca Davis. Accelerating the diﬀusion of innovations
using opinion leaders. The Annals of the American Academy of Political andSocial Science, 566(1):55–67, 1999.
[35] Jianxiong Guo, Yapu Zhang, and Weili Wu. An overall evaluation on beneﬁts
of competitive inﬂuence diﬀusion. IEEE Transactions on Big Data, pages
1–1, 2021.
[36] Flaviano Morone, Kevin Roth, Byungjoon Min, H. Eugene Stanley, andHernán A. Makse. Model of brain activation predicts the neural collectiveinﬂuence map of the brain. Proceedings of the National Academy of Sciences,
114(15):3849–3854, 2017.
[37] Linyuan Lü, Duan-Bing Chen, and Tao Zhou. The small world yields themost eﬀective information spreading. New Journal of Physics, 13(12):123005,
2011.
[38] Jianxiong Guo, Tiantian Chen, and Weili Wu. A multi-feature diﬀusion
model: Rumor blocking in social networks. IEEE/ACM Transactions on
Networking, 29(1):386–397, 2021.
[39] Paulo Shakarian, Abhinav Bhatnagar, Ashkan Aleali, Elham Shaabani, andRuocheng Guo. The Independent Cascade and Linear Threshold Models, pages
35–48. Springer International Publishing, Cham, 2015.
[40] Xian Teng, Sen Pei, Flaviano Morone, and Hernán A Makse. Collectiveinﬂuence of multiple spreaders evaluated by tracing real information ﬂow inlarge-scale social networks. Scientiﬁc Reports, 6(1):1–11, 2016.
[41] 西浦博 and 稲葉寿. 感染症流行の予測: 感染症数理モデルにおける定量的課
題. 2006.

125

[42] 荒牧英治, 増川佐知子, 森田瑞樹, et al. Twitter catches the ﬂu: 事実性判定を用いたインフルエンザ流行予測. 研究報告自然言語処理 (NL), 2011(1):1–8,

2011.
[43] Romualdo Pastor-Satorras and Alessandro Vespignani. Immunization of complex networks. Physical Review E, 65:036104, Feb 2002.
[44] Javier Borge-Holthoefer, Alejandro Rivero, and Yamir Moreno. Locating privileged spreaders on an online social network. Physical Review E, 85(6):066123,
2012.
[45] Gouhei Tanaka, Kai Morino, and Kazuyuki Aihara. Dynamical robustness incomplex networks: the crucial role of low-degree nodes. Scientiﬁc Reports,
2(1):1–6, 2012.
[46] Maksim Kitsak, Lazaros K Gallos, Shlomo Havlin, Fredrik Liljeros, Lev Muchnik, H Eugene Stanley, and Hernán A Makse. Identiﬁcation of inﬂuential
spreaders in complex networks. Nature Physics, 6(11):888–893, 2010.
[47] Duanbing Chen, Linyuan Lü, Ming-Sheng Shang, Yi-Cheng Zhang, and Tao
Zhou. Identifying inﬂuential nodes in complex networks. Physica A: Statistical
Mechanics and its Applications, 391(4):1777–1787, 2012.
[48] Shuai Gao, Jun Ma, Zhumin Chen, Guanghui Wang, and Changming Xing.
Ranking the spreading ability of nodes in complex networks based on local
structure. Physica A: Statistical Mechanics and its Applications, 403:130–147,
2014.
[49] Nam Parshad Bhatia and Giorgio P Szegö. Stability theory of dynamicalsystems. Springer Science & Business Media, 2002.
[50] Yamir Moreno, Romualdo Pastor-Satorras, and Alessandro Vespignani. Epidemic outbreaks in complex heterogeneous networks. The European PhysicalJournal B-Condensed Matter and Complex Systems, 26(4):521–529, 2002.
[51] Albert-László Barabási, Réka Albert, and Hawoong Jeong. Mean-ﬁeld theory for scale-free random networks. Physica A: Statistical Mechanics and its
Applications, 272(1):173–187, 1999.
126

[52] Reuven Cohen, Keren Erez, Daniel ben Avraham, and Shlomo Havlin. Resilience of the internet to random breakdowns.

Physical Review Letters,

85:4626–4628, Nov 2000.
[53] Reuven Cohen, Keren Erez, Daniel ben Avraham, and Shlomo Havlin. Breakdown of the internet under intentional attack.

Physical Review Letters,

86:3682–3685, Apr 2001.
[54] Duncan S Callaway, Mark EJ Newman, Steven H Strogatz, and Duncan J
Watts. Network robustness and fragility: Percolation on random graphs.
Physical Review Letters, 85(25):5468, 2000.
[55] Albert-László Barabási and Eric Bonabeau. Scale-free networks. Scientiﬁc
American, 288(5):60–69, 2003.
[56] Reuven Cohen and Shlomo Havlin. Scale-free networks are ultrasmall. Physical Review Letters, 90(5):058701, 2003.
[57] Giulia De Masi, Giulia Iori, and Guido Caldarelli. Fitness model for theitalian interbank money market. Physical Review E, 74(6):066112, 2006.
[58] Kimmo Soramäki, Morten L Bech, Jeﬀrey Arnold, Robert J Glass, and Walter E Beyeler. The topology of interbank payment ﬂows. Physica A: Statistical
Mechanics and its Applications, 379(1):317–333, 2007.
[59] Mark Steyvers and Joshua B Tenenbaum. The large-scale structure of semantic networks: Statistical analyses and a model of semantic growth. Cognitive
science, 29(1):41–78, 2005.
[60] Derek J. de Solla Price. Networks of scientiﬁc papers. Science, 149(3683):510–
515, 1965.
[61] Réka Albert, Hawoong Jeong, and Albert-László Barabási. Error and attack
tolerance of complex networks. Nature, 406(6794):378–382, 2000.
[62] Zhi-Gang Shao, Xian-Wu Zou, Zhi-Jie Tan, and Zhun-Zhi Jin. Growing networks with mixed attachment mechanisms. Journal of Physics A: Mathematical and General, 39(9):2035–2042, feb 2006.
127

[63] Lei Min and Zhao Qinggui. Degree distribution of a mixed attachments
model for evolving networks. In Yanwen Wu, editor, Advanced Technology in
Teaching - Proceedings of the 2009 3rd International Conference on Teaching
and Computational Science (WTCS 2009), pages 815–822, Berlin, Heidelberg,
2012. Springer Berlin Heidelberg.
[64] Petter Holme and Beom Jun Kim. Growing scale-free networks with tunableclustering. Physical Review E, 65(2):026107, 2002.
[65] Paul L Krapivsky, Sidney Redner, and Francois Leyvraz. Connectivity ofgrowing random networks. Physical Review Letters, 85(21):4629, 2000.
[66] Paul L Krapivsky and Sidney Redner. Organization of growing random networks. Physical Review E, 63(6):066123, 2001.
[67] Paul L Krapivsky and Sidney Redner. A statistical physics perspective on
web growth. Computer Networks, 39(3):261–276, 2002.
[68] Romualdo Pastor-Satorras, Eric Smith, and Ricard V Solé. Evolving protein
interaction networks through gene duplication. Journal of Theoretical Biology,
222(2):199–210, 2003.
[69] P. L. Krapivsky and S. Redner. Network growth by copying. Physical Review
E, 71:036118, Mar 2005.
[70] Cynthia S. Q. Siew and Michael S. Vitevitch. Investigating the inﬂuenceof inverse preferential attachment on network development. Entropy, 22(9),2020.
[71] Cynthia S. Q. Siew and Michael S. Vitevitch. An investigation of network
growth principles in the phonological language network. Journal of Experimental Psychology: General, 149(12), 2020.
[72] Christian M. Schneider, André A. Moreira, José S. Andrade, Shlomo Havlin,and Hans J. Herrmann. Mitigation of malicious attacks on networks. Proceedings of the National Academy of Sciences, 108(10):3838–3841, 2011.

128

[73] Zhi-Xi Wu and Petter Holme. Onion structure and network robustness. Physical Review E, 84:026106, Aug 2011.
[74] Yukio Hayashi. Growing self-organized design of eﬃcient and robust complex
networks. In 2014 IEEE Eighth International Conference on Self-Adaptive
and Self-Organizing Systems. IEEE,Xplore, 2014.
[75] VN Zadorozhnyi and EB Yudin. Growing network: models following nonlinear preferential attachment rule. Physica A: Statistical Mechanics and its
Applications, 428:111–132, 2015.
[76] Mark EJ Newman. Assortative mixing in networks. Physical Review Letters,
89(20):208701, 2002.
[77] Mark Newman. 8.7 Assortative mixing. In Networks, pages 266–268. Oxford
University Press, 2010.
[78] Xu-Hua Yang, Shun-Li Lou, Guang Chen, Sheng-Yong Chen, and Wei Huang.
Scale-free networks via attaching to random neighbors. Physica A: Statistical
Mechanics and its Applications, 392(17):3531–3536, 2013.

129