CS345Data Mining课件.ppt

Existence and Uniqueness h = λAa a = μAT h h = λμAAT h a = λμATA a Under reasonable assumptions about A, the dual iterative algorithm converges to vectors h* and a* such that: h* is the principal eigenvector of the matrix AAT a* is the principal eigenvector of the matrix ATA 精品文档 Bipartite cores Hubs Authorities Most densely-connected core (primary core) Less densely-connected core (secondary core) 精品文档 Secondary cores A single topic can have many bipartite cores corresponding to different meanings, or points of view abortion: pro-choice, pro-life evolution: darwinian, intelligent design jaguar: auto, Mac, NFL team, panthera onca How to find such secondary cores? 精品文档 Non-primary eigenvectors AAT and ATA have the same set of eigenvalues An eigenpair is the pair of eigenvectors with the same eigenvalue The primary eigenpair (largest eigenvalue) is what we get from the iterative algorithm Non-primary eigenpairs correspond to other bipartite cores The eigenvalue is a measure of the density of links in the core 精品文档 Finding secondary cores Once we find the primary core, we can remove its links from the graph Repeat HITS algorithm on residual graph to find the next bipartite core Technically, not exactly equivalent to non-primary eigenpair model 精品文档 Creating the graph for HITS We need a well-connected graph of pages for HITS to work well 精品文档 Page Rank and HITS Page Rank and HITS are two solutions to the same problem What is the value of an inlink from S to D? In the page rank model, the value of the link depends on the links into S In the HITS model, it depends on the value of the other links out of S The destinies of Page Rank and HITS post-1998 were very different Why? 精品文档 Web Spam Search has become the default gateway to the web Very high premium to appear on the first page of search results e.g., e-commerce sites advertising-driven sites 精品文档 What is web spam? Spamming = any deliberate action solely in order to boost a web page’s position in search engine res