Perron-Frobenius on the web
Saturday, May 14th, 2005Or, how to make a search engine.
Imagine the web is irreducible, by which I mean you could get from any page to any other by following links; pages without links (and pages no one links to) demonstrate that the web is not irreducible — but this is mathematics, so we are not going to let it worry us. Further, imagine there are millions of monkeyspigeons randomly clicking on links (forming a Markov chain). Perron-Frobenius theory can tell us the probability of these random walks through cyberspace visiting a particular page at an instance in time.