Rozprawy doktorskie na temat „Graph dynamics”

Thesis (S.M.)--Massachusetts Institute of Technology, School of Architecture and Planning, Program in Media Arts and Sciences, 2006.
Includes bibliographical references (p. 58-60).
Graphs are often used in artificial intelligence as means for symbolic knowledge representation. A graph is nothing more than a collection of symbols connected to each other in some fashion. For example, in computer vision a graph with five nodes and some edges can represent a table - where nodes correspond to particular shape descriptors for legs and a top, and edges to particular spatial relations. As a framework for representation, graphs invite us to simplify and view the world as objects of pure structure whose properties are fixed in time, while the phenomena they are supposed to model are actually often changing. A node alone cannot represent a table leg, for example, because a table leg is not one structure (it can have many different shapes, colors, or it can be seen in many different settings, lighting conditions, etc.) Theories of knowledge representation have in general concentrated on the stability of symbols - on the fact that people often use properties that remain unchanged across different contexts to represent an object (in vision, these properties are called invariants). However, on closer inspection, objects are variable as well as stable. How are we to understand such problems? How is that assembling a large collection of changing components into a system results in something that is an altogether stable collection of parts?
(cont.) The work here presents one approach that we came to encompass by the phrase "graph dynamics". Roughly speaking, dynamical systems are systems with states that evolve over time according to some lawful "motion". In graph dynamics, states are graphical structures, corresponding to different hypothesis for representation, and motion is the correction or repair of an antecedent structure. The adapted structure is an end product on a path of test and repair. In this way, a graph is not an exact record of the environment but a malleable construct that is gradually tightened to fit the form it is to reproduce. In particular, we explore the concept of attractors for the graph dynamical system. In dynamical systems theory, attractor states are states into which the system settles with the passage of time, and in graph dynamics they correspond to graphical states with many repairs (states that can cope with many different contingencies). In parallel with introducing the basic mathematical framework for graph dynamics, we define a game for its control, its attractor states and a method to find the attractors. From these insights, we work out two new algorithms, one for Bayesian network discovery and one for active learning, which in combination we use to undertake the object recognition problem in computer vision. To conclude, we report competitive results in standard and custom-made object recognition datasets.
by Andre Figueiredo Ribeiro.
S.M.

Dynamics of social processes in populations, such as the spread of emotions, influence, language, mass movements, and warfare (often referred to individually and collectively as contagions), are increasingly studied because of their social, political, and economic impacts. Discrete dynamical systems (discrete in time and discrete in agent states) are often used to quantify contagion propagation in populations that are cast as graphs, where vertices represent agents and edges represent agent interactions. We refer to such formulations as graph dynamical systems. For social applications, threshold models are used extensively for agent state transition rules (i.e., for vertex functions). In its simplest form, each agent can be in one of two states (state 0 (1) means that an agent does not (does) possess a contagion), and an agent contracts a contagion if at least a threshold number of its distance-1 neighbors already possess it. The transition to state 0 is not permitted. In this study, we extend threshold models in three ways. First, we allow transitions to states 0 and 1, and we study the long-term dynamics of these bithreshold systems, wherein there are two distinct thresholds for each vertex; one governing each of the transitions to states 0 and 1. Second, we extend the model from a binary vertex state set to an arbitrary number r of states, and allow transitions between every pair of states. Third, we analyze a recent hierarchical model from the literature where inputs to vertex functions take into account subgraphs induced on the distance-1 neighbors of a vertex. We state, prove, and analyze conditions characterizing long-term dynamics of all of these models.
Master of Science

One way to construct noncommutative analogues of a Riemannian manifold Σ is to make use of the Toeplitz quantization procedure. In Paper III and IV, we construct C-algebras for a continuously deformable class of spheres and tori, and by introducing the directed graph of a representation, we can completely characterize the representation theory of these algebras in terms of the corresponding graphs. It turns out that the irreducible representations are indexed by the periodic orbits and N-strings of an iterated map s:(reals) 2→(reals)2 associated to the algebra. As our construction allows for transitions between spheres and tori (passing through a singular surface), one easily sees how the structure of the matrices changes as the topology changes. In Paper II, noncommutative analogues of minimal surface and membrane equations are constructed and new solutions are presented -- some of which correspond to minimal tori embedded in S7. Paper I is concerned with the problem of finding differential equations for the eigenvalues of a symmetric N × N matrix satisfying Xdd=0. Namely, by finding N(N-1)/2 suitable conserved quantities, the time-evolution of X (with arbitrary initial conditions), is reduced to non-linear equations involving only the eigenvalues of Χ.
QC 20100630

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, February 2003.
Includes bibliographical references (leaves 186-191).
This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Our research focuses on developing design-oriented analytical tools that enable us to better understand how a network comprising dynamic and static elements behaves when it is set in oscillatory motion, and how the interconnection topology relates to the spectral properties of the system. Such oscillatory networks are ubiquitous, extending from miniature electronic circuits to large-scale power networks. We tap into the rich mathematical literature on graph spectra, and develop theoretical extensions applicable to networks containing nodes that have finite nonnegative weights-including nodes of zero weight, which occur naturally in the context of power networks. We develop new spectral graph-theoretic results spawned by our engineering interests, including generalizations (to node-weighted graphs) of various structure-based eigenvalue bounds. The central results of this thesis concern the phenomenon of dynamic coherency, in which clusters of vertices move in unison relative to each other. Our research exposes the relation between coherency and network structure and parameters. We study both approximate and exact dynamic coherency. Our new understanding of coherency leads to a number of results. We expose a conceptual link between theoretical coherency and the confinement of an oscillatory mode to a node cluster. We show how the eigenvalues of a coherent graph relate to those of its constituent clusters.
(cont.) We use our eigenvalue expressions to devise a novel graph design algorithm; given a set of vertices (of finite positive weight) and a desired set of eigenvalues, we construct a graph that meets the specifications. Our novel graph design algorithm has two interesting corollaries: the graph eigenvectors have regions of support that monotonically decrease toward faster modes, and we can construct graphs that exactly meet our generalized eigenvalue bounds. It is our hope that the results of this thesis will contribute to a better understanding of the links between structure and dynamics in oscillatory networks.
by Babak Ayazifar.
Ph.D.

Approved for public release; distribution is unlimited
By measuring network changes, we can get a better understanding of a network. Extending this to the Internet, we are able to understand the constantly occuring changes on an international scale. In this research, we propose a measure that conveys the relative magnitude of the change between two networks (i.e., Internet topology). The measure is normalised and intuitively gives an indication of whether the change is small or large. We start off by applying this measure to standard common graphs, as well as random graphs. These graphs were first simulated and the measurements taken; results were then proved theoretically. These corresponded to the simulation results, thus demonstrating correctness. For case studies, we compared actual implemented networks with that which is inferred by probes. This comparison was done to study how accurate the probes were in discovering actual network topology. Finally, we conducted real-world experiments by applying the measurements to certain segments of the Internet. We observed that the measurements indeed do pick up events which significantly influenced structural changes to the Internet.

Many problems in applied mathematics and physics are formulated most naturally in terms of matrices, and can be solved by computing functions of these matrices. For example, in quantum mechanics, the coherent dynamics of physical systems is described by the matrix exponential of their Hamiltonian. In state of the art experiments, one can now observe such unitary evolution of many-body systems, which is of fundamental interest in the study of many-body quantum phenomena. On the other hand the theoretical simulation of such non-equilibrium many-body dynamics is very challenging. In this thesis, we develop a symbolic approach to matrix functions and quantum dynamics based on a novel algebraic structure we identify for sets of walks on graphs. We begin by establishing the graph theoretic equivalent to the fundamental theorem of arithmetic: all the walks on any finite digraph uniquely factorise into products of prime elements. These are the simple paths and simple cycles, walks forbidden from visiting any vertex more than once. We give an algorithm that efficiently factorises individual walks and obtain a recursive formula to factorise sets of walks. This yields a universal continued fraction representation for the formal series of all walks on digraphs. It only involves simple paths and simple cycles and is thus called a path-sum. In the second part, we recast matrix functions into path-sums. We present explicit results for a matrix raised to a complex power, the matrix exponential, matrix inverse, and matrix logarithm. We introduce generalised matrix powers which extend desirable properties of the Drazin inverse to all powers of a matrix. In the third part, we derive an intermediary form of path-sum, called walk-sum, relying solely on physical considerations. Walk-sum describes the dynamics of a quantum system as resulting from the coherent superposition of its histories, a discrete analogue to the Feynman path-integrals. Using walk-sum we simulate the dynamics of quantum random walks and of Rydberg-excited Mott insulators. Using path-sum, we demonstrate many-body Anderson localisation in an interacting disordered spin system. We give two observable signatures of this phenomenon: localisation of the system magnetisation and of the linear magnetic response function. Lastly we return to the study of sets of walks. We show that one can construct as many representations of series of walks as there are ways to define a walk product such that the factorisation of a walk always exist and is unique. Illustrating this result we briefly present three further methods to evaluate functions of matrices. Regardless of the method used, we show that graphs are uniquely characterised, up to an isomorphism, by the prime walks they sustain.

A homomorphism from a graph G to a graph H is a function from V (G) to V (H) that preserves edges. Many combinatorial structures that arise in mathematics and in computer science can be represented naturally as graph homomorphisms and as weighted sums of graph homomorphisms. In this thesis we study the complexity of various problems related to graph homomorphisms.

In this thesis we have considered three different market graphs; one solely based on stock returns, another one based on stock returns with vertices weighted with a liquidity measure and lastly one based on correlations of volume fluctuations. Research is conducted on two different markets; the Swedish and the American stock market. We want to introduce graph theory as a method for representing the stock market in order to show that one can more fully understand the structural properties and dynamics of the stock market by studying the market graph. We found many signs of increased globalization by studying the clustering coefficient and the correlation distribution. The structure of the market graph is such that it pinpoints specific sectors when the correlation threshold is increased and different sectors are found in the two different markets. For low correlation thresholds we found groups of independent stocks that can be used as diversified portfolios. Furthermore, the dynamics revealed that it is possible to use the daily absolute change in edge density as an indicator for when the market is about to make a downturn. This could be an interesting topic for further studies. We had hoped to get additional results by considering volume correlations, but that did not turn out to be the case. Regardless of that, we think that it would be interesting to study volume based market graphs further.
I denna uppsats har vi tittat på tre olika marknadsgrafer; en enbart baserad på avkastning, en baserad på avkastning med likvidviktade noder och slutligen en baserad på volymkorrelationer. Studien är gjord på två olika marknader; den svenska och den amerikanska aktiemarknaden. Vi vill introducera grafteori som ett verktyg för att representera aktiemarknaden och visa att man bättre kan förstå aktiemarknadens strukturerade egenskaper och dynamik genom att studera marknadsgrafen. Vi fann många tecken på en ökad globalisering genom att titta på klusterkoefficienten och korrelationsfördelningen. Marknadsgrafens struktur är så att den lokaliserar specifika sektorer när korrelationstaket ökas och olika sektorer är funna för de två olika marknaderna. För låga korrelationstak fann vi grupper av oberoende aktier som kan användas som diversifierade portföljer. Vidare, avslöjar dynamiken att det är möjligt att använda daglig absolut förändring i bågdensiteten som en indikator för när marknaden är på väg att gå ner. Detta kan vara ett intressant ämne för vidare studier. Vi hade hoppats på att erhålla ytterligare resultat genom att titta på volymkorrelationer men det visade sig att så inte var fallet. Trots det tycker vi att det skulle vara intressant att djupare studera volymbaserade marknadsgrafer.

