En l'absence d'une autorité de nommage centrale sur le Web de données, il est fréquent que différents graphes de connaissances utilisent des noms (IRIs) différents pour référer à la même entité. Chaque fois que plusieurs noms sont utilisés pour désigner la même entité, les faits owl:sameAs sont nécessaires pour déclarer des liens d’identité et améliorer l’exploitation des données disponibles. De telles déclarations d'identité ont une sémantique logique stricte, indiquant que chaque propriété affirmée à un nom sera également déduite à l'autre et vice versa. Bien que ces inférences puissent être extrêmement utiles pour améliorer les systèmes fondés sur les connaissances tels que les moteurs de recherche et les systèmes de recommandation, l'utilisation incorrecte de l'identité peut avoir des effets négatifs importants dans un espace de connaissances global comme le Web de données. En effet, plusieurs études ont montré que owl:sameAs est parfois incorrectement utilisé sur le Web des données. Cette thèse étudie le problème de liens d’identité erronés ou inappropriés qui sont exprimés par des liens owl:sameAs et propose des solutions différentes mais complémentaires. Premièrement, elle présente une ressource contenant la plus grande collection de liens d’identité collectés du LOD Cloud, avec un service Web à partir duquel les données et leur clôture transitive peuvent être interrogées. Une telle ressource a à la fois des impacts pratiques (elle aide les utilisateurs à trouver différents noms pour la même entité), ainsi qu'une valeur analytique (elle révèle des aspects importants de la connectivité du LOD Cloud). En outre, en s’appuyant sur cette collection de 558 millions liens d’identité, nous montrons comment des mesures de réseau telles que la structure de communauté du réseau owl:sameAs peuvent être utilisées afin de détecter des liens d’identité éventuellement erronées. Pour cela, nous attribuons un degré d'erreur pour chaque lien owl:sameAs en fonction de la densité de la ou des communautés dans lesquelles elles se produisent et de leurs caractéristiques symétriques. L'un des avantages de cette approche est qu'elle ne repose sur aucune connaissance supplémentaire. Finalement, afin de limiter l'utilisation excessive et incorrecte du owl:sameAs, nous définissons une nouvelle relation pour représenter l'identité de deux instances d’une classe dans un contexte spécifique (une sous-partie de l’ontologie). Cette relation d'identité s'accompagne d'une approche permettant de détecter automatiquement ces liens, avec la possibilité d'utiliser certaines contraintes expertes pour filtrer des contextes non pertinents. La détection et l’exploitation des liens d’identité contextuels détectés sont effectuées sur deux graphes de connaissances pour les sciences de la vie, construits en collaboration avec des experts du domaine de l’institut national de la recherche agronomique (INRA). / In the absence of a central naming authority on the Web of data, it is common for different knowledge graphs to refer to the same thing by different names (IRIs). Whenever multiple names are used to denote the same thing, owl:sameAs statements are needed in order to link the data and foster reuse. Such identity statements have strict logical semantics, indicating that every property asserted to one name, will also be inferred to the other, and vice versa. While such inferences can be extremely useful in enabling and enhancing knowledge-based systems such as search engines and recommendation systems, incorrect use of identity can have wide-ranging effects in a global knowledge space like the Web of data. With several studies showing that owl:sameAs is indeed misused for different reasons, a proper approach towards the handling of identity links is required in order to make the Web of data succeed as an integrated knowledge space. This thesis investigates the identity problem at hand, and provides different, yet complementary solutions. Firstly, it presents the largest dataset of identity statements that has been gathered from the LOD Cloud to date, and a web service from which the data and its equivalence closure can be queried. Such resource has both practical impacts (it helps data users and providers to find different names for the same entity), as well as analytical value (it reveals important aspects of the connectivity of the LOD Cloud). In addition, by relying on this collection of 558 million identity statements, we show how network metrics such as the community structure of the owl:sameAs graph can be used in order to detect possibly erroneous identity assertions. For this, we assign an error degree for each owl:sameAs based on the density of the community(ies) in which they occur, and their symmetrical characteristics. One benefit of this approach is that it does not rely on any additional knowledge. Finally, as a way to limit the excessive and incorrect use of owl:sameAs, we define a new relation for asserting the identity of two ontology instances in a specific context (a sub-ontology). This identity relation is accompanied with an approach for automatically detecting these links, with the ability of using certain expert constraints for filtering irrelevant contexts. As a first experiment, the detection and exploitation of the detected contextual identity links are conducted on two knowledge graphs for life sciences, constructed in a mutual effort with domain experts from the French National Institute of Agricultural Research (INRA).

