概要 - 単一ソースパーソナライズドPageRankのためのより厳しい下界
タイトル
単一ソースパーソナライズドPageRankのためのより厳しい下界
時間
2025-07-19 03:32:08
著者
{"Xinpeng Jiang","Haoyu Liu","Siqiang Luo","Xiaokui Xiao"}
カテゴリ
{cs.DS,cs.CC}
リンク
http://arxiv.org/abs/2507.14462v1
PDF リンク
http://arxiv.org/pdf/2507.14462v1
概要
この論文は、ノードsから始まり、すべての他のノードに終わるα-崩壊ランダムウォークの確率を量化する単一ソースパーソナライズドページランク（SSPPR）クエリの近似の下限を調査しています。著者は、絶対誤差（SSPPR-A）と相対誤差（SSPPR-R）の2つの標準的な誤差設定に焦点を当てています。
SSPPRクエリ計算のためのより厳しい上限の追求は広く探求されており、SSPPR-R設定では最もよく知られている複雑さがO(min(log(1/δ), m log(n), log(n) / δ^m))、SSPPR-A設定ではO(min(log(1/ε), m log(n), ε^2 / ε, m log(1/ε)))であることが示されています。しかし、対応する下限は依然として非常に広範で、それぞれO(min(m, 1/δ))とO(min(n, 1/ε))に過ぎません。これにより、上限と下限の間に大きなギャップが生じます。
このギャップを埋めるために、著者は以下のようにこの重要な問題に対するより厳しい下限を達成しました：
* SSPPR-Rに対して、δ ∈ (0, 1)の任意のδに対してO(min(m, log(δ) / δ))の改良された下限を証明しました。
* SSPPR-Aに対して、ε ∈ (0, 1)の任意のεと、任意の非常に小さい定数β ∈ (0, 1)に対してm ∈ O(n^2-β)の条件下で、全体的な下限O(min(m, ε^2 / ε))を確立しました。
要約すると、著者はSSPPR-Rに対してδが1/nの近くにある場合に、SSPPR-Aに対してεの近くにある場合に、前の最もよく知られている下限結果を対数因子log(1/δ)（SSPPR-R）またはlog(1/ε)（SSPPR-A）で改善しました。この進歩は、効率的なアルゴリズムの設計をさらに進めるための重要な洞察とインスピレーションを研究コミュニティに提供します。
推奨論文
電気機械シミュレーションにおける不確実性評価のための並列時間積分を用いたマルチレベルモンテカルロサンプリング
監督量子画像処理
「真空圧縮強化微メートル尺度蒸気セル磁力計」
VideoITG: 指示的な時空基盤を用いた多模様ビデオ理解
高次元仕様を持つ複雑な細長いポリマー部品のグリーンインジェクション成形に新しい形状冷却配置の適用
無絡みの光子によるベール不平等の違反
高次元の正則単形の数
サイエンスが危機に直面している：データ操作と誤情報の時代における長期の生態学的および進化研究に対する組織的なサポートの緊急な必要性
「コードベースのPIRスキーマの安全性について」
会話が歪んだ後でもどうなるか？対話予測モデルの評価