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

Title

フラクタル階層ネットワークの自己組織化と増強法

Author(s)林, 幸雄

Citation

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

Issue Date

2017‑05‑31

Type

Research Paper

Text version

publisher

URL

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

RightsDescription

基盤研究(C)（一般）, 研究期間：2013〜2016, 課題番
号：25330100, 研究者番号：70293397, 研究分野：複雑ネットワーク科学

Japan Advanced Institute of Science and Technology

４版

様

式

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

科学研究費助成事業

研究成果報告書
平成 ２９ 年５ 月 ３１ 日現在

機関番号： １３３０２
研究種目： 基盤研究(C)（一般）
研究期間： 2013 〜 2016
課題番号： ２５３３０１００
研究課題名（和文）フラクタル階層ネットワークの自己組織化と増強法

研究課題名（英文）Self‑organization of fractal hierarchical networks and the enhancement

研究代表者
林

幸雄（Hayashi, Yukio）

北陸先端科学技術大学院大学・先端科学技術研究科・教授
研究者番号：７０２９３３９７
交付決定額（研究期間全体）：（直接経費）

3,500,000 円

研究成果の概要（和文）：増大する通信量に対してスケーラブルに成長する構造を災害等に活用する為、人口分布に応じた再帰分割で設計されたネットワーク上で、乱歩による探索が非一様な通信分布において優れることを明らかにし、搬送蓄積型の遅延耐性ネットワークのルーティング法に拡張した。さらに、その階層面の効率的巡回リレー法を提案し、遅延最小の負荷配分の最適問題を解いた。また、長方形の再帰四分割で構築した道路網を近似する土台から成長させたネットワークが、高い頑健性と通信効率を兼ね備えることを示した。
さらに副産物として、攻撃耐性が極めて強い頑健な玉葱状構造を協調的な部分複写等に基づいて成長させる構築
手法を世界で初めて見出した。

研究成果の概要（英文）：In order to apply a scalable growing structure for increasing communication
to emergent situation in disasters etc., we considered a geographical network designed by recursive
divisions into quarters according to population, and showed that random walks on the network aresuperior to searching targets at unknown positions in spatially non‑uniform distribution ofcommunication requests. It was extended to a routing method on DTN: delay‑tolerant‑network ofcarry‑store‑forward type. We also proposed an efficient routing in the minimum delay by relay ofcyclic deliveries on hierarchical faces, and solved the optimal load. In addition, we showed thatthe network grown from approximated road‑base by recursive divisions into four rectangles has both
high robustness and efficiency.
As a by‑product, for the first time in the world, we found new construction methods based oncooperative partial‑copying etc. for growing onion‑like networks with very strong robustness against
intentional attacks.
研究分野： 複雑ネットワーク科学
キーワード： 自己組織化
人口分布

遅延耐性ネットワーク(DTN)

自律分散

ルーティング

再帰分割

頑健性

玉葱状構造