Graph model has been playing an important role in analyzing the data from real applications such as social networks, communication networks, and information networks. It models entities of the applications as vertices/nodes in the graph, and models relationships among the entities as edges between vertices in the graph. In recent years there has been an increasing number of studies of complex graph analysis coinciding with the rapid development of information technologies, such as online social networks and (mobile/email) communication networks. Due to the growing sizes of these graph data, traditional algorithms and tools are not capable of carrying out the desired operations on the growing amount of data. Motivated by this, we in this thesis investigate three representation problems in graph data analytics, and propose efficient algorithms for these problems. Firstly, we study the problem of community detection in undirected graphs. Community, as one important characteristic of real-world graphs, is relevant to a variety of problems, e.g., community detection, clustering and community search. How can communities of real networks be extracted within reasonable execution time and with high accuracy? Unlike existing community detection algorithms, which suffer from resolution limits or long execution times, the recently proposed interaction model based on distance dynamics has a logic view that simulates the interaction among vertices over time and leads to the discovery of qualified communities. However, the state-of-the-art algorithm Attractor for distance dynamics does not scale to large graphs, especially those with large maximum vertex degrees. In this thesis, we aim to scale distance dynamics to large graphs. To achieve that, we propose a fast distance dynamics algorithm FDD. We show that FDD has a worst-case time complexity of O(T · γ · m), where T is the number of iterations until convergence, γ is a small constant, and m is the number of edges in the input graph. Thus, the time complexity of FDD does not depend on the maximum vertex degree. Moreover, we also propose three optimization techniques to alleviate the dependency on T: active-edge queue, transitivity, and distance computation. Extensive empirical studies on large real graphs demonstrated the efficiency and effectiveness of FDD. Secondly, we study the problem of community search over directed graphs. We aim to identify a directed community such that it contains a set Q of query vertices and its members are frequently interacting with each other. The existing models for community search over directed graphs have some drawbacks. For example, the D-core-based model returns a sparse graph and requires end-users to provide two sensitive input parameters that are hard to specify in practice. We formulate a novel measure of cohesiveness for directed graph, called minimum interaction degree (ID), based on which we then define the notion of ID-core. Using the ID-core model, we formulate an ID-core-based community search problem and ID-core-based closest community search problem for directed graphs. We also design three algorithms namely, index-free algorithm, index-based algorithm and closest community search algorithm to solve the problems efficiently. While index-free algorithm incur reasonable time costs in answering a query, our index-based algorithm can answer a query efficiently in optimal time complexity with regard to the community size. On the other hand, the closest community search algorithm guarantees the best quality in an efficient time. Extensive empirical studies on large real directed graphs demonstrated the efficiency and the effectiveness of our models and our algorithms. Lastly, we study the problem of computing a maximum independent set on a large graph which is a key topic in the field of graph analytics and algorithms. Kernelization is a technique for developing exact and approximate maximum independent set algorithms by applying reduction rules on the graph until a smaller graph (kernel) is obtained to which no rule can be applied. While exact algorithms produce a small kernel by slow kernelization, heuristic algorithms yield a large kernel by fast kernelization. To achieve a small kernel using fast kernelization, we propose a novel method that produces a small kernel with high quality independent sets by partitioning the graph and applying simple and advanced reduction rules incrementally, using four techniques that accelerate the kernelization process. We then apply an efficient maximum clique computation algorithm on the complementary kernel to collect the remaining independent set. Empirical studies verify that, in real datasets, our two-step method can generate a maximum, or near-maximum, independent set. Our method, compared with the existing algorithms for the best-known produced kernels (VCSolver (Akiba and Iwata 2016) and ParFastKer (Hespe et al. 2018)), can achieve smaller kernels than ParFastKer with a similar kernelization processing speed, and achieve faster kernelization than VCSolver with a similar kernels.

La tesi versa sobre sistemes dinàmics discrets 1-dimensionals, des d'un punt de vista combinatori i topològic. Estem interessats en les òrbites periòdiques i l'entropia topològica de les aplicacions contínues definides en arbres i grafs.
El problema central és la caracterització del conjunt de períodes de totes les òrbites periòdiques d'una aplicació contínua d'un arbre en ell mateix. El teorema de Sharkovskii (1964) fou el primer resultat remarcable en aquest sentit. Aquest bonic teorema estableix que el conjunt de períodes d'una aplicació de l'interval és un segment inicial d'un ordre lineal (ordre de Sharkovskii). Recíprocament, donat qualsevol segment inicial d'aquest ordre, existeix una aplicació de l'interval que el té com a conjunt de períodes.
Durant les darreres dècades hi ha hagut diversos intents de trobar resultats similars al de Sharkovskii per a altres espais 1-dimensionals. Recentment, el cas d'arbres ha estat tractat especialment. El Teorema de Baldwin (1991) resol el problema en el cas de les n-estrelles i ha estat un dels avenços més significatius en aquesta direcció. Aquest resultat estableix que el conjunt de períodes per a una aplicació de la n-estrella és unió finita de segments inicials de n ordres parcials (ordres de Baldwin), i recíprocament.
El nostre objectiu principal és descriure l'estructura del conjunt de períodes de qualsevol aplicació contínua d'un arbre T en termes de les propietats combinatòries i topològiques de T: quantitat i disposició d'extrems, vèrtexs i arestes. En el capítol 1 discutim detalladament la manera més natural d'atacar el problema, i proposem una estratègia consistent en tres etapes consecutives. L'eina principal d'aquesta estratègia són els models minimals de patrons. Aquestes nocions es van desenvolupar i utilitzar durant les darreres dècades en el context de l'interval. En canvi, no es disposava de definicions operatives equivalents per a arbres, fins que al 1997 Alseda, Guaschi, Los, Manyosas i Mumbru proposaren de definir el patró d'un conjunt finit invariant P essencialment com una classe d'homotopia d'aplicacions relativa a P, i provaren (constructivament) que sempre existeix un model P-canònic amb propietats de minimalitat dinàmica.
L'objectiu del capítol 2 és implementar completament el programa proposat, duent a terme les etapes 2 i 3. El resultat principal d'aquest capítol diu que, donada una aplicació g definida en un arbre T, existeix un conjunt S de successions finites d'enters positius tal que el conjunt de períodes de g és (excepte un conjunt finit explícitament acotat) una unió finita de segments inicials d'ordres de Baldwin donats en termes del conjunt S, que depèn de les propietats combinatòries de l'arbre T. També provem el recíproc.
En el capítol 3 duem a terme experiments informàtics sobre la minimalitat dinàmica dels models canònics. En un esperit de programació modular, hem dissenyat moltes funcions autocontingudes que poden ser usades per implementar una gran varietat d'aplicacions d'ús divers. Entre altres, tenim funcions que calculen el model canònic d'un patró donat per l'usuari, calculen la matriu de Markov associada a un model monòton a trossos i extreuen tots els llaços simples d'una matriu de transició de Markov.
Finalment, en el capítol 4 generalitzem alguns resultats de Block i Coven, Misiurewicz i Nitecki i Takahashi, en els quals l'entropia topològica d'una aplicació de l'interval s'aproxima per les entropies de les seves òrbites periòdiques. Hem provat relacions anàlogues en el context de les aplicacions de grafs.
This memoir deals with one-dimensional discrete dynamical systems, from both a topological and a combinatorial point of view. We are interested in the periodic orbits and topological entropy of continuous self-maps defined on trees and graphs.
The central problem is the characterisation of the set of periods of all periodic orbits exhibited by any continuous map from a tree into itself. The Sharkovskii's Theorem (1964) was the first remarkable result in this setting. This theorem states that the set of periods of any interval map is an initial segment of a linear ordering (the so-called Sharkovskii ordering). Conversely, given any initial segment of the Sharkovskii ordering, there exists an interval map whose set of periods coincides with it.
During the last decades there have been several attempts to find results similar to that of Sharkovskii for other one-dimensional spaces. Recently, the case of maps defined on general trees has been specially treated. Baldwin's Theorem (1991), which solves the problem in the case of n-stars for any n, has been one of the most significant advances in this direction. This result states that the set of periods of any n-star map is a finite union of initial segments of n-many partial orderings (the Baldwin orderings). The converse is also true.
Our main purpose is to describe the generic structure of the set of periods of any continuous self-map defined on a tree T in terms of the combinatorial and topological properties of T: amount and arrangement of endpoints, vertices and edges. In Chapter 1 we make a detailed discussion about which is the more natural approach to this problem, and we propose a strategy consisting on three consecutive stages and using minimal models of patterns as the main tool. These notions were developed in the context of interval maps and widely used in a number of papers during the last two decades. However, equivalent operative definitions for tree maps were not available until 1997, when Alseda, Guaschi, Los, Manosas and Mumbru proposed to define the pattern of a finite invariant set P essentially as a homotopy class of maps relative to the points of P, and proved (constructively) that there always exists a P-canonical model displaying dynamic minimality properties.
The goal of Chapter 2 is to implement in full the above programme by completing stages 2 and 3. The main result of Chapter 2 tells us that for each tree map g defined on a tree T there exists a finite set S of sequences of positive integers such that the set of periods of g is (up to an explicitly bounded finite set) a finite union of initial segments of Baldwin orderings, given in terms of the set S, which depends on the combinatorial properties of the tree T. We also prove the converse result.
In Chapter 3 we report some computer experiments on the minimality of the dynamics of canonical models. In a spirit of modular programming, we have designed lots of self-contained functions which can be used to implement a wide variety of several-purpose software. Among other, we have functions that: compute the canonical model of a pattern provided by the user, calculate the Markov transition matrix associated to a piecewise monotone tree map and extract all the simple loops of a given length from a Markov transition matrix.
Finally, in Chapter 4 we generalize some results of Block & Coven, Misiurewicz & Nitecki and Takahashi, where the topological entropy of an interval map was approximated by the entropies of its periodic orbits. We prove analogous relations in the setting of graph maps.

Moore and Shannon's reliability polynomial can be used as a global statistic to explore the behavior of diffusive processes on a graph dynamical system representing a finite sized interacting system. It depends on both the network topology and the dynamics of the process and gives the probability that the system has a particular desired property. Due to the complexity involved in evaluating the exact network reliability, the problem has been classified as a NP-hard problem. The estimation of the reliability polynomials for large graphs is feasible using Monte Carlo simulations. However, the number of samples required for an accurate estimate increases with system size. Instead, an adaptive method using Bernstein polynomials as kernel density estimators proves useful. Network reliability has a wide range of applications ranging from epidemiology to statistical physics, depending on the description of the functionality. For example, it serves as a measure to study the sensitivity of the outbreak of an infectious disease on a network to the structure of the network. It can also be used to identify important dynamics-induced contagion clusters in international food trade networks. Further, it is analogous to the partition function of the Ising model which provides insights to the interpolation between the low and high temperature limits.
Ph. D.
The research presented here explores the effects of the structural properties of an interacting system on the outcomes of a diffusive process using Moore-Shannon network reliability. The network reliability is a finite degree polynomial which provides the probability of observing a certain configuration for a diffusive process on networks. Examples of such processes analyzed here are outbreak of an epidemic in a population, spread of an invasive species through international trade of commodities and spread of a perturbation in a physical system with discrete magnetic spins. Network reliability is a novel tool which can be used to compare the efficiency of network models with the observed data, to find important components of the system as well as to estimate the functions of thermodynamic state variables.

