La science des réseaux est notamment à la recherche de modèles mathématiques capables de reproduire le comportement de systèmes complexes empiriques. Cependant, la représentation usuelle, le graphe, est parfois inadéquate étant donné sa limitation à encoder uniquement les relations par paires. De nombreux travaux récents suggèrent que l'utilisation de l'hypergraphe, une généralisation décrivant les interactions d'ordre supérieur (plus de deux composantes), permet d'expliquer des phénomènes auparavant incompris avec le graphe. Or, la structure de ces réseaux complexes est rarement ou difficilement observée directement. De fait, on mesure plutôt une quantité intermédiaire, comme la fréquence de chaque interaction, pour ensuite reconstruire la structure originale. Bien que de nombreuses méthodes de reconstruction de graphes aient été développées, peu d'approches permettent de retrouver les interactions d'ordre supérieur d'un système complexe. Dans ce mémoire, on développe une nouvelle approche de reconstruction pouvant déceler les interactions connectant trois noeuds parmi des observations dyadiques bruitées. Basée sur l'inférence bayésienne, cette méthode génère la distribution des hypergraphes les plus plausibles pour un jeu de données grâce à un algorithme de type Metropolis-Hastings-within-Gibbs, une méthode de Monte-Carlo par chaînes de Markov. En vue d'évaluer la pertinence d'un modèle d'interactions d'ordre supérieur pour des observations dyadiques, le modèle d'hypergraphe développé est comparé à un second modèle bayésien supposant que la structure sous-jacente est un graphe admettant deux types d'interactions par paires. Les résultats obtenus pour des hypergraphes synthétiques et empiriques indiquent que la corrélation intrinsèque à la projection d'interactions d'ordre supérieur améliore le processus de reconstruction lorsque les observations associées aux interactions dyadiques et triadiques sont semblables. / Network science is looking for mathematical models capable of reproducing the behavior of empirical complex systems. However, the usual representation, the graph, is sometimes inadequate given its limitation to encode only pairwise relationships. Many recent works suggest that the use of the hypergraph, a generalization describing higher-order interactions (more than two components), allows to explain phenomena previously not understood with graphs. However, the structure of these complex networks is seldom or hardly observed directly. Instead, we measure an intermediate quantity, such as the frequency of each interaction, and then reconstruct the original structure. Although many graph reconstruction methods have been developed, few approaches recover the higher-order interactions of a complex system. In this thesis, we develop a new reconstruction approach which detects interactions connecting three vertices among noisy dyadic observations. Based on Bayesian inference, this method generates the distribution of the most plausible hypergraphs for a dataset using a Metropolis-Hastings-within-Gibbs algorithm, a Markov chain Monte Carlo method. In order to evaluate the relevance of a higher-order interaction model for dyadic observations, the developed hypergraph model is compared to a second Bayesian model assuming that the underlying structure is a graph admitting two types of pairwise interactions. Results for synthetic and empirical hypergraphs indicate that the intrinsic correlation to the projection of higher-order interactions improves the reconstruction process when observations associated with dyadic and triadic interactions are similar.

.

