1,721,019 research outputs found
Recommandations dans les réseaux sociaux en fonction du contexte de diffusion d'information
No full textAvec la popularité montante des médias sociaux en tant que voies d'accès à l'information, la formulation de recommandations dans des scénarios sociaux spécifiques mérite une attention particulière, où les modèles de diffusion de l'information et les mécanismes d'influence sont exploités. Dans notre travail, nous nous efforçons de servir l'information aux utilisateurs des médias sociaux de manière directe ou indirecte : la première se rapportant à la recommandation des actualités et la seconde à la maximisation de l'influence dans un objectif de l'équité.Les systèmes de recommandation des actualités sont généralement basés sur le contenu sémantique des articles et les profils des utilisateurs, alors que le scénario de recommandation implicite est ignoré. Nous considérons une perspective de diffusion et d'influence sur le problème de la recommandation des actualités, et nous proposons une approche légère d'apprentissage profond, appelée DSN (Deep Influence-Aware News Recommendation in Social Media). Cette approche vise la recommandation des actualités dans les plateformes de micro-blogging, telles que Twitter ou Weibo, dont l'extrême vélocité des données exige un compromis satisfaisant entre la complexité du modèle et son efficacité. Nous utilisons des "graph embeddings" - des représentations de nœuds qui sont indicatives des schémas de diffusion des actualités - qui conduisent à des informations sociales précieuses pour les recommandations. Pour fusionner les représentations sémantiques et sociales des actualités, un réseau neuronal convolutif spécialement conçu pour la représentation conjointe des caractéristiques (SCNN, Social-Related Multi-Source Feature Extraction) est utilisé comme encodeur d'actualité, tandis qu'un modèle d'attention agrège automatiquement les différents intérêts des utilisateurs. Pour approfondir la dimension temporelle et les problèmes liés à la séquentialité de la recommandation des actualités dans le scénario des microblogs, nous proposons une deuxième approche de recommandation qui tient également compte de la diffusion et de l'influence dans le média, appelée IGNiteR (News Recommendation in Microblogging Applications). Il s'agit d'un modèle de recommandation approfondie basé sur le contenu qui exploite conjointement toutes les facettes des données susceptibles d'avoir un impact sur les décisions d'y acceder. Nous avons réalisé des expériences approfondies sur les deux mêmes ensembles de données du monde réel, montrant qu'IGNiteR surpasse les méthodes de recommandation des actualités basées sur l'apprentissage profond les plus récentes.Pour la recommandation indirecte des informations concernant la maximisation de l'influence avec équité, qui vise à sélectionner k nœuds influents pour maximiser la diffusion d'informations dans un réseau, tout en garantissant que certains attributs sensibles des utilisateurs (par exemple, le sexe, l'emplacement, l'âge, etc.) sont affectés équitablement. Le défi consiste donc à trouver une solution évolutive, applicable à des réseaux comptant des millions ou des milliards de nœuds. Nous proposons deux approches basées sur les données : (a) l'échantillonnage des participants basé sur l'équité (FPS, Fairness-based Participant Sampling), et (b) l'équité en tant que contexte (FAC, Fairness as Contex). Elles sont basées sur l'apprentissage des représentations des nœuds (embeddings) pour extraire les caractéristiques des utilisateurs liées à la propagation des informations à partir des cascades de diffusion, au lieu de la connectivité sociale, et de cette façon nous pouvons traiter de très grands graphes. Les caractéristiques extraites sont ensuite utilisées pour sélectionner les influenceurs qui maximisent la propagation de l'influence. Les algorithmes proposés sont génériques et représentent les premières solutions axées sur les politiques qui peuvent être appliquées à des ensembles arbitraires d'attributs sensibles à grande échelle.With the increasing popularity of social media as pathways to information, making recommendations in specific social scenarios deserves attention, where the information diffusion patterns and influence mechanisms therein are exploited. We strive in our work to develop models and algorithms for serving information to users in social media, either in a direct user-based (personalized) way or in an indirect audience-based way, with the former pertaining to news recommendation and the latter referring to fairness in influence maximization. News recommendation systems are generally based on the semantic content of news items and user profiles, whereas the underlying recommendation scenario is ignored. We consider in our PhD work a diffusion and influence-aware perspective on the news recommendation problem, and we first propose a lightweight deep learning approach for it, called DSN. This approach targets news recommendation in micro-blogging platforms, such as Twitter or Weibo, whose extreme data velocity demands a satisfactory trade-off between the model's complexity and its effectiveness. We use graph embeddings -- node representations that are indicative of news diffusion patterns -- leading to valuable social-related information for recommendations. To merge the semantics and social-related representations of news, a specially designed convolutional neural network for joint feature representation (SCNN) is used as the news encoder, while an attention model automatically aggregates the different interests of users. To further exploit the time dimension, with a sequential recommendation perspective on news recommendation in the micro-blogging scenario, we propose secondly in our PhD work an alternative deep-learning based recommendation model, which is also diffusion and influence-aware, called Influence-Graph News Recommender (IGNteR). It is a content-based deep recommendation model that jointly exploits all the data facets that may impact adoption decisions, namely semantics, diffusion-related features pertaining to local and global influence among users, temporal attractiveness, and timeliness, as well as dynamic user preferences. We perform extensive experiments on the same real-world datasets, showing that IGNiteR outperforms the state-of-the-art deep-learning based news recommendation methods.For the indirect and audience-based recommendation setting, we focus on influence maximization with fairness, which aims to select k influential nodes to maximise the spread of information in a network, while ensuring that selected sensitive user attributes (e.g., gender location, origin, race, etc.) are fairly affected, i.e., are proportionally similar between the original network and the affected users. We propose two data-driven approaches: (a) fairness-based participant sampling (FPS) and (b) fairness as context (FAC), which are based on learning node representations (embeddings) to extract spread-related user features from diffusion cascades information, instead of the social connectivity, and in this way we can deal with very large graphs. The extracted features are then used in selecting influencers that maximize the influence spread, while also being fair with respect to the chosen sensitive attributes. In FPS, fairness and cascade length information are considered independently in the decision-making process, while FAC considers these information facets jointly and takes into account correlations between them. The proposed algorithms are generic and represent the first policy-driven solutions that can be applied to arbitrary sets of sensitive attributes at scale
Searching complex data on the structured Web
No full textNous assistons aujourd’hui à un développement continu et rapide du Web Structuré, dans lequel les documents (les pages Web) ne sont plus composés que du texte non structuré mais sont centrés sur les données, présentant des contenus structurés et des objets complexes. Ces pages Web sont générées le plus souvent de façon dynamique à partir d’une base de données accessible via des formulaires (Web caché), et sont organisées selon une structure régulière et prédéfinie. Les plates-formes de recherche actuelles ne permettent d’obtenir que des pages en utilisant des méthodes traditionnelles de recherche par des mots-clés, qui sont inadaptées pour interroger le Web structuré. En effet, la recherche par mots-clés est sémantiquement pauvre et ignore les liens structurels existant entre les différents contenus des objets complexes (ex. dans une page Web d’un site commercial, constituée d’une liste de livres, les entités élémentaires “titre” et “auteur” composant chaque “livre” sont présentées selon une disposition qui illustre leurs relations. De nouveaux moyens de recherche sur le Web sont donc nécessaires, pour permettre à l’utilisateur de cibler des données complexes avec une sémantique précise. L’objectif de cette thèse est de fournir des algorithmes efficaces pour l’extraction et la recherche des objets structurées (un livre, un concert de musique, etc.) de façon automatique, à l’aide de méthodes adaptées allant au-delà de la recherche par mots-clés. Nous avons proposé une approche d’interrogation du Web en deux étapes, qui permet à l’utilisateur de décrire le schéma des objets ciblés, de façon souple et précise. Les deux problématiques principales adressées sont : (1) la sélection de sources Web structurées les plus pertinentes pour un schéma fourni par l’utilisateur (c-à-d, contenant les objets, instances de ce schéma), et (2) la construction de wrappers (extracteurs) pour l’extraction des objets complexes ciblés à partir des sources sélectionnées, en exploitant la régularité des structures des pages et la sémantique des données. Notre approche est générique, dans le sens où elle nŠest pas spécifique à des sources ou des objets d’un domaine particulier. Elle a été implantée (système ObjectRunner) et testée sur des sources Web appartenant à des domaines variés. Les résultats obtenus montrent, en particulier, une pertinente élevée au niveau de la sélection de sources et un gain significatif au niveau de la qualité de l’extraction par rapport aux approches existantes.We are witnessing in recent years a steady growth of the so-called structured Web, in which documents (Web pages) are no longer quasi-textual, but are data-centric, presen-ting structured content, complex objects. Such schematized pages are often generated dynamically by means of formatting templates over a database, possibly using user input via forms (hidden Web). The current Web search platforms allow only to retrieve Web pages by traditional keyword search methods, which are not adapted to query the structured Web. Indeed, keyword search is semantically poor and ignores the existing structural links between various components of complex objects (e.g., in a commercial Web site page, providing book lists, the atomic entities “title” and “author” forming each “book” are displayed in a way that illustrates their relationship. New ways of searching the Web are thus required, in order to enable users to target complex data, with a clear semantics. The main aim of this thesis is to provide effective algorithms for extracting and retrieving structured objects (e.g., a book, a music concert, etc.) automatically, using adapted methods rather going beyond the keyword search ones. We propose a two-phase querying approach of the Web, which allows users to first describe the schema of the targeted objects, in a flexible, lightweight and precise manner. The two main problems we address are : (1) the selection of the most relevant structured Web sources with respect to the schema provided by the user (i.e., containing objects, instances of this schema), and (2) the construction of wrappers for extracting the targeted complex objects from the selected sources, leveraging both the regularity of the pages and the semantics of the data. Our approach is generic, in the sense that it can be applied to any domain and schema for complex objects. It has been implemented in the ObjectRunner system, and tested extensively. The experimental results show high source-selection relevance and significant improvements over existing techniques in terms of extraction precision
Query rewriting using views : a theoretical and practical perspective
No full textDans ce document, nous adressons le problème de la réécriture de requêtes avec des vues, en adoptant une perspective à la fois théorique et pratique. Dans le premier et principal chapitre, nous approchons le sujet de la recherche de toutes les reformulations minimales (sans atomes relationnels redondants) pour une requête relationnelle conjonctive, sous des contraintes d’intégrité qui incluent la relation entre les schémas source et cible. Nous présentons un nouvel algorithme, correct et complet, le Provenance-Aware Chase & Backchase, qui résout le problème des reformulations avec des performances significatives sur le plan pratique. Nous présentons sa caractérisation théorique détaillée, son implémentation optimisée et son évaluation, montrant des gains de performance jusqu’à deux ordres de grandeur par rapport à un SGBD commercial. Nous généralisons notre algorithme pour trouver directement des reformulations de coût minimum pour les fonctions de coût monotones, et montrons les gains de performance de cette adaptation. Avec notre algorithme, nous introduisons également un nouveau type de chase, la Provenance-Aware Chase, qui comporte son propre intérêt théorique, en tant que moyen de raisonnement sur l’interaction entre la provenance et les contraintes. Dans le deuxième chapitre, nous nous plaçons dans un contexte XML et nous revisitons le travail de Cautis, Deutsch and Onose sur problème de la réécriture de requêtes XPath par un seul niveau d’intersection de plusieurs vues. Nous étendons l’analyse de ce probleme en montrant ses connexions avec les problèmes de l’équivalence DAG-arbre et de la union-freeness d’un DAG. Nous raffinons un algorithme de réécriture proposé par Cautis, Deutsch and Onose pour obtenir une complexité polynomiale et améliorer sa complétude, et présentons un ensemble d’optimisations des procedures de réécriture, necessaires pour atteindre des performances pratiques. Nous fournissons une implementation complète comprenant ces optimizations ainsi que son evaluation experimentale extensive, montrant la performance et l’utilité de la technique polynomiale de réécriture.In this work, we address the problem of query rewriting using views, by adopting both a theoretical and a pragmatic perspective. In the first and main chapter, we approach the topic of finding all minimal (i.e. with no redundant relational atoms) conjunctive query reformulations for a relational conjunctive query, under constraints expressed as embedded dependencies, including the relationship between the source and the target schemas. We present a novel sound and complete algorithm, the Provenance-Aware Chase & Backchase, that solves the minimal reformulations problem with practically relevant performance. We provide a detailed theoretical characterization of our algorithm. We further present the optimized implementation and the experimental evaluation thereof, and exhibit natural scenarios yielding speed-ups of up to two orders of magnitude between the execution of a best view-based rewriting found by a commercial DBMS and that of a best rewriting found by our algorithm. We generalize the Provenance-Aware Chase & Backchase towards directly finding minimum-cost reformulations for monotonic cost functions, and show the performance improvements this adaptation further enables. With our algorithm, we introduce a novel chase flavour, the Provenance-Aware Chase, which is interesting on its own, as a means of reasoning about the interaction between provenance and constraints. In the second chapter, we move to an XML context and revisit the previous work of Cautis, Deutsch and Onose on the problem of finding XPath query rewritings with a single level of intersection of multiple views. We enrich the analysis of the rewriting problem by showing its links to the problems of DAG-tree equivalence and union-freeness. We refine the rule-based rewriting technique proposed by Cautis, Deutsch and Onose to ensure its polynomial complexity and improve its completeness, and present a range of optimizations on the rewriting procedures, necessary to achieve practical performance. We provide a complete implementation comprising these optimizations and a thorough experimental evaluation thereof, showing the performanceand utility of the polynomial rewriting technique
Distributed Access Control: A Privacy-conscious Approach
No full textInternational audienceWith more and more information being exchanged or published on the Web or in peer-to-peer, and with the significant growth in numbers of distributed, heterogeneous data sources, issues like access control and data privacy are becoming increasingly complex and difficult to manage. Very often, when dealing with sensitive information in such settings, the specification of access control policies and their enforcement are no longer handled by the actual data sources, and are (partially) delegated to third-parties. Besides practical reasons, this is the case when decisions regarding access depend on factors which overpass the scope and knowledge of some of the entities involved. More specifically, policies may depend on \emph{private} aspects concerning users (accessing data) or data owners. In this case, the only solution is to entrust some third-party authority with all the information needed to apply access policies. However, as the policies themselves depend on sensitive information, this outsourcing raises new privacy issues, that were not present in centralized environments. In particular, information leaks may occur during access control enforcement. In this paper, we consider these issues and, starting from non-conventional digital signatures, we take a first step towards an implementation solution for such settings where both data and access policies are distributed. Our approach involves rewriting user queries into forms which are authorized, and we illustrate this for both structured (relational) and semi-structured (XML) data and queries
Adaptive Methods for User-Centric Information Access Applications
No full textLorsque les internautes naviguent sur le Web, ils laissent de nombreuses traces que nous nous proposons d’exploiter pour améliorer les applications d'accès à l'information. Nous étudions des techniques centrées sur les utilisateurs qui tirent parti des nombreux types de rétroaction pour perfectionner les services offerts aux utilisateurs. Nous nous concentrons sur des applications telles que la recommandation et le marketing d’influence dans lesquelles les utilisateurs génèrent des signaux (clics, "j'aime", etc.) que nous intégrons dans nos algorithmes afin de fournir des services fortement contextualisés. La première partie de cette thèse est consacrée à une approche interactive de la recherche d'information sur les médias sociaux. Le problème consiste à récupérer un ensemble de k résultats dans un réseau social sous la contrainte que la requête peut être incomplète (par exemple, si le dernier terme est un préfixe). Chaque fois que l'utilisateur met à jour sa requête, le système met à jour l'ensemble des résultats de recherche en conséquence. Nous adoptons une interprétation de la pertinence de l'information qui tient compte du réseau, selon laquelle l'information produite par les utilisateurs proches de l'utilisateur faisant la requête est jugée plus pertinente. Ensuite, nous étudions une version générique de la maximisation de l'influence, dans laquelle nous voulons maximiser l'influence des campagnes d'information ou de marketing en sélectionnant de manière adaptative les utilisateurs initiant la propagation de l'information parmi un petit sous-ensemble de la population. Notre approche ne fait aucune hypothèse sur le modèle de diffusion sous-jacent ni même sur la structure du réseau de diffusion. Notre méthode a d'importantes applications dans le marketing d’influence qui vise à s’appuyer sur les influenceurs de réseaux sociaux pour promouvoir des produits ou des idées. Enfin, nous abordons le problème bien connu du démarrage à froid auquel sont confrontés les systèmes de recommandation par une approche adaptative. Si aucune information n’est disponible concernant l'appréciation d’un article, le système de recommandation doit recueillir des signaux (clics, etc.) afin d'estimer la valeur de l'article. Cependant, afin de minimiser les mauvaises recommandations faites aux utilisateurs, le système ne doit pas recueillir ces signaux de façon négligente. Nous introduisons un algorithme dynamique qui vise à alterner intelligemment les recommandations visant à accumuler de l'information et celles s'appuyant sur les données déjà recueillies.When users interact on modern Web systems, they let numerous footprints which we propose to exploit in order to develop better applications for information access. We study a family of techniques centered on users, which take advantage of the many types of feedback to adapt and improve services provided to users. We focus on applications like recommendation and influencer marketing in which users generate discrete feedback (e.g. clicks, "likes", reposts, etc.) that we incorporate in our algorithms in order to deliver strongly contextualized services. The first part of this dissertation is dedicated to an approach for as-you-type search on social media. The problem consists in retrieving a set of k search results in a social-aware environment under the constraint that the query may be incomplete (e.g., if the last term is a prefix). Every time the user updates his / her query, the system updates the set of search results accordingly. We adopt a "network-aware" interpretation of information relevance, by which information produced by users who are closer to the user issuing a request is considered more relevant. Then, we study a generic version of influence maximization, in which we want to maximize the influence of marketing or information campaigns by adaptively selecting "spread seeds" from a small subset of the population. Influencer marketing is a straightforward application of this, in which the focus of a campaign is placed on precise key individuals who are typically able to reach millions of consumers. This represents an unprecedented tool for online marketing that we propose to improve using an adaptive approach. Notably, our approach makes no assumptions on the underlying diffusion model and no diffusion network is needed. Finally, we propose to address the well-known cold start problem faced by recommender systems with an adaptive approach. If no information is available regarding the user appreciation of an item, the recommender system needs to gather feedback (e.g., clicks) so as to estimate the value of the item. However, in order to minimize "bad" recommendations, a well-designed system should not collect feedback carelessly. We introduce a dynamic algorithm that aims to intelligently achieve the balance between "bad" and "good" recommendations
Apprentissage et optimisation sur les graphes
No full textLes graphes, structures de données fondamentales, sont utilisés pour représenter des schémas complexes dans divers domaines. Les réseaux de neurones graphiques (GNN), un paradigme d'apprentissage profond conçu pour les données structurées en graphes, offrent une solution d'apprentissage profond efficace pour extraire des informations de ces relations complexes. Cette thèse explore l'application des GNNs pour relever deux défis clés : maximiser l'influence dans les réseaux sociaux et prédire les liens manquants dans les graphes de connaissances avec des données limitées. Avec des applications allant de l'optimisation des campagnes de santé publique et de la lutte contre la désinformation à la complétion des bases de connaissances, cette recherche répond au besoin de méthodes efficaces et robustes dans ces domaines. La maximisation de l'influence (IM) se concentre sur l'identification des nœuds les plus influents au sein d'un réseau social pour maximiser la diffusion d'informations ou d'idées. Cette thèse explore des méthodes pour résoudre le problème de l'IM, en particulier dans des scénarios réels avec des réseaux massifs et divers thèmes d'information. Nous construisons nos modèles en nous basant sur S2V-DQN, une approche qui combine les réseaux Deep Q-Networks (DQN) pour l'apprentissage par renforcement avec Structure2Vec (S2V) pour l'intégration de graphes. Nous développons d'abord notre modèle IM-GNN qui intègre des fonctionnalités GNN avancées telles que les mécanismes d'attention graphique et le codage positionnel, démontrant des performances concurrentielles par rapport aux méthodes existantes pour la maximisation de l'influence. Nous étendons ensuite nos recherches pour aborder la maximisation de l'influence sensible au sujet (TIM) où la diffusion de l'information est influencée par son contenu thématique, exigeant que les modèles considèrent non seulement la structure du réseau mais aussi les sujets des messages partagés. C'est là que les limites des méthodes traditionnelles d'IM deviennent apparentes. Notre modèle TIM-GNN gère efficacement cette complexité en incorporant un entraînement sensible au sujet et des méthodes probabilistes pour construire des graphes de diffusion sensibles au sujet. Pour résoudre les problèmes de latence des requêtes, nous introduisons TIM-GNNx, qui intègre des mécanismes d'attention croisée et une matrice Q précalculée. Nos expériences sur des ensembles de données réels démontrent que notre modèle atteint des performances concurrentielles en termes de diffusion d'influence par rapport aux méthodes de l'état de l'art tout en offrant des améliorations significatives en termes de latence et de robustesse. Notre modèle TIM-GNNx trouve un équilibre entre l'efficacité des requêtes et la maximisation de l'influence, ce qui le rend particulièrement adapté aux applications en temps réel. Dans le domaine des graphes de connaissances, nous explorons la prédiction de liens à peu d'exemples (FSLP), où l'objectif est de prédire les relations manquantes avec des exemples d'entraînement limités. Notre étude se concentre sur la possibilité d'intégrer une méthode de complétion de graphe de connaissances basée sur les chemins, PathCon, avec un cadre de méta-apprentissage MetaR pour résoudre les limites de ce dernier. Bien que nos recherches initiales n'aient pas apporté d'améliorations significatives ou de contributions scientifiques notables, elles ont fourni des informations pertinentes sur les défis de cette tâche et ont éclairé le développement d'un prototype pour le projet AIDA. Ce prototype démontre la valeur pratique de nos recherches et ouvre la voie à de futures explorations dans ce domaine. Dans l'ensemble, cette thèse apporte des solutions nouvelles et efficaces basées sur GNN pour la maximisation de l'influence et explore des pistes prometteuses pour la prédiction de liens à peu d'exemples dans les graphes de connaissances, repoussant les limites de ces domaines de recherche.Graphs are a fundamental data structure used to represent complex patterns in various domains. Graph Neural Networks (GNNs), a deep learning paradigm specifically designed for graph-structured data, offer a powerful deep learning solution for extracting insights from these intricate relationships. This thesis explores the application of GNNs to address two key challenges: maximizing influence in social networks and predicting missing links in knowledge graphs with limited data. With applications ranging from optimizing public health campaigns and combating misinformation to knowledge base completion, this research addresses the need for computationally efficient and robust methods in these domains. Influence maximization (IM) focuses on identifying the most influential nodes within a social network to maximize the spread of information or ideas. This thesis explores methods for tackling the IM problem, particularly in real-world scenarios with massive networks and diverse information themes. We build our models upon the S2V-DQN framework, a powerful approach that combines Deep Q-Networks (DQNs) for reinforcement learning with Structure2Vec (S2V) for graph embedding. We first develop our IM-GNN model that incorporates advanced GNN features such as graph attention mechanisms and positional encoding, demonstrating competitive performance against existing learning-based and non-learning based methods for influence maximization. We further extend our research to tackle Topic-aware Influence Maximization (TIM) where the spread of information is influenced by its thematic content, requiring models to consider not only network structure but also the topics of the messages being shared. This is where the limitations of traditional IM methods become apparent. Our TIM-GNN model effectively handles this complexity by incorporating topic-aware training and probabilistic methods for constructing topic-aware diffusion graphs. To address query latency concerns, we introduce TIM-GNNx, which integrates cross-attention mechanisms and a pre-computed Q-matrix. Our experiments on real-world datasets demonstrate that our proposed model achieves competitive performance in terms of influence spread compared to state-of-the-art methods while also offering significant improvements in query time latency and robustness to changes in the diffusion graph. Notably, our TIM-GNNx model strikes a balance between query efficiency and maximizing influence, making it particularly well-suited for real-time applications. In the realm of knowledge graphs, we explore Few-Shot Link Prediction (FSLP), where the goal is to predict missing relationships with limited training examples, which is crucial for addressing the long-tail phenomenon. In knowledge graphs, the long-tail phenomenon refers to the fact that a large number of entities (nodes) and relations (edges) have very few connections or occurrences. This results in a distribution where a small number of popular entities or relations have many connections, while the vast majority have very few. Our investigation focuses on the feasibility of integrating a path-based knowledge graph completion method PathCon with a meta-learning framework MetaR to address the limitations of the latter. While our initial investigations did not yield significant improvements or notable scientific contributions, they provided valuable insights into the challenges of this task and informed the development of a prototype, deployed as an API, for the AIDA project. This prototype demonstrates the practical value of our research and paves the way for future explorations in this area. Overall, this thesis contributes novel and efficient GNN-based solutions for influence maximization and explores promising directions for few-shot link prediction in knowledge graphs, pushing the boundaries of these research areas
Data management in social networks
No full textNous abordons dans cette thèse quelques-unes des questions soulevées par I'émergence d'applications sociales sur le Web, en se concentrant sur deux axes importants: l'efficacité de recherche sociale dans les applications Web et l'inférence de liens sociaux signés à partir des interactions entre les utilisateurs dans les applications Web collaboratives. Nous commençons par examiner la recherche sociale dans les applications de "tag- ging". Ce problème nécessite une adaptation importante des techniques existantes, qui n'utilisent pas des informations sociaux. Dans un contexte ou le réseau est importante, on peut (et on devrait) d'exploiter les liens sociaux, ce qui peut indiquer la façon dont les utilisateurs se rapportent au demandeur et combien de poids leurs actions de "tagging" devrait avoir dans le résultat. Nous proposons un algorithme qui a le potentiel d'évoluer avec la taille des applications actuelles, et on le valide par des expériences approfondies. Comme les applications de recherche sociale peut être considérée comme faisant partie d'une catégorie plus large des applications sensibles au contexte, nous étudions le problème de répondre aux requêtes à partir des vues, en se concentrant sur deux sous-problèmes importants. En premier, la manipulation des éventuelles différences de contexte entre les différents points de vue et une requête d'entrée conduit à des résultats avec des score incertains, valables pour le nouveau contexte. En conséquence, les algorithmes top-k actuels ne sont plus directement applicables et doivent être adaptés aux telle incertitudes dans les scores des objets. Deuxièmement, les techniques adaptées de sélection de vue sont nécessaires, qui peuvent s’appuyer sur les descriptions des requêtes et des statistiques sur leurs résultats. Enfin, nous présentons une approche pour déduire un réseau signé (un "réseau de confiance") à partir de contenu généré dans Wikipedia. Nous étudions les mécanismes pour deduire des relations entre les contributeurs Wikipédia - sous forme de liens dirigés signés - en fonction de leurs interactions. Notre étude met en lumière un réseau qui est capturée par l’interaction sociale. Nous examinons si ce réseau entre contributeurs Wikipedia représente en effet une configuration plausible des liens signes, par l’étude de ses propriétés globaux et locaux du reseau, et en évaluant son impact sur le classement des articles de Wikipedia.We address in this thesis some of the issues raised by the emergence of social applications on the Web, focusing on two important directions: efficient social search inonline applications and the inference of signed social links from interactions between users in collaborative Web applications. We start by considering social search in tagging (or bookmarking) applications. This problem requires a significant departure from existing, socially agnostic techniques. In a network-aware context, one can (and should) exploit the social links, which can indicate how users relate to the seeker and how much weight their tagging actions should have in the result build-up. We propose an algorithm that has the potential to scale to current applications, and validate it via extensive experiments. As social search applications can be thought of as part of a wider class of context-aware applications, we consider context-aware query optimization based on views, focusing on two important sub-problems. First, handling the possible differences in context between the various views and an input query leads to view results having uncertain scores, i.e., score ranges valid for the new context. As a consequence, current top-k algorithms are no longer directly applicable and need to be adapted to handle such uncertainty in object scores. Second, adapted view selection techniques are needed, which can leverage both the descriptions of queries and statistics over their results. Finally, we present an approach for inferring a signed network (a "web of trust")from user-generated content in Wikipedia. We investigate mechanisms by which relationships between Wikipedia contributors - in the form of signed directed links - can be inferred based their interactions. Our study sheds light into principles underlying a signed network that is captured by social interaction. We investigate whether this network over Wikipedia contributors represents indeed a plausible configuration of link signs, by studying its global and local network properties, and at an application level, by assessing its impact in the classification of Wikipedia articles.javascript:nouvelleZone('abstract');_ajtAbstract('abstract')
Distributed Access Control: A Privacy-conscious Approach
Get PDFInternational audienceWith more and more information being exchanged or published on the Web or in peer-to-peer, and with the significant growth in numbers of distributed, heterogeneous data sources, issues like access control and data privacy are becoming increasingly complex and difficult to manage. Very often, when dealing with sensitive information in such settings, the specification of access control policies and their enforcement are no longer handled by the actual data sources, and are (partially) delegated to third-parties. Besides practical reasons, this is the case when decisions regarding access depend on factors which overpass the scope and knowledge of some of the entities involved. More specifically, policies may depend on \emph{private} aspects concerning users (accessing data) or data owners. In this case, the only solution is to entrust some third-party authority with all the information needed to apply access policies. However, as the policies themselves depend on sensitive information, this outsourcing raises new privacy issues, that were not present in centralized environments. In particular, information leaks may occur during access control enforcement. In this paper, we consider these issues and, starting from non-conventional digital signatures, we take a first step towards an implementation solution for such settings where both data and access policies are distributed. Our approach involves rewriting user queries into forms which are authorized, and we illustrate this for both structured (relational) and semi-structured (XML) data and queries
Apprentissage séquentiel pour la diffusion d'information
No full textMotivés par les scénarios de diffusion de l'information et de publicité dans le les réseaux sociaux, nous étudions un problème de maximisation de l'influence (MI) dans lequel on suppose que l'on en sait peu sur le réseau de diffusion ou sur le modèle qui détermine comment l'information peut se propager.Dans un tel environnement incertain, on peut se concentrer sur des campagnes de diffusion à plusieurs tours, avec l'objectif de maximiser le nombre d'utilisateurs distincts qui sont influencés ou activés, à partir d'une base de nœuds influents.Au cours d'une campagne, les graines de propagation sont sélectionnées séquentiellement lors de tours consécutifs, et les commentaires sont collectés sous la forme des nœuds activés à chaque tour.L'impact (récompense) d'un tour est alors quantifié par le nombre de nœuds nouvellement activés. En général, il faut maximiser la propagation totale de la campagne, comme la somme des récompenses des tours.Nous considérons deux sous-classes de d'IM, emph{cimp} (CIMP) et emph{ecimp} (ECIMP), où (i) la récompense d'un tour d'une campagne en cours consiste uniquement en de nouvelles activations (non observées lors des tours précédents de cette campagne),(ii) le contexte du tour et les données historiques des tours précédents peuvent être exploités pour apprendre la meilleure politique, et(iii) ECIMP est CIMP répété plusieurs fois, ce qui permet d'apprendre également des campagnes précédentes.Ce problème est directement motivé par les scénarios du monde réel de la diffusion de l'information dans le marketing d'influence, où (i) seule la première / unique activation d'un utilisateur cible présente un intérêt (et cette activation persistera comme une activation acquise, latente, tout au long de la campagne).(ii) de précieuses informations secondaires sont disponibles pour l'agent d'apprentissageDans ce contexte, une approche d'exploration-exploitation pourrait être utilisée pour apprendre les principaux paramètres de diffusion sous-jacents, tout en exécutant les campagnes.Pour CIMP, nous décrivons et comparons deux méthodes de bandits à bras multiples contextuels, avec des limites supérieures de confiance sur le potentiel restant des influenceurs, l'une utilisant un modèle linéaire généralisé et l'estimateur de Good-Turing pour le potentiel restant, et l'autre adaptant directement l'algorithme LinUCB à notre cadre.Pour ECIMP, nous proposons l'algorithmelgtlsvi qui implémente le principe d'optimisme face à l'incertitude pour l'apprentissage par renforcement, avec approximation linéaire.L'agent d'apprentissage estime pour chaque nœud de départ son potentiel restant avec un estimateur de Good-Turing, modifié par une fonction Q estimée. Nous montrons qu'ils surpassent les performances des méthodes de base utilisant les idées les plus récentes, sur des données synthétiques et réelles, tout en présentant un comportement différent et complémentaire, selon les scénarios dans lesquels ils sont déployés.Motivated by scenarios of information diffusion and advertising in social media, we study an emph{influence maximization} (IM) problem in which little is assumed to be known about the diffusion network or about the model that determines how information may propagate. In such a highly uncertain environment, one can focus on emph{multi-round diffusion campaigns}, with the objective to maximize the number of distinct users that are influenced or activated, starting from a known base of few influential nodes.During a campaign, spread seeds are selected sequentially at consecutive rounds, and feedback is collected in the form of the activated nodes at each round.A round's impact (reward) is then quantified as the number of emph{newly activated nodes}.Overall, one must maximize the campaign's total spread, as the sum of rounds' rewards.We consider two sub-classes of IM, emph{cimp} (CIMP) and emph{ecimp} (ECIMP), where (i) the reward of a given round of an ongoing campaign consists of only the extit{new activations} (not observed at previous rounds within that campaign), (ii) the round's context and the historical data from previous rounds can be exploited to learn the best policy, and (iii) ECIMP is CIMP repeated multiple times, offering the possibility of learning from previous campaigns as well.This problem is directly motivated by the real-world scenarios of information diffusion in emph{influencer marketing}, where (i) only a target user's emph{first} / unique activation is of interest (and this activation will emph{persist} as an acquired, latent one throughout the campaign), and (ii) valuable side-information is available to the learning agent.In this setting, an explore-exploit approach could be used to learn the key underlying diffusion parameters, while running the campaigns.For CIMP, we describe and compare two methods of emph{contextual multi-armed bandits}, with emph{upper-confidence bounds} on the remaining potential of influencers, one using a generalized linear model and the Good-Turing estimator for remaining potential (glmucb), and another one that directly adapts the LinUCB algorithm to our setting (linucb).For ECIMP, we propose the algorithmlgtlsvi, which implements the extit{optimism in the face of uncertainty} principle for episodic reinforcement learning with linear approximation. The learning agent estimates for each seed node its remaining potential with a Good-Turing estimator, modified by an estimated Q-function.We show that they outperform baseline methods using state-of-the-art ideas, on synthetic and real-world data, while at the same time exhibiting different and complementary behavior, depending on the scenarios in which they are deployed
- …
