DOC PREVIEW
Duke CPS 100E - Random Walks

This preview shows page 1-2 out of 5 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CompSci 100E3.1Random Walks• “A drunk man wil l find his way home, but a drunkbird may get lost forever”! – Shizuo Kakutani• Suppose you proceed randomly from the middle ofa large city whose streets form a completegrid! Will you make it back home?! Will you escape?• What if you mark the intersections you’ve visited?! Self avoiding random walk! Applications to chemistry: polymer formationCompSci 100E3.22-D Arrays• Want to arrange information in rows and columns• Initializedouble[][] a = new double[M][N];• Nested loops to accessfor (int i = 0; i < M; i+= 1) for (int j = 0; j < N; j+= 1) a[i][j] = 0;• Represent as 1-D array?CompSci 100E3.3PageRank• Google's PageRank™ algorithm. [Sergey Brin andLarry Page, 1998]! Measure popularity of pages based on hyperlink structureof Web.Revolutionized access to world's information.CompSci 100E3.490-10 Rule• Model. Web surfer chooses next page:! 90% of the time surfer clicks random hyperlink.! 10% of the time surfer types a random page.• Caveat. Crude, but useful, web surfing model.! No one chooses links with equal probability.! No real potential to surf directly to each page on the web.! The 90-10 breakdown is just a guess.! It does not take the back button or bookmarks into account.! We can only afford to work with a small sample of the web.! …CompSci 100E3.5Web Graph Input Format• Input format.! N pages numbered 0 through N-1.! Represent each hyperlink with a pair of integers.Graph representationCompSci 100E3.6Transition Matrix• Transition matrix. p[i][j]= prob. that surfer movesfrom page i to j.surfer on page 1 goes topage 2 next 38% of the timeCompSci 100E3.7Web Graph to Transition Matrix% java Transition tiny.txt5 5 0.02000 0.92000 0.02000 0.02000 0.02000 0.02000 0.02000 0.38000 0.38000 0.20000 0.02000 0.02000 0.02000 0.92000 0.02000 0.92000 0.02000 0.02000 0.02000 0.02000 0.47000 0.02000 0.47000 0.02000 0.02000CompSci 100E3.8Monte Carlo Simulation• Monte Carlo simulation.! Surfer starts on page 0.! Repeatedly choose next page, according to transitionmatrix.! Calculate how often surfer visits each page.transition matrixpageHow? see next slideCompSci 100E3.9Random Surfer• Random move. Surfer is on page page. How tochoose next page j?! Row page of transition matrix gives probabilities.! Compute cumulative probabilities for row page.! Generate random number r between 0.0 and 1.0.! Choose page j corresponding to interval where r lies.pagetransition matrixCompSci 100E3.10Random Surfer• Random move. Surfer is on page page. How tochoose next page j?! Row page of transition matrix gives probabilities.! Compute cumulative probabilities for row page.! Generate random number r between 0.0 and 1.0.! Choose page j corresponding to interval where r lies.// make one random movedouble r = Math.random();double sum = 0.0;for (int j = 0; j < N; j++) { // find interval containing r sum += p[page][j]; if (r < sum) { page = j; break; }}CompSci 100E3.11Random Surfer: Monte CarloSimulationpublic class RandomSurfer { public static void main(String[] args) { int T = Integer.parseInt(args[0]); // number of moves int N = in.nextInt(); // number of pages int page = 0; // current page double[][] p = new int[N][N]; // transition matrix // read in transition matrix ... // simulate random surfer and count page frequencies int[] freq = new int[N]; for (int t = 0; t < T; t++) { // make one random move freq[page]++; } // print page ranks for (int i = 0; i < N; i++) { System.out.println(String.format("%8.5f", (double) freq[i] / T); } System.out.println(); }}see previous slidepage rankCompSci 100E3.12Mathematical Context• Convergence. For the random surfer model, thefraction of time the surfer spends on each pageconverges to a unique distribution, independent ofthe starting page.! 428,6711,570,055, 417,2051,570,055, 229,5191,570,055, 388,1621,570,055, 106,4981,570,055" # $ % & ' "page rank""stationary distribution" of Markov chain"principal eigenvector" of transition matrixCompSci 100E3.13The Power Method• Q. If the surfer starts on page 0, what is theprobability that surfer ends up on page i after onestep?• A. First row of transition matrix.CompSci 100E3.14The Power Method• Q. If the surfer starts on page 0, what is theprobability that surfer ends up on page i after twosteps?• A. Matrix-vector multiplication.CompSci 100E3.15The Power Method• Power method. Repeat until page ranks converge.CompSci 100E3.16Mathematical Context• Convergence. For the random surfer model, thepower method iterates converge to aunique distribution, independent of the startingpage."page rank""stationary distribution" of Markov chain"principal eigenvector" of transition matrixCompSci 100E3.17CompSci 100E3.18Random Surfer: Scientific Challenges• Google's PageRank™ algorithm. [Sergey Brin and Larry Page,1998]! Rank importance of pages based on hyperlink structure of web,using 90-10 rule.! Revolutionized access to world's information.• Scientific challenges. Cope with 4 billion-by-4 billion matrix!! Need data structures to enable computation.! Need linear algebra to fully understand


View Full Document

Duke CPS 100E - Random Walks

Documents in this Course
Topics

Topics

9 pages

Lecture

Lecture

3 pages

Notes

Notes

2 pages

Hashing

Hashing

19 pages

Lecture

Lecture

59 pages

Lecture

Lecture

6 pages

Lecture

Lecture

4 pages

Lecture

Lecture

20 pages

Lecture

Lecture

12 pages

Lecture

Lecture

12 pages

Lecture

Lecture

7 pages

Lecture

Lecture

8 pages

Lecture

Lecture

10 pages

Lecture

Lecture

4 pages

Notes

Notes

16 pages

Lecture

Lecture

5 pages

Lecture

Lecture

9 pages

Lecture

Lecture

4 pages

Lecture

Lecture

13 pages

Lecture

Lecture

6 pages

Lecture

Lecture

16 pages

Lecture

Lecture

5 pages

Lecture

Lecture

5 pages

Lecture

Lecture

12 pages

Lecture

Lecture

12 pages

Lecture

Lecture

10 pages

Sets

Sets

14 pages

Lecture

Lecture

9 pages

Lecture

Lecture

4 pages

Test 1

Test 1

7 pages

Load more
Download Random Walks
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Random Walks and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Random Walks 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?