Web and Social Network Analytics
Week 2: Search Engines & Web Crawler
Dr. Zexun Chen 
Jan-2025
Introduction
Search Engines: One of the most widely-used sources of information
Architecture
Shingling for Duplicates
- Compare and determine how similar.
- Document comparison.
- Plagiarism detection.
- Shingle: String of length \(k\) in a document \(d\).
- Example: \(k = 5\) in “University of Edinburgh.”
- Shingles: “Unive”, “niver”, …, “burgh.”
- \(k\) typically not too small to avoid overlap in documents.
- Degree of overlap between two documents:
- \(S(d_j)\): The shingles in \(d_j\).
- Jaccard index (intersection over union): \[ J(S(d_1), S(d_2)) = \frac{|S(d_1)\cap S(d_2)|}{|S(d_1) \cup S(d_2)|} \]
- If threshold exceeded: regarded as similar.
- Apply hashing to document’s shingles.
- Information on shingles.
- Challenges:
- High computational resources for large documents or web pages.
- Optimal size of shingles.
Basics
Web Crawler
It aims to quickly and efficiently gather as many useful web pages as possible. Also called spiders, bots, or web robots.
- Starting Point: Begin with a list of web addresses (URLs).
- Crawling: Visit each URL and read the content of the page.
- Extracting Links: Identify all hyperlinks on the page and add them to the list of URLs to visit.
- Repeating the Process: Continue crawling these new URLs.
- Respecting Rules: Adhere to
robots.txtfiles and meta tags.
Link Analysis
- Based on the principle of referral:
- Relies on the relevance and quality of web pages.
- Quantifies the influence of a web page by the number of referrals.
- Acts as evidence for authority.
- Potential Abuse:
- Link spam by setting up many referring websites.
- Sets the web up as a graph:
- Nodes (vertices): Web pages.
- Edges (links): Hyperlinks between pages.
Markov Chains: Definition
A Markov chain (or process) is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event.
Key Concepts
- In each step, a random choice is made.
- Consists of \(N\) states (e.g., each web page).
- \(N \times N\) transition probability matrix \(P\):
- Each row of \(P\) adds up to 1.
- \(P_{ij}\) tells the probability that the next state is \(j\) when in state \(i\).
Markov Chains: Surfer’s Position
- At time \(t\), the probability vector is \(x_0 P\): \[ (x_0 P) P = x_0 P^2 \]
- Converges to a steady-state distribution.
- Each entry of \(P\) only depends on the current state.
Markov Chains: Adjacency Matrix
A random surfer’s behavior on the web graph can be modeled with an adjacency matrix: \[ A = (a_{ij}) = \text{Number of edges from vertex $i$ to $j$}. \]
- Dead Ends:
- No outlinks; rows in \(A\) sum to 0.
- After a few iterations, entries in \(x\) become 0.
- Solutions:
- Drop dead ends (cascading effect).
- Add “teleportation” links:
- Randomly jump to another page with probability \(0 < \alpha < 1\).
Markov Chains: Example 1
- Converting this web graph from an adjacency matrix to a transition matrix for \(\alpha = 0.3\): \[ A = \begin{pmatrix} 1 & 0 & 1\\ 0 & 0 & 0\\ 0 & 1 & 0 \end{pmatrix} \]
- Transition matrix accounts for teleportation probability.
Markov Chains: Example 2
- Converting this web graph from an adjacency matrix to a transition matrix for \(\alpha = 0.7\): \[ A = \begin{pmatrix} 1 & 0 & 1\\ 0 & 0 & 0\\ 1 & 1 & 1 \end{pmatrix} \]
- Transition matrix includes teleportation adjustments with a higher \(\alpha\) value.
PageRank: Algorithm Overview
- Basic algorithm underlying Google’s search engine.
- Named after Larry Page (Co-founder of Google).
- A general approach for scoring nodes in a network.
PageRank Computation
- Left eigenvectors of \(P\) are vectors \(\pi\) of size \(N\):
- \(\pi P = \lambda \pi\), where \(\lambda\) are the eigenvalues of \(P\).
- If \(\pi\) is the steady-state distribution: \[ \pi P = 1 \pi \]
- Compute left eigenvector of \(P\) for eigenvalue 1 to obtain PageRank values \(\pi\).
- Calculated through power iteration:
- Start with an initial distribution \(x\).
- Find \(xP^t\) for large \(t\), as frequencies converge.
- Simulates a user’s surfing behavior.
PageRank Computation: Exercise
Question
- Find the “coolest page” if \(x_0 = (1 \, 0 \, 0)\) over 3 iterations: \[ P = \begin{pmatrix} 0.45 & 0.1 & 0.45\\ 0.33 & 0.33 & 0.33\\ 0.1 & 0.8 & 0.1 \end{pmatrix} \]
Solution
Personalized PageRank
- Linear combination of a small number of topic-specific distributions.
- Example: \[
0.06 \pi_S + 0.04 \pi_P
\]
- For sports and politics browsing.
- User has 10% teleport probability:
- 6% sports teleport.
- 4% politics teleport.
Hubs and Authorities
- PageRank: Simplistic view of a network (one score per node).
- Hubs and Authorities: Richer view of a network with different node types:
- Hub: A page that points to many others.
- Authority: A page that many others refer to.
- Reflecting Types of Websites:
- Broad-topic searches often land on authority pages:
- Example: Searching “leukaemia” leads to the National Cancer Institute’s page.
- Hub pages point to authoritative pages:
- Example: Searching “sell property” leads to Rightmove.
- Broad-topic searches often land on authority pages:
HITS Algorithm
- Hyperlink-Induced Topic Search (HITS)(Kleinberg, 1997):
- Assemble the target subset of web pages and then Compute \(AA^T\) / \(A^T A\).
- Calculate eigenvectors to find \(\textbf{h}\) and \(\textbf{a}\), Output the top-scoring hubs and authorities.
Take Home Messages
- Search Engines
- Web Search Basics
- Web Crawler
- Indexing and Storing Data
- Searching Algorithms:
- Link Analysis
- Markov Chains (***)
- PageRank (**)
- Hubs and Authorities (**)
