Skip to Main content Skip to Navigation
Conference papers

Concept Lattices as a Search Space for Graph Compression

Lucas Bourneuf 1, 2 Jacques Nicolas 3
1 Dyliss - Dynamics, Logics and Inference for biological Systems and Sequences
Inria Rennes – Bretagne Atlantique , IRISA-D7 - GESTION DES DONNÉES ET DE LA CONNAISSANCE
3 GenScale - Scalable, Optimized and Parallel Algorithms for Genomics
Inria Rennes – Bretagne Atlantique , IRISA-D7 - GESTION DES DONNÉES ET DE LA CONNAISSANCE
Abstract : Because of the increasing size and complexity of available graph structures in experimental sciences like molecular biology, techniques of graph visualization tend to reach their limit. To assist experimental scientists into the understanding of the underlying phenomena, most visualization methods are based on the organization of edges and nodes in clusters. Among recent ones, Power Graph Analysis is a lossless compression of the graph based on the search of cliques and bicliques, improving the readability of the overall structure. Royer et al. introduced a heuristic approach providing approximate solutions to this NP-complete problem. Later, Bourneuf et al. formalized the heuristic using Formal Concept Analysis. This paper proposes to extend this work by a for-malization of the graph compression search space. It shows that (1) the heuristic cannot always achieve an optimal compression, and (2) the concept lattice associated to a graph enables a more complete exploration of the search space. Our conclusion is that the search for graph compression can be usefully associated with the search for patterns in the concept lattice and that, conversely, confusing sets of objects and attributes brings new interesting problems for FCA.
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-02399578
Contributor : Lucas Bourneuf <>
Submitted on : Thursday, December 12, 2019 - 3:42:31 PM
Last modification on : Tuesday, February 25, 2020 - 8:08:12 AM
Document(s) archivé(s) le : Friday, March 13, 2020 - 10:34:50 PM

File

Conference_ICFCA_2019_Camera_r...
Files produced by the author(s)

Identifiers

Citation

Lucas Bourneuf, Jacques Nicolas. Concept Lattices as a Search Space for Graph Compression. ICFCA 2019 - 15th International Conference on Formal Concept Analysis, Jun 2019, Francfort, Germany. pp.274-289, ⟨10.1007/978-3-030-21462-3_18⟩. ⟨hal-02399578⟩

Share

Metrics

Record views

54

Files downloads

131