La puissance de calcul des plus grands calculateurs ne fait qu'augmenter: de quelques centaines de cœurs de calculs dans les années 1990, on en est maintenant à plusieurs millions! Leur infrastructure évolue aussi: elle n'est plus linéaire, mais complètement hiérarchique. Les applications de calcul intensif, largement utilisées par la communauté scientifique, doivent donc se munir d'outils permettant d'utiliser pleinement l'ensemble de ces ressources de manière efficace. La simulation numérique repose bien souvent sur d'importants calculs dont le coût, en termes de temps et d'accès mémoire, peut fortement varier au cours du temps: on parle de charge de calcul variable. Dans cette Thèse, on se propose d'étudier les outils actuels de répartition des données et des calculs, afin de voir les raisons qui font que de tels outils ne sont pas pleinement adaptés aux fortes variations de charge ainsi qu'à la hiérarchie toujours plus importante des nouveaux calculateurs. Nous proposerons alors un nouveau modèle d'ordonnancement et de partitionnement, basé sur des interactions physiques, particulièrement adapté aux applications basées sur des maillages réguliers et présentant de fortes variations de charge au cours du temps. Nous validerons alors ce modèle en le comparant à des outils de partitionnement de graphes reconnus et largement utilisés, et verrons les raisons qui le rendent plus performant pour des applications aussi bien parallèles que distribuées. Enfin, nous proposerons une interface nous permettant d'utiliser cette méthode d'ordonnancement dans des calculateurs toujours plus hiérarchiques. / Computing capability of largest computing centers is still increasing: from a few hundred of cores in the90's, they can now exceed several million of cores! Their infrastructure also evolves: it is no longerlinear, but fully hierarchical.High Performance applications, well used by the scientific community, require on tools that allow themto efficiently and fully use computing resources.Numerical simulations mostly rely on large computations chains for which the cost (computing load), either acomputing time or a memory access time, can strongly vary over time: it is referred to as dynamic computing loadevolution.In this thesis, we propose to study actual data partitioning and computing scheduling tools, and to explore theirlimitations with regards to strong and repetitive load variation as well as the still increasing cluster hierarchy.We will then propose a new scheduling and partitioning model, based on physical interactions, particularlysuitable to regular mesh based applications that produce strong computing load variations over time.We will then compare our model against well-known and widely used graph partitioning tools and we will see thereasons that make this model more reliable for such parallel and distributed applications.Lastly, we will propose a multi-level scheduling interface that is specially designed to allow to use ourmodel in even more hierarchical clusters.