The fight against epidemics/pandemics is one of man versus nature. Technological advances have not only improved existing methods for monitoring and controlling disease outbreaks, but have also provided new means for investigation, such as through modeling and simulation. This dissertation explores the relationship between social structure and disease dynamics. Social structures are modeled as graphs, and outbreaks are simulated based on a well-recognized standard, the susceptible-infectious-removed (SIR) paradigm. Two independent, but related, studies are presented. The first involves measuring the severity of outbreaks as social network parameters are altered. The second study investigates the efficacy of various vaccination policies based on social structure. Three disease-related centrality measures are introduced, contact, transmission, and spread centrality, which are related to previously established centrality measures degree, betweenness, and closeness, respectively. The results of experiments presented in this dissertation indicate that reducing the neighborhood size along with outside-of-neighborhood contacts diminishes the severity of disease outbreaks. Vaccination strategies can effectively reduce these parameters. Additionally, vaccination policies that target individuals with high centrality are generally shown to be slightly more effective than a random vaccination policy. These results combined with past and future studies will assist public health officials in their effort to minimize the effects of inevitable disease epidemics/pandemics.

This thesis concerns the decentralized formation shape control of a set of homogeneous agents in the plane whose actuation dynamics are nonlinear and passive. The formation shape is specified by a subset of interagent distances. The formation is modeled as an undirected graph, with vertices representing the agents. An edge exists between two vertices if the specification provides the distance between them. Enough distances are assumed to have been specified to make the underlying graph rigid. Each agent executes its control law by measuring its relative positions from its neighbor and by knowing its absolute velocity. The control law is the same as previously proposed for a network where the agents have linear time invariant (LTI) passive dynamics. Despite the nonlinearity we show local convergence of this same law. The stability proof is in fact simpler than given in the LTI case through a redefinition of the state space. The results are verified by simulations that show that the control law can indeed stabilize under wider ranges of dynamics than previously perceived.

In recent years, several different methods have been proposed to compare brain networks with the joint use of graph theory and graph metrics. Another relatively unexplored comparison method is comparing the brain’s response to various input signals by simulating the brain’s dynamics. The brain activity signals are dependent on the physical connectivity patterns of the brain, therefore brain activity signals can be studied in addition to the study of connectivity patterns of brain graphs. Thus, in this study we use both static graph metrics and the dynamics of the brain to compare the brain networks of healthy test subjects and of patients with mild cognitive impairment (MCI). This was done by measuring and comparing the characteristic path length, clustering coefficient, small worldness and average degree distribution of each subject, as well as the Fourier transform amplitude at the frequency of the induced input signal. The result showed that the static graph metrics small worldness and clustering coefficient showed a small difference between the two groups. Differences between the two groups could also be observed with regards to the metric measured on the dynamics, however only between individual brain regions of the brain networks and only at certain input frequencies. The lack of consistency in these results hinders us from drawing deductions about this metric’s ability to differentiate the two groups. However, the study showed compelling enough results to argue for further research in comparing brain network with the use of simulated dynamics.
På senare år har flera olika metoder för att jämföra hjärnans nätverk framställts med hjälp av grafteori och olika statiska graf mätetal. En relativt outforskad jämförelsemetod är att jämföra påverkan som stimulanssignaler har på hjärnan med hjälp av att simulera hjärnans systemdynamik med stimulanssignaler av olika frekvenser som indata in i hjärnnätverket. Eftersom hjärnaktivitetssignaler är beroende av hjärnans struktur, kan man studera hjärnaktivitetssignaler tillsammans med hjärnans struktur. Följaktligen, ämnar denna studie att jämföra hjärnnätverken av patienter med mild kognitiv nedsättning (MCI) och av friska kontrolldeltagare genom att jämföra statiska graf mätetal och den påverkan som simulerade stimulanssignaler av varierande frekvenser har på hjärnan. Detta gjordes genom att jämföra graf mätetalen characteristic path length, clustering koefficient, small worldness och den genomsnittliga grad distributionen, samt att jämföra Fourier transform amplituden vid frekvensen av stimulanssignalen av varje deltagares hjärnnätverk vid sex olika tidpunkter. Studiens resultat visade på att de statiska graf mätetalen small worldness och clustering- koefficient kunde måttligen skilja grupperna. Skillnader mellan de två deltagargrupperna kunde även observeras vid vissa individuella hjärnregioner som utgör hjärnnätverken när Fourier transform amplituden vid stimulanssignalens frekvens användes som mätetal. Eftersom mätetalets resultater inte var homogena över hela datamängden, kan inte vi dra slutsatser om mätetalets förmåga att urskilja MCI patienter från friska kontrolldeltagare. Dock har studiens resultat visat tillräckligt övertalande tecken på att simuleringen av hjärnans systemdynamik med stimulanssignaler skulle kunne urskilja hjärnnätverk för att uppmana till vidare forskning kring denna jämförelsemetod.

This thesis is composed of two complementary projects. One focuses on the study of the dynamics between emotional and cognitive networks in healthy subjects using functional magnetic resonance imaging (fMRI). The second project builds on the results obtained in healthy subjects to formulate a computational model of the physiopathology and treatment mechanisms in major depression disorder (MDD). 1. Graph-based analysis on the emotional-cognitive demands The regulation of cognitive and emotional processes is critical for diverse functions such as attention, problem solving, error detection, motivation, decision making and social behavior. Dysregulation of these processes is at the core of Major Depressive Disorder (MDD). Currently neuroimaging and anatomical methods applied to emotional and cognitive processes present two views of brain organization: one view presents a considerable degree of functional specialization and the other view proposes that cognition and emotion are integrated in the brain. Here, we address this issue by studying the network topology underlying the competitive interactions between emotional and cognitive networks in healthy subjects. To this end, we designed a task that contrasted periods with very high emotional and cognitive demands. We concatenated two tasks: A Sadness Provocation (SP) followed by a Spatial Working Memory (WM) task. We hypothesized that this behavioral paradigm would enhance the modularity of emotional and cognitive brain networks and would reveal the cortical areas that act as network hubs, which are critical for regulating the flow and integration of information between regions. We collected fMRI data from 22 healthy subjects performing this task. We analyzed their brain activity with a general linear model, looking for activation patterns linked to the various phases of the tasks, which we then used to extract 20 regions of interest (ROI) on a subject-by-subject basis. We computed the correlations between fMRI time series in pairs of ROIs, obtaining a matrix of correlations for each subject, and we then applied network measures from graph theory. Subjects that scored highest their sadness intensity showed a more marked decrease in their cognitive performance after SP, and presented stronger activity in subgenual anterior cingulate cortex (sACC) and weaker activity in dorsolateral prefrontal cortex (dlPFC). The network analysis identified two main modules, one cognitive and one emotional. Analysis of connectivity degree and participation coefficient identified the areas that acted as hubs and their modulation: the left dlPFC degree decreased after sadness provocation and the left medial frontal pole (mFP) degree was modulated by sadness intensity. Functional connectivity analyses revealed that these hub areas modulated their connectivity following sadness experience: dlPFC and sACC showed stronger anticorrelation, and mFP and sACC strengthened their correlation. Our results identify the hubs that mediate the interaction between emotional and cognitive networks in a context of high emotional and cognitive demands, and they suggest possible targets to develop new therapeutic strategies for mood disorders. 2. A computational model of Major Depression Several lines of evidence associate major depressive disorder (MDD) with a dysfunction of cingulo-frontal network dynamics following glutamate metabolism dysfunction in the ventral anterior cingulate cortex (vACC). However, we still lack a mechanistic framework to understand how these alterations underlie MDD and how treatments improve depression symptoms. We built a biophysical computational model of two cortical areas (vACC, and dorso-lateral prefrontal cortex, dlPFC) that acts as a switch between emotional and cognitive processing: the two areas cannot be co-active due to effective mutual inhibition. We simulated MDD by slowing down glutamate decay in vACC, serotonergic treatments (SSRI) by activating serotonin 1A receptors in vACC, and deep brain stimulation by periodic stimulation of vACC interneurons at 130 Hz. We analyzed network dynamics mathematically in a simpler firing rate network model, and we derived the conditions for the emergence of cortical oscillations. MDD networks differed from healthy networks in that vACC presented constant activation in the absence of emotional inputs, which was not suppressed by dlPFC activation. In turn, vACC hyper-activation prevented dlPFC from responding to cognitive signals, mimicking cognitive dysfunction in MDD. SSRI counteracted aberrant vACC activity but it also abolished its normal response to emotional stimuli. In treatment-resistant models, DBS treatment restored the switch function. Activity oscillations in the theta and beta/gamma bands correlated with network function, representing a marker of switch-like operation in the network. The model articulates mechanistically how glutamate deficits generate aberrant vACC dynamics, and how this underlies emotional and cognitive symptoms in MDD. The model accounts for the progression of depression, dose-dependent SSRI treatment, DBS treatment of treatment-resistant models and EEG rhythmic biomarkers in a biophysical model of the pathophysiology of MDD.
Esta tesis se compone de dos proyectos complementarios. Uno se centra en el estudio de la dinámica entre redes emocionales y cognitivas en sujetos sanos utilizando imágenes de resonancia magnética funcional (fMRI). El segundo proyecto se basa en los resultados obtenidos en sujetos sanos para formular un modelo computacional de los mecanismos fisiopatológicos y tratamientos en el trastorno de depresión mayor (MDD). 1. Análisis de grafos en función de las demandas emocionales cognitiva La regulación de los procesos cognitivos y emocionales es fundamental para diversas funciones como la atención, resolución de problemas, la detección de errores, la motivación, la toma de decisiones y el comportamiento social. La desregulación de estos procesos está en el núcleo del trastorno depresivo mayor (MDD). Actualmente métodos de neuroimagen y anatómicos aplicados a los procesos emocionales y cognitivos presentan dos puntos de vista acerca de la organización del cerebro: un punto de vista presenta un alto grado de especialización funcional y el otro punto de vista propone que la cognición y la emoción se integran en el cerebro. Aquí, abordamos esta cuestión mediante el estudio de la topología de red subyacente durante interacciones competitivas entre las redes emocionales y cognitivos en sujetos sanos. Para ello, hemos diseñado una tarea que contrasta períodos muy altas demandas emocionales y cognitivas. Concatenamos dos tareas: una provocación tristeza (SP), seguida de una tarea de memoria de trabajo espacial (WM). La hipótesis es que este paradigma conductual mejoraría la modularidad de las redes cerebrales emocionales y cognitivas y revelaría las áreas corticales que actúan como hub de la red, que son fundamentales para regular el flujo y la integración de información entre regiones. Se recogieron datos de la fMRI de 22 sujetos sanos que realizan esta tarea. Se analizó su actividad cerebral con un modelo general lineal, en busca de patrones de activación ligados a las diversas fases de las tareas, que luego utilizamos para extraer 20 regiones de interés (ROI) para cada sujeto. Hemos calculado las correlaciones entre las series de tiempo de fMRI para pares de regiones de interés, y construimos una matriz de correlaciones para cada sujeto, y luego aplicamos medidas de red desde la teoría de grafos. Los sujetos que puntuaron más alto su intensidad tristeza mostraron una más marcada disminución en su rendimiento cognitivo después de SP, y presentaron una mayor actividad en la corteza anterior cingulada subgenual (sACC) y la actividad más débil en la corteza prefrontal dorsolateral (dlPFC). El análisis de redes identificó dos módulos principales, uno cognitivo y otro emocional. Análisis del grado de conectividad y el coeficiente de participación identificaron las áreas que actuaban como hub y su modulación: el grado del dlPFC disminuyó después de la provocación tristeza y el grado del polo medial frontal (mFP) fue modulada por la intensidad de la tristeza. Los análisis de conectividad funcional reveló que estas áreas modulan su conectividad dependiendo de la experiencia de tristeza: dlPFC y sACC mostraron anticorrelación más fuerte, y mFP y sACC aumentaron su correlación positiva en los sujetos que más se entristecieron. Nuestros resultados identifican los hub que median la interacción entre redes emocionales y cognitivos en un contexto de altas demandas emocionales y cognitivas, y sugieren posibles objetivos para desarrollar nuevas estrategias terapéuticas para los trastornos del estado de ánimo. 2. Modelo computacional para la depresión mayor Varias líneas de evidencia asocian el trastorno depresivo mayor (TDM) con una disfunción de la dinámica de la red cíngulo-frontal, y especialmente una disfunción en el metabolismo del glutamato en la corteza cingulada anterior ventral (vACC). Sin embargo, todavía carecemos de un marco mecanicista para entender cómo estas alteraciones subyacen TDM y cómo los tratamientos mejoran los síntomas de depresión. Construimos un modelo biofísico computacional de dos áreas corticales (vACC y dlPFC) que actúa como un interruptor entre el procesamiento emocional y cognitivo: las dos áreas no pueden ser co-activo debido a la inhibición mutua eficaz. Hemos simulado el TDM por enlentecimiento en la recaptura del glutamato en vACC, los tratamientos serotoninérgicos (ISRS) mediante la activación de los receptores de serotonina 1A en vACC y la estimulación cerebral profunda mediante la estimulación periódica de interneuronas en el vACC a 130 Hz (DBS). Se analizó la dinámica de la red matemáticamente en un modelo de red tasa de disparo más simple, y derivamos las condiciones para la aparición de oscilaciones corticales. Las redes TDM difieren de las redes sanas en que vACC presentó activación constante en ausencia de estímulos emocionales, que no fue suprimida por la activación dlPFC. A su vez, la hiper-activación del vACC impidió al dlPFC responder a los estímulos cognitivos, imitando la disfunción cognitiva del TDM. ISRS contrarrestaron actividad aberrante en el vACC pero también abolió su respuesta normal a los estímulos emocionales. En los modelos resistentes al tratamiento, el tratamiento DBS restauró la función de interruptor. Oscilaciones en las bandas theta y beta/gamma correlacionaron con la función de red, específicamente con el rango bistable, lo que representa un marcador de operación de interruptor de la red. El modelo articula mecánicamente cómo el déficit en el metabolismo del glutamato genera dinámicas aberrantes en vACC, y cómo esto subyace síntomas emocionales y cognitivos en el TDM. El modelo representa la progresión de la depresión, la respuesta (dependiente de dosis) al tratamiento con ISRS, como DBS rescata la función de la red en modelos resistentes al tratamiento y explica porque las oscilaciones son biomarcadores, en un modelo biofísico de la fisiopatología del trastorno depresivo mayor.

