This thesis is concerned with studying the behavior of a gossiping protocol in the specific sense meant by Ericsson; in the following pages I’ll introduce a Markov process which models the spread of information in such systems. The results will be verified by means of a discreet-event simulation. / Gossiping Protocols, are inherently random in behavior.Nonetheless, they are not structure-less. Their asymptotic behavior when implemented in large scales is the matter of focus in this thesis. / Tel: +46709700505 Address: Pinnharvsgatan 3 E lgh 1202 43147 Mölndal Sweden

L’étude des phénomènes de la diffusion d’information à grand échelle est un domaine récent. La diffusion d’information est définie comme le processus de communication par lequel une idée ou une information se propage dans une population et qui peut impacter le comportement des individus. Les institutions, tout comme les entreprises, cherchent à comprendre et à prévoir l’impact de la propagation d’information sur les individus. Une approche de modélisation et simulation permet de mieux comprendre ce processus social et de répondre à ces questions. La modélisation et la simulation à base d’agents offre une approche puissante pour modéliser un tel processus social. Toutefois, les modèles actuels simplifient fortement les facteurs culturels et les informations représentées dans le modèle ainsi que les différents liens interconnectant les individus. Ces éléments sont centraux et déterminants pour le processus de propagation. Afin d'améliorer les modèles de propagation, nous explorons dans cette thèse une représentation de la population plus réaliste. Nous proposons une architecture de modélisation et simulation permettant de simuler les phénomènes de propagation au sein des réseaux sociaux multiplexes et dynamiques basée sur le formalisme DEVS. / The study of information dissemination phenomena of large-scale is a new field. Diffusion of information is defined as the communication process by which an idea or information spreads within a social system and that can impact the behaviour of individuals. Institutions and firms search to understand and predict the impact of information propagation on individuals. Agent-based modelling is a powerful approach for studying such a collective process. However, existing models oversimplify adopters' cultural attributes, different type of link and information content, despite the evidence of their central role in diffusion process. In this thesis, we challenge the feasibility and utility of a more realistic representation of population. We use the DEVS formalism, extended by DS-DEVS and PDEVS in order to simulate the propagation phenomena within a multi-layer social network (MSN).

Dans cette thèse nous étudierons des problématiques de graphes. Nous proposons deux études théoriques sur la recherche et l'énumération de cliques et quasi-cliques. Ensuite nous proposons une étude appliquée sur la propagation d'information dans un graphe d'entités nommées. Premièrement, nous étudierons la recherche de cliques dans des graphes compressés. Les problèmes MCE et MCP sont des problèmes rencontrés dans l'analyse des graphes. Ce sont des problèmes difficiles, pour lesquels des solutions adaptées doivent être conçues pour les grands graphes. Nous proposons de travailler sur une version compressée du graphe. Nous montrons les bons résultats obtenus par notre méthode pour l'énumération de cliques maximales. Secondement, nous étudierons l'énumération de quasi-cliques maximales. Nous proposons un algorithme distribué qui énumère l'ensemble des quasi-cliques maximales. Nous proposons aussi une heuristique qui liste des quasi-cliques plus rapidement. Nous montrons l'intérêt de l'énumération de ces quasi-cliques par une évaluation des relations en regardant la co-occurrence des noeuds dans l'ensemble des quasi-cliques énumérées. Troisièmement, nous travaillerons sur la diffusion d'événements dans un graphe d'entités nommées. De nombreux modèles existent pour simuler des problèmes de diffusion de rumeurs ou de maladies dans des réseaux sociaux ou des problèmes de propagation de faillites dans les milieux bancaires. Nous proposons de répondre au problème de diffusion d'événements dans des réseaux hétérogènes représentant un environnement économique du monde. Nous proposons un problème de diffusion, nommé problème de classification de l'infection, qui consiste à déterminer quelles entités sont concernées par un événement. Pour ce problème, nous proposons deux modèles inspirés du modèle de seuil linéaire auxquels nous ajoutons différentes fonctionnalités. Finalement, nous testons et validons nos modèles sur un ensemble d'événements / In this thesis we will study graph problems. We will study theoretical problems in pattern research and applied problems in information diffusion. We propose two theoretical studies on the identification/detection and enumeration of dense subgraphs, such as cliques and quasi-cliques. Then we propose an applied study on the propagation of information in a named entities graph. First, we will study the identification/detection of cliques in compressed graphs. The MCE and MCP are problems that are encountered in the analysis of data graphs. These problem are difficult to solve (NP-Hard for MCE and NP-Complete for MCP), and adapted solutions must be found for large graphs. We propose to solve these problems by working on a compressed version of the initial graph. We show the correct results obtained by our method for the enumeration of maximal cliques on compressed graphs. Secondly, we will study the enumeration of maximal quasi-cliques. We propose a distributed algorithm that enumerates the set of maximal quasi-cliques of the graph. We show that this algorithm lists the set of maximal quasi-cliques of the graph. We also propose a heuristic that lists a set of quasi-cliques more quickly. We show the interest of enumerating these quasi-cliques by an evaluation of relations by looking at the co-occurrence of nodes in the set of enumerated quasi-cliques. Finally, we work on the event diffusion in a named entities graph. Many models exist to simulate diffusion problems of rumors or diseases in social networks and bankruptcies in banking networks. We address the issue of significant events diffusion in heterogeneous networks, representing a global economic environment. We propose a diffusion problem, called infection classification problem, which consists to dertemine which entities are concerned by an event. To solve this problem we propose two models inspired by the linear threshold model to which we add different features. Finally, we test and validate our models on a set of events

