In this paper, we extend the notion of similarity matrix, which has been used
to define similarity between nodes of two graphs, to the case of colored graphs,
where the coloring is either on the nodes or on the edges of both graphs.
The proposed method tries to find the optimal matching between the nodes or edges
of both graphs but only performs the comparison when their colors are the same.
The proposed cost function nevertheless uses the connectivity between all nodes
and edges of both graphs. We then also show how to extend this to the notion of
low rank similarity matrix, by defining it as a constrained optimization problem.
Publié le : 2009-11-15
Classification:
Algorithms,
graph algorithms,
graph theory,
eigenvalues of graphs,
05C50,
05C85,
15A18,
68R10
@article{1257776243,
author = {Van Dooren, Paul and Fraikin, Catherine},
title = {Similarity matrices for colored graphs},
journal = {Bull. Belg. Math. Soc. Simon Stevin},
volume = {16},
number = {1},
year = {2009},
pages = { 705-722},
language = {en},
url = {http://dml.mathdoc.fr/item/1257776243}
}
Van Dooren, Paul; Fraikin, Catherine. Similarity matrices for colored graphs. Bull. Belg. Math. Soc. Simon Stevin, Tome 16 (2009) no. 1, pp. 705-722. http://gdmltest.u-ga.fr/item/1257776243/