Search

This document provides concrete syntax illustrated with ex-amples for the Porgy’s strategy language and the language for rulealgorithm and conditions. Porgy is a visual, interactive modelling tool based on port graph rewriting. In Porgy, system states are represented by port graphs, and the dynamic evolution of the system is defined via port graph rewrite rules. Strategy expressions are used to control the application of rules, more precisely, strategy expressions indicate both the rule to be applied at each step in a rewriting derivation, and the position in the graph where the rule is applied (the latter is done via focusing constructs). Some of the strategy constructs are strongly inspired from term rewriting languages such as Elan [Borovansk´yBorovansk´y et al., 1998], Stratego [Visser, 2001] and Tom [Balland et al., 2007]. Focusing operators are not present in term rewriting languages (although they rely on implicit traversal strategies). The direct management of positions in strategy expressions, via the distinguished position and banned subgraphs in the target graph and in a located port graph rewrite rule are original features of the language and are managed using positioning constructs. This document describes the concrete syntax of strategy expressions, explains how the different kinds of constructs are used, and provides examples.

In this thesis, we present a collection of network generation and information diffusion models expressed using a specific formalism called strategic located graph rewriting, as well as a novel network layout algorithm to show the result of information diffusion in large social networks. Graphs are extremely versatile mathematical objects which can be used to represent a wide variety of high-level systems. They can be transformed in multiple ways (e.g., creating new elements, merging or altering existing ones), but such modifications must be controlled to avoid unwanted operations. To ensure this point, we use a specific formalism called strategic graph rewriting. In this work, a graph rewriting system operates on a single graph, which can then be transformed according to some transformation rules and a strategy to steer the transformation process. First, we adapt two social network generation algorithms in order to create new networks presenting small-world characteristics. Then, we translate different diffusion models to simulate information diffusion phenomena. By adapting the different models into a common formalism, we make their comparison much easier along with the adjustment of their parameters. Finally, we finish by presenting a novel compact layout method to display overviews of the results of our information diffusion method., Dans cette thèse, nous présentons à la fois une collection de modèles de générations de réseaux et de diffusion d'information exprimés à l'aide d'un formalisme particulier appelé la réécriture de graphes, ainsi qu'une nouvelle méthode de représentation permettant la visualisation de la diffusion d'information dans des grands réseaux sociaux. Les graphes sont des objets mathématiques particulièrement versatiles qui peuvent être utilisés pour représenter une large variété de systèmes abstraits. Ces derniers peuvent être transformés de multiples façons (création, fusion ou altération de leur éléments), mais de telles modifications doivent être contrôlées afin d'éviter toute opération non souhaitée. Pour cela, nous faisons appel au formalisme particulier de la réécriture de graphes afin d'encadrer et de contrôler toutes les transformations. Dans notre travail, un système de réécriture de graphes opère sur un graphe, qui peut être transformé suivant un ensemble de règles, le tout piloté par une stratégie. Nous commençons tout d'abord par utiliser la réécriture en adaptant deux algorithmes de génération de réseaux, ces derniers permettant la création de réseaux aux caractéristiques petit monde. Nous traduisons ensuite vers le formalisme de réécriture différents modèles de diffusion d'information dans les réseaux sociaux. En énonçant à l'aide d'un formalisme commun différents algorithmes, nous pouvons plus facilement les comparer, ou ajuster leurs paramètres. Finalement, nous concluons par la présentation d'un nouvel algorithme de dessin compact de grands réseaux sociaux pour illustrer nos méthodes de propagation d'information.

