%0 Journal Article %1 10.1109/TKDE.2013.15 %A Kollias, Giorgos %A Gallopoulos, Efstratios %A Grama, Ananth %C Los Alamitos, CA, USA %D 2013 %I IEEE Computer Society %J IEEE Transactions on Knowledge and Data Engineering %K google pagerank %N PrePrints %P 1 %R 10.1109/TKDE.2013.15 %T Surfing the Network for Ranking by Multidamping %V 99 %X This paper presents a novel algorithmic (re)formulation of functional rankings, which is a family of link-based methods for ranking nodes in a network. With diverse application in network analytics - PageRank is a special case - functional rankings can be approximated as polynomials of a stochastic matrix derived from the adjacency matrix of the graph. We prove that these polynomials can be expressed as products of Google matrices parameterized by different damping factors. For this reason, we refer to our formulation as multidamping. We demonstrate that multidamping has a number of desirable characteristics: (i) for problems such as finding the highest ranked pages, multidamping admits extremely fast approximate solutions; (ii) multidamping provides an intuitive interpretation of existing functional rankings - such as LinearRank, TotalRank and Generalized Hyperbolic Rank - in terms of the surfing habits of model web users; (iii) multidamping provides a natural framework based on Monte Carlo type methods that have efficient parallel and distributed implementations. It also provides the basis for constructing new link-based rankings based on inhomogeneous products of Google matrices. We present algorithms for computing damping factors for existing functional rankings analytically and numerically. We validate various benefits of multidamping on a number of real datasets.

@article{10.1109/TKDE.2013.15, abstract = {This paper presents a novel algorithmic (re)formulation of functional rankings, which is a family of link-based methods for ranking nodes in a network. With diverse application in network analytics - PageRank is a special case - functional rankings can be approximated as polynomials of a stochastic matrix derived from the adjacency matrix of the graph. We prove that these polynomials can be expressed as products of Google matrices parameterized by different damping factors. For this reason, we refer to our formulation as multidamping. We demonstrate that multidamping has a number of desirable characteristics: (i) for problems such as finding the highest ranked pages, multidamping admits extremely fast approximate solutions; (ii) multidamping provides an intuitive interpretation of existing functional rankings - such as LinearRank, TotalRank and Generalized Hyperbolic Rank - in terms of the surfing habits of model web users; (iii) multidamping provides a natural framework based on Monte Carlo type methods that have efficient parallel and distributed implementations. It also provides the basis for constructing new link-based rankings based on inhomogeneous products of Google matrices. We present algorithms for computing damping factors for existing functional rankings analytically and numerically. We validate various benefits of multidamping on a number of real datasets.}, added-at = {2013-03-28T10:34:01.000+0100}, address = {Los Alamitos, CA, USA}, author = {Kollias, Giorgos and Gallopoulos, Efstratios and Grama, Ananth}, biburl = {https://www.bibsonomy.org/bibtex/25eadd072cd0a9dcac5f1eb6c59c539b2/ytyoun}, doi = {10.1109/TKDE.2013.15}, interhash = {90817ff3a6f4183340e2e5efd247fbe8}, intrahash = {5eadd072cd0a9dcac5f1eb6c59c539b2}, issn = {1041-4347}, journal = {IEEE Transactions on Knowledge and Data Engineering}, keywords = {google pagerank}, number = {PrePrints}, pages = 1, publisher = {IEEE Computer Society}, timestamp = {2015-06-14T09:18:17.000+0200}, title = {Surfing the Network for Ranking by Multidamping}, volume = 99, year = 2013 }