L'objectif de cette thèse est de développer des outils de prédiction d'interactions entre protéines qui puissent être appliqués en particulier sur le réseau d’interaction autour de la protéine CFTR, qui est impliquée dans la mucoviscidose. Le développement de méthodes de prédiction in silico peut s'avérer utile pour suggérer aux biologistes de nouvelles cibles d'interaction. Nous proposons une nouvelle méthode pour la prédiction de liens dans un réseau. Afin de bénéficier de l'information des données non étiquetées, nous nous plaçons dans le cadre de l'apprentissage semi-supervisé. Nous abordons ce problème de prédiction comme une tâche d'apprentissage d'un noyau de sortie. Un noyau de sortie est supposé coder les proximités existantes entres les nœuds du graphe et l'objectif est d'approcher ce noyau à partir de descriptions appropriées en entrée. L'utilisation de l'astuce du noyau dans l'ensemble de sortie permet de réduire le problème d'apprentissage à celui d'une fonction d'une seule variable à valeurs dans un espace de Hilbert. En choisissant les fonctions candidates pour la régression dans un espace de Hilbert à noyau reproduisant à valeur opérateur, nous développons, comme dans le cas de fonctions à valeurs scalaires, des outils de régularisation. Nous établissons en particulier des théorèmes de représentation, qui permettent de définir de nouveaux modèles de régression. Nous avons testé l'approche développée sur des données artificielles, des problèmes test ainsi que sur un réseau d'interaction chez la levure et obtenu de très bons résultats. Puis nous l'avons appliquée à la prédiction d'interactions entre protéines dans le cas d'un réseau construit autour de CFTR. / The aim of this thesis is to develop tools for predicting interactions between proteins that can be applied to the human proteins forming a network with the CFTR protein. This protein, when defective, is involved in cystic fibrosis. The development of in silico prediction methods can be useful for biologists to suggest new interaction targets. We propose a new method to solve the link prediction problem. To benefit from the information of unlabeled data, we place ourselves in the semi-supervised learning framework. Link prediction is addressed as an output kernel learning task, referred as Output Kernel Regression. An output kernel is assumed to encode the proximities of nodes in the target graph and the goal is to approximate this kernel by using appropriate input features. Using the kernel trick in the output space allows one to reduce the problem of learning from pairs to learning a single variable function with output values in a Hilbert space. By choosing candidates for regression functions in a reproducing kernel Hilbert space with operator valued kernels, we develop tools for regularization as for scalar-valued functions. We establish representer theorems in the supervised and semi-supervised cases and use them to define new regression models for different cost functions. We first tested the developed approach on transductive link prediction using artificial data, benchmark data as well as a protein-protein interaction network of the yeast and we obtained very good results. Then we applied it to the prediction of protein interactions in a network built around the CFTR protein.

The so-called Web 2.0 revolution has fundamentally changed the way people interact with the Internet. The Web has turned from a read-only infrastructure to a collaborative platform. By expressing their preferences and sharing private information, the users benefit from a personalized Web experience. Yet, these systems raise several problems in terms of \emph{privacy} and \emph{scalability}. The social platforms use the user information for commercial needs and expose the privacy and preferences of the users. Furthermore, centralized personalized systems require costly data-centers. As a consequence, existing centralized social platforms do not exploit the full extent of the personalization possibilities. In this thesis, we consider the design of social networks and social information services in the context of \emph{peer-to-peer} (P2P) networks. P2P networks are decentralized architecture, thus the users participates to the service and control their own data. This greatly improves the privacy of the users and the scalability of the system. Nevertheless, building social systems in a distributed context also comes with many challenges. The information is distributed among the users and the system has be able to efficiently locate relevant data. The contributions of this thesis are as follow. We define the \emph{cold start link prediction} problem, which consists in predicting the edges of a social network solely from the social information of the users. We propose a method based on a \emph{probabilistic graph} to solve this problem. We evaluate it on a dataset from Flickr, using the group membership as social information. Our results show that the social information indeed enables a prediction of the social network. Thus, the centralization of the information threatens the privacy of the users, hence the need for decentralized systems. We propose \textsc{SoCS}, a \emph{decentralized} algorithm for \emph{link prediction}. Recommending neighbors is a central functionality in social networks, and it is therefore crucial to propose a decentralized approach as a first step towards P2P social networks. \textsc{SoCS} relies on gossip protocols to perform a force-based embedding of the social networks. The social coordinates are then used to predict links among vertices. We show that \textsc{SoCS} is adapted to decentralized systems at it is churn resilient and has a low bandwidth consumption. We propose \textsc{GMIN}, a \emph{decentralized} platform for \emph{personalized services} based on social information. \textsc{GMIN} provides each user with neighbors that share her interests. The clustering algorithm we propose takes care to encompass all the different interests of the user, and not only the main ones. We then propose a personalized \emph{query expansion} algorithm (\textsc{GQE}) that leverages the \textsc{GMIN} neighbors. For each query, the system computes a tag centrality based on the relations between tags as seen by the user and her neighbors.

