Depth-based hypergraph complexity traces from directed line graphs
Por favor, use este identificador para citar o enlazar este ítem:
http://hdl.handle.net/10045/53435
Título: | Depth-based hypergraph complexity traces from directed line graphs |
---|---|
Autor/es: | Bai, Lu | Escolano, Francisco | 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: | Hypergraphs | Directed line graphs | Entropies | Centroid vertex | Depth-based complexity traces |
Área/s de conocimiento: | Ciencia de la Computación e Inteligencia Artificial |
Fecha de publicación: | jun-2016 |
Editor: | Elsevier |
Cita bibliográfica: | Pattern Recognition. 2016, 54: 229-240. doi:10.1016/j.patcog.2016.01.004 |
Resumen: | In this paper, we aim to characterize the structure of hypergraphs in terms of structural complexity measure. Measuring the complexity of a hypergraph in a straightforward way tends to be elusive since the hyperedges of a hypergraph may exhibit varying relational orders. We thus transform a hypergraph into a line graph which not only accurately reflects the multiple relationships exhibited by the hyperedges but is also easier to manipulate for complexity analysis. To locate the dominant substructure within a line graph, we identify a centroid vertex by computing the minimum variance of its shortest path lengths. A family of centroid expansion subgraphs of the line graph is then derived from the centroid vertex. We compute the depth-based complexity traces for the hypergraph by measuring either the directed or undirected entropies of its centroid expansion subgraphs. The resulting complexity traces provide a flexible framework that can be applied to both hypergraphs and graphs. We perform (hyper)graph classification in the principal component space of the complexity trace vectors. Experiments on (hyper)graph datasets abstracted from bioinformatics and computer vision data demonstrate the effectiveness and efficiency of the complexity traces. |
Patrocinador/es: | This work is supported by National Natural Science Foundation of China (Grant no. 61503422). This work is supported by the Open Projects Program of National Laboratory of Pattern Recognition. Francisco Escolano is supported by the project TIN2012-32839 of the Spanish Government. Edwin R. Hancock is supported by a Royal Society Wolfson Research Merit Award. |
URI: | http://hdl.handle.net/10045/53435 |
ISSN: | 0031-3203 (Print) | 1873-5142 (Online) |
DOI: | 10.1016/j.patcog.2016.01.004 |
Idioma: | eng |
Tipo: | info:eu-repo/semantics/article |
Derechos: | © 2016 Elsevier Ltd. |
Revisión científica: | si |
Versión del editor: | http://dx.doi.org/10.1016/j.patcog.2016.01.004 |
Aparece en las colecciones: | INV - MVRLab - Artículos de Revistas |
Archivos en este ítem:
Archivo | Descripción | Tamaño | Formato | |
---|---|---|---|---|
2016_Bai_etal_PattRecog_final.pdf | Versión final (acceso restringido) | 428,49 kB | Adobe PDF | Abrir Solicitar una copia |
2016_Bai_etal_PattRecog_accepted.pdf | Accepted Manuscript (acceso abierto) | 534,6 kB | Adobe PDF | Abrir Vista previa |
Todos los documentos en RUA están protegidos por derechos de autor. Algunos derechos reservados.