様 式 Ｃ−１９、Ｆ−１９−１、Ｚ−１９、ＣＫ−１９（共通）１． 研究開始当初の背景
前世紀末、フラクタル統計物理学者やWeb科学者らにより、知人や企業間の社会的つながり、インターネットや電力網等の技術イン
フラ、遺伝子やタンパク質の生化学反応系な
どの現実のネットワークに広く共通する特徴：Scale‑Free(SF)構造とSmall‑World(SW)性が発見され、その基本生成規則やハブ攻撃に対する極端な脆弱性が次々と解明され、複雑ネットワーク科学という新分野の誕生で通信網を含むネットワーク研究に新たな可能性を開いた。
従来の理論からは全く予想出来なかったこ
れらの結果が得られた背景には、大規模なデータ分析と物理的解析が大きく貢献している。
最近では、携帯ユーザの軌跡や、電力‑通信‑
物流‑経済など異種ネットワーク間の相互依存問題も扱われ、米国NSF をはじめ欧州でも重点研究投資されている(例えばScience 325,
Special Issue: Complex Systems andNetworks, July 2009)。また、空間上のネッ
トワーク構築法についても7‑8 年程前から国際研究前線で徐々に活発化し、再帰的三角分割に基づくRandom Apollonian (RA)モデルやリンク長に関する優先的選択を加えた修正
Barabasi‑Albert(BA)モデルなどが提案されてきた。しかしながら、これらはSF ネットワークであり、潰れた三角形による長距離リンクの存在や、ハブ攻撃への脆弱性の欠点を持つ。一方、計算幾何学ではバランスの取れた
三角分割としてDelaunay Triangulation (DT)が古くから知られているが、局所分散処理のみでネットワーク成長させることが出来ない
為、我々はこれらを組み合わせた
Delaunay‑Like SF (DLSF)モデルを提案し、結合耐性を大幅に向上できる少量のショートカ
ット辺を追加することで、長距離リンクと脆弱性の問題に対処した。さらに、どの方向にも潰れのない典型的な形状としての正三角形
や正方形の再帰分割に基づいて成長する
Multi‑Scale Quartered (MSQ)モデルを考え、最適に近い結合耐性、（任意のノード間が直線距離の高々t=2 倍の経路で到達する）
t‑spanner な短い経路長、局所情報のみでのルーティング、より少ないトラフィック負荷等の優れた特性を示している。
国際的には物理学者が複雑ネットワーク研
究の主流で、移動体の分析をはじめ情報通信
関連分野にも積極的に参入してきている一方、計算幾何学やアルゴリズム論との接点は未だに薄い。我々はこうした異なる研究領域の融合可能性に着目しながら、地理的空間上のネットワーク構築法とショートカット追加法による頑健性の向上に関して以前から先導的立場に居る。特に、実際の人口分布に従って空間上のノード配置と結合を同時に行う自己組織化モデルを独自に提案してきた。

２． 研究の目的
都市への移住傾向や技術の進歩等によって、増大する通信要求にスケーラブルに成長できるネットワーク構造を持ち、無線通信にも適した局所情報に基づく分散処理による、近未来の情報通信ネットワークの自己組織化法を検討する。特に、人口密度等に応じた再帰分割で構築されるネットワークのフラクタル階層構造に着目して、災害時やその事
前及び事後の対策をも考慮した修復強化箇
所を探りつつ、効率的でより頑健性を増す為のショートカット追加法や協調的ルーティ
ング法を見出す。
３．研究の方法
再帰分割に基づく広いクラスのネットワー
ク構造に着目して、その階層構造を利用することで効率的かつ頑健性を向上させるショー
トカット追加法や自律分散型ルーティング法を探る。シミュレーション実験でSW 性や最大連結成分などネットワーク科学の指標を用いて通信効率や頑健性を分析しながら、理論面で確率的遷移モデルの解析も活用する。これらから、人口分布や災害時に応じた空間上のノード配置と結合を自己組織化する優れたネットワーク設計法を探り、MSQモデルを長方形分割で一般化したG‑MSQ モデル以外のネットワークにも適用できる通信効率及び頑健性の向上策を見出す。主な課題を以下とした。
(1) G‑MSQ ネットワークのフラクタル階層構
造を利用したショートカット追加法
初期正方形から、ある面を選択してその面内の縦横分割軸で四分割することを、総ノード数Nまで繰り返して構築されるG‑MSQモデルを考える。このモデル上にショートカット追加をどう施したら良いかを探り、通信効率に相当するSW性と頑健性で評価する。SW性は、
総ノード数Nの三桁程度の変化に対して最小ホップ経路の平均中継ホップ数がO(log N)になるかどうかで調べる。頑健性は、次数順の攻撃やランダム故障によるノード除去率fに対する、最大連結成分(GC)サイズSの比S/NとGC以外の孤立クラスタの平均サイズ
より計る。
のピークがGC崩壊の臨界点を示す。
また、同じ臨界値でも崩壊の急激さを計れるSの積分値も求める。各条件においてそれぞれ
100サンプルの平均値を用いる。人口分布は総務省・統計局の地域メッシュ統計データを用いて、ノードのテリトリ領域（各メッシュ点
からの最近接アクセスで定義）内の人口に比例した確率で面を選択し、その人口重心位置に最も近いLxL格子上の縦横軸で四分割する。
(2) 二分割モデルにおける理論解析
再帰的な面の四分割に基づく G‑MSQ モデル
を、二分割モデルに拡張すると、ある 1 本のリンクの除去・追加に応じた面の統合・分割が扱え、災害時等における断線と、応急処置
的な橋渡し対策に相当する。この再帰分割に

