Éditeur(s) : HAL CCSD Elsevier
Résumé : International audience
Given a graph, its hyperbolicity is a measure of how close its distance distribution is to the one of a tree. This parameter has gained recent attention in the analysis of some graph algorithms and the classification of complex networks. We study on practical improvements for the computation of hyperbolicity in large graphs. Precisely, we investigate on relations between the hyperbolicity of a graph G and the hyperbolicity of its atoms, that are the subgraphs output by the clique-decomposition invented by Tarjan [51, 65]. We prove that the maximum hyperbolicity taken over the atoms is at most one unit off from the hyperbol-icity of G and the bound is sharp. We also give an algorithm to slightly modify the atoms, called the " substitution method " , which is at no extra cost than computing the clique-decomposition, and so that the maximum hyperbolicity taken over the resulting graphs is exactly the hyperbolicity of the input graph G. An experimental evaluation of our method for computing the hyperbolicity of a given graph from its atoms is provided for collaboration networks and biological networks. Finally, on a more theoretical side, we deduce from our results the first linear-time algorithm for computing the hyperbolicity of an outerplanar graph.
ISSN: 0304-3975

hal-01540756
https://hal.inria.fr/hal-01540756
https://hal.inria.fr/hal-01540756/document
https://hal.inria.fr/hal-01540756/file/CCDL-2017.pdf
DOI : 10.1016/j.tcs.2017.06.001

Éditeur(s) : HAL CCSD IOS Press
Résumé : International audience
Recent work has used graphs to modelize expression data from microarray experiments, in view of partitioning the genes into clusters. In this paper, we introduce the use of a decomposition by clique separators. Our aim is to improve the classical clustering methods in two ways: first we want to allow an overlap between clusters, as this seems biologically sound, and second we want to be guided by the structure of the graph to define the number of clusters. We test this approach with a well-known yeast database (Saccharomyces cerevisiae). Our results are good, as the expression profiles of the clusters we find are very coherent. Moreover, we are able to organize into another graph the clusters we find, and order them in a fashion which turns out to respect the chronological order defined by the the sporulation process.
ISSN: 1386-6338

hal-00521936
https://hal.archives-ouvertes.fr/hal-00521936

Éditeur(s) : HAL CCSD Springer
Résumé : Third International Workshop, MLMI 2012, Held in Conjunction with MICCAI 2012
International audience
Universal Nearest Neighbours (unn) is a classifier recently proposed, which can also effectively estimates the posterior probability of each classification act. This algorithm, intrinsically binary, requires the use of a decomposition method to cope with multiclass problems, thus reducing their complexity in less complex binary subtasks. Then, a reconstruction rule provides the final classification. In this paper we show that the application of unn algorithm in conjunction with a reconstruction rule based on the posterior probabilities provides a classification scheme robust among different biomedical image datasets. To this aim, we compare unn performance with those achieved by Support Vector Machine with two different kernels and by a k Nearest Neighbours classifier, and applying two different reconstruction rules for each of the aforementioned classification paradigms. The results on one private and five public biomedical datasets show satisfactory performance.
Machine Learning in Medical Imaging
Nice, France

hal-00958909
https://hal.archives-ouvertes.fr/hal-00958909
https://hal.archives-ouvertes.fr/hal-00958909/document
https://hal.archives-ouvertes.fr/hal-00958909/file/Miccai.pdf
DOI : 10.1007/978-3-642-35428-1_15