L’étude de la conflictualité armée dans les pays en développement et des effets des interventions extérieures visant à la circonscrire constitue un enjeu majeur et multidisciplinaire. La complexité des processus sociaux entrelacés dans de tels contextes génère des défis particuliers pour les approches de modélisation et simulation informatique. En effet la forme des conflits actuels, centrés autour des populations locales, a amené les forces de stabilisation à développer des actions dites d'influence, qui se donnent pour but de convaincre les locaux de la légitimité des opérations. Ce travail en retient trois (opérations psychologiques OMI/PSYOPS, opérations civilo-militaires et Key Leader Engagements) et propose une modélisation permettant de représenter la propagation de leurs effets au sein d'une population virtuelle réaliste. Cela nécessite une représentation détaillée des mécanismes psychologiques de persuasion et d’influence et des structures sociales considérées, et constitue donc un apport à l’analyse des processus de communication au sein de réseaux sociaux. On fait le choix d'une simulation sociale orientée agents permettant de représenter d'une part un échantillon composé uniquement d'individus (jusqu’à environ 10 000) dotés de mécanismes de traitement réalistes, et d'autre part la complexité des sphères de sociabilité collective en générant cette population sous forme d'un réseau multicouche. Le modèle conceptuel ainsi conçu permet d’intégrer pour chaque étape des critères pertinents pour la simulation des actions, mais aussi, eut égard à la nature même de celles-ci et de leurs enjeux, d’éclairer certains mécanismes sociaux caractéristiques d’un conflit armé / The study, analysis and understanding of armed violence phenomenons in developing countries and of the effects of international military interventions aimed at resolving them is a crucial contemporary issue. These situations coincidentally present, considering the plethora and complexity of the implicated and intertwined social processes, a challenge for social computing, modeling and simulation. A challenge but also an opportunity, as the evolution of the forms of conflict, today centered on the local populations, has prompted the armies tasked with implementing stabilization missions to develop influence actions. Such operations, overall concerned with persuading the locals of the legitimacy of the operations, allow a more comprehensive approach to conflict resolution, beyond the simple use of force. Modeling some of these specific actions (PSYOPS, CIMIC, and Key Leader Engagement) is a credible project and a contribution to analysis of communication and persuasion processes in social networks by taking into account detailed and specific social and cultural factors. This research thus presents a conceptual model allowing simulation of the effects of these specific actions of influence in a realistic civilian population. We chose an agent-based approach as these lend particularly well with this type of research, allowing us to generate a group of up to 10,000 agents, composed solely of individuals for a detailed cognitive treatment, and structured as a multilayer network for representing complex sociality. Given the nature of such actions and their context of application, such a model also highlights some social mechanisms typical of armed conflict situations