Random Surfing Revisited: Generalizing PageRank's Teleportation Model
This work addresses the need for more expressive network centrality measures in fields like web search and social network analysis, though it is incremental as it builds directly on PageRank.
The authors tackled the problem of improving PageRank's teleportation model by introducing NCDawareRank, a ranking framework that incorporates network meta-information and higher-order structure while maintaining computational efficiency, resulting in enhanced robustness and effectiveness as a centrality measure in experiments on real-world networks.
We revisit the Random Surfer model, focusing on its--often overlooked--Teleportation component, and we introduce NCDawareRank; a novel ranking framework designed to exploit network meta-information as well as aspects of its higher-order structural organization in a way that preserves the mathematical structure and the attractive computational characteristics of PageRank. A rigorous theoretical exploration of the proposed model reveals a wealth of mathematical properties that entail tangible benefits in terms of robustness, computability, as well as modeling flexibility and expressiveness. A set of experiments on real-work networks verify the theoretically predicted properties of NCDawareRank, and showcase its effectiveness as a network centrality measure.