Link Analysis (Link Analysis)
Jump to navigation
Jump to search
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
No parameters found.
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 nlogn )$ | $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
Error creating thumbnail: Unable to save thumbnail to destination
Space Complexity Graph
Error creating thumbnail: Unable to save thumbnail to destination
Time-Space Tradeoff
Error creating thumbnail: Unable to save thumbnail to destination