Link Analysis

Description

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.

Related Problems

Related: InDegree Analysis

Parameters

$n$: number of pages

$m$: number of hyperlinks

$z$: # of topics/categories

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
The PAGERANK Algorithm	1998	$O(m n )$	$O(n)$	Exact	Deterministic	Time
The (Hyperlink-Induced Topic Search) HITS Algorithm	1998	$O(n^{2} k)$	$O(n)$	Exact	Deterministic	Time
Kleinberg	1998	$O(m^{2} n )$		Exact	Deterministic	Time
The (Stochastic Approach for Link Structure Analysis) SALSA Algorithm	2000	$O(m^{2} n )$	$O(n)$?	Exact	Deterministic	Time
Randomized HITS	2001	$O(m n\log n )$	$O(n)$	Exact	Deterministic	Time
PHITS Coheng Chan	2000	$O(m n )$	$O(nz)$?	Exact	Deterministic	Time
Haveliwala	2002	$O(m n )$	$O(nz)$?	Exact	Deterministic	Time
Jeh and Widom	2003	$O(m n )$	$O(nh)$	Exact	Deterministic	Time
Richardson and Domingos	2002	$O(m n )$	$O(nl)$	Exact	Deterministic	Time
Tomlin	2003	$O(m n )$	$O(n)$?	Exact	Deterministic	Time
Achlioptas	2001	$O(mn )$	$O((n+l)$^{2})?	Exact	Deterministic	Time

Time Complexity Graph