Complex network theory has been well established as one of the main tools for understanding and analyzing the behavior of the natural systems that surround us. Social networks, genetic and protein interaction networks, airline and road traffic networks, brain connectivity networks and web graphs are only some of the examples. As network theory evolves it becomes more apparent that these complex systems are often composed of multiple types of interactions, each carrying a different piece of information, and therefore are commonly represented in the form of multiplex networks, where each layer represents a different type of interaction among nodes. In addition to the interactions among the nodes of the networks, these systems also present correlations among the various types of interactions, as represented by the intrinsic structure and the associations of the various layers of the graph. For example, in social sciences, a network with a large overlap between two layers that represent two distinct types of people interactions i.e. friendship and professional ties might indicate that there is an interconnection between the two in the given network. In another example, in transportation networks, where nodes represent airports connected by flights operated by specific airlines (each airline representing a layer of the graph), the structure of the layers can provide information about the airline: traditional airlines such as Lufthansa tend to have a large overlap in activity pattern with other airlines, whereas low-cost airlines such as easyJet tend to avoid such overlaps. Due to their ability to represent such complex entity interactions, multiplex networks have lately been the focus of a large part of the research community, studying a variety of aspects, such as structural measures, node communities detection, layer reducibility, network generative models, and information spreading. In this work we focus on techniques for the exploration of the intrinsic structure of multiplex networks, and contemplate ways of addressing common challenges of learning from multiplex networks. In particular, our work focuses on three main directions: structured regression, graph summarization and graph similarity. We analyze and discuss the main challenges of each of these research directions, and then we propose novel methods to address them. For each problem, we utilize artificial data to study their effectiveness, understand their intrinsic properties and evaluate their behavior under a controlled network structure. Then, we report applications on real-world data sets, from variety of domains, and compare our proposed methods with state-of-the-art and well established baseline methods. Through this work, we aim to offer proof that the networks' intrinsic structure, when utilized, can increase the informative power of network theory models and allow researchers to build more educated algorithms. / Computer and Information Science

Cette thèse porte en premier lieu sur l'analyse et le désassemblage de programmes malveillants utilisant certaines techniques d'obscurcissement telles que l'auto-modification et le chevauchement de code. Les programmes malveillants trouvés dans la pratique utilisent massivement l'auto-modification pour cacher leur code utile à un analyste. Nous proposons une technique d'analyse hybride qui utilise une trace d'exécution déterminée par analyse dynamique. Cette analyse découpe le programme auto-modifiant en plusieurs sous-parties non auto-modifiantes que nous pouvons alors étudier par analyse statique en utilisant la trace comme guide. Cette seconde analyse contourne d'autres techniques de protection comme le chevauchement de code afin de reconstruire le graphe de flot de contrôle du binaire analysé. Nous étudions également un détecteur de programmes malveillants, fonctionnant par analyse morphologique : il compare les graphes de flot de contrôle d'un programme à analyser à ceux de programmes connus comme malveillants. Nous proposons une formalisation de ce problème de comparaison de graphes, des algorithmes permettant de le résoudre efficacement et détaillons des cas concrets d'application à la détection de similarités logicielles / This dissertation explores tactics for analysis and disassembly of malwares using some obfuscation techniques such as self-modification and code overlapping. Most malwares found in the wild use self-modification in order to hide their payload from an analyst. We propose an hybrid analysis which uses an execution trace derived from a dynamic analysis. This analysis cuts the self-modifying binary into several non self-modifying parts that we can examine through a static analysis using the trace as a guide. This second analysis circumvents more protection techniques such as code overlapping in order to recover the control flow graph of the studied binary. Moreover we review a morphological malware detector which compares the control flow graph of the studied binary against those of known malwares. We provide a formalization of this graph comparison problem along with efficient algorithms that solve it and a use case in the software similarity field

Cette thèse s'organise en deux parties : une première partie s'intéresse aux mesures de similarité entre sommets d'un graphe, une seconde aux méthodes de clustering de graphe biparti. Une nouvelle mesure de similarité entre sommets basée sur des marches aléatoires en temps courts est introduite. Cette méthode a l'avantage, en particulier, d'être insensible à la densité du graphe. Il est ensuite proposé un large état de l'art des similarités entre sommets, ainsi qu'une comparaison expérimentale de ces différentes mesures. Cette première partie se poursuit par la proposition d'une méthode robuste de comparaison de graphes partageant le même ensemble de sommets. Cette mesure est mise en application pour comparer et fusionner des graphes de synonymie. Enfin une application d'aide à la construction de ressources lexicales est présentée. Elle consiste à proposer de nouvelles relations de synonymie à partir de l'ensemble des relations de synonymie déjà existantes. Dans une seconde partie, un parallèle entre l'analyse formelle de concepts et le clustering de graphe biparti est établi. Ce parallèle conduit à l'étude d'un cas particulier pour lequel une partition d’un des groupes de sommets d’un graphe biparti peut-être déterminée alors qu'il n'existe pas de partitionnement correspondant sur l’autre type de sommets. Une méthode simple qui répond à ce problème est proposée et évaluée. Enfin Kodex, un système de classification automatique des résultats d'une recherche d'information est présenté. Ce système est une application en RI des méthodes de clustering vues précédemment. Une évaluation sur une collection de deux millions de pages web montre les avantages de l'approche et permet en outre de mieux comprendre certaines différences entre méthodes de clustering. / This thesis is organized in two parts : the first part focuses on measures of similarity (or proximity) between vertices of a graph, the second part on clustering methods for bipartite graph. A new measure of similarity between vertices, based on short time random walks, is introduced. The main advantage of the method is that it is insensitive to the density of the graph. A broad state of the art of similarities between vertices is then proposed, as well as experimental comparisons of these measures. This is followed by the proposal of a robust method for comparing graphs sharing the same set of vertices. This measure is shown to be applicable to the comparison and merging of synonymy networks. Finally an application for the enrichment of lexical resources is presented. It consists in providing candidate synonyms on the basis of already existing links. In the second part, a parallel between formal concept analysis and clustering of bipartite graph is established. This parallel leads to the particular case where a partition of one of the vertex groups can be determined whereas there is no corresponding partition on the other group of vertices. A simple method that addresses this problem is proposed and evaluated. Finally, a system of automatic classification of search results (Kodex) is presented. This system is an application of previously seen clustering methods. An evaluation on a collection of two million web pages shows the benefits of the approach and also helps to understand some differences between clustering methods.