Les graphes de données sont naturellement utilisés dans de nombreux contextes incluant par exemple les réseaux sociaux ou le Web sémantique. L'information contenue dans la base de données se trouve alors aussi bien dans les données mêmes que dans la topologie du graphe, c'est-à-dire dans la manière dont les données sont connectées. Cela implique donc de considérer les questions traditionnelles en théorie des bases de données pour des langages de requêtes capables de parler des chemins connectant les nœuds du graphe. Nous nous intéressons en particulier aux problèmes de la déterminabilité et de la réécriture d'une requête à l'aide de vues. Il s'agit alors de décider si une vue de la base de données contient suffisamment d'information pour répondre entièrement à une requête sans consulter la base de données directement, et dans ce cas, d'exprimer explicitement la réponse à la requête à partir de la vue. Ce cadre rencontre de nombreuses applications, notamment pour l'intégration de données et l'optimisation de requêtes. Nous commençons par comparer ces deux questions aux autres problèmes de décision classiques dans ce contexte : calcul des réponses certaines, test de cohérence et mise à jour d'une instance de vue. Nous améliorons ensuite ces résultats dans deux cas spécifiques. Tout d'abord, nous montrons que pour les requêtes régulières de chemin, l'existence d'une réécriture monotone coïncide avec l'existence d'une réécriture dans Datalog. Puis, nous montrons que pour des vues s'intéressant uniquement aux longueurs des chemins du graphe, une notion plus faible de déterminabilité, appelée déterminabilité asymptotique, est décidable et résulte en des réécritures du premier ordre. / Graph databases appear naturally in various scenarios, such as social networks and the semantic Web. In these cases, the information contained in the database lies as much in the data itself as in the topology of the graph, that is, in how the data points are linked together. This leads to considering traditional database theory questions for query languages that return data nodes based on the paths of the graph connecting them. We focus our attention on the view-based query determinacy and rewriting problems. They ask the question whether a view of the database contains enough information to fully answer a query without accessing the database directly. If so, we then want to express the answer to the query directly with regards to the view. This setting occurs in many applications, such as data integration and query optimization. We start by comparing these two tasks to other common task in this setting: computing certain answers, checking consistency of a view instance and updating it. We then build on these results in two specific cases. First, we show that for regular path queries, the existence of a monotone rewriting coincides with the existence of a rewriting expressible in Datalog. Then, we show that for views that only consider the lengths of the path in the graph, we can decide a weaker form of determinacy, called asymptotic determinacy, and produce first-order rewritings for the queries that are asymptotically determined.

