%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 }