【研究分野】数理情報学

【研究領域課題番号】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千円)

【研究分野】情報学基礎理論

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

【研究キーワード】

アルゴリズム / 固定パラメタ容易性 / 点モデル / Pottsモデル / Tutte多項式 / グラフ向き付け / 組合せ物理 / Iceモデル / 6点モデル / マトロイド / グラフ / アルゴリズム論 / マトロイドマイナー理論 / アルゴリズム理論

【研究成果の概要】

マトロイドの分解理論とTutte多項式理論の研究を組合せ物理と融合し、計算論的組合せ物理という面からの研究を行った。Iceモデルとその拡張の6点モデルに対して、carving幅に関するFPTアルゴリズム構成した。Pottsモデルで枝幅に関するFPTアルゴリズムも構成した。Tutte多項式に関するMerino-Welsh予想に関して、グラフの枝の向き付けに関する問題を計算解析してTutte予想の一部解決を行った。

【研究の社会的意義】

従来、数理物理において数学と物理の両面から研究されてきた組合せ物理において、計算解析を行うアルゴリズムの開発と、本研究グループメンバが構築した組合せ構造のデータベースを活用した解析を行うことによって、新たに計算論的組合せ物理という研究アプローチを示した。融合する諸分野の理論予想の一部解決も行え、アルゴリズム論からはFPTアルゴリズムの有用性を広げた。物理モデルの量子情報処理との関係を通した量子コンピュータへ研究を展開することが期待できる。

【研究種目】挑戦的萌芽研究

【研究期間】2016-04-01 - 2019-03-31

【配分額】3,380千円 (直接経費: 2,600千円、間接経費: 780千円)

【研究分野】情報学基礎理論

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

【研究キーワード】

アルゴリズム / グラフ / ナノ回路

【研究成果の概要】

直交半直線交差グラフ（平面上の水平あるいは垂直な半直線の集合を点集合とし，直交する二つの半直線に対応する点対を辺で結んで得られるグラフ）の理論を更に発展させました．このグラフはナノ回路の耐故障設計に応用されますが，超大規模グラフになるため効率的なデータ構造と高速なアルゴリズムが必要になります．まず，OBDD(Ordered Binary Decision Diagram)が超大規模直交半直線交差グラフの効率的なデータ構造であることを明らかにしました．また，ナノ回路の耐故障設計において重要な役割を演じる「グラフの双辞書式順序問題」を凸グラフに対して解く高速な並列アルゴリズムを提案しています．

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

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

【配分額】4,810千円 (直接経費: 3,700千円、間接経費: 1,110千円)

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

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

【研究キーワード】

符号理論 / 情報理論 / 統計力学 / 理論計算機科学 / LDPC符号 / 疎グラフ / ランダムグラフ / 情報統計力学 / アルゴリズム / 確率的手法 / グラフ / グループテスト / 分散アルゴリズム / ランダム

【研究成果の概要】

現代符号理論の深化, ならびにその学際分野への展開を目指して、本研究課題は、(1) 統計力学的手法に基づくLDPC/LDGM符号の理論の深化 (三村・和田山) (2) 疎グラフに基づく観測系における推定理論の構築 (和田山)(3) 疎なランダムグラフの理論への貢献と応用 (和田山・泉)を中心に研究に取り組んだ。主たる研究成果として、疎グラフに基づくグループテストに対する情報理論的解析、疎グラフに基づく非線形符号の重み分布解析、ランダムグラフにおける種々の問題、ロバースの局所補題の応用、分散グラフアルゴリズムにおける通信複雑性とそれを用いた計算時間限界解析が挙げられる。

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

【研究期間】2013-04-01 - 2016-03-31

【配分額】16,510千円 (直接経費: 12,700千円、間接経費: 3,810千円)

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

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

【研究キーワード】

トラヒック / 推定 / DNS / 暗号化 / グラフ / スケーラビリティ / 通信 / インターネット / 計測 / アルゴリズム / 高速

【研究成果の概要】

本研究課題の遂行にあたり、特にアプリケーションとして有望であるテーマから研究を進めた。具体的には暗号化通信の通信先ホスト名を推定する問題に取り組みんだ。この問題を解決するために、ドメインネームグラフと呼ぶデータ構造とアルゴリズムを提案し、DNSの観測情報から暗号化された通信の宛先ホスト名を高精度に推定できることを実証した。結果を国際会議 TMA 2015 (採録率 29.6%)で発表、スケーラビリティに関する課題を克服した結果を 2015年度に Computer Comminications 誌にて発表。国内特許出願1件と同出願のPCT出願1件を実施。国内招待講演を1件実施。

