google hacking: Rahul Dutt Avasthy
These methods will be easily understood by the Hackers
Any help for the Novice Hackers Please drop in your Comments : Rahul
u can also drop in ur E - Mail Id's to be mailed a detailed Presentation on Google HACKING
Click Here to Drop Comments, Requests n Suggestions
Using Google, and some finely crafted searches we can find a lot of interesting information.
For Example we can find:
Credit Card Numbers
Passwords
Software / MP3's
...... (and on and on and on) Presented below is just a sample of interesting searches that we can send to google to obtain info that some people might not want us having.. After you get a taste using some of these, try your own crafted searches to find info that you would be interested in.
Try a few of these searches:
More searches which Mother Nature never intended! Most of these are handy for finding security exploits on your own site; simply add a string from your own domain’s URL to check. But really, why limit ourselves? If it has an evil purpose, I’m including it. By the way, there is nothing illegal about typing in a search string; it is up to the website to secure this data. It’s what you DO with this information that you find which makes all of the difference. signin filetype:url - OK, class, this is how we do NOT use Javascript to manage our passwords. Any questions? Javascript password block “index of /” ( upload.cfm | upload.asp | upload.php | upload.cgi | upload.jsp | upload.pl ) - A great way to find file upload pages on websites. Most of these will be password protected; every now and then you find one that isn’t! Like this German Spanish site… image upload I guess some civic-minded folk want to provide you with free file storage… (intitle:”WordPress › Setup Configuration File”)|(inurl:”setup-config.php?step=1″) - WordPress has become one of the leading blog systems out there. So you should be aware that if you run WordPress, there are black-hat hackers out there working around the clock to find a vulnerability on your site. Some of the hits returned from this search will be people who never configured it after they installed it, so it’s waiting for anyone to find it and take over. Now that we’re done plowing through all of the boring security research stuff, here’s a couple of cute tricks. In these last two cases, these may not be security violations at all; they might be intentionally giving the stuff away and the worst you’re doing is bypassing an ad or two. DSC00001.JPG - This was in a lot of bookmark sites lately. What you do is search Google images for this string… and if nobody else is looking, turn “safe search” off! What this is is the default naming scheme for image files taken on Sony digital cameras. People post the picture without renaming it. And don’t forget DSC00002.JPG, DSC00003.JPG, and so on. Judging by my browsing so far, the first thing most people photograph is their girlfriend. intitle:”index of” ”last modified” ”parent directory” (wmv|mp3) - At last the one everybody was waiting for: finding free media! Now, this example gives you directories with movie files in either MWV (Windows Media Viewer) or MP3. To find files on a particular subject, just enter the name of that subject. I’ll not speculate on what kind of movies you might be looking for - but I’m sure you’ll think of something! To change that to some other media file, you can try replacing wmv with jpg for images, wav for sounds, etc. The trouble is, this hack is so old that a number of adult porn sites have deliberately set up their web pages to mimic this result, where, of course, you end up with a pop-up demanding credit card data or getting link-jacked to a malware site. Have fun, and remember that I gave you all this handy info in the good faith that you’ll only use it responsibly.
intitle:"Index of" passwords modified
allinurl:auth_user_file.txt
"access denied for user" "using password"
"A syntax error has occurred" filetype:ihtml
allinurl: admin mdb
"ORA-00921: unexpected end of SQL command"
inurl:passlist.txt
"Index of /backup"
"Chatologica MetaSearch" "stack tracking:"
Amex Numbers: 300000000000000..399999999999999
MC Numbers: 5178000000000000..5178999999999999
visa 4356000000000000..4356999999999999
"parent directory " /appz/ -xxx -html -htm -php -shtml -opendivx -md5 -md5sums
"parent directory " DVDRip -xxx -html -htm -php -shtml -opendivx -md5 -md5sums
"parent directory "Xvid -xxx -html -htm -php -shtml -opendivx -md5 -md5sums
"parent directory " Gamez -xxx -html -htm -php -shtml -opendivx -md5 -md5sums
"parent directory "MP3-xxx -html -htm -php -shtml -opendivx -md5 -md5sums
"parent directory " Name of Singer or album -xxx -html -htm -php -shtml -opendivx -md5 -md5sums
Notice that I am only changing the word after the parent directory, change it to what you want and you will get a lot of stuff.
METHOD 2
put this string in google search:
?intitle:index.of? mp3
You only need add the name of the song/artist/singer.
Example: ?intitle:index.of? mp3 jackson
METHOD 3
put this string in google search:
inurl:microsoft filetype:iso
You can change the string to watever you want, ex. microsoft to adobe, iso to zip etc…
"# -FrontPage-" inurl:service.pwd
Frontpage passwords.. very nice clean search results listing !!
"AutoCreate=TRUE password=*"
This searches the password for "Website Access Analyzer"
, a Japanese software that creates webstatistics. For those who can read Japanese, check out the author's site at: http://www.coara.or.jp/~passy/
"http://*:*@www" domainname
This is a query to get inline passwords from search engines (not just Google), you must type in the query followed with the the domain name without the .com or .net
"http://*:*@www" bangbus or "http://*:*@www"bangbus
Another way is by just typing
"http://bob:bob@www"
"sets mode: +k"
This search reveals channel keys (passwords) on IRC as revealed from IRC chat logs.
allinurl: admin mdb
Not all of these pages are administrator's access databases containing usernames, passwords and other sensitive information, but many are!
allinurl:auth_user_file.txt
DCForum's password file. This file gives a list of (crackable) passwords, usernames and email addresses for DCForum and for DCShop (a shopping cart program(!!!). Some lists are bigger than others, all are fun, and all belong to googledorks. =)
intitle:"Index of" config.php
This search brings up sites with "config.php" files. To skip the technical discussion, this configuration file contains both a username and a password for an SQL database. Most sites with forums run a PHP message base. This file gives you the keys to that forum, including FULL ADMIN access to the database.
eggdrop filetype:user user
These are eggdrop config files. Avoiding a full-blown descussion about eggdrops and IRC bots, suffice it to say that this file contains usernames and passwords for IRC users.
intitle:index.of.etc
This search gets you access to the etc directory, where many many many types of password files can be found. This link is not as reliable, but crawling etc directories can be really fun!
filetype:bak inurl:"htaccess|passwd|shadow|htusers"
This will search for backup files (*.bak) created by some editors or even by the administrator himself (before activating a new version).
Every attacker knows that changing the extenstion of a file on a webserver can have ugly consequences.
Let's pretend you need a serial number for windows xp pro.
In the google search bar type in just like this - "Windows XP Professional" 94FBR
the key is the 94FBR code.. it was included with many MS Office registration codes so this will help you dramatically reduce the amount of 'fake' porn sites that trick you.
or if you want to
find the serial for winzip 8.1 - "Winzip 8.1"
Google Page Rank Explained
Grand Valley State University Imagine a library containing 25 billion documents but with no centralized organization and no librarians. In addition, anyone may add a document at any time without telling anyone. You may feel sure that one of the documents contained in the collection has a piece of information that is vitally important to you, and, being impatient like most of us, you'd like to find it in a matter of seconds. How would you go about doing it? Posed in this way, the problem seems impossible. Yet this description is not too different from the World Wide Web, a huge, highly-disorganized collection of documents in many different formats. Of course, we're all familiar with search engines (perhaps you found this article using one) so we know that there is a solution. This article will describe Google's PageRank algorithm and how it returns pages from the web's collection of 25 billion documents that match search criteria so well that "google" has become a widely used verb. Most search engines, including Google, continually run an army of computer programs that retrieve pages from the web, index the words in each document, and store this information in an efficient format. Each time a user asks for a web search using a search phrase, such as "search engine," the search engine determines all the pages on the web that contains the words in the search phrase. (Perhaps additional information such as the distance between the words "search" and "engine" will be noted as well.) Here is the problem: Google now claims to index 25 billion pages. Roughly 95% of the text in web pages is composed from a mere 10,000 words. This means that, for most searches, there will be a huge number of pages containing the words in the search phrase. What is needed is a means of ranking the importance of the pages that fit the search criteria so that the pages can be sorted with the most important pages at the top of the list. One way to determine the importance of pages is to use a human-generated ranking. For instance, you may have seen pages that consist mainly of a large number of links to other resources in a particular area of interest. Assuming the person maintaining this page is reliable, the pages referenced are likely to be useful. Of course, the list may quickly fall out of date, and the person maintaining the list may miss some important pages, either unintentionally or as a result of an unstated bias. Google's PageRank algorithm assesses the importance of web pages without human evaluation of the content. In fact, Google feels that the value of its service is largely in its ability to provide unbiased results to search queries; Google claims, "the heart of our software is PageRank." As we'll see, the trick is to ask the web itself to rank the importance of pages.
![\[ I(P_i)=\sum_{P_j\in B_i} \frac{I(P_j)}{l_j} \]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vUsQ9gtTuK7lZ8bfrQoEbt_NI4P-KL5DcOWHOcozPwJiso92588d39totZSAjJuevM5IbW-Hwi4IGcuF0dch6Q-zyrQn8uBOOLTt10gSDeimB_DYsa6jP_wIv7NRpuretGqm8=s0-d "\[ I(P_i)=\sum_{P_j\in B_i} \frac{I(P_j)}{l_j} \]")
This may remind you of the chicken and the egg: to determine the importance of a page, we first need to know the importance of all the pages linking to it. However, we may recast the problem into one that is more mathematically familiar. Let's first create a matrix, called the hyperlink matrix, ![$ {\bf H}=[H_{ij}] $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_tNh7aXla6jfIULcNEeigAmld2zGif4XNmUa07M7Wy7YBS1XI6kJCNRV-RlIsCk3SsKU79lQg3IKHuQWM2sCzxnkHPc3ohXjsiC0MmlqZYaKiNK08WJSjlXwJW8pj0IG1Rdkr0=s0-d "$ {\bf H}=[H_{ij}] $")
in which the entry in the ith row and jth column is ![\[ H_{ij}=\left\{\begin{array}{ll}1/l_{j} & \hbox{if } P_j\in B_i \\ 0 & \hbox{otherwise} \end{array}\right. \]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_tjgHOUY4WfOvDvTFpnDe9Qrczp0CL0iKVxQzSLoHPEW2YoMjLMfUkVqXcvxy-maMBtnfTXfysPHPhJvZ8R9sJ4K0PbgQCJpRKASQDFHXiagbHzwEbeUT8MjIZwiDx2kYfBSxE=s0-d "\[ H_{ij}=\left\{\begin{array}{ll}1/l_{j} & \hbox{if } P_j\in B_i \\ 0 & \hbox{otherwise} \end{array}\right. \]")
Notice that H has some special properties. First, its entries are all nonnegative. Also, the sum of the entries in a column is one unless the page corresponding to that column has no links. Matrices in which all the entries are nonnegative and the sum of the entries in every column is one are called stochastic; they will play an important role in our story. We will also form a vector ![$ I=[I(P_i)] $](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_uOZnsKjAJUyRWwhHDCWM0vvHEoEiC0zZCPRZ-VwMx7huZO0LZOu2ldoe9Dy_6k-L8aW6ExISk--clUcnJfm73D4p6s6QwDKMFxQ5kie6Tqhvc6BLeYN5bcREjwE-FkzHEtCe4=s0-d "$ I=[I(P_i)] $")
whose components are PageRanks--that is, the importance rankings--of all the pages. The condition above defining the PageRank may be expressed as ![\[ I = {\bf H}I \]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vnUXT8XL9rqS1hKpLW2If_EZoJGdz-qJC7WcEYs80XA9uvOWIcZtBMclP-CSgq65smyWATzsgFZOC1vURc7mdr4Ef3My3NuTc6Nl7V6bb6Ure07LO3OLSKLDUjqPkNzhAP8gc=s0-d "\[ I = {\bf H}I \]")
In other words, the vector I is an eigenvector of the matrix H with eigenvalue 1. We also call this a stationary vector of H. Let's look at an example. Shown below is a representation of a small collection (eight) of web pages with links represented by arrows. 
The corresponding matrix is
This shows that page 8 wins the popularity contest. Here is the same figure with the web pages shaded in such a way that the pages with higher PageRanks are lighter. 
![\[ I^{k+1}={\bf H}I^k \]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_u_Q6EDQkpAxMAX7C2tZ4xiE03bsE3ZTkBLazJchEDoruS2N1_uDmgmGojV2LcFmbfpaNALCqI59_wEHLvIJTLkLzMpN3SVtbVeq_7AwHswF1jVkH0a21XKqB8KH3THEpGgBQ=s0-d "\[ I^{k+1}={\bf H}I^k \]")
The method is founded on the following general principle that we will soon investigate.
We will illustrate with the example above.
It is natural to ask what these numbers mean. Of course, there can be no absolute measure of a page's importance, only relative measures for comparing the importance of two pages through statements such as "Page A is twice as important as Page B." For this reason, we may multiply all the importance rankings by some fixed quantity without affecting the information they tell us. In this way, we will always assume, for reasons to be explained shortly, that the sum of all the popularities is one.
Here is one way in which our algorithm could proceed:
In this case, the importance rating of both pages is zero, which tells us nothing about the relative importance of these pages. The problem is that P2 has no links. Consequently, it takes some of the importance from page P1 in each iterative step but does not pass it on to any other page. This has the effect of draining all the importance from the web. Pages with no links are called dangling nodes, and there are, of course, many of them in the real web we want to study. We'll see how to deal with them in a minute, but first let's consider a new way of thinking about the matrix H and stationary vector I. 
. As we surf randomly, we will denote by 
the fraction of time that we spend on page Pj. Then the fraction of the time that we end up on page Pi page coming from Pj is 
. If we end up on Pi, we must have come from a page linking to it. This means that ![\[ T_i = \sum_{P_j\in B_i} T_j/l_j \]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_tfHW5sSL_iSPsExVrLuDym5rJl3pcSb4rRnP1G9073v20xeLivrDRPXDjt2n7fHkMBYQQmuu2UQDguCOXwLGsXCZukrcXi2Dc1ImcWiH1tzvsebkx1cQxkTK16FqJbiWCXmrJk=s0-d "\[ T_i = \sum_{P_j\in B_i} T_j/l_j \]")
where the sum is over all the pages Pj linking to Pi. Notice that this is the same equation defining the PageRank rankings and so 
. This allows us to interpret a web page's PageRank as the fraction of time that a random surfer spends on that web page. This may make sense if you have ever surfed around for information about a topic you were unfamiliar with: if you follow links for a while, you find yourself coming back to some pages more often than others. Just as "All roads lead to Rome," these are typically more important pages. Notice that, given this interpretation, it is natural to require that the sum of the entries in the PageRank vector I be one. Of course, there is a complication in this description: If we surf randomly, at some point we will surely get stuck at a dangling node, a page with no links. To keep going, we will choose the next page at random; that is, we pretend that a dangling node has a link to every other page. This has the effect of modifying the hyperlink matrix H by replacing the column of zeroes corresponding to a dangling node with a column in which each entry is 1/n. We call this new matrix S. In our previous example, we now have
In other words, page P2 has twice the importance of page P1, which may feel about right to you. The matrix S has the pleasant property that the entries are nonnegative and the sum of the entries in each column is one. In other words, it is stochastic. Stochastic matrices have several properties that will prove useful to us. For instance, stochastic matrices always have stationary vectors. For later purposes, we will note that S is obtained from H in a simple way. If A is the matrix whose entries are all zero except for the columns corresponding to dangling nodes, in which each entry is 1/n, then S = H + A. ![]()
S are ![src=]()
S are ![align=]()
and that ![]()
|\lambda_2| \geq |\lambda_3| \geq \ldots \geq |\lambda_n| \] " src="http://www.ams.org/featurecolumn/images/december2006/index_15.gif" title="\[ 1 = \lambda_1 > |\lambda_2| \geq |\lambda_3| \geq \ldots \geq |\lambda_n| \] " align="absmiddle"> We will also assume that there is a basis vj of eigenvectors for S with corresponding eigenvalues 
. This assumption is not necessarily true, but with it we may more easily illustrate how the power method works. We may write our initial vector I 0 as ![\[ I^0 = c_1v_1+c_2v_2 + \ldots + c_nv_n \]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_ueEAWgnUvtizx5zR2IrV-us7z-gBHNEJF_Q-L5RX4VeONpbUUt44o6ogc0o63CQa4xI8pg6Kiip1Z8WkQ03eGxI4tDvZ05HOPJKDTwOTzuL_hWjtCXo32N_6JegMZCBNwMqITf=s0-d "\[ I^0 = c_1v_1+c_2v_2 + \ldots + c_nv_n \]")
Then 
Since the eigenvalues 
with 
have magnitude smaller than one, it follows that 
if 
and therefore 
, an eigenvector corresponding to the eigenvalue 1. It is important to note here that the rate at which 
is determined by 
. When 
is relatively close to 0, then 
relatively quickly. For instance, consider the matrix ![\[ {\bf S} = \left[\begin{array}{cc}0.65 & 0.35 \\ 0.35 & 0.65 \end{array}\right]. \]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_uIVzIJT4uXuzGg2AYq6pHmuOrBpkdQVwWq8VwsBTMa8o-4ysIhVMGnDhNkQma3eP0q6lY0Mh3-JdyrN_HVOIECLQbvbeox-ha3dZ_Ezzg1LBQ246e5JTocHR47jWzCk0pwXiw=s0-d "\[ {\bf S} = \left[\begin{array}{cc}0.65 & 0.35 \\ 0.35 & 0.65 \end{array}\right]. \]")
The eigenvalues of this matrix are 
and 
. In the figure below, we see the vectors I k, shown in red, converging to the stationary vector I shown in green. 
Now consider the matrix ![\[ {\bf S} = \left[\begin{array}{cc}0.85 & 0.15 \\ 0.15 & 0.85 \end{array}\right]. \]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_tVuXnz1vC3vWlqqVqT6Lg1wL4lrPm09lqE4JIQN0dY2eGpDiAX7PkgdP97JgVLpBquEx2qrfnGfhp_SxinaVDyvnOArjOEOanRRNEr6WvaC-ofhLKIyNnbkZxidr3x4ksSPxs=s0-d "\[ {\bf S} = \left[\begin{array}{cc}0.85 & 0.15 \\ 0.15 & 0.85 \end{array}\right]. \]")
Here the eigenvalues are 
and 
. Notice how the vectors I k converge more slowly to the stationary vector I in this example in which the second eigenvalue has a larger magnitude. 
and ![]()
S is 
S is ![]()
Then we see
In this case, the sequence of vectors I k fails to converge. Why is this? The second eigenvalue of the matrix S satisfies 
and so the argument we gave to justify the power method no longer holds. To guarantee that ![]()
. This means that, for some m, Sm has all positive entries. In other words, if we are given two pages, it is possible to get from the first page to the second after following m links. Clearly, our most recent example does not satisfy this property. In a moment, we will see how to modify our matrix S to obtain a primitive, stochastic matrix, which therefore satisfies ![src=]()
. This means that, for some m, Sm has all positive entries. In other words, if we are given two pages, it is possible to get from the first page to the second after following m links. Clearly, our most recent example does not satisfy this property. In a moment, we will see how to modify our matrix S to obtain a primitive, stochastic matrix, which therefore satisfies ![]()
S is
Notice that the PageRanks assigned to the first four web pages are zero. However, this doesn't feel right: each of these pages has links coming to them from other pages. Clearly, somebody likes these pages! Generally speaking, we want the importance rankings of all pages to be positive. The problem with this example is that it contains a smaller web within it, shown in the blue box below. 
Links come into this box, but none go out. Just as in the example of the dangling node we discussed above, these pages form an "importance sink" that drains the importance out of the other four pages. This happens when the matrix S is reducible; that is, S can be written in block form as ![\[ S=\left[\begin{array}{cc} * & 0 \\ * & * \end{array}\right]. \]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_s9LsLE8Cg81nai2x4ZqRnElHq_Y3FvkwokGX-J_gpzxVORcNwucJkykXUlk3uWXfVDfkQQe5DqqLaw_4flJqoOdhekk-SFmZnJV_sE1Oqbav1xxQ-AW2duXE3jwUDrjSmS0x5C=s0-d "\[ S=\left[\begin{array}{cc} * & 0 \\ * & * \end{array}\right]. \]")
Indeed, if the matrix S is irreducible, we can guarantee that there is a stationary vector with all positive entries. A web is called strongly connected if, given any two pages, there is a way to follow links from the first page to the second. Clearly, our most recent example is not strongly connected. However, strongly connected webs provide irreducible matrices S. To summarize, the matrix S is stochastic, which implies that it has a stationary vector. However, we need S to also be (a) primitive so that ![]()
To find a new matrix that is both primitive and irreducible, we will modify the way our random surfer moves through the web. As it stands now, the movement of our random surfer is determined by S: either he will follow one of the links on his current page or, if at a page with no links, randomly choose any other page to move to. To make our modification, we will first choose a parameter ![src=]()
To find a new matrix that is both primitive and irreducible, we will modify the way our random surfer moves through the web. As it stands now, the movement of our random surfer is determined by S: either he will follow one of the links on his current page or, if at a page with no links, randomly choose any other page to move to. To make our modification, we will first choose a parameter ![align=]()
between 0 and 1. Now suppose that our random surfer moves in a slightly different way. With probability 
, he is guided by S. With probability 
, he chooses the next page at random. If we denote by 1 the 
matrix whose entries are all one, we obtain the Google matrix: ![\[ {\bf G}=\alpha{\bf S}+ (1-\alpha)\frac{1}{n}{\bf 1} \]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_ufo64_Bcnnt2hnz5YDASJH3yV7nfOBR_bTzkA_PCoe2OuhkLbxuZ735lt5N3rugUSUWloljEP5dy5Wq-doqrIBk-jgbnbWc36PSLjy08YrpR_u-N_egRW0riMK-BB7ahqjY77e=s0-d "\[ {\bf G}=\alpha{\bf S}+ (1-\alpha)\frac{1}{n}{\bf 1} \]")
Notice now that G is stochastic as it is a combination of stochastic matrices. Furthermore, all the entries of G are positive, which implies that G is both primitive and irreducible. Therefore, G has a unique stationary vector I that may be found using the power method. The role of the parameter is an important one. Notice that if 
, then G = S. This means that we are working with the original hyperlink structure of the web. However, if 
, then 
. In other words, the web we are considering has a link between any two pages and we have lost the original hyperlink structure of the web. Clearly, we would like to take close to 1 so that we hyperlink structure of the web is weighted heavily into the computation. However, there is another consideration. Remember that the rate of convergence of the power method is governed by the magnitude of the second eigenvalue 
. For the Google matrix, it has been proven that the magnitude of the second eigenvalue 
. This means that when is close to 1 the convergence of the power method will be very slow. As a compromise between these two competing interests, Serbey Brin and Larry Page, the creators of PageRank, chose 
. 
matrices where n is about 25 billion! In fact, the power method is especially well-suited to this situation. Remember that the stochastic matrix S may be written as ![\[ {\bf S}={\bf H} + {\bf A} \]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vCP5li-hcWcnQZTxlO8y8T0u4BIjvsKRQe_z3xYBafI8RqwDLKjNqQJM21w2J2d5A91WCcWGVJ-ueX3oEkAoIzXyCz1uoL4r7SGxFjIfS9ScfnM_jv9qUhWsMmiJMHw-tJM12T=s0-d "\[ {\bf S}={\bf H} + {\bf A} \]")
and therefore the Google matrix has the form ![\[ {\bf G}=\alpha{\bf H} + \alpha{\bf A} + \frac{1-\alpha}{n}{\bf 1} \]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_uy9Mi3klfBhXvCmF4coPveDOC-Fupn2cdq9yPUcLGQmlZDaZbIs42802RENyk7H5PPspNxzi6h0RyGQ36MDZY-5rBwqla56ARkygJwYKZj4LhwWuaWpcrHoq_RFaHhD1fm_DbF=s0-d "\[ {\bf G}=\alpha{\bf H} + \alpha{\bf A} + \frac{1-\alpha}{n}{\bf 1} \]")
Therefore, ![\[ {\bf G}I^k=\alpha{\bf H}I^k + \alpha{\bf A}I^k + \frac{1-\alpha}{n}{\bf 1}I^k \]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_u80wYLOAzElq4eiFwaMi047PHkkqJa_k2iMxkPLIwOzEQnII9I3mBTMZGmaK2eq0heZB3qGjQqkCuNmmrstNuaFeYJtFruRUQ2rjjn9Ks683q3xL77_w9GziqMiJEYE-BHZlXN=s0-d "\[ {\bf G}I^k=\alpha{\bf H}I^k + \alpha{\bf A}I^k + \frac{1-\alpha}{n}{\bf 1}I^k \]")
Now recall that most of the entries in H are zero; on average, only ten entries per column are nonzero. Therefore, evaluating HI k requires only ten nonzero terms for each entry in the resulting vector. Also, the rows of A are all identical as are the rows of 1. Therefore, evaluating AI k and 1I k amounts to adding the current importance rankings of the dangling nodes or of all web pages. This only needs to be done once. With the value of chosen to be near 0.85, Brin and Page report that 50 - 100 iterations are required to obtain a sufficiently good approximation to I. The calculation is reported to take a few days to complete. Of course, the web is continually changing. First, the content of web pages, especially for news organizations, may change frequently. In addition, the underlying hyperlink structure of the web changes as pages are added or removed and links are added or removed. It is rumored that Google recomputes the PageRank vector I roughly every month. Since the PageRank of pages can be observed to fluctuate considerably during this time, it is known to some as the Google Dance. (In 2002, Google held a Google Dance!)
How to tell who's important
If you've ever created a web page, you've probably included links to other pages that contain valuable, reliable information. By doing so, you are affirming the importance of the pages you link to. Google's PageRank algorithm stages a monthly popularity contest among all pages on the web to decide which pages are most important. The fundamental idea put forth by PageRank's creators, Sergey Brin and Lawrence Page, is this: the importance of a page is judged by the number of pages linking to it as well as their importance. We will assign to each web page P a measure of its importance I(P), called the page's PageRank. At various sites, you may find an approximation of a page's PageRank. (For instance, the home page of The American Mathematical Society currently has a PageRank of 8 on a scale of 10. Can you find any pages with a PageRank of 10?) This reported value is only an approximation since Google declines to publish actual PageRanks in an effort to frustrate those would manipulate the rankings. Here's how the PageRank is determined. Suppose that page Pj has lj links. If one of those links is to page Pi, then Pj will pass on 1/lj of its importance to Pi. The importance ranking of Pi is then the sum of all the contributions made by pages linking to it. That is, if we denote the set of pages linking to Pi by Bi, then This may remind you of the chicken and the egg: to determine the importance of a page, we first need to know the importance of all the pages linking to it. However, we may recast the problem into one that is more mathematically familiar. Let's first create a matrix, called the hyperlink matrix, in which the entry in the ith row and jth column is Notice that H has some special properties. First, its entries are all nonnegative. Also, the sum of the entries in a column is one unless the page corresponding to that column has no links. Matrices in which all the entries are nonnegative and the sum of the entries in every column is one are called stochastic; they will play an important role in our story. We will also form a vector whose components are PageRanks--that is, the importance rankings--of all the pages. The condition above defining the PageRank may be expressed as In other words, the vector I is an eigenvector of the matrix H with eigenvalue 1. We also call this a stationary vector of H. Let's look at an example. Shown below is a representation of a small collection (eight) of web pages with links represented by arrows. The corresponding matrix is  | with stationary vector |  |
Computing I
There are many ways to find the eigenvectors of a square matrix. However, we are in for a special challenge since the matrix H is a square matrix with one column for each web page indexed by Google. This means that H has about n = 25 billion columns and rows. However, most of the entries in H are zero; in fact, studies show that web pages have an average of about 10 links, meaning that, on average, all but 10 entries in every column are zero. We will choose a method known as the power method for finding the stationary vector I of the matrix H. How does the power method work? We begin by choosing a vector I 0 as a candidate for I and then producing a sequence of vectors I k by The method is founded on the following general principle that we will soon investigate. | General principle: The sequence I k will converge to the stationary vector I. |
| I 0 | I 1 | I 2 | I 3 | I 4 | ... | I 60 | I 61 |
| 1 | 0 | 0 | 0 | 0.0278 | ... | 0.06 | 0.06 |
| 0 | 0.5 | 0.25 | 0.1667 | 0.0833 | ... | 0.0675 | 0.0675 |
| 0 | 0.5 | 0 | 0 | 0 | ... | 0.03 | 0.03 |
| 0 | 0 | 0.5 | 0.25 | 0.1667 | ... | 0.0675 | 0.0675 |
| 0 | 0 | 0.25 | 0.1667 | 0.1111 | ... | 0.0975 | 0.0975 |
| 0 | 0 | 0 | 0.25 | 0.1806 | ... | 0.2025 | 0.2025 |
| 0 | 0 | 0 | 0.0833 | 0.0972 | ... | 0.18 | 0.18 |
| 0 | 0 | 0 | 0.0833 | 0.3333 | ... | 0.295 | 0.295 |
Three important questions
Three questions naturally come to mind:- Does the sequence I k always converge?
- Is the vector to which it converges independent of the initial vector I 0?
- Do the importance rankings contain the information that we want?
 | with matrix |  |
