SODA21に論文が2本通りました (2/2)

 論文が SODA21 (Symposium on Discrete Algorithms) に 2本採択されました。

・Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH

Shuichi Hirahara and Nobutaka Shimizu

arXiv

・How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices?

Shuji Kijima, Nobutaka Shimizu, and Takeharu Shiraga

arXiv

の2本です。どちらの論文も非常に面白い内容で、嬉しいことに全ての査読者にかなり褒めて頂きました。

この記事では、前回に引き続き、後者の論文

How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices?

の概要をものすごく簡潔に紹介します。

具体的なモデルと結果を述べると少し長くなってしまうので、背景と貢献を簡単に紹介させて頂きます。

実世界に現れるネットワーク上の解析は、そのネットワーク上での様々な現象 (例えば情報拡散など）の振る舞いを知る上で大きな手がかりとなるため非常に重要な研究トピックの一つとなっており、ランダムウォークなどの手法が用いられることが多々あります。

また、実世界に現れるネットワーク (例えばSNSのネットワーク, 化学反応ネットワーク, 携帯電話の基地のセルラネットワークなど) は時間と共にそのグラフ構造が変化します。

この背景を踏まえ、時間とともに変化する動的なネットワーク上でのランダムウォークを理論的に解析するというのが本論文の主題となります。

実は動的なネットワーク上のランダムウォークは幾つか既存研究があるのですが、それらのほとんどは、辺だけが動的に変化するネットワークを対象としています。

というのも、ネットワーク上でランダムウォークを評価する際には、全頂点を訪問するのに必要な時間 (cover time) 、特定の頂点を訪問するのにかかる時間 (hitting time) 、定常分布に収束するまでにかかる時間 (mixing time) などの指標が基本的です。しかし頂点数が動的に変化するようなネットワークに対してはこれらの指標は定義できない（例えば cover time はどうする？）ため、何を解析していいのかがよく分かりませんでした（つまり、ランダムウォークをしている最中にも頂点が増えていくことがあるので、全頂点を訪問するという概念がよく分かりません）。

本論文では、頂点が動的に増え続けるグラフ (growing graph) 上のランダムウォークを評価する指標として、「時刻1からnまでのランダムウォークでカバーされない頂点の個数」を見ることを提案し、様々なタイプのグラフに対してその個数の期待値の上下界を導出しました。

頂点集合が動的に変化するグラフの解析は非常に重要なトピックではあるものの、そのようなグラフ上のランダムウォークはこれまでほとんど解析されていませんでした。でもそのようなグラフ上のランダムウォークの解析は考えるべき課題であり、その需要に応えたという点がこの論文の最大の貢献です。