《海量数据挖掘-王永利》ch05-linkanalysis2.pptVIP

* [Kleinberg ‘98] J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, Repeated matrix powering * Convergence criterion: J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * λ = 1 / ?hi μ = 1 / ?ai 1 1 1 A = 1 0 1 0 1 0 1 1 0 AT = 1 0 1 1 1 0 h(yahoo) h(amazon) h(m’soft) = = = .58 .58 .58 .80 .53 .27 .80 .53 .27 .79 .57 .23 . . . . . . . . . .788 .577 .211 a(yahoo) = .58 a(amazon) = .58 a(m’soft) = .58 .58 .58 .58 .62 .49 .62 . . . . . . . . . .628 .459 .628 .62 .49 .62 * Yahoo M’soft Amazon J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * * * * * * * * * * Do not forget to tell the joke I used to do this when I was young when talking about point (1) :D * 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-seller might pretend to be about “movies” Techniques for achieving high relevance/importance for a web page J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * 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 J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * 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