Scalable Analytics: Chapter 6

Overview of Large Graph Analysis and Analytics

• Graph data analytics is a critical component of information retrieval and data mining, sitting alongside topics such as high-dimensional data, clustering, and stream processing.

• Applications of graph analytics include:

  • PageRank and SimRank for node and similarity ranking.

  • Community detection for identifying social or functional groups.

  • Spam detection.

  • Scalable machine learning (SVM, Decision Trees, kNN).

  • Recommender systems and association rules.

Varieties of Graph Data

• Social Networks: Represented by the Facebook social graph, mapping connections between individuals.

• Media Networks: Illustrated by connections between political blogs, showing how information and influence flow through media outlets.

• Information Networks: Includes citation networks and "maps of science." These display the overlap and relationships between diverse disciplines such as:

  • Hard Sciences: Chemistry, Physics, Math, Computer Science, and Electrical Engineering.

  • Applied Sciences: Chemical Engineering (ChE), Mechanical Engineering (ME), Civil Engineering (CivE), and Biotechnology.

  • Life/Earth Sciences: Biology, Infectious Diseases, Brain Research, Medical Specialties, and Earth Sciences.

  • Humanities and Social Sciences.

• Communication Networks: Visualized as routers connecting different domains (e.g., Domain 1, Domain 2, Domain 3).

• Technological Networks: A classic example is the Seven Bridges of Königsberg, analyzed by Euler in 1735.

The Web as a Directed Graph

• The World Wide Web is modeled as a directed graph where:

  • Nodes: Represent individual webpages.

  • Edges: Represent hyperlinks between pages.

• Nodes exhibit massive diversity in connectivity. For instance, a site like www.stanford.edu may have over $23,400$ incoming links, whereas a personal site like www.joe-schmoe.com might have only $1$.

• Challenge of Web Search:

  1. The web contains an immense variety of information sources.

  2. Finding the "best" answer for generic queries (e.g., "newspaper") requires ranking pages by importance rather than just keyword match.

PageRank: The "Flow" Formulation

• Links as Votes: A page is considered more important if it has more incoming links (in-links). However, not all in-links are equal; links from important pages carry more weight.

• Recursive Definition: A page is important if it is pointed to by other important pages.

• The Model:

  • Each link's vote is proportional to the importance of its source page.

  • If page $j$ has importance $r_j$ and $d_j$ out-links, each link confers $r_j / d_j$ votes.

  • The importance of page $j$ ($r_j$) is the sum of votes from its in-links:

$r_j = \sum_{i \to j} \frac{r_i}{d_i}$

• Example Flow Equations: For a small graph with nodes $y$, $a$, and $m$:

  • $r_y = \frac{r_y}{2} + \frac{r_a}{2}$

  • $r_a = \frac{r_y}{2} + r_m$

  • $r_m = \frac{r_a}{2}$

• To find a unique solution, an additional constraint is added such that the sum of all ranks equals $1$ ($r_y + r_a + r_m = 1$).

Matrix Formulation of PageRank

• Stochastic Adjacency Matrix ($M$):

  • If page $i$ has $d_i$ out-links, and there is a link from $i$ to $j$, then $M_{ji} = \frac{1}{d_i}$. If no link exists, $M_{ji} = 0$.

  • $M$ is column-stochastic—its columns sum to $1$.

• Rank Vector ($r$): A vector where $r_i$ is the importance score of page $i$, and $\sum_i r_i = 1$.

• Stationary Distribution: The flow equations are expressed as a matrix-vector multiplication:

$r = M \cdot r$

• This indicates that $r$ is an eigenvector of the matrix $M$ with a corresponding eigenvalue of $\lambda = 1$.

Power Iteration Method

• Power iteration is an iterative scheme to solve for the rank vector $r$ in web-scale graphs:

  1. Initialize: Set $r^{(0)} = [\frac{1}{N}, \dots, \frac{1}{N}]^T$ where $N$ is the number of pages.

  2. Iterate: Calculate $r^{(t+1)} = M \cdot r^{(t)}$.

  3. Converge: Stop when the L1 norm of the difference between successive vectors is less than a threshold $\epsilon$:

|r^{(t+1)} - r^{(t)}|_1 < \epsilon

• Random Walk Interpretation: A random surfer starts at a page and follows out-links uniformly at random. The vector $p(t)$, where the $i$-th coordinate is the probability the surfer is at page $i$ at time $t$, eventually reaches the stationary distribution $r$.

Problems and The Google Formulation

• Spider Traps: A group of pages whose out-links only point within the group. In power iteration, the random surfer gets stuck, and these pages eventually absorb all the PageRank.

• Dead Ends: Pages with no out-links. These cause the total PageRank in the system to leak out toward zero during iteration, as the matrix is no longer column-stochastic.

• The Teleportation Solution: Google uses "teleports" to solve these issues. At each step, a surfer has two options:

  1. With probability $\beta$, follow a link at random.

  2. With probability $1 - \beta$, jump (teleport) to a random page in the entire web.

  • A typical value for $\beta$ is $0.8$ to $0.85$.

• The Google Equation:

$r_j = \sum_{i \to j} \beta \frac{r_i}{d_i} + (1 - \beta) \frac{1}{N}$

• The Google Matrix ($A$):

$A = \beta M + \frac{1 - \beta}{N} \mathbf{1}_{N \times N}$

Scalable Computation of PageRank

• For $N = 1$ billion pages, the matrix $A$ is too dense to fit in memory. However, the calculation can be rearranged to utilize the sparsity of $M$:

$r = \beta M \cdot r + \frac{1 - \beta}{N} \mathbf{1}$

• Sparse Matrix Encoding: $M$ is encoded using only non-zero entries. Each entry consists of a source node, its out-degree, and a list of destination nodes.

• Block-Stripe Update Algorithm: To handle cases where the rank vector does not fit in RAM:

  • Divide the vector $r_{new}$ into $k$ blocks.

  • Divide the matrix $M$ into stripes such that each stripe contains only destination nodes corresponding to a specific block of $r_{new}$.

  • This reduces the cost per iteration to approximately $|M|(1 + \epsilon) + (k+1)|r|$.

Topic-Specific PageRank

• Standard PageRank measuring generic popularity is biased against topic-specific authorities.

• Goal: Evaluate pages based on proximity to a particular topic.

• Method: Modify the teleportation behavior. Instead of jumping to any page with equal probability, the user teleports only to a specific "teleport set" $S$ of relevant pages.

• Matrix Adjustment:

$A_{ij} = \begin{cases} \beta M_{ij} + \frac{1 - \beta}{|S|} &amp; \text{if } i \in S \\ \beta M_{ij} + 0 &amp; \text{otherwise} \end{cases}$

• Topic vectors $S$ can be determined by user bookmarks, query context, or manual menus.

Web Spam and TrustRank

• Term Spam: Spammers add irrelevant keywords (e.g., "movie") thousands of times or use invisible text to fool early search engines that relied on word frequency.

• Link Spam: Spammers create "link farms"—complex topographies of owned pages linking to a target page to artificially boost its PageRank.

• TrustRank: A specialized version of topic-specific PageRank designed to combat spam.

  • Seed Set: A small subset of pages is manually identified as "trusted" (good) pages.

  • Propagation: Perform PageRank with the teleport set equal to the trusted set.

  • Trust Attenuation: Trust decreases as the distance from the trusted seed increases.

  • Trust Splitting: Trust is diluted as the number of out-links from a page increases.

  • Pages with a TrustRank score below a certain threshold are classified as spam.