{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:34:33Z","timestamp":1750224873509,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":54,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,7,7]],"date-time":"2023-07-07T00:00:00Z","timestamp":1688688000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS2118620","CCF2106999"],"award-info":[{"award-number":["CNS2118620","CCF2106999"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1867\/20","867\/19"],"award-info":[{"award-number":["1867\/20","867\/19"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,7,9]]},"DOI":"10.1145\/3580507.3597782","type":"proceedings-article","created":{"date-parts":[[2023,7,7]],"date-time":"2023-07-07T14:19:22Z","timestamp":1688739562000},"page":"586-625","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Graph Ranking and the Cost of Sybil Defense"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-2882-8626","authenticated-orcid":false,"given":"Gwendolyn","family":"Farach-Colton","sequence":"first","affiliation":[{"name":"Rutgers University, New Brunswick, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3616-7788","authenticated-orcid":false,"given":"Martin","family":"Farach-Colton","sequence":"additional","affiliation":[{"name":"Rutgers University, New Brunswick, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1879-6089","authenticated-orcid":false,"given":"Leslie Ann","family":"Goldberg","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5522-9193","authenticated-orcid":false,"given":"Hanna","family":"Komlos","sequence":"additional","affiliation":[{"name":"Rutgers University, New Brunswick, United States of America"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3197-0854","authenticated-orcid":false,"given":"John","family":"Lapinskas","sequence":"additional","affiliation":[{"name":"Bristol University, Bristol, United Kingdom"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3167-1766","authenticated-orcid":false,"given":"Reut","family":"Levi","sequence":"additional","affiliation":[{"name":"Reichman University, Herzliya, Israel"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5572-3754","authenticated-orcid":false,"given":"Moti","family":"Medina","sequence":"additional","affiliation":[{"name":"Bar Ilan University, Ramat Gan, Israel"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5842-6256","authenticated-orcid":false,"given":"Miguel A.","family":"Mosteiro","sequence":"additional","affiliation":[{"name":"Pace University, New York, United States of America"}]}],"member":"320","published-online":{"date-parts":[[2023,7,7]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms. SIAM, 1661--1668","author":"Addario-Berry Louigi","year":"2012","unstructured":"Louigi Addario-Berry and Tao Lei . 2012 . The mixing time of the Newman-Watts small world . In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms. SIAM, 1661--1668 . Louigi Addario-Berry and Tao Lei. 2012. The mixing time of the Newman-Watts small world. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms. SIAM, 1661--1668."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1609067.1609070"},{"key":"e_1_3_2_1_3_1","volume-title":"Diameter of the world-wide web. nature 401, 6749","author":"Albert R\u00e9ka","year":"1999","unstructured":"R\u00e9ka Albert , Hawoong Jeong , and Albert-L\u00e1szl\u00f3 Barab\u00e1si . 1999. Diameter of the world-wide web. nature 401, 6749 ( 1999 ), 130. R\u00e9ka Albert, Hawoong Jeong, and Albert-L\u00e1szl\u00f3 Barab\u00e1si. 1999. Diameter of the world-wide web. nature 401, 6749 (1999), 130."},{"key":"e_1_3_2_1_4_1","first-page":"3","article-title":"Communities, random walks, and social Sybil defense","volume":"10","author":"Alvisi Lorenzo","year":"2014","unstructured":"Lorenzo Alvisi , Allen Clement , Alessandro Epasto , Silvio Lattanzi , and Alessandro Panconesi . 2014 . Communities, random walks, and social Sybil defense . Internet Mathematics 10 , 3 -- 4 (2014), 360--420. Lorenzo Alvisi, Allen Clement, Alessandro Epasto, Silvio Lattanzi, and Alessandro Panconesi. 2014. Communities, random walks, and social Sybil defense. Internet Mathematics 10, 3--4 (2014), 360--420.","journal-title":"Internet Mathematics"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1451983.1452000"},{"key":"e_1_3_2_1_6_1","volume-title":"Foundations of Computer Science, 2006. FOCS'06. 47th Annual IEEE Symposium on. IEEE, 475--486","author":"Andersen Reid","year":"2006","unstructured":"Reid Andersen , Fan Chung , and Kevin Lang . 2006 . Local graph partitioning using PageRank vectors . In Foundations of Computer Science, 2006. FOCS'06. 47th Annual IEEE Symposium on. IEEE, 475--486 . Reid Andersen, Fan Chung, and Kevin Lang. 2006. Local graph partitioning using PageRank vectors. In Foundations of Computer Science, 2006. FOCS'06. 47th Annual IEEE Symposium on. IEEE, 475--486."},{"volume-title":"Advances in Data and Web Management","author":"Asano Yasuhito","key":"e_1_3_2_1_7_1","unstructured":"Yasuhito Asano , Yu Tezuka , and Takao Nishizeki . 2007. Improvements of HITS algorithms for spam links . In Advances in Data and Web Management . Springer , 479--490. Yasuhito Asano, Yu Tezuka, and Takao Nishizeki. 2007. Improvements of HITS algorithms for spam links. In Advances in Data and Web Management. Springer, 479--490."},{"key":"e_1_3_2_1_8_1","unstructured":"Ricardo A. Baeza-Yates Carlos Castillo and Vicente L\u00f3pez. 2005. PageRank Increase under Different Collusion Topologies. In AIRWeb. 17--24.  Ricardo A. Baeza-Yates Carlos Castillo and Vicente L\u00f3pez. 2005. PageRank Increase under Different Collusion Topologies. In AIRWeb. 17--24."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/1929861.1929864"},{"key":"e_1_3_2_1_10_1","volume-title":"Emergence of scaling in random networks. science 286, 5439","author":"Barab\u00e1si Albert-L\u00e1szl\u00f3","year":"1999","unstructured":"Albert-L\u00e1szl\u00f3 Barab\u00e1si and R\u00e9ka Albert . 1999. Emergence of scaling in random networks. science 286, 5439 ( 1999 ), 509--512. Albert-L\u00e1szl\u00f3 Barab\u00e1si and R\u00e9ka Albert. 1999. Emergence of scaling in random networks. science 286, 5439 (1999), 509--512."},{"key":"e_1_3_2_1_11_1","volume-title":"First Workshop on the Economics of Networked Systems (Netecon?06)","author":"Bhattacharjee Rajat","year":"2006","unstructured":"Rajat Bhattacharjee and Ashish Goel . 2006 . Incentive based ranking mechanisms . In First Workshop on the Economics of Networked Systems (Netecon?06) . 62--68. Rajat Bhattacharjee and Ashish Goel. 2006. Incentive based ranking mechanisms. In First Workshop on the Economics of Networked Systems (Netecon?06). 62--68."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"e_1_3_2_1_13_1","volume-title":"Graph structure in the web. Computer networks 33, 1--6","author":"Broder Andrei","year":"2000","unstructured":"Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , and Janet Wiener . 2000. Graph structure in the web. Computer networks 33, 1--6 ( 2000 ), 309--320. Andrei Broder, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Sridhar Rajagopalan, Raymie Stata, Andrew Tomkins, and Janet Wiener. 2000. Graph structure in the web. Computer networks 33, 1--6 (2000), 309--320."},{"key":"e_1_3_2_1_14_1","unstructured":"Alice Cheng and Eric Friedman. 2006. Manipulability of PageRank under Sybil strategies.  Alice Cheng and Eric Friedman. 2006. Manipulability of PageRank under Sybil strategies."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.05.007"},{"key":"e_1_3_2_1_16_1","volume-title":"On power-law relationships of the Internet topology. ACM SIGCOMM computer communication review 29, 4","author":"Faloutsos Michalis","year":"1999","unstructured":"Michalis Faloutsos , Petros Faloutsos , and Christos Faloutsos . 1999. On power-law relationships of the Internet topology. ACM SIGCOMM computer communication review 29, 4 ( 1999 ), 251--262. Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. 1999. On power-law relationships of the Internet topology. ACM SIGCOMM computer communication review 29, 4 (1999), 251--262."},{"key":"e_1_3_2_1_17_1","unstructured":"Mart\u00edn Farach-Colton. [n. d.]. Personal communication from Google employee Number 110.  Mart\u00edn Farach-Colton. [n. d.]. Personal communication from Google employee Number 110."},{"key":"e_1_3_2_1_18_1","volume-title":"International journal of neural systems 28, 02","author":"McKay Fletcher Jack","year":"2016","unstructured":"Jack McKay Fletcher and Thomas Wennekers . 2016. From structure to activity: Using centrality measures to predict neuronal activity . International journal of neural systems 28, 02 ( 2016 ), 1750013. Jack McKay Fletcher and Thomas Wennekers. 2016. From structure to activity: Using centrality measures to predict neuronal activity. International journal of neural systems 28, 02 (2016), 1750013."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2005.10129104"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2010.5462078"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/781027.781046"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/140976649"},{"key":"e_1_3_2_1_23_1","unstructured":"Google [n. d.]. Google Online Link Spam Notification Form. https:\/\/www.google.com\/webmasters\/tools\/paidlinks?hl=enAccessed: 10\/30\/2017.  Google [n. d.]. Google Online Link Spam Notification Form. https:\/\/www.google.com\/webmasters\/tools\/paidlinks?hl=enAccessed: 10\/30\/2017."},{"key":"e_1_3_2_1_24_1","unstructured":"Google 2001. Google Press Center: Fun Facts. https:\/\/web.archive.org\/web\/20010715123343\/https:\/\/www.google.com\/press\/funfacts.html. Accessed on 10\/28\/2017.  Google 2001. Google Press Center: Fun Facts. https:\/\/web.archive.org\/web\/20010715123343\/https:\/\/www.google.com\/press\/funfacts.html. Accessed on 10\/28\/2017."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488433"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1182635.1164166"},{"key":"e_1_3_2_1_28_1","unstructured":"Zolt\u00e1n Gy\u00f6ngyi and Hector Garcia-Molina. 2005. Link Spam Alliances. In VLDB. ACM 517--528.  Zolt\u00e1n Gy\u00f6ngyi and Hector Garcia-Molina. 2005. Link Spam Alliances. In VLDB. ACM 517--528."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316740"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2003.1208999"},{"key":"e_1_3_2_1_31_1","first-page":"1","article-title":"Manipulation-resistant reputations using hitting time","volume":"5","author":"Hopcroft John","year":"2008","unstructured":"John Hopcroft and Daniel Sheldon . 2008 . Manipulation-resistant reputations using hitting time . Internet Mathematics 5 , 1 -- 2 (2008), 71--90. John Hopcroft and Daniel Sheldon. 2008. Manipulation-resistant reputations using hitting time. Internet Mathematics 5, 1--2 (2008), 71--90.","journal-title":"Internet Mathematics"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btq680"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775191"},{"key":"e_1_3_2_1_34_1","volume-title":"Proceedings of the 2012 ACM Conference on Ubiquitous Computing. ACM, 980--987","author":"Jin Zhaoyan","year":"2012","unstructured":"Zhaoyan Jin , Dianxi Shi , Quanyuan Wu , Huining Yan , and Hua Fan . 2012 . LBSNRank: personalized PageRank on location-based social networks . In Proceedings of the 2012 ACM Conference on Ubiquitous Computing. ACM, 980--987 . Zhaoyan Jin, Dianxi Shi, Quanyuan Wu, Huining Yan, and Hua Fan. 2012. LBSNRank: personalized PageRank on location-based social networks. In Proceedings of the 2012 ACM Conference on Ubiquitous Computing. ACM, 980--987."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1214\/17-AAP1323"},{"key":"e_1_3_2_1_36_1","volume-title":"authorities, and communities. ACM computing surveys (CSUR) 31, 4es","author":"Kleinberg Jon M","year":"1999","unstructured":"Jon M Kleinberg . 1999. Hubs , authorities, and communities. ACM computing surveys (CSUR) 31, 4es ( 1999 ), 5. Jon M Kleinberg. 1999. Hubs, authorities, and communities. ACM computing surveys (CSUR) 31, 4es (1999), 5."},{"key":"e_1_3_2_1_37_1","volume-title":"Hyperbolic geometry of complex networks. Physical Review E 82","author":"Krioukov Dimitri","year":"2010","unstructured":"Dimitri Krioukov , Fragkiskos Papadopoulos , Maksim Kitsak , Amin Vahdat , and Mari\u00e1n Bogu n\u00e1. 2010. Hyperbolic geometry of complex networks. Physical Review E 82 ( 2010 ). Issue 3. Dimitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Mari\u00e1n Bogu n\u00e1. 2010. Hyperbolic geometry of complex networks. Physical Review E 82 (2010). Issue 3."},{"key":"e_1_3_2_1_38_1","first-page":"37","article-title":"Web spam detection with anti-trust rank","volume":"6","author":"Krishnan Vijay","year":"2006","unstructured":"Vijay Krishnan and Rashmi Raj . 2006 . Web spam detection with anti-trust rank .. In AIRWeb , Vol. 6. 37 -- 40 . Vijay Krishnan and Rashmi Raj. 2006. Web spam detection with anti-trust rank.. In AIRWeb, Vol. 6. 37--40.","journal-title":"AIRWeb"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1149121.1149123"},{"key":"e_1_3_2_1_40_1","unstructured":"David Asher Levin Yuval Peres and Elizabeth Lee Wilmer. 2009. Markov chains and mixing times. American Mathematical Soc.  David Asher Levin Yuval Peres and Elizabeth Lee Wilmer. 2009. Markov chains and mixing times. American Mathematical Soc."},{"key":"e_1_3_2_1_41_1","volume-title":"Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Systems, 1124--1132","author":"Liu Brandon K","year":"2016","unstructured":"Brandon K Liu , David C Parkes , and Sven Seuken . 2016 . Personalized hitting time for informative trust mechanisms despite Sybils . In Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Systems, 1124--1132 . Brandon K Liu, David C Parkes, and Sven Seuken. 2016. Personalized hitting time for informative trust mechanisms despite Sybils. In Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Systems, 1124--1132."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.06.009"},{"volume-title":"Probability and Computing","author":"Mitzenmacher Michael","key":"e_1_3_2_1_43_1","unstructured":"Michael Mitzenmacher and Eli Upfal . 2005. Probability and Computing . Cambridge University Press . Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing. Cambridge University Press."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1879141.1879191"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0375-9601(99)00757-4"},{"key":"e_1_3_2_1_46_1","volume-title":"Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI 2001","author":"Ng Andrew Y.","year":"2001","unstructured":"Andrew Y. Ng , Alice X. Zheng , and Michael I. Jordan . 2001a. Link Analysis, Eigenvectors and Stability . In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI 2001 , Seattle, Washington, USA, August 4--10 , 2001 . 903--910. Andrew Y. Ng, Alice X. Zheng, and Michael I. Jordan. 2001a. Link Analysis, Eigenvectors and Stability. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI 2001, Seattle, Washington, USA, August 4--10, 2001. 903--910."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/383952.384003"},{"key":"e_1_3_2_1_49_1","unstructured":"StatCounter. [n. d.]. Search Engine Market Share. http:\/\/gs.statcounter.com\/search-engine-market-share. Accessed: 10\/30\/2017.  StatCounter. [n. d.]. Search Engine Market Share. http:\/\/gs.statcounter.com\/search-engine-market-share. Accessed: 10\/30\/2017."},{"key":"e_1_3_2_1_50_1","unstructured":"Danny Sullivan. [n. d.]. Google Has New Head Of Web Spam But Won't Be The \"New Matt Cutts\". https:\/\/searchengineland.com\/google-head-web-spam-221482. Accessed on 5\/17\/2019.  Danny Sullivan. [n. d.]. Google Has New Head Of Web Spam But Won't Be The \"New Matt Cutts\". https:\/\/searchengineland.com\/google-head-web-spam-221482. Accessed on 5\/17\/2019."},{"key":"e_1_3_2_1_51_1","volume-title":"The anatomy of the Facebook social graph. arXiv preprint arXiv:1111.4503","author":"Ugander Johan","year":"2011","unstructured":"Johan Ugander , Brian Karrer , Lars Backstrom , and Cameron Marlow . 2011. The anatomy of the Facebook social graph. arXiv preprint arXiv:1111.4503 ( 2011 ). Johan Ugander, Brian Karrer, Lars Backstrom, and Cameron Marlow. 2011. The anatomy of the Facebook social graph. arXiv preprint arXiv:1111.4503 (2011)."},{"key":"e_1_3_2_1_52_1","unstructured":"University of Milan Laboratory of Web Algorithmics. 2007. Web Spam Collections. http:\/\/chato.cl\/webspam\/datasets\/ URLs retrieved 04\/2020.  University of Milan Laboratory of Web Algorithmics. 2007. Web Spam Collections. http:\/\/chato.cl\/webspam\/datasets\/ URLs retrieved 04\/2020."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1851275.1851226"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2034575.2034593"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2009.2034047"},{"key":"e_1_3_2_1_56_1","volume-title":"SybilGuard: defending against Sybil attacks via social networks","author":"Yu Haifeng","year":"2008","unstructured":"Haifeng Yu , Michael Kaminsky , Phillip B Gibbons , and Abraham D Flaxman . 2008. SybilGuard: defending against Sybil attacks via social networks . IEEE\/ACM Transactions on networking 16, 3 ( 2008 ), 576--589. Haifeng Yu, Michael Kaminsky, Phillip B Gibbons, and Abraham D Flaxman. 2008. SybilGuard: defending against Sybil attacks via social networks. IEEE\/ACM Transactions on networking 16, 3 (2008), 576--589."}],"event":{"name":"EC '23: 24th ACM Conference on Economics and Computation","sponsor":["SIGecom Special Interest Group on Economics and Computation"],"location":"London United Kingdom","acronym":"EC '23"},"container-title":["Proceedings of the 24th ACM Conference on Economics and Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3580507.3597782","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3580507.3597782","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:57Z","timestamp":1750182537000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3580507.3597782"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,7]]},"references-count":54,"alternative-id":["10.1145\/3580507.3597782","10.1145\/3580507"],"URL":"https:\/\/doi.org\/10.1145\/3580507.3597782","relation":{},"subject":[],"published":{"date-parts":[[2023,7,7]]},"assertion":[{"value":"2023-07-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}