1,721,019 research outputs found
Agrégation spatio-temporelle d’événements : le cas de la crise syrienne (Paper presented at ECTQG 2013)
No full textIDENTIFICATION OF INTERNATIONAL MEDIA EVENTS BY SPATIAL AND TEMPORAL AGGREGATION OF NEWSPAPERS RSS FLOWS Application to the case of the Syrian Civil War between May 2011 and December 2012 GIRAUD Timothée, CNRS – UMS 2414 RIATE, [email protected] GRASLAND Claude, Université Paris Diderot – UMR 8504 Géographie-cités,[email protected] LAMARCHE-PERRIN Robin, Université de Grenoble – UMR 5217 LIG, [email protected] DEMAZEAU Yves, CNRS – UMR 5217 LIG, Yves.Dema..
Correlations in heterogeneous information networks : prediction and modelling of links from metapaths
No full textDe nombreuses entités possiblement de natures différentes sont reliées par des liens pouvant également être de natures différentes. De telles données peuvent être représentées par un graphe d’information hétérogène (heterogeneous information network, HIN). De plus, il existe souvent des corrélations entre entités ou événements de la vie réelle. Une fois ces derniers représentés par des abstractions appropriées telles que les HIN, les corrélations peuvent dès lors se retrouver dans ces graphes particuliers. Motivé par ces considérations, cette thèse s’intéresse aux effets des possibles corrélations entre les liens d’un HIN sur sa structure. Ce présent travail tente de répondre à des questions telles que : y a-t-il des corrélations entre les liens de différents types ? Si oui, est-il possible de les quantifier ? Que signifient-elles ? Est-ce que ces corrélations peuvent servir à prédire l’apparition de liens ? À modéliser des dynamiques de co-évolution ? Les exemples étudiés peuvent être divisés en deux catégories. Premièrement, l’utilisation des corrélations pour la prédiction du poids des liens est étudiée. Il est montré que les corrélations entre les liens, et plus particulièrement entre les chemins, peuvent être utilisées pour récupérer et prédire le poids d’autres liens, d’un type spécifié. Deuxièmement, une dynamique de poids de liens est considérée. Il est montré que la co-évolution de liens peut servir, par exemple, à définir un modèle d’attention entre individus et sujets. Les résultats préliminaires sont en accord avec d’autres présents dans la littérature, principalement relatifs aux modèles de dynamiques d’opinions. Globalement, ce travail illustre l’importance des corrélations entre les liens d’un HIN. En outre, il soutient le fait général que différents types de nœuds et liens abondent dans la nature et qu’il peut être important et instructif de prendre en compte cette diversité afin de comprendre l’organisation et le fonctionnement d’un système.Many entities, possibly of different natures, are linked by physical or virtual links, that may also be of different natures. Such data can be represented by a heterogeneous information network (HIN). In addition, there are often correlations between real-life entities or events. Once represented by suitable abstractions (such as HIN), these correlations can therefore be found in the HIN. Motivated by these considerations, this thesis investigates the effects of possible correlations between the links of an HIN on its structure. This present work aims at answering questions such as: are there indeed correlations between different types of links? If so, is it possible to quantify them? What do they mean? How can they be interpreted? Can these correlations be used to predict the occurrence of links? To model co-evolution dynamics? The examples studied can be divided into two categories. First, the use of correlations for the prediction of the links’ weight is studied. It is shown that correlations between links, and more specifically between paths, can be used to recover and, to some extent, predict the weight of other links of a specified type. Second, a link weight dynamics is considered. It is shown that link co-evolution can be used, for example, to define a model of attention between individuals and subjects. The preliminary results are in agreement with others in the literature, mainly related to models of opinion dynamics. Overall, this work illustrates the importance of correlations between the links of an HIN. In addition, it supports the general fact that different types of nodes and links abound in nature and that it could be important and instructive to take this diversity into account in order to understand the organization and functioning of a system
Anomaly detection in link streams : combining structural and temporal features
No full textUn flot de liens est un ensemble de liens {(t,u,v)} dans lequel un triplet (t,u,v) modélise l'interaction entre deux entités u et v à l'instant t. Dans de nombreuses situations, les données résultent de la mesure des interactions entre plusieurs millions d'entités au cours du temps et peuvent ainsi être étudiées grâce au formalisme des flots de liens. C'est le cas des appels téléphoniques, des échanges d'e-mails, des transferts d'argent, des contacts entre individus, du trafic IP, des achats en ligne, et bien d'autres encore. L'objectif de cette thèse est la détection d'ensembles de liens anormaux dans un flot de liens. Dans une première partie, nous concevons une méthode qui construit différents contextes, un contexte étant un ensemble de caractéristiques décrivant les circonstances d'une anomalie. Ces contextes nous permettent de trouver des comportements inattendus pertinents, selon plusieurs dimensions et perspectives. Dans une seconde partie, nous concevons une méthode permettant de détecter des anomalies dans des distributions hétérogènes dont le comportement est constant au cours du temps, en comparant une séquence de distributions hétérogènes similaires. Nous appliquons nos outils méthodologiques à des interactions temporelles provenant de retweets sur Twitter et de trafic IP du groupe MAWI.A link stream is a set of links {(t, u, v)} in which a triplet (t, u, v) models the interaction between two entities u and v at time t. In many situations, data result from the measurement of interactions between several million of entities over time and can thus be studied through the link stream's formalism. This is the case, for instance, of phone calls, email exchanges, money transfers, contacts between individuals, IP traffic, online shopping, and many more. The goal of this thesis is the detection of sets of abnormal links in a link stream. In a first part, we design a method that constructs different contexts, a context being a set of characteristics describing the circumstances of an anomaly. These contexts allow us to find unexpected behaviors that are relevant, according to several dimensions and perspectives. In a second part, we design a method to detect anomalies in heterogeneous distributions whose behavior is constant over time, by comparing a sequence of similar heterogeneous distributions. We apply our methodological tools to temporal interactions coming from retweets of Twitter and IP traffic of MAWI group
Macroscopic Analysis of Large-scale Systems : Epistemic Emergence and Spatiotemporal Aggregation
No full textL'analyse des systèmes de grande taille est confrontée à des difficultés d'ordre syntaxique et sémantique : comment observer un million d'entités distribuées et asynchrones ? Comment interpréter le désordre résultant de l'observation microscopique de ces entités ? Comment produire et manipuler des abstractions pertinentes pour l'analyse macroscopique des systèmes ? Face à l'échec de l'approche analytique, le concept d'émergence épistémique - relatif à la nature de la connaissance - nous permet de définir une stratégie d'analyse alternative, motivée par le constat suivant : l'activité scientifique repose sur des processus d'abstraction fournissant des éléments de description macroscopique pour aborder la complexité des systèmes. Cette thèse s'intéresse plus particulièrement à la production d'abstractions spatiales et temporelles par agrégation de données. Afin d'engendrer des représentations exploitables lors du passage à l'échelle, il apparaît nécessaire de contrôler deux aspects essentiels du processus d'abstraction. Premièrement, la complexité et le contenu informationnel des représentations macroscopiques doivent être conjointement optimisés afin de préserver les détails pertinents pour l'observateur, tout en minimisant le coût de l'analyse. Nous proposons des mesures de qualité (critères internes) permettant d'évaluer, de comparer et de sélectionner les représentations en fonction du contexte et des objectifs de l'analyse. Deuxièmement, afin de conserver leur pouvoir explicatif, les abstractions engendrées doivent être cohérentes avec les connaissances mobilisées par l'observateur lors de l'analyse. Nous proposons d'utiliser les propriétés organisationnelles, structurelles et topologiques du système (critères externes) pour contraindre le processus d'agrégation et pour engendrer des représentations viables sur les plans syntaxique et sémantique. Par conséquent, l'automatisation du processus d'agrégation nécessite de résoudre un problème d'optimisation sous contraintes. Nous proposons dans cette thèse un algorithme de résolution générique, s'adaptant aux critères formulés par l'observateur. De plus, nous montrons que la complexité de ce problème d'optimisation dépend directement de ces critères. L'approche macroscopique défendue dans cette thèse est évaluée sur deux classes de systèmes. Premièrement, le processus d'agrégation est appliqué à la visualisation d'applications parallèles de grande taille pour l'analyse de performance. Il permet de détecter les anomalies présentes à plusieurs niveaux de granularité dans les traces d'exécution et d'expliquer ces anomalies à partir des propriétés syntaxiques du système. Deuxièmement, le processus est appliqué à l'agrégation de données médiatiques pour l'analyse des relations internationales. L'agrégation géographique et temporelle de l'attention médiatique permet de définir des évènements macroscopiques pertinents sur le plan sémantique pour l'analyse du système international. Pour autant, nous pensons que l'approche et les outils présentés dans cette thèse peuvent être généralisés à de nombreux autres domaines d'application.The analysis of large-scale systems faces syntactic and semantic difficulties: How to observe millions of distributed and asynchronous entities? How to interpret the disorder that results from the microscopic observation of such entities? How to produce and handle relevant abstractions for the systems' macroscopic analysis? Faced with the failure of the analytic approach, the concept of epistemic emergence - related to the nature of knowledge - allows us to define an alternative strategy. This strategy is motivated by the observation that scientific activity relies on abstraction processes that provide macroscopic descriptions to broach the systems' complexity. This thesis is more specifically interested in the production of spatial and temporal abstractions through data aggregation. In order to generate scalable representations, the control of two essential aspects of the aggregation process is necessary. Firstly, the complexity and the information content of macroscopic representations should be jointly optimized in order to preserve the relevant details for the observer, while minimizing the cost of the analysis. We propose several measures of quality (internal criteria) to evaluate, compare and select the representations depending on the context and the objectives of the analysis. Secondly, in order to preserve their explanatory power, the generated abstractions should be consistent with the background knowledge exploited by the observer for the analysis. We propose to exploit the systems' organisational, structural and topological properties (external criteria) to constrain the aggregation process and to generate syntactically and semantically consistent representations. Consequently, the automation of the aggregation process requires solving a constrained optimization problem. We propose a generic algorithm that adapts to the criteria expressed by the observer. Furthermore, we show that the complexity of this optimization problem directly depend on these criteria. The macroscopic approach supported by this thesis is evaluated on two classes of systems. Firstly, the aggregation process is applied to the visualisation of large-scale distributed applications for performance analysis. It allows the detection of anomalies at several scales in the execution traces and the explanation of these anomalies according to the system syntactic properties. Secondly, the process is applied to the aggregation of news for the analysis of international relations. The geographical and temporal aggregation of media attention allows the definition of semantically consistent macroscopic events for the analysis of the international system. Furthermore, we believe that the approach and the tools presented in this thesis can be extended to a wider class of application domains
An Information-theoretic Framework for the Lossy Compression of Link Streams
Get PDFInternational audienceGraph compression is a data analysis technique that consists in the replacement of parts of a graph by more general structural patterns in order to reduce its description length. It notably provides interesting exploration tools for the study of real, large-scale, and complex graphs which cannot be grasped at first glance. This article proposes a framework for the compression of temporal graphs, that is for the compression of graphs that evolve with time. This framework first builds on a simple and limited scheme, exploiting structural equivalence for the lossless compression of static graphs, then generalises it to the lossy compression of link streams, a recent formalism for the study of temporal graphs. Such generalisation relies on the natural extension of (bidimensional) relational data by the addition of a third temporal dimension. Moreover, we introduce an information-theoretic measure to quantify and to control the information that is lost during compression, as well as an algebraic characterisation of the space of possible compression patterns to enhance the expressiveness of the initial compression scheme. These contributions lead to the definition of a combinatorial optimisation problem, that is the Lossy Multistream Compression Problem, for which we provide an exact algorithm
Des collaborations possibles entre philosophie et intelligence artificielle
No full textCe mémoire s'intéresse aux collaborations possibles entre Intelligence Artificielle et philosophie. Il montre que les deux disciplines peuvent partager des objets, des théories et des résultats pour apprendre l'une de l'autre. La stratégie de ce mémoire consiste à expliciter des relations épistémologiques entre les problématiques propres aux deux disciplines ("IA faible" et "IA forte"), afin de définir des modes de collaboration sur le plan disciplinaire. La deuxième partie de ce mémoire présente les travaux de philosophes et de spécialistes de l'IA, depuis les débuts de l'Intelligence Artificielle jusqu'aux années 80. Elle expose les démarches collaboratives exploitées par ces chercheurs, de manière implicite ou explicite. La troisième partie présente des travaux où la philosophie sert de socle conceptuel à l'Intelligence Artificielle, notamment en ce qui concerne la simulation de phénomènes émergents. La quatrième partie réalise un renversement des relations classiques entre les deux disciplines. C'est au tour de l'Intelligence Artificielle de se mettre au service de la philosophie, en formulant de nouvelles hypothèses de recherche ou en testant les théories philosophiques à partir de cas concrets. Ce mémoire, enfin, espère œuvrer pour le rapprochement des deux disciplines et ainsi encourager philosophes et spécialistes de l'IA à collaborer sur les sujets qui leurs sont chers
Le test de Turing pour évaluer les théories de l'esprit
No full textCe mémoire propose une méthode pour confronter les théories de l'esprit répondant à la problématique générale : quelles machines ont un esprit, et pourquoi ? Dans notre approche, les réponses extensives engendrées par les théories sont utilisées pour délimiter leurs points de désaccords et identifier des cas de divergence cruciaux. L'évaluation et le choix d'une théorie est ainsi éclairé par une analyse focalisée sur de tels cas particuliers. Voici comment est présentée notre approche. La partie 2 introduit une méthode empirique assez classique pour définir la notion d'esprit de manière comportementale. Il s'agit du test de Turing. La partie 3 propose d'évaluer ce test en le confrontant à une seconde définition de la notion d'esprit : le sens fonctionnel. Les divergences entre ces deux définitions permettent de révéler des contradictions et des incohérences entre deux théories de l'esprit. Le choix entre l'une ou l'autre et les raisons d'un tel choix sont obtenus à partir de l'étude de ces cas particuliers. La partie 4 applique cette méthode d'évaluation aux débats historiques qui ont opposé au XXe siècle trois théories fonctionnalistes. Il s'agit du cognitivisme, du connexionnisme et du modèle énactif de l'esprit. Les évaluations passées de ces théories sont reformulées et clarifiées à l'aide de l'approche développée dans ce mémoire
Conceptualisation de l'émergence : dynamiques microscopiques et analyse macroscopique des SMA
No full textNational audienceLa décentralisation et l'asynchronisme croissant des SMA posent un problème de fond à l'IA : comment réaliser une analyse macroscopique de systèmes con\\c cus au niveau microscopique ? Cet article propose de répondre à ce problème en élaborant un concept d'émergence adéquat. Les origines philosophiques de la notion d'émergence permettent de formuler les exigences d'une telle conceptualisation. L'idée principale tient sur le fait que les phénomènes émergents ne doivent pas être considérés comme une propriété des SMA, mais comme une propriété de la méthode d'observation utilisée. Nous parlons d'émergence épistémique. Deux exigences concernant l'approche des SMA sont formulées à partir de ce concept. Nous présentons une méthode d'observation macroscopique compatible avec ces exigences et répondant ainsi à la problématique de cet article
Analyse macroscopique des grands systèmes : émergence épistémique et agrégation spatio-temporelle
No full textThe analysis of large-scale systems faces syntactic and semantic difficulties: How to observe millions of distributed and asynchronous entities? How to interpret the disorder that results from the microscopic observation of such entities? How to produce and handle relevant abstractions for the systems' macroscopic analysis? Faced with the failure of the analytic approach, the concept of epistemic emergence - related to the nature of knowledge - allows us to define an alternative strategy. This strategy is motivated by the observation that scientific activity relies on abstraction processes that provide macroscopic descriptions to broach the systems' complexity. This thesis is more specifically interested in the production of spatial and temporal abstractions through data aggregation. In order to generate scalable representations, the control of two essential aspects of the aggregation process is necessary. Firstly, the complexity and the information content of macroscopic representations should be jointly optimized in order to preserve the relevant details for the observer, while minimizing the cost of the analysis. We propose several measures of quality (internal criteria) to evaluate, compare and select the representations depending on the context and the objectives of the analysis. Secondly, in order to preserve their explanatory power, the generated abstractions should be consistent with the background knowledge exploited by the observer for the analysis. We propose to exploit the systems' organisational, structural and topological properties (external criteria) to constrain the aggregation process and to generate syntactically and semantically consistent representations. Consequently, the automation of the aggregation process requires solving a constrained optimization problem. We propose a generic algorithm that adapts to the criteria expressed by the observer. Furthermore, we show that the complexity of this optimization problem directly depend on these criteria. The macroscopic approach supported by this thesis is evaluated on two classes of systems. Firstly, the aggregation process is applied to the visualisation of large-scale distributed applications for performance analysis. It allows the detection of anomalies at several scales in the execution traces and the explanation of these anomalies according to the system syntactic properties. Secondly, the process is applied to the aggregation of news for the analysis of international relations. The geographical and temporal aggregation of media attention allows the definition of semantically consistent macroscopic events for the analysis of the international system. Furthermore, we believe that the approach and the tools presented in this thesis can be extended to a wider class of application domains.L'analyse des systèmes de grande taille est confrontée à des difficultés d'ordre syntaxique et sémantique : comment observer un million d'entités distribuées et asynchrones ? Comment interpréter le désordre résultant de l'observation microscopique de ces entités ? Comment produire et manipuler des abstractions pertinentes pour l'analyse macroscopique des systèmes ? Face à l'échec de l'approche analytique, le concept d'émergence épistémique - relatif à la nature de la connaissance - nous permet de définir une stratégie d'analyse alternative, motivée par le constat suivant : l'activité scientifique repose sur des processus d'abstraction fournissant des éléments de description macroscopique pour aborder la complexité des systèmes. Cette thèse s'intéresse plus particulièrement à la production d'abstractions spatiales et temporelles par agrégation de données. Afin d'engendrer des représentations exploitables lors du passage à l'échelle, il apparaît nécessaire de contrôler deux aspects essentiels du processus d'abstraction. Premièrement, la complexité et le contenu informationnel des représentations macroscopiques doivent être conjointement optimisés afin de préserver les détails pertinents pour l'observateur, tout en minimisant le coût de l'analyse. Nous proposons des mesures de qualité (critères internes) permettant d'évaluer, de comparer et de sélectionner les représentations en fonction du contexte et des objectifs de l'analyse. Deuxièmement, afin de conserver leur pouvoir explicatif, les abstractions engendrées doivent être cohérentes avec les connaissances mobilisées par l'observateur lors de l'analyse. Nous proposons d'utiliser les propriétés organisationnelles, structurelles et topologiques du système (critères externes) pour contraindre le processus d'agrégation et pour engendrer des représentations viables sur les plans syntaxique et sémantique. Par conséquent, l'automatisation du processus d'agrégation nécessite de résoudre un problème d'optimisation sous contraintes. Nous proposons dans cette thèse un algorithme de résolution générique, s'adaptant aux critères formulés par l'observateur. De plus, nous montrons que la complexité de ce problème d'optimisation dépend directement de ces critères. L'approche macroscopique défendue dans cette thèse est évaluée sur deux classes de systèmes. Premièrement, le processus d'agrégation est appliqué à la visualisation d'applications parallèles de grande taille pour l'analyse de performance. Il permet de détecter les anomalies présentes à plusieurs niveaux de granularité dans les traces d'exécution et d'expliquer ces anomalies à partir des propriétés syntaxiques du système. Deuxièmement, le processus est appliqué à l'agrégation de données médiatiques pour l'analyse des relations internationales. L'agrégation géographique et temporelle de l'attention médiatique permet de définir des évènements macroscopiques pertinents sur le plan sémantique pour l'analyse du système international. Pour autant, nous pensons que l'approche et les outils présentés dans cette thèse peuvent être généralisés à de nombreux autres domaines d'application
Analyse macroscopique des grands systèmes : émergence épistémique et agrégation spatio-temporelle
No full textThe analysis of large-scale systems faces syntactic and semantic difficulties: How to observe millions of distributed and asynchronous entities? How to interpret the disorder that results from the microscopic observation of such entities? How to produce and handle relevant abstractions for the systems' macroscopic analysis? Faced with the failure of the analytic approach, the concept of epistemic emergence - related to the nature of knowledge - allows us to define an alternative strategy. This strategy is motivated by the observation that scientific activity relies on abstraction processes that provide macroscopic descriptions to broach the systems' complexity. This thesis is more specifically interested in the production of spatial and temporal abstractions through data aggregation. In order to generate scalable representations, the control of two essential aspects of the aggregation process is necessary. Firstly, the complexity and the information content of macroscopic representations should be jointly optimized in order to preserve the relevant details for the observer, while minimizing the cost of the analysis. We propose several measures of quality (internal criteria) to evaluate, compare and select the representations depending on the context and the objectives of the analysis. Secondly, in order to preserve their explanatory power, the generated abstractions should be consistent with the background knowledge exploited by the observer for the analysis. We propose to exploit the systems' organisational, structural and topological properties (external criteria) to constrain the aggregation process and to generate syntactically and semantically consistent representations. Consequently, the automation of the aggregation process requires solving a constrained optimization problem. We propose a generic algorithm that adapts to the criteria expressed by the observer. Furthermore, we show that the complexity of this optimization problem directly depend on these criteria. The macroscopic approach supported by this thesis is evaluated on two classes of systems. Firstly, the aggregation process is applied to the visualisation of large-scale distributed applications for performance analysis. It allows the detection of anomalies at several scales in the execution traces and the explanation of these anomalies according to the system syntactic properties. Secondly, the process is applied to the aggregation of news for the analysis of international relations. The geographical and temporal aggregation of media attention allows the definition of semantically consistent macroscopic events for the analysis of the international system. Furthermore, we believe that the approach and the tools presented in this thesis can be extended to a wider class of application domains.L'analyse des systèmes de grande taille est confrontée à des difficultés d'ordre syntaxique et sémantique : comment observer un million d'entités distribuées et asynchrones ? Comment interpréter le désordre résultant de l'observation microscopique de ces entités ? Comment produire et manipuler des abstractions pertinentes pour l'analyse macroscopique des systèmes ? Face à l'échec de l'approche analytique, le concept d'émergence épistémique - relatif à la nature de la connaissance - nous permet de définir une stratégie d'analyse alternative, motivée par le constat suivant : l'activité scientifique repose sur des processus d'abstraction fournissant des éléments de description macroscopique pour aborder la complexité des systèmes. Cette thèse s'intéresse plus particulièrement à la production d'abstractions spatiales et temporelles par agrégation de données. Afin d'engendrer des représentations exploitables lors du passage à l'échelle, il apparaît nécessaire de contrôler deux aspects essentiels du processus d'abstraction. Premièrement, la complexité et le contenu informationnel des représentations macroscopiques doivent être conjointement optimisés afin de préserver les détails pertinents pour l'observateur, tout en minimisant le coût de l'analyse. Nous proposons des mesures de qualité (critères internes) permettant d'évaluer, de comparer et de sélectionner les représentations en fonction du contexte et des objectifs de l'analyse. Deuxièmement, afin de conserver leur pouvoir explicatif, les abstractions engendrées doivent être cohérentes avec les connaissances mobilisées par l'observateur lors de l'analyse. Nous proposons d'utiliser les propriétés organisationnelles, structurelles et topologiques du système (critères externes) pour contraindre le processus d'agrégation et pour engendrer des représentations viables sur les plans syntaxique et sémantique. Par conséquent, l'automatisation du processus d'agrégation nécessite de résoudre un problème d'optimisation sous contraintes. Nous proposons dans cette thèse un algorithme de résolution générique, s'adaptant aux critères formulés par l'observateur. De plus, nous montrons que la complexité de ce problème d'optimisation dépend directement de ces critères. L'approche macroscopique défendue dans cette thèse est évaluée sur deux classes de systèmes. Premièrement, le processus d'agrégation est appliqué à la visualisation d'applications parallèles de grande taille pour l'analyse de performance. Il permet de détecter les anomalies présentes à plusieurs niveaux de granularité dans les traces d'exécution et d'expliquer ces anomalies à partir des propriétés syntaxiques du système. Deuxièmement, le processus est appliqué à l'agrégation de données médiatiques pour l'analyse des relations internationales. L'agrégation géographique et temporelle de l'attention médiatique permet de définir des évènements macroscopiques pertinents sur le plan sémantique pour l'analyse du système international. Pour autant, nous pensons que l'approche et les outils présentés dans cette thèse peuvent être généralisés à de nombreux autres domaines d'application
- …
