The DOI matches its Crossref record; 16 of the 16 references it cites were found in a registry or an index.
A Measure of Similarity between Graph Vertices: Applications to Synonym Extraction and Web Searching
Abstract
We introduce a concept of {similarity} between vertices of directed graphs. Let G A and G B betwo directed graphs with, respectively, n A and n B vertices. We define an n B \times n A similarity matrixS whose real entry s ij expresses how similar vertex j (in G A ) is to vertex i (in G B ): we say that s ij is their similarity score. The similarity matrix can be obtained as the limit of the normalized even iterates of S k +1 = BS k A T + B T S k A, where A and B are adjacency matrices of the graphs and S 0 is a matrix whose entries are all equal to 1. In the special case where G A = G B = G, the matrix S is square and the score s ij is the similarity score between the vertices i and j of G. We point out that Kleinberg's "hub and authority" method to identify web-pages relevant to a given query can be viewed as a special case of our definition in the case where one of the graphs has two vertices and a unique directed edge between them. In analogy to Kleinberg, we show that our similarity scores are given by the components of a dominant eigenvector of a nonnegative matrix. Potential applications of our similarity concept are numerous. We illustrate an application for the automatic extraction of synonyms in a monolingual dictionary.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Horn, R. A., & Johnson, C. R. (1985) · Cited by 22,203
Horn, R. A., & Johnson, C. R. (1991) · Cambridge University Press eBooks · doi:10.1017/cbo9780511840371 · Cited by 9,319
Authoritative sources in a hyperlinked environment
Kleinberg, J. M. (1999) · Journal of the ACM · doi:10.1145/324133.324140 · Cited by 8,959
Bollobás, B. (1985) · Cited by 6,196
Chung, F. (1996) · CBMS Regional Conference Series in Mathematics · doi:10.1090/cbms/092 · Cited by 5,524
Nonnegative Matrices in the Mathematical Sciences
(1979) · Elsevier eBooks · doi:10.1016/c2013-0-10361-3 · Cited by 5,451
Biggs, N. (1974) · doi:10.1017/cbo9780511608704 · Cited by 2,940
SimRank: a measure of structural-context similarity
Jeh, G., & Widom, J. (2002) · Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/775047.775126 · Cited by 1,925
Spectra of graphs : theory and application
Cvetković, D., Doob, M., & Sachs, H. (1995) · Cited by 1,825
cacute, C., Vs, M., Doob, M., & Sachs, H. (1980) · Cited by 1,478
Cited by
Link prediction in complex networks: A survey
Lü, L., & Zhou, T. (2011) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2010.11.027 · Cited by 2,819
Newman, M. (2018) · doi:10.1093/oso/9780198805090.001.0001 · Cited by 2,297
struc2vec: Learning Node Representations from Structural Identity
Ribeiro, L. F. R., Saverese, P. H. P., & Figueiredo, D. R. (2017) · Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/3097983.3098061 · Cited by 1,011
Leicht, E. A., Holme, P., & Newman, M. E. J. (2006) · Physical Review E · doi:10.1103/physreve.73.026120 · Cited by 916
Bubble rap: social-based forwarding in delay tolerant networks
Hui, P., Crowcroft, J., & Yoneki, E. (2008) · Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing · doi:10.1145/1374618.1374652 · Cited by 814
Metadata
- Authors
- Blondel, V. D., Gajardo, A., Heymans, M., Senellart, P., & Van Dooren, P.
- Venue
- SIAM Review
- Published
- 2004-01
- Volume
- 46
- Issue
- 4
- Pages
- 647-666
- ISSN
- 0036-1445 (ISSN-L)
- 1095-7200
- OpenAlex
- W2113367658
- Cited by
- 423
- References
- 16
- FWCI
- 21.83
- 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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: A Measure of Similarity between Graph Vertices: Applications to Synonym Extraction and Web Searching. https://app.cochat.ai/papers/10.1137/s0036144502415960
- The paper
- Blondel, V. D., Gajardo, A., Heymans, M., Senellart, P., & Van Dooren, P. (2004). A Measure of Similarity between Graph Vertices: Applications to Synonym Extraction and Web Searching. SIAM Review. https://doi.org/10.1137/s0036144502415960
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.