Paper Info
Title
NCDawareRank: a novel ranking method that exploits the decomposable structure of the web
Abstract
Research about the topological characteristics of the hyperlink graph has shown that Web possesses a nested block structure, indicative of its innate hierarchical organization. This crucial observation opens the way for new approaches that can usefully regard Web as a Nearly Completely Decomposable(NCD) system; In recent years, such approaches gave birth to various efficient methods and algorithms that exploit NCD from a computational point of view and manage to considerably accelerate the extraction of the PageRank vector. However, very little have been done towards the qualitative exploitation of NCD. In this paper we propose NCDawareRank, a novel ranking method that uses the intuition behind NCD to generalize and refine PageRank. NCDawareRank considers both the link structure and the hierarchical nature of the Web in a way that preserves the mathematically attractive characteristics of PageRank and at the same time manages to successfully resolve many of its known problems, including Web Spamming Susceptibility and Biased Ranking of Newly Emerging Pages. Experimental results show that NCDawareRank is more resistant to direct manipulation, alleviates the problems caused by the sparseness of the link graph and assigns more reasonable ranking scores to newly added pages, while maintaining the ability to be easily implemented on a large-scale and in a computationally efficient manner.
Year
DOI
Venue
2013
10.1145/2433396.2433415
WSDM
Keywords
Field
DocType
web spamming susceptibility,innate hierarchical organization,nested block structure,novel ranking method,decomposable structure,link structure,hyperlink graph,pagerank vector,hierarchical nature,regard web,computationally efficient manner,link graph,link analysis,ranking,sparsity
PageRank,Data mining,World Wide Web,Ranking,Computer science,Link analysis,Theoretical computer science,Exploit,Hyperlink,Link farm,Spamming,Hierarchical organization
Conference
Citations 
PageRank 
References 
12
0.65
22
Authors
2
Name
Order
Citations
PageRank
Athanasios N. Nikolakopoulos1599.02
John D. Garofalakis217636.73