ランダムウォーク中心性は、ノードの重要性と影響力を定量化するための基本的な指標であり、他の全てのノードから特定のノードへの到達時間の重み付き平均として定義されています。本論文では、大規模なネットワークにおけるこの指標の計算が従来の手法では困難であるという課題に対し、新しいランダムウォーク中心性の定式化を提案し、2つのスケーラブルなアルゴリズムを紹介しています。一つは近似的なコレスキー分解とスパース逆推定を利用し、もう一つは根付きスパニングツリーのサンプリングを行います。これらのアルゴリズムは、ほぼ線形の時間で動作し、強力な近似保証を提供します。10百万以上のノードを持つ大規模な実ネットワークでの実験により、提案したアルゴリズムの効率性と近似の質が示されています。