La première partie de cette thèse est dédiée à l’état de l’art sur les réseaux pair-à-pair, la recherche d’information dans de tels réseaux et la problématique de la fouille des données dans le contexte pair-à-pair en se focalisant plus particulièrement sur les méthodes de regroupement (clustering) et les arbres de décision.La seconde partie traite des réseaux où les pairs disposent de leurs propres schémas de données. On y analyse plus particulièrement les fondements et le fonctionnement du système SenPeer. On propose alors une architecture supportant une organisation communautaire des réseaux pair-à-pairs sémantiques. Cela nous permet alors de construire des réseaux pair-à-pair sémantiques structurés en communautés appelés cSON (CommunitySemantic Overlay Network).Ce qui pose alors les questions concernant l’explicitation des communautés et leur exploitation pour améliorer les performances (temps de réponse, nombres de messages, précision et le rappel). Pour construire les communautés, nous étudions deux alternatives différentes : (1) Médiation sémantique : la construction des communautés se base sur les liens sémantiques entre les super-pairs et la confiance qu’ils ont les uns envers les autres et (2) Clustering : un algorithme de clustering basé sur l’analyse des requêtes traitées par les super-pairs est à la base de construction des communautés. Ensuite, nous proposons deux méthodes pour calculer des caractérisations des communautaires en se plaçant dans les deux champs de recherche suivants : (1) Data mining: on cherche à caractériser chaque communauté à l’aide d’une connaissance extraite des requêtes traitées par ses super-pairs d’une même communauté CK (Communauty Knowledge) et (2) Hypergraphes : A l’inverse de la méthode précédente, notre objectif maintenant est de caractériser collectivement les communautés. On formalise ce problème comme la recherche des MCS (minimal covering shortcuts) qui sont des raccourcis, entre les super pairs,minimaux couvrants toutes les communautés. Nous développons ensuite deux méthodes de routages de requêtes CK-rooting et MCS-rooting en utilisant respectivement la connaissance communautaire et les MCS afin d’identifier les super-pairs susceptibles de traiter une requête donnée.Dans la troisième partie, nous présentons le simulateur développé pour supporter l’approche cSON. Nous présentons alors les résultats empiriques résultant de simulations et qui montrent une amélioration significative des performances de l’approche basée uniquement sur la médiation sémantique. Cette partie se termine avec la description d’une application de recherche d’information basée sur le partage de documents scientifiques enrichis. / The first part of this thesis is dedicated to the state of the art on the peer-to-peer networks, the information retrieval in such networks, and the problematic of data mining in the peer-to-peer context more particularly on clustering methods and decision trees.The second part deals with networks where peers have their own data schemas. We examine more particularlythe fundamentals and functioning of the system “SenPeer”. Then, we propose an architecture supporting acommunity organization of semantic peer-to-peer networks. This allows us to build peer-to-peer semantic structured communities called cSON (Communauty Semantic Overlay Network).This raises many questions concerning the explanation of communities and their operating to improve performances (response time, number of messages, precision and recall). To build communities, we study two different alternatives: (1) Semantic Mediation: the building of communities is based on semantic links between super-peers and the confidence that they have between them and (2) Clustering: a clustering algorithm, based onthe analysis of queries processed by the super-peers, is the base of community building. Then, we propose twomethods to calculate the characterizations of communities in the two research fields: (1) Data mining: we try to characterize each community using knowledge extracted from applications processed by his super-peers of the same community CK (Community Knowledge) and (2) Hypergraphs: Unlike the previous method, our goal nowis to characterize the communities collectively. We formalize this problem as the research of the MCS (minimalcovering shortcuts) which are shortcuts between the super-peers, minimum shortcuts covering all communities.Then, we develop two methods of queries routing CK-rooting and MCS-rooting respectively using community knowledge and MCS to identify the super-peers may process a given query.In the third section, we present the simulator developed to support the cSON approach. We present the empirical results representing the simulations and which show a significant improvement of performance of the approachonly based on semantic mediation.This part ends with a description of an application of information retrieval based on sharing enriched scientific documents.

Le concept de radio logicielle (SDR) est une solution pertinente pour concevoir des équipements multi-standards. Une façon de réaliser de tels équipements est d'identifier les fonctions et opérateurs communs entre les standards. Cette approche s'appelle la paramétrisation et est divisée en deux catégories : l'approche pragmatique qui est une version pratique pour créer et développer des opérateurs communs à partir d'opérateurs existants, et l'approche théorique dont l'objectif est de réaliser une exploration graphique d'un équipement multi-standards selon différents niveaux de granularité, accompagnée d'un problème d'optimisation. C'est cette dernière approche qui a constitué le sujet de base de cette thèse. Ainsi, une fonction de coût doit être optimisée afin de sélectionner les opérateurs communs entre les différentes normes, ce qui permet de proposer une configuration optimale à partir de laquelle sont déduits les opérateurs communs. Dans notre travail, nous avons dans un premier temps modélisé théoriquement la structure graphique d'un système multi-standards par un hypergraphe orienté. En outre, nous avons fourni une expression mathématique alternative de la fonction de coût suggérée, en utilisant des définitions propres à la théorie des graphes. Ensuite, nous avons montré que le problème d'optimisation associé était un problème NP sous une certaine contrainte, ce qui a entraîné une preuve d'exclusion de certaines configurations dont les coûts ne peuvent être minimaux. Ceci a constitué la deuxième contribution de cette thèse. Enfin, nous avons proposé un nouvel algorithme permettant de résoudre le problème d'optimisation donné, et dont l'intérêt est de donner une solution optimale du problème au lieu d'une solution approchée fournie par les méthodes heuristiques classiques. Un programme associé à cet algorithme a été développé en langage C, puis appliqué à plusieurs exemples de cas génériques afin d'en étudier les performances.

