Résumé - Boudes inférieures plus strictes pour le Personalized PageRank de source unique

Boudes inférieures plus strictes pour le Personalized PageRank de source unique

2025-07-19 03:32:08

{"Xinpeng Jiang","Haoyu Liu","Siqiang Luo","Xiaokui Xiao"}

{cs.DS,cs.CC}

Cette étude examine les bornes inférieures pour approximer la requête Single Source Personalized PageRank (SSPPR), qui quantifie les probabilités d'un déplacement aléatoire α-décroissant partant du nœud s et se terminant à tous les autres nœuds. Les auteurs se concentrent sur deux configurations d'erreur standard : l'erreur absolue (SSPPR-A) et l'erreur relative (SSPPR-R). La quête de bornes supérieures plus étroites pour le calcul de la requête SSPPR a été largement explorée, avec les complexités les plus couramment connues données par O(min(log(1/δ), m log(n), log(n) / δ^m)) pour la configuration SSPPR-R, et O(min(log(1/ε), m log(n), ε^2 / ε, m log(1/ε))) pour la configuration SSPPR-A. Cependant, les bornes inférieures correspondantes restent considérablement plus larges, seulement O(min(m, 1/δ)) et O(min(n, 1/ε)), respectivement. Cela crée des écarts importants entre les bornes supérieures et inférieures. Pour combler cet écart, les auteurs atteignent des bornes inférieures plus étroites pour ce problème important de la manière suivante : * Pour SSPPR-R, ils prouvent une borne inférieure améliorée de O(min(m, log(δ) / δ)) pour tout δ ∈ (0, 1). * Pour SSPPR-A, ils établissent une borne inférieure globale de O(min(m, ε^2 / ε)) pour tout ε ∈ (0, 1) et m ∈ O(n^2-β) pour tout constante arbitraire β ∈ (0, 1). En résumé, les auteurs améliorent les résultats de bornes inférieures les plus connus précédents de facteur logarithmique log(1/δ) (SSPPR-R) ou log(1/ε) (SSPPR-A), où ils atteignent des bornes inférieures et supérieures correspondantes sur la requête SSPPR-R lorsque δ est environ 1/n. Cette avancée fournit des insights et de l'inspiration significatifs pour la communauté de recherche afin de concevoir des algorithmes efficaces et d'approfondir la compréhension théorique du PPR.