Depth-based hypergraph complexity traces from directed line graphs
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10045/53435
Title: | Depth-based hypergraph complexity traces from directed line graphs |
---|---|
Authors: | Bai, Lu | Escolano, Francisco | 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: | Hypergraphs | Directed line graphs | Entropies | Centroid vertex | Depth-based complexity traces |
Knowledge Area: | Ciencia de la Computación e Inteligencia Artificial |
Issue Date: | Jun-2016 |
Publisher: | Elsevier |
Citation: | Pattern Recognition. 2016, 54: 229-240. doi:10.1016/j.patcog.2016.01.004 |
Abstract: | 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. |
Sponsor: | 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 |
Language: | eng |
Type: | info:eu-repo/semantics/article |
Rights: | © 2016 Elsevier Ltd. |
Peer Review: | si |
Publisher version: | http://dx.doi.org/10.1016/j.patcog.2016.01.004 |
Appears in Collections: | INV - MVRLab - Artículos de Revistas |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
2016_Bai_etal_PattRecog_final.pdf | Versión final (acceso restringido) | 428,49 kB | Adobe PDF | Open Request a copy |
2016_Bai_etal_PattRecog_accepted.pdf | Accepted Manuscript (acceso abierto) | 534,6 kB | Adobe PDF | Open Preview |
Items in RUA are protected by copyright, with all rights reserved, unless otherwise indicated.