Link Analysis: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 10: | Line 10: | ||
== Parameters == | == Parameters == | ||
$n$: number of pages | |||
$m$: number of hyperlinks | |||
$z$: # of topics/categories | |||
== Table of Algorithms == | == Table of Algorithms == | ||
| Line 28: | Line 32: | ||
| [[The (Stochastic Approach for Link Structure Analysis) SALSA Algorithm (Link Analysis Link Analysis)|The (Stochastic Approach for Link Structure Analysis) SALSA Algorithm]] || 2000 || $O(m^{2} n )$ || $O(n)$? || Exact || Deterministic || [https://dl-acm-org.ezproxy.canberra.edu.au/doi/abs/10.1145/382979.383041 Time] | | [[The (Stochastic Approach for Link Structure Analysis) SALSA Algorithm (Link Analysis Link Analysis)|The (Stochastic Approach for Link Structure Analysis) SALSA Algorithm]] || 2000 || $O(m^{2} n )$ || $O(n)$? || Exact || Deterministic || [https://dl-acm-org.ezproxy.canberra.edu.au/doi/abs/10.1145/382979.383041 Time] | ||
|- | |- | ||
| [[Randomized HITS (Link Analysis Link Analysis)|Randomized HITS]] || 2001 || $O(m | | [[Randomized HITS (Link Analysis Link Analysis)|Randomized HITS]] || 2001 || $O(m n\log n )$ || $O(n)$ || Exact || Deterministic || [https://dl-acm-org.ezproxy.canberra.edu.au/doi/pdf/10.1145/383952.384003 Time] | ||
|- | |- | ||
| [[PHITS Coheng Chan (Link Analysis Link Analysis)|PHITS Coheng Chan]] || 2000 || $O(m n )$ || $O(nz)$? || Exact || Deterministic || [http://web.cse.msu.edu/~cse960/Papers/LinkAnalysis/phits.pdf Time] | | [[PHITS Coheng Chan (Link Analysis Link Analysis)|PHITS Coheng Chan]] || 2000 || $O(m n )$ || $O(nz)$? || Exact || Deterministic || [http://web.cse.msu.edu/~cse960/Papers/LinkAnalysis/phits.pdf Time] | ||
Revision as of 07:53, 10 April 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
$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
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