Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 39 ยท Text and Web Mining

Web Mining and PageRank

Understand the three kinds of web mining (content, structure, usage), build PageRank and HITS from scratch, parse HTML links, and sessionize clickstream logs with runnable Python examples.

Web mining applies data mining to the web. Three different data sources give three branches:

  • Web content mining extracts knowledge from page content: text, images, tables. Search snippets, price comparison and product review analysis belong here. Techniques from text mining apply directly.
  • Web structure mining studies the link graph: pages are nodes and hyperlinks are directed edges. Ranking pages by importance (PageRank, HITS) and finding communities live here.
  • Web usage mining analyzes how people use sites: server logs, clickstreams and sessions. It powers recommendations, site redesign and fraud detection.

Three branches of web mining

Content What the pages say
Structure How pages link
Usage How people browse

Search engines combine all three.

1 / 2

Getting data from pages

Crawlers fetch pages and extract text and links. The parsing step is plain HTML processing. Here Python's built-in parser extracts links from a page held in a string (a real crawler would fetch pages over the network, obey robots.txt and rate limits, and respect each site's terms of use).

Python Extract links from HTML

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

PageRank

The insight behind early Google: a page is important if important pages link to it. PageRank models a "random surfer" who follows a random outgoing link with probability d (the damping factor, typically 0.85) and jumps to a random page with probability 1 - d. The long-run share of time spent on each page is its PageRank.

Formally, for N pages: PR(p) = (1 - d)/N + d * sum(PR(q) / outdegree(q)) over all pages q linking to p. It is solved by repeating the update (power iteration) until the values settle. Pages with no outgoing links (dangling nodes) are handled by spreading their rank evenly.

Python PageRank by power iteration

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Page C receives links from four of the five pages, so it wins; D, which nobody links to, ends up with the minimum possible rank. Changing d shifts how much random jumping softens the differences.

HITS: hubs and authorities

HITS (Hyperlink-Induced Topic Search) gives every page two scores. An authority is a page many good hubs point to; a hub is a page that points to many good authorities (like a curated resource list). The scores reinforce each other and are computed iteratively with the adjacency matrix A: authority = A^T hub, hub = A authority, normalizing after each step.

Python HITS scores

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

C is the top authority; A and D, which each point at two authority pages, tie as the strongest hubs. Compared with PageRank, HITS is query-dependent and was designed to run on a small set of pages related to a query.

Link analysis can be gamed with link farms and spam, so real search engines combine it with many content and quality signals.

Web usage mining

Web servers log every request: IP address, timestamp, URL, status. Usage mining proceeds in steps:

  1. Clean the log: drop images, scripts and bot requests.
  2. Identify users and sessions: group one user's requests, and start a new session after a long gap (commonly 30 minutes).
  3. Mine the sessions: frequent navigation paths, association rules ("people who read A also read B"), clustering of visitors, next-page prediction.
Python Sessionizing a clickstream

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The gap of 85 minutes splits user u1 into two sessions. The transition counts are the basis of a simple next-page recommender or a Markov model of browsing.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which branch of web mining studies hyperlinks between pages?

    Structure mining analyzes the link graph, with algorithms such as PageRank and HITS.
  2. 2. What is the role of the damping factor d in PageRank?

    With probability d the surfer follows a link; with 1 - d the surfer teleports to a random page.
  3. 3. In HITS, what is a hub?

    Hubs are good lists of links; authorities are good sources that hubs point to.
  4. 4. Why are sessions defined with a time gap of about 30 minutes?

    A long inactivity gap is a practical heuristic for the end of one visit and the start of another.

Summary

  • Web mining has three branches: content, structure (links) and usage (logs).
  • PageRank scores pages by a random-surfer model solved with power iteration; HITS gives hub and authority scores.
  • Usage mining cleans logs, builds sessions and mines paths, rules and clusters.
  • Respect robots.txt, rate limits and privacy when collecting web data.

Next: Topic Modeling and Sentiment Analysis