TY - GEN

T1 - Graph Ranking and the Cost of Sybil Defense

AU - Farach-Colton, Gwendolyn

AU - Farach-Colton, Martin

AU - Goldberg, Leslie Ann

AU - Komlos, Hanna

AU - Lapinskas, John

AU - Levi, Reut

AU - Medina, Moti

AU - Mosteiro, Miguel A.

N1 - Publisher Copyright:
© 2023 ACM.

PY - 2023/7/9

Y1 - 2023/7/9

N2 - Ranking functions such as PageRank assign numeric values (ranks) to nodes of graphs, most notably the web graph. Node rankings are an integral part of Internet search algorithms, since they can be used to order the results of queries. However, these ranking functions are famously subject to attacks by spammers, who modify the web graph in order to give their own pages more rank.We characterize the interplay between rankers and spammers as a game. We define the two critical features of this game, spam resistance and distortion, based on how spammers spam and how rankers protect against spam. We observe that all the ranking functions that are well-studied in the literature, including the original formulation of PageRank, have poor spam resistance, poor distortion, or both.Finally, we study Min-PPR, the form of PageRank used at Google itself, but which has received no (theoretical or empirical) treatment in the literature. We prove that Min-PPR has low distortion and high spam resistance. A secondary benefit is that Min-PPR comes with an explicit cost function on nodes that shows how important they are to the spammer; thus a ranker can focus their spam-detection capacity on these vulnerable nodes. Both Min-PPR and its associated cost function are straightforward to compute.

AB - Ranking functions such as PageRank assign numeric values (ranks) to nodes of graphs, most notably the web graph. Node rankings are an integral part of Internet search algorithms, since they can be used to order the results of queries. However, these ranking functions are famously subject to attacks by spammers, who modify the web graph in order to give their own pages more rank.We characterize the interplay between rankers and spammers as a game. We define the two critical features of this game, spam resistance and distortion, based on how spammers spam and how rankers protect against spam. We observe that all the ranking functions that are well-studied in the literature, including the original formulation of PageRank, have poor spam resistance, poor distortion, or both.Finally, we study Min-PPR, the form of PageRank used at Google itself, but which has received no (theoretical or empirical) treatment in the literature. We prove that Min-PPR has low distortion and high spam resistance. A secondary benefit is that Min-PPR comes with an explicit cost function on nodes that shows how important they are to the spammer; thus a ranker can focus their spam-detection capacity on these vulnerable nodes. Both Min-PPR and its associated cost function are straightforward to compute.

UR - http://www.scopus.com/inward/record.url?scp=85168159974&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85168159974&partnerID=8YFLogxK

U2 - 10.1145/3580507.3597782

DO - 10.1145/3580507.3597782

M3 - Conference contribution

AN - SCOPUS:85168159974

T3 - EC 2023 - Proceedings of the 24th ACM Conference on Economics and Computation

SP - 586

EP - 625

BT - EC 2023 - Proceedings of the 24th ACM Conference on Economics and Computation

PB - Association for Computing Machinery, Inc

T2 - 24th ACM Conference on Economics and Computation, EC 2023

Y2 - 9 July 2023 through 12 July 2023

ER -