Au cours de la dernière décennie, les réseaux (les graphes) se sont révélés être un outil efficace pour modéliser des systèmes complexes. La problématique de détection de communautés est une tâche centrale dans l’analyse des réseaux complexes. La majeur partie des travaux dans ce domaine s’intéresse à la structure topologique des réseaux. Cependant, dans plusieurs cas réels, les réseaux complexes ont un ensemble d’attributs associés aux nœuds et/ou aux liens. Ces réseaux sont dites : réseaux attribués. Mes activités de recherche sont basées principalement sur la détection des communautés dans les réseaux attribués. Pour aborder ce problème, on s’est intéressé dans un premier temps aux attributs relatifs aux liens, qui sont un cas particulier des réseaux multiplexes. Un multiplex est un modèle de graphe multi-relationnel. Il est souvent représenté par un graphe multi-couches. Chaque couche contient le même ensemble de nœuds mais encode une relation différente. Dans mes travaux de recherche, nous proposons une étude comparative des différentes approches de détection de communautés dans les réseaux multiplexes. Cette étude est faite sur des réseaux réels. Nous proposons une nouvelle approche centrée "graine" pour la détection de communautés dans les graphes multiplexes qui a nécessité la redéfinition des métriques de bases des réseaux complexes au cas multiplex. Puis, nous proposons une approche de clustering dans les réseaux attribués qui prend en considération à la fois les attributs sur les nœuds et sur les liens. La validation de mes approches a été faite avec des indices internes et externes, mais aussi par une validation guidée par un système de recommandation que nous avons proposé et dont la détection de communautés est sa tâche principale. Les résultats obtenus sur ces approches permettent d’améliorer la qualité des communautés détectées en prenant en compte les informations sur les attributs du réseaux. De plus, nous offrons des outils d’analyse des réseaux attribués sous le langage de programmation R. / In complex networks analysis field, much effort has been focused on identifying graphs communities of related nodes with dense internal connections and few external connections. In addition to node connectivity information that are mostly composed by different types of links, most real-world networks contains also node and/or edge associated attributes which can be very relevant during the learning process to find out the groups of nodes i.e. communities. In this case, two types of information are available : graph data to represent the relationship between objects and attributes information to characterize the objects i.e nodes. Classic community detection and data clustering techniques handle either one of the two types but not both. Consequently, the resultant clustering may not only miss important information but also lead to inaccurate findings. Therefore, various methods have been developed to uncover communities in networks by combining structural and attribute information such that nodes in a community are not only densely connected, but also share similar attribute values. Such graph-shape data is often referred to as attributed graph.This thesis focuses on developing algorithms and models for attributed graphs. Specifically, I focus in the first part on the different types of edges which represent different types of relations between vertices. I proposed a new clustering algorithms and I also present a redefinition of principal metrics that deals with this type of networks.Then, I tackle the problem of clustering using the node attribute information by describing a new original community detection algorithm that uncover communities in node attributed networks which use structural and attribute information simultaneously. At last, I proposed a collaborative filtering model in which I applied the proposed clustering algorithms.

Le but de cette thèse est d'améliorer la qualité des systèmes de recommandation pour la navigation Web en utilisant la séquentialité des actions de navigation des utilisateurs. La notion de séquentialité a déjà été étudiée dans ce contexte. De telles études tentent habituellement de trouver un bon compromis entre précision, complexité en temps et en mémoire, et couverture. De plus, le Web a cela de particulier que du bruit peut être contenu au sein des navigations (erreurs de navigation, apparition de pop-ups, etc.), et que les utilisateurs peuvent effectuer des navigations parallèles. La plupart des modèles qui ont été proposés dans la littérature exploitent soit des suites contiguës de ressources et ne sont pas résistants au bruit, soit des suites discontiguës de ressources et induisent une complexité en temps et en mémoire importantes. Cette complexité peut être réduite en effectuant une sélection sur les séquences, mais cela engendre alors des problèmes de couverture. Enfin à notre connaissance, le fait que les utilisateurs puissent effectuer des navigations parallèles n'a jamais été étudié du point de vue de la recommandation. La problématique de cette thèse est donc de proposer un nouveau modèle séquentiel ayant les cinq caractéristiques suivantes : (1) une bonne précision de recommandation, (2) une bonne résistance au bruit, (3) la prise en compte des navigations parallèles, (4) une bonne couverture (5) et une faible complexité en temps et en mémoire. Afin de répondre à cette problématique, nous nous inspirons de la Modélisation Statistique du Langage (MSL), qui a des caractéristiques très proches de celles de la navigation Web. La MSL est étudiée depuis beaucoup plus longtemps que les systèmes de recommandation et a largement prouvé sa précision et son efficacité. De plus, la plupart des modèles statistiques de langage qui ont été proposés prennent en compte des séquences. Nous avons donc étudié la possibilité d'exploiter les modèles utilisés en MSL et leur adaptation aux contraintes spécifiques de la navigation Web.

