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

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

Author(s)廖, 福軒

CitationIssue Date

2023-09

TypeThesis or Dissertation

Text version

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

RightsDescription

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

Japan Advanced Institute of Science and Technology

氏

名

LIAO, Fuxuan

学

位の種

類

博士（工学）

学

位記番号

共博工第 1 号

学 位 授 与 年 月 日
論文題

目論 文 審 査 委 員

令和 5 年 9 月 22 日
ループ強化に基づく逆優先選択とメッセージ伝搬法の情報拡散や攻撃耐性に対する強固な効果
林 幸雄 北陸先端科学技術大学院大学教授

小谷 一孔同教授

郷右近 英臣

同准教授

坂本 二郎

金沢大学教授高邉 賢史

東京工業大学准教授

論文の内容の要旨
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 effectof 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 thefuture growth of our network infrastructures.
Keywords:
Network science, Self-organization, Minimum degree attachment, Influence maximum problem,
Statistical physics approach
論文審査の結果の要旨
本論文審査委員会は、提出学位論文に対する論文指導会を令和 5 年 6 月 1 日に、公聴会を令和 5年 8 月 2 日に行い、これら口頭発表の結果を踏まえ、以下のように判定した。
ネットワーク上で情報拡散を最大化する拡散の種ノードを見つける問題は、コンピュータ科学における組み合わせ的な難問として古くから知られている。一方、現実の多くのネットワークに共通して存在する Scale-Free 構造から、多数の結合リンクを持つハブを拡散の種に選ぶのが妥当と直感的には思えるが、複数の種からの拡散の重なりはこれまで考慮されてない。さらに、ハブが出来ないネットワークにおける、頑健性（攻撃に対する結合耐性）や拡散特性はほとんど明らかにされてない。本研究では、これらに関して、ハブに囚われない新たな考え方を提示し、情報拡散と頑健性の両者の向上に極めて効果的なネットワーク設計法を新規開拓した。
１）インフルエンサー抽出に相当する情報拡散最大化として、種間を隔てる l-hops 頂点被覆問題を的確に帰着させ、その難問を統計物理の近似解法とサンプル不要の高速化で高精度に推定できることを数値的に示し、従来のハブ選択を含む種々の中心性で種ノードを選択した場合を凌駕する高い拡散力を持つことを複数の現実の社会的ネットワーク（のデータ）を用いたシミュレーションから明示した。
２）ハブが出来ないネットワーク成長原理として、従来の真逆となる逆優先的選択モデルを独自に考え、Poisson 分布とべき乗分布のピンポイントから種々の次数分布をパラメトリックに連続補間しつつ、正則グラフにまで拡張して、混在していた距離と最小次数のうち後者がより主要因となり、通信効率と頑健性を大幅に改善できることを数値的に明らかにした。但し、Scale-Free 構造から脱却してハブを持たない場合は、比較的均等な拡散力の種ノードが多数必要となることも示した。
これらの研究成果を、2 報の国際学術論文と４報の国際会議予稿集（+国内口頭発表 2 件）に掲載している。人工モデルのみならず実データも用いた分析で、特定のネットワークに限定されない普遍的な特性を明らかにした理論的側面のみならず、頑健で情報拡散最大化を実現できるネットワーク設計・構築の指針を広く具体的に与えた有用性も高い。これらの内容は、コンピュータ科学と統計物理学の方法論を融合させてはいるが、SNS 上の IT ビジネスにも応用が期待され工学的にも十分価値があると言え、博士（工学）として認められる。