Authors 
: 

Document type 
: 
Communication à un colloque (Conference Paper) – Présentation orale avec comité de sélection

Abstract 
: 
We introduce a concept of similarity between vertices of directed graphs. Let G(A) and G(B) be two directed graphs with respectively n(A) and n(B) vertices. We define a n(A) x n(B) similarity matrix S whose real entry s(ij) expresses how similar vertex i (in G(A)) is to vertex j (in G(B)) we say that s(ij) is their similarity score. In the special case where G(A) = G(B) = G, the score s(ij) is the similarity score between the vertices i and j of G and the square similarity matrix S is the self similarity matrix of the graph G. We point out that Kleinberg's "hub and authority" method to identify webpages 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 Klemberg, we show that our similarity scores are given by the components of a dominant vector of a nonnegative matrix and we propose a simple iterative method to compute them. 
Access type 
: 
Accès restreint 
Publication date 
: 
2003 
Language 
: 
Anglais 
Conference 
: 
"30th International Colloquium on Automata, Languages and Programming (ICALP 2003)", EINDHOVEN(Netherlands) (Jun 30jul 04, 2003) 
Journal information 
: 
"Lecture Notes in Computer Science"  Vol. 2719, p. 739750 (2003) 
Peer reviewed 
: 
yes 
issn 
: 
03029743 
eissn 
: 
16113349 
Publisher 
: 
Springerverlag Berlin (Berlin)

Affiliation 
: 
UCL
 FSA/INMA  Département d'ingénierie mathématique

Links 
: 