Dans cette thèse, nous étudions la sémantique des relations entre les utilisateurs et des forces antagonistes que nous observons naturellement dans diverses relations sociales, comme hostilité ou méfiance. L'étude de ces relations soulève de nombreux problèmes à la fois techniques, puisque l'arsenal mathématique n'est souvent pas adapté aux liens négatifs, mais aussi pratiques à cause de la difficulté rencontrée pour collecter de telles données (expliciter une relation négative est perçu comme malvenu pour de nombreux utilisateurs). Nous nous intéressons alors aux solutions alternatives de collecte afin d'inférer ces relations négatives à partir d'autres contenus. En particulier, nous allons utiliser les jugements communs que les utilisateurs partagent à propos d'items (données des systèmes de recommandation). Nous apportons trois contributions. Dans la première, nous allons aborder le cas des accords sur les items qui peuvent ne pas avoir la même sémantique selon qu'ils concernent des items appréciés ou non par les utilisateurs. Nous verrons que le fait de ne pas aimer un même produit n'est pas synonyme de similarité. Ensuite, nous allons prendre en compte dans notre seconde contribution les distributions de notes des utilisateurs et des items afin de mesurer si les accords ou les désaccords arrivent par hasard ou non, afin notamment d'éviter les conséquences des différents biais utilisateurs et items présents dans ce type de données. Enfin, notre troisième contribution consistera à exploiter ces différents résultats afin de prédire le signe des liens entre utilisateurs à partir des seuls jugements communs à propos des items et sans aucune information sociale négative. / In this thesis, we study the semantic of relations between users and, in particular, the antagonistic forces we naturally observe in various social relationships, such as hostility or suspicion. The study of these relationships raises many problems both techniques - because the mathematical arsenal is not really adapted to the negative ties - and practical, due to the difficulty of collecting such data (explaining a negative relationship is perceived as intrusive and inappropriate for many users). That’s why we focus on the alternative solutions consisting in inferring these negative relationships from more widespread content. We use the common judgments about items the users share, which are the data used in recommender systems. We provide three contributions, described in three distinct chapters. In the first one, we discuss the case of agreements about items that may not have the same semantics if they involve appreciated items or not by two users. We will see that disliking the same product does not mean similarity. Afterward, we consider in our second contribution the distributions of user ratings and items ratings in order to measure whether the agreements or disagreements may happen by chance or not, in particular to avoid the user and item biases observed in this type of data. Our third contribution consists in using these results to predict the sign of the links between users from the only positive ties and the common judgments about items, and then without any negative social information.