Cette thèse porte sur l'utilisation des GAI-Nets, un modèle graphique pour la représentation compacte de préférences, pour atteindre des fonctionnalités propres à un système de recommandation dans le cadre où l'espace d'alternatives a une structure combinatoire de grande taille. Typiquement, les systèmes de recommandation sur le Web utilisent des techniques bien adaptées au conseil d'articles fortement standardisés, tels que les CDs et les DVDs, mais impraticables dans un cadre combinatoire. Par ailleurs, les systèmes de recommandation pour le cadre combinatoire sont souvent fondés sur des modèles supposant une indépendance entre attributs qui assure la modélisation des préférences par une utilité additive. Les GAI-Nets permettent des interactions entre les attributs, étant ainsi plus généraux. Nos problématiques clés sont le choix et le rangement des kmeilleures alternatives. Nous étudions également le problème de la recherche de solutions de compromis selon des critères non-linéaires dans le cadre de la décision collective/multicritère, et aussi l'élicitation des GAI-Nets. Nous proposons des algorithmes adaptés à la résolution de tels problèmes et, finalement, nous construisons une application Web pour appliquer les techniques développées dans une situation décisionnelle concrète.

Ces dernières années, le contenu disponible sur le Web a augmenté de manière considérable dans ce qu’on appelle communément le Web social. Pour l’utilisateur moyen, il devient de plus en plus difficile de recevoir du contenu de qualité sans se voir rapidement submergé par le flot incessant de publications. Pour les fournisseurs de service, le passage à l’échelle reste problématique. L’objectif de cette thèse est d’aboutir à une meilleure expérience utilisateur à travers la mise en place de systèmes de filtrage et de recommandation. Le filtrage consiste à offrir la possibilité à un utilisateur de ne recevoir qu’un sous ensemble des publications des comptes auxquels il est abonné. Tandis que la recommandation permet la découverte d’information à travers la suggestion de comptes à suivre sur des sujets donnés. Nous avons élaboré MicroFilter un système de filtrage passant à l’échelle capable de gérer des flux issus du Web ainsi que RecLand, un système de recommandation qui tire parti de la topologie du réseau ainsi que du contenu afin de générer des recommandations pertinentes. / In the last years, the amount of available data on the social Web has exploded. For the average user, it became hard to find quality content without being overwhelmed with publications. For service providers, the scalability of such services became a challenging task. The aim of this thesis is to achieve a better user experience by offering the filtering and recommendation features. Filtering consists to provide for a given user, the ability of receiving only a subset of the publications from the direct network. Where recommendation allows content discovery by suggesting relevant content producers on given topics. We developed MicroFilter, a scalable filtering system able to handle Web-like data flows and RecLand, a recommender system that takes advantage of the network topology as well as the content in order to provide relevant recommendations.

Cette thèse s'articule autour des problèmes d'optimisation à grande échelle, et plus particulièrement autour des méthodes de factorisation matricielle sur des problèmes de grandes tailles. L'objectif des méthodes de factorisation de grandes matrices est d'extraire des variables latentes qui permettent d'expliquer les données dans un espace de dimension réduite. Nous nous sommes intéressés au domaine d'application de la recommandation et plus particulièrement au problème de prédiction de préférences d'utilisateurs. Dans une contribution nous nous sommes intéressés à l'application de méthodes de factorisation dan un environnement de recommandation contextuelle et notamment dans un contexte social. Dans une seconde contribution, nous nous sommes intéressés au problème de sélection de modèle pour la factorisation où l'on cherche à déterminer de façon automatique le rang de la factorisation par estimation de risque.

Cette thèse s'articule autour des problèmes d'optimisation à grande échelle, et plus particulièrement autour des méthodes de factorisation matricielle sur des problèmes de grandes tailles. L'objectif des méthodes de factorisation de grandes matrices est d'extraire des variables latentes qui permettent d'expliquer les données dans un espace de dimension réduite. Nous nous sommes intéressés au domaine d'application de la recommandation et plus particulièrement au problème de prédiction de préférences d'utilisateurs.Dans une contribution, nous nous sommes intéressés à l'application de méthodes de factorisation dans un environnement de recommandation contextuelle et notamment dans un contexte social.Dans une seconde contribution, nous nous sommes intéressés au problème de sélection de modèle pour la factorisation où l'on cherche à déterminer de façon automatique le rang de la factorisation par estimation de risque.

