A measure of similarity between graph vertices

摘要: We introduce a concept of similarity between vertices directed graphs. Let G_A and G_B be two define matrix whose (i, j)-th real entry expresses how similar vertex j (in G_A) is to i G_B. The can obtained as the limit normalized even iterates linear transformation. In special case where G_A=G_B=G, square score G. point out that Kleinberg's "hub authority" method identify web-pages relevant given query viewed our definition in one graphs has unique edge them. analogy Kleinberg, we show scores are by components dominant eigenvector non-negative matrix. Potential applications numerous. illustrate an application for automatic extraction synonyms monolingual dictionary.