We introduce a concept of similarity between vertices of directed graphs. Let G<font size="-1">A and G<font size="-1">B be two directed graphs with, respectively, n<font size="-1">A and n<font size="-1">B vertices. We define an n<font size="-1">B n<font size="-1">A similarity matrix S whose real entry s<font size="-1">ij expresses how similar vertex j (in G<font size="-1">A) is to vertex i (in G<font size="-1">B): we say that s<font size="-1">ij is their similarity score. The similarity matrix can be obtained as the limit of the normalized even iterates of S<font size="-1">k+1 = BS<font size="-1">kA<font size="-1">T + B<font size="-1">TS<font size="-1">kA, where A and B are adjacency matrices of the graphs and S<font size="-1">0 is a matrix whose entries are all equal to 1. In the special case where G<font size="-1">A = G<font size="-1">B = G, the matrix S is square and the score s<font size="-1">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.
%0 Journal Article
%1 Blondel:2004:MSG:1035533.1035557
%A Blondel, Vincent D.
%A Gajardo, Anah\'ı
%A Heymans, Maureen
%A Senellart, Pierre
%A Dooren, Paul Van
%C Philadelphia, PA, USA
%D 2004
%I Society for Industrial and Applied Mathematics
%J SIAM Rev.
%K 2013 applications graph measure similarity vertices
%N 4
%P 647--666
%R 10.1137/S0036144502415960
%T A Measure of Similarity Between Graph Vertices: Applications to Synonym Extraction and Web Searching
%U http://dx.doi.org/10.1137/S0036144502415960
%V 46
%X We introduce a concept of similarity between vertices of directed graphs. Let G<font size="-1">A and G<font size="-1">B be two directed graphs with, respectively, n<font size="-1">A and n<font size="-1">B vertices. We define an n<font size="-1">B n<font size="-1">A similarity matrix S whose real entry s<font size="-1">ij expresses how similar vertex j (in G<font size="-1">A) is to vertex i (in G<font size="-1">B): we say that s<font size="-1">ij is their similarity score. The similarity matrix can be obtained as the limit of the normalized even iterates of S<font size="-1">k+1 = BS<font size="-1">kA<font size="-1">T + B<font size="-1">TS<font size="-1">kA, where A and B are adjacency matrices of the graphs and S<font size="-1">0 is a matrix whose entries are all equal to 1. In the special case where G<font size="-1">A = G<font size="-1">B = G, the matrix S is square and the score s<font size="-1">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.
@article{Blondel:2004:MSG:1035533.1035557,
abstract = {We introduce a concept of {similarity} between vertices of directed graphs. Let G<font size="-1">A and G<font size="-1">B be two directed graphs with, respectively, n<font size="-1">A and n<font size="-1">B vertices. We define an n<font size="-1">B \times n<font size="-1">A similarity matrix S whose real entry s<font size="-1">ij expresses how similar vertex j (in G<font size="-1">A) is to vertex i (in G<font size="-1">B): we say that s<font size="-1">ij is their similarity score. The similarity matrix can be obtained as the limit of the normalized even iterates of S<font size="-1">k+1 = BS<font size="-1">kA<font size="-1">T + B<font size="-1">TS<font size="-1">kA, where A and B are adjacency matrices of the graphs and S<font size="-1">0 is a matrix whose entries are all equal to 1. In the special case where G<font size="-1">A = G<font size="-1">B = G, the matrix S is square and the score s<font size="-1">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.},
acmid = {1035557},
added-at = {2014-01-02T15:18:39.000+0100},
address = {Philadelphia, PA, USA},
author = {Blondel, Vincent D. and Gajardo, Anah\'{\i} and Heymans, Maureen and Senellart, Pierre and Dooren, Paul Van},
biburl = {https://www.bibsonomy.org/bibtex/2daf491a8de00ad2e330592641d4bfb27/s_nkeha},
description = {A Measure of Similarity between Graph Vertices},
doi = {10.1137/S0036144502415960},
interhash = {b59d33c99477e70a646615cd0470f459},
intrahash = {daf491a8de00ad2e330592641d4bfb27},
issn = {0036-1445},
issue_date = {2004},
journal = {SIAM Rev.},
keywords = {2013 applications graph measure similarity vertices},
month = apr,
number = 4,
numpages = {20},
pages = {647--666},
publisher = {Society for Industrial and Applied Mathematics},
timestamp = {2014-01-04T12:59:33.000+0100},
title = {A Measure of Similarity Between Graph Vertices: Applications to Synonym Extraction and Web Searching},
url = {http://dx.doi.org/10.1137/S0036144502415960},
volume = 46,
year = 2004
}