L’OLAP (On-Line Analytical Processing) est le paradigme principal pour accéder aux données multidimensionnelles dans les entrepôts de données. Pour obtenir une haute expressivité d’interrogation, malgré un petit effort de formulation de la requête, OLAP fournit un ensemble d’opérations (comme drill-down et slice-and-dice ) qui transforment une requête multidimensionnelle en une autre, de sorte que les requêtes OLAP sont normalement formulées sous la forme de séquences appelées Sessions OLAP. Lors d’une session OLAP l’utilisateur analyse les résultats d’une requête et, selon les données spécifiques qu’il voit, applique une seule opération afin de créer une nouvelle requête qui lui donnera une meilleure compréhension de l’information. Les séquences de requêtes qui en résultent sont fortement liées à l’utilisateur courant, le phénomène analysé, et les données. Alors qu’il est universellement reconnu que les outils OLAP ont un rôle clé dans l’exploration souple et efficace des cubes multidimensionnels dans les entrepôts de données, il est aussi communément admis que le nombre important d’agrégations et sélections possibles, qui peuvent être exploités sur des données, peut désorienter l’expérience utilisateur. / OLAP (On-Line Analytical Processing) is the main paradigm for accessing multidimensional data in data warehouses. To obtain high querying expressiveness despite a small query formulation effort, OLAP provides a set of operations (such as drill-down and slice-and-dice) that transform one multidimensional query into another, so that OLAP queries are normally formulated in the form of sequences called OLAP sessions. During an OLAP session the user analyzes the results of a query and, depending on the specific data she sees, applies one operation to determine a new query that will give her a better understanding of information. The resulting sequences of queries are strongly related to the issuing user, to the analyzed phenomenon, and to the current data. While it is universally recognized that OLAP tools have a key role in supporting flexible and effective exploration of multidimensional cubes in data warehouses, it is also commonly agreed that the huge number of possible aggregations and selections that can be operated on data may make the user experience disorientating.

Les plateformes de crowdsourcing spatial (PCS) sont des systèmes qui permettent à des personnes, appelées commanditaires, de publier des tâches spatiales afin de trouver la main-d’œuvre pour les exécuter. Ces tâches spatiales exigent que leurs exécutants soient à un endroit donné, souvent dans une fenêtre de temps donnée, pour être accomplies. Quelques exemples de PCS sont Uber et TaskRabbit. Les PCS suscitent beaucoup d’intérêt dans la recherche, mais des pistes de recherche sont encore à explorer.Doan et al. [2011] a soutenu que l’objectif réside maintenant dans “la construction de plateformes générales de crowdsourcing qui peuvent être utilisées pour développer rapidement ces systèmes”. Depuis, peu de travaux ont porté sur la conception technique des PCS. En outre, il existe un écart entre ce qui est mis en oeuvre par les PCS de l’industrie et les propositions que l’on trouve dans la littérature scientifique. Nous proposons GENIUS-C, une architecture générique pour les PCS. Nous fournissons une implémentation de référence (IR) pour GENIUS-C, fonctionnant comme un cadre pour le développement de PCS. GENIUS-C et son IR sont destinés à combler les écarts entre le monde académique et industriel, et faciliter la compréhension et le développement rapide de PCS.Nous étudions également l’important problème de l’appariement des exécutants et des tâches d’un PCS. Comment peut-on trouver une ou plusieurs tâches adaptées à un exécutant (et vice versa)? Certains utilisent des techniques de système de recommandation, d’autres des approches d’optimisation. La plupart d’entre eux ne tiennent pas compte des dimensions spatio-temporelles des tâches et des exécutants. Ceux qui en tiennent compte ignorent les préférences des exécutants, des commanditaires ou du système lui-même. Dans ce contexte, nous identifions et modélisons le problème réel et récurrent suivant: une fois que l’exécutant est prêt à accomplir des tâches, quelle est la meilleure séquence de tâches à suivre en respectant ses contraintes spatio-temporelles? Comment cette séquence peut-elle être obtenue en tenant compte des préférences de l’exécutant, des commanditaires, du système lui-même ou d’une combinaison de ceux-ci? Nous nommons cette situation le Problème de la Recommandation de Trajectoire, auquel nous proposons une solution optimale, et étudions des heuristiques d’approximation pour le résoudre. / Spatial Crowdsourcing Platforms (SCP) are systems that allow people, called requesters, to publish spatial tasks in order to find suitable workforce to perform it. These spatial tasks require workers to be at a given location, usually within a given time window, to be accomplished. Some examples of SCPs are: Uber, BlaBlaCar and TaskRabbit. SCPs are source of much interest for academy, however several research opportunities remain.Doan et al. [2011] argued that the race is now on “toward building general crowdsourcing platforms that can be used to develop such systems quickly". Since then, little has been done to investigate the technical design of SCPs precisely. Also, there is a gap between what is done in commercial platform and in scientific literature. We propose GENIUS-C, a generic architecture for SPCs. We provide a reference implementation (RI) for GENIUS-C, that works as a framework for the development of SCPs. GENIUS-C and its RI are meant to fill the gap between the academic and industry world, and facilitate the understanding and the quick development of new SCPs.We also study the important problem of matching workers and tasks. How can we find one or more tasks suitable for a worker (and vice versa)? Some tackle this issue using recommender system techniques, others optimization approaches. Most of them do not take into account the spatiotemporal dimensions of tasks and workers. Others take it into account, but to ignore the preferences of either workers, requesters or the system itself. In this context, we identify and model the following common real-life problem: once a worker is willing to spend sometime accomplishing tasks, what is the best sequence of tasks to be followed respecting their spatiotemporal constraints? How can this sequence be obtained taking into account the preferences of the worker, the requesters, the system itself, or a combination of them? We name this situation the Trajectory Recommendation Problem (TRP), propose a feasible exact solution and study approximation heuristics for it.

