The DOI matches its Crossref record; 21 of the 21 references it cites were found in a registry or an index.
SALSA: the stochastic approach for link-structure analysis
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 dervised an algoirthm 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 quivalent to a weighted in degree analysis of the link-sturcutre of WWW subgraphs, making it computationally more efficient than the Mutual reinforcement approach. We compare that results of applying SALSA to the results derived through Kleinberg's approach. These comparisions reveal a topological Phenomenon called the TKC effect which, in certain cases, prevents the Mutual reinforcement approach from identifying meaningful authorities.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The anatomy of a large-scale hypertextual Web search engine
Brin, S., & Page, L. (1998) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(98)00110-x · Cited by 16,004
Authoritative sources in a hyperlinked environment
Kleinberg, J. M. (1999) · Journal of the ACM · doi:10.1145/324133.324140 · Cited by 8,959
Co‐citation in the scientific literature: A new measure of the relationship between two documents
Small, H. (1973) · Journal of the American Society for Information Science · doi:10.1002/asi.4630240406 · Cited by 5,345
Bibliographic coupling between scientific papers
Kessler, M. M. (1963) · American Documentation · doi:10.1002/asi.5090140103 · Cited by 2,855
Garfield, E. (1972) · Science · doi:10.1126/science.178.4060.471 · Cited by 2,788
The Web as a Graph: Measurements, Models, and Methods
Kleinberg, J. M., Kumar, R., Raghavan, P., Rajagopalan, S., & Tomkins, A. S. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-48686-0_1 · Cited by 1,016
Latent semantic indexing: a probabilistic analysis
Papadimitriou, C. H., Tamaki, H., Raghavan, P., & Vempala, S. (1998) · Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems · doi:10.1145/275487.275505 · Cited by 863
Inferring Web communities from link topology
Gibson, D., Kleinberg, J., & Raghavan, P. (1998) · Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space---structure in hypermedia systems links, objects, time and space---structure in hypermedia systems - HYPERTEXT '98 · doi:10.1145/276627.276652 · Cited by 768
Automatic resource compilation by analyzing hyperlink structure and associated text
Chakrabarti, S., Dom, B., Raghavan, P., Rajagopalan, S., Gibson, D., & Kleinberg, J. (1998) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(98)00087-7 · Cited by 697
Gallager, R. G. (1997) · Journal of the Operational Research Society · doi:10.1038/sj.jors.2600329 · Cited by 691
Improved Algorithms for Topic Distillation in a Hyperlinked Environment
Bharat, K., & Henzinger, M. R. (2017) · ACM SIGIR Forum · doi:10.1145/3130348.3130367 · Cited by 676
Mining the Web's link structure
Chakrabarti, S., Dom, B. E., Kumar, S. R., Raghavan, P., Rajagopalan, S., Tomkins, A., Gibson, D., & Kleinberg, J. (1999) · Computer · doi:10.1109/2.781636 · Cited by 501
Gallager, R. G. (1996) · doi:10.1007/978-1-4615-2329-1 · Cited by 494
The stochastic approach for link-structure analysis (SALSA) and the TKC effect
Lempel, R., & Moran, S. (2000) · Computer Networks · doi:10.1016/s1389-1286(00)00034-7 · Cited by 481
Self-citationStructural analysis of hypertexts: identifying hierarchies and useful metrics
Botafogo, R. A., Rivlin, E., & Shneiderman, B. (1992) · ACM Transactions on Information Systems · doi:10.1145/146802.146826 · Cited by 421
Silk from a sow's ear: extracting usable structures from the Web
Pirolli, P., Pitkow, J., & Rao, R. (1996) · Proceedings of the SIGCHI conference on Human factors in computing systems common ground - CHI '96 · doi:10.1145/238386.238450 · Cited by 378
An Analysis of Some Graph Theoretical Cluster Techniques
Augustson, J. G., & Minker, J. (1970) · Journal of the ACM · doi:10.1145/321607.321608 · Cited by 229
Searching for information in a hypertext medical handbook
Frisse, M. E. (1988) · Communications of the ACM · doi:10.1145/48511.48518 · Cited by 220
HyPursuit: a hierarchical network search engine that exploits content-link hypertext clustering
Weiss, R., Vélez, B., & Sheldon, M. A. (1996) · Proceedings of the the seventh ACM conference on Hypertext - HYPERTEXT '96 · doi:10.1145/234828.234846 · Cited by 209
The quest for correct information on the Web: hyper search engines
Marchiori, M. (1997) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(97)00036-6 · Cited by 191
WebQuery: searching and visualizing the Web through connectivity
Carrière, S. J., & Kazman, R. (1997) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(97)00062-7 · Cited by 173
Cited by
Structured Encryption and Controlled Disclosure
Chase, M., & Kamara, S. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-17373-8_33 · Cited by 520
A Survey on PageRank Computing
Berkhin, P. (2005) · Internet Mathematics · doi:10.1080/15427951.2005.10129098 · Cited by 474
WTF: the who to follow service at Twitter
Gupta, P., Goel, A., Lin, J., Sharma, A., Wang, D., & Zadeh, R. (2013) · Proceedings of the 22nd international conference on World Wide Web · doi:10.1145/2488388.2488433 · Cited by 461
Data-intensive text processing with MapReduce
Lin, J., & Dyer, C. (2009) · Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, Companion Volume: Tutorial Abstracts on - NAACL '09 · doi:10.3115/1620950.1620951 · Cited by 445
Biased assimilation, homophily, and the dynamics of polarization
Dandekar, P., Goel, A., & Lee, D. T. (2013) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1217220110 · Cited by 435
Metadata
- Authors
- Lempel, R., & Moran, S.
- Venue
- ACM Transactions on Information Systems
- Published
- 2001-04
- Volume
- 19
- Issue
- 2
- Pages
- 131-160
- ISSN
- 1046-8188 (ISSN-L)
- 1558-2868
- OpenAlex
- W2039976898
- Cited by
- 362
- References
- 21
- FWCI
- 37.18
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.