Cette thèse réunit en trois articles mon intérêt éclectique pour la théorie des graphes. Le premier problème étudié est la conjecture de Erdos-Faber-Lovász: La réunion de k graphes complets distincts, ayant chacun k sommets, qui ont deux-à-deux au plus un sommet en commun peut être proprement coloriée en k couleurs. Cette conjecture se caractérise par le peu de résultats publiés. Nous prouvons qu’une nouvelle classe de graphes, construite de manière inductive, satisfait la conjecture. Le résultat consistera à présenter une classe qui ne présente pas les limitations courantes d’uniformité ou de régularité. Le deuxième problème considère une conjecture concernant la couverture des arêtes d’un graphe: Si G est un graphe simple avec alpha(G) = 2, alors le nombre minimum de cliques nécessaires pour couvrir l’ensemble des arêtes de G (noté ecc(G)) est au plus n, le nombre de sommets de G. La meilleure borne connue satisfaite par ecc(G) pour tous les graphes avec nombre d’indépendance de deux est le minimum de n + delta(G) et 2n − omega(racine (n log n)), où delta(G) est le plus petit nombre de voisins d’un sommet de G. Notre objectif a été d’obtenir la borne ecc(G) <= 3/2 n pour une classe de graphes la plus large possible. Un autre résultat associé à ce problème apporte la preuve de la conjecture pour une classe particulière de graphes: Soit G un graphe simple avec alpha(G) = 2. Si G a une arête dominante uv telle que G \ {u,v} est de diamètre 3, alors ecc(G) <= n. Le troisième problème étudie le jeu de policier et voleur sur un graphe. Presque toutes les études concernent les graphes statiques, et nous souhaitons explorer ce jeu sur les graphes dynamiques, dont les ensembles d’arêtes changent au cours du temps. Nowakowski et Winkler caractérisent les graphes statiques pour lesquels un unique policier peut toujours attraper le voleur, appellés cop-win, à l’aide d’une relation <= définie sur les sommets de ce graphe: Un graphe G est cop-win si et seulement si la relation <= définie sur ses sommets est triviale. Nous adaptons ce théorème aux graphes dynamiques. Notre démarche nous mène à une relation nous permettant de présenter une caractérisation des graphes dynamiques cop-win. Nous donnons ensuite des résultats plus spécifiques aux graphes périodiques. Nous indiquons aussi comment généraliser nos résultats pour k policiers et l voleurs en réduisant ce cas à celui d’un policier unique et un voleur unique. Un algorithme pour décider si, sur un graphe périodique donné, k policiers peuvent capturer l voleurs découle de notre caractérisation. / This thesis represents in three articles my eclectic interest for graph theory. The first problem is the conjecture of Erdos-Faber-Lovász: If k complete graphs, each having k vertices, have the property that every pair of distinct complete graphs have at most one vertex in common, then the vertices of the resulting graph can be properly coloured by using k colours. This conjecture is notable in that only a handful of classes of EFL graphs are proved to satisfy the conjecture. We prove that the Erdos-Faber-Lovász Conjecture holds for a new class of graphs, and we do so by an inductive argument. Furthermore, graphs in this class have no restrictions on the number of complete graphs to which a vertex belongs or on the number of vertices of a certain type that a complete graph must contain. The second problem addresses a conjecture concerning the covering of the edges of a graph: The minimal number of cliques necessary to cover all the edges of a simple graph G is denoted by ecc(G). If alpha(G) = 2, then ecc(G) <= n. The best known bound satisfied by ecc(G) for all the graphs with independence number two is the minimum of n + delta(G) and 2n − omega(square root (n log n)), where delta(G) is the smallest number of neighbours of a vertex in G. In this type of graph, all the vertices at distance two from a given vertex form a clique. Our approach is to extend all of these n cliques in order to cover the maximum possible number of edges. Unfortunately, there are graphs for which it’s impossible to cover all the edges with this method. However, we are able to use this approach to prove a bound of ecc(G) <= 3/2n for some newly studied infinite families of graphs. The third problem addresses the game of Cops and Robbers on a graph. Almost all the articles concern static graphs, and we would like to explore this game on dynamic graphs, the edge sets of which change as a function of time. Nowakowski and Winkler characterize static graphs for which a cop can always catch the robber, called cop-win graphs, by means of a relation <= defined on the vertices of such graphs: A graph G is cop-win if and only if the relation <= defined on its vertices is trivial. We adapt this theorem to dynamic graphs. Our approach leads to a relation, that allows us to present a characterization of cop-win dynamic graphs. We will then give more specific results for periodic graphs, and we will also indicate how to generalize our results to k cops and l robbers by reducing this case to one with a single cop and a single robber. An algorithm to decide whether on a given periodic graph k cops can catch l robbers follows from our characterization.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Dans cette thèse, nous étudions les propriétés de concentration des fonctions propres du laplacien discret sur des graphes réguliers de degré fixé dont le nombre de sommets tend vers l'infini. Cette étude s'inspire de la théorie de l'ergodicité quantique sur les variétés. Par analogie avec cette dernière, nous développons un calcul pseudo-différentiel sur les arbres réguliers : nous définissons des classes de symboles et des opérateurs associés, et nous prouvons un certain nombre de propriétés de ces classes de symboles et opérateurs. Nous montrons notamment que les opérateurs sont bornés dans L², et nous donnons des formules de l'adjoint et du produit. Nous nous servons ensuite de cette théorie pour montrer un théorème d'ergodicité quantique pour des suites de graphes réguliers dont le nombre de sommets tend vers l'infini. Il s'agit d'un résultat de délocalisation de la plupart des fonctions propres dans la limite des grands graphes réguliers. Les graphes vérifient une hypothèse d'expansion et ne comportent pas trop de cycles courts, deux hypothèses vérifiées presque sûrement par des suites de graphes réguliers aléatoires. / N this thesis, we study concentration properties of eigenfunctions of the discrete Laplacian on regular graphs of fixed degree, when the number of vertices tend to infinity. This study is made in analogy with the Quantum Ergodicity theory on manifolds. We construct a pseudo-differential calculus on regular trees by defining symbol classes and associated operators and proving some properties of these classes of symbols and operators. In particular we prove that the operators are bounded on L² and give adjoint and product formulas. We then use this theory to prove a Quantum Ergodicity theorem on large regular graphs. This is a property of delocalization of most eigenfunctions in the large scale limit. We consider expander graphs with few short cycles (for instance random large regular graphs). These hypothesis are almost surely satisfied by sequences of random regular graphs.

