Resumen - Límites Inferiores más Rígidos para el Personalized PageRank de Origen Único

Límites Inferiores más Rígidos para el Personalized PageRank de Origen Único

2025-07-19 03:32:08

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

{cs.DS,cs.CC}

Este documento investiga los límites inferiores para la aproximación de la consulta Single Source Personalized PageRank (SSPPR), que cuantifica las probabilidades de un caminar aleatorio α-decay que parte del nodo s y termina en todos los demás nodos. Los autores se centran en dos configuraciones estándar de error: error absoluto (SSPPR-A) y error relativo (SSPPR-R). La búsqueda de límites superiores más ajustados para la computación de consultas SSPPR ha sido extensamente explorada, con las complejidades conocidas mejor dadas por O(min(log(1/δ), m log(n), log(n) / δ^m)) para la configuración SSPPR-R, y O(min(log(1/ε), m log(n), ε^2 / ε, m log(1/ε))) para la configuración SSPPR-A. Sin embargo, los límites inferiores correspondientes siguen siendo significativamente más anchos, solo O(min(m, 1/δ)) y O(min(n, 1/ε)), respectivamente. Esto resulta en un gran espacio entre los límites superior e inferior. Para bridar esta brecha, los autores logran límites inferiores más ajustados para este problema importante de la siguiente manera: * Para SSPPR-R, demuestran un límite inferior mejorado de O(min(m, log(δ) / δ)) para cualquier δ ∈ (0, 1). * Para SSPPR-A, establecen un límite inferior global de O(min(m, ε^2 / ε)) para cualquier ε ∈ (0, 1) y m ∈ O(n^2-β) para cualquier constante β ∈ (0, 1) arbitrariamente pequeña. En resumen, los autores mejoran los resultados de los límites inferiores conocidos previamente en un factor logarítmico log(1/δ) (SSPPR-R) o log(1/ε) (SSPPR-A), donde logran coincidir los límites inferior y superior en la consulta SSPPR-R cuando δ está alrededor de 1/n. Este progreso proporciona importantes insights e inspiración para la comunidad de investigación para diseñar algoritmos eficientes y profundizar en la comprensión teórica del PPR.