よる G‑MSQ モデルをマルコフ連鎖の観点から理論的に扱い、道路網で囲まれた面積分布やガラス破片分布と類似した、G‑MSQ モデルの辺で囲まれた面積分布の解析を行う。
(3) 協調的なメッセージフェリーによる DTN
ルーティング
人口分布で空間的に偏ったG‑MSQネット構造を利用した乱歩による餌獲得が、一様空間上の生物の最適探索戦略のLevy飛行に勝ることから、その拡張としての自律分散型ルーテ
ィングを考える。但し、餌探索では特に場所に関係なく見つかれば良かったのに対して、ルーティングではパケット毎に受信先ノードが決まっていることから、各メッセージフェリー(MF)が通過ノードの履歴情報を保持しながら、基地局に相当するノードが仲介役となって互いに情報交換する。その際、あるMFが滞在する現時点のノードから（別のMFが届け
たい）受信先ノードまで到達可能な経路：ノード系列を知らせ合い、より短い経路を提供
できれば更新する。まず基本特性として、独立したMFの軌跡に着目して、ネットワーク上の全ノードのカバー時間、あるノードから別のあるノードへの平均初通過時間などを調べる。次に、2個以上のフェリーによるノードを仲介した非同期かつ効率的な経路情報の交換を実現する協調的アルゴリズムを検討する。
その際、MF数に応じた軌跡の重なりでネット
ワークをどの程度カバーできるかに関して、MF数を変えながら、パケット発生率に対する平均到達率や平均到達時間の関係も調べる。
(4) 次数相関を考慮した新たな自己組織化法の提案
極めて脆弱な SF ネットワークでも、正の次数相関を持つ玉葱状構造になれば頑健性が最適になることが国際研究の最前線で近年分かってきた。そこで、既存の結合構造を廃棄した従来の全体的なリワイヤ法ではなく、何らかの局所処理とショートカット追加に
よって逐次成長しながら玉葱状構造が創発できる新たなネットワーク自己組織化法を見出す。この新手法から、G‑MSQ ネットワー
ク以外で通信効率と頑健性を向上させる為の対策の目途を得る。
(5) ネットワーク分析ツールとしての整備
これまで使ったネットワーク分析手法のJavaソースをモジュール化し、簡易説明を付けて整備することで、今後の有効活用を図る。
４. 研究成果
以下、研究の方法の各番号順に対応した成果を記載する。
(1)
人口分布に応じた重心分割による長方形の再帰四分割で構築した G‑MSQ ネットが道路網を近似することを見つけ、道路を移動して通信機器を運び災害時等に無線通信網を構築することを考慮して、G‑MSQ ネットのノード
配置と隣接関係を基に徐々に成長するモデルを提案した。その際、課題(4)で得られた知見を活かして、最近接アクセスの負荷が大きいノードを優先した、フラクタルな表面成長としての侵略型浸透で部分コピー元ノードを選び、更に、低次数ノード間の次数相関を強化する為にランダム選択ノード間にショートカット追加を施すことで、トポロジー
的に玉葱状構造を創発し、高い頑健性と通信効率を兼ね備えることを３大都市付近の人口分布データに対して数値的に示した①。
(2)
再帰二分割によるランダム過程において、同時刻に分割で生成された兄弟面の頻度分
布の一般的性質を理論的に明らかにした⑤。
また、次数分布等の指標の理論解析が困難な成長する広いクラスのネットワークにおいて、数値的に次数分布が推定できる一般的枠組みを導いた③。
(3)
人口分布に応じた再帰四分割で構築された G‑MSQ ネット上で空間的に偏った乱歩による探索が、従来の一様ランダムな標的分布では最適な二次元格子上の Levy 飛行よりも優れている特性を活かした、搬送蓄積型 MF に
よる DTN ルーティングの自律分散な協調的ア
ルゴリズムを開発した。その基本特性である、
全ノードのカバー時間、あるノードから別のあるノードへの平均初通過時間、及び、バイ
アスのない一様ランダム選択と空間的に偏った人口分布に応じた選択のそれぞれにおけるパケット発生率に対する平均到達率や平均到達時間の関係を数値的に明らかにした⑦。
さらに上記の乱歩よりも確実かつ迅速に転送可能な定形面を巡回する MF によるルーテ
ィングに発展させ、主要７都市付近の人口分
布データに応じて構築された再帰四分割ネットワークの各面をなす正三角形及び正方形のサイクル上を移動する MF の運搬リレー
による DTN ルーティングを考えて、それぞれの人口分布に比例した各ノードへの通信要求量を最短距離パスで転送する情報流に対する、MF のサイクル巡回度に相当するサービ
ス負荷の最適割当問題として直列型待ち行
列理論を用いて定式化④し、正三角形と正方形の場合で負荷の割当分布からその優劣を数値的に比較した。
(4)
次数相関を確率的に強める、部分的なリン
ク複写のコピー操作とショートカット追加に従った協調原理から、頑健な玉葱状構造を逐次成長しながら創発でき、更にホップ数的に短い平均経路長で通信効率も高いネット
ワークの構築法を世界で初めて見出した⑥。
この部分コピー操作とショートカット追加に従ったネットワーク自己組織化において、