Le système immunitaire adaptatif est capable de produire une réponse spécifique contre presque tous le pathogènes qui agressent notre organisme. Ceci est dû aux anticorps qui sont des protéines secrétées par les cellules B. Les molécules qui provoquent cette réaction sont appelées antigènes : pendant une réponse immunitaire, les cellules B sont soumises à un processus d’apprentissage afin d’améliorer leur capacité à reconnaitre un antigène donne. Ce processus est appelé maturation d’affinité des anticorps. Nous établissons un cadre mathématique très flexible dans lequel nous définissons et étudions des modelés évolutionnaires simplifies inspirés par la maturation d’affinité des anticorps. Nous identifions les éléments constitutifs fondamentaux de ce mécanisme d’évolution extrêmement rapide et efficace : mutation, division et sélection. En commençant par une analyse rigoureuse du mécanisme de mutation dans le Chapitre 2, nous procédons à l’enrichissement progressif du modelé en ajoutant et analysant le processus de division dans le Chapitre 3 ,puis des pressions sélectives dépendantes de l’affinité dans le Chapitre 4. Notre objectif n’est pas de construire un modèle mathématique très détaillé et exhaustif de la maturation d’affinité des anticorps, mais plutôt d’enquêter sur les interactions entre mutation, division et sélection dans un contexte théorique simplifie. On cherche à comprendre comment les différents paramètres biologiques influencent la fonctionnalité du système, ainsi qu’à estimer les temps caractéristiques de l’exploration de l’espace d’états des traits des cellules B. Au-delà des motivations biologiques de la modélisation de la maturation d’affinité des anticorps, l’analyse de ce processus d’apprentissage nous a amenée à concevoir un modèle mathématique qui peut également s’appliquer à d’autres systèmes d’évolution, mais aussi à l’étude de la propagation de rumeurs ou de virus. Notre travail théorique s’accompagne de nombreuses simulations numériques qui viennent soit l’illustrer soit montrer que certains résultats demeurent extensibles a des situations plus compliquées. / The adaptive immune system is able to produce a specific response against almost any pathogen that could penetrate our organism and inflict diseases. This task is assured by the production of antigen-specific antibodies secreted by B-cells. The agents which causes this reaction are called antigens: during an immune response B-cells are submitted to a learning process in order to improve their ability to recognize the immunizing antigen. This process is called antibody affinity maturation. We set a highly flexible mathematical environment in which we define and study simplified mathematical evolutionary models inspired by antibody affinity maturation. We identify the fundamental building blocks of this extremely efficient and rapid evolutionary mechanism: mutation, division and selection. Starting by a rigorous analysis of the mutational mechanism in Chapter 2, we proceed by successively enriching the model by adding and analyzing the division process in Chapter 3 and affinity-dependent selection pressures in Chapter 4. Our aim is not to build a very detailed and comprehensive mathematical model of antibody affinity maturation, but rather to investigate interactions between mutation, division and selection in a simplified theoretical context. We want to understand how the different biological parameters affect the system’s functionality, as well as estimate the typical time-scales of the exploration of the state-space of B-cell traits. Beyond the biological motivations of antibody affinity maturation modeling, the analysis of this learning process leads us to build a mathematical model which could be relevant to model other evolutionary systems, but also gossip or virus propagation. Our method is based on the complementarity between probabilistic tools and numerical simulations.

