Details
| Original language | English |
|---|---|
| Article number | 86 |
| Journal | Applied Network Science |
| Volume | 4 |
| Issue number | 1 |
| Early online date | 22 Oct 2019 |
| Publication status | E-pub ahead of print - 22 Oct 2019 |
Abstract
Most real-world graphs collected from the Web like Web graphs and social network graphs are partially discovered or crawled. 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 crawled 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. We further propose an algorithm that identifies connected subgraphs over the input graph for which the relative ordering is preserved. 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 and our High-fidelity Component Selection approach.
Keywords
- Crawls, PageRank, Ranking deviations
ASJC Scopus subject areas
- General
- Computer Science(all)
- Computer Networks and Communications
- Mathematics(all)
- Computational Mathematics
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Applied Network Science, Vol. 4, No. 1, 86, 22.10.2019.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - Estimating PageRank deviations in crawled graphs
AU - Holzmann, Helge
AU - Anand, Avishek
AU - Khosla, Megha
N1 - Funding information: We thank the anonymous reviewers for their valuable comments which helped in improving the manuscript. The publication of this article was funded by the Open Access Fund of the Leibniz Universität Hannover. This work is partially funded by SoBigData (European Union’s Horizon 2020 research and innovation programme under grant agreement No. 654024). Acknowledgements
PY - 2019/10/22
Y1 - 2019/10/22
N2 - Most real-world graphs collected from the Web like Web graphs and social network graphs are partially discovered or crawled. 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 crawled 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. We further propose an algorithm that identifies connected subgraphs over the input graph for which the relative ordering is preserved. 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 and our High-fidelity Component Selection approach.
AB - Most real-world graphs collected from the Web like Web graphs and social network graphs are partially discovered or crawled. 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 crawled 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. We further propose an algorithm that identifies connected subgraphs over the input graph for which the relative ordering is preserved. 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 and our High-fidelity Component Selection approach.
KW - Crawls
KW - PageRank
KW - Ranking deviations
UR - http://www.scopus.com/inward/record.url?scp=85074136590&partnerID=8YFLogxK
U2 - 10.1007/s41109-019-0201-9
DO - 10.1007/s41109-019-0201-9
M3 - Article
AN - SCOPUS:85074136590
VL - 4
JO - Applied Network Science
JF - Applied Network Science
IS - 1
M1 - 86
ER -