Cette thèse traite de problèmes liés à la théorie des limitesd'objets combinatoires, une récente théorie qui a permis de tisserdes liens entre différents domaines tels que la combinatoire,l'analyse, la géométrie ou la théorie de la probabilité.Cette thèse applique des méthode venant de cette théorie à des problèmesde combinatoire extrémale.Dans un premier chapitre, je développe une théorie des limites d'objetsappelés emph{types d'ordre}, un objets qui encode des configurationsd'ensembles de points du plan. Le type d'ordre d'un ensemble de pointssuffit à caractériser de nombreuses propriétés essentielles de cet ensemblede point comme, par exemple, son enveloppe convexe.Je montre qu'une limite de type d'ordre peut être représentée par un objetanalogue à un graphon à valeurs O ou 1.Je fais ensuite le lien entre limites de type d'ordre et la distributionnaturelle de limite de type d'ordre obtenue par l’échantillonnage de pointsdu plan suivant une certaine probabilité.De cette manière, toute probabilité sur le plan engendre une limite de typed'ordre. Je montre d'une part que cette correspondance n'est pas surjective-c'est à dire qu'il existe des limites de type d'ordre ne venant pas de probabilitédu plan- et j'étudie d'autre part son injectivité.Je montre que si le support d'une mesure de probabilité est assez gros, par exemple siil contient une boule ouvert, alors la limite que cette mesure engendre suffit à caractériser cette mesure à une transformation projective près.Un second chapitre traite de test de propriété.Un testeur de propriété est un algorithme aléatoire permettant de séparerles objets ayant une certaine propriété des objet à distance au moins εde l'avoir, au sens de la distance d'édition.Ce domaine donne des algorithmes extrêmement rapides, et en particulierdes algorithmes dont la complexité ne dépends pas de la taille de l'entréemais seulement du paramètre de précision ε.Un résultat fondamental de cet domaine pour les graphes montré par Alonet Shapira est le suivant : toute classe de graphe héréditaire possède un teltesteur.Cette thèse contribue à la question suivante :Quelles classes de graphes possède un testeur dont la complexité est unpolynôme en 1/ε ?Je montre qu'en particulier la classe des graphes d'intervales possède un teltesteur.La théorie des algèbres de drapeaux est un outil étroitement lié aux limites degraphes denses qui donne une méthode pour démontrer des bornes sur certainsparamètres combinatoires à l'aide d'un ordinateur.Dans un troisième chapitre, je présente un programme écrit durant ma thèsequi implémente cette méthode.Ce programme fonctionne comme une bibliothèque pour calculer dans les algèbresde drapeaux, manipuler des inégalités sur les drapeaux ou encoder des problèmesd'optimisations par une instance de programme semi-défini positif qui peutensuite être résolu par un solveur externe.Ce programme est en particulier utilisé pour obtenir un nouvelle borne pour le cas triangulaire de la conjecture de Caccetta-Häggkvist. / This thesis is focused on problems related to the theory of combinatorial limits.This theory opened links between different fields such asanalysis, combinatorics, geometry and probability theory.In this thesis, we apply ideas coming from this framework toproblems in extremal combinatorics.In a first chapter we develop a theory of limits for emph{order types},a geometrical object that encodes configuration of a set of points in theplane by the mean of the orientations of their triangles.The order type of a point set suffices to determine many of its properties,such as for instance the boundary of its convex hull.We show that the limit of a converging sequence of order typescan be represented by random-free object analogous to a graphon.Further, we link this notion to the natural distributions of order typesarising from the sampling of random points from some probability measureof the plane.We observe that in this mean, every probability measure gives rise to a limitof order types.We show that this map from probability measure on the plane to limit oforder type is not surjective.Concerning its injectivity,we prove that if a measure has large enough support, for instance if its supportcontains an open ball, the limit of order types the measure generatessuffices to essentially determine this measure.A second chapter is focused on property testing.A tester is a randomized algorithm for distinguishing between objects satisfyinga property from those that are at some distance at least εfrom having itby means of the edition distance.This gives very efficient algorithms, and in particular algorithms whosecomplexity does not depend on the size of the input but only on the parameter ε.For graphs, it has been shown by Alon and Shapira that every hereditary propertyhas such a tester.We contribute to the following question :which classes of graphs have a one-sided property tester with a number of queries that is a polynomial in 1/ε ?We give a proof that the class of interval graphs has such a tester.The theory of flag algebras is a framework introduced by Razborovclosely related to dense limit of graphs, that gives a way to systematicallyderive bounds for parameters in extremal combinatorics.In a third chapter we present a program developed during my Phd.that implements this method.This program works as a library that can compute flag algebras,manipulate inequalities on densities and encode the optimization of some parameterin a semi-definite positive instance that can be given to a dedicated solverto obtain a bound on this parameter.This program is in particular used to obtain a new bound forthe triangle case of the Caccetta-Häggkvist conjecture.