La publication scientifique dans les revues spécialisées et les actes de conférences permet de communiquer les progrès en sciences. Les comités de rédaction et de programme sous-jacents représentent la clé de voûte du processus d'évaluation. Avec le développement des revues et le nombre croissant de conférences scientifiques organisées chaque année, rechercher des experts pour participer à ces comités est une activité chronophage mais critique. Cette thèse se focalise sur la tâche de suggestion de membres de comité de programme (CP) pour des conférences scientifiques. Elle comporte trois volets. Premièrement, nous proposons une modélisation basée sur un graphe hétérogène pondéré de l'expertise scientifique multifacette des chercheurs. Deuxièmement, nous définissons des indicateurs scientométriques pour quantifier les critères impliqués dans la constitution de CP. Troisièmement, nous concevons une approche de suggestion de membres de CP pour une conférence donnée, en combinant les résultats des indicateurs scientométriques susmentionnés. Notre approche est expérimentée pour une des conférences de premier plan de notre communauté de recherche : SIGIR, en considérant ses éditions de 1971 à 2015, ainsi que les conférences proches thématiquement. / Academic publishing in specialized journals and conference proceedings is the main way to communicate progress in science. The underlying editorial and program committees represent the cornerstone of the evaluation process. With the development of journals and the increasing number of scientific conferences held annually, searching for experts who would serve in these committees is a time-consuming and yet critical activity. This PhD thesis focuses on the task of suggesting program committee (PC) members for scientific conferences. It is organized into three parts. First, we propose a modelling of the multifaceted scientific expertise of researchers based on a weighted heterogeneous graph. Second, we define scientometric indicators to quantify the criteria involved in the composition of CPs. Third, we design a CP member suggestion approach for a given conference, combining the results of the aforementioned scientometric indicators. Our approach is experimented in the context of leading conferences of our research community: SIGIR, considering its editions from 1971 to 2015, and topically close conferences.

Les systèmes de recommandation actuels ont besoin de recommander des objets pertinents aux utilisateurs (exploitation), mais pour cela ils doivent pouvoir également obtenir continuellement de nouvelles informations sur les objets et les utilisateurs encore peu connus (exploration). Il s'agit du dilemme exploration/exploitation. Un tel environnement s'inscrit dans le cadre de ce que l'on appelle " apprentissage par renforcement ". Dans la littérature statistique, les stratégies de bandit sont connues pour offrir des solutions à ce dilemme. Les contributions de cette thèse multidisciplinaire adaptent ces stratégies pour appréhender certaines problématiques des systèmes de recommandation, telles que la recommandation de plusieurs objets simultanément, la prise en compte du vieillissement de la popularité d'un objet ou encore la recommandation en temps réel. / Current recommender systems need to recommend items that are relevant to users (exploitation), but they must also be able to continuously obtain new information about items and users (exploration). This is the exploration / exploitation dilemma. Such an environment is part of what is called "reinforcement learning". In the statistical literature, bandit strategies are known to provide solutions to this dilemma. The contributions of this multidisciplinary thesis the adaptation of these strategies to deal with some problems of the recommendation systems, such as the recommendation of several items simultaneously, taking into account the aging of the popularity of an items or the recommendation in real time.