Zusammenfassung - Schärferer untere Schranken für Single-Source Personalisierten PageRank

Schärferer untere Schranken für Single-Source Personalisierten PageRank

2025-07-19 03:32:08

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

{cs.DS,cs.CC}

Diese Arbeit untersucht die unteren Schranken für die Approximation der Single Source Personalized PageRank (SSPPR)-Abfrage, die die Wahrscheinlichkeiten quantifiziert, dass eine α-Zerfalls-zufällige Wanderung von Knoten s ausgeht und bei allen anderen Knoten endet. Die Autoren konzentrieren sich auf zwei Standardfehlerinstellungen: absolute Fehler (SSPPR-A) und relativer Fehler (SSPPR-R). Die Suche nach engeren oberen Schranken für die Berechnung der SSPPR-Abfrage wurde weitgehend erforscht, und die bekanntesten Komplexitäten betragen O(min(log(1/δ), m log(n), log(n) / δ^m)) für die SSPPR-R-Einstellung und O(min(log(1/ε), m log(n), ε^2 / ε, m log(1/ε))) für die SSPPR-A-Einstellung. Allerdings bleiben die entsprechenden unteren Schranken erheblich lockerer, nämlich O(min(m, 1/δ)) und O(min(n, 1/ε)). Dies führt zu erheblichen Lücken zwischen den oberen und unteren Schranken. Um diese Lücke zu schließen, erreichen die Autoren engere untere Schranken für dieses wichtige Problem wie folgt: * Für SSPPR-R beweisen sie eine verbesserte untere Schranke von O(min(m, log(δ) / δ)) für jeden δ ∈ (0, 1). * Für SSPPR-A setzen sie eine allgemeine untere Schranke von O(min(m, ε^2 / ε)) für jeden ε ∈ (0, 1) und m ∈ O(n^2-β) für jede beliebige kleine Konstante β ∈ (0, 1). Zusammenfassend verbessern die Autoren die bislang bekanntesten unteren Schrankenresultate um einen logarithmischen Faktor log(1/δ) (SSPPR-R) oder log(1/ε) (SSPPR-A), wobei sie auf der SSPPR-R-Abfrage Matching untere und obere Schranken erreichen, wenn δ ungefähr 1/n beträgt. Dieser Fortschritt bietet bedeutende Einblicke und Anregungen für die Forschergemeinschaft, um effiziente Algorithmen zu entwerfen und die theoretische Verständnis des PPR zu vertiefen.