Une classe de graphes est close par mineurs si, pour tout graphe dans la classe et tout mineur de ce graphe, le mineur est ́egalement dans la classe. Par un fameux th ́eor`eme de Robertson et Seymour, nous savons que car- act ́eriser une telle classe peut ˆetre fait `a l’aide d’un nombre fini de mineurs exclus minimaux. Ceux-ci sont des graphes qui n’appartiennent pas `a la classe et qui sont minimaux dans le sens des mineurs pour cette propri ́et ́e.Dans cette thèse, nous étudions trois problèmes à propos de classes de graphes closes par mineurs. Les deux premiers sont reliés à la caractérisation de certaines classes de graphes, alors que le troisième étudie une relation de “packing-covering” dans des graphes excluant un mineur.Pour le premier problème, nous étudions des plongements isométriques de graphes dont les arêtes sont pondérées dans des espaces métriques. Principalement, nous nous intêressons aux espaces ell_2 et ell_∞. E ́tant donné un graphe pondéré, un plongement isométrique associe à chaque sommet du graphe un vecteur dans l’autre espace de sorte que pour chaque arête du graphe le poids de celle-ci est égal à la distance entre les vecteurs correspondant à ses sommets. Nous disons qu’une fonction de poids sur les arêtes est une fonction de distances réalisable s’il existe un tel plongement. Le paramètre f_p(G) détermine la dimension k minimale d’un espace ell_p telle que toute fonction de distances réalisable de G peut être plongée dans ell_p^k. Ce paramètre est monotone dans le sens des mineurs. Nous caractérisons les graphes tels que f_p(G) a une grande valeur en termes de mineurs inévitables pour p = 2 et p = ∞. Une famille de graphes donne des mineurs inévitables pour un invariant monotone pour les mineurs, si ces graphes “expliquent” pourquoi l’invariant est grand.Le deuxième problème étudie les mineurs exclus minimaux pour la classe de graphes avec φ(G) borné par une constante k, où φ(G) est un paramètre lié au dominant des coupes d’un graphe G. Ce polyèdre contient tous les points qui, composante par composante, sont plus grands ou égaux à une combination convexe des vecteurs d’incidence de coupes dans G. Le paramètre φ(G) est égal au membre de droite maximum d’une description linéaire du dominant des coupes de G en forme entière minimale. Nous étudions les mineurs exclus minimaux pour la propriété φ(G) <= 4 et montrons une nouvelle borne sur φ(G) en termes du “vertex cover number”.Le dernier problème est d’un autre type. Nous étudions une relation de “packing-covering” dans les classes de graphes excluant un mineur. Étant donné un graphe G, une boule de centre v et de rayon r est l’ensemble de tous les sommets de G qui sont à distance au plus r de v. Pour un graphe G et une collection de boules donnés nous pouvons définir un hypergraphe H dont les sommets sont ceux de G et les arêtes correspondent aux boules de la collection. Il est bien connu que dans l’hypergraphe H, le “transversal number” τ(H) vaut au moins le “packing number” ν(H). Nous montrons une borne supérieure sur ν(H) qui est linéaire en τ(H), résolvant ainsi un problème ouvert de Chepoi, Estellon et Vaxès. / A class of graphs is closed under taking minors if for each graph in the class and each minor of this graph, the minor is also in the class. By a famous result of Robertson and Seymour, we know that characterizing such a class can be done by identifying a finite set of minimal excluded minors, that is, graphs which do not belong to the class and are minor-minimal for this property.In this thesis, we study three problems in minor-closed classes of graphs. The first two are related to the characterization of some graph classes, while the third one studies a packing-covering relation for graphs excluding a minor.In the first problem, we study isometric embeddings of edge-weighted graphs into metric spaces. In particular, we consider ell_2- and ell_∞-spaces. Given a weighted graph, an isometric embedding maps the vertices of this graph to vectors such that for each edge of the graph the weight of the edge equals the distance between the vectors representing its ends. We say that a weight function on the edges of the graph is a realizable distance function if such an embedding exists. The minor-monotone parameter f_p(G) determines the minimum dimension k of an ell_p-space such that any realizable distance function of G is realizable in ell_p^k. We characterize graphs with large f_p(G) value in terms of unavoidable minors for p = 2 and p = ∞. Roughly speaking, a family of graphs gives unavoidable minors for a minor-monotone parameter if these graphs “explain” why the parameter is high.The second problem studies the minimal excluded minors of the class of graphs such that φ(G) is bounded by some constant k, where φ(G) is a parameter related to the cut dominant of a graph G. This unbounded polyhedron contains all points that are componentwise larger than or equal to a convex combination of incidence vectors of cuts in G. The parameter φ(G) is equal to the maximum right-hand side of a facet-defining inequality of the cut dominant of G in minimum integer form. We study minimal excluded graphs for the property φ(G) <= 4 and provide also a new bound of φ(G) in terms of the vertex cover number.The last problem has a different flavor as it studies a packing-covering relation in classes of graphs excluding a minor. Given a graph G, a ball of center v and radius r is the set of all vertices in G that are at distance at most r from v. Given a graph and a collection of balls, we can define a hypergraph H such that its vertices are the vertices of G and its edges correspond to the balls in the collection. It is well-known that, in the hypergraph H, the transversal number τ(H) is at least the packing number ν(H). We show that we can bound τ(H) from above by a linear function of ν(H) for every graphs G and ball collections H if the graph G excludes a minor, solving an open problem by Chepoi, Estellon et Vaxès. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Cette thèse a pour thème la coloration de diverses classes de graphes épars. Shearer montra en 1983 [She83] que le ratio d'indépendance des graphes sans triangle de degré maximal d est au moins (1-o(1))ln d/d, et 13 ans plus tard Johansson [Joh96] démontra que le nombre chromatique de ces graphes est au plus O(d/ln d) quand d tend vers l'infini. Ce dernier résultat fut récemment amélioré par Molloy [Mol19], qui montra que la borne (1+o(1))d/ln d est valide quand d tend vers l'infini.Tandis que le résultat de Molloy s'exprime à l'aide d'un paramètre global, le degré maximal du graphe, nous montrons qu'il est possible de l'étendre à la coloration locale. Il s'agit de la coloration par liste, où la taille de la liste associée à chaque sommet ne dépend que de son degré. Avec une méthode différente se basant sur les propriétés de la distribution hard-core sur les ensembles indépendants d'un graphe, nous obtenons un résultat similaire pour la coloration fractionnaire locale, avec des hypothèses plus faibles. Nous démontrons également un résultat concernant la coloration fractionnaire locale des graphes où chaque sommet est contenu dans un nombre borné de triangles, et une borne principalement optimale sur le taux d'occupation — la taille moyenne des ensembles indépendants — de ces graphes. Nous considérons également les graphes de maille 7, et prouvons des résultats similaires qui améliorent les bornes précédemment connues quand le degré maximal du graphe est au plus 10^7. Finalement, pour les graphes d-réguliers où d vaut 3, 4, ou 5, de maille g variant entre 6 et 12, nous démontrons de nouvelles bornes inférieures sur le ratio d'indépendance.Le Chapitre 2 est dédié à la coloration à distance t d'un graphe, qui généralise la notion de coloration forte des arêtes. Nous cherchons à étendre le théorème de Johansson à la coloration à distance t, par l'exclusion de certains cycles. Le résultat de Johansson s'obtient par exclusion des triangles, ou des cycles de taille k pour n'importe quelle valeur de k. Nous montrons que l'exclusion des cycles de taille 2k, pour n'importe quel k>t, a un effet similaire sur le nombre chromatique à distance t, et sur l'indice chromatique à distance t+1. En outre, quand t est impair, une conclusion similaire peut se faire pour le nombre chromatique à distance t par l'exclusion des cycles de d'une taille impaire fixée valant au moins 3t. Nous étudions l'optimalité de ces résultats à l'aide de constructions de nature combinatoire, algébrique, et probabiliste.Dans le Chapitre 3, nous nous intéressons à la densité bipartie induite des graphes sans triangle, un paramètre relaxant celui de la coloration fractionnaire. Motivés par une conjecture de Esperet, Kang, et Thomassé [EKT19], qui prétend que la densité bipartie induite de graphes sans triangle de degré moyen d est au moins de l'ordre de ln d, nous démontrons cette conjecture quand d est suffisamment grand en termes du nombre de sommets n, à savoir d est au moins de l'ordre de (n ln n)^(1/2). Ce résultat ne pourrait être amélioré que par une valeur de l'ordre de ln n, ce que nous montrons à l'aide d'une construction reposant sur le processus sans triangle. Nos travaux se ramènent à un problème intéressant, celui de déterminer le nombre chromatique fractionnaire maximal d'un graphe épars à n sommets. Nous prouvons des bornes supérieures non triviales pour les graphes sans triangle, et pour les graphes dont chaque sommet appartient à un nombre borné de triangles.Cette thèse est reliée aux nombres de Ramsey. À ce jour, le meilleur encadrement connu sur R(3,t) nous est donné par le résultat de Shearer, et par une analyse récente du processus sans triangle [BoKe13+,FGM13+], ce qui donne(1-o(1)) t²/(4 ln t) < R(3,t) < (1+o(1)) t²/ln t. (1)Beaucoup de nos résultats ne pourraient être améliorés à moins d'améliorer par la même occasion (1), ce qui constituerait une révolution dans la théorie de Ramsey quantitative. / This thesis focuses on generalisations of the colouring problem in various classes of sparse graphs.Triangle-free graphs of maximum degree d are known to have independence ratio at least (1-o(1))ln d/d by a result of Shearer [She83], and chromatic number at most O(d/ln d) by a result of Johansson [Joh96], as d grows to infinity. This was recently improved by Molloy, who showed that the chromatic number of triangle-free graphs of maximum degree d is at most (1+o(1))d/ln d as d grows to infinity.While Molloy's result is expressed with a global parameter, the maximum degree of the graph, we first show that it is possible to extend it to local colourings. Those are list colourings where the size of the list associated to a given vertex depends only on the degree of that vertex. With a different method relying on the properties of the hard-core distribution on the independent sets of a graph, we obtain a similar result for local fractional colourings, with weaker assumptions. We also provide an analogous result concerning local fractional colourings of graphs where each vertex is contained in a bounded number of triangles, and a sharp bound for the occupancy fraction — the average size of an independent set — of those graphs. In another direction, we also consider graphs of girth 7, and prove related results which improve on the previously known bounds when the maximum degree does not exceed 10^7. Finally, for d-regular graphs with d in the set {3,4,5}, of girth g varying between 6 and 12, we provide new lower bounds on the independence ratio.The second chapter is dedicated to distance colourings of graphs, a generalisation of strong edge-colourings. Extending the theme of the first chapter, we investigate minimal sparsity conditions in order to obtain Johansson-like results for distance colourings. While Johansson's result follows from the exclusion of triangles — or actually of cycles of any fixed length — we show that excluding cycles of length 2k, provided that k>t, has a similar effect for the distance-t chromatic number and the distance-(t+1) chromatic index. When t is odd, the same holds for the distance-t chromatic number by excluding cycles of fixed odd length at least 3t. We investigate the asymptotic sharpness of our results with constructions of combinatorial, algebraic, and probabilistic natures.In the third chapter, we are interested in the bipartite induced density of triangle-free graphs, a parameter which conceptually lies between the independence ratio and the fractional chromatic number. Motivated by a conjecture of Esperet, Kang, and Thomassé [EKT19], which states that the bipartite induced density of a triangle-free graph of average degree d should be at least of the order of ln d, we prove that the conjecture holds for when d is large enough in terms of the number of vertices n, namely d is at least of the order of (n ln n)^(1/2). Our result is shown to be sharp up to term of the order of ln n, with a construction relying on the triangle-free process. Our work on the bipartite induced density raises an interesting related problem, which aims at determining the maximum possible fractional chromatic number of sparse graph where the only known parameter is the number of vertices. We prove non trivial upper bounds for triangle-free graphs, and graphs where each vertex belongs to a bounded number of triangles.All the content of this thesis is a collection of specialisations of the off-diagonal Ramsey theory. To this date, the best-known bounds on the off-diagonal Ramsey number R(3,t) come from the aforementioned result of Shearer for the upper-bound, and a recent analysis of the triangle-free process [BoKe13+,FGM13+] for the lower bound, giving(1-o(1)) t²/(4 ln t) < R(3,t) < (1+o(1)) t²/ln t. (1)Many of our results are best possible barring an improvement of (1), which would be a breakthrough in off-diagonal Ramsey theory.

De nos jours, les interactions ont une part prépondérante dans notre vie. Ces interactions peuvent représenter la diffusion de rumeurs, de maladies, etc. Comprendre comment ces interactions affectent notre vie est important. Une façon naturelle de faire est d'utiliser la théorie des graphes. Néanmoins, comme le montrent certaines études, l'aspect temporel ne doit pas être négligé. Dans ce travail, nous nous sommes concentrés sur la détection d'individus importants dans ces graphes en utilisant des métriques de centralité qui prennent en compte l'aspect temporel. Nous avons proposé un protocole de comparaison qui compare les différentes mesures de centralité existantes. Nous l'avons appliqué sur plusieurs graphes, ce qui nous a donné un aperçu de la façon dont les différentes métriques agissent. Ensuite, nous avons observé le besoin de calcul élevé de ces métriques de centralité. Dès lors, nous avons introduit une méthode qui réduit ce besoin. Finalement, nous avons introduit une nouvelle mesure de centralité, appelée ego-betweenness centrality. / Nowadays, interactions are a huge part of our daily life. These interactions can represent the diffusion of rumors, diseases, etc. Understanding how these interactions affect our life is quite important. A natural way to do so is using graph theory. However, this is not straightforward as studies show the temporal aspect, in other words, the order of interactions, should be taken into account. In this work, we concentrated on detecting the important individuals in these graphs using centrality metrics that take into account the temporal aspect. We proposed a comparison protocol that compares the different centrality metrics that exist. We applied it on several networks, which gave us insight on how the different metrics react. Secondly, we observed the high computational need of these centrality metrics. Therefore, we introduced a method to reduce this need. And finally, we introduced a novel centrality metric that we call ego-betweenness centrality.

La richesse de la programmation par contraintes repose sur la très large variété des algorithmes qu’elle utilise en puisant dans les grands domaines de l’Intelligence Artificielle, de la Programmation Logique et de la Recherche Opérationnelle. Cependant, cette richesse, qui offre aux spécialistes une palette quasi-illimitée de configurations possibles pour attaquer des problèmes combinatoires, devient une frein à la diffusion plus large du paradigme, car les outils actuels sont très loin d’une boîte noire, et leur utilisation suppose une bonne connaissance du domaine, notamment en ce qui concerne leur paramétrage. Dans cette thèse, nous proposons d’analyser le comportement des contraintes de cardinalité avec des modèles probabilistes et des outils de dénombrement, pour paramétrer automatiquement les solveurs de contraintes : heuristiques de choix de variables et de choix de valeurs et stratégies de recherche. / The main asset of constraint programming is its wide variety of algorithms that comes from the major areas of artificial intelligence, logic programming and operational research. It offers specialists a limitless range of possible configurations to tackle combinatorial problems, but it becomes an obstacle to the wider diffusion of the paradigm. The current tools are very far from being used as a black-box tool, and it assumes a good knowledge of the field, in particular regarding the parametrization of solvers.In this thesis, we propose to analyze the behavior of cardinality constraints with probabilistic models and counting tools, to automatically parameterize constraint solvers: heuristics of choice of variables and choice of values and search strategies.

L'utilisation croissante des réseaux sociaux et de capteurs génère une grande quantité de données qui peuvent être représentées sous forme de graphiques complexes. Il y a de nombreuses tâches allant de l'analyse de l'information à la prédiction et à la récupération que l'on peut imaginer sur ces données où la relation entre les noeuds de graphes devrait être informative. Dans cette thèse, nous avons proposé différents modèles pour trois tâches différentes: - Classification des noeuds graphiques - Prévisions de séries temporelles relationnelles - Filtrage collaboratif. Tous les modèles proposés utilisent le cadre d'apprentissage de la représentation dans sa variante déterministe ou gaussienne. Dans un premier temps, nous avons proposé deux algorithmes pour la tâche de marquage de graphe hétérogène, l'un utilisant des représentations déterministes et l'autre des représentations gaussiennes. Contrairement à d'autres modèles de pointe, notre solution est capable d'apprendre les poids de bord lors de l'apprentissage simultané des représentations et des classificateurs. Deuxièmement, nous avons proposé un algorithme pour la prévision des séries chronologiques relationnelles où les observations sont non seulement corrélées à l'intérieur de chaque série, mais aussi entre les différentes séries. Nous utilisons des représentations gaussiennes dans cette contribution. C'était l'occasion de voir de quelle manière l'utilisation de représentations gaussiennes au lieu de représentations déterministes était profitable. Enfin, nous appliquons l'approche d'apprentissage de la représentation gaussienne à la tâche de filtrage collaboratif. Ceci est un travail préliminaire pour voir si les propriétés des représentations gaussiennes trouvées sur les deux tâches précédentes ont également été vérifiées pour le classement. L'objectif de ce travail était de généraliser ensuite l'approche à des données plus relationnelles et pas seulement des graphes bipartis entre les utilisateurs et les items. / The increasing use of social and sensor networks generates a large quantity of data that can be represented as complex graphs. There are many tasks from information analysis, to prediction and retrieval one can imagine on those data where relation between graph nodes should be informative. In this thesis, we proposed different models for three different tasks: - Graph node classification - Relational time series forecasting - Collaborative filtering. All the proposed models use the representation learning framework in its deterministic or Gaussian variant. First, we proposed two algorithms for the heterogeneous graph labeling task, one using deterministic representations and the other one Gaussian representations. Contrary to other state of the art models, our solution is able to learn edge weights when learning simultaneously the representations and the classifiers. Second, we proposed an algorithm for relational time series forecasting where the observations are not only correlated inside each series, but also across the different series. We use Gaussian representations in this contribution. This was an opportunity to see in which way using Gaussian representations instead of deterministic ones was profitable. At last, we apply the Gaussian representation learning approach to the collaborative filtering task. This is a preliminary work to see if the properties of Gaussian representations found on the two previous tasks were also verified for the ranking one. The goal of this work was to then generalize the approach to more relational data and not only bipartite graphs between users and items.

Cette thèse présente une méthode de segmentation de modèles 3D en parties significatives ou fonctionnelles. La segmentation s’effectue par "transfert" d’une segmentation exemple : la segmentation d’un modèle est calculée en transférant les segments d’une segmentation exemple d’un objet appartenant à la même classe de modèles 3D. Pour ce faire, nous avons adapté et étendu la méthode de segmentation par les marches aléatoires et transformé notre problème en un problème de localisation et mise en correspondance de faces germes. Notre méthode comporte quatre étapes fondamentales : la mise en correspondance entre le modèle exemple et le modèle cible, la localisation automatique de germes sur le modèle cible pour initialiser les régions, le calcul des segments du modèle cible et l’amélioration de leurs frontières. En constatant que les critères de similarité diffèrent selon que les objets sont de type rigide (chaises, avions,…) ou de type articulé (humains, quadrupèdes,…), nous décomposons notre approche en deux. La première dédiée aux objets rigides, où la mise en correspondance est basée sur le calcul des transformations rigides afin d’aligner au mieux les parties significatives des deux objets comparés. La deuxième dédiée aux modèles articulés, où la mise en correspondance des parties fonctionnelles, présentant des variations de poses plus importantes, est basée sur des squelettes calculés via des diagrammes de Reeb. Nous montrons à travers des évaluations qualitatives et quantitatives que notre méthode obtient des résultats meilleurs que les techniques de segmentation individuelle et comparables aux techniques de co-segmentation avec un temps de calcul nettement inférieur. / In this dissertation, we present a new method to segment 3D models into their functional parts. The segmentation is performed by a transfer approach: a semantic-oriented segmentation of an object is calculated using a pre-segmented example model from the same class (chairs, humans, etc.). To this end, we adapted and extended the random walk segmentation method which allowed us to transform our problem into a problem of locating and matching seed faces. Our method consists of four fundamental steps: establishing correspondences between the example and the target model, localizing seeds to initialize regions in the target model, computing the segments and refining their boundaries in the target model. We decomposed our approach in two, taking into account similarity criteria which differ regarding the object type (rigid vs. articulated). The first approach is dedicated to rigid objects (chairs, airplanes, etc.), where the matching is based on rigid transformations to determine the best alignment between the functional parts of the compared objects. The second one focused on articulated objects (humans, quadrupeds, etc.), where coarse topological shape attributes are used in a skeleton-based approach to cover larger pose variations when computing correspondences between functional parts. We show through qualitative and quantitative evaluations that our method improves upon individual segmentation techniques and obtains results that are close to the co-segmentation techniques results with an important calculation time reduction.

Avec l’avènement du numérique, il est désormais possible aux chercheurs d’amasser des grandes quantités de données et les plateformes de réseaux sociaux en ligne ne font pas exception à cela. Les sociologues, comme d’autres, se sont emparés de ces nouvelles ressources afin de poursuivre leurs enquêtes sur les modalités de l’interaction entre individus et leur impact sur la structuration de la sociabilité. Suivant cette voie, ce travail de thèse vise à l’analyse d’un grand nombre de comptes Facebook, aussi bien au travers des outils classiques de l’analyse de données que de la théorie des graphes, à laquelle des contributions méthodologiques sont apportées. Deux facteurs principaux encouragent l’étude de l’activité et de la sociabilité en ligne. D’une part, le temps important dédié à cette plateforme par de nombreux internautes justifie l’intérêt porté par les sociologues aux échanges qui s’y construisent. Par ailleurs, et contrairement à ce que l’on peut observer sur d’autre sites de réseaux sociaux en ligne, les liens entre individus sur Facebook sont proches de ceux hors-lignes. Dans un premier temps, la thèse s’évertue à démêler les multiples facettes de ce à quoi ”être sur Facebook” correspond. Distribués autour de pratiques normatives fabulées, les usages de nos enquêtés fluctuent au gré de leur appropriation ou non des composantes de l’importante variété de moyens de communication proposés par la plateforme. Ces usages, comme on le verra, sont ainsi différemment adoptés selon les catégories socioprofessionnelles et influent par ailleurs sur les modalités d’échanges et d’interactions des enquêtés avec leurs amis en ligne. Ces modalités sont également explorées dans ce travail, tout comme le rôle du conjoint et sa place dans la structure relationnelle. La seconde partie de la thèse se propose de construire une typologie de ces structures relationnelles dites égocentrées, c’est-à-dire depuis le point de vue de l’enquêté. Cette typologie des réseaux de sociabilité en ligne se base sur l’énumération de leurs sous-graphes induits, les graphlets, initialement développée par des chercheurs en bioinformatique. Cette approche offre une vision méso (entre micro et macro) des réseaux, propice à souligner des phénomènes inédits de sociologie des réseaux. A fort potentiel pluri-disciplinaire, la méthodologie graphlets elle même est également discutée et explorée. / With the digital advent, it is now possible for researchers to collect important amounts of data and online social network platforms are surely part of it. Sociologists, among others, seized those new resources to investigate over interaction modalities between individuals as well as their impact on the structure of sociability. Following this lead, this thesis work aims at analyzing a large number of Facebook accounts, through data analysis and graph theory classical tools, and to bring methodological contributions. Two main factors encourage to study Facebook social activities. On one hand, the importance of time spent on this platform by many Internet users justifies by itself the sociologists interest. On the other, and contrarily to what we observe on other social network websites, ties between individuals are similar to the ones that appear offline. First, the thesis proposes to detangle the multiple meanings that are behind the fact of ”being on Facebook”. The uses of our surveyed are not compacted in fantasized normative practices but vary depending on how they appropriate the different composers of the platform tools. These uses, as we will see it, do not concern all the socioprofessional categories in the same way and they also influence how the respondents interact with their online friends. The manuscript also explores these interactions, as well as the lover role into the relational structure. Second part of the thesis builds a typology of these relational structures. They are said as egocentred, which means that they are taken from the perspective of the respondent. This typology of social networks is based on their graphlet counts, that are the number of times each type of subnetwork appear in them. This approach offers a meso perspective (between micro and macro), that is propitious to underline some new social phenomena. With a high pluri-disciplinary potential, the graphlet methodology is also discussed and explored itself.

Le projet scientifique dans lequel s’inscrit ma thèse a pour objectif l’élaboration d’algorithmes distribués et efficaces pour les réseaux informatiques. Ce projet vise une catégorie particulière des algorithmes distribués, dits auto-stabilisants. Il s’agit d’algorithmes ayant pour propriété de retrouver un comportement correct suite à une panne dans le réseau et ce, sans aucune intervention humaine. Le travail effectué en collaboration avec mes directeurs de thèse s’est concentré, plus précisément, autour des problèmes de couplage, de cliques et des paradigmes de publications-souscriptions dans ce domaine de l’informatique théorique. Dans un premier temps on a traité le problème du couplage maximal dans sa version anonyme, en fournissant un algorithme auto-stabilisant probabiliste et efficace. Ces travaux sont parus dans le journal PPL. De plus, on s’est intéressé au problème du couplage dans sa version maximum identifiée. Son travail améliore le dernier algorithme présent dans la littérature pour l’approximation de ce type de couplage au 2/3 de la solution optimale. Ces travaux sont parus dans une conférence internationale OPODIS. Par ailleurs, j'ai eu l’opportunité de collaborer en Allemagne avec Prof. Volker Turau au sein du groupe de télématique de l’Université technique de Hambourg. Le cadre de cette collaboration a été les algorithmes auto-stabilisants pour les paradigmes de publication-souscription. Cela a abouti à un algorithme efficace pour la version en canal de ce problème, introduisant la notion de raccourci pour le routage de messages dans ces paradigmes. Les résultats ont fait l’objet d’un Brief Announcement et d’un papier, publiés dans des conférences internationales, SSS et NetSyS. J'ai aussi bénéficié d’une collaboration avec Mr. Gerry Siegemund qui a été accueilli au laboratoire d’Informatique de l’École Polytechnique. Il a été question de trouver un algorithme efficace et auto-stabilisant pour la partition d’un réseau en cliques. Cette collaboration a eu pour résultat un algorithme pour le problème améliorant le dernier en date. Ce résultat est en cours de rédaction pour soumission à une conférence internationale. / The main focus of my thesis is the design of an efficient kind of distributed algorithms, known as: Self-stabilizing. These algorithms have the property to recover from faults in the environment they're executed in, and this without any human intervention. Recovering here, means converging toward a pre-defined, correct configuration. In this setting, I was mainly interested by the problems of matching in graphs, clique partitions and publication subscription paradigms. For the maximal version of the matching problem in anonymous graphs, we achieved a more efficient randomized, self-stabilizing algorithm. This work is published in a journal version in PPL. The maximum version of the same problem, but in an identified setting, led to the design of an efficient self-stabilizing algorithm that approximates the optimal solution up to the 2/3. This result was published at OPODIS. During a research visit at TUHH, Hamburg, Germany. Together with Pr. Volker Turau we tackled the problem of self-stabilizing publish/subscribe paradigms. This led to an algorithm introducing the new notion of short-cuts in this type of structures and was published under a brief announcement and a regular paper at SSS and NetSyS. In collaboration with Mr. Siegemund, then a visiting researcher at LIX, École Polytechnique, we worked on an efficient self-stabilizing algorithm for clique partitions. This work is still in progress and in preparation for an eventual publication.

La science moderne des graphes est apparue ces dernières années comme un domaine d'intérêt et a apporté des progrès significatifs à notre connaissance des réseaux. Jusqu'à récemment, les algorithmes d'exploration de données existants étaient destinés à des données structurées / relationnelles, alors que de nombreux ensembles de données nécessitent une représentation graphique, comme les réseaux sociaux, les réseaux générés par des données textuelles, les structures protéiques 3D ou encore les composés chimiques. Il est donc crucial de pouvoir extraire des informations pertinantes à partir de ce type de données et, pour ce faire, les méthodes d'extraction et d'analyse des graphiques ont été prouvées essentielles.L'objectif de cette thèse est d'étudier les problèmes dans le domaine de la fouille de graphes axés en particulier sur la conception de nouveaux algorithmes et d'outils liés à la diffusion d'informations et plus spécifiquement sur la façon de localiser des entités influentes dans des réseaux réels. Cette tâche est cruciale dans de nombreuses applications telles que la diffusion de l'information, les contrôles épidémiologiques et le marketing viral.Dans la première partie de la thèse, nous avons étudié les processus de diffusion dans les réseaux sociaux ciblant la recherche de caractéristiques topologiques classant les entités du réseau en fonction de leurs capacités influentes. Nous nous sommes spécifiquement concentrés sur la décomposition K-truss qui est une extension de la décomposition k-core. On a montré que les noeuds qui appartiennent au sous-graphe induit par le maximal K-truss présenteront de meilleurs proprietés de propagation par rapport aux critères de référence. De tels épandeurs ont la capacité non seulement d'influencer une plus grande partie du réseau au cours des premières étapes d'un processus d'étalement, mais aussi de contaminer une plus grande partie des noeuds.Dans la deuxième partie de la thèse, nous nous sommes concentrés sur l'identification d'un groupe de noeuds qui, en agissant ensemble, maximisent le nombre attendu de nœuds influencés à la fin du processus de propagation, formellement appelé Influence Maximization (IM). Le problème IM étant NP-hard, il existe des algorithmes efficaces garantissant l’approximation de ses solutions. Comme ces garanties proposent une approximation gloutonne qui est coûteuse en termes de temps de calcul, nous avons proposé l'algorithme MATI qui réussit à localiser le groupe d'utilisateurs qui maximise l'influence, tout en étant évolutif. L'algorithme profite des chemins possibles créés dans le voisinage de chaque nœud et précalcule l'influence potentielle de chaque nœud permettant ainsi de produire des résultats concurrentiels, comparés à ceux des algorithmes classiques.Finallement, nous étudions le point de vue de la confidentialité quant au partage de ces bons indicateurs d’influence dans un réseau social. Nous nous sommes concentrés sur la conception d'un algorithme efficace, correct, sécurisé et de protection de la vie privée, qui résout le problème du calcul de la métrique k-core qui mesure l'influence de chaque noeud du réseau. Nous avons spécifiquement adopté une approche de décentralisation dans laquelle le réseau social est considéré comme un système Peer-to-peer (P2P). L'algorithme est construit de telle sorte qu'il ne devrait pas être possible pour un nœud de reconstituer partiellement ou entièrement le graphe en utilisant les informations obtiennues lors de son exécution. Notre contribution est un algorithme incrémental qui résout efficacement le problème de maintenance de core en P2P tout en limitant le nombre de messages échangés et les calculs. Nous fournissons également une étude de sécurité et de confidentialité de la solution concernant la désanonymisation des réseaux, nous montrons ainsi la rélation avec les strategies d’attaque précédemment definies tout en discutant les contres-mesures adaptés. / Modern science of graphs has emerged the last few years as a field of interest and has been bringing significant advances to our knowledge about networks. Until recently the existing data mining algorithms were destined for structured/relational data while many datasets exist that require graph representation such as social networks, networks generated by textual data, 3D protein structures and chemical compounds. It has become therefore of crucial importance to be able to extract meaningful information from that kind of data and towards this end graph mining and analysis methods have been proven essential. The goal of this thesis is to study problems in the area of graph mining focusing especially on designing new algorithms and tools related to information spreading and specifically on how to locate influential entities in real-world networks. This task is crucial in many applications such as information diffusion, epidemic control and viral marketing. In the first part of the thesis, we have studied spreading processes in social networks focusing on finding topological characteristics that rank entities in the network based on their influential capabilities. We have specifically focused on the K-truss decomposition which is an extension of the core decomposition of the graph. Extensive experimental analysis showed that the nodes that belong to the maximal K-truss subgraph show a better spreading behavior when compared to baseline criteria. Such spreaders can influence a greater part of the network during the first steps of a spreading process but also the total fraction of the influenced nodes at the end of the epidemic is greater. We have also observed that node members of such dense subgraphs are those achieving the optimal spreading in the network.In the second part of the thesis, we focused on identifying a group of nodes that by acting all together maximize the expected number of influenced nodes at the end of the spreading process, formally called Influence Maximization (IM). The IM problem is actually NP-hard though there exist approximation guarantees for efficient algorithms that can solve the problem while obtaining a solution within the 63% of optimal classes of models. As those guarantees propose a greedy approximation which is computationally expensive especially for large graphs, we proposed the MATI algorithm which succeeds in locating the group of users that maximize the influence while also being scalable. The algorithm takes advantage the possible paths created in each node’s neighborhood to precalculate each node’s potential influence and produces competitive results in quality compared to those of baseline algorithms such as the Greedy, LDAG and SimPath. In the last part of the thesis, we study the privacy point of view of sharing such metrics that are good influential indicators in a social network. We have focused on designing an algorithm that addresses the problem of computing through an efficient, correct, secure, and privacy-preserving algorithm the k-core metric which measures the influence of each node of the network. We have specifically adopted a decentralization approach where the social network is considered as a Peer-to-peer (P2P) system. The algorithm is built based on the constraint that it should not be possible for a node to reconstruct partially or entirely the graph using the information they obtain during its execution. While a distributed algorithm that computes the nodes’ coreness is already proposed, dynamic networks are not taken into account. Our main contribution is an incremental algorithm that efficiently solves the core maintenance problem in P2P while limiting the number of messages exchanged and computations. We provide a security and privacy analysis of the solution regarding network de-anonimization and show how it relates to previously defined attacks models and discuss countermeasures.