Modelling mechanical systems using symbolic equations can provide many advantages over the more widely-used numerical methods of modelling these systems. The use of symbolic equations produces more efficient models, which can be used for many purposes such as real-time simulation and control. However, the number, complexity, and computational efficiency of these equations is highly dependent on which coordinate set was used to model the system. One method of modelling a mechanism's topology and formulating its symbolic equations is to model the system using a graph-theoretical approach. This approach models mechanisms using a linear graph, from which spanning trees can be used to define a mechanism's coordinate set. This report develops two tree selection algorithms capable of estimating the tree set, and hence coordinate set, that produces models having the fastest forward dynamic simulation times. The first tree selection algorithm is a heuristic-based algorithm that tries to find the coordinate set containing the minimal possible number of modelling variables. Most of this algorithm's heuristics are based on tree selection criteria found in the literature and on observations of a series of benchmark problems. It uses the topology information provided by a system's graph to find the coordinates set for the given system that produce very low simulation times of the system. The second tree selection algorithm developed in this report also uses graph theory. It bases most of its heuristics on observations of one of the methods developed to obtain a mechanical system's symbolic equations using graph theory. This second algorithm also makes use of, and improves upon, a few of the heuristics developed in the first tree selection algorithm. A series of examples for both algorithms will demonstrate the computational efficiency obtained by using the modelling variables found by the automated tree selection algorithms that are proposed in this report.

Many novel graph neural network models have reported an impressive performance on benchmark dataset, but the theory behind these networks is still being developed. In this thesis, we study the trajectory of Gradient descent (GD) and Stochastic gradient descent (SGD) in the loss landscape of Graph neural networks by replicating Xing et al. [1] study for feed-forward networks. Furthermore, we empirically examine if the training process could be accelerated by an optimization algorithm inspired from Stochastic gradient Langevin dynamics and what effect the topology of the graph has on the convergence of GD by perturbing its structure. We find that the loss landscape is relatively flat and that SGD does not encounter any significant obstacles during its propagation. The noise-induced gradient appears to aid SGD in finding a stationary point with desirable generalisation capabilities when the learning rate is poorly optimized. Additionally, we observe that the topological structure of the graph plays a part in the convergence of GD but further research is required to understand how.
Många nya grafneurala nätverk har visat imponerande resultat på existerande dataset, dock är teorin bakom dessa nätverk fortfarande under utveckling. I denna uppsats studerar vi banor av gradientmetoden (GD) och den stokastiska gradientmetoden (SGD) i lösningslandskapet till grafiska faltningsnätverk genom att replikera studien av feed-forward nätverk av Xing et al. [1]. Dessutom undersöker vi empiriskt om träningsprocessen kan accelereras genom en optimeringsalgoritm inspirerad av Stokastisk gradient Langevin dynamik, samt om grafens topologi har en inverkan på konvergensen av GD genom att ändra strukturen. Vi ser att lösningslandskapet är relativt plant och att bruset inducerat i gradienten verkar hjälpa SGD att finna stabila stationära punkter med önskvärda generaliseringsegenskaper när inlärningsparametern har blivit olämpligt optimerad. Dessutom observerar vi att den topologiska grafstrukturen påverkar konvergensen av GD, men det behövs mer forskning för att förstå hur.

This dissertation is made up of two independent parts. In Part I we consider the Pestov Identity, an identity stated for smooth functions on the tangent bundle of a manifold and linking the Riemannian curvature tensor to the generators of the geodesic flow, and we lift it to the bundle of k-tuples of tangent vectors over a compact manifold M of dimension n. We also derive an integrated version over the bundle of orthonormal k-frames of M as well as a restriction to smooth functions on such a bundle. Finally, we present a dynamical application for the parallel transport of the Grassmannian of oriented k-planes of M. In Part II we consider a family of compact and connected n-dimensional manifolds, called graph-like manifold, shrinking to a metric graph in the appropriate limit. We describe the asymptotic behaviour of the eigenvalues of the Hodge Laplacian acting on differential forms on those manifolds in the appropriate limit. As an application, we produce manifolds and families of manifolds with arbitrarily large spectral gaps in the spectrum of the Hodge Laplacian.

Agent-based epidemic simulation (ABES) is a powerful and realistic approach for studying the impacts of disease dynamics and complex interventions on the spread of an infection in the population. Among many ABES systems, EpiSimdemics comes closest to the popular agent-based epidemic simulation systems developed by Eubank, Longini, Ferguson, and Parker. EpiSimdemics is a general framework that can model many reaction-diffusion processes besides the Susceptible-Exposed-Infectious-Recovered (SEIR) models. This model allows the study of complex systems as they interact, thus enabling researchers to model and observe the socio-technical trends and forces. Pandemic planning at the world level requires simulation of over 6 billion agents, where each agent has a unique set of demographics, daily activities, and behaviors. Moreover, the stochastic nature of epidemic models, the uncertainty in the initial conditions, and the variability of reactions require the computation of several replicates of a simulation for a meaningful study. Given the hard timelines to respond, running many replicates (15-25) of several configurations (10-100) (of these compute-heavy simulations) can only be possible on high-performance clusters (HPC). These agent-based epidemic simulations are irregular and show poor execution performance on high-performance clusters due to the evolutionary nature of their workload, large irregular communication and load imbalance. For increased utilization of HPC clusters, the simulation needs to be scalable. Many challenges arise when improving the performance of agent-based epidemic simulations on high-performance clusters. Firstly, large-scale graph-structured computation is central to the processing of these simulations, where the star-motif quality nodes (natural graphs) create large computational imbalances and communication hotspots. Secondly, the computation is performed by classes of tasks that are separated by global synchronization. The non-overlapping computations cause idle times, which introduce the load balancing and cost estimation challenges. Thirdly, the computation is overlapped with communication, which is difficult to measure using simple methods, thus making the cost estimation very challenging. Finally, the simulations are iterative and the workload (computation and communication) may change through iterations, as a result introducing load imbalances. This dissertation focuses on developing a cost estimation model and load balancing schemes to increase the runtime efficiency of agent-based epidemic simulations on high-performance clusters. While developing the cost model and load balancing schemes, we perform the static and dynamic load analysis of such simulations. We also statically quantified the computational and communication workloads in EpiSimdemics. We designed, developed and evaluated a cost model for estimating the execution cost of large-scale parallel agent-based epidemic simulations (and more generally for all constrained producer-consumer parallel algorithms). This cost model uses computational imbalances and communication latencies, and enables the cost estimation of those applications where the computation is performed by classes of tasks, separated by synchronization. It enables the performance analysis of parallel applications by computing its execution times on a number of partitions. Our evaluations show that the model is helpful in performance prediction, resource allocation and evaluation of load balancing schemes. As part of load balancing algorithms, we adopted the Metis library for partitioning bipartite graphs. We have also developed lower-overhead custom schemes called Colocation and MetColoc. We performed an evaluation of Metis, Colocation, and MetColoc. Our analysis showed that the MetColoc schemes gives a performance similar to Metis, but with half the partitioning overhead (runtime and memory). On the other hand, the Colocation scheme achieves a similar performance to Metis on a larger number of partitions, but at extremely lower partitioning overhead. Moreover, the memory requirements of Colocation scheme does not increase as we create more partitions. We have also performed the dynamic load analysis of agent-based epidemic simulations. For this, we studied the individual and joint effects of three disease parameter (transmissiblity, infection period and incubation period). We quantified the effects using an analytical equation with separate constants for SIS, SIR and SI disease models. The metric that we have developed in this work is useful for cost estimation of constrained producer-consumer algorithms, however, it has some limitations. The applicability of the metric is application, machine and data-specific. In the future, we plan to extend the metric to increase its applicability to a larger set of machine architectures, applications, and datasets.
Ph. D.