La découverte et l'interprétation de motifs et de règles sont deux tâches centrales en extraction de connaissances dans les bases de données. Cette thèse traite de l'extraction et des usages de motifs minimaux à la fois en fouille de données et dans le domaine des hypergraphes. D'une part, nous proposons une méthode efficace pour la découverte de motifs delta-libres dans les données larges, malgré les difficultés algorithmiques inhérentes à ce type de données. Cette méthode repose sur l'utilisation de l'extension des motifs et d'un nouveau critère d'élagage. D'autre part, nous nous intéressons à la qualité des règles d'associations et nous présentons un cadre générique qui permet de mieux comprendre les similarités et différences entre mesures. Il montre que de nombreuses mesures (appelées SBMs pour Simultaneously Bounded Measures) ont des comportements proches. Ce résultat permet de garantir des valeurs minimales pour toutes les SBMs et la production de règles de qualité par rapport à l'ensemble de ces mesures. Enfin, l'apport des méthodes de type <> pour d'autres domaines est mis en évidence. Nous montrons que notre approche de découverte de motifs dans les données larges est exploitable pour calculer efficacement les traverses minimales d'un hypergraphe, un problème réputé comme particulièrement difficile. Différentes applications, notamment en biologie, montrent l'intérêt pratique de nos méthodes.

Cette thèse présente différents aperçus de problèmes de mathématiques discrètes en lien avec la théorie des graphes. Elle s'intéresse en particulier à la coloration de graphes, i.e. l'assignation de couleurs aux sommets (ou arêtes) d'un graphes sous certaines contraintes locales, notamment l'exclusion de motifs. Pour différents types de coloration (choisissabilité des sommets, des arêtes, coloration acyclique ou linéaire, ...), un état de l'art est présenté, accompagné de résultats d'existence sur les graphes planaires ou leurs sous-classes, ayant pour but de minimiser le nombre de couleurs nécessaires pour un degré maximum ou un degré moyen maximum (Mad) donnés. Cette thèse traite également de décompositions induites de graphes, et démontre qu'il existe pour tout graphe $H$ une suite infinie de graphes denses dont les arêtes peuvent être partitionnées en copies induites de $H$. Cette preuve requiert le formalisme des hypergraphes, pour lesquels un autre résultat de décomposition est démontré, i.e. une décomposition optimale de l'hypergraphe complet 3-régulier en hypergraphes $\alpha$-acycliques. La troisième parti porte sur des questions algorithmiques. Elles consistent en problèmes d'optimisation ou d'existence, motivés par le routage d'information dans les réseaux, analysés par le formalisme classique de complexité algorithmique, ou traitent de la recherche de sous-graphes dans le formalisme de la complexité paramétrée. Dans une quatrième partie sont considérés des problèmes de comptage issus de la chimie, suivis de la présentation de Programmes Linéaires Entiers utilisés dans le logiciel de mathématiques Sage.

