{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,12]],"date-time":"2025-09-12T19:25:55Z","timestamp":1757705155019,"version":"3.37.3"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,10,22]],"date-time":"2019-10-22T00:00:00Z","timestamp":1571702400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,10,22]],"date-time":"2019-10-22T00:00:00Z","timestamp":1571702400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Netw Sci"],"published-print":{"date-parts":[[2019,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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<jats:sc>PageRank<\/jats:sc>. In this paper we focus on studying such deviations in ordering\/ranking imposed by<jats:sc>PageRank<\/jats:sc>over crawled graphs. We first show that deviations in rankings induced by<jats:sc>PageRank<\/jats:sc>are indeed possible. We measure how much a ranking, induced by<jats:sc>PageRank<\/jats:sc>, 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<jats:sc>HAK<\/jats:sc>measure that is based on computing the impact redistribution of<jats:sc>PageRank<\/jats:sc>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<jats:sc>HAK<\/jats:sc>and our<jats:italic>High-fidelity Component Selection<\/jats:italic>approach.<\/jats:p>","DOI":"10.1007\/s41109-019-0201-9","type":"journal-article","created":{"date-parts":[[2019,10,23]],"date-time":"2019-10-23T04:27:21Z","timestamp":1571804841000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Estimating PageRank deviations in crawled graphs"],"prefix":"10.1007","volume":"4","author":[{"given":"Helge","family":"Holzmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Avishek","family":"Anand","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0319-3181","authenticated-orcid":false,"given":"Megha","family":"Khosla","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,10,22]]},"reference":[{"key":"201_CR1","unstructured":"Archiveteam (2011) Friendster Social Network Dataset: Friends. https:\/\/archive.org\/details\/friendster-dataset-201107 , published under CC0 1.0 Universal."},{"issue":"1","key":"201_CR2","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1145\/1052934.1052938","volume":"5","author":"M Bianchini","year":"2005","unstructured":"Bianchini, M, Gori M, Scarselli F (2005) Inside pagerank. ACM Trans Internet Technol (TOIT) 5(1):92\u2013128.","journal-title":"ACM Trans Internet Technol (TOIT)"},{"issue":"2","key":"201_CR3","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1051\/ita:2006004","volume":"40","author":"P Boldi","year":"2006","unstructured":"Boldi, P, Lonati V, Santini M, Vigna S (2006) Graph fibrations, graph isomorphism, and pagerank. RAIRO-Theor Inform Appl 40(2):227\u2013253.","journal-title":"RAIRO-Theor Inform Appl"},{"key":"201_CR4","doi-asserted-by":"publisher","unstructured":"Boldi, P, Rosa M, Santini M, Vigna S (2011) Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks. In: Srinivasan S, Ramamritham K, Kumar A, Ravindra MP, Bertino E, Kumar R (eds)Proceedings of the 20th international conference on World Wide Web, 587\u2013596.. ACM Press. https:\/\/doi.org\/10.1145\/1963405.1963488 .","DOI":"10.1145\/1963405.1963488"},{"key":"201_CR5","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1007\/978-3-540-30216-2_14","volume-title":"Algorithms and Models for the Web-Graph","author":"Paolo Boldi","year":"2004","unstructured":"Boldi, P, Santini M, Vigna S (2004) Do your worst to make the best: Paradoxical effects in pagerank incremental computations In: International Workshop on Algorithms and Models for the Web-Graph, 168\u2013180.. Springer. https:\/\/doi.org\/10.1007\/978-3-540-30216-2_14 ."},{"key":"201_CR6","first-page":"595","volume-title":"Proc. of the Thirteenth International World Wide Web Conference (WWW 2004)","author":"P Boldi","year":"2004","unstructured":"Boldi, P, Vigna S (2004) The WebGraph framework I: Compression techniques In: Proc. of the Thirteenth International World Wide Web Conference (WWW 2004), 595\u2013601.. ACM Press, Manhattan. http:\/\/law.di.unimi.it\/datasets.php ."},{"key":"201_CR7","first-page":"132","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"B Bollob\u00e1s","year":"2003","unstructured":"Bollob\u00e1s, B, Borgs C, Chayes J, Riordan O (2003) Directed Scale-free Graphs In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 132\u2013139.. Society for Industrial and Applied Mathematics, Philadelphia. http:\/\/dl.acm.org\/citation.cfm?id=644108.644133 ."},{"key":"201_CR8","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1016\/j.jda.2012.04.011","volume":"16","author":"G Borradaile","year":"2012","unstructured":"Borradaile, G, Heeringa B, Wilfong G (2012) The knapsack problem with neighbour constraints. J Discret Algoritm 16:224\u2013235. https:\/\/doi.org\/10.1016\/j.jda.2012.04.011 .","journal-title":"J Discret Algoritm"},{"issue":"3","key":"201_CR9","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/s00799-016-0171-9","volume":"18","author":"M Costa","year":"2017","unstructured":"Costa, M, Gomes D, Silva MJ (2017) The evolution of web archiving. Int J Digit Libr 18(3):191\u2013205.","journal-title":"Int J Digit Libr"},{"key":"201_CR10","doi-asserted-by":"publisher","unstructured":"Dasgupta, A, Kumar R, Sarlos T (2014) On estimating the average degree In: Proceedings of the 23rd international conference on World wide web, 795\u2013806.. ACM. https:\/\/doi.org\/10.1145\/2566486.2568019 .","DOI":"10.1145\/2566486.2568019"},{"key":"201_CR11","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"P Erdo\u0307s","year":"1959","unstructured":"Erdo\u0307s, P, R\u00e9nyi A (1959) On random graphs. Publ Math Debr 6:290\u2013297.","journal-title":"Publ Math Debr"},{"key":"201_CR12","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1038\/ncomms1396","volume":"2","author":"G Ghoshal","year":"2011","unstructured":"Ghoshal, G, Barab\u00e1si AL (2011) Ranking stability and super-stable nodes in complex networks. Nat Commun 2:394.","journal-title":"Nat Commun"},{"issue":"4","key":"201_CR13","doi-asserted-by":"publisher","first-page":"1141","DOI":"10.1214\/aoms\/1177706098","volume":"30","author":"EN Gilbert","year":"1959","unstructured":"Gilbert, EN (1959) Random graphs. Ann Math Statist 30(4):1141\u20131144.","journal-title":"Ann Math Statist"},{"issue":"9","key":"201_CR14","doi-asserted-by":"publisher","first-page":"1872","DOI":"10.1109\/JSAC.2011.111011","volume":"29","author":"M Gjoka","year":"2011","unstructured":"Gjoka, M, Kurant M, Butts CT, Markopoulou A (2011) Practical recommendations on crawling online social networks. IEEE J Sel Areas Commun 29(9):1872\u20131892.","journal-title":"IEEE J Sel Areas Commun"},{"key":"201_CR15","unstructured":"Hagberg, AA, Schult DA, Swart PJ (2008) Exploring network structure, dynamics, and function using NetworkX In: Proceedings of the 7th Python in Science Conference (SciPy2008)."},{"key":"201_CR16","doi-asserted-by":"publisher","unstructured":"Hardiman, SJ, Katzir L (2013) Estimating clustering coefficients and size of social networks via random walk In: Proceedings of the 22nd international conference on World Wide Web, 539\u2013550.. ACM. https:\/\/doi.org\/10.1145\/2488388.2488436 .","DOI":"10.1145\/2488388.2488436"},{"key":"201_CR17","unstructured":"Haveliwala, T (1999) Efficient computation of pagerank. Tech Rep:1999\u201331."},{"key":"201_CR18","doi-asserted-by":"publisher","unstructured":"Haveliwala, TH (2002) Topic-sensitive pagerank In: Proceedings of the 11th international conference on World Wide Web, 517\u2013526.. ACM. https:\/\/doi.org\/10.1145\/511511.511513 .","DOI":"10.1145\/511511.511513"},{"key":"201_CR19","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/978-3-030-05411-3_9","volume-title":"Studies in Computational Intelligence","author":"Helge Holzmann","year":"2018","unstructured":"Holzmann, H, Anand A, Khosla M (2018) Delusive pagerank in incomplete graphs In: Complex Networks and Their Applications VII, 104\u2013117. https:\/\/doi.org\/10.1007\/978-3-030-05411-3_9 ."},{"key":"201_CR20","doi-asserted-by":"publisher","unstructured":"Holzmann, H, Nejdl W, Anand A (2016) The dawn of today\u2019s popular domains: A study of the archived german web over 18 years In: Digital Libraries (JCDL), 2016 IEEE\/ACM Joint Conference on, 73\u201382.. IEEE. https:\/\/doi.org\/10.1145\/2910896.2910901 .","DOI":"10.1145\/2910896.2910901"},{"key":"201_CR21","doi-asserted-by":"publisher","unstructured":"Holzmann, H, Nejdl W, Anand A (2017) Exploring web archives through temporal anchor texts In: Proceedings of the 2017 ACM on Web Science Conference, 289\u2013298.. ACM. https:\/\/doi.org\/10.1145\/3091478.3091500 .","DOI":"10.1145\/3091478.3091500"},{"key":"201_CR22","doi-asserted-by":"publisher","unstructured":"H\u00fcbler, C, Kriegel HP, Borgwardt K, Ghahramani Z (2008) Metropolis algorithms for representative subgraph sampling In: Data Mining, 2008. ICDM\u201908. Eighth IEEE International Conference on, 283\u2013292.. IEEE. https:\/\/doi.org\/10.1109\/icdm.2008.124 .","DOI":"10.1109\/icdm.2008.124"},{"key":"201_CR23","doi-asserted-by":"publisher","unstructured":"Huurdeman, HC, Ben-David A, Kamps J, Samar T, de Vries AP (2014) Finding pages on the unarchived web In: Proceedings of the 14th ACM\/IEEE-CS Joint Conference on Digital Libraries, 331\u2013340.. IEEE Press. https:\/\/doi.org\/10.1109\/jcdl.2014.6970188 .","DOI":"10.1109\/jcdl.2014.6970188"},{"key":"201_CR24","doi-asserted-by":"publisher","unstructured":"Katzir, L, Liberty E, Somekh O (2011) Estimating sizes of social networks via biased sampling In: Proceedings of the 20th international conference on World wide web, 597\u2013606.. ACM. https:\/\/doi.org\/10.1145\/1963405.1963489 .","DOI":"10.1145\/1963405.1963489"},{"issue":"1\/2","key":"201_CR25","doi-asserted-by":"publisher","first-page":"81","DOI":"10.2307\/2332226","volume":"30","author":"MG Kendall","year":"1938","unstructured":"Kendall, MG (1938) A new measure of rank correlation. Biometrika 30(1\/2):81\u201393.","journal-title":"Biometrika"},{"issue":"5","key":"201_CR26","doi-asserted-by":"publisher","first-page":"604","DOI":"10.1145\/324133.324140","volume":"46","author":"JM Kleinberg","year":"1999","unstructured":"Kleinberg, JM (1999) Authoritative sources in a hyperlinked environment. J ACM (JACM) 46(5):604\u2013632.","journal-title":"J ACM (JACM)"},{"key":"201_CR27","doi-asserted-by":"publisher","unstructured":"Leskovec, J, Faloutsos C (2006) Sampling from large graphs In: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, 631\u2013636.. ACM. https:\/\/doi.org\/10.1145\/1150402.1150479 .","DOI":"10.1145\/1150402.1150479"},{"issue":"1","key":"201_CR28","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1217299.1217301","volume":"1","author":"Jure Leskovec","year":"2007","unstructured":"Leskovec, J, Kleinberg J, Faloutsos C (2007) Graph evolution: Densification and shrinking diameters. ACM Trans Knowl Discov Data 1(1). https:\/\/doi.org\/10.1145\/1217299.1217301 .","journal-title":"ACM Transactions on Knowledge Discovery from Data"},{"key":"201_CR29","doi-asserted-by":"publisher","unstructured":"Li, RH, Yu JX, Qin L, Mao R, Jin T (2015) On random walk based graph sampling In: Data Engineering (ICDE), 2015 IEEE 31st International Conference on, 927\u2013938.. IEEE. https:\/\/doi.org\/10.1109\/icde.2015.7113345 .","DOI":"10.1109\/icde.2015.7113345"},{"key":"201_CR30","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1145\/2020408.2020431","volume-title":"Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"AS Maiya","year":"2011","unstructured":"Maiya, AS, Berger-Wolf TY (2011) Benefits of Bias: Towards Better Characterization of Network Sampling In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 105\u2013113.. ACM, New York. http:\/\/doi.acm.org\/10.1145\/2020408.2020431 , https:\/\/doi.org\/10.1145\/2020408.2020431 ."},{"key":"201_CR31","unstructured":"Ng, AY, Zheng AX, Jordan MI (2001a) Link analysis, eigenvectors and stability In: Proceedings of the 17th International Joint Conference on Artificial Intelligence - Volume 2, IJCAI\u201901, 903\u2013910.. Morgan Kaufmann Publishers Inc., San Francisco."},{"key":"201_CR32","doi-asserted-by":"crossref","unstructured":"Ng, AY, Zheng AX, Jordan MI (2001b) Stable algorithms for link analysis In: Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, 258\u2013266.. ACM, New York.","DOI":"10.1145\/383952.384003"},{"key":"201_CR33","doi-asserted-by":"crossref","unstructured":"Page, L, Brin S, Motwani R, Winograd T (1999) The PageRank Citation Ranking: Bringing Order to the Web In: Technical Report.. Stanford InfoLab. Previous number = SIDL-WP-1999-0120. http:\/\/ilpubs.stanford.edu:8090\/422\/ .","DOI":"10.1016\/B978-088415228-6.50166-0"},{"issue":"4","key":"201_CR34","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1016\/j.socnet.2013.09.003","volume":"35","author":"JA Smith","year":"2013","unstructured":"Smith, JA, Moody J (2013) Structural effects of network sampling coverage i: Nodes missing at random. Soc Netw 35(4):652\u2013668.","journal-title":"Soc Netw"},{"key":"201_CR35","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/j.socnet.2016.04.005","volume":"48","author":"JA Smith","year":"2017","unstructured":"Smith, JA, Moody J, Morgan JH (2017) Network sampling coverage ii: the effect of non-random missing data on network measurement. Soc Netw 48:78\u201399.","journal-title":"Soc Netw"},{"key":"201_CR36","unstructured":"The Internet Archive (Unknown Month 1996) The Internet Archive. http:\/\/archive.org ."},{"key":"201_CR37","first-page":"793","volume-title":"Proceedings of the 28th International Conference on International Conference on Machine Learning","author":"A Vattani","year":"2011","unstructured":"Vattani, A, Chakrabarti D, Gurevich M (2011) Preserving Personalized Pagerank in Subgraphs In: Proceedings of the 28th International Conference on International Conference on Machine Learning, 793\u2013800.. Omnipress, USA. http:\/\/dl.acm.org\/citation.cfm?id=3104482.3104582 ."},{"issue":"4","key":"201_CR38","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1016\/j.socnet.2012.01.003","volume":"34","author":"DJ Wang","year":"2012","unstructured":"Wang, DJ, Shi X, McFarland DA, Leskovec J (2012) Measurement error in network data: A re-classification. Soc Netw 34(4):396\u2013409.","journal-title":"Soc Netw"},{"issue":"4","key":"201_CR39","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1145\/1851275.1851231","volume":"40","author":"Tianyi Wang","year":"2010","unstructured":"Wang, T, Chen Y, Zhang Z, Sun P, Deng B, Li X (2010) Unbiased sampling in directed social graph In: ACM SIGCOMM Computer Communication Review, ACM, vol. 40, 401\u2013402. https:\/\/doi.org\/10.1145\/1851275.1851231 .","journal-title":"ACM SIGCOMM Computer Communication Review"},{"key":"201_CR40","doi-asserted-by":"publisher","unstructured":"Xin, RS, Gonzalez JE, Franklin MJ, Stoica I (2013) Graphx: A resilient distributed graph system on spark In: First International Workshop on Graph Data Management Experiences and Systems, GRADES \u201913. https:\/\/doi.org\/10.1145\/2484425.2484427 .","DOI":"10.1145\/2484425.2484427"},{"issue":"4","key":"201_CR41","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1145\/2847526","volume":"40","author":"Z Zhou","year":"2016","unstructured":"Zhou, Z, Zhang N, Gong Z, Das G (2016) Faster random walks by rewiring online social networks on-the-fly. ACM Trans Database Syst (TODS) 40(4):26.","journal-title":"ACM Trans Database Syst (TODS)"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-019-0201-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s41109-019-0201-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-019-0201-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,21]],"date-time":"2023-09-21T23:55:50Z","timestamp":1695340550000},"score":1,"resource":{"primary":{"URL":"https:\/\/appliednetsci.springeropen.com\/articles\/10.1007\/s41109-019-0201-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,22]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["201"],"URL":"https:\/\/doi.org\/10.1007\/s41109-019-0201-9","relation":{},"ISSN":["2364-8228"],"issn-type":[{"type":"electronic","value":"2364-8228"}],"subject":[],"published":{"date-parts":[[2019,10,22]]},"assertion":[{"value":"27 February 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 August 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 August 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 October 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare that they have no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"86"}}