L'explosion de données relationnelles largement disponiblessous la forme de graphes de connaissances a permisle développement de multiples applications, dont les agents personnels automatiques,les systèmes de recommandation et l'amélioration desrésultats de recherche en ligne.La grande taille et l'incomplétude de ces bases de donnéesnécessite le développement de méthodes de complétionautomatiques pour rendre ces applications viables.La complétion de graphes de connaissances, aussi appeléeprédiction de liens, se doit de comprendre automatiquementla structure des larges graphes de connaissances (graphes dirigéslabellisés) pour prédire les entrées manquantes (les arêtes labellisées).Une approche gagnant en popularité consiste à représenter ungraphe de connaissances comme un tenseur d'ordre 3, etd'utiliser des méthodes de décomposition de tenseur pourprédire leurs entrées manquantes.Les modèles de factorisation existants proposent différentscompromis entre leur expressivité, et leur complexité en temps et en espace.Nous proposons un nouveau modèle appelé ComplEx, pour"Complex Embeddings", pour réconcilier expressivité etcomplexité par l'utilisation d'une factorisation en nombre complexes,dont nous explorons le lien avec la diagonalisation unitaire.Nous corroborons notre approche théoriquement en montrantque tous les graphes de connaissances possiblespeuvent être exactement décomposés par le modèle proposé.Notre approche, basées sur des embeddings complexesreste simple, car n'impliquant qu'un produit trilinéaire complexe,là où d'autres méthodes recourent à des fonctions de compositionde plus en plus compliquées pour accroître leur expressivité.Le modèle proposé ayant une complexité linéaire en tempset en espace est passable à l'échelle, tout endépassant les approches existantes sur les jeux de données de référencepour la prédiction de liens.Nous démontrons aussi la capacité de ComplEx àapprendre des représentations vectorielles utiles pour d'autres tâches,en enrichissant des embeddings de mots, qui améliorentles prédictions sur le problème de traitement automatiquedu langage d'implication entre paires de phrases.Dans la dernière partie de cette thèse, nous explorons lescapacités de modèles de factorisation à apprendre lesstructures relationnelles à partir d'observations.De part leur nature vectorielle,il est non seulement difficile d'interpréter pourquoicette classe de modèles fonctionne aussi bien,mais aussi où ils échouent et comment ils peuventêtre améliorés. Nous conduisons une étude expérimentalesur les modèles de l'état de l'art, non pas simplementpour les comparer, mais pour comprendre leur capacitésd'induction. Pour évaluer les forces et faiblessesde chaque modèle, nous créons d'abord des tâches simplesreprésentant des propriétés atomiques despropriétés des relations des graphes de connaissances ;puis des tâches représentant des inférences multi-relationnellescommunes au travers de généalogies synthétisées.À partir de ces résultatsexpérimentaux, nous proposons de nouvelles directionsde recherches pour améliorer les modèles existants,y compris ComplEx. / The explosion of widely available relational datain the form of knowledge graphsenabled many applications, including automated personalagents, recommender systems and enhanced web search results.The very large size and notorious incompleteness of these data basescalls for automatic knowledge graph completion methods to make these applicationsviable. Knowledge graph completion, also known as link-prediction,deals with automatically understandingthe structure of large knowledge graphs---labeled directed graphs---topredict missing entries---labeled edges. An increasinglypopular approach consists in representing knowledge graphs as third-order tensors,and using tensor factorization methods to predict their missing entries.State-of-the-art factorization models propose different trade-offs between modelingexpressiveness, and time and space complexity. We introduce a newmodel, ComplEx---for Complex Embeddings---to reconcile both expressivenessand complexity through the use of complex-valued factorization, and exploreits link with unitary diagonalization.We corroborate our approach theoretically and show that all possibleknowledge graphs can be exactly decomposed by the proposed model.Our approach based on complex embeddings is arguably simple,as it only involves a complex-valued trilinear product,whereas other methods resort to more and more complicated compositionfunctions to increase their expressiveness. The proposed ComplEx model isscalable to large data sets as it remains linear in both space and time, whileconsistently outperforming alternative approaches on standardlink-prediction benchmarks. We also demonstrateits ability to learn useful vectorial representations for other tasks,by enhancing word embeddings that improve performanceson the natural language problem of entailment recognitionbetween pair of sentences.In the last part of this thesis, we explore factorization models abilityto learn relational patterns from observed data.By their vectorial nature, it is not only hard to interpretwhy this class of models works so well,but also to understand where they fail andhow they might be improved. We conduct an experimentalsurvey of state-of-the-art models, not towardsa purely comparative end, but as a means to get insightabout their inductive abilities.To assess the strengths and weaknesses of each model, we create simple tasksthat exhibit first, atomic properties of knowledge graph relations,and then, common inter-relational inference through synthetic genealogies.Based on these experimental results, we propose new researchdirections to improve on existing models, including ComplEx.

