advertisement

Lecture: Link Analysis http://bicmr.pku.edu.cn/~wenzw/bigdata2016.html Acknowledgement: this slides is based on Prof. Jure Leskovec’s lecture notes 1/78 Outline 1 Introduction 2 PageRank 3 PageRank in Reality 4 Extensions Topic-Specific PageRank TrustRank: combating the web spam 2/78 Communication networks domain2 domain1 router domain3 Internet 3/78 Web search How to organize the Web? First try: Human curated Web directories Yahoo, baidu, hao123 Second try: Web Search Information Retrieval investigates: Find relevant docs in a small and trusted set But: Web is huge, full of untrusted documents, random things, web spam, etc. 4/78 Web as a directed graph Web as a directed graph: Nodes: Webpages; Edges: Hyperlinks 5/78 Web as a directed graph Web as a directed graph: Nodes: Webpages; Edges: Hyperlinks 6/78 Three basic things of search engines Crawl the web and locate all web pages with public access. Index the data from step 1, so that it can be searched efficiently for relevant keywords or phrases. Rate the importance of each page in the database, so that when a user does a search and the subset of pages in the database with the desired information has been found, the more important pages can be presented first. 7/78 Web search: two challenges Two 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 8/78 Ranking nodes on the graph All web pages are not equally "important" www.pku.edu.cn vs. www.tsinghua.edu.cn There is large diversity in the web-graph node connectivity Let’s rank the pages by the link structure! 9/78 Outline 1 Introduction 2 PageRank 3 PageRank in Reality 4 Extensions Topic-Specific PageRank TrustRank: combating the web spam 10/78 Links as votes Idea: links as votes Page is more important if it has more links In-coming links? Out-going links? Think of in-links as votes www.pku.edu.cn: 6,649 links www.alexa.com/siteinfo/www.pku.edu.cn www.tsinghua.edu.cn: 8579 links www.alexa.com/siteinfo/www.tsinghua.edu.cn Are all in-links equal? Links from important pages count more Recursive question! 11/78 Links as votes 12/78 Example: PageRank scores 13/78 Simple recursive formulation Each link’s vote is proportional to the importance of its source page If page j with importance rj has n out-links, each link gets rj /n votes Page j’s own importance is the sum of the votes on its in-links 14/78 PageRank: the "flow" model A "vote" from an important page is worth more A page is important if it is pointed to by other important pages Define a "rank" rj for page j rj = X ri di i→j where di is the out-degree of node i 15/78 Solving the flow equations No unique solution All solutions equivalent modulo the scale factor Additional constraint forces uniqueness: ry + ra + rm = 1 Solution: ry = 2/5, ra = 2/5, rm = 1/5 Gaussian elimination method works for small examples, but we need a better method for large web-size graphs We need a new formulation! 16/78 PageRank: matrix formulation Stochastic adjacency matrix M Let page i has di out-links Mji = 1 di 0 if i → j otherwise M is a column stochastic matrix (column sum to 1) Rank vector r: vector with an entry per page rP i is the importance score of page i i ri = 1 The flow equation rj = P ri i→j di can be written as r = Mr 17/78 Example Remember the flow equation: rj = ri i→j di P Flow equation in the matrix form: Mr = r Suppose page i links to 3 pages, including j i j . ri rj = 1/3 M . r = r 18/78 Eigenvector formulation NOTE: x is an eigenvector of A with the corresponding eigenvalue λ if: Ax = λx Flow equation in the matrix form: Mr = r The rank vector r is an eigenvector of the stochastic web matrix M In fact, its first or principal eigenvector, with corresponding eigenvalue 1 Largest eigenvalue of M is 1 since M is column stochastic. We know r is unit length and each column of M sums to one, so Mr ≤ 1 We can now efficiently solve for r through power iteration 19/78 Example: flow equations y a m y y ½ a ½ m 0 a ½ m 0 0 ½ 1 0 r = M∙r ry = ry /2 + ra /2 ra = ry /2 + rm rm = ra /2 y ½ a = ½ m 0 ½ 0 ½ 0 1 0 y a m 20/78 Power iteration 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 Initialize: r(0) = [1/N, . . . , 1/N]> Iterate: r(t+1) = Mr(t) , i.e., rt+1 = j X r(t) i i→j di , di : out-degree of node i Stop when kr(t+1) − r(t) k1 ≤ 21/78 Random walk interpretation Imagine a random web surfer: At any time t, surfer is on some page i At time t + 1, the surfer follows an out-link from i uniformly at random Ends up on some page j linked from i Process repeats indefinitely Let pt vector whose i-th coordinate is the prob. that the surfer is at page i at time t So, pt is a probability distribution over pages 22/78 The stationary distribution Where is the surfer at time t + 1? Follows a link uniformly at random pt+1 = Mpt Suppose the random walk reaches a state pt+1 = Mpt = pt then pt is the stationary distribution of a random walk Our original rank vector r satisfies r = Mr So r is a stationary distribution for the random walk 23/78 PageRank: three questions rt+1 = j X r(t) i i→j di , or equivalently r = Mr Does it converge? Does it converge to what we want? Are results reasonable? 24/78 Does it converge? a Example: ra = rb 1 0 rj b 0 1 1 0 (t +1) (t ) r =∑ i i→ j d i 0 1 Iteration 0, 1, 2, … 25/78 Does it converge to what we want? a Example: ra = rb 1 0 rj b 0 1 0 0 (t +1) (t ) r =∑ i i→ j d i 0 0 Iteration 0, 1, 2, … 26/78 PageRank: problems Two problems: 1 Some pages are dead ends (have no out-links) Such pages cause importance to "leak out" 2 Spider traps (all out-links are within the group) Eventually spider traps absorb all importance 27/78 Problem: spider traps 28/78 Solution: random teleports 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 Commonly β ∈ [0.8, 0.9] Surfer will teleport out of spider trap within a few time steps 29/78 Problem: dead ends 30/78 Solution: always teleport Teleports: Follow random teleport links with probability 1.0 from dead-ends Adjust matrix accordingly Surfer will teleport out of spider trap within a few time steps 31/78 Why teleports solve the problem? r(t+1) = Mr(t) Markov chains Set of states X Transition matrix P where Pij = P(Xt = i|Xt−1 = j) π specifying the stationary probability of being at each state x∈X Goal is to find π such that π = Pπ 32/78 Why is this analogy useful? Theory of Markov chains Fact: For any start vector, the power method applied to a Markov transition matrix P will converge to a unique positive stationary vector as long as P is stochastic, irreducible and aperiodic (By the Perron-Frobenius theorem, an irreducible and aperiodic Markov chain is guaranteed to converge to a unique stationary distribution) 33/78 Make M stochastic (column)-stochastic: every column sums to 1 A possible solution: add green links 1 A = M + a> ( 1) n where ai = 1 if node i has out deg 0, otherwise ai = 0 34/78 Make M aperiodic A chain is periodic if there exists k > 1 such that the interval between two visits to some state s is always a multiple of k A possible solution: add green links 35/78 Make M irreducible From any state, there is a non-zero probability of going from any one state to any another A possible solution: add green links 36/78 Google’s solution: random jumps Google’s solution that does it all: Makes M stochastic, aperiodic, irreducible 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 [Brin-Page, 98] rj = X ri 1 β + (1 − β) di n i→j This formulation assumes that M has no dead ends We can either preprocess matrix M to remove all dead ends or explicitly follow random teleport links with probability 1.0 from dead-ends 37/78 Google’s solution: random jumps PageRank equation [Brin-Page, 98] rj = X ri 1 β + (1 − β) di n i→j Since 1> r = 1, the Google matrix A: 1 A = βM + (1 − β) 11> n A is stochastic, aperiodic and irreducible, so r(t+1) = Ar(t) In practice β ∈ [0.8, 0.9] (make around 5 steps and jump) 38/78 Random teleports (β = 0.8) y 1/n·1·1T M 0.8·½+0.2·⅓ 1/2 1/2 0 0.8 1/2 0 0 0 1/2 1 0.8+0.2·⅓ a m 1/3 1/3 1/3 + 0.2 1/3 1/3 1/3 1/3 1/3 1/3 y 7/15 7/15 1/15 a 7/15 1/15 1/15 m 1/15 7/15 13/15 A y a = m 1/3 1/3 1/3 0.33 0.20 0.46 0.24 0.20 0.52 0.26 0.18 0.56 ... 7/33 5/33 21/33 39/78 Simple proof using linear algebra Every stochastic matrix has 1 as an eigenvalue. V1 (A) : eigenspace for eigenvalue 1 of a stochastic matrix A. Fact 1: If M is positive and stochastic, then any eigenvector in V1 (M) has all positive or all negative components. Fact 2: If M is positive and stochastic, then V1 (M) has dimension 1. 40/78 Proof of Fact 1 Suppose x ∈ V1 (M) contains elements of mixed sign. Since Mij > 0, each Mij xj are of mixed sign. Then |xi | = | n X Mij xj | < j=1 n X Mij |xj | j=1 Since M is stochastic, we can obtain a contradition ! n n X n n n n X X X X X |xi | < Mij |xj | = Mij |xj | = |xj | i=1 i=1 j=1 j=1 i=1 j=1 If xj ≥ 0 for all j, then xi > 0 since Mij > 0 and not all xj are zero. 41/78 Proof of Fact 2 Claim: Let v, w ∈ Rm with m ≥ 2 and linearly independent. Then for some s and t that are not both zero, the vector x = sv + tw has both positive and negative components. P Linear independence implies neither v nor w is zero. Let d = i vi . If d = 0, then v must P contain mixed sign, and taking s = 1, t = 0. If d = 6 0, set s = − i wi /d, t = 1 and x = sv + w. Then x 6= 0 but P x = 0. i i Fact 2: Proof by contradiction. Suppose there are two linearly independent eigenvectors v and w in the subspace V1 (M). For any real numbers s and t that are not both zero, the nonzero vector x = sv + tw must be in V1 (M), and so have components that are all negative or all positive. But by the above claim, for some choice of s and t the vector x must contain components of mixed sign. 42/78 Convergence of Power Iteration Claim 1: Let P M be positive and stochastic. Let V be a subspace of v such that i vi = 0. Then Mv ∈ V and kMvk1 ≤ ckvk1 for any v ∈ V and 0 < c < 1. Let w = Mv. Then w ∈ V since n X i=1 wi = n X n X Mij vj = i=1 j=1 Let ei = sgn(wi ) and aj = n X n X vj j=1 i=1 ! Mij = n X vj = 0 j=1 Pn then ei are of mixed sign n n n n X X X X Mij vj = kwk1 = ei wi = ei aj vj i=1 i=1 ei Mij , i=1 j=1 j=1 P Since ni=1 Mij = 1 with 0 < Mij < 1, there exists 0 < c < 1 such that |aj | < c. 43/78 Convergence of Power Iteration Claim 2: Let M be positive and stochastic. Then it has a unique q > 0 such that Mq = q with kqk1 = 1. The vector q can be computed as q = limk→∞ Mk x0 with x0 > 0 and kx0 k1 = 1. The existence of q has been proved. We can write x0 = q + v where v ∈ V defined in Claim 1. We have Mk x0 = Mk q + Mk v = q + Mk v Since kMk vk1 ≤ ck kvk1 for 0 < c < 1, then limk→∞ Mk x0 = q. 44/78 Convergence rate of Power Iteration r(1) = Mr(0) , r(2) = Mr(1) = M2 r(0) , . . . Claim: The sequence Mr(0) , . . . , Mk r(0) , . . . approaches the dominant eigenvector of M. Proof: Assume M has n linearly independent eigenvectors, x1 , x2 , . . . , xn with corresponding eigenvalues λ1 , λ2 , . . . , λn such that λ1 > λ2 ≥ . . . ≥ λn Since x1 , x2 , . . . , xn is a basis in Rn , we can write r(0) = c1 x1 + c2 x2 + . . . + cn xn Using Mxi = λi xi , we have Mr(0) = M(c1 x1 + c2 x2 + . . . + cn xn ) n X = ci λi xi i=1 45/78 Convergence rate of Power Iteration Repeated multiplication on both sides produces k (0) Mr = n X ci λki xi i=1 = λk1 n X ci i=1 Since λ1 > λi , i = 2, . . . , n. Then i = 2, . . . , n. λi λ1 λi λ1 k ! xi < 1, and limk→∞ k λi λ1 = 0, Therefore, Mk r(0) ≈ c1 λk1 x1 Note if c1 = 0, then the method won’t converge. 46/78 Outline 1 Introduction 2 PageRank 3 PageRank in Reality 4 Extensions Topic-Specific PageRank TrustRank: combating the web spam 47/78 Computing the PageRank The matrix A = βM + (1 − β) N1 11> Key step is matrix-vector multiplication rnew = Arold Easy if we have enough main memory to hold A, rold , rnew Suppose there are N = 1 billion pages Suppose we need 4 bytes for each entry 2 billion entries for vectors, approx 8GB Matrix A has N 2 entries - 1018 is huge! 48/78 Sparse matrix formulation We just rearranged the PageRank equation r = βMr + 1−β 1N N M is a sparse matrix! (with no dead-ends) 10 links per node, approximately 10N entries So in each iteration, we need to Compute rnew = Arold Add a constant value (1 − β)/N to each entry in rnew P Note if M contains dead-ends then i rinew < 1 and we also have to renormalize rnew so that it sums to 1 49/78 Sparse matrix encoding Encode sparse matrix using only nonzero entries Space proportional roughly to number of links Say 10N, or 4*10*1 billion = 40GB Still won’t fit in memory, but will fit on disk source degree node destination nodes 0 3 1, 5, 7 1 5 17, 64, 113, 117, 245 2 2 13, 23 50/78 Basic algorithm: update step Assume enough RAM to fit rnew into memory Store rold and matrix M on disk Then 1 step of power-iteration is Initialize all entries of rnew to (1 − β)/N For each page p (of out-degree n): Read into memory: p, n, dest1 , , destn , rold (p) for j = 1 to n: rnew (destj ) += βrold (p)/n rold rnew 0 1 2 3 4 5 6 src 0 1 2 degree 3 4 2 destination 1, 5, 6 17, 64, 113, 117 13, 23 0 1 2 3 4 5 6 51/78 Analysis Assume enough RAM to fit rnew into memory Store rold and matrix M on disk In each iteration, we have to Read rold and M Write rnew back to disk IO cost: 2|r| + |M| Question: What if we could not even fit rnew in memory? 52/78 Block based update algorithm rnew 0 1 2 3 src 0 1 2 degree 4 2 2 destination 0, 1, 3, 5 0, 5 3, 4 rold 0 1 2 3 4 5 4 5 53/78 Analysis of block update Similar to nested-loop join in databases Break rnew into k blocks that fit in memory Scan M and rold once for each block k scans of M and rold k(|r| + |M|) + |r| = k|M| + (k + 1)|r| Can we do better? Hint: M is much bigger than r (approx 10-20x), so we must avoid reading it k times per iteration 54/78 Block stripe update algorithm rnew 0 1 2 3 4 5 src degree destination 0 1 4 3 2 2 0 1 0 4 3 2 2 3 0 1 4 3 5 2 2 4 0, 1 rold 0 1 2 3 4 5 5 55/78 Analysis of block stripe update Break M into stripes Each stripe contains only destination nodes in the corresponding block of rnew Some additional overhead per stripe But it is usually worth it Cost per iteration: |M|(1 + ) + (k + 1)|r| 56/78 Some problems with PageRank Measures generic popularity of a page Biased against topic-specific authorities Solution: Topic-Specific PageRank Uses a single measure of importance Other models e.g., hubs-and-authorities Solution: Hubs-and-Authorities (HITS) Susceptible to Link spam Artificial link topographies created in order to boost page rank Solution: TrustRank 57/78 Outline 1 Introduction 2 PageRank 3 PageRank in Reality 4 Extensions Topic-Specific PageRank TrustRank: combating the web spam 58/78 Topic-Specific PageRank Instead of generic popularity, can we measure popularity within a topic? 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 Example: Query "Trojan" wants different pages depending on whether you are interested in sports, history and computer security 59/78 Topic-Specific PageRank Random walker has a small probability of teleporting at any step Teleport can go to: Standard PageRank: Any page with equal probability Topic Specific PageRank: A topic-specific 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 For each teleport set S, we get a different vector rS 60/78 Matrix formulation To make this work all we need is to update the teleportation part of the PageRank formulation βMij + (1 − β)/|S| if i ∈ S Aij = βMij otherwise A is stochastic! We have 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 Maintains sparseness 61/78 Example Suppose S = {1}, β = 0.8 0.2 1 0.5 0.4 2 Node 0.5 0.4 1 3 0.8 1 1 0.8 0.8 1 2 3 4 Iteration 0 1 0.25 0.4 0.25 0.1 0.25 0.3 0.25 0.2 4 S={1}, β=0.90: r=[0.17, 0.07, 0.40, 0.36] S={1} , β=0.8: r=[0.29, 0.11, 0.32, 0.26] S={1}, β=0.70: r=[0.39, 0.14, 0.27, 0.19] 2 … 0.28 0.16 0.32 0.24 stable 0.294 0.118 0.327 0.261 S={1,2,3,4}, β=0.8: r=[0.13, 0.10, 0.39, 0.36] S={1,2,3} , β=0.8: r=[0.17, 0.13, 0.38, 0.30] S={1,2} , β=0.8: r=[0.26, 0.20, 0.29, 0.23] S={1} , β=0.8: r=[0.29, 0.11, 0.32, 0.26] 62/78 Discovering the topic Create different PageRanks for different topics 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, ... 63/78 TrustRank: combating the web spam 64/78 Web spam 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 (Search Engine Optimization) industry might disagree! Approximately 10-15% of web pages are spam 65/78 Web search 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 2 Number of times query words appeared Prominence of word position, e.g. title, header 66/78 First spammers As people began to use search engines to find things on the Web, those with commercial interests tried to exploit search engines to bring people to their own site — whether they wanted to be there or not Example: shirt-sellers might pretend to be about "movies" Add the word movie 1,000 times to your page and set text color to the background color Or, run the query "movie" on your target search engine, copy the first result into your page and make it "invisible" Techniques for achieving high relevance/importance for a web page These and similar techniques are term spam 67/78 Google’s solution to term spam 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 PageRank as a tool to measure the "importance" of Web pages 68/78 Why it works? Our hypothetical shirt-seller looses Saying he is about movies doesn’t help, because others don’t say he is about movies His page isn’t very important, so it won’t be ranked high for shirts or movies Example: Shirt-seller creates 1,000 pages, each links to his with "movie" in the anchor text These pages have no links in, so they get little PageRank So the shirt-seller can’t beat truly important movie pages like IMDB 69/78 Spam farming 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 farm: creating link structures that boost PageRank of a particular page 70/78 Link spamming 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 Own pages Completely controlled by spammer May span multiple domain names 71/78 Link farms Spammer’s goal: maximize the PageRank of target page t Technique: Get as many links from accessible pages as possible to target page t Construct "link farm" to get PageRank multiplier effect Accessible Own 1 Inaccessible t 2 M N…# pages on the web M…# of pages spammer owns 72/78 Analysis x: PageRank contributed by accessible pages y: PageRank of target page t 1−β Rank of each "farm" page = βy M + N 1−β βy 1 − β + ]+ M N N β(1 − β)M 1 − β 2 = x+β y+ + N N y = x + βM[ Ignore the last term (very small) and solve for y: y= where c = x M +c 1 − β2 N β 1+β For β = 0.85, 1/(1 − β 2 ) = 3.6 Multiplier effect for "acquired" PageRank By making M large, we can make y as large as we want 73/78 Combating spam Combating term spam Analyze text using statistical methods Similar to email spam filtering Also useful: Detecting approximate duplicate pages Combating link spam Detection and blacklisting of structures that look like spam farms TrustRank = topic-specific PageRank with a teleport set of "trusted" pages 74/78 TrustRank: idea Basic principle: Approximate isolation It is rare for a "good" page to point to a "bad" (spam) page Sample a set of seed pages from the web Have an oracle (human) to identify the good pages and the spam pages in the seed set Expensive task, so we must make seed set as small as possible 75/78 Trust propagation Call the subset of seed pages that are identified as good the trusted pages Perform a topic-sensitive PageRank with teleport set = trusted pages Propagate trust through links: each page gets a trust value between 0 and 1 Use a threshold value and mark all pages below the trust threshold as spam 76/78 Why is it a good idea? Trust attenuation The degree of trust conferred by a trusted page decreases with the distance in the graph Trust splitting The larger the number of out-links from a page, the less scrutiny the page author gives each out-link Trust is split across out-links 77/78 Picking the seed set 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 need make all good pages reachable from seed set by short paths Suppose we want to pick a seed set of k pages, how? 1 PageRank: pick the top-k pages by PageRank 2 Use trusted domains, e.g. .edu, .mil, .gov 78/78