【研究種目】研究活動スタート支援

【研究期間】2013-08-30 - 2016-03-31

【配分額】2,730千円 (直接経費: 2,100千円、間接経費: 630千円)

【研究分野】情報学基礎

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

【研究キーワード】

アルゴリズム / グラフ / ナノ回路

【研究成果の概要】

直交半直線交差グラフ（平面上の水平あるいは垂直な半直線の集合を点集合とする交差グラフ）の理論を発展させました．この理論に基づいて，次世代集積回路の革新的な技術として注目を集めているナノ回路の耐故障設計において重要な役割を果たす「直交半直線交差グラフの部分グラフ同型問題」とその特別な場合である「直交半直線交差グラフの均衡完全２部部分グラフ問題」に関するアルゴリズムを発展させました．すなわち，直交半直線交差木に対して前者を解く従来よりも高速なアルゴリズムを提案すると共に，直交半直線交差グラフの特別な場合である２部置換グラフに対して後者を解く従来よりも高速なアルゴリズムを提案しています．

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

【研究期間】2011-04-28 - 2015-03-31

【配分額】5,200千円 (直接経費: 4,000千円、間接経費: 1,200千円)

【研究分野】情報学基礎

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

【研究キーワード】

アルゴリズム / グラフ / ナノ回路

【研究成果の概要】

直交半直線交差グラフ(平面上の水平あるいは垂直な半直線の集合を点集合とする交差グラフ)という新しいグラフのクラスを提案して,その離散構造を解明しました.この直交半直線交差グラフの理論に基づいて,次世代集積回路の革新的な技術として注目を集めているナノ回路の耐故障設計において重要な役割を果たす「直交半直線交差グラフの部分グラフ同型問題」とその特別な場合である「直交半直線交差グラフの均衡完全2部部分グラフ問題」に対して,前者はNP困難と呼ばれる難しい問題であるが,後者は多項式時間のアルゴリズムで効率的に解ける易しい問題であることを明らかにしました.

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

【研究期間】2008 - 2010

【配分額】4,550千円 (直接経費: 3,500千円、間接経費: 1,050千円)

【研究分野】数学一般(含確率論・統計数学)

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

【研究キーワード】

離散数学 / グラフ / 閉路 / アルゴリズム

【研究成果の概要】

離散数学、特に、グラフ理論に関する研究が活発に行われた。たとえば、グラフの頂点集合の分割問題としては、k-連結グラフは大きさを指定したk個の連結部分グラフに分割できるという結果が有名であるが、連結度を最小次数におきかえた問題、すなわち、最小次数がk以上の連結グラフは大きさを指定したk個の部分グラフで最小次数が1以上のものに分割できるという予想を肯定的に解決した。さらに、最小次数が3k-2以上ならば、各部分グラフが含むべき点を1点ずつ指定しても孤立点を含まないように分割できということを証明した。
また、独立な2点の次数和が頂点数以上ならばハミルトン閉路が存在するという有名な結果を拡張して、独立な3点の次数和が頂点数以上ならば2つの閉路で頂点集合を覆うことができるということを示した。さらに、連結グラフの独立な3点の次数和が頂点数以上であれば、最長閉路の長さが最長通路の長さ-1以上になることを示した。
グラフの自動描画に関しても進展があった。グラフの頂点間に適当な力を働かせると、安定状態では構造がよくわかるレイアウトが得られる。頂点と辺の間にも力を働かせることにより頂点が無関係な辺の近くにいかないようになった。また、力を定義する関数と最終状態数の関係もわかってきて、頂点間の距離が小さいとき、あまり大きな力を加えないほうが最終状態数が多くならないことがわかった。一方、グラフ距離が2の時は比較的大きな反発力を与えたほうが美しいレイアウトが得られることもわかった。
また、整数から成る集合を和が指定した値になるように分割するという問題も研究された。とくに、1から2n-1までの奇数の集合を和が偶数で一定の値となるように分割できるための必要十分条件が得られた。

【研究種目】一般研究(C)

【研究期間】1995

【配分額】2,100千円 (直接経費: 2,100千円)

【研究分野】数学一般

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

