A Measure of Similarity between Graph Vertices: Applications to Synonym Extraction and Web Searching
The DOI matches its Crossref record; 16 of the 16 references it cites were found in a registry or an index.
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.
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
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
Spectra of graphs : theory and application
Cvetković, D., Doob, M., & Sachs, H. (1995) · Cited by 2,127
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
cacute, C., Vs, M., Doob, M., & Sachs, H. (1980) · Cited by 1,478
A Survey of Matrix Theory and Matrix Inequalities
H., A. S., Marcus, M., & Minc, H. (1965) · Mathematics of Computation · doi:10.2307/2004116 · Cited by 1,405
Similarity flooding: a versatile graph matching algorithm and its application to schema matching
Melnik, S., Garcia-Molina, H., & Rahm, E. (2003) · Proceedings 18th International Conference on Data Engineering · doi:10.1109/icde.2002.994702 · Cited by 1,341
Cvetkovic, D., Rowlinson, P., & Simic, S. (1997) · Cambridge University Press eBooks · doi:10.1017/cbo9781139086547 · Cited by 531
Automatic Discovery of Similar Words
Senellart, P. P., & Blondel, V. D. (2004) · Springer eBooks · doi:10.1007/978-1-4757-4305-0_2 · Cited by 75
Self-citationReplicated transfer matrix analysis of Ising spin models on small world lattices
Nikoletopoulos, T., Coolen, A. C. C., Castillo, I. P., Skantzos, N. S., Hatchett, J. P. L., & Wemmenhove, B. (2004) · Journal of Physics A Mathematical and General · doi:10.1088/0305-4470/37/25/003 · Cited by 66
Sandwiching random graphs: universality between random graph models
Kim, J. H., & Vu, V. H. (2004) · Advances in Mathematics · doi:10.1016/j.aim.2003.10.007 · Cited by 65
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
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.