Classification et désarticulation de graphes de termes.pdf

Classification et d´esarticulation de graphes de termes 1 1 2 2 Anne Berry , Bangaly Kaba , Mohamed Nadif , Eric SanJuan , Alain Sigayret1 {berry, kaba, sigayret}@isima.fr, {nadif, eric.sanjuan}@iut.univ-metz.fr 1 LIMOS - Universit´e Blaise Pascal - France 2 IUT de Metz, LITA - Universit´e de Metz, France Abstract Algorithm CPLCL (Classification by Preferential Clustered Link) for the classification graphs of syntactic variations, introduced by Ibekwe - SanJuan in [10, 6], has the mathematical properties of single link clustering, since it is partly founded on the concept of component related to a subgraph, while avoiding the chain effect as much as possible. In spite of these properties, this algorithm of hierarchical classification does not make it possible to avoid the formation of some classes of too great dimension. However, the visualization of subgraphs corresponding to these classes with the AiSee interface high- lights obvious structural graph properties, which enable their decomposition with recent formal tools. This motivates us in developing underlying graph-theoretical aspects with algorithm CPCL presented in TermWatch and in defining a decomposition algorithm for these classes. R´esum´e Ibekwe-SanJuan introduit dans [10, 6] un algorithme de classification de graphes de relations syntaxiques, qui poss`ede les propri´et´es math´ematiques de la classification par lien simple (CLS), tout en limitant les effets de chaˆınes. Malgr´e cela, cet algorithme de classification hi´erarchique, implant´e dans le syst`eme TermWatch, ne permet pas d’´eviter la formation de quelques