Whenever one wishes to try out or fine tune a social network analysis solution, being able to apply the said solution to an appropriate data set is of the utmost importance. However, and despite their established popularity, such network structures are rarely open or available in their entirety, thus developing the need for random generative models able to create graphs with properties close to those of real-world networks. We introduce a new generative model allowing the creation of such graphs. Our solution can be fine-tuned and used to build a wide array of graphs, ranging from small-world networks --with some of the free-scale networks characteristics-- to completely random graphs., Lors de la construction ou l'évaluation de méthodes d'analyse de réseaux sociaux, il est important de pouvoir tester sa solution sur des données viables. Cependant, et malgré leur grande popularité, les structures internes de ces réseaux, indiquant les relations inter-individus, ne sont que rarement ouvertes ou diffusées, forçant les chercheurs à se tourner vers des réseaux construits par des modèles de génération aléatoire. Nous présentons un nouveau modèle de génération permettant la création de graphes. Notre solution est paramétrable et peut être utilisée pour construire un large éventail de graphes, allant des réseaux sociaux petit monde --avec certaines caractéristiques des réseaux invariants d'échelle-- à des graphes complètement aléatoires.

Démonstration logicielle; National audience; PORGY is a visual environment for rule-based modelling based on port graphs and port graph rewrite rules whose application is steered by rewriting strategies. The focus of this demonstration is the visual and interactive features offered by PORGY, which facilitate an exploratory approach to model, simulate and analyse different ways of applying the rules while recording the model evolution, as well as tracking and plotting system parameters.; Porgy is a visual environment for rule-based modelling based on port graphs and port graph rewrite rules whose application is steered by rewriting strategies. The focus of this demonstration is the visual and interactive features offered by \Porgy, which facilitate an exploratory approach to model, simulate and analyse different ways of applying the rules while recording the model evolution, as well as tracking and plotting system parameters.

Numerous propagation models in social networks describing social influence can be found in the literature, making it difficult to select an appropriate model in a given situation. Selecting the most relevant model requires the ability to objectively compare them. This comparison can only be made at the cost of describing models based on a common formalism and independant from them. We propose to use graph rewriting to formally describe the propagation mechanisms as local transformation rules applied according to a strategy. This approach makes complete sense when supported by a visual analytics framework dedicated to graph rewriting. The paper first presents several models and illustrates them through selected simulations. We then show how our visual analytics framework allows to interactively manipulate models, and underline their differences based on measures computed on simulation traces., Les modèles de propagation d'informations, d'influence et d'actions dans les réseaux sociaux sont nombreux et diversifiés rendant le choix de ce-lui approprié à une situation donnée potentiellement difficile. La sélection d'un modèle pertinent pour une situation exige de pouvoir effectuer des comparai-sons de modèles. Cette comparaison n'est possible qu'au prix d'une traduction des modèles dans un formalisme commun et indépendant de ceux-ci. Nous pro-posons l'utilisation de la réécriture de graphes afin d'exprimer les mécanismes de propagation sous la forme d'un ensemble de règles de transformation lo-cales appliquées selon une stratégie donnée. Cette démarche prend tout son sens lorsque les modèles ainsi traduits sont étudiés et simulés à partir d'une plate-forme de visualisation analytique dédiée à la réécriture de graphe. Après avoir décrit quelques modèles et effectué différentes simulations, nous montrons sur quelques exemples comment la plate-forme permet d'interagir avec ces forma-lismes, et comparer interactivement les traces d'exécution de chaque modèle grâce à diverses mesures soulignant leurs différences.

Whenever one wishes to try out or fine tune a social network analysis solution, being able to apply the said solution to an appropriate data set is of the utmost importance. However, and despite their established popularity, such network structures are rarely open or available in their entirety, thus developing the need for random generative models able to create graphs with properties close to those of real-world networks. We introduce a new generative model allowing the creation of such graphs. Our solution can be fine-tuned and used to build a wide array of graphs, ranging from small-world networks --with some of the free-scale networks characteristics-- to completely random graphs.; Lors de la construction ou l'évaluation de méthodes d'analyse de réseaux sociaux, il est important de pouvoir tester sa solution sur des données viables. Cependant, et malgré leur grande popularité, les structures internes de ces réseaux, indiquant les relations inter-individus, ne sont que rarement ouvertes ou diffusées, forçant les chercheurs à se tourner vers des réseaux construits par des modèles de génération aléatoire. Nous présentons un nouveau modèle de génération permettant la création de graphes. Notre solution est paramétrable et peut être utilisée pour construire un large éventail de graphes, allant des réseaux sociaux petit monde --avec certaines caractéristiques des réseaux invariants d'échelle-- à des graphes complètement aléatoires.