| I 0 | I 1 | I 2 | I 3=I |
| 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 |
A probabilitistic interpretation of H
Imagine that we surf the web at random; that is, when we find ourselves on a web page, we randomly follow one of its links to another page after one second. For instance, if we are on page Pj with lj links, one of which takes us to page Pi, the probability that we next end up on Pi page is then . As we surf randomly, we will denote by the fraction of time that we spend on page Pj. Then the fraction of the time that we end up on page Pi page coming from Pj is . If we end up on Pi, we must have come from a page linking to it. This means that where the sum is over all the pages Pj linking to Pi. Notice that this is the same equation defining the PageRank rankings and so . This allows us to interpret a web page's PageRank as the fraction of time that a random surfer spends on that web page. This may make sense if you have ever surfed around for information about a topic you were unfamiliar with: if you follow links for a while, you find yourself coming back to some pages more often than others. Just as "All roads lead to Rome," these are typically more important pages. Notice that, given this interpretation, it is natural to require that the sum of the entries in the PageRank vector I be one. Of course, there is a complication in this description: If we surf randomly, at some point we will surely get stuck at a dangling node, a page with no links. To keep going, we will choose the next page at random; that is, we pretend that a dangling node has a link to every other page. This has the effect of modifying the hyperlink matrix H by replacing the column of zeroes corresponding to a dangling node with a column in which each entry is 1/n. We call this new matrix S. In our previous example, we now have | with matrix |  | and eigenvector |  |
How does the power method work?
In general, the power method is a technique for finding an eigenvector of a square matrix corresponding to the eigenvalue with the largest magnitude. In our case, we are looking for an eigenvector of S corresponding to the eigenvalue 1. Under the best of circumstances, to be described soon, the other eigenvalues of S will have a magnitude smaller than one; that is, . This assumption is not necessarily true, but with it we may more easily illustrate how the power method works. We may write our initial vector I 0 as Then Since the eigenvalues with have magnitude smaller than one, it follows that if and therefore , an eigenvector corresponding to the eigenvalue 1. It is important to note here that the rate at which is determined by . When is relatively close to 0, then relatively quickly. For instance, consider the matrix The eigenvalues of this matrix are and . In the figure below, we see the vectors I k, shown in red, converging to the stationary vector I shown in green. Now consider the matrix Here the eigenvalues are and . Notice how the vectors I k converge more slowly to the stationary vector I in this example in which the second eigenvalue has a larger magnitude. When things go wrong
In our discussion above, we assumed that the matrix S had the property that and | I 0 | I 1 | I 2 | I 3 | I 4 | I 5 |
| 1 | 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 | 0 |
and so the argument we gave to justify the power method no longer holds. To guarantee that  | with stationary vector |  |
Links come into this box, but none go out. Just as in the example of the dangling node we discussed above, these pages form an "importance sink" that drains the importance out of the other four pages. This happens when the matrix S is reducible; that is, S can be written in block form as Indeed, if the matrix S is irreducible, we can guarantee that there is a stationary vector with all positive entries. A web is called strongly connected if, given any two pages, there is a way to follow links from the first page to the second. Clearly, our most recent example is not strongly connected. However, strongly connected webs provide irreducible matrices S. To summarize, the matrix S is stochastic, which implies that it has a stationary vector. However, we need S to also be (a) primitive so that , he is guided by S. With probability , he chooses the next page at random. If we denote by 1 the matrix whose entries are all one, we obtain the Google matrix: Notice now that G is stochastic as it is a combination of stochastic matrices. Furthermore, all the entries of G are positive, which implies that G is both primitive and irreducible. Therefore, G has a unique stationary vector I that may be found using the power method. The role of the parameter is an important one. Notice that if , then G = S. This means that we are working with the original hyperlink structure of the web. However, if , then . In other words, the web we are considering has a link between any two pages and we have lost the original hyperlink structure of the web. Clearly, we would like to take close to 1 so that we hyperlink structure of the web is weighted heavily into the computation. However, there is another consideration. Remember that the rate of convergence of the power method is governed by the magnitude of the second eigenvalue . For the Google matrix, it has been proven that the magnitude of the second eigenvalue . This means that when is close to 1 the convergence of the power method will be very slow. As a compromise between these two competing interests, Serbey Brin and Larry Page, the creators of PageRank, chose . Computing I
What we've described so far looks like a good theory, but remember that we need to apply it to matrices where n is about 25 billion! In fact, the power method is especially well-suited to this situation. Remember that the stochastic matrix S may be written as and therefore the Google matrix has the form Therefore, Now recall that most of the entries in H are zero; on average, only ten entries per column are nonzero. Therefore, evaluating HI k requires only ten nonzero terms for each entry in the resulting vector. Also, the rows of A are all identical as are the rows of 1. Therefore, evaluating AI k and 1I k amounts to adding the current importance rankings of the dangling nodes or of all web pages. This only needs to be done once. With the value of chosen to be near 0.85, Brin and Page report that 50 - 100 iterations are required to obtain a sufficiently good approximation to I. The calculation is reported to take a few days to complete. Of course, the web is continually changing. First, the content of web pages, especially for news organizations, may change frequently. In addition, the underlying hyperlink structure of the web changes as pages are added or removed and links are added or removed. It is rumored that Google recomputes the PageRank vector I roughly every month. Since the PageRank of pages can be observed to fluctuate considerably during this time, it is known to some as the Google Dance. (In 2002, Google held a Google Dance!) Summary
Brin and Page introduced Google in 1998, a time when the pace at which the web was growing began to outstrip the ability of current search engines to yield useable results. At that time, most search engines had been developed by businesses who were not interested in publishing the details of how their products worked. In developing Google, Brin and Page wanted to "push more development and understanding into the academic realm." That is, they hoped, first of all, to improve the design of search engines by moving it into a more open, academic environment. In addition, they felt that the usage statistics for their search engine would provide an interesting data set for research. It appears that the federal government, which recently tried to gain some of Google's statistics, feels the same way. There are other algorithms that use the hyperlink structure of the web to rank the importance of web pages. One notable example is the HITS algorithm, produced by Jon Kleinberg, which forms the basis of the Teoma search engine. In fact, it is interesting to compare the results of searches sent to different search engines as a way to understand why some complain of a Googleopoly.Better Search engine
| Search Engine name http://www.gahooyoogle.com/ *** http://www.jux2.com/ ***** http://www.dogpile.com/ ***** http://www.sputtr.com/ ***** http://www.spacetime.com/ http://mindset.research.yahoo.com/ http://www.mooter.com/ http://qunu.com/ http://www.webcrawler.com/info.wbcrwl/ http://www.scirus.com/srsapp/ http://www.randomwebsearch.com/ http://www.soople.com/soople_int.php | URL | Category |
| Accoona | www.accoona.com | A.I. Search (HM) |
| AfterVote (SEM) | www.aftervote.com | Social Search |
| Agent 55 | www.agent55.com | MetaSearch |
| AllTha.at | www.allth.at | Continuous Search |
| AnswerBus | www.answerbus.com | Semantic Search |
| Blabline | www.blabline.com | Podcast Search |
| Blinkx* | www.blinkx.com | Video Search |
| Blogdigger | www.blogdigger.com | Blog Search |
| Bookmach.com* | www.bookmach.com | Bookmark Search |
| ChaCha* (#1 2006) | www.chacha.com | Guided Search |
| ClipBlast!* | www.clipblast.com | Video Search |
| Clusty* | www.clusty.com | Clustering Search |
| CogHog | www.infactsolutions.com/projects/coghog/demo.htm | Semantic Search |
| Collarity* | www.collarity.com | Social Search (HM) |
| Congoo* | www.congoo.com | Premium Content Search |
| CrossEngine (Mr. Sapo)* | www.crossengine.com | MetaSearch |
| Cydral | http://en.cydral.com | Image Search (French) |
| Decipho* | www.decipho.com | Filtered Search |
| Deepy | www.deepy.com | RIA Search |
| Ditto* | www.ditto.com | Visual Search |
| Dogpile | www.dogpile.com | MetaSearch |
| Exalead* | www.exalead.com/search | Visual Search |
| Factbites* | www.factbites.com | Filtered Search |
| FeedMiner | www.feedminer.com | RSS Feeds Search |
| Feedster | www.feedster.com | RSS Feeds Search |
| Filangy | www.filangy.com | Social Search |
| Find Forward | www.findforward.com | Meta Feature Search |
| FindSounds* | www.findsounds.com | Audio Search |
| Fisssh! | www.fisssh.com | Filtered Search (HM) |
| FyberSearch | www.fybersearch.com | Meta Feature Search |
| Gigablast* | www.gigablast.com | Blog Search |
| Girafa* | www.girafa.com | Visual Display |
| Gnosh | www.gnosh.org | Meta Search |
| GoLexa | www.golexa.com | Meta Feature Search |
| GoshMe* (SEM) | www.goshme.com | Meta Meta Search |
| GoYams* | www.goyams.com | Meta Search |
| Grokker* | www.grokker.com | Meta Search |
| Gruuve | www.gruuve.com | Recommendation Search |
| Hakia | www.hakia.com | Meaning Based Search |
| Hyper Search | http://hypersearch.webhop.org.90.seekdotnet.com | Filtered Search |
| iBoogie | www.iboogie.com | Clustering Search |
| IceRocket* | www.icerocket.com | Blog Search |
| Info.com | www.info.com | MetaSearch |
| Ixquick* | www.ixquick.com | Meta Search |
| KartOO* | www.kartoo.com | Clustering Search |
| KoolTorch (SEM) | www.kooltorch.com | Clustering Search |
| Lexxe* | www.lexxe.com | Natural Language Processing (NLP) |
| Lijit | www.lijit.com | Search People |
| Like* | www.like.com | Visual Search |
| LivePlasma* | www.liveplasma.com | Recommendation Search (HM) |
| Local.com* | www.local.com | Local Search |
| Mamma | www.mamma.com | MetaSearch |
| Mnemomap | www.mnemo.org | Clustering Search |
| Mojeek* | www.mojeek.com | Custom Search Engines (CSE) |
| Mooter* | www.mooter.com | Clustering Search |
| Mp3Realm | http://mp3realm.org | MP3 Search |
| Mrquery | www.mrquery.com | Clustering Search |
| Ms. Dewey* | www.msdewey.com | Unique Interface (HM) |
| Nutshell | www.gonutshell.com | MetaSearch |
| Omgili | www.omgili.com | Social Search |
| Pagebull* | www.pagebull.com | Visual Display |
| PeekYou | www.peekyou.com | People Search |
| Pipl | http://pipl.com | People Search |
| PlanetSearch* | www.planetsearch.com | MetaSearch |
| PodZinger | www.podzinger.com | Podcast Search |
| PolyMeta | www.polymeta.com | MetaSearch |
| Prase | www.prase.us | MetaSearch |
| PureVideo | www.purevideo.com | Video Search (HM) |
| Qksearch | www.qksearch.com | Clustering Search |
| Querycat | http://querycat.com | F.A.Q. Search (HM) |
| Quintura* | www.quintura.com | Clustering Search |
| RedZee | www.redzee.com | Visual Display |
| Retrievr | http://labs.systemone.at/retrievr/ | Visual Search |
| Searchbots | www.searchbots.net | Continuous Search |
| SearchKindly | www.searchkindly.org | Charity Search |
| Searchles* (DumbFind) | www.searchles.com | Social Search |
| SearchTheWeb2* | www.searchtheweb2.com | Long Tail Search |
| SeeIt | www.seeit.com | Image Search |
| Sidekiq* | www.sidekiq.com | MetaSearch |
| Slideshow* | http://slideshow.zmpgroup.com/ | Visual Display |
| Slifter* | www.slifter.com | Mobile Shopping Search (HM) |
| Sphere | www.sphere.com | Blog Search |
| Sproose | www.sproose.com | Social Search |
| Srchr* | www.srchr.com | MetaSearch |
| SurfWax* | www.surfwax.com | Meaning Based Search |
| Swamii | www.swamii.com | Continuous Search (HM) |
| TheFind.com* | www.thefind.com | Shopping Search |
| Trexy* | www.trexy.com | Search Trails |
| Turboscout* | www.turboscout.com | MetaSearch |
| Twerq | www.twerq.com | Tabbed Results |
| Url.com* | www.url.com | Social Search |
| WasaLive! | http://en.wasalive.com | RSS Search |
| Web 2.0* | www.web20searchengine.com | Web 2.0 Search |
| Webbrain* | www.webbrain.com | Clustering Search |
| Whonu?* | www.whonu.com | MetaSearch |
| Wikio* | www.wikio.com | Web 2.0 Search |
| WiseNut* | www.wisenut.com | Clustering Search |
| Yoono* | www.yoono.com | Social Search |
| ZabaSearch* | www.zabasearch.com | People Search |
| Zuula* | www.zuula.com | Tabbed Search (HM) |
No comments:
Post a Comment