This thesis develops a number of graph-based techniques that are capable of measuring the dynamic behaviour of a network and discusses their application in network management. By representing a computer network as a time series of uniquely labelled graphs, it is possible to measure the degree of change that has occurred between a pair of graphs, and hence the dynamics in a network. Concepts introduced include the median graph, intra- and inter- graph clustering, and hierarchical graph representations. The focus is on producing efficient algorithms and improved measures of network change. It is believed that these graph-based techniques for measuring network dynamics have great potential in network anomaly detection, and thus will improve reliability of enterprise intranets.

This thesis develops a number of graph-based techniques that are capable of measuring the dynamic behaviour of a network and discusses their application in network management. By representing a computer network as a time series of uniquely labelled graphs, it is possible to measure the degree of change that has occurred between a pair of graphs, and hence the dynamics in a network. Concepts introduced include the median graph, intra- and inter- graph clustering, and hierarchical graph representations. The focus is on producing efficient algorithms and improved measures of network change. It is believed that these graph-based techniques for measuring network dynamics have great potential in network anomaly detection, and thus will improve reliability of enterprise intranets.

Title: Application of hierarchical graph grammars in procedural 3D world gen- eration Author: Jakub Svoboda Abstract: Procedural content generation (PCG) is an often-used technique in video games. It allows us to generate large quantities and permutations of con- tent. A common problem in utilizing PCG in level design is that it is challenging to generate content close to what a human would create in overall quality and structure. One way of solving these problems is using graph grammars to rep- resent relations in the game world. Implementing a working graph generator using graph grammars and applying it to generate worlds is not very well docu- mented. This thesis will try to overcome this problem by implementing such a generator and extending it to use hierarchical graph grammars. The generator will be used to generate a 3D open world. The generator should be suitable for levels in other types of games. Keywords: procedural content generation, game development, hierarchical graphs, graph grammars, procedural level design

Les travaux de ma thèse s'articulent en trois parties distinctes.Dans la première partie j'étudie les mesures de Malliavin-Shavguldize sur les difféomorphismes du cercle et de l'intervalle. Il s'agit de mesures de type « Haar » pour ces groupes de dimension infinie : elles furent introduites il a une vingtaine d'années pour permettre une étude de leur théorie des représentations. Un premier chapitre est dédié à recueillir les résultats présents dans la littérature et et les représenter dans une forme plus étendue, avec un regard particulier sur les propriétés de quasi-invariance de ces mesures. Ensuite j'étudie de problèmes de nature plus dynamique : quelle est la dynamique qu'on doit s'attendre d'un difféomorphisme choisi uniformément par rapport à une mesure de Malliavin-Shavguldize ? Je démontre en particulier qu'il y a une forte présence des difféomorphismes de type Morse-Smale.La partie suivante vient de mon premier travail publié, obtenu en collaboration avec Andrés Navas. Inspirés d'un théorème récent de Avila et Kocsard sur l'unicité des distributions invariantes par un difféomorphisme lisse minimal du cercle, nous analysons le même problème en régularité faible, avec des argument plus géométriques.La dernière partie est constituée des résultats récemment obtenus avec Mikhail Khristoforov et Victor Kleptsyn. Nous abordons les problèmes reliés à la gravité quantique de Liouville en étudiant des espaces auto-similaires qui sont la limite de graphes finis. Nous démontrons qu'il est possible de trouver des distances aléatoires non-triviales sur ces espaces qui sont compatibles avec la structure auto-similaire. / This thesis is divided into three different parts.In the first part, we study the Malliavin-Shavgulidze measure on circle and interval diffeomorphisms. They are Haar-like measures for these infinite-dimensional groups: they were introduced about twenty years ago to help to study their represantation theory. The first chapter collects the results that were obtained in the past years and in some cases we present them under a renewed point of view, with particular attention on quasi-invariance properties for this measures. Then we study some questions of dynamical nature: which is the typical dynamics that we must expect described by a diffeomorphism chosen randomly according to some Malliavin-Shavguldize measure? In particular, we prove that there is a strong presence of Morse-Smale diffeomorphisms.The third chapter comes from the published joint work with Andrés Navas. Inspired by a recent theorem by Avila and Kocsard about the uniqueness of the invariant distribution for a minimal smooth circle diffeomorphism, we analyse the same problem in low regularity, with more geometric arguments.The last part corresponds to the recent results obtained with Mikhail Khristoforov and Victor Kleptsyn. We consider problems in relation with Liouville quantum gravity, by studying self-similar metric spaces which are the limit of finite graphs. We prove that it is possible to find nontrivial random distances on these spaces which are compatible with the self-similar structure.