This paper introduces a novel framework that incorporates ℓ1-regularization into heat kernel and Katz centrality computations, yielding sparse solutions with provable locality guarantees. The approach enables sublinear-time approximations while maintaining rigorous error bounds, and develops efficient algorithms that exploit the sparsity induced by ℓ1-regularization for locality-aware computation.
Key findings
Introduces ℓ1-regularized variants of heat kernel and Katz centrality promoting sparsity.
Proves sublinear time complexity for local computation algorithms.
Establishes approximation guarantees relating regularized solutions to exact counterparts.
Designs practical algorithms exploiting ℓ1-regularized problem structure.
Limitations & open questions
The paper does not discuss the limitations of the proposed methods.