Tulip is an information visualization framework dedicated to the analysis and visualization of relational data. Based on more than 15 years of research and development, Tulip is built on a suite of tools and techniques , that can be used to address a large variety of domain-specific problems. With Tulip, we aim to provide Python and/or C++ developers a complete library, supporting the design of interactive information visualization applications for relational data, that can be customized to address a wide range of visualization problems. In its current iteration, Tulip enables the development of algorithms, visual encodings, interaction techniques, data models, and domain-specific visualizations. This development pipeline makes the framework efficient for creating research prototypes as well as developing end-user applications. The recent addition of a complete Python programming layer wraps up Tulip as an ideal tool for fast prototyping and treatment automation, allowing to focus on problem solving, and as a great system for teaching purposes at all education levels.

The propagation models in social networks and alike are numerous and hard to compareto each other. We suggest in the following the use of graph rewriting technique to divide eachmodel and create additionnal contrasting points. Such method, seconded with a customizedvisualization software granting an understandable presentation of the results, eases the usertasks by assisting her/him in finding an appropriate propagation model., L’étude des réseaux sociaux ainsi que les comportements de leurs utilisateurs a levé beau-coup de questions et mené à la création de nombreux modèles tentant de régénérer artificielle-ment les agissements observés. Ces résultats peuvent être utilisés afin de prédire les réponsesdes utilisateurs face à certains stimuli et possiblement en anticiper l’évolution. Un tel usageest notamment répandu dans le domaine de la publicité et du placement de produits (initié parDomingos et Richardson (2001)) ou encore en médecine et santé publique pour l’anticipationet le traitement des épidémies (Dodds et Watts (2005)).Deux modèles ont été initialement décrits pour tenter de caractériser les différentes facettesde ce problème, respectivement la propagation par seuil d’activation ou par cascade indépen-dante, par la suite reconnus comme appartenant à un modèle plus général introduit par Kempeet al. (2003). Après étude de la bibliographie disponible, nous nous sommes rendus compteque le grand nombre de modèles disponibles pouvait devenir désavantageux dès lors où la per-sonne désirant émuler une propagation n’avait qu’une idée approximative du modèle pouvantlui convenir pour s’approcher au mieux de son cas d’étude. Cette réflexion nous a amené à nousdemander comment un utilisateur pouvait effectivement sélectionner ou comparer des modèleslui paraissant appropriés. Entre autres, les pistes auxquelles nous nous sommes intéressés nousont également amené à nous pencher vers la visualisation et sur certains de ses aspects pouvantêtre exploités pour mener à bien cette tâche.

National audience; Toute sortes de données peuvent être visualisées. Évidemment, certains types de visualisa-tions sont plus adaptés que d'autres selon les cas d'application : ainsi un système de fichiers est souvent dessiné sous la forme d'un arbre, tandis qu'une vue noeuds-liens est préférée pour vi-sualiser un réseau social. Quand le nombre d'éléments à visualiser devient trop important, ces visualisations sont difficiles à utiliser. Les éléments sont alors difficiles à distinguer, rendant l'extraction visuelle d'information d'autant plus complexe. Lors de nos premiers travaux sur les phénomènes de propagation dans les réseaux sociaux (Vallet et al., 2015), nous nous sommes retrouvés confrontés à ce problème dès que les ré-seaux étudiés comptaient quelques dizaines de milliers d'éléments. Nous avons en particulier essayé les représentations multi-niveaux qui sont communément rencontrées. Elles permettent une exploration intuitive et peuvent être utilisées sur de très grands graphes, néanmoins, les données de départ doivent être hiérarchisées et tous les éléments ne sont jamais montrés en même temps, empêchant ainsi une représentation globale du graphe. D'autres solutions ren-contrées utilisent des courbes de remplissage afin de distribuer de manière efficace et compacte les éléments dans l'espace. Ces techniques, telle que Muelder et Ma (2008), autorisent la re-présentation d'un nombre d'éléments élevé dans un espace restreint. Malgré tout, l'encodage visuel d'informations sur les noeuds est peu visible de par la taille réduite des éléments et nécessite d'alterner constamment entre une vue globale et une représentation plus détaillée. FIG. 1 – Illustration du fonctionnement de JASPER. Pour répondre à nos besoins, nous avons développé JASPER, qui reprend certaines caracté-ristiques des représentations orientées pixels, tout en reposant sur l'utilisation d'une courbe de remplissage telle qu'introduite par Keim (2000). La combinaison de ces deux techniques nous permet de répartir les noeuds dans l'espace afin d'améliorer leur visibilité et de quand même prendre en compte les arêtes qui sont souvent absentes des visualisations orientées pixels. En effet, le placement des noeuds sur la courbe est réalisé de façon à préserver la proximité des

