Question? Leave a message!




Web as a directed graph

Web as a directed graph
Big Data Analytics CSCI 4030 High dim. Graph Infinite Machine Apps data data data learning Locality Filtering PageRank, Recommen sensitive data SVM SimRank der systems hashing streams Community Web Decision Association Clustering Detection advertising Trees Rules Dimensional Duplicate Spam Queries on Perceptron, ity document Detection streams kNN reduction detection Big Data Analytics CSCI 4030 2  A graph is a representation of a set of objects (e.g., users, computers, …) where some pairs of objects are connected by links  Objects are called nodes or vertices  Links are called edges  The edges may be directed or undirected Big Data Analytics CSCI 4030 3 Facebook social graph 4degrees of separation BackstromBoldiRosaUganderVigna, 2011 Big Data Analytics CSCI 4030 4 Connections between political blogs Polarization of the network AdamicGlance, 2005 Big Data Analytics CSCI 4030 5 Citation networks and Maps of science Börner et al., 2012 Big Data Analytics CSCI 4030 6 domain2 domain1 router domain3 Internet Big Data Analytics CSCI 4030 7  Web as a directed graph:  Nodes: Webpages  Edges: Hyperlinks I teach a class on Databases. CSCI3030: Classes are in the UA building Computer Science Department at UOIT UOIT Big Data Analytics CSCI 4030 8  Web as a directed graph:  Nodes: Webpages  Edges: Hyperlinks I teach a class on Databases. CSCI 3030: Classes are in the UA building Computer Science Department at UOIT UOIT J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org 9 Big Data Analytics CSCI 4030 10  How to make the Web accessible  First try: Human curated Web directories  Yahoo, DMOZ, LookSmart  Second try: Web Search  Information Retrieval investigates: Find relevant docs in a small and trusted set  Newspaper articles, Patents, etc.  But: Web is huge, full of untrusted documents, random things, web spam, etc. Big Data Analytics CSCI 4030 11 2 challenges of web search:  (1) Web contains many sources of information Who to “trust”  Trick: Trustworthy pages may point to each other  (2) What is the “best” answer to query “newspaper”  No single right answer  Trick: Pages that actually know about newspapers might all be pointing to many newspapers Big Data Analytics CSCI 4030 12  All web pages are not equally “important” www.joeschmoe.com vs. www.stanford.edu  Let’s rank the pages by the link structure Big Data Analytics CSCI 4030 13  We will cover the following Link Analysis approaches for computing importances of nodes in a graph:  Page Rank  TopicSpecific (Personalized) Page Rank  Web Spam Detection Algorithms Big Data Analytics CSCI 4030 14  Idea: Links as votes  Page is more important if it has more links  Incoming links Outgoing links  Think of inlinks as votes:  www.stanford.edu has 23,400 inlinks  www.joeschmoe.com has 1 inlink  Are all inlinks are equal  Links from important pages count more  Recursive question Big Data Analytics CSCI 4030 16 A B C 3.3 38.4 34.3 D E F 3.9 8.1 3.9 1.6 1.6 1.6 1.6 1.6 Big Data Analytics CSCI 4030 17  Each link’s vote is proportional to the importance of its source page  If page j with importance r has n outlinks, j each link gets r / n votes j  Page j’s own importance is the sum of the votes on its inlinks i k r /3 i r /4 k j r /3 j r = r /3+r /4 j i k r /3 r /3 j j Big Data Analytics CSCI 4030 18 The web in 1839  A “vote” from an important y/2 page is worth more  A page is important if it is y pointed to by other important a/2 pages y/2  Define a “rank” r for page j m j a m a/2 r i “Flow” equations: r   j r = r /2 + r /2 y y a d i j i r = r /2 + r a y m r = r /2 m a 𝒅 … outdegree of node 𝒊 𝒊 Big Data Analytics CSCI 4030 19 Flow equations:  3 equations, 3 unknowns, r = r /2 + r /2 y y a no constants r = r /2 + r a y m  No unique solution r = r /2 m a  Additional constraint forces uniqueness: 𝒓 +𝒓 + 𝒓 = 𝟏 𝒚 𝒂 𝒎 𝟐 𝟐 𝟏  Solution: 𝒓 = ,𝒓 = ,𝒓 = 𝒚 𝒂 𝒎 𝟓 𝟓 𝟓  Gaussian elimination method (an algorithm for solving linear equations) works for small examples, but we need a better method for large websize graphs  We need a new formulation Big Data Analytics CSCI 4030 20  Stochastic adjacency matrix 𝑴  Let page 𝑖 has 𝑑 outlinks 𝑖 1  If 𝑖 →𝑗 , then 𝑀 = else 𝑀 = 0 𝑗𝑖 𝑗𝑖 𝑑 𝑖 𝑴 is a column stochastic matrix  Columns sum to 1  Rank vector 𝒓 : vector with an entry per page 𝑟 is the importance score of page 𝑖 𝑖  𝑟 =1 𝑖 𝑖 r i  The flow equations can be written r   j d i j i 𝒓 = 𝑴 ⋅ 𝒓 Big Data Analytics CSCI 4030 21 y a m y ½ ½ 0 y a ½ 0 1 a m 0 ½ 0 m r = M∙r r = r /2 + r /2 y ½ ½ 0 y y y a a = ½ 0 1 a r = r /2 + r a y m m 0 ½ 0 m r = r /2 m a Big Data Analytics CSCI 4030 22 r i r   Remember the flow equation:  j d i j i  Flow equation in the matrix form 𝑴 ⋅ 𝒓 =𝒓  Suppose page i links to 3 pages, including j (d = 3) i i j r j . = r i 1/3 . M r r = Big Data Analytics CSCI 4030 23  The flow equations can be written 𝒓 = 𝑴 ∙ 𝒓  Just a Definition  x is an eigenvector with the corresponding eigenvalue λ if: =𝝀𝒙  So the rank vector r is an eigenvector of the stochastic web matrix M  Largest eigenvalue of M is 1 since M is column stochastic (with nonnegative entries)  We can now efficiently solve for r The method is called Power iteration Big Data Analytics CSCI 4030 24 𝑨𝒙 Given a web graph with n nodes, where the nodes are pages and edges are hyperlinks  Power iteration: a simple iterative scheme  Suppose there are N web pages (t) r (t1) (0) T i  Initialize: r = 1/N,….,1/N r  j  d i j i (t+1) (t)  Iterate: r = M ∙ r d …. outdegree of node i i (t+1) (t)  Stop when r – r  Big Data Analytics CSCI 4030 25 y a m  Power Iteration: y y ½ ½ 0 (0) T  r = 1/N,….,1/N a ½ 0 1 a m 0 ½ 0 m (t+1) (t)  r = M ∙ r (t+1) (t)  r – r  r = r /2 + r /2 1 y y a r = r /2 + r a y m r = r /2 m a  Example: r 1/3 1/3 5/12 9/24 6/15 y r = 1/3 3/6 1/3 11/24 … 6/15 a r 1/3 1/6 3/12 1/6 3/15 m Iteration 0, 1, 2, … Big Data Analytics CSCI 4030 26  Power iteration: (𝟏) (𝟎) 𝒓 =𝑴 ⋅𝒓 (𝟐) 𝟏 𝟏 𝟐 𝟎 𝒓 =𝑴 ⋅𝒓 =𝑴 𝑴 𝒓 =𝑴 ⋅𝒓 (𝟑) 𝟐 𝟐 𝟎 𝟑 𝟎 𝒓 =𝑴 ⋅𝒓 =𝑴 𝑴 𝒓 =𝑴 ⋅𝒓  Claim: 𝟎 𝟐 𝟎 𝒌 𝟎 Sequence 𝑴 ⋅𝒓 ,𝑴 ⋅𝒓 ,…𝑴 ⋅𝒓 ,… will converge (under which conditions) Big Data Analytics CSCI 4030 27 (t) r (t1) i or r   j equivalently r  Mr d i j i  Does this converge  Does it converge to what we want  Are results reasonable Big Data Analytics CSCI 4030 29 Dead end 2 problems:  (1) Some pages are dead ends (have no outlinks)  Such pages cause importance to “leak out”  (2) Spider traps: (all outlinks are within the group)  And eventually spider traps absorb all importance Big Data Analytics CSCI 4030 30 y a m  Power Iteration: y y ½ ½ 0 a ½ 0 0 a m 0 ½ 1 m m is a spider trap r = r /2 + r /2 y y a  Example: r = r /2 a y r = r /2 + r m a m r 1/3 2/6 3/12 5/24 0 y r = 1/3 1/6 2/12 3/24 … 0 a r 1/3 3/6 7/12 16/24 1 m Iteration 0, 1, 2, … All the PageRank score gets “trapped” in node m. Big Data Analytics CSCI 4030 31  The Google solution for spider traps: At each time step, the random surfer has two options  With probability , follow a link at random  With probability 1, jump to some random page  Common values for  are in the range 0.8 to 0.9  Surfer will teleport out of spider trap within a few time steps y y a a m m Big Data Analytics CSCI 4030 32 y a m  Power Iteration: y y ½ ½ 0 a ½ 0 0 a m 0 ½ 0 m r = r /2 + r /2 y y a r = r /2 a y r = r /2 m a  Example: r 1/3 2/6 3/12 5/24 0 y r = 1/3 1/6 2/12 3/24 … 0 a r 1/3 1/6 1/12 2/24 0 m Iteration 0, 1, 2, … Here the PageRank “leaks” out since the matrix is not stochastic. Big Data Analytics CSCI 4030 33  Teleports: Follow random teleport links with probability 1.0 from deadends  Adjust matrix accordingly y y a a m m y a m y a m y ½ ½ 0 y ½ ½ ⅓ a ½ 0 0 a ½ 0 ⅓ m 0 ½ 0 m 0 ½ ⅓ Big Data Analytics CSCI 4030 34 Why are deadends and spider traps a problem and why do teleports solve the problem  Spidertraps are not a problem, but with traps PageRank scores are not what we want  Solution: Never get stuck in a spider trap by teleporting out of it in a finite number of steps  Deadends are a problem  The matrix is not column stochastic so our initial assumptions are not met  Solution: Make matrix column stochastic by always teleporting when there is nowhere else to go Big Data Analytics CSCI 4030 35  Google’s solution that does it all: At each step, random surfer has two options:  With probability , follow a link at random  With probability 1, jump to some random page  PageRank equation BrinPage, 98 𝑟 1 𝑖 𝑟 = 𝛽 +(1−𝛽) 𝑗 𝑑 𝑁 𝑖 𝑖→𝑗 d : outdegree of node i i N: total number of webpages Big Data Analytics CSCI 4030 36  PageRank equation BrinPage, ‘98 𝑟 1 𝑖 𝑟 = 𝛽 +(1−𝛽) 𝑗 𝑑 𝑁 𝑖 𝑖→𝑗  The Google Matrix A: 1/N …N by N matrix NxN where all entries are 1/N 1 𝐴 =𝛽 𝑀 +1−𝛽 𝑁 𝑁 ×𝑁  We have a recursive equation: 𝒓 =𝑨 ⋅𝒓 And the Power method still works  What is   In practice  =0.8,0.9 (make 5 steps on avg., jump) Big Data Analytics CSCI 4030 37 1/N M NxN 7/15 1/2 1/2 0 1/3 1/3 1/3 y + 0.2 0.8 1/2 0 0 1/3 1/3 1/3 0 1/2 1 1/3 1/3 1/3 y 7/15 7/15 1/15 13/15 a 7/15 1/15 1/15 a m 1/15 7/15 13/15 m A y 1/3 0.33 0.24 0.26 7/33 a = . . . 1/3 0.20 0.20 0.18 5/33 m 1/3 0.46 0.52 0.56 21/33 Big Data Analytics CSCI 4030 38  Key step is matrixvector multiplication new old  r = A ∙ r  Easy if we have enough main memory to hold old new A, r , r  Say N = 1 billion pages  We need 4 bytes for each entry (say)  2 billion entries for vectors, approx 8GB 2  Matrix A has N entries 18  10 is a large number  Google invented MapReduce and Hadoop mainly to calculate PageRank 40 Big Data Analytics CSCI 4030  Measures generic popularity of a page  Biased against topicspecific authorities  Solution: TopicSpecific PageRank (next)  Sensitive to Link spam  Artificial link topographies created in order to boost page rank  Solution: TrustRank Big Data Analytics CSCI 4030 41  Instead of generic popularity, can we measure popularity within a topic  Example: Query “Trojan” wants different pages depending on whether you are interested in sports, history and computer security  Goal: Evaluate Web pages not just according to their popularity, but by how close they are to a particular topic, e.g. “sports” or “history”  Allows search queries to be answered based on interests of the user Big Data Analytics CSCI 4030 43  Random walker has a small probability of teleporting at any step  Teleport can go to:  Standard PageRank: Any page with equal probability  To avoid deadend and spidertrap problems  Topic Specific PageRank: A topicspecific set of “relevant” pages (teleport set)  Idea: Bias the random walk  When walker teleports, she pick a page from a set S  S contains only pages that are relevant to the topic  E.g., Open Directory (DMOZ) pages for a given topic/query Big Data Analytics CSCI 4030 44  To make this work all we need is to update the teleportation part of the PageRank formulation: 𝑨 = 𝜷 𝑴 +(𝟏 −𝜷 )/𝑺 if 𝒊∈ 𝑺 𝜷 𝑴 +𝟎 otherwise  A is stochastic  We weighted all pages in the teleport set S equally  Could also assign different weights to pages  Compute as for regular PageRank:  Multiply by M, then add a vector Big Data Analytics CSCI 4030 45 𝒊𝒋 𝒊𝒋 𝒊𝒋0.2 Suppose S = 1,  = 0.8 0.5 1 Node Iteration 0.5 0.4 0 1 2 … stable 0.4 1 0.25 0.4 0.28 0.294 1 2 3 2 0.25 0.1 0.16 0.118 0.8 3 0.25 0.3 0.32 0.327 1 1 4 0.25 0.2 0.24 0.261 0.8 0.8 4 S=1,2,3,4, β=0.8: r=0.13, 0.10, 0.39, 0.36 S=1, β=0.90: S=1,2,3 , β=0.8: r=0.17, 0.07, 0.40, 0.36 r=0.17, 0.13, 0.38, 0.30 S=1 , β=0.8: S=1,2 , β=0.8: r=0.29, 0.11, 0.32, 0.26 r=0.26, 0.20, 0.29, 0.23 S=1, β=0.70: S=1 , β=0.8: r=0.39, 0.14, 0.27, 0.19 r=0.29, 0.11, 0.32, 0.26 Big Data Analytics CSCI 4030 46  Create different PageRanks for different topics  The 16 DMOZ toplevel categories:  arts, business, sports,…  Which topic ranking to use  User can pick from a menu  Classify query into a topic  Can use the context of the query  E.g., query is launched from a web page talking about a known topic  History of queries e.g., “basketball” followed by “Jordan”  User context, e.g., user’s bookmarks, … Big Data Analytics CSCI 4030 47  Spamming:  Any deliberate action to boost a web page’s position in search engine results, incommensurate with page’s real value  Spam:  Web pages that are the result of spamming  This is a very broad definition  SEO industry might disagree  SEO = search engine optimization  Approximately 1015 of web pages are spam Big Data Analytics CSCI 4030 49  Early search engines:  Crawl the Web  Index pages by the words they contained  Respond to search queries (lists of words) with the pages containing those words  Early page ranking:  Attempt to order pages matching a search query by “importance”  First search engines considered:  (1) Number of times query words appeared  (2) Prominence of word position, e.g. title, header Big Data Analytics CSCI 4030 50  As people began to use search engines, those with commercial interests tried to exploit search engines  Example:  Shirtseller might pretend to be about “movies”  Techniques for achieving high relevance/importance for a web page Big Data Analytics CSCI 4030 51  How do you make your page appear to be about movies  (1) Add the word movie 1,000 times to your page  Set text color to the background color, so only search engines would see it  (2) Or, run the query “movie” on your target search engine  See what page came first in the listings  Copy it into your page, make it “invisible”  These and similar techniques are term spam Big Data Analytics CSCI 4030 52 1) Believe what people say about you, rather than what you say about yourself  Use words in the anchor text (words that appear underlined to represent the link) and its surrounding text 2) PageRank as a tool to measure the “importance” of Web pages Big Data Analytics CSCI 4030 53 Big Data Analytics CSCI 4030 54 SPAM FARMING J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org 55  Once Google became the dominant search engine, spammers began to work out ways to fool Google  Spam farms were developed to concentrate PageRank on a single page  Link spam:  Creating link structures that boost PageRank of a particular page Big Data Analytics CSCI 4030 56  Three kinds of web pages from a spammer’s point of view  Inaccessible pages  Accessible pages  e.g., blog comments pages  spammer can post links to his pages  Owned pages  Completely controlled by spammer  May span multiple domain names Big Data Analytics CSCI 4030 57 Accessible Owned 1 Inaccessible 2 t M Millions of farm pages Get as many links from accessible pages as possible to target page t Big Data Analytics CSCI 4030 58  Combating link spam  Detection and blacklisting of structures that look like spam farms  Leads to another war – hiding and detecting spam farms  TrustRank  Spam Mass Big Data Analytics CSCI 4030 60  Basic principle: Approximate isolation  It is rare for a “good” page to point to a “bad” (spam) page  Choose a set of seed pages that are identified as good the trusted pages  Perform a topicsensitive PageRank with teleport set = trusted pages  Propagate trust through links Big Data Analytics CSCI 4030 61  Two conflicting considerations:  Human has to inspect each seed page, so seed set must be as small as possible  Must ensure every good page gets adequate trust rank, so we need to make all good pages reachable from seed set by short paths Big Data Analytics CSCI 4030 62  Suppose we want to pick a seed set of k pages  How to do that  (1) PageRank:  Pick the top k pages by PageRank  Theory is that you can’t get a bad page’s rank really high  (2) Use trusted domains whose membership is controlled, like .edu, .mil, .gov Big Data Analytics CSCI 4030 63 𝒓 = PageRank of page p 𝒑 + 𝒓 = PageRank of p with teleport into 𝒑 trusted pages only  Then: What fraction of a page’s PageRank comes from spam pages + 𝒓 − 𝒓 Trusted 𝒑 𝒑 set  Spam mass of p = 𝒓 𝒑  Pages with high spam mass are spam. Web Big Data Analytics CSCI 4030 64  Given an example of the Web  Compute transition matrix  What is the meaning of the transition matrix  Compute Page Rank. Big Data Analytics CSCI 4030 65  One way to deal with dead ends is to drop the dead ends from the graph, and also drop their incoming arcs. Doing so may create more dead ends, which have to be dropped, recursively.  Apply this method on the dead ends of the following graph and draw the new graph.  Compute the transition matrix of the new graph. Big Data Analytics CSCI 4030 66  PageRank is an algorithm that assigns a real number, called its PageRank, to each page on the Web.  The PageRank of a page is a measure of how important the page is, or how likely it is to be a good response to any search query. Big Data Analytics CSCI 4030 67  Dead Ends: A dead end is a Web page with no links out. The presence of dead ends will cause the PageRank of some or all of the pages to go to 0 in the iterative computation Big Data Analytics CSCI 4030 68  Spider Traps: A spider trap is a set of nodes that, while they may link to each other, have no links out to other nodes.  To counter the effect of spider traps (and of dead ends, if we do not eliminate them), PageRank is normally computed in a way that modifies the simple iterative multiplication by the transition matrix (teleport) Big Data Analytics CSCI 4030 69  If we know the queryer is interested in a certain topic, then it makes sense to bias the PageRank in favor of pages on that topic.  TrustRank: One way to ameliorate the effect of link spam is to compute a topicsensitive PageRank called TrustRank, where the teleport set is a collection of trusted pages Big Data Analytics CSCI 4030 70  Review slides  Read Chapter 5 from course book.  You can find electronic version of the book on Blackboard. Big Data Analytics CSCI 4030 71
Website URL
Comment