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

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

Author(s)中条, 雅貴CitationIssue Date

2023‑03

TypeThesis or Dissertation

Text version

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

RightsDescription

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

Japan Advanced Institute of Science and Technology

氏

名

中条 雅貴

学

位の種類

博士（融合科学）学

位記番号

共博融第 1 号

学 位 授 与 年 月 日
論文題

目論 文 審 査 委 員

令和 5 年 3 月 24 日
攻撃に対して頑健なネットワーク構造の解明と効率的な頑健性向上手法の提案
林 幸雄

北陸先端科学技術大学院大学教授

小谷 一孔

同上教授郷右近 英臣 同上准教授

坂本 二郎

教授

金沢大学

矢久保 孝介 北海道大学教授

論文の内容の要旨
Our society is supported by a wide variety of large and complex networks, such as the Internet (WWW), SNS,electric power, transportation, water supply, and international trading systems. These real-world networks commonly
have a scale-free property, which is characterized by power-law degree distributions. Unfortunately, scale-free networks
are extremely vulnerable against malicious attacks. Thus, it is important to reveal robust networks against attacks andobtain effective methods for strengthening the robustness of the existing networks.
In previous studies, for improving the network robustness of connectivity against attacks, several methods have been
proposed so far by enhancing a degree–degree correlation. As a highly robust structure against attacks, an "onion-likestructure" with the positive degree–degree correlation have been discussed.
Recently, apart from the degree-degree correlation, it has been noticed that the robustness against attacks and loops in
networks may be strongly correlated with each other. Therefore, as a new perspective for improving the robustness, wefocus on the loops, especially the size of Feedback Vertex Set (FVS), which is the minimum node set whose removal
makes the network no loops.
For improving the robustness against attacks, we propose two types of loop-enhancing rewirings, which are expected
to increase the size of FVS. We consider two types of rewiring with and without keeping the degree distribution because
we also investigate the effect of the degree modification on the robustness. Then, we applied our proposed andconventional methods to some real-world network data and evaluated the improvement in robustness. From the resultswith keeping degree distributions, our method increases the robustness to the same or more than the state-of-the-art
methods based on the degree-degree correlation. In addition, we confirm that our method has the largest increase in thesize of FVS. From the results without keeping degree distributions, we find that every our and conventional methods
significantly increase both the robustness and the size of FVS, compared to the methods with keeping degree
distributions. From these results, the robustness is strongly correlated with the size of FVS more than the conventionaldegree–degree correlation. Moreover, the modification of degree distributions significantly improves both therobustness and the size of FVS.
As a method for improving the robustness without keeping degree distributions, we investigate link addition methods.
In previous studies of link addition methods, two different effective strategies for choosing pairs of unconnected nodes
to add links have been considered: the minimum degree and the longest distance strategies. Thus, we propose several

kinds of link addition methods with selecting nodes by degree and distance, for investigating the contributions ofdegrees and distances in improvements of the robustness. Through numerical simulation, the minimum degree strategy
is the most effective for improving the robustness in both synthetic and real-world networks.
As an exception, only in the small number of added links, the longest distance strategy is the best.
Conversely, the shortest distance strategy rarely contributes to improving the robustness, even combined with theminimum degree strategy. Thus, enhancing longer loops is essential for improving the robustness.
Based on the significant increase of the robustness by modifying degree distributions, we investigate robust networks
in varying degree distributions. First, we consider the continuously changing degree distributions ranging frompower-law to exponential or narrower ones. Numerical results show that the smaller variances of degree distributions
lead to higher robustness and the size of FVS in this first range. Second, we consider a random regular graph with theminimum degree variance and the perturbed networks in their comprehensive discrete or random perturbations. In thissecond range, we find the random regular graphs have the highest robustness against attacks, and find a tendency forsmaller degree variance to have higher robustness.
In summary, we emphasize the important points to further improve the robustness against attacks.
Enhancing long loops strongly improves the robustness against attacks, more than the conventional degree-degreecorrelation. For adding links, the minimum degree strategy is the most effective for improving the robustness. We
suggest that the random regular graph with the minimum degree variance has optimal robustness.
keywords: Network robustness against attacks, Enhancing loops, Link addition methods, The minimum degree
strategy, The minimum variance of degree distributions.

論文審査の結果の要旨
本論文審査委員会は、提出学位論文に対する論文指導会を令和 4 年 12 月 8 日に、公聴会を令和 5 年1 月 30 日に行い、これら口頭発表の結果を踏まえ、以下のように判定した。
現代社会を支える重要インフラとして、電力網・通信網・物流網など現実の多くのネットワークにはスケールフリー(SF)と呼ばれる共通のつながり構造が存在することが今世紀初頭頃に発見された。この SF 構造は、大多数の低い次数（リンク数）のノードと、極少数の高い次数のハブで構成されるべき乗次数分布に従い、悪意のある選択的なハブ攻撃に対して、極端に脆弱で分断されやすい深刻な問題が存在する。しかも、SF 構造は利己的な高い次数への優先的選択結合で創発する。この問題に対して近年、同程度の次数のノード同士が結合しやすい正の次数相関を持つとき、攻撃に対する結合耐性が改善されることが母関数に基づく理論解析等から提示されたが、次数相関を強くする程、耐性が強くなる訳ではなく、より本質的な解決策が求められていた。本論文では、従来の次数相関ではなく、ループン強化に着目した次数分布の変化という新規の視点に基づいて、以下を検討している。
１．ループ強化に基づくリワイヤリング法やリンク追加法
ループ形成に必要不可欠なノードである組合せ最適化のフィードバック頂点集合を統計物理手法で近似的に求める、あるいはループ数に対応する全域木数をラプラシアンの固有値で効率的反復計算する等を活用してループ強化するリワイヤリング法を考案し、特に次数分布を保存しない場合では、負の次数相関でも結合耐性が高い反例と、次数分布の幅が狭くなる共通性を発見した。言い換えると、低い次数のノードに逆優先的選択結合する程、耐性強化される。この新原理に、ノード間の距離も考慮したリンク追加法を考案し、短いループは耐性強化に寄与しないことも数値的に明示した。
２．摂動解析による最適耐性の解明
上記の新原理の効果をより精密に確かめる為、ランダムレギュラーグラフ(RR)から網羅的な二峰次数分布への、及び、ランダムなより多峰次数分布への摂動解析で、RR の最適耐性を明らかにした。
これらの研究成果を、2 報の国際学術論文と 3 報の国際会議予稿集に掲載している。人工モデルのみならず実データも用いた分析で、特定のネットワークに限定されない普遍的な特性を明らかにした理論的側面のみならず、現状の脆弱性の問題を克服できる今後のネットワーク設計・構築の指針を広く具体的に与えられると考えられ、有用性も高い。本論文は、情報工学（最適化アルゴリズム）と統計物理学の両アプローチを巧妙に組合せ、レジリエンスに関するシステム工学や環境生態学、社会学の組織論の考え方をも融合した、異分野の観点を踏まえた博士（融合科学）として認められる。