Graphs are a commonly used abstraction for diverse kinds of interactions, e.g., on Twitter and Facebook. Different kinds of topological properties of such graphs are computed for gaining insights into their structure. Computing properties of large real networks is computationally very challenging. Further, most real world networks are dynamic, i.e., they change over time. Therefore there is a need for efficient dynamic algorithms that offer good space-time trade-offs. In this thesis we study the problem of computing the reachability set size of a vertex, which is a fundamental problem, with applications in databases and social networks. We develop the first Giraph based algorithms for different dynamic versions of these problems, which scale to graphs with millions of edges.
Master of Science

In view of the fact that a same complex phenomenon can be approached by different conceptual frameworks, it is natural to inquire on the possibility to find connections between different types of quantities, such as topological, dynamical, statistical or thermodynamical, characterizing the same system. The present work is built on the idea that this line of approach can provide interesting insights on possible universal principles governing complex phenomena. In Chapter I we introduce concepts and tools of dynamical systems and thermodynamics as applied in macroscopic scale description as well as, for a later use, a number of selected representative models. In Chapter II we briefly present the elements of the theory of Markov processes describing a large class of stochastic process and also introduce some important concepts on the probabilistic description of deterministic systems. This chapter ends with a thermodynamic formulation accounting for the evolution of the entropy under the effect of stochastic fluctuations. In Chapter III, after introducing the main concepts and recent advances in network theory, we provide a connection between dynamical systems and network theory, which shows how universal structural properties of evolving networks can arise from deterministic dynamics. More specifically, we show explicitly the relation between the connectivity patterns of these networks and the indicators of the underlying dynamics, such as the local Lyapunov exponents. Our analysis is applied to representative models of chaotic maps, chaotic flows and is finally extended to stochastic processes. In Chapter IV we address the inverse problem, namely, processes whose dynamics is determined, in part, by the structure of the network in which they are embedded. In particular, we focus on systems of particles diffusing on a lattice and reacting instantaneously upon encountering each other. We study the role of the topology, the degree of synchronicity of motion and the reaction mechanism on the efficiency of the process. This lead us to identify a common generic mechanism responsible for the behavior of the efficiency, as a function of the control parameters. Finally, in Chapter V we study the connection between the topology and the thermodynamic properties of reaction networks, with focus on the entropy production and the system’s efficiency at nonequilibrium steady states. We also explore the connection between dynamic and thermodynamic properties of nonlinear feedbacks, as well as the response properties of reaction networks against both deterministic and stochastic external perturbations. We address networks of varying topologies, from regular lattices to complex structures./Le présent travail s’inscrit dans le domaine de recherche sur les systèmes complexes. Différentes approches, basées des systèmes dynamiques, de la thermodynamique des systèmes hors d’équilibre, de la physique statistique et, plus récemment, de la théorie des réseaux, sont combinés afin d’explorer des liens entre différentes types de grandeurs qui caractérisent certaines classes de comportements complexes. Dans le Chapitre I nous introduisons les principaux concepts et outils de systèmes dynamiques et de thermodynamique. Dans le Chapitre II nous présentons premièrement des éléments de la théorie de processus de Markov, ainsi que les concepts à la base de la description probabiliste des systèmes déterministes. Nous finissons le chapitre en proposant une formulation thermodynamique qui décrit l’évolution de l’entropie hors d’équilibre, soumis à l’influence de fluctuations stochastiques. Dans le Chapitre III nous introduisons les concepts de base en théorie des réseaux, ainsi qu’un résumé générale des progrès récents dans le domaine. Nous établissons ensuite une connexion entre la théorie des systèmes dynamiques et la théorie de réseaux. Celle-ci permet d’approfondir la compréhension des mécanismes responsables de l’émergence des propriétés structurelles dans des réseaux crées par des lois dynamiques déterministes. En particulier, nous mettons en évidence la relation entre des motifs de connectivité de ce type de réseaux et des indicateurs de la dynamique sous-jacente, tel que des exposant de Lyapounov locaux. Notre analyse est illustrée par des applications et des flots chaotiques et étendue à des processus stochastiques. Dans le Chapitre IV nous étudions le problème complémentaire, à savoir, celui de processus dont la dynamique est déterminée, en partie, par la structure du réseau dans lequel elle se déroule. Plus précisément, nous nous concentrons sur le cas de systèmes de particules réactives, diffusent au travers d’un réseau et réagissant instantanément lorsqu’un rencontre se produit entre elles. Nous étudions le rôle de la topologie, du degré de synchronicité des mouvements et aussi celui du mécanisme de réaction sur l’efficacité du processus. Dans les différents modèles étudiés, nous identifions un mécanisme générique commun, responsable du comportement de l’efficacité comme fonction des paramètres de contrôle. Enfin, dans le Chapitre V nous abordons la connexion entre la topologie et les propriétés thermodynamiques des réseaux de réactions, en analysant le comportement local et global de la production d’entropie et l’efficacité du système dans des état stationnaires de non-équilibre. Nous explorons aussi la connexion entre la dynamique et les propriétés de boucles de rétroaction non linéaires, ainsi que les propriétés de réponse des réseaux de réaction à des perturbations stochastiques et déterministes externes. Nous considérons le cas de réseaux à caractère régulier aussi bien que celui de réseaux complexes.

Doctorat en Sciences
info:eu-repo/semantics/nonPublished

We broaden the theory of dynamical interpretation, investigate the property of commutativity and explore the subject of subgroups forming free products in Thompson's group V. We expand Brin's terminology for a revealing pair to an any tree pair. We use it to analyse the dynamical behaviour of an arbitrary tree pair which cannot occur in a revealing pair. Hence, we design a series of algorithms generating Brin's revealing pair from any tree pair, by successively eliminating the undesirable structures. To detect patterns and transitioning between tree pairs, we introduce a new combinatorial object called the chains graph. A newly defined, unique and symmetrical type of a tree pair, called a balanced tree pair, stems from the use of the chains graphs. The main theorem of Bleak et al. in "Centralizers in the R. Thompson's Group V_n" states the necessary structure of the centraliser of an element of V. We provide a converse to this theorem, by proving that each of the predicted structures is realisable. Hence we obtain a complete classification of centralisers in V. We give an explicit construction of an element of V with prescribed centraliser. The underlying concept is to embed a Cayley graph of a finite group into the flow graph (introduced in Bleak et al.) of the desired element. To reflect the symmetry, we present the resulting element in terms of a balanced tree pair. The group V is conjectured to be a universal coCF group, which generates interest in studying its subgroups. We develop a better understanding of embeddings into V by providing a necessary and sufficient dynamical condition for two subgroups (not both torsion) to form a free product in V. For this, we use the properties, explored in Bleak and Salazar-Díaz "Free Products in Thompson's Group V", of sets of so--called important points, and the Ping-Pong action induced on them.

The objective of this thesis is to provide a temporal analysis of the structural and interaction dynamics of large evolving graphs. In this thesis we propose new definitions of important graph metrics in order to include the temporal dimension of the dynamic graphs. We further extend the three important problems of data mining, in the temporal setting. The three problems that we propose are temporal graph summarization, temporal community search and temporal betweenness centrality. Additionally, we propose a distributed version of all our algorithms, that help our techniques to scale up to million vertices. We, finally, evaluate the validity of our methods in terms of efficiency and effectiveness with extensive experimentation on large-scale real-world graphs.
L’objectiu d’aquesta tesi és proporcionar una anàlisi temporal de l'evolució estructural i d’interacció de grans gràfics dinàmics. En aquesta tesi proposem noves definicions de mètriques de gràfiques importants per tal d’incloure la dimensió temporal dels gràfics dinàmics. Ampliem tres problemes importants de mineria de dades en gràfics per a un entorn temporal. Els tres problemes són el resum de gràfics temporals, la cerca temporal de comunitats i la centralitat temporal dels gràfics. A més, proposem una versió distribuïda de tots els nostres algoritmes, que ajuden a les nostres tècniques a escalar fins a milions de vèrtexs. Finalment, avaluem la validesa dels nostres mètodes en termes d’eficiència i eficàcia amb una àmplia experimentació en gràfics del món real a gran escala.
El objetivo de esta tesis es proporcionar un análisis temporal de las dinámicas estructurales y de interacción de grafos masivos dinámicos. Para esto proponemos nuevas definiciones de métricas en grafos importantes para incluir la dimensión temporal de los grafos dinámicos. Además, ampliamos tres problemas importantes de minería de datos en un contexto temporal. Ellos son los resúmenes de grafos temporales, la búsqueda de comunidades en un contexto temporal y la centralidad temporal en grafos. Además, proponemos una versión distribuida de todos nuestros algoritmos, que permiten que nuestras técnicas a escalar hasta millones de vértices. Finalmente, evaluamos la validez de nuestros métodos en términos de eficiencia y efectividad con extensos experimentos en gráfos de gran escala en el mundo real.

Enterprises use live video streaming as a mean of communication. Streaming high-quality video to thousands of devices in a corporate network is not an easy task; the bandwidth requirements often exceed the network capacity. For that matter, Peer-To-Peer (P2P) networks have been proven beneficial, as peers can exchange content efficiently by utilizing the topology of the corporate network. However, such networks are dynamic and their topology might not always be known. In this project we propose ABD, a new dynamic graph representation learning approach, which aims to estimate the bandwidth capacity between peers in a corporate network. The architecture of ABDis adapted to the properties of corporate networks. The model is composed of an attention mechanism and a decoder. The attention mechanism produces node embeddings, while the decoder converts those embeddings into bandwidth predictions. The model aims to capture both the dynamicity and the structure of the dynamic network, using an advanced training process. The performance of ABD is tested with two dynamic graphs which were produced by real corporate networks. Our results show that ABD achieves better results when compared to existing state-of-the-art dynamic graph representation learning models.
Företag använder live video streaming för både intern och extern kommunikation. Strömmning av hög kvalitet video till tusentals tittare i ett företagsnätverk är inte enkelt eftersom bandbreddskraven ofta överstiger kapaciteten på nätverket. För att minska lasten på nätverket har Peer-to-Peer (P2P) nätverk visat sig vara en lösning. Här anpassar sig P2P nätverket efter företagsnätverkets struktur och kan därigenom utbyta video data på ett effektivt sätt. Anpassning till ett företagsnätverk är ett utmanande problem eftersom dom är dynamiska med förändring över tid och kännedom över topologin är inte alltid tillgänglig. I det här projektet föreslår vi en ny lösning, ABD, en dynamisk approach baserat på inlärning av grafrepresentationer. Vi försöker estimera den bandbreddskapacitet som finns mellan två peers eller tittare. Architekturen av ABD anpassar sig till egenskaperna av företagsnätverket. Själva modellen bakom ABD använder en koncentrationsmekanism och en avkodare. Attention mekanismen producerar node embeddings, medan avkodaren konverterar embeddings till estimeringar av bandbredden. Modellen fångar upp dynamiken och strukturen av nätverket med hjälp av en avancerad träningsprocess. Effektiviteten av ABD är testad på två dynamiska nätverksgrafer baserat på data från riktiga företagsnätverk. Enligt våra experiment har ABD bättre resultat när man jämför med andra state-of the-art modeller för inlärning av dynamisk grafrepresentation.