We develop an algebraic approach, based on labelled-graph strategic rewriting , for the study of social networks, specifically network generation and propagation mechanisms. This approach sheds a new light on these problems, and leads to new or improved generation and propagation algorithms. We argue that relevant concepts are provided by three ingredients: labelled graphs to represent networks of data or users, rewrite rules to describe concurrent local transformations, and strategies to express control. We show how these techniques can be used to generate random networks that are suitable for social network analysis, simulate different propagation mechanisms, and analyse and compare propagation models by extracting common rules and differences, thus leading to improved algorithms. We illustrate with examples the flexibility of the approach.

International audience; Modeling propagation dynamics on networks is an amazingly fertile and active area of research. Roughly speaking, network models aim at gaining a better understanding of how actors influence the overall network behavior through their individual actions. Models typically consist in specifying a finite number of algorithmic rules from which overall structural trends can be derived. One is entitled to think that moving beyond the state-of-the-art in network modeling requires the ability to compare models, not only looking at their performance and suitability, but at a fundamental level. This ambitious goal requires having a common language describing models, allowing to objectively compare them and unfold their inherent properties and complexity. The results we present aim at providing a common framework turning network propagation modeling into rule-based modeling (aka graph rewriting). That is, models are described as a set of algorithmic rules acting locally. We show the validity of our approach by providing a description of the well-known model proposed by Goyal et al. 2010 relying on probabilistic rules, where nodes trigger actions depending on their neighbor's influences. Rule-based modeling not only provides a common language to define, describe and build models. It also paves the road to a formal setting from which model simulations can be steered. Because the application of rules is stochastic and non-deterministic, different variations of a model can be defined and easily compared. Our approach is moreover supported through the visual framework PORGY, turning model validation and comparison into a game where one iterates transformation rules on an initial graph, until some condition is met. The results we have obtained using Goyal's model confirm rule-based modeling as a promising avenue. Extending its application to other models will show its use as a common, if not universal, formal language to define and describe network propagation models.

International audience; Modeling propagation dynamics on networks is an amazingly fer-tile and active area of research. Roughly speaking, network models aim at gaining a better understanding of how actors influence the overall network behaviour through their individual actions. How-ever, considering the extended literature surrounding the subject, one is entitled to think that moving beyond the state-of-the-art in network modeling requires the ability to compare models, or con-sider slight variations of a model. This requires having a common language describing all considered models, allowing to objectively compare them and unfold their inherent properties and complex-ity. This also assumes users can easily run models, steer them and interactively evaluate their performance and behaviour. The approach we describe aims at providing a framework turning network propagation modeling into rule-based modeling (aka graph rewriting). That is, models are described as a set of algorithmic transformation rules acting locally. Our approach has partially been validated by providing such a description of a well-known model relying on probabilistic rules, where nodes trigger actions depend-ing on their neighbor's influences. The results so obtained confirm rule-based modeling as a promising avenue. The use of a visual an-alytics framework to conduct such tasks is vital and motivated us to further develop and adapt a general purpose visual analytics system for graph rewriting to the particular case of network propagation.