フラクタルな表面成長や道路状の近接関係
による新ノード配置の空間的な制約にも、トポロジー的には頑健な玉葱状構造はほとん
ど影響しないことを明らかにした②。また、空間上のネットワーク自己組織化に関する
典型的な手法として、利己的な優先的選択の強弱、リンクの淘汰、再帰分割、部分複写、を取り上げて現状の課題等を整理して書籍にまとめた。
(5)
昨年発見され新たな脅威となった攻撃法に対する頑健性の数値解析を含めて、ネット
ワークの最短経路としてホップ数やユーク
リッド距離の双方に基づく経路長の分布を求める分析ツールを、GPU での高速化も可能
な Aparapi API 利用に拡張し、Java 環境設
定の説明とともにシュルスクリプトによる利用法をマニュアル文書化して整備した。
５．主な発表論文等〔雑誌論文〕（計 7 件）① 松久保 潤, 林 幸雄, 人口分布に基づく
道路網状土台上の頑健かつ効率的な成長型ネットワークモデル, 情報処理学会論文誌,査読有, Vol.6掲載予定, 2017, ペ
ージ数:11.
② Yukio Hayashi, Spatially self-organizedresilient networks by a distributed
cooperative mechanism, Physica A, 査
読有, Vol.457, pp.255-269, 2016.
③ Yukio Hayashi, Asymptotic behavior of
the node degrees in the ensemble
average of adjacency matrix, Network
Science, 査読有, Vol.4, No.3, pp.385-399,
2016, Cambridge University Press.
https://www.cambridge.org/core/journal
s/network-science/article/asymptotic-be
havior-of-the-node-degrees-in-the-ense
mble-average-of-adjacency-matrix/3DF
634DE205031BA5464685AD93082AA④ Yukio Hayashi, Recoverable DTN
Routing based on a Relay of Cyclic
Message-Ferries on a MSQ Network,
IEEE Xplore Digital Library FoCAS
2015, 査読有, pp.37-42, 2015.
⑤ Yukio Hayashi, Simple Derivation of
the Lifetime and the Distribution ofFaces for a Binary Subdivision Model,
IEICE Trans. Fundamentals, 査読有,Vol.E98-A, No.8, pp.1841-1844, 2015.
⑥ Yukio Hayashi, Growing Self-organized
Design of Efficient and Robust Complex
Networks, IEEE Xplore Digital Library
SASO 2014, 査読有, pp.50-59, 2014.
⑦ Yukio Hayashi, and Takayuki Komaki,
Adaptive Fractal-like Network
Structure for Efficient Search of
Targets at Unknown Positions and for
Cooperative Routing, International