Fundação de Amparo à Pesquisa do Estado do Rio de Janeiro
A Amazônia exibe uma variedade de cenários que se complementam. Parte desse ecossistema sofre anualmente severas alterações em seu ciclo hidrológico, fazendo com que vastos trechos de floresta sejam inundados. Esse fenômeno, entretanto, é extremamente importante para a manutenção de ciclos naturais. Neste contexto, compreender a dinâmica das áreas alagáveis amazônicas é importante para antecipar o efeito de ações não sustentáveis. Sob esta motivação, este trabalho estuda um modelo de escoamento em áreas alagáveis amazônicas, baseado nas equações de Navier-Stokes, além de ferramentas que possam ser aplicadas ao modelo, favorecendo uma nova abordagem do problema. Para a discretização das equações é utilizado o Método dos Volumes Finitos, sendo o Método do Gradiente Conjugado a técnica escolhida para resolver os sistemas lineares associados. Como técnica de resolução numérica das equações, empregou-se o Método Marker and Cell, procedimento explícito para solução das equações de Navier-Stokes. Por fim, as técnicas são aplicadas a simulações preliminares utilizando a estrutura de dados Autonomous Leaves Graph, que tem recursos adaptativos para manipulação da malha que representa o domínio do problema
Amazon exhibits a variety of scenarios that complement each other. Yearly, part of this ecosystem suffers severe changes in its hydrological cycle, causing flood through vast stretches of the forest. This phenomenon, however, is extremely important for the maintenance of natural cycles. In this context, understanding the Amazonian floodplains dynamics is important to anticipate the effect of unsustainable actions. Under this motivation, this work presents a study of an Amazonian floodplains flow model, based on Navier-Stokes equations, besides other tools that can be applied to the model, thus leading to a new approach to the problem. To discretize the model equations the Finite Volume Method was employed. To solve the associated linear systems the Conjugate Gradient Method technique was chosen. For numerical solution of the equations, the Marker and Cell Method, a explicit solution procedure for Navier-Stokes equations, was employed. All these techniques are applied to preliminary simulations using the Autonomous Leaves Graph algorithm which has adaptive features to manipulate the domain grid problem

Assessing complex brain activity as a function of the type of epilepsy and in the context of the 3D source of seizure onset remains a critical and challenging endeavor. In this dissertation, we tried to extract the attributes of the epileptic brain by looking at the modular interactions from scalp electroencephalography (EEG). A classification algorithm is proposed for the connectivity-based separation of interictal epileptic EEG from normal. Connectivity patterns of interictal epileptic discharges were investigated in different types of epilepsy, and the relation between patterns and the epileptogenic zone are also explored in focal epilepsy. A nonlinear recurrence-based method is applied to scalp EEG recordings to obtain connectivity maps using phase synchronization attributes. The pairwise connectivity measure is obtained from time domain data without any conversion to the frequency domain. The phase coupling value, which indicates the broadband interdependence of input data, is utilized for the graph theory interpretation of local and global assessment of connectivity activities. The method is applied to the population of pediatric individuals to delineate the epileptic cases from normal controls. A probabilistic approach proved a significant difference between the two groups by successfully separating the individuals with an accuracy of 92.8%. The investigation of connectivity patterns of the interictal epileptic discharges (IED), which were originated from focal and generalized seizures, was resulted in a significant difference ( ) in connectivity matrices. It was observed that the functional connectivity maps of focal IED showed local activities while generalized cases showed global activated areas. The investigation of connectivity maps that resulted from temporal lobe epilepsy individuals has shown the temporal and frontal areas as the most affected regions. In general, functional connectivity measures are considered higher order attributes that helped the delineation of epileptic individuals in the classification process. The functional connectivity patterns of interictal activities can hence serve as indicators of the seizure type and also specify the irritated regions in focal epilepsy. These findings can indeed enhance the diagnosis process in context to the type of epilepsy and effects of relative location of the 3D source of seizure onset on other brain areas.

The internal cushioning systems of hydraulic linear actuators, of special interest in mobile machinery, pursue to avoid mechanical shocks at their end of stroke. The design where the piston, with perimeter grooves, regulates the flow by standing in front of the outlet port has not been studied in depth until now. Consequently, the operating fundamentals, influencing factors and optimization of these cushioning designs have been investigated. First, a dynamic model has been developed using the bond graph technique that integrates the mechanical equations of the actuator, the hydraulic circuit and the flow through the studied internal cushion design. This considers the evolution of internal flow during cushioning, characterized in detail by fluid-dynamic simulation. This CFD model has been validated experimentally for its refinement and well-founded determination of discharge coefficients. Subsequently, the complete dynamics of the actuator and, in particular, the radial movement of the piston are experimentally studied by means of the difficult installation of a sophisticated displacement sensor. Finally, the experimental observations and the fluid-dynamic coefficients are integrated into the dynamic model; ultimately, the model aims to predict the experimental behavior of the cushioning during the movement of the arm of an excavator. The radial movement of the observed piston turns it into an active and adjusting element that is essential in cushioning. This radial movement in coherence with the significant drag force estimated in the CFD simulation, generated by the flow through the grooves, where the laminar flow regime predominates. Analytical models are suitable for predicting the behavior of the cushioning system, observing results comparable to those experimentally obtained . There is an optimal behavior, highly influenced by the mechanical stress conditions of the system, subject to a compromise between an increasing section of the grooves and an optimization of the radial gap. In addition, given the difficult direct measurement of the radial movement of the piston, an indirect measurement method has been evaluated using low-cost accelerometers. Thus, a bond graph simulation model predicts the results of the double integration of acceleration, observed experimentally. Influenced by the diverse nature of the existing movements, the severe propagation of measurement errors makes indirect measurement of piston radial motion inadequate.
Los sistemas internos de amortiguación de actuadores lineales hidráulicos, de especial interés en maquinaria móvil, buscan evitar choques mecánicos en sus finales de carrera. El diseño donde el pistón, dispuesto con ranuras perimetrales, regula el flujo al interponerse frente al puerto de salida no ha sido estudiado en profundidad hasta ahora. En consecuencia, se han investigado las bases de funcionamiento, los factores de influencia y la optimización de estos diseños de amortiguación. Primeramente, se ha desarrollado un modelo dinámico mediante la técnica bond graph que integra las ecuaciones mecánicas propias del actuador, del circuito hidráulico y del flujo a través del amortiguador interno estudiado. Éste considera la evolución del flujo interno durante la amortiguación, caracterizada detalladamente mediante simulación fluido-dinámica. Este modelo CFD ha sido validado experimentalmente para su refinamiento y la determinación fundada de los coeficientes de descarga. Seguidamente, se estudia experimentalmente la dinámica completa del actuador y, en especial, el movimiento radial del pistón mediante la difícil instalación de un sofisticado sensor de desplazamiento. Finalmente, las observaciones experimentales y los coeficientes fluido-dinámicos se integran en el modelo dinámico; éste pretende, en última instancia, prever el comportamiento experimental de la amortiguación del actuador durante el movimiento del brazo de una retroexcavadora. El movimiento radial del pistón observado convierte éste en un elemento activo fundamental en la amortiguación. Este movimiento radial es coherente con la significativa fuerza de empuje estimada en la simulación CFD, generada por el flujo a través de las ranuras, donde predomina el régimen laminar. Los modelos analíticos se muestran adecuados para la predicción del comportamiento del sistema de amortiguación, observándose resultados comparables a los obtenidos experimentalmente. Existe un comportamiento óptimo, influenciado en gran medida por las condiciones de solicitación mecánica del sistema, sujeto a un compromiso entre una sección creciente de las ranuras y una optimización del espacio radial. Complementariamente, dada la complicada medida directa del movimiento radial del pistón, se ha evaluado la medida indirecta mediante acelerómetros de bajo coste. Así, un modelo de simulación bond graph predice los resultados de la doble integración de la aceleración, observados experimentalmente. Influenciada por la diversa naturaleza de los movimientos presentes, la severa propagación de los errores de medida hace inadecuada la medida indirecta del movimiento radial del pistón.

Knowledge diffusion networks consist of individuals who exchange knowledge and knowledge flows connecting the individuals. By studying knowledge diffusion in a network perspective, it helps us understand how the connections between individuals affect the knowledge diffusion processes. Existing research on knowledge diffusion networks mostly adopts a uni-dimensional perspective, where all the individuals in the networks are assumed to be of the same type. It also assumes that there is only one type of knowledge flow in the network. This dissertation proposes a multi-dimensional perspective of knowledge diffusion networks and examines the patterns of knowledge diffusion with Exponential Random Graph Model (ERGM) based approaches. The objective of this dissertation is to propose a framework that effectively addresses the multi-dimensionality of knowledge diffusion networks, to enable researchers and practitioners to conceptualize the multi-dimensional knowledge diffusion networks in various domains, and to provide implications on how to stimulate and control the knowledge diffusion process. The dissertation consists of three essays, all of which examine the multi-dimensional knowledge diffusion networks in a specific context, but each focuses on a different aspect of knowledge diffusion. Chapter 2 focuses on how structural properties of networks affect various types of knowledge diffusion processes in the domain of commercial technology. The study uses ERGM to simultaneously model multiple types of knowledge flows and examine their interactions. The objective is to understand the impacts of network structures on knowledge diffusion processes. Chapter 3 focuses on examining the impact of individual attributes and the attributes of knowledge on knowledge diffusion in the context of scientific innovation. Based on social capital theory, the study also utilizes ERGM to examine how knowledge transfer and knowledge co-creation can be affected by the attributes of individual researchers and the attributes of scientific knowledge. Chapter 4 considers the dynamic aspect of knowledge diffusion and proposes a novel network model extending ERGM to identify dynamic patterns of knowledge diffusion in social media. In the proposed model, dynamic patterns in social media networks are modeled based on the nodal attributes of individuals and the temporal information of network ties.