Les applications réelles liées aux problèmes de satisfaction partielle de contraintes (PCSP : Partial Constraints Satisfaction Problem) sont de plus en plus nombreuses, ce qui justifie l’intérêt croissant des chercheurs pour cette classe de problèmes. La résolution d’un PCSP revient à affecter des valeurs à toutes ses variables tout en maximisant (ou minimisant) une fonction objectif prédéfinie. Ces problèmes sont NP-difficiles, par conséquent il n’existe aucune approche aussi bien exacte qu’heuristique efficace sur les grandes instances. Pour résoudre efficacement les instances difficiles, une multitude de solutions sont proposées, allant de l’hybridation à l’apprentissage en passant par la décomposition. Dans notre travail, nous nous intéressons à cette dernière proposition, qui consiste à fractionner le problème PCSP en plusieurs sous-problèmes PCSP de tailles raisonnables, puis proposer des algorithmes de résolution pour les problèmes décomposés. Cette approche a pour but de bénéficier de la structure du problème afin d’accélérer sa résolution tout en garantissant des solutions optimales ou sous-optimales. Deux grand axes sont explorés : les approches basées sur la décomposition et celles guidées par la décomposition. Les approches basées sur la décomposition consistent à résoudre séparément les parties difficiles du problème décomposé, puis combiner les solutions partielles obtenues en vue d’atteindre une solution globale du problème d’origine. Les approches guidées par la décomposition consistent à développer des métaheuristiques qui tiennent compte de la structure du problème décomposé. Les algorithmes proposés sont testés et validés sur des instances réelles des problèmes PSCP, comme le problème d’affectation de fréquences et le problème de coloration de graphes / The wide range of potential applications concerned by the resolution of Partial Constraints Satisfaction Problems (PCSP) justifies the growing interest of scientists in this class of problems. Solving a PCSP means searching for values to assign to the decision variables in order to maximize (or minimize) a predefined objective function. These problems are NP-hard, so there isn’t an exact approach nor an efficient heuristic able to provide the optimal solution for large instances. In order to solve effectively the difficult instances, numerous approaches based on hybridization, learning or decomposition are proposed. In the present work, we focus on the latter proposal, which consists in splitting the PCSP into several smaller size PCSPs and we propose some methods to solve the decomposed problem. Two wide axes are explored : the resolution based on the decomposition and the one guided by decomposition. The former solves separately the difficult parts of the decomposed problem (cuts or clusters) and then combines partial solutions obtained in order to achieve a global solution for the original problem. The latter aims at benefiting from the structure of the problem to be decomposed in order to accelerate its resolution while ensuring optimal or near optimal solutions. All the proposed algorithms are tested and validated on the well-known benchmarks of PCSP problems such as Frequency Assignment Problem (FAP) and graph coloring problem

La recherche menée dans cette thèse a pour but de développer une analyse harmonique pour des fonctions définies sur les sommets d'un graphe orienté. À l'ère du déluge de données, de nombreuses données sont sous forme de graphes et données sur ce graphe. Afin d'analyser d'exploiter ces données de graphes, nous avons besoin de développer des méthodes mathématiques et numériquement efficientes. Ce développement a conduit à l'émergence d'un nouveau cadre théorique appelé le traitement de signal sur graphe dont le but est d'étendre les concepts fondamentaux du traitement de signal classique aux graphes. Inspirées par l'aspect multi échelle des graphes et données sur graphes, de nombreux constructions multi-échelles ont été proposé. Néanmoins, elles s'appliquent uniquement dans le cadre non orienté. L'extension d'une analyse harmonique sur graphe orienté bien que naturelle, s'avère complexe. Nous proposons donc une analyse harmonique en utilisant l'opérateur de marche aléatoire comme point de départ de notre cadre. Premièrement, nous proposons des bases de type Fourier formées des vecteurs propres de l'opérateur de marche aléatoire. De ces bases de Fourier, nous en déterminons une notion fréquentielle en analysant la variation de ses vecteurs propres. La détermination d'une analyse fréquentielle à partir de la base des vecteurs de l'opérateur de marche aléatoire nous amène aux constructions multi-échelles sur graphes orientés. Plus particulièrement, nous proposons une construction en trames d'ondelettes ainsi qu'une construction d'ondelettes décimées sur graphes orientés. Nous illustrons notre analyse harmonique par divers exemples afin d'en montrer l'efficience et la pertinence. / The research conducted in this thesis aims to develop a harmonic analysis for functions defined on the vertices of an oriented graph. In the era of data deluge, much data is in the form of graphs and data on this graph. In order to analyze and exploit this graph data, we need to develop mathematical and numerically efficient methods. This development has led to the emergence of a new theoretical framework called signal processing on graphs, which aims to extend the fundamental concepts of conventional signal processing to graphs. Inspired by the multi-scale aspect of graphs and graph data, many multi-scale constructions have been proposed. However, they apply only to the non-directed framework. The extension of a harmonic analysis on an oriented graph, although natural, is complex. We, therefore, propose a harmonic analysis using the random walk operator as the starting point for our framework. First, we propose Fourier-type bases formed by the eigenvectors of the random walk operator. From these Fourier bases, we determine a frequency notion by analyzing the variation of its eigenvectors. The determination of a frequency analysis from the basis of the vectors of the random walk operator leads us to multi-scale constructions on oriented graphs. More specifically, we propose a wavelet frame construction as well as a decimated wavelet construction on directed graphs. We illustrate our harmonic analysis with various examples to show its efficiency and relevance.