Durant ces dernières années, nous avons observe une expansion progressive et continue des réseaux mobile sans-fil centres sur l’être humain. L’apparition de ces réseaux a encouragé les chercheurs à réfléchir à de nouvelles solutions pour assurer une évaluation efficace et une conception adéquate des protocoles de communication. En effet, ces réseaux sont sujets à de multiples contraintes telles que le manque d’infrastructure, la topologie dynamique, les ressources limitées ainsi que la qualité de service et la sécurité des informations précaires. Nous nous sommes spécialement intéressés à l’aspect dynamique du réseau et en particulier à la mobilité humaine. La mobilité humaine a été largement étudiée pour pouvoir extraire ses propriétés intrinsèques et les exploiter pour des approches plus adaptées à cette mobilité. Parmi les propriétés les plus intéressantes soulevées dans la littérature, nous nous sommes focalisés sur l’impact des interactions sociales entre les entités du réseau sur la mobilité humaine et en conséquence sur la structure du réseau. Pour recueillir des informations structurelles sur le réseau, plusieurs métriques et techniques ont été empruntées de l’analyse des réseaux sociaux (SNA). Cet outil peut être assimilé à une autre alternative pour mesurer des indicateurs de performance du réseau. Plus précisément, il extrait des informations structurelles du réseau et permet aux protocoles de communication de bénéficier d’indications utiles telles que la robustesse du réseau, les nœuds centraux ou encore les communautés émergentes. Dans ce contexte, la SNA a été largement utilisée pour prédire les liens dans les réseaux sociaux en se basant notamment sur les informations structurelles. Motivés par l’importance des liens sociaux dans les réseaux mobiles sans-fil centres sur l’être humain et par les possibilités offertes par la SNA pour prédire les liens, nous nous proposons de concevoir la première méthode capable de prédire les liens dans les réseaux sans-fil mobiles tels que les réseaux ad-hoc mobiles (MANETs) et les réseaux tolérants aux délais (DTNs). Notre proposition suit l’évolution de la topologie du réseau sur T périodes à travers un tenseur (en ensemble de matrices d’adjacence et chacune des matrices correspond aux contacts observés durant une période bien spécifique). Ensuite, elle s’appuie sur le calcul de la mesure sociométrique de Katz pour chaque paire de nœuds pour mesurer l’étendue des relations sociales entre les différentes entités du réseau. Une telle quantification donne un aperçu sur les liens dont l’occurrence est fortement pressentie à la période T+1 et les nouveaux liens qui se créent dans le futur sans pour autant avoir été observés durant le temps de suivi. Pour attester l’efficacité de notre proposition, nous l’appliquons sur trois traces réelles et nous comparons sa performance à celles d’autres techniques de prédiction de liens présentées dans la littérature. Les résultats prouvent que notre méthode est capable d’atteindre le meilleur niveau d’efficacité et sa performance surpasse celles des autres techniques. L’une des majeures contributions apportées par cette proposition met en exergue la possibilité de prédire les liens d’une manière décentralisée. En d’autres termes, les nœuds sont capables de prédire leurs propres liens dans le futur en se basant seulement sur la connaissance du voisinage immédiat (voisins à un et deux sauts). En outre, nous sommes désireux d’améliorer encore plus la performance de notre méthode de prédiction de liens. Pour quantifier la force des relations sociales entre les entités du réseau, nous considérons deux aspects dans les relations : la récence des interactions et leur fréquence. À partir de là, nous nous demandons s’il est possible de prendre en compte un troisième critère pour améliorer la précision des prédictions […] / During the last years, we have observed a progressive and continuous expansion of human-centered mobile wireless networks. The advent of these networks has encouraged the researchers to think about new solutions in order to ensure efficient evaluation and design of communication protocols. In fact, these networks are faced to several constraints as the lack of infrastructure, the dynamic topology, the limited resources and the deficient quality of service and security. We have been interested in the dynamicity of the network and in particular in human mobility. The human mobility has been widely studied in order to extract its intrinsic properties and to harness them to propose more accurate approaches. Among the prominent properties depicted in the literature, we have been specially attracted by the impact of the social interactions on the human mobility and consequently on the structure of the network. To grasp structural information of such networks, many metrics and techniques have been borrowed from the Social Network Analysis (SNA). The SNA can be seen as another network measurement task which extracts structural information of the network and provides useful feedback for communication protocols. In this context, the SNA has been extensively used to perform link prediction in social networks relying on their structural properties. Motivated by the importance of social ties in human-centered mobile wireless networks and by the possibilities that are brought by SNA to perform link prediction, we are interested by designing the first link prediction framework adapted for mobile wireless networks as Mobile Ad-hoc Networks (MANETs) and Delay/Disruption Tolerant Networks (DTN). Our proposal tracks the evolution of the network through a third-order tensor over T periods and computes the sociometric Katz measure for each pair of nodes to quantify the strength of the social ties between the network entities. Such quantification gives insights about the links that are expected to occur in the period T+1 and the new links that are created in the future without being observed during the tracking time. To attest the efficiency of our framework, we apply our link prediction technique on three real traces and we compare its performance to the ones of other well-known link prediction approaches. The results prove that our method reaches the highest level of accuracy and outperforms the other techniques. One of the major contributions behind our proposal highlights that the link prediction in such networks can be made in a distributed way. In other words, the nodes can predict their future links relying on the local information (one-hop and two-hop neighbors) instead of a full knowledge about the topology of the network. Furthermore, we are keen to improve the link prediction performance of our tensor-based framework. To quantify the social closeness between the users, we take into consideration two aspects of the relationships: the recentness of the interactions and their frequency. From this perspective, we wonder if we can consider a third criterion to improve the link prediction precision. Asserting the heuristic that stipulates that persistent links are highly predictable, we take into account the stability of the relationships (link and proximity stabilities). To measure it, we opt for the entropy estimation of a time series proposed in the Lempel-Ziv data compression algorithm. As we think that our framework measurements and the stability estimations complement each other, we combine them in order to provide new link prediction metrics. The simulation results emphasize the pertinence of our intuition. Providing a tensor-based link prediction framework and proposing relative enhancements tied to stability considerations represent the main contributions of this thesis. Along the thesis, our concern was also focused on mechanisms and metrics that contribute towards improving communication protocols in these mobile networks […]