Cette thèse s'inscrit dans le cadre de la conception des systèmes mécatroniques. Les travaux se positionnent dans les premières phases du cycle de conception, là où les principaux efforts méthodologiques sont à mener pour améliorer la qualité et la fonctionnalité des produits, et reposent sur le prototypage virtuel (modélisation et simulation). Une approche méthodologique envisageable est de reformuler le problème de conception sous une forme inverse, pour directement utiliser les spécifications du cahier des charges, usuellement exprimées sur les sorties, pour calculer les inconnues du problème. Dans ce contexte, le laboratoire Ampère développe une méthodologie de conception et dimensionnement, basée sur l'inversion de modèle, utilisant le formalisme bond graph, pour proposer une démarche reposant sur des critères dynamiques et énergétiques, et dont la principale originalité est sa phase d'analyse structurelle, permettant une hiérarchisation d’analyse suivant différents niveaux de la structure physique du modèle (topologie, phénoménologie, paramétrage). L'objectif est de contribuer au développement de cette méthodologie, en l’étendant aux modèles appartenant à la classe des systèmes singuliers, porté par la velléité de décliner la démarche à la conception fonctionnelle du châssis automobile et de ses sous-systèmes, comportant un certain nombre d'abstractions de modélisation et d'idéalisations. Cette déclinaison est proposée, d’une part, au niveau de la structure du modèle et, d’autre part, à un niveau considérant sa phénoménologie et ses lois de comportement. Elle requiert la mise en place préalable d'un référentiel algébrique, essentiellement issu de travaux sur la commande des systèmes, pour constituer une base de validation des extensions graphiques (digraphe et bond graph) proposées. En plus de la généralisation qu'ils constituent à la classe des modèles singuliers, les présents travaux proposent une uniformisation des précédentes approches de la méthodologie, originellement appliquées respectivement aux modèles directs et aux modèles inverses, de sorte qu'il n'est à présent plus nécessaire de les différencier
The context of this PhD thesis is the modeling and design of mechatronic systems. The study is positioned in the early design stage of the conception cycle (V-Cycle), where the main efforts have to be produced in terms of methodology, to enhance the quality and the functionality of the products, and based on virtual prototyping (modeling and simulation). One of the possible methodology is to reformulate the design problem as an inverse problem, in order to directly use the design specification of the product, usually given in terms of the system outputs, and then solve the design problem. In this context, the Ampere laboratory of INSA Lyon has developed a conception and design methodology, based on inverse approach and using the bond graph formalism, to propose a step-by-step method based on dynamic and energetic criteria, with a structural analysis phase that allows hierarchical analysis steps, depending on the structural physical layout of the model (topological, phenomenological, parameter set). The aim of the present works is to contribute to the development of this methodology, by enhancing it to the class of descriptor systems. This choice is led by the aim to apply the methodology in the context of chassis design and vehicle dynamics, where, among other, multi-body models represented as a differential-algebraic equation (DAE) system could occur. The contributions are proposed at the level of the topology of the model, as well as at the level of the phenomenological / behavioral aspects. A preliminary step is to enhance the existing algebraic framework to support graphical extension (in term of digraph and bond graph). The overall methodological extensions allow, firstly, a generalization of the approach to the class of descriptor systems, and, secondly, to reach a standardization of the procedures, previously dedicated to direct or inverse models, so as no mandatory differences between those models have to be done anymore

The Chain Event Graph (CEG) is a type of tree-based graphical model that accommodates all discrete Bayesian Networks as a particular subclass. It has already been successfully used to capture context-specific conditional independence structures of highly asymmetric processes in a way easily appreciated by domain experts. Being built from a tree, a CEG has a huge number of free parameters that makes the class extremely expressive but also very large. Exploring the enormous CEG model space then makes it necessary to design bespoke algorithms for this purpose. All Bayesian algorithms for CEG model selection in the literature are based on the Dirichlet characterisation of a family of CEGs spanned by a single event tree. Here I generalise this framework for a CEG model space spanned by a collection of different event trees. A new concept called hyper-stage is also introduced and provides us with a framework to design more efficient algorithms. These improvements are nevertheless insufficient to scale up the model search for more challenging applications. In other contexts, recent analyses of Bayes Factor model selection using conjugate priors have suggested that the use of such prior settings tends to choose models that are not sufficiently parsimonious. To sidestep this phenomenon, non-local priors (NLPs) have been successfully developed. These priors enable the fast identification of the simpler model when it really does drive the data generation process. In this thesis, I define three new families of NLPs designed to be applied specifically to discrete processes defined through trees. In doing this, I develop a framework for a CEG model search which appears to be both robust and computationally efficient. Finally, I define a Dynamic Chain Event Graph (DCEG). I develop object-recursive methods to fully analyse a particularly useful and feasibly implementable new subclass of these models called the N Time-Slice DCEG (NT-DCEG). By exploiting its close links with the Dynamic Bayesian Network I show how the NT-DCEG can be used to depict various structural and Granger causal hypotheses about a studied process. I also show how to construct from the topology of this graph intrinsic random variables which exhibit context-specific independences that can then be checked by domain experts. Throughout the thesis my methods are illustrated using examples of multivariate processes describing inmate radicalisation in a prison, and survey data concerning childhood hospitalisation and booking a tourist train.

Autonomous mobile robots - both aerial and terrestrial vehicles - have gained immense importance due to the broad spectrum of their potential military and civilian applications. One of the indispensable requirements for the autonomy of a mobile vehicle is the vehicle's capability of planning and executing its motion, that is, finding appropriate control inputs for the vehicle such that the resulting vehicle motion satisfies the requirements of the vehicular task. The motion planning and control problem is inherently complex because it involves two disparate sub-problems: (1) satisfaction of the vehicular task requirements, which requires tools from combinatorics and/or formal methods, and (2) design of the vehicle control laws, which requires tools from dynamical systems and control theory. Accordingly, this problem is usually decomposed and solved over two levels of hierarchy. The higher level, called the geometric path planning level, finds a geometric path that satisfies the vehicular task requirements, e.g., obstacle avoidance. The lower level, called the trajectory planning level, involves sufficient smoothening of this geometric path followed by a suitable time parametrization to obtain a reference trajectory for the vehicle. Although simple and efficient, such hierarchical separation suffers a serious drawback: the geometric path planner has no information of the kinematic and dynamic constraints of the vehicle. Consequently, the geometric planner may produce paths that the trajectory planner cannot transform into a feasible reference trajectory. Two main ideas appear in the literature to remedy this problem: (a) randomized sampling-based planning, which eliminates altogether the geometric planner by planning in the vehicle state space, and (b) geometric planning supported by feedback control laws. The former class of methods suffer from a lack of optimality of the resultant trajectory, while the latter class of methods makes a restrictive assumption concerning the vehicle kinematic model. In this thesis, we propose a hierarchical motion planning framework based on a novel mode of interaction between these two levels of planning. This interaction rests on the solution of a special shortest-path problem on graphs, namely, one using costs defined on multiple edge transitions in the path instead of the usual single edge transition costs. These costs are provided by a local trajectory generation algorithm, which we implement using model predictive control and the concept of effective target sets for simplifying the non-convex constraints involved in the problem. The proposed motion planner ensures "consistency" between the two levels of planning, i.e., a guarantee that the higher level geometric path is always associated with a kinematically and dynamically feasible trajectory. We show that the proposed motion planning approach offers distinct advantages in comparison with the competing approaches of discretization of the state space, of randomized sampling-based motion planning, and of local feedback-based, decoupled hierarchical motion planning. Finally, we propose a multi-resolution implementation of the proposed motion planner, which requires accurate descriptions of the environment and the vehicle only for short-term, local motion planning in the immediate vicinity of the vehicle.

The analysis of dynamic systems provides insights into their time-dependent characteristics. This enables us to monitor, evaluate, and improve systems from various areas. They are often represented as graphs that model the system's components and their relations. The analysis of the resulting dynamic graphs yields great insights into the system's underlying structure, its characteristics, as well as properties of single components. The interpretation of these results can help us understand how a system works and how parameters influence its performance. This knowledge supports the design of new systems and the improvement of existing ones. The main issue in this scenario is the performance of analyzing the dynamic graph to obtain relevant properties. While various approaches have been developed to analyze dynamic graphs, it is not always clear which one performs best for the analysis of a specific graph. The runtime also depends on many other factors, including the size and topology of the graph, the frequency of changes, and the data structures used to represent the graph in memory. While the benefits and drawbacks of many data structures are well-known, their runtime is hard to predict when used for the representation of dynamic graphs. Hence, tools are required to benchmark and compare different algorithms for the computation of graph properties and data structures for the representation of dynamic graphs in memory. Based on deeper insights into their performance, new algorithms can be developed and efficient data structures can be selected. In this thesis, we present four contributions to tackle these problems: A benchmarking framework for dynamic graph analysis, novel algorithms for the efficient analysis of dynamic graphs, an approach for the parallelization of dynamic graph analysis, and a novel paradigm to select and adapt graph data structures. In addition, we present three use cases from the areas of social, computer, and biological networks to illustrate the great insights provided by their graph-based analysis. We present a new benchmarking framework for the analysis of dynamic graphs, the Dynamic Network Analyzer (DNA). It provides tools to benchmark and compare different algorithms for the analysis of dynamic graphs as well as the data structures used to represent them in memory. DNA supports the development of new algorithms and the automatic verification of their results. Its visualization component provides different ways to represent dynamic graphs and the results of their analysis. We introduce three new stream-based algorithms for the analysis of dynamic graphs. We evaluate their performance on synthetic as well as real-world dynamic graphs and compare their runtimes to snapshot-based algorithms. Our results show great performance gains for all three algorithms. The new stream-based algorithm StreaM_k, which counts the frequencies of k-vertex motifs, achieves speedups up to 19,043 x for synthetic and 2882 x for real-world datasets. We present a novel approach for the distributed processing of dynamic graphs, called parallel Dynamic Graph Analysis (pDNA). To analyze a dynamic graph, the work is distributed by a partitioner that creates subgraphs and assigns them to workers. They compute the properties of their respective subgraph using standard algorithms. Their results are used by the collator component to merge them to the properties of the original graph. We evaluate the performance of pDNA for the computation of five graph properties on two real-world dynamic graphs with up to 32 workers. Our approach achieves great speedups, especially for the analysis of complex graph measures. We introduce two novel approaches for the selection of efficient graph data structures. The compile-time approach estimates the workload of an analysis after an initial profiling phase and recommends efficient data structures based on benchmarking results. It achieves speedups of up to 5.4 x over baseline data structure configurations for the analysis of real-word dynamic graphs. The run-time approach monitors the workload during analysis and exchanges the graph representation if it finds a configuration that promises to be more efficient for the current workload. Compared to baseline configurations, it achieves speedups up to 7.3 x for the analysis of a synthetic workload. Our contributions provide novel approaches for the efficient analysis of dynamic graphs and tools to further investigate the trade-offs between different factors that influence the performance.

This thesis addresses the issue of efficient dynamic graph drawing for large scale connected graphs with around 10,000 vertices. It contains three main contributions. Firstly, an efficient method for approximating the n-body calculations used in Force Directed Placement (FDP) is described, exploiting use of a multilevel scheme to approximate distance between groups of vertices much like the Barnes Hut Octree. The method suggests better representation of the graphs underlying relationships. In experiments this algorithm, referred to as Multilevel Global Force (MGF), reduces running time by an average of 40% compared to the popular Barnes Hut Octree approximation method. Secondly, optimisation methods used in static graph drawing (such as multilevel and approximation schemes) are adapted for use in dynamic graph drawing, simultaneously improving the quality of layouts produced and reducing the complexity such that large graphs with thousands of vertices can be drawn in interactive time. Thirdly, several techniques are introduced for incorporating graph changes into the dynamic graph drawing to differing extents, allowing the viewer to decide whether the ongoing layout should preserve the original layout or prioritise the graph changes. The works are combined to form an efficient multilevel dynamic graph drawing algorithm.

The underlying mathematical model of many simulation models is graph dynamical systems (GDS). This dynamical system, its implementation, and analyses on each will be the focus of this paper. When using a simulation model to answer a research question, it is important to describe this underlying mathematical model in which we are operating for verification and validation. In this paper we discuss analyses commonly used in simulation models. These include sensitivity analyses and uncertainty quantification, which provide motivation for stability and structure-to-function research in GDS. We review various results in these areas, which contribute toward validation and computationally tractable analyses of our simulation model. We then present two new areas of research - stability of transient structure with respect to update order permutations, and an application of GDS in which a time-varying generalized cellular automata is implemented as a simulation model.
Master of Science