Journal On Advances in Networks andServices, 査読有, Vol.6, No.1&2,
pp.37-50, 2013.
〔学会発表〕（計 21 件）
(1) Yukio
Hayashi,Emergenceof
Resilience in Growing Networks by
Range-limited Intermediations, The
5th International Workshop on
Complex
Networks
andtheirApplications,
Milan
Italy,
Nov.30-Dec.2, 2016.
(2) 林 幸雄, 情報ネットワーク科学シリー
ズ全体と第 1 巻の話 -レジリエントなネットワークの新設計法を含め-, 電子情報通信学会ソサエティ大会 招待講演
企画セッション
BI-3 情報ネットワ
ーク科学に関する最新学術動向 予稿集,
9/21-22, 2016, 北海道大学（北海道・札幌）.
(3) 高 陽, 林 幸雄, 人口分布に従った遅延耐性ネットワークの最適化, 第 13 回ネットワーク生態学シンポジウム,
8/22-23, 2016, オークラアカデミアアークホテル（千葉・木更津）.
(4) 山中 康行, 林 幸雄, 災害発生時における空間的拡がりをもつ被害を想定したネットワーク構築, 第 13 回ネットワー
ク生態学シンポジウム, 8/22-23, 2016,
オークラアカデミアアークホテル（千葉・木更津）.
(5) 松久保 潤, 林 幸雄, 道路網状土台の上で成長する頑健な通信網の構造的特徴,
第 13 回ネットワーク生態学シンポジウ
ム, 8/22-23, 2016, オークラアカデミア
アークホテル（千葉・木更津）.
(6) 林 幸雄, 分散協調する無人機で構成された復活力を持つ情報通信ネットワー
クシステム, 電子情報通信学会総合大会
シンポジウムセッション AS-6 安全・安
心な生活のための情報通信システム,
DVD 予 稿 集 AS-6-4, pp.S-79-80,
3/15-18, 2016, 九州大学（福岡・福岡）.
(7) 林 幸雄, 成長するネットワークの次数分布推定の一般的枠組み, 電子情報通信学会総合大会 一般セッション N-2 複
雑コミュニケーションサイエンス, DVD
予稿集 N-2-1, pp.368, 3/15-18, 2016,
九州大学（福岡・福岡）.
(8) Yukio Hayashi, Recoverable DTN
Routing based on a Relay of Cyclic
Message-Ferries on a MSQ Network,
The 3rd Workshop on the FoCAS(Fundamentals of Collective Adaptive
Systems)
at
The
9th
IEEE
International Conference on SASO
(Self-Adaptive and Self-Organizing
systems), Boston, USA, Sept.21, 2015.
(9) Yukio Hayashi, and Jun Matsukubo,
Resilient spatial networks withonion-like topological structure onfractal growths, Proc. of CCS(Conference on Complex Systems)
2015,
Tempe,
ArizonaUSA,
Sept.28-Oct.2, 2015.
(10) Yukio Hayashi, and Jun Matsukubo,
Emergence of robust and efficient
networks in an incrementally growing
mechanism,
ECCS(European
Conference on Complex Systems) 2014,
Track 1: Foundation of Complex
Systems, Lucca Italy, Sept. 22-26,
2014.
(11) Yukio
Hayashi,
Growing
Self-organized Design of Efficient andRobust Complex Networks, The 8thIEEE International Conference on
SASO, London UK, Sept. 8-12, 2014.
(12) Kazuya Kawamoto, Jun Matsukubo
and Yukio Hayashi, Approximation of
Betweenness
Centrality
forapplication to the social network, The
8thInternational
Collaboration
Symposiumon
Information,
Production and Systems, Kyushu
University(Fukuoka ・ Fukuoka),
Japan, Nov. 12-13, 2014.
(13) Kazuya Kawamoto, Jun Matsukubo,
and Yukio Hayashi, Analysis for
Betweenness Centrality in Social
Network
Models,"The
2nd
International
ConferenceonIndustrial Application Engineering
2014, pp.27-31, Changshu Institute ofTechnology, Changshu China, March
27-29, 2014.
(14) 林 幸雄, ネットワーク生態学シンポジ
ウムの十年を振り返って, 第 11 回ネットワーク生態学シンポジウム 特別企画,
9/4-5, 2014, 湘南国際村（神奈川・逗子）.
(15) 林 幸雄, 空間上の次世代ネットワーク
設計法 -自己組織化の四本柱を中心に-,第 11 回ネットワーク生態学シンポジウ
ム チュートリアル講演, 9/4-5, 2014, 湘
南国際村（神奈川・逗子）.
(16) 河本 和也, 林 幸雄, 松久保 潤, 社会的ネットワークへの適用を考えた媒介中心性の近似計算, 第 11 回ネットワーク
生態学シンポジウム, USB 予稿集（6 頁）
9/4-5, 2014, 湘南国際村（神奈川・逗子）.
(17) 石川 尚人, 松久保 潤, 林 幸雄, ネット
ワークの構造的特徴に対する頑健性の解析, 第 11 回ネットワーク生態学シンポジウム, USB 予稿集（6 頁） 9/4-5,
2014, 湘南国際村（神奈川・逗子）.
(18) 林 幸雄, 頑健な玉葱状ネットワークの増殖的な自己組織化構築法, 電子情報通信学会 第 11 回複雑コミュニケーション
サ イ エ ン ス 研 究 会 , USB 予 稿 集
CSS-001（7 頁）, 8/7-8, 2014, 丸駒温泉（北海道・支笏湖）.

