概要

離散数学・アルゴリズム理論, 特にランダムな挙動を含む構造・アルゴリズムに興味があります. "選択を乱数に委ねる"というとでたらめな結末を想像するかもしれませんが, 確率的な操作を巧妙に用いた効率的なアルゴリズム・また実現象を的確に捉えた数理モデルが数多く考案されています. それらは時に驚くほど簡素であり, また環境変化への適応性・並列化の容易さなど嬉しい性質を複数併せ持つものも存在します.  以下, 2つの具体的なテーマを紹介します. 

ランダムウォーク

ネットワーク上をランダムに動き回るエージェント(ランダムウォーク)を用いてネットワークの性質を探ろうとする, "ネットワーク上のランダムウォーク"研究に従事しております. ランダムウォークを用いたアルゴリズムは簡素さ, 局所性, 並列化の容易さ, 耐故障性などが長所であり, ランダムウォークによる"ネットワークが分断されていないかのチェック", "ネットワークの探索", "所望の部分構造の検知"などの研究がこれまでに行われております. より具体的には, ウォーカーが"所望の場所に到達するまでにかかる時間", "ネットワーク全体を訪問しきるまでにかかる時間"などの特徴量解析に基づいたアルゴリズムの性能保証を行っていますが, 解析において未解決な部分は意外にも多く, 例えば"100人のウォーカーで探索を行えば100倍探索が速くなるか"といった一見自明そうな疑問が未解決として残っています.

投票者モデル

各頂点が"意見"を保持するようなネットワーク上において, "乱択した近傍の意見を参考に自身の意見を更新していく"という確率モデル, 投票者モデル(voter model)とそのネットワーク上での合意/派閥形成の仕組みに興味があります. 複数のエージェント(プロセッサ, ロボット, etc.)が協調して何らかの処理を行おうとする際, エージェント間での"合意"は欠かすことの出来ない基本的かつ重要な計算です. 投票者モデルは合意計算への単純, 低コスト, 局所的なアプローチとして複数の研究が為されており, 特に環境変化に対する頑健性について優れた性質を持つことが分かっています.  一方で, 合意形成に至る速度・条件に関し未解明な点が多く残されています. 投票者モデルは確率論における古典的な相互作用確率系列(interacting particle system)の一つであり, 上述のランダムウォークとも深い関係があることが知られています.