In many types of network, the relationship between structure and function is of great significance. This work is particularly concerned with community structures, which arise in a wide variety of domains. A simple oscillator model is applied to networks with community structures and shows that waves of regular oscillation are caused by synchronised clusters of nodes. Moreover, we demonstrate that such global oscillations may arise as a direct result of network topology. We also observe that additional modes of oscillation (as detected through frequency analysis) occur in networks with additional levels of hierarchy and that such modes may be directly related to network structure. This method is applied in two specific domains (metabolic networks and metropolitan transport), demonstrating the robustness of the results when applied to real world systems. A topological analysis is also applied to the real world networks of metabolism and metropolitan transport using standard graphical measures. This yields a new artificial network growth model, which agrees closely with the graphical measures taken on metabolic pathway networks. This new model demonstrates a simple mechanism to produce the particular features found in these networks. We conclude that (where the distribution of oscillator frequencies and the interactions between them are known to be unimodal) the observations may be applicable to the detection of underlying community structure in networks, shedding further light on the general relationship between structure and function in complex systems.

The main subject of the thesis is concerned with interacting particle systems, which are classes of spatio-temporal stochastic processes describing the evolution of particles in interaction with each other. The particles move on a finite or infinite discrete space and on each element of this space the state of the configuration is integer valued. Configurations of particles evolve in continuous time according to a Markov process. Here the space is either the infinite deterministic d-dimensional lattice or a random graph given by the finite d-dimensional torus with random matchings. In Part I we investigate the stochastic order in a particle system with multiple births, deaths and jumps on the d-dimensional lattice: stochastic order is a key tool to understand the ergodic properties of a system. We give applications on biological models of spread of epidemics and metapopulation dynamics systems. In Part II we analyse the coalescing random walk in a class of finite random graphs modeling social networks, the small world graphs. We derive the law of the meeting time of two random walks on small world graphs and we use this result to understand the role of random connections in meeting time of random walks and to investigate the behavior of coalescing random walks.

Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2013.
Cataloged from PDF version of thesis.
Includes bibliographical references (pages 67-73).
Data-graph computations are a parallel-programming model popularized by programming systems such as Pregel, GraphLab, PowerGraph, and GraphChi. A fundamental issue in parallelizing data-graph computations is the avoidance of races between computation occurring on overlapping regions of the graph. Common solutions such as locking protocols and bulk-synchronous execution often sacrifice performance, update atomicity, or determinism. A known alternative is chromatic scheduling which uses a vertex coloring of the conflict graph to divide data-graph updates into sets which may be parallelized without races. To date, however, only static data-graph computations, which do not schedule updates at runtime, have employed chromatic scheduling. I introduce PRISM, a work-efficient scheduling algorithm for dynamic data-graph computations that uses chromatic scheduling. For a collection of four application benchmarks on a modern multicore machine, chromatic scheduling approximately doubles the performance of the lock-based GraphLab implementation, and triples the performance of GraphChi's update execution phase when enforcing determinism. Chromatic scheduling motivates the development of efficient deterministic parallel coloring algorithms. New analysis of the Jones-Plassmann message-passing algorithm shows that only O([Delta] + In A in V/ In ln V) rounds are needed to color a graph G = (V, E) with max vertex degree [Delta], generalizing previous results for bounded degree graphs. A new log-degree ordering heuristic is described which can reduce the number of colors used in practice, while only increasing the number of rounds by a logrithmic factor. An efficient implementation for the shared-memory setting is described and analyzed using the CRQW contention model, showing that this algorithm performs [Theta](V + E) work and has expected span O([Delta] In [Delta]A + 1n 2[Delta] In V/In In V). Benchmarks on a set of real world graphs show that, in practice, these parallel algorithms achieve modest speedup over optimized serial code (around 4x on a 12-core machine).
by Tim Kaler.
M. Eng.

Thesis (Ph. D.)--West Virginia University, 2001.
Title from document title page. Document formatted into pages; contains viii, 52 p. : ill. Vita. Includes abstract. Includes bibliographical references (p. 51).

Building models, whether to explain or to predict observed data, is an exercise of describing how the values of observed variables depend on those of others. Black box models only describe relationships between observed variables, and they are evaluated by their ability to accurately describe the values of observed variables in new situations not previously available to the model–such as the output response to a new set of inputs, for example. Black box models describe the observed behavior of the underlying system, but they may not correctly describe the way in which the system computes this behavior. White box models, on the other hand, describe the observed behavior and also incorporate hidden, intermediate variables that are used to describe the specific computation the underlying system uses to generate its observed behavior. In this sense, we say the white box model captures the structure of the system, in addition to its observed behavior. Since a given white box model may be accurately described by an infinite variety of black box models, all computing the same observed behavior but using different structures to do so, we say that any of these black box models is an abstraction of the white box model. This thesis constructs foundational pieces of a unifying theory of linear mathematical abstractions that are central to scientific modeling. It offers a precise description of the spectrums of grey box models linking any white and black box representation. There are various motivations for having this rich variety of representations of a given system. One key motivation is that of consilience, that is, to deepen our understanding of the modeling process by connecting various well developed theories under the umbrella of a broader theory. This work offers a precise relationship between Mason’s signal flow graphs [34] and Willem’s behavioral systems theory [66], in addition to linking the classical transfer function theory used by Nyquist [44], Bode [3], and Weiner [65] to the state space theory preferred by Kalman [27]. Another motivation comes from the application of identification or learning a model of the system from data. Learning problems trade off the number of a priori assumptions that one must make about a system, as well as the richness of available data, with the complexity of a model that one is able to confidently learn from measured observations. This work offers insight into these tradeoffs by characterizing them precisely over entire spectrums of grey box models of increasing complexity. A third motivation comes from the application of vulnerability analysis, which is the study of sensitivities of system behavior to structural perturbations in a grey-box model describing the attack surface, or representation of the system as visible to a potential attacker. The main results of this work, and its specific contributions, are as follows: 1. We define new graph-theoretic constructs and use them to create a unified framework for structural abstractions, 2. We demonstrate that there will always exist a complete, structure preserving, acyclic abstraction for every single-input, fully-connected system, 3. We define structural controllability of an abstraction of a system and argue why our definition is good, and 4. We show how complete abstractions preserve structural controllability. These results were accepted for publication in two papers at the 2020 International Federation of Automatic Control World Congress, each submitted to a different special invited session. These papers comprise Chapters 2 and 3, respectively, of the thesis presented here, and they are expected to appear in print July 2020.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2016-09-05T12:22:29Z No. of bitstreams: 2 Dissertação - Celmo José dos Reis - 2016.pdf: 3460998 bytes, checksum: c611b6ef55a816f6919e420bf4255a44 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2016-09-05T12:23:42Z (GMT) No. of bitstreams: 2 Dissertação - Celmo José dos Reis - 2016.pdf: 3460998 bytes, checksum: c611b6ef55a816f6919e420bf4255a44 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Made available in DSpace on 2016-09-05T12:23:42Z (GMT). No. of bitstreams: 2 Dissertação - Celmo José dos Reis - 2016.pdf: 3460998 bytes, checksum: c611b6ef55a816f6919e420bf4255a44 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2016-07-11
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES
Given the need for a better interaction between teachers and students in math classes, there is, currently, an increasing search for new educational tools that involve computational resources. This monograph proposes a teaching strategy that makes the study of mathematics more enjoyable and engaging, showing how math can be used in order to provide the high school student elements to understand the reason to study math and what connection it has with their daily lives. Starting from the observation that the teaching of mathematics in public schools has struggled for acceptance of the students because mathematics is presented mostly in a traditional way, i.e., it presents the student with a pile of ready-made formulas without practical sense for them. This makes it become exhausting and ineffective, leading the student even despise mathematics. Faced with these issues, we propose the use of the program Gnumeric as a tool in teaching Progressions, Functions and Graphics. Currently, interdisciplinarity has been present in education and, following this idea, we use along with the program the mathematical modeling of population dynamics, in particular the dynamics of the Aedes aegypti mosquito as a motivation to work with the proposed contents. It is further proposed to inform and alert students about diseases caused by the mosquito Aedes aegypti.
Tendo em vista a necessidade de uma melhor interação entre docentes e alunos em sala de aula na abordagem de conteúdos matemáticos, atualmente é grande a busca por novas ferramentas didáticas que envolvem recursos computacionais. Propõe-se com este trabalho, fornecer uma ferramenta didática de ensino que torne o estudo da matemática mais prazeroso e envolvente, que seja mais realístico e que forneça ao aluno do ensino médio condições de avaliação do porquê estudar matemática e qual a ligação destes conteúdos com seu dia a dia, partindo da observação de que o ensino da Matemática nas escolas públicas vem enfrentando dificuldades de aceitação e aprendizagem pelos alunos, pois os conteúdos matemáticos são apresentados quase sempre de forma tradicional, ou seja, apresenta-se ao aluno um amontoado de fórmulas prontas sem sentido prático para os mesmos. Dessa forma, o ensino se torna desgastante e ineficaz, levando o aluno a até mesmo, desprezar a Matemática. Frente a essas questões, esse trabalho propõe o uso do aplicativo Gnumeric como ferramenta de apoio no ensino de progressões, funções e construção de gráficos. Atualmente, a interdisciplinaridade tem estado presente na educação e, seguindo essa ideia, usa-se juntamente ao aplicativo a modelagem matemática da dinâmica de populações, em particular do Aedes aegypti como motivação para se trabalhar o conteúdo proposto. Propõe-se ainda, informar e alertar os alunos acerca de doenças causadas pelo mosquito Aedes aegypti.

Répondre à des requêtes de routage requiert que les entités du réseau, nommées routeurs, aient une connaissance à jour sur la topologie de celui-ci, cette connaissance est appelée table de routage. Le réseau est modélisé par un graphe dans lequel les noeuds représentent les routeurs, et les arêtes les liens de communication entre ceux ci.Cette thèse s'intéresse au calcul des tables de routage dans un modèle distribué.Dans ce modèle, les calculs sont effectués par un ensemble de processus placés sur les noeuds. Chaque processus a pour objectif de calculer la table de routage du noeud sur lequel il se trouve. Pour effectuer ce calcul les processus doivent communiquer entre eux. Dans des réseaux de grande taille, et dans le cadre d'un calcul distribué, le maintien à jour des tables de routage peut être coûteux en terme de communication. L'un des thèmes principaux abordés et celui de la réduction des coûts de communication lors de ce calcul. L'une des solutions apportées consisteà réduire la taille des tables de routage, permettant ainsi de réduire les coûts de communication. Cette stratégie classique dans le modèle centralisé est connue sous le nom de routage compact. Cette thèse présente notamment un algorithme de routage compact distribué permettant de réduire significativement les coûts de communication dans les réseaux tels que le réseau internet, i.e. le réseau des systèmes autonomes ainsi que dans des réseaux sans-échelle. Ce document contient également une étude expérimentale de différents algorithmes de routage compact distribués.Enfin, les problèmes liés à la dynamique du réseau sont également abordés. Plusprécisément le reste de l'étude porte sur un algorithme auto-stabilisant de calcul d'arbre de plus court chemin, ainsi que sur l'impact de la suppression de noeuds ou d'arêtes sur les tables de routage stockées aux routeurs.