The stochastic approach for link-structure analysis (SALSA) and the TKC effect

Today, when searching for information on the World Wide Web, one usually pe rforms a query through a term-based search engine. These engines return, as the query's result, a list of Web sites whose contents match the query. Fo r broad topic queries, such searches often result in a huge set of retrieve d documents, many of which are irrelevant to the user. However, much inform ation is contained in the link-structure of the World Wide Web. Information such as which pages are linked to others can be used to augment search alg orithms. In this context, Jon Kleinberg introduced the notion of two distin ct types of Web sites: hubs and authorities. Kleinberg argued that hubs and authorities exhibit a mutually reinforcing relationship: a good hub will p oint to many authorities, and a good authority will be pointed at by many h ubs. In light of this, he devised an algorithm aimed at finding authoritati ve sites. We present SALSA, a new stochastic approach for link structure an alysis, which examines random walks on graphs derived from the link structu re. We show that both SALSA and Kleinberg's mutual reinforcement approach e mploy the same meta-algorithm. We then prove that SALSA is equivalent to a weighted in-degree analysis of the link-structure of World Wide Web subgrap hs, making it computationally more efficient than the mutual reinforcement approach. We compare the results of applying SALSA to the results derived t hrough kleinberg's approach. These comparisons reveal a topological phenome non called the TKC effect (Tightly Knit Community) which, in certain cases, prevents the mutual reinforcement approach from identifying meaningful aut horities. (C) 2000 Published by Elsevier Science B.V. All rights reserved.