{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T08:35:03Z","timestamp":1781253303091,"version":"3.54.1"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2008,3,1]],"date-time":"2008-03-01T00:00:00Z","timestamp":1204329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-0347933IIS-0713581"],"award-info":[{"award-number":["IIS-0347933IIS-0713581"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst."],"published-print":{"date-parts":[[2008,3]]},"abstract":"<jats:p>\n            Link-based ranking algorithms are among the most important techniques to improve web search. In particular, the PageRank algorithm has been successfully used in the Google search engine and has been attracting much attention recently. However, we find that PageRank has a \u201czero-one gap\u201d problem which, to the best of our knowledge, has not been addressed in any previous work. This problem can be potentially exploited to spam PageRank results and make the state-of-the-art link-based antispamming techniques ineffective. The zero-one gap problem arises as a result of the current ad hoc way of computing transition probabilities in the random surfing model. We therefore propose a novel\n            <jats:italic>DirichletRank<\/jats:italic>\n            algorithm which calculates these probabilities using Bayesian estimation with a Dirichlet prior. DirichletRank is a variant of PageRank, but does not have the problem of zero-one gap and can be analytically shown substantially more resistant to some link spams than PageRank. Experiment results on TREC data show that DirichletRank can achieve better retrieval accuracy than PageRank due to its more reasonable allocation of transition probabilities. More importantly, experiments on the TREC dataset and another real web dataset from the Webgraph project show that, compared with the original PageRank, DirichletRank is more stable under link perturbation and is significantly more robust against both manually identified web spams and several simulated link spams. DirichletRank can be computed as efficiently as PageRank, and thus is scalable to large-scale web applications.\n          <\/jats:p>","DOI":"10.1145\/1344411.1344416","type":"journal-article","created":{"date-parts":[[2008,4,8]],"date-time":"2008-04-08T15:40:00Z","timestamp":1207669200000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":35,"title":["DirichletRank"],"prefix":"10.1145","volume":"26","author":[{"given":"Xuanhui","family":"Wang","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tao","family":"Tao","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jian-Tao","family":"Sun","sequence":"additional","affiliation":[{"name":"Microsoft Research Asia, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Azadeh","family":"Shakery","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chengxiang","family":"Zhai","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2008,4,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148170.1148225"},{"key":"e_1_2_1_2_1","volume-title":"2nd International Workshop on Adversarial Information Retrieval on the Web.","author":"Becchetti L.","unstructured":"Becchetti , L. , Castillo , C. , Donato , D. , Leonardi , S. , and Baeza-Yates , R . 2006. Link-Based characterization and detection of Web spam . In 2nd International Workshop on Adversarial Information Retrieval on the Web. Becchetti, L., Castillo, C., Donato, D., Leonardi, S., and Baeza-Yates, R. 2006. Link-Based characterization and detection of Web spam. In 2nd International Workshop on Adversarial Information Retrieval on the Web."},{"key":"e_1_2_1_3_1","volume-title":"1st International Workshop on Adversarial Information Retrieval on the Web.","author":"Benczur A.","unstructured":"Benczur , A. , Csalogany , K. , Sarlos , T. , and Uher , M . 2005. SpamRank-Fully automatic link spam detection . In 1st International Workshop on Adversarial Information Retrieval on the Web. Benczur, A., Csalogany, K., Sarlos, T., and Uher, M. 2005. SpamRank-Fully automatic link spam detection. In 1st International Workshop on Adversarial Information Retrieval on the Web."},{"key":"e_1_2_1_4_1","first-page":"335","article-title":"A survey on PageRank computing","volume":"1","author":"Berkhin P.","year":"2005","unstructured":"Berkhin , P. 2005 . A survey on PageRank computing . Internet Math. 1 , 3, 335 -- 380 . Berkhin, P. 2005. A survey on PageRank computing. Internet Math. 1, 3, 335--380.","journal-title":"Internet Math."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/290941.290972"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1052934.1052938"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060745.1060827"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1052934.1052942"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/371920.372096"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008992.1009068"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the International World Wide Web Conference (WWW), 65--74","author":"Chakrabarti S.","unstructured":"Chakrabarti , S. , Dom , B. , Gibson , D. , Kleinberg , J. , Raghavan , P. , and Rajagopalan , S . 1998. Automatic resource list compilation by analyzing hyperlink structure and associated text . In Proceedings of the International World Wide Web Conference (WWW), 65--74 . Chakrabarti, S., Dom, B., Gibson, D., Kleinberg, J., Raghavan, P., and Rajagopalan, S. 1998. Automatic resource list compilation by analyzing hyperlink structure and associated text. In Proceedings of the International World Wide Web Conference (WWW), 65--74."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the International Conference on Machine Learning (ICML), 167--174","author":"Cohn D.","unstructured":"Cohn , D. and Chang , H . 2000. Learning to probabilistically identify authoritative documents . In Proceedings of the International Conference on Machine Learning (ICML), 167--174 . Cohn, D. and Chang, H. 2000. Learning to probabilistically identify authoritative documents. In Proceedings of the International Conference on Machine Learning (ICML), 167--174."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022649401552"},{"key":"e_1_2_1_15_1","volume-title":"Overview of the TREC 2003 Web track. In Proceedings of the 12th Text Retrieval Conference (TREC), 78--92","author":"Craswell N.","unstructured":"Craswell , N. and Hawking , D . 2003 . Overview of the TREC 2003 Web track. In Proceedings of the 12th Text Retrieval Conference (TREC), 78--92 . Craswell, N. and Hawking, D. 2003. Overview of the TREC 2003 Web track. In Proceedings of the 12th Text Retrieval Conference (TREC), 78--92."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/511446.511512"},{"key":"e_1_2_1_17_1","volume-title":"Tech. Rep. 49372 LBNL.","author":"Ding C. H. Q.","year":"2002","unstructured":"Ding , C. H. Q. , He , X. , Husbands , P. , Zha , H. , and Simon , H. D . 2002 . PageRank: HITS and a unified framework for link analysis. Tech. Rep. 49372 LBNL. Ding, C. H. Q., He, X., Husbands, P., Zha, H., and Simon, H. D. 2002. PageRank: HITS and a unified framework for link analysis. Tech. Rep. 49372 LBNL."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988714"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1017074.1017077"},{"key":"e_1_2_1_20_1","unstructured":"Golub G. H. and Loan C. F. V. 1996. Matrix Computations. Johns Hopkins University Press Baltimore MD.  Golub G. H. and Loan C. F. V. 1996. Matrix Computations. Johns Hopkins University Press Baltimore MD."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the Very Large DataBase (VLDB), 517--528","author":"Gyongyi Z.","unstructured":"Gyongyi , Z. and Garcia-Molina , H . 2005a. Link spam alliances . In Proceedings of the Very Large DataBase (VLDB), 517--528 . Gyongyi, Z. and Garcia-Molina, H. 2005a. Link spam alliances. In Proceedings of the Very Large DataBase (VLDB), 517--528."},{"key":"e_1_2_1_22_1","volume-title":"1st International Workshop on Adversarial Information Retrieval on the Web.","author":"Gyongyi Z.","unstructured":"Gyongyi , Z. and Garcia-Molina , H . 2005b. Web spam taxonomy . In 1st International Workshop on Adversarial Information Retrieval on the Web. Gyongyi, Z. and Garcia-Molina, H. 2005b. Web spam taxonomy. In 1st International Workshop on Adversarial Information Retrieval on the Web."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the International Conference on Very Large DataBase (VLDB), 576--587","author":"Gyongyi Z.","unstructured":"Gyongyi , Z. , Garcia-Molina , H. , and Pedersen , J . 2004. Combating Web spam with TrustRank . In Proceedings of the International Conference on Very Large DataBase (VLDB), 576--587 . Gyongyi, Z., Garcia-Molina, H., and Pedersen, J. 2004. Combating Web spam with TrustRank. In Proceedings of the International Conference on Very Large DataBase (VLDB), 576--587."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/511446.511513"},{"key":"e_1_2_1_25_1","unstructured":"Haveliwala T. H. and Kamwar S. D. 2003. The second Eigenvalue of the Google matrix. Tech. Rep. Stanford University. March.  Haveliwala T. H. and Kamwar S. D. 2003. The second Eigenvalue of the Google matrix. Tech. Rep. Stanford University. March."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022623210503"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775191"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775190"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324140"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10791-005-5661-0"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/511446.511514"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060745.1060829"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press UK.   Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press UK.","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/383952.384003"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1135777.1135794"},{"key":"e_1_2_1_36_1","unstructured":"Page L. Brin S. Motwani R. and Winograd T. 1999. The PageRank citation ranking: Bringing order to the Web. Tech. Rep. Stanford University. November.  Page L. Brin S. Motwani R. and Winograd T. 1999. The PageRank citation ranking: Bringing order to the Web. Tech. Rep. Stanford University. November."},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the Conference on Advances Neural Information Proving Systems (NIPS), 1441--1448","author":"Richardson M.","unstructured":"Richardson , M. and Domingos , P . 2002. The intelligent surfer: Probabilistic combination of link and content information in PageRank . In Proceedings of the Conference on Advances Neural Information Proving Systems (NIPS), 1441--1448 . Richardson, M. and Domingos, P. 2002. The intelligent surfer: Probabilistic combination of link and content information in PageRank. In Proceedings of the Conference on Advances Neural Information Proving Systems (NIPS), 1441--1448."},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the Conference on Advances Neural Information Proving Systems (NIPS), 697--704","author":"Steck H.","unstructured":"Steck , H. and Jaakkola , T . 2002. On the Dirichlet prior and Bayesian regularization . In Proceedings of the Conference on Advances Neural Information Proving Systems (NIPS), 697--704 . Steck, H. and Jaakkola, T. 2002. On the Dirichlet prior and Bayesian regularization. In Proceedings of the Conference on Advances Neural Information Proving Systems (NIPS), 697--704."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1076034.1076178"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1062745.1062762"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1135777.1135792"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1076034.1076068"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/564376.564387"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/383952.384019"},{"key":"e_1_2_1_45_1","volume-title":"Workshop on Algorithms and Models for the Web Graph.","author":"Zhang H.","unstructured":"Zhang , H. , Goel , A. , Govindan , R. , Mason , K. , and Roy , B. V . 2004. Improving Eigenvector-Based reputation systems against collusions . In Workshop on Algorithms and Models for the Web Graph. Zhang, H., Goel, A., Govindan, R., Mason, K., and Roy, B. V. 2004. Improving Eigenvector-Based reputation systems against collusions. In Workshop on Algorithms and Models for the Web Graph."}],"container-title":["ACM Transactions on Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1344411.1344416","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1344411.1344416","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:39:04Z","timestamp":1750253944000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1344411.1344416"}},"subtitle":["Solving the zero-one gap problem of PageRank"],"short-title":[],"issued":{"date-parts":[[2008,3]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,3]]}},"alternative-id":["10.1145\/1344411.1344416"],"URL":"https:\/\/doi.org\/10.1145\/1344411.1344416","relation":{},"ISSN":["1046-8188","1558-2868"],"issn-type":[{"value":"1046-8188","type":"print"},{"value":"1558-2868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,3]]},"assertion":[{"value":"2006-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-04-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}