【研究分野】知能情報学

【研究領域課題番号】17H01785 (KAKENデータベースで見る）

【研究キーワード】

多層ネットワーク / 情報伝搬 / コミュニティ / ネットワーク / 影響最大化 / 変分オートエンコーダ / コミュニティ抽出 / 人工知能 / アルゴリズム

【研究成果の概要】

(1)グラフ畳み込みネットワークにおいて、グラフの近傍の情報と大域的な情報とを共に用いることで、学習性能を向上させる方法を開発し、2019年6月に人工知能学会研究会優秀賞を受賞した。(2)グラフニューラルネットワークを用いて、与えられたネットワークのbetweenness中心性の計算を高速近似する手法を開発し、採択率21%の国際会議CIKM 2019に採択された。
(1)グラフ畳み込みネットワークは層の数を増やすと精度が大きく落ちてしまう。また、学習ラベルの数が少ない場合に、他の手法に比べ精度が大きく下がってしまうことがわかっている。そこで本研究では、従来のグラフ畳み込みネットワークの学習に加えて、グラフの構造特徴を保持する学習を同時に行う手法を提案した。グラフ畳み込みによるノードのラベル推定タスクの学習に加え、構造特徴を保持する学習を同時に行うことで、ノードの近傍情報とグラフ全体の構造の両方を考慮した学習が可能になる。半教師あり分類問題において、提案手法は既存手法と比べて高い精度を得ることを示した。
(2)betweenness中心性はネットワークの情報伝搬における影響力の高い頂点をみつける上で重要な尺度である。しかし、betweenness中心性の正確な計算は計算コストが高い。提案されている近似手法も、非効率であったり、精度を犠牲にしたものであったり、その両方であったりする。この研究では、Graph Neural Network(GNN)ベースの近似手法を提案した。具体的な改良点として、(a)畳み込みの際の特徴凝集を流入方法と流出方向に分けて計算し、(b)頂点自身の特徴を使わずに凝集し(c)最短経路上にない頂点を検出し、隣接行列における対応する行要素と列要素を零にした。人工データおよび実データを用いた実験で、他の手法と比べて精度および計算時間の両方で優れていることを示した。

【研究種目】基盤研究(B)

【研究期間】2017-04-01 - 2022-03-31

【配分額】16,250千円 (直接経費: 12,500千円、間接経費: 3,750千円)

【研究分野】数理情報学

【研究領域課題番号】17F17727 (KAKENデータベースで見る）

【研究キーワード】

network flow / large scale network / algorithms / network / flow / graph / algorithm

【研究成果の概要】

In this year we have focused on the transmission of knowledge in information networks. A typical property of those networks is their massive scale, making classical algorithms difficult to apply. In previous research, we have introduced a model to evaluate the influence of the different actors (for instance, the articles in a citation network) in the transmission of this knowledge.
We encountered (and solved) several difficulties. The two major difficulties come from the temporal property of information networks. In our citation network example, we had considered that articles were static once submitted. However, it is not the case of pre-print articles that can be freely updated. First, cycles of influence exist, allowing self-gratification. Second, it also raises the question of the amount of knowledge produced by each version of an article.
We provided a method to decycle networks with small cycles. This method is also used to approximate the transmission of knowledge in networks with any cycle size. Such an extension is possible due to the nature of knowledge influence to fade at each interaction.
To handle the updates of articles (versioning) and dynamic citations, we needed a temporal model for interactions that can capture any arbitrary timeframe. We extended the definition of the classical flow and cut in graphs to stream graphs.

【研究種目】特別研究員奨励費

【研究期間】2017-10-13 - 2020-03-31

【配分額】1,400千円 (直接経費: 1,400千円)

【研究分野】情報ネットワーク

【研究領域課題番号】17H01742 (KAKENデータベースで見る）

【研究キーワード】

ネットワーク / ユビキタスコンピューティング / 劣通信環境 / 群集流動 / DTN / 最適化 / アルゴリズム

【研究成果の概要】

大規模災害時の避難誘導のみならず，平常時における群集事故の回避や混雑解消のためにも，群集誘導の必要性が高まっている．そこで本研究では，リアルタイム群集流動制御技術の確立を目的として，群集流動制御の数理モデルの構築，制御アルゴリズムの設計を行い，実データに基づく大規模シミュレーションによる有効性評価を目標としている．
これまでに主に以下の成果を得た．
・人間を含む生物のモビリティとその数理モデルに関して，ミクロ的には各要素の持つ値が変化しているにも関わらず，マクロ的な視点ではスケールフリー性が維持されるメカニズムを調べた．再現できるモデルを検討し，数値実験によりその妥当性を評価した．
・群集流動制御に適したネットワーク設計に関する研究成果として，主にリンク・ノード保護による高信頼化設計法に関する研究を行った．これは，一部のリンク・ノードを保護することによって，ネットワーク全体の信頼性を向上させることを目的とした設計問題である．これに対して，必要な信頼性を有するネットワークを設計するためにリンク付加のみ，もしくはリンク保護のみで行うよりも，リンク付加と保護を両方適切に組み合わせることによってコストを抑えられる可能性がある．そこで本稿では，リンク付加と保護を組み合わせたネットワーク設計問題を定式化し，NP困難性を示し，条件を限定した場合に多項式時間で解けることを示した．さらに，実際のネットワークトポロジに対してアルゴリズムを適用することにより，リンク付加と保護を組み合わせたネットワーク設計の有効性を示した．

【研究種目】基盤研究(B)

【研究期間】2017-04-01 - 2021-03-31

【配分額】18,590千円 (直接経費: 14,300千円、間接経費: 4,290千円)

【研究分野】通信・ネットワーク工学

【研究領域課題番号】26709028 (KAKENデータベースで見る）

【研究キーワード】

先端的通信 / 符号技術 / 変復調 / MIMO / 協調通信 / インデックス変調 / 空間変調 / 移動体通信 / 非同期検出 / 大規模アレイ / 差動空間変調 / ネットワーク / 情報通信工学 / アルゴリズム / 大規模MIMO / 分散ネットワーク / 差動符号化変調 / EXITチャート / ミリ波通信 / 周波数領域等化

【研究成果の概要】

空間変調マルチアンテナ伝送方式をベースとした巨大な空間（送信アンテナ）の自由度を利用可能な高速・高信頼な大規模アレイシステムの符号設計手法を開発する。ここで、伝播路推定誤差、受信機での復号演算量、パイロットオーバヘッドの問題を解決し、信頼性と送信レートのトレードオフを柔軟にとることができる高い通信品質を実現するシステムを開発する。特に、周波数利用効率の高い非同期検出方式を組み込んだシステムを提案する。さらに、単一基地局に多数のアンテナを備えた集中基地局シナリオだけでなく、複数基地局を協調的に制御する分散シナリオも対象としたシステムを提案する。

【研究種目】若手研究(A)

【研究期間】2014-04-01 - 2018-03-31

【配分額】22,360千円 (直接経費: 17,200千円、間接経費: 5,160千円)

【研究分野】社会システム工学・安全システム

【研究領域課題番号】22510135 (KAKENデータベースで見る）

【研究キーワード】

アルゴリズム / ネットワーク / 最適化 / システム工学 / 工学システム

【研究成果の概要】

ネットワーク最適化に対する基礎理論を発展させ,ゲーム理論やグラフ理論と融合することで,社会システムにおけるネットワーク構造の分析を行った.具体的には,コミュニティ抽出のアルゴリズム構築と有効性の検証,情報伝播ネットワークの特徴付け,グラフの一様性を表す飽和グラフの分析などである.また,仮想計算機配置問題,オークションの財の割当,スタッフスケジューリング,タクシー配車問題などにネットワーク基礎理論が適用できることも示した.

【研究種目】基盤研究(C)

【研究期間】2010 - 2012

【配分額】3,120千円 (直接経費: 2,400千円、間接経費: 720千円)

【研究分野】代数学

【研究領域課題番号】10440012 (KAKENデータベースで見る）

【研究キーワード】

整数論 / コンピュータ / アルゴリズム / ソフト / データ / ネットワーク / メイリングリスト / TNT

【研究成果の概要】

本研究は,数論の分野において,現在迄に証明されている定理や方法を用いて、初等整数論,代数体や楕円曲線の不変量をコンピュータで計算し,それを通じて数論の汎用システムの構築をする為の現実的な蓄積と理論的な基礎を確立する事を目的として進められた.この二年間の研究の進展は,当初の数論を中心とした分野を超えて,広く環論や代数幾何を含む代数学に於けるコンピュータによる計算と関連するに至った.
初年度に集積したデータとプログラム,また研究成果の全国への公開配布の為のサーヴァTNTのシステムとしての再構築に基いて、今年度は,これらのデータやソフトの分類と整理をして,その相互リンクの方式を設計し,それに基いた数論ツールTNT(Pre-release)のシステム構築の基本設計の為に第3回代数学と計算研究集会を開催し,経験交流と意見交換を行ってきた.
以上の計算と構築の結果を総合して,現段階で得られている数論の基本的なアルゴリズムと数表とをまとめる基礎的な準備をする事ができた.更に今後の,この分野で求められている重要なアルゴリズムの問題と欠けている大切な数表を明らかにし,総合的な汎用ソフトウェアとデータベースを構築する展望を示す事ができた.

【研究種目】基盤研究(B)

【研究期間】1998 - 1999

【配分額】4,400千円 (直接経費: 4,400千円)

【研究分野】情報工学

【研究領域課題番号】02302047 (KAKENデータベースで見る）

【研究キーワード】

アルゴリズム / 並列処理 / 組合せ問題 / 離散構造 / 計算幾何学 / ネットワ-ク / 分散処理

【研究成果の概要】

初年度には離散構造を処理するアルゴリズムについて種々の観点から調査・検討を行った.これにより現在のアルゴリズムの限界や新しいアルゴリズム論に関する知見を得るに至った.特に並列・分散アルゴリズムに関して現状の調査・検討が行われ,新しいアルゴリズムの設計のための土台が築かれた.さらに,最終年度には,前年において得られた研究成果を土台として,総合的見地から種々の新しいアルゴリズムを設計解析した.現在から将来に向け有用となる近似・確率・並列・分散・ハ-ドウェアアルゴリズムに関する新しい知見を得るに至った.さらに計算理論に関する成果も種々得られた.代表的な成果を以下に示す.
1.VLSIのレイアウト設計における重要な問題に一つに回路分割問題があり,これまでに様々なアルゴリズムが提案されてきている.本研究では回路を構成するモジュ-ルの集合とネットリストが与えられたとき,モジュ-ル集合を2分割して左右の部分の面積をほぼ等しくし,かつ両方の部分に跨る配線の本数を最小にする問題に関するアルゴリズムを与えた.グラフの表現に基づいた方法と平面上の点集合に写像した上で点集合の2分割問題を解く方法を比較した.この結果はアルゴリズムを構成するときにグラフモデルと幾何モデルのいずれを用いるかを決定するために有用である.
2.NP完全問題などの複雑さの高い問題に対して,平均時間的には効率良く解くと主張されるアルゴリズムが数多く開発されている.それらの評価は通常解析的になされるが,実際的立場の研究者からは,実際に計算機実験によっても行われるべきだとの指摘がある.本研究では充足可能性問題に対するこのようなアルゴリズムの評価に用いるべき例題生成はいかにあるべきかについて調査・検討した.さらに,その要求を満足するような例題生成アルゴリズムが存在することを示した.

【研究種目】総合研究(A)

【研究期間】1990 - 1991

【配分額】10,800千円 (直接経費: 10,800千円)