Les réseaux sociaux sont de très grands systèmes permettant de représenter les interactions sociales entre les individus. L'analyse des réseaux sociaux est une collection de méthodes spécialement conçues pour examiner les aspects relationnels des structures sociales. L'un des défis les plus importants dans l'analyse de réseaux sociaux est le problème de prédiction de liens. La prédiction de liens étudie l'existence potentielle de nouvelles associations parmi des entités sociales non connectées. La plupart des approches de prédiction de liens se concentrent sur une seule source d'information, c'est-à-dire sur les aspects topologiques du réseau (par exemple le voisinage des nœuds) en supposant que les données sociales sont entièrement fiables. Pourtant, ces données sont généralement bruitées, manquantes et sujettes à des erreurs d'observation causant des distorsions et des résultats probablement erronés. Ainsi, cette thèse propose de gérer le problème de prédiction de liens sous incertitude. D'abord, deux nouveaux modèles de graphes de réseaux sociaux uniplexes et multiplexes sont introduits pour traiter l'incertitude dans les données sociales. L'incertitude traitée apparaît au niveau des liens et est représentée et gérée à travers le cadre de la théorie des fonctions de croyance. Ensuite, nous présentons huit méthodes de prédiction de liens utilisant les fonctions de croyance fondées sur différentes sources d'information dans les réseaux sociaux uniplexes et multiplexes. Nos contributions s'appuient sur les informations disponibles sur le réseau social. Nous combinons des informations structurelles aux informations des cercles sociaux et aux attributs des nœuds, ainsi que l'apprentissage supervisé pour prédire les nouveaux liens. Des tests sont effectués pour valider la faisabilité et l'intérêt de nos approches à celles de la littérature. Les résultats obtenus sur les données du monde réel démontrent que nos propositions sont pertinentes et valables dans le contexte de prédiction de liens. / Social networks are large structures that depict social linkage between millions of actors. Social network analysis came out as a tool to study and monitor the patterning of such structures. One of the most important challenges in social network analysis is the link prediction problem. Link prediction investigates the potential existence of new associations among unlinked social entities. Most link prediction approaches focus on a single source of information, i.e. network topology (e.g. node neighborhood) assuming social data to be fully trustworthy. Yet, such data are usually noisy, missing and prone to observation errors causing distortions and likely inaccurate results. Thus, this thesis proposes to handle the link prediction problem under uncertainty. First, two new graph-based models for uniplex and multiplex social networks are introduced to address uncertainty in social data. The handled uncertainty appears at the links level and is represented and managed through the belief function theory framework. Next, we present eight link prediction methods using belief functions based on different sources of information in uniplex and multiplex social networks. Our proposals build upon the available information in data about the social network. We combine structural information to social circles information and node attributes along with supervised learning to predict new links. Tests are performed to validate the feasibility and the interest of our link prediction approaches compared to the ones from literature. Obtained results on social data from real-world demonstrate that our proposals are relevant and valid in the link prediction context.

