cicyt UNIZAR
Full-text links:

Download:

Current browse context:

cs.DS

Change to browse by:

References & Citations

DBLP - CS Bibliography

Bookmark

(what is this?)
CiteULike logo BibSonomy logo Mendeley logo del.icio.us logo Digg logo Reddit logo ScienceWISE logo

Computer Science > Data Structures and Algorithms

Title: Closure Operators and Spam Resistance for PageRank

Abstract: We study the spammablility of ranking functions on the web. Although graph-theoretic ranking functions, such as Hubs and Authorities and PageRank exist, there is no graph theoretic notion of how spammable such functions are.
We introduce a very general cost model that only depends on the observation that changing the links of a page that you own is free, whereas changing the links on pages owned by others requires effort or money. We define spammability to be the ratio between the amount of benefit one receives for one's spamming efforts and the amount of effort/money one must spend to spam. The more effort/money it takes to get highly ranked, the less spammable the function.
Our model helps explain why both hubs and authorities and standard PageRank are very easy to spam. Although standard PageRank is easy to spam, we show that there exist spam-resistant PageRanks. Specifically, we propose a ranking method, Min-k-PPR, that is the component-wise min of a set of personalized PageRanks centered on k trusted sites. Our main results are that Min-k-PPR is, itself, a type of PageRank and that it is expensive to spam.
We elucidate a surprisingly elegant algebra for PageRank. We define the space of all possible PageRanks and show that this space is closed under some operations. Most notably, we show that PageRanks are closed under (normalized) component-wise min, which establishes that (normalized) Min-k-PPRis a PageRank. This algebraic structure is also key to demonstrating the spam resistance of Min-k-PPR.
Comments: 19 pages
Subjects: Data Structures and Algorithms (cs.DS); Social and Information Networks (cs.SI)
Cite as: arXiv:1803.05001 [cs.DS]
  (or arXiv:1803.05001v2 [cs.DS] for this version)

Submission history

From: Martín Farach-Colton [view email]
[v1] Tue, 13 Mar 2018 18:52:21 GMT (19kb)
[v2] Thu, 15 Mar 2018 10:57:38 GMT (19kb)