Lempel R, Moran S "SALSA: The stochastic approach for link-structure analysis" ACM TRANSACTIONS ON INFORMATION SYSTEMS 19 (2): 131-160 APR 2001

[Eugene Garfield]

R. Lempel   lempel at cs.technion.ac.il
S. Moran moran at cs.technion.ac.il

TITLE SALSA: The stochastic approach for link-structure analysis
AUTHOR Lempel R, Moran S
JOURNAL ACM TRANSACTIONS ON INFORMATION SYSTEMS 19 (2): 131-160 APR 2001

 Document type: Article    Language: English    Cited References: 25
Times Cited: 0


Abstract:
Today, when searching for information on the WWW, one usually performs a
query through a term-based search engine. These engines return, as the
query's result, a list of Web pages whose contents matches the query. For
broad-topic queries, such searches often result in a huge set of retrieved
documents, many of which are irrelevant to the user. However, much
information is contained in the link-structure of the WWW. Information such
as which pages are linked to others can be used to augment search
algorithms. In this context, Jon Kleinberg introduced the notion of two
distinct types of Web pages: hubs and authorities. Kleinberg argued that
hubs and authorities exhibit a mutually reinforcing relationship: a good hub
will point to many authorities, and a good authority will be pointed at by
many hubs. In light of this, he devised an algorithm aimed at finding
authoritative pages. We present SALSA, a new stochastic approach for
link-structure analysis, which examines random walks on graphs derived from
the link-structure. We show that both SALSA and Kleinberg's Mutual
Reinforcement approach employ the same metaalgorithm. We then prove that
SALSA is equivalent to a weighted in-degree analysis of the link-structure
of WWW subgraphs, making it computationally more efficient than the Mutual
Reinforcement approach. We compare the results of applying SALSA to the
results derived through Kleinberg's approach. These comparisons reveal a
topological phenomenon called the TKC Effect which, in certain cases,
prevents the Mutual Reinforcement approach from identifying meaningful
authorities.

Author Keywords:
algorithms, experimentation, theory, link-structure analysis, hubs and
authorities, random walks, SALSA, TKC effect

KeyWords Plus:
CITATION

Addresses:
Lempel R, Technion Israel Inst Technol, Dept Comp Sci, IL-32000 Haifa,
Israel
Technion Israel Inst Technol, Dept Comp Sci, IL-32000 Haifa, Israel

Publisher:
ASSOC COMPUTING MACHINERY, NEW YORK

IDS Number:
462PL

ISSN:
1046-8188

Cited Author            Cited Work                Volume      Page      Year

 AUGUSTSON JG          J ASSOCIATION COMPUT          17       571      1970
 BHARAT K              P 21 ANN INT ACM SIG                   104      1998
 BOTAFOGO RA           ACM T INFORM SYST             10       142      1992
 BRIN S                P 7 INT C WWW                                   1998
 CARRIERE J            P 6 INT C WWW                                   1997
 CHAKRABARTI S         IEEE COMPUTER    AUG                            1999
 CHAKRABARTI S         P 7 INT WWW C                                   1998
 CHAKRABARTI S         P ACM SIGIR WORKSH H                            1998
 CHAKRABARTI S         SCI AM           JUN                            1999
 FRISSE ME             COMMUN ACM                    31       880      1988
 FURNKRANZ J           TROEFAI9829 AUSTR RE                            1998
 GALLAGER RG           DISCRETE STOCHASTIC                             1996
 GARFIELD E            SCIENCE                      178       471      1972
 GIBSON D              P 9 ACM C HYP HYP                      225      1998
 KESSLER MM            AM DOC                        14        10      1963
 KLEINBERG JM          P 1998 ACM SIAM S DI                            1998
 KLEINBERG JM          P 5 INT C COMP COMB                             1999
 LAW K                 AUTOMATIC CATEGORIZA                            1999
 LEMPEL R              CS200006 TECHN ISR I                            2000
 MARCHIORI M           P 6 INT C WWW                                   1997
 PAPADIMITRIOU CH      P 17 ACM SIGACT SIGM                   159      1998
 PIROLLI P             P ACM C HUM FACT COM                   118      1996
 SMALL H               J AM SOC INFORM SCI           24       265      1973
 VANRIJSBERGEN CJ      INFORMATION RETRIEVA                            1979
 WEISS R               P 7 ACM C HYP WASH D                   180      1996


When responding, please attach my original message
_______________________________________________________________________
Eugene Garfield, PhD.  email: garfield at codex.cis.upenn.edu
home page: www.eugenegarfield.org
Tel: 215-243-2205 Fax 215-387-1266
President, The Scientist LLC. www.the-scientist.com
Chairman Emeritus, ISI www.isinet.com
Past President, American Society for Information Science and Technology
(ASIS&T)  www.asis.org
_______________________________________________________________________