InDegree Analysis: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| 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 20: | Line 24: | ||
|- | |- | ||
| [[The INDEGREE Algorithm (InDegree Analysis Link Analysis)|The INDEGREE Algorithm]] || 1997 || $O( | | [[The INDEGREE Algorithm (InDegree Analysis Link Analysis)|The INDEGREE Algorithm]] || 1997 || $O(mn)$ || $O(n)$ || Exact || Deterministic || [https://www.w3.org/People/Massimo/papers/quest_hypersearch.pdf Time] | ||
|- | |- | ||
|} | |} | ||
| Line 27: | Line 31: | ||
[[File:Link Analysis - InDegree Analysis - Time.png|1000px]] | [[File:Link Analysis - InDegree Analysis - Time.png|1000px]] | ||
Latest revision as of 09:11, 28 April 2023
Description
A simple heuristic that can be viewed as the predecessor of all Link Analysis Ranking algorithms is to rank the pages according to their popularity (also referred to as visibility (Marchiori 1997)). The popularity of a page is measured by the number of pages that link to this page. We refer to this algorithm as the InDegree algorithm, since it ranks pages according to their in-degree in the graph $G$. That is, for every node $i$, $a_i = |B(i)|$.
Related Problems
Related: Link 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 INDEGREE Algorithm | 1997 | $O(mn)$ | $O(n)$ | Exact | Deterministic | Time |
Time Complexity Graph
Error creating thumbnail: Unable to save thumbnail to destination