(19) 林 幸雄, 再帰的面分割によるネットワーク構築と DTN 探索戦略に関するレビュー, 電子情報通信学会 第 10 回複雑コ
ミュニケーションサイエンス研究会,
USB 予稿集 CSS-2014-008（4 頁）,
5/19-20, 2014, 大阪大学（大阪・吹田）.
(20) Yukio Hayashi, Imitations lead tospatial clusters of relatively large
degree nodes in a random growing
network, Satellite Workshop on
Dynamic
Information
andCommunication Networks in Netsci:
International
ConferenceandSymposium on Network Science,
Copenhagen, Denmark, June 3-7,
2013.
(21) 松久保 潤, 林 幸雄, 経路の局所的な媒介度に基づくショートカットリンクの追加法, 第 10 回ネットワーク生態学シンポジウム USB 予稿集（4 頁） 9/1-2,
2013, かんぽの宿 有馬（兵庫・有馬）.
〔図書〕（計 2 件）(1) 村田 正幸 成瀬 誠 編著, 電子情報通信学会 監修, 情報ネットワーク科学入門, 情報ネットワーク科学シリーズ 1,
コロナ社, 2015, 総ページ数：218, 林 幸
雄 著:分担執筆, 9 章 情報ネットワークとレジリエンス, pp.139-153.
(2) 林 幸雄 著, 自己組織化する複雑ネット
ワーク -空間上の次世代ネットワークデ
ザイン-, 近代科学社, 2014, 総ページ
数：166.
〔産業財産権〕○出願状況（計 0 件）
○取得状況（計 0 件）
〔その他〕
ホームページ等
なし
６．研究組織(1)研究代表者
林 幸雄（HAYASHI YUKIO）
北陸先端科学技術大学院大学・先端科学技術研究科・教授
研究者番号：70293397(2)研究分担者
松久保 潤（MATSUKUBO JUN）
北九州工業高等専門学校・生産デザイン工学科・准教授研究者番号： 90413872(3)連携研究者
なし(4)研究協力者なし