%0 Conference Paper %1 mlg2018_2 %A Holzmann, Helge %A Anand, Avishek %A Khosla, Megha %B Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG) %D 2018 %K %T What the HAK? Estimating Ranking Deviations in Incomplete Graphs %X Abstract: Most real-world graphs collected from the Web like Web graphs and social network graphs are incomplete. This leads to inaccurate estimates of graph properties based on link analysis such as PageRank. In this paper we focus on studying such deviations in ordering/ranking imposed by PageRank over incomplete graphs. We first show that deviations in rankings induced by PageRank are indeed possible. We measure how much a ranking, induced by PageRank, on an input graph could deviate from the original unseen graph. More importantly, we are interested in conceiving a measure that approximates the rank correlation among them without any knowledge of the original graph. To this extent we formulate the HAK measure that is based on computing the impact redistribution of PageRank according to the local graph structure. Finally, we perform extensive experiments on both real-world Web and social network graphs with more than 100M vertices and 10B edges as well as synthetic graphs to showcase the utility of HAK.

@inproceedings{mlg2018_2, abstract = {Abstract: Most real-world graphs collected from the Web like Web graphs and social network graphs are incomplete. This leads to inaccurate estimates of graph properties based on link analysis such as PageRank. In this paper we focus on studying such deviations in ordering/ranking imposed by PageRank over incomplete graphs. We first show that deviations in rankings induced by PageRank are indeed possible. We measure how much a ranking, induced by PageRank, on an input graph could deviate from the original unseen graph. More importantly, we are interested in conceiving a measure that approximates the rank correlation among them without any knowledge of the original graph. To this extent we formulate the HAK measure that is based on computing the impact redistribution of PageRank according to the local graph structure. Finally, we perform extensive experiments on both real-world Web and social network graphs with more than 100M vertices and 10B edges as well as synthetic graphs to showcase the utility of HAK. }, added-at = {2018-10-22T15:22:31.000+0200}, author = {Holzmann, Helge and Anand, Avishek and Khosla, Megha}, biburl = {https://www.bibsonomy.org/bibtex/2e79f4306f00502d8527486f045ed8a65/alexandriaproj}, booktitle = {Proceedings of the 14th International Workshop on Mining and Learning with Graphs (MLG)}, interhash = {d42d73d94816816df1dd0f3099088a63}, intrahash = {e79f4306f00502d8527486f045ed8a65}, keywords = {}, timestamp = {2018-10-22T15:22:31.000+0200}, title = {What the HAK? Estimating Ranking Deviations in Incomplete Graphs}, venue = {14th International Workshop on Mining and Learning with Graphs (MLG’18), co-located with KDD’18, August 20, 2018, London, United Kingdom}, year = 2018 }