Link analysis for the web

Link analysis is a technique that studies the hyperlinks between web pages (the web graph) to find which pages are important, how pages are related and how communities form. A web page is a node and a hyperlink is a directed edge. A link from page A to B is treated as a vote, or recommendation, for B.

Basic ideas

• In-links (back-links) to a page show its popularity.
• Out-links show what the page points to.
• Links from important pages count more than links from unknown pages.
• The anchor text of a link describes the target page.

Main algorithms

1. PageRank: the rank of a page depends on the number and the rank of the pages linking to it: PR(A) = (1-d) + d × Σ PR(Ti)/C(Ti), where d is the damping factor (about 0.85) and C(Ti) is the number of outgoing links of Ti.
2. HITS (Hubs and Authorities): a hub is a page pointing to many good authorities; an authority is a page pointed to by many good hubs. Scores are updated iteratively.
3. Co-citation and bibliographic coupling for finding related pages.

Example

   A --> B
   A --> C
   C --> B
   B --> A

B has two in-links (from A and C), so it is the most important page. A has only one in-link, but it comes from B, the most important page, which gives its whole vote to A, so A is also ranked well. C's only in-link comes from A, which splits its vote between B and C, so C is the least important. Solving the PageRank equations with d = 0.85 gives PR(B) ≈ 1.19, PR(A) ≈ 1.16 and PR(C) ≈ 0.64.

Applications

Ranking search results (Google), crawling priority, detecting web spam and link farms, finding communities and social network analysis, and measuring the influence of sites and authors.

Limitations

Spam links can be created artificially, new pages have few links, and old pages have an advantage.