サーバ間通信を考慮したグラフ・ネットワーク設計・制御に関するアルゴリズムの研究

点击翻译按钮获取中文摘要

現実のネットワークはまったくランダムなネットワークとは異なり,特徴的な性質を持つということが分かりつつある.このようなネットワークの特性を調べることにより,情報通信ネットワークにおけるサーバ間通信を考慮したグラフ・ネットワーク設計・制御に関する諸問題においてアルゴリズムを適用する範囲を限定でき,計算量の削減につなげられる可能性がある.そこで本研究では,現実の情報通信ネットワークにおける様々なアルゴリズムの計算量を削減することを目指すために,現実の情報通信ネットワークなどの自律的に形成されるネットワークの特性を反映した形成モデルを提案・解析した.本年度は特に実データに基づいた解析に重点を置いて検討した.具体的には,携帯電話のトラフィックと加入者数の関係を解析することにより,このネットワーク形成モデルを提案・解析した.その結果,グラフから点集合を選ぶことにより得られる生成部分グラフの成長において,次数の高い点から選び出されると捉えることにより,実データの傾向と整合性を持つモデルが得られた.一方,ランダムな点選択など他の方法では整合性を持たせることはできない.したがって,携帯電話の加入は,人間関係においてハブとなる人間から優先的に起こったと解釈することができる.本検討結果に加え,これまでに得た結果から,多くの現実のネットワークが属するグラフのクラスが限定でき,制御・設計に関する諸問題に対する高速アルゴリズムを設計する際の適用領域が明確化された.