Details
| Original language | English |
|---|---|
| Title of host publication | Complex Networks and Their Applications VII |
| Subtitle of host publication | Volume 1 Proceedings The 7th International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2018 |
| Editors | Renaud Lambiotte, Luis M. Rocha, Pietro Lió, Hocine Cherifi, Luca Maria Aiello, Chantal Cherifi |
| Publisher | Springer Verlag |
| Pages | 104-117 |
| Number of pages | 14 |
| Volume | 1. |
| Edition | 1. |
| ISBN (electronic) | 978-3-030-05411-3 |
| ISBN (print) | 978-3-030-05410-6 |
| Publication status | Published - 2 Dec 2018 |
| Event | 7th International Conference on Complex Networks and their Applications, COMPLEX NETWORKS 2018 - Cambridge, United Kingdom (UK) Duration: 11 Dec 2018 → 13 Dec 2018 |
Publication series
| Name | Studies in Computational Intelligence |
|---|---|
| Volume | 812 |
| ISSN (Print) | 1860-949X |
| ISSN (electronic) | 1860-9503 |
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.
ASJC Scopus subject areas
- Computer Science(all)
- Artificial Intelligence
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
Complex Networks and Their Applications VII: Volume 1 Proceedings The 7th International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2018. ed. / Renaud Lambiotte; Luis M. Rocha; Pietro Lió; Hocine Cherifi; Luca Maria Aiello; Chantal Cherifi. Vol. 1. 1. ed. Springer Verlag, 2018. p. 104-117 (Studies in Computational Intelligence; Vol. 812).
Research output: Chapter in book/report/conference proceeding › Conference contribution › Research › peer review
}
TY - GEN
T1 - Delusive PageRank in Incomplete Graphs
AU - Holzmann, Helge
AU - Anand, Avishek
AU - Khosla, Megha
N1 - Funding information: This work is partially funded by ALEXANDRIA (ERC 339233).
PY - 2018/12/2
Y1 - 2018/12/2
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85059075892&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-05411-3_9
DO - 10.1007/978-3-030-05411-3_9
M3 - Conference contribution
AN - SCOPUS:85059075892
SN - 978-3-030-05410-6
VL - 1.
T3 - Studies in Computational Intelligence
SP - 104
EP - 117
BT - Complex Networks and Their Applications VII
A2 - Lambiotte, Renaud
A2 - Rocha, Luis M.
A2 - Lió, Pietro
A2 - Cherifi, Hocine
A2 - Aiello, Luca Maria
A2 - Cherifi, Chantal
PB - Springer Verlag
T2 - 7th International Conference on Complex Networks and their Applications, COMPLEX NETWORKS 2018
Y2 - 11 December 2018 through 13 December 2018
ER -