概要
離散数学・アルゴリズム理論, 特にランダムな挙動を含む構造・アルゴリズムに興味があります. "選択を乱数に委ねる"というとでたらめな結末を想像するかもしれませんが, 確率的な操作を巧妙に用いた効率的なアルゴリズム・また実現象を的確に捉えた数理モデルが数多く考案されています. それらは時に驚くほど簡素であり, また環境変化への適応性・並列化の容易さなど嬉しい性質を複数併せ持つものも存在します. 以下, 2つの具体的なテーマを紹介します.
ランダムウォーク
ネットワーク上をランダムに動き回るエージェント(ランダムウォーク)を用いてネットワークの性質を探ろうとする, "ネットワーク上のランダムウォーク"研究に従事しております. ランダムウォークを用いたアルゴリズムは簡素さ, 局所性, 並列化の容易さ, 耐故障性などが長所であり, ランダムウォークによる"ネットワークが分断されていないかのチェック", "ネットワークの探索", "所望の部分構造の検知"などの研究がこれまでに行われております. より具体的には, ウォーカーが"所望の場所に到達するまでにかかる時間", "ネットワーク全体を訪問しきるまでにかかる時間"などの特徴量解析に基づいたアルゴリズムの性能保証を行っていますが, 解析において未解決な部分は意外にも多く, 例えば"100人のウォーカーで探索を行えば100倍探索が速くなるか"といった一見自明そうな疑問が未解決として残っています.
来嶋秀治, 清水伸高, 白髪丈晴, "動的グラフ上のランダムウォーク," 応用数理32巻1号, 5-15 (2022).
DOI: https://doi.org/10.11540/bjsiam.32.1_5Nobutaka Shimizu, Takeharu Shiraga, "Reversible random walks on dynamic graphs," Random Structures & Algorithms, 63(4), 1100-1136 (2023).
DOI: 10.1002/rsa.21164/ スライド (NII Shonan meeting: Markov Chain Monte Carlo 2.0)Shuji Kijima, Nobutaka Shimizu, Takeharu Shiraga, "How many vertices does a random walk miss in a network with moderately increasing the number of vertices?," in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), 106-122.
DOI: 10.1137/1.9781611976465.8
投票者モデル
各頂点が"意見"を保持するようなネットワーク上において, "乱択した近傍の意見を参考に自身の意見を更新していく"という確率モデル, 投票者モデル(voter model)とそのネットワーク上での合意/派閥形成の仕組みに興味があります. 複数のエージェント(プロセッサ, ロボット, etc.)が協調して何らかの処理を行おうとする際, エージェント間での"合意"は欠かすことの出来ない基本的かつ重要な計算です. 投票者モデルは合意計算への単純, 低コスト, 局所的なアプローチとして複数の研究が為されており, 特に環境変化に対する頑健性について優れた性質を持つことが分かっています. 一方で, 合意形成に至る速度・条件に関し未解明な点が多く残されています. 投票者モデルは確率論における古典的な相互作用確率系列(interacting particle system)の一つであり, 上述のランダムウォークとも深い関係があることが知られています.
Colin Cooper, Tomasz Radzik, Takeharu Shiraga, "Discrete incremental voting," OPODIS 2023, to appear.
DOI: 10.1145/3583668.3594582 (Brief Announcement at PODC 2023)/ arXiv: 2305.15632 (full version).Nobutaka Shimizu, Takeharu Shiraga, "Quasi-majority functional voting on expander graphs," in Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), 97:1-97:19.
DOI: 10.4230/LIPIcs.ICALP.2020.97/ arXiv:2002.07411 (full version).Nobutaka Shimizu, Takeharu Shiraga, "Phase transitions of Best‐of‐two and Best‐of‐three on stochastic block models," Random Structures & Algorithms, 59(1), 96-140 (2021).
DOI: 10.1002/rsa.20992Colin Cooper, Tomasz Radzik, Nicolas Rivera, Takeharu Shiraga, "Fast plurality consensus in regular expanders," in Proceedings of the 31st International Symposium on Distributed Computing (DISC 2017), 13:1-13:16.
DOI: 10.4230/LIPIcs.DISC.2017.13Colin Cooper, Robert Elsasser, Tomasz Radzik, Nicolas Rivera, Takeharu Shiraga, "Fast consensus for voting on general expander graphs," in Proceedings of the 29th International Symposium on Distributed Computing (DISC 2015), 248-262.
DOI: 10.1007/978-3-662-48653-5_17