Dirichlet densifiers for improved commute times estimation
Por favor, use este identificador para citar o enlazar este ítem:
http://hdl.handle.net/10045/88752
Título: | Dirichlet densifiers for improved commute times estimation |
---|---|
Autor/es: | Curado, Manuel | Escolano, Francisco | Lozano, Miguel Angel | Hancock, Edwin R. |
Grupo/s de investigación o GITE: | Laboratorio de Investigación en Visión Móvil (MVRLab) |
Centro, Departamento o Servicio: | Universidad de Alicante. Departamento de Ciencia de la Computación e Inteligencia Artificial |
Palabras clave: | Graph densification | Dirichlet problems | Random walkers | Commute times |
Área/s de conocimiento: | Ciencia de la Computación e Inteligencia Artificial |
Fecha de publicación: | jul-2019 |
Editor: | Elsevier |
Cita bibliográfica: | Pattern Recognition. 2019, 91: 56-68. doi:10.1016/j.patcog.2019.02.012 |
Resumen: | In this paper, we develop a novel Dirichlet densifier that can be used to increase the edge density in undirected graphs. Dirichlet densifiers are implicit minimizers of the spectral gap for the Laplacian spectrum of a graph. One consequence of this property is that they can be used improve the estimation of meaningful commute distances for mid-size graphs by means of topological modifications of the original graphs. This results in a better performance in clustering and ranking. To do this, we identify the strongest edges and from them construct the so called line graph, where the nodes are the potential q −step reachable edges in the original graph. These strongest edges are assumed to be stable. By simulating random walks on the line graph, we identify potential new edges in the original graph. This approach is fully unsupervised and it is both more scalable and robust than recent explicit spectral methods, such as the Semi-Definite Programming (SDP) densifier and the sufficient condition for decreasing the spectral gap. Experiments show that our method is only outperformed by some choices of the parameters of a related method, the anchor graph, which relies on pre-computing clusters representatives, and that the proposed method is effective on a variety of real-world datasets. |
Patrocinador/es: | M. Curado, F. Escolano and M.A. Lozano are funded by the projects TIN2015-69077-P and BES2013-064482 of the Spanish Government. |
URI: | http://hdl.handle.net/10045/88752 |
ISSN: | 0031-3203 (Print) | 1873-5142 (Online) |
DOI: | 10.1016/j.patcog.2019.02.012 |
Idioma: | eng |
Tipo: | info:eu-repo/semantics/article |
Derechos: | © 2019 Elsevier Ltd. |
Revisión científica: | si |
Versión del editor: | https://doi.org/10.1016/j.patcog.2019.02.012 |
Aparece en las colecciones: | INV - MVRLab - Artículos de Revistas |
Archivos en este ítem:
Archivo | Descripción | Tamaño | Formato | |
---|---|---|---|---|
2019_Curado_etal_PatternRecogn_final.pdf | Versión final (acceso restringido) | 2,32 MB | Adobe PDF | Abrir Solicitar una copia |
2019_Curado_etal_PatternRecogn_preprint.pdf | Preprint (acceso abierto) | 3,46 MB | Adobe PDF | Abrir Vista previa |
Todos los documentos en RUA están protegidos por derechos de autor. Algunos derechos reservados.