Dirichlet densifiers for improved commute times estimation
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10045/88752
Title: | Dirichlet densifiers for improved commute times estimation |
---|---|
Authors: | Curado, Manuel | Escolano, Francisco | Lozano, Miguel Angel | Hancock, Edwin R. |
Research Group/s: | Laboratorio de Investigación en Visión Móvil (MVRLab) |
Center, Department or Service: | Universidad de Alicante. Departamento de Ciencia de la Computación e Inteligencia Artificial |
Keywords: | Graph densification | Dirichlet problems | Random walkers | Commute times |
Knowledge Area: | Ciencia de la Computación e Inteligencia Artificial |
Issue Date: | Jul-2019 |
Publisher: | Elsevier |
Citation: | Pattern Recognition. 2019, 91: 56-68. doi:10.1016/j.patcog.2019.02.012 |
Abstract: | 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. |
Sponsor: | 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 |
Language: | eng |
Type: | info:eu-repo/semantics/article |
Rights: | © 2019 Elsevier Ltd. |
Peer Review: | si |
Publisher version: | https://doi.org/10.1016/j.patcog.2019.02.012 |
Appears in Collections: | INV - MVRLab - Artículos de Revistas |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
2019_Curado_etal_PatternRecogn_final.pdf | Versión final (acceso restringido) | 2,32 MB | Adobe PDF | Open Request a copy |
2019_Curado_etal_PatternRecogn_preprint.pdf | Preprint (acceso abierto) | 3,46 MB | Adobe PDF | Open Preview |
Items in RUA are protected by copyright, with all rights reserved, unless otherwise indicated.