Link Analysis: Difference between revisions
Jump to navigation
Jump to search
(Created page with "{{DISPLAYTITLE:Link Analysis (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...") |
No edit summary |
||
| Line 44: | Line 44: | ||
|} | |} | ||
== Time Complexity | == Time Complexity Graph == | ||
[[File:Link Analysis - Time.png|1000px]] | [[File:Link Analysis - Time.png|1000px]] | ||
== Space Complexity | == Space Complexity Graph == | ||
[[File:Link Analysis - Space.png|1000px]] | [[File:Link Analysis - Space.png|1000px]] | ||
== Pareto | == Pareto Frontier Improvements Graph == | ||
[[File:Link Analysis - Pareto Frontier.png|1000px]] | [[File:Link Analysis - Pareto Frontier.png|1000px]] | ||
Revision as of 13:05, 15 February 2023
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
Pareto Frontier Improvements Graph
Error creating thumbnail: Unable to save thumbnail to destination