InDegree Analysis (Link Analysis)

From Algorithm Wiki
Jump to navigation Jump to search


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


$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

Link Analysis - InDegree Analysis - Time.png