Le but des modèles traditionnels en classification (comme les partitions et les hiérarchies de parties) est de permettre de discriminer sans ambiguïté et donc de produire des classes non empiétantes (i.e. l’intersection de deux classes est vide ou une classe est incluse dans l'autre). Cependant, cette exigence de non ambiguïté peut conduire à occulter de l’information. Dans le cas des plantes hybrides en biologie par exemple ou encore de textes appartenant à plusieurs genres en analyse textuelle. Les modèles généraux comme les hypergraphes ou les treillis permettent de prendre en compte l’empiétance entre les classes. Plus précisément, les modèles dits "totalement équilibrés" autorisent l'empiétance tout en conservant certaines contraintes utiles en classification.En apprentissage automatique, les arbres de décision, très utilisés pour leur simplicité d'utilisation et de compréhension réalisent à chaque étape un partitionnement d'un ensemble en deux sous-ensembles.Nous montrons dans ce travail différents liens entre la classification traditionnelle et l'apprentissage automatique supervisé et montrons certains apports que chacun des deux mondes peut faire à l'autre.Nous proposons deux méthodes de classification mêlant les deux univers puis étendons la notion de binarité, très utilisée dans le cas des arbres, aux hypergraphes et aux treillis. Nous montrons alors l'équivalence entre les systèmes binarisables et les systèmes totalement équilibrés, faisant de ces derniers de parfaits candidats à la réalisation de modèles de classification en classes empiétantes. Nous proposons également diverses approximations de systèmes par des systèmes totalement équilibrés. / Traditionally, classification models (such as partitions and hierarchies) aim at separating without ambiguities and produce non-overlapping clusters (i.e two clusters are either disjoint or one is included in the other). However, this non ambiguity may lead to mask information such as in the case of hybrid plants in biology or of texts which belong to two (or more) different genres in textual analysis for instance. General models like hypergraphs or lattices allow to take into account overlapping clusters. More precisely, "totally balanced" models allows class infringement and presents some useful constraints for classification.In machine learning, decision trees are a widely used model as they are simple to use and understand. They are also based on the idea of partition of sets.We show in this work different links between traditional classification and supervised machine learning and show what each world can bring to the other.We propose two methods of classification which link the two universes. We then extend the notion of binarity, widely-used for trees, to hypergraphs and lattices. We show the equivalence between binarizable systems and totally balanced systems, which makes of totally balanced structures a great candidate for classification models with class infringement. We also propose some approximation methods of any system (lattice, hypergraph, dissimilarity) by a totally balanced one.

Dans cette thèse, nous considérons plusieurs paramètres des hypergraphes et nous étudions si les restrictions aux sous-classes des hypergraphes permettent d’obtenir des propriétés combinatoires et algorithmiques souhaitables. La plupart des paramètres que nous prenons en compte sont des instances spéciales des packings et transversals des hypergraphes.Dans la première partie, nous allons nous concentrer sur les line graphs des graphes subcubiques sans triangle et nous allons démontrer que pour tous ces graphes il y a un independent set de taille au moins 3|V(G)|/10 et cette borne est optimale. Conséquence immédiate: nous obtenons une borne inférieure optimale pour la taille d’un couplage maximum dans les graphes subcubiques sans triangle. De plus, nous montrons plusieurs résultats algorithmiques liés au FEEDBACK VERTEX SET, HAMILTONIAN CYCLE et HAMILTONIAN PATH quand restreints aux line graphs des graphes subcubiques sans triangle.Puis nous examinons trois hypergraphes ayant la propriété d’Erdős-Pósa et nous cherchons à déterminer les fonctions limites optimales. Tout d’abord, nous apportons une fonction theta-bounding pour la classe des graphes subcubiques et nous étudions CLIQUE COVER: en répondant à une question de Cerioli et al., nous montrons qu’il admet un PTAS pour les graphes planaires. Par la suite, nous nous intéressons à la Conjecture de Tuza et nous montrons que la constante 2 peut être améliorée pour les graphes avec arêtes contenues dans au maximum quatre triangles et pour les graphes sans certains odd-wheels. Enfin, nous nous concentrons sur la Conjecture de Jones: nous la démontrons dans le cas des graphes sans griffes avec degré maximal 4 et nous faisons quelques observations dans le cas des graphes subcubiques.Nous étudions ensuite la VC-dimension de certains hypergraphes résultants des graphes. En particulier, nous considérons l’hypergraphe sur l’ensemble des sommets d’un certain graphe qui est induit par la famille de ses sous-graphes k-connexes. En généralisant les résultats de Kranakis et al., nous fournissons des bornes supérieures et inférieures optimales pour la VC-dimension et nous montrons que son calcul est NP-complet, pour chacun k > 0. Enfin, nous démontrons que ce problème (dans le cas k = 1) et le problème étroitement lié CONNECTED DOMINATING SET sont soit solvables en temps polynomial ou NP-complet, quand restreints aux classes de graphes obtenues en interdisant un seul sous-graphe induit.Dans la partie finale de cette thèse, nous nous attaquons aux meta-questions suivantes: Quand est-ce qu’un certain problème “difficile” de graphe devient “facile”?; Existe-t-il des frontières séparant des instances “faciles” et “difficiles”? Afin de répondre à ces questions, dans le cas des classes héréditaires, Alekseev a introduit la notion de boundary class pour un problème NP-difficile et a montré qu’un problème Pi est NP-difficile pour une classe héréditaire X finiment défini si et seulement si X contient un boundary class pour Pi. Nouscontinuons la recherche des boundary classes pour les problèmes suivants: HAMILTONIAN CYCLE THROUGH SPECIFIED EDGE, HAMILTONIAN PATH, FEEDBACK VERTEX SET, CONNECTED DOMINATING SET and CONNECTED VERTEX COVER. / In this thesis, we consider several hypergraph parameters and study whether restrictions to subclasses of hypergraphs allow to obtain desirable combinatorial or algorithmic properties. Most of the parameters we consider are special instances of packings and transversals of hypergraphs.In the first part, we focus on line graphs of subcubic triangle-free graphs and show that any such graph G has an independent set of size at least 3|V(G)|/10, the bound being sharp. As an immediate consequence, we obtain a tight lower bound for the matching number of subcubic triangle-free graphs. Moreover, we prove several algorithmic results related to FEEDBACK VERTEX SET, HAMILTONIAN CYCLE and HAMILTONIAN PATH when restricted to line graphs of subcubic triangle-free graphs.Then we consider three hypergraphs having the Erdős-Pósa Property and we seek to determine the optimal bounding functions. First, we provide an optimal theta-bounding function for the class of subcubic graphs and we study CLIQUE COVER: answering a question by Cerioli et al., we show it admits a PTAS for planar graphs. Then we focus on Tuza’s Conjecture and show that the constant 2 in the statement can be improved for graphs whose edges are contained in at most four triangles and graphs obtained by forbidding certain odd-wheels. Finally, we concentrate on Jones’ Conjecture: we prove it in the case of claw-free graphs with maximum degree at most 4 and we make some observations in the case of subcubic graphs.Then we study the VC-dimension of certain set systems arising from graphs. In particular, we consider the set system on the vertex set of some graph which is induced by the family of its k-connected subgraphs. Generalizing results by Kranakis et al., we provide tight upper and lower bounds for the VC-dimension and we show that its computation is NP-complete, for each k > 0. Finally, we show that this problem (in the case k = 1) and the closely related CONNECTED DOMINATING SET are either NP-complete or polynomial-time solvable when restricted to classes of graphs obtained by forbidding a single induced subgraph.In the final part of the thesis, we consider the following meta-questions: When does a certain “hard” graph problem become “easy”?; Is there any “boundary” separating “easy” and “hard” instances? In order to answer these questions in the case of hereditary classes, Alekseev introduced the notion of a boundary class for an NP-hard problem and showed that a problem Pi is NP-hard for a finitely defined (hereditary) class X if and only if X contains a boundary class for Pi. We continue the search of boundary classes for the following problems: HAMILTONIAN CYCLE THROUGH SPECIFIED EDGE, HAMILTONIAN PATH, FEEDBACK VERTEX SET, CONNECTED DOMINATING SET and CONNECTED VERTEX COVER.

No description available.

La factorisation des tenseurs est au coeur des méthodes d'analyse des données massives multidimensionnelles dans de nombreux domaines, dont les systèmes de recommandation, les graphes, les données médicales, le traitement du signal, la chimiométrie, et bien d'autres.Pour toutes ces applications, l'obtention rapide de la décomposition des tenseurs est cruciale pour pouvoir traiter manipuler efficacement les énormes volumes de données en jeu.L'objectif principal de cette thèse est la conception d'algorithmes pour la décomposition de tenseurs multidimensionnels creux, possédant de plusieurs centaines de millions à quelques milliards de coefficients non-nuls. De tels tenseurs sont omniprésents dans les applications citées plus haut.Nous poursuivons cet objectif via trois approches.En premier lieu, nous proposons des algorithmes parallèles à mémoire distribuée, comprenant des schémas de communication point-à-point optimisés, afin de réduire les coûts de communication. Ces algorithmes sont indépendants du partitionnement des éléments du tenseur et des matrices de faible rang. Cette propriété nous permet de proposer des stratégies de partitionnement visant à minimiser le coût de communication tout en préservant l'équilibrage de charge entre les ressources. Nous utilisons des techniques d'hypergraphes pour analyser les paramètres de calcul et de communication de ces algorithmes, ainsi que des outils de partitionnement d'hypergraphe pour déterminer des partitions à même d'offrir un meilleur passage à l'échelle. Deuxièmement, nous étudions la parallélisation sur plate-forme à mémoire partagée de ces algorithmes. Dans ce contexte, nous déterminons soigneusement les tâches de calcul et leur dépendances, et nous les exprimons en termes d'une structure de données idoine, et dont la manipulation permet de révéler le parallélisme intrinsèque du problème. Troisièmement, nous présentons un schéma de calcul en forme d'arbre binaire pour représenter les noyaux de calcul les plus coûteux des algorithmes, comme la multiplication du tenseur par un ensemble de vecteurs ou de matrices donnés. L'arbre binaire permet de factoriser certains résultats intermédiaires, et de les ré-utiliser au fil du calcul. Grâce à ce schéma, nous montrons comment réduire significativement le nombre et le coût des multiplications tenseur-vecteur et tenseur-matrice, rendant ainsi la décomposition du tenseur plus rapide à la fois pour la version séquentielle et la version parallèle des algorithmes.Enfin, le reste de la thèse décrit deux extensions sur des thèmes similaires. La première extension consiste à appliquer le schéma d'arbre binaire à la décomposition des tenseurs denses, avec une analyse précise de la complexité du problème et des méthodes pour trouver la structure arborescente qui minimise le coût total. La seconde extension consiste à adapter les techniques de partitionnement utilisées pour la décomposition des tenseurs creux à la factorisation des matrices non-négatives, problème largement étudié et pour lequel nous obtenons des algorithmes parallèles plus efficaces que les meilleurs actuellement connus.Tous les résultats théoriques de cette thèse sont accompagnés d'implémentations parallèles,aussi bien en mémoire partagée que distribuée. Tous les algorithmes proposés, avec leur réalisation sur plate-forme HPC, contribuent ainsi à faire de la décomposition de tenseurs un outil prometteur pour le traitement des masses de données actuelles et à venir. / Tensor factorization has been increasingly used to analyze high-dimensional low-rank data ofmassive scale in numerous application domains, including recommender systems, graphanalytics, health-care data analysis, signal processing, chemometrics, and many others.In these applications, efficient computation of tensor decompositions is crucial to be able tohandle such datasets of high volume. The main focus of this thesis is on efficient decompositionof high dimensional sparse tensors, with hundreds of millions to billions of nonzero entries,which arise in many emerging big data applications. We achieve this through three majorapproaches.In the first approach, we provide distributed memory parallel algorithms with efficientpoint-to-point communication scheme for reducing the communication cost. These algorithmsare agnostic to the partitioning of tensor elements and low rank decomposition matrices, whichallow us to investigate effective partitioning strategies for minimizing communication cost whileestablishing computational load balance. We use hypergraph-based techniques to analyze computational and communication requirements in these algorithms, and employ hypergraphpartitioning tools to find suitable partitions that provide much better scalability.Second, we investigate effective shared memory parallelizations of these algorithms. Here, we carefully determine unit computational tasks and their dependencies, and express them using aproper data structure that exposes the parallelism underneath.Third, we introduce a tree-based computational scheme that carries out expensive operations(involving the multiplication of the tensor with a set of vectors or matrices, found at the core ofthese algorithms) faster by factoring out and storing common partial results and effectivelyre-using them. With this computational scheme, we asymptotically reduce the number oftensor-vector and -matrix multiplications for high dimensional tensors, and thereby rendercomputing tensor decompositions significantly cheaper both for sequential and parallelalgorithms.Finally, we diversify this main course of research with two extensions on similar themes.The first extension involves applying the tree-based computational framework to computingdense tensor decompositions, with an in-depth analysis of computational complexity andmethods to find optimal tree structures minimizing the computational cost. The second workfocuses on adapting effective communication and partitioning schemes of our parallel sparsetensor decomposition algorithms to the widely used non-negative matrix factorization problem,through which we obtain significantly better parallel scalability over the state of the artimplementations.We point out that all theoretical results in the thesis are nicely corroborated by parallelexperiments on both shared-memory and distributed-memory platforms. With these fastalgorithms as well as their tuned implementations for modern HPC architectures, we rendertensor and matrix decomposition algorithms amenable to use for analyzing massive scaledatasets.