【研究キーワード】

組合せ論 / グラフ / 曲面への埋込み / 計算幾何 / アルゴリズム / アソシエーションスキーム / スピンモデル / 組合せ理論 / 分割問題 / 閉路 / 次数 / 埋め込み / 連結度 / 双対グラフ / 指標表

【研究成果の概要】

グラフ理論の基礎的な分野において研究が活発に行われた。特に、k-因子や連結[2,k]-因子、ハミルトン閉路などが存在するために、点連結度、辺連結度、強度、結合数などグラフの連結性を表す不変量が満たすべき条件について色々な結果が得られた。たとえば、独立した3頂点の次数の和がグラフの位数以上ならば、いくつかの例外を除き、最長閉路の長さは最長通過の点数-1以上であることが示された。これは、今までに知られていたこの種の結果を統一的に記述した形で拡張しており、最長閉路の性質に関する基本的な結果になると思われる。3-連結グラフには可縮な辺が存在するという結果は有名であるが、その分布に関する研究や3点以上の可縮な部分グラフの存在に関する条件が得られた。たとえば、グラフを任意の大きさの孤立点を持たない部分集合に分割できるための最小次数に関する最善の条件が求まった。曲面の幾何学的性質と、そこに埋め込まれたグラフの性質の間には深い関係がある。平面に埋め込まれたグラフ、すなわち、平面グラフには双対グラフが定義できるが、その他の曲面の場合には双対グラフの定義は成功していない。射影平面への異なる埋め込みに対応する双対グラフの性質を調べることにより、双対概念の見直しが行われた。また、各種の曲面上の三角形分割や四角形分割の性質が調べられた。代数的組合せ論においては、距離正則グラフやアソシエーションスキームの分類問題や、スピンモデル、アダマ-ル行列の研究が進展し、興味ある実例が色々構成された。とくに、代数的グラフ理論の中心的研究対象である距離正則グラフの研究では、対応するアソシエーションスキームの表現を研究することが重要であることがわかってきた。とくに、有限群の場合と同じような指標表が定義できることがわかり、代表的なアソシエーションスキームであるハミングスキーム等の指標表の性質が調べられた。さらに、有限幾何や各種組み合わせ問題に関する各種アルゴリズムの解析と開発が行われた。

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

【研究期間】1992 - 1994

【配分額】9,000千円 (直接経費: 9,000千円)

【研究分野】情報工学

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

【研究キーワード】

ニュ-ラルネットワ-ク / グラフ / クリ-ク / ボルツマン機械 / 確率化アルゴリズム / Nークィ-ン問題 / 近似アルゴリズム / アルゴリズム / nークィ-ン問題

【研究成果の概要】

1.逐次探索方式によって出来る限り最大に近いクリ-クを抽出するため、いくつかのヒュ-リスティックな方法を考察・組合せ、節点数の3乗オ-ダ時間計算量の近似アルゴリズムを開発し、解精度・実行速度について良好な結果を得た。
2.Boltzmann機械の概念を基礎として、局所最適解から容易に脱出し易いエネルギ-関数を考案し、逐次より最大に近いクリ-クを抽出結果として出してゆく確率アルゴリズムを提案した。更に、それに対していくつかの改良・変形版を考案した。先ず、このアルゴリズムは、前記1のアルゴリズムと同程度の実行時間をかけた場合には、前記によるのと同等あるいはそれ以上の解精度を得た。更に、解探索の反復を行うことにより、時間計算量の多項式オ-ダ性を保ったまま、この解精度を逐次改善してゆけることを確認した。
一方、確率処理を除いた決定性アルゴリズムも開発し、さほど解精度を低下させることなく、実行時間を前記確率アルゴリズムの1/10以下にすることに成功した。更に、前記確率アルゴリズムを組み合せることにより、解精度・実行時間共に優れたアルゴリズムを確立し、その有効性を大量の計算機実験により実証した。
また、対象グラフが刻々時間的に変動する場合にも、前記アルゴリズムは単純な変更により容易に対応可能となることを明らかにし、実験的にその有効性を確認した。
3.nーqueen問題に対して前記2の方法を適用することにより、従来のシミュレ-テッドアニ-リングを用いる方法による場合に比べて2桁〜3桁以上高速に解を求めることができることを実験的に明らかにした。

【研究種目】一般研究(C)

【研究期間】1990 - 1991

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