Link Analysis

Unlike "flat" document collections, the World Wide Web is hypertext and provides considerable auxiliary information on top of the text of the web pages, such as link structure and link text. With link analysis, we take advantage of the link structure of the Web to produce a global "importance" ranking of every web page that helps search engines and users quickly make sense of the vast heterogeneity of the World Wide Web.

Parameters

$n$ : number of pages
$m$ : number of hyperlinks
$z$ : # of topics/categories

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 10 of 10 algorithms


Jeh and Widom	2003	$O(mn)$	$O(nh)$
Tomlin	2003	$O(mn)$	$O(n)$
Haveliwala	2002	$O(mn)$	$O(nz)$
Richardson and Domingos	2002	$O(mn)$	$O(nl)$
Randomized HITS	2001	$O(mn \log n)$	$O(n)$
Achlioptas	2001	$O(mn)$	$O((n+l)^2)$
The (Stochastic Approach for Link Structure Analysis) SALSA Algorithm	2000	$O(m^2 n)$	$O(n)$
PHITS Coheng Chan	2000	$O(mn)$	$O(nz)$
The PAGERANK Algorithm	1998	$O(n^3)$	$O(n)$
The (Hyperlink-Induced Topic Search) HITS Algorithm	1998	$O(n^2 k)$	$O(n)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms