Damping from the Escape Probability: A free calibration rule for diffusion-based reachability ranking in uncertain graphs

Abstract

Future Work & Claimed Research Direction: Congestion-Aware Per-Node Damping While the global P̄_esc rule successfully calibrates the network-wide diffusion by setting the optimal baseline teleportation rate, our oracle ablations indicate an unexploited headroom (approx. +0.062 Spearman) available to a per-node damping vector (α_i). As demonstrated in our negative results, localizing the escape probability (e.g., neighborhood-smoothed P_esc) actively degrades performance, proving that the unexploited per-vertex signal is not escape-based. Consequently, our ongoing research—and the focus of the author's upcoming thesis—introduces a Structural Congestion-Aware Damping model. The proposed framework postulates that local α_i should be modulated by topological congestion rather than edge-reliability alone. The architectural claim is a hybrid formulation: α_i = f(α_global(P̄_esc), LocalCongestion_i) where the global rule establishes the network's center of gravity, and α_i diverges locally based on cheap structural proxies. Architectural Note on Congestion: While exact node congestion can theoretically be derived by solving the global linear system of the network's Markov chain (stationary distribution), doing so exacts a prohibitive computational cost (O(n²) to O(n³)), which would defeat the primary engineering advantage of our framework. Therefore, the framework relies strictly on local structural proxies (e.g., k-core number, local clustering, or degree distribution) to maintain a strict O(|E|) computational complexity. The physical intuition is that highly interconnected hubs act as diffusion "black holes"; modulating their specific damping factor based on localized congestion allows the operator to dynamically prevent mass-trapping while preserving linear-time scalability. This framework constitutes the immediate next phase of this research project.