Dirichlet densifiers for improved commute times estimation
Empreu sempre aquest identificador per citar o enllaçar aquest ítem
http://hdl.handle.net/10045/88752
Títol: | Dirichlet densifiers for improved commute times estimation |
---|---|
Autors: | Curado, Manuel | Escolano, Francisco | Lozano, Miguel Angel | Hancock, Edwin R. |
Grups d'investigació o GITE: | Laboratorio de Investigación en Visión Móvil (MVRLab) |
Centre, Departament o Servei: | Universidad de Alicante. Departamento de Ciencia de la Computación e Inteligencia Artificial |
Paraules clau: | Graph densification | Dirichlet problems | Random walkers | Commute times |
Àrees de coneixement: | Ciencia de la Computación e Inteligencia Artificial |
Data de publicació: | de juliol-2019 |
Editor: | Elsevier |
Citació bibliogràfica: | Pattern Recognition. 2019, 91: 56-68. doi:10.1016/j.patcog.2019.02.012 |
Resum: | 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. |
Patrocinadors: | 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 |
Tipus: | info:eu-repo/semantics/article |
Drets: | © 2019 Elsevier Ltd. |
Revisió científica: | si |
Versió de l'editor: | https://doi.org/10.1016/j.patcog.2019.02.012 |
Apareix a la col·lecció: | INV - MVRLab - Artículos de Revistas |
Arxius per aquest ítem:
Arxiu | Descripció | Tamany | Format | |
---|---|---|---|---|
2019_Curado_etal_PatternRecogn_final.pdf | Versión final (acceso restringido) | 2,32 MB | Adobe PDF | Obrir Sol·licitar una còpia |
2019_Curado_etal_PatternRecogn_preprint.pdf | Preprint (acceso abierto) | 3,46 MB | Adobe PDF | Obrir Vista prèvia |
Tots els documents dipositats a RUA estan protegits per drets d'autors. Alguns drets reservats.