L'objectif de cette thèse est de développer des outils de prédiction d'interactions entre protéines qui puissent être appliqués en particulier chez l'homme, sur les protéines qui constituent un réseau avec la protéine CFTR. Cette protéine, lorsqu'elle est défectueuse, est impliquée dans la mucoviscidose. Le développement de méthodes de prédiction in silico peut s'avérer utile pour suggérer aux biologistes de nouvelles cibles d'interaction et pour mieux expliquer les fonctions des protéines présentes dans ce réseau. Nous proposons une nouvelle méthode pour le problème de la prédiction de liens dans un réseau. Afin de bénéficier de l'information des données non étiquetées, nous nous plaçons dans le cadre de l'apprentissage semi-supervisé. Nous abordons ce problème de prédiction comme une tâche d'apprentissage d'un noyau de sortie, appelée régression à noyau de sortie. Un noyau de sortie est supposé coder les proximités existantes entre les noeuds du graphe et l'objectif est d'approcher ce noyau à partir de descriptions appropriées en entrée. L'utilisation de l'astuce du noyau dans l'ensemble de sortie permet de réduire le problème d'apprentissage à partir de paires à un problème d'apprentissage d'une fonction d'une seule variable à valeurs dans un espace de Hilbert. En choisissant les fonctions candidates pour la régression dans un espace de Hilbert à noyau reproduisant à valeur opérateur, nous développons, comme dans le cas de fonctions à valeurs scalaires, des outils de régularisation. Nous établissons en particulier des théorèmes de représentation dans le cas supervisé et dans le cas semi-supervisé, que nous utilisons ensuite pour définir de nouveaux modèles de régression pour différentes fonctions de coût, appelés IOKR-ridge et IOKR-margin. Nous avons d'abord testé l'approche développée sur des données artificielles, des problèmes test ainsi que sur un réseau d'interaction protéine-protéine chez la levure S. Cerevisiae et obtenu de très bons résultats. Puis nous l'avons appliquée à la prédiction d'interactions entre protéines dans le cas d'un réseau construit autour de la protéine CFTR.