3 ms·

> The HITS algorithm has one drawback that it is super easy to game it. PageRank is not entirely resistant, but its a little more robust. > Create a harvester

by samhw 4y ago

> The HITS algorithm has one drawback that it is super easy to game it. PageRank is not entirely resistant, but its a little more robust. > Create a harvester page that points to lots and lots of popular, high traffic pages on the internet. By virtue of doing this it can accumulate a lot of Hubs score which it can redirect as an Authority score to an intended page. I'm not sure how HITS is any more "easy to game" than PageRank? As far as I understand it, the differences are almost entirely limited to performance characteristics, not semantics. The example you give doesn't seem to be specific to HITS (as opposed to PageRank) in any way. (I'm also not sure how "game theory" is relevant here, unless by "game theory" you just mean "the idea that people will try to game it".)

srean 4y ago
One could pose this as an adversarial game. For the simplistic case consider two participants -- (i) the ranker that chooses a ranking scheme (we need to constrain the space of ranking schemes somehow for this to lead to any useful formulation), (ii) web page who tries to outrank other pages by strategically linking to other pages, and possibly buying links to itself from other pages. One can give (ii) a budget to add and delete links and pages that it can control. In this framework one then try to compute what's an equilibrium strategy. The multiplayer version is a lot more complicated. If you check my original comment, I gave a simple scheme to attack HITS rank. The main drawback is that one can 'harvest' Authority score using 'out-links'. Outlinks are cheap and easy, compared to 'inlinks'. Sybil attack is a little harder for Pagerank.
- samhw 4y ago
  > If you check my original comment I gave a simple scheme to attack HITS rank. Sybil attack is a little harder for Pagerank. OK, but how is it harder for PageRank? I can't really see any differences in the semantics of the two algorithms, so I'm not sure what kind of added vulnerability one or the other could have. > One could pose this as an adversarial game. Yeah, I appreciate that, that's what I was referring to as "the idea that people will try to game it". It's not really the kind of 'game' that would be considered in game theory, though, because it doesn't have any interesting or emergent properties - the designer's response will just be "oh yeah we should stop people gaming our algorithm".
  - srean 4y ago
    > OK, but how is it harder for PageRank? If you are familiar with the algorithms, which I assume you are, you can work it out. To make my page score high on the PageRank score I need to acquire links from high PageRank score pages. This is a lot harder because it depends on a) in-links and b) high PageRank pages. With Hits, its easy for one page to harvest a high Hub score. All that is needed is to outlink to known good pages (authority). Providing outlinks is trivial. Once so harvested, one can direct that flow to a designated page to give it a high Authority score. > It's not really the kind of 'game' that would be considered in game theory Why not ? Formalize the strategy spaces of both the players and its a very valid game in the Game Theory sense. For the ranker you have to consider some functional space of functions over a graph. For the page player it has a budget of alterations it can make to the graph.
    - samhw 4y ago
      > With Hits, its easy for one page to harvest a high Hub score. All that is needed is to outlink to known good pages (authority). Providing outlinks is trivial. Once so harvested, one can direct that flow to a designated page to give it a high Authority score. Are you saying that you think HITS doesn't recursively score the quality of references by their own scores? That's not true. It does exactly what PageRank does in that respect: a page's score depends on the score of those which reference it, which in turn depends on... etc. The 'hub' vs 'authority' distinction is interesting but not really relevant here: we're considering a page's 'authority' score, which depends on the 'hub' score of those who outlink to it, and at that point we're just doing PageRank [again, except performance-wise and arguably freshness-wise]. Like I said: the only non-trivial differences between them are implementation / performance-related, not semantic. > Why not ? Formalize the strategy spaces of both the players and its a very valid game in the Game Theory sense. For the ranker you have to consider some functional space of functions over a graph. Yes, again: possible to frame it as a formally valid problem if you really want to; still not an interesting one. We're only talking about this because you want to maintain that your earlier statement was true. "You have to consider some functional space of functions over a graph" gives no detail (besides that, yes, you can model something–maybe documents, maybe people, who knows?–as a graph) and sounds like something written by a person with a gun to their head. Or maybe I'm wrong and there's a fascinating problem which you just don't want to divulge to me.

by samhw 4y ago

srean 4y ago

One could pose this as an adversarial game. For the simplistic case consider two participants -- (i) the ranker that chooses a ranking scheme (we need to constrain the space of ranking schemes somehow for this to lead to any useful formulation), (ii) web page who tries to outrank other pages by strategically linking to other pages, and possibly buying links to itself from other pages. One can give (ii) a budget to add and delete links and pages that it can control. In this framework one then try to compute what's an equilibrium strategy. The multiplayer version is a lot more complicated. If you check my original comment, I gave a simple scheme to attack HITS rank. The main drawback is that one can 'harvest' Authority score using 'out-links'. Outlinks are cheap and easy, compared to 'inlinks'. Sybil attack is a little harder for Pagerank.

samhw 4y ago
> If you check my original comment I gave a simple scheme to attack HITS rank. Sybil attack is a little harder for Pagerank. OK, but how is it harder for PageRank? I can't really see any differences in the semantics of the two algorithms, so I'm not sure what kind of added vulnerability one or the other could have. > One could pose this as an adversarial game. Yeah, I appreciate that, that's what I was referring to as "the idea that people will try to game it". It's not really the kind of 'game' that would be considered in game theory, though, because it doesn't have any interesting or emergent properties - the designer's response will just be "oh yeah we should stop people gaming our algorithm".
- srean 4y ago
  > OK, but how is it harder for PageRank? If you are familiar with the algorithms, which I assume you are, you can work it out. To make my page score high on the PageRank score I need to acquire links from high PageRank score pages. This is a lot harder because it depends on a) in-links and b) high PageRank pages. With Hits, its easy for one page to harvest a high Hub score. All that is needed is to outlink to known good pages (authority). Providing outlinks is trivial. Once so harvested, one can direct that flow to a designated page to give it a high Authority score. > It's not really the kind of 'game' that would be considered in game theory Why not ? Formalize the strategy spaces of both the players and its a very valid game in the Game Theory sense. For the ranker you have to consider some functional space of functions over a graph. For the page player it has a budget of alterations it can make to the graph.
  - samhw 4y ago
    > With Hits, its easy for one page to harvest a high Hub score. All that is needed is to outlink to known good pages (authority). Providing outlinks is trivial. Once so harvested, one can direct that flow to a designated page to give it a high Authority score. Are you saying that you think HITS doesn't recursively score the quality of references by their own scores? That's not true. It does exactly what PageRank does in that respect: a page's score depends on the score of those which reference it, which in turn depends on... etc. The 'hub' vs 'authority' distinction is interesting but not really relevant here: we're considering a page's 'authority' score, which depends on the 'hub' score of those who outlink to it, and at that point we're just doing PageRank [again, except performance-wise and arguably freshness-wise]. Like I said: the only non-trivial differences between them are implementation / performance-related, not semantic. > Why not ? Formalize the strategy spaces of both the players and its a very valid game in the Game Theory sense. For the ranker you have to consider some functional space of functions over a graph. Yes, again: possible to frame it as a formally valid problem if you really want to; still not an interesting one. We're only talking about this because you want to maintain that your earlier statement was true. "You have to consider some functional space of functions over a graph" gives no detail (besides that, yes, you can model something–maybe documents, maybe people, who knows?–as a graph) and sounds like something written by a person with a gun to their head. Or maybe I'm wrong and there's a fascinating problem which you just don't want to divulge to me.