Foundations  (F) Session 3

Abstract: Geometric representations of data provide useful tools for visualisation, classification and prediction. In particular, geometric approaches to network analysis have grown in popularity recently as the effectiveness of simple geometric models to generate complex networks with interesting properties becomes clearer. Techniques such as Multidimensional Scaling (MDS) provide a method of embedding high dimensional data, or networks into lower-dimensional spaces. However, classical MDS forces a representation in Euclidean space, which may not necessarily be appropriate. In this talk we use ideas from the causal set approach to quantum gravity to find a general method for embedding networks in spaces with any metric signature, not just a Riemannian one (with all eigenvalues of the metric positive). We demonstrate this on the most common case found in physics, a Lorentzian manifold (with one negative eigenvalue of the metric). These manifolds represent spacetime as used in relativity. We show that for networks which naturally form Directed Acyclic Graphs (DAG), such as citation networks, spacetime embeddings are appropriate. This is because the constraint of having no cycles in a DAG corresponds to the causal structure of events in spacetime: that if A caused B to happen, it cannot also be the case that B caused A. As an illustration of these techniques we embed well known citation networks from papers on the arXiv, and from cases of the US Supreme Court in flat spacetime and see that this embedding accurately predicts edges in the networks. Close

Abstract: Self-organization is defined as the spontaneous emergence of order arising out of local interactions in a complex system. The central to the idea of self-organization is the interaction between the agents, the particles, the elements that constitute the system. In biological systems, particle-particle interactions or particle-field interactions are often mediated by chemical trails (chemotaxis), or swarm behaviour that optimizes system efficiency. In non-biological systems, particle-field interaction plays the crucial role, as these interactions modify the surrounding field or often the topology of the energy landscape. Interactions in a system, or a system and its surroundings, are governed by energetic and entropic exchanges, either in terms of forces or in terms of statistical information. Since, energy and time, the two properties of matter and space we look into the Principle of Least Action to search for answers as it involves both time and energy into its formulation. Since, the Action Principle minimizes action and directs the system elements along least action trajectories on the energy landscape (surrounding field), it is imperative that a one to one correspondence exists between the Second Law of Thermodynamics and the Action Principle. In a system in equilibrium, the system particles can occupy all possible microstates whereas in a self-organizing, out-of-equilibrium system only certain microstates will be accessible to the system particles. In these systems, in order to organize efficiently the system particles interact locally and coordinate globally, in a way that lets swarms of agents to uniformly follow least action trajectories and simultaneously degrade their free-energies in order to maintain the organizational structure of the system at the expense of entropy export along the least action paths. The question we ask is how the symmetry breaking is mediated in a physical system? Close

Abstract: We present universal framework for generation, analysis and control of non-trivial states/patterns in the complex systems like kinetic hierarchies describing general set-up for non-equilibrium dynamics and their important reductions. We start from the proper underlying functional spaces and their internal hidden symmetries which generate all dynamical effects. The key ingredients are orbits of these symmetries, their representations, and Local Nonlinear Harmonic Analysis on these orbits. All that provides the possibility to consider the maximally localized fundamental generic modes, non-linear (in case of the non-abelian underlying symmetry) and non-gaussian, which are not so smooth as gaussians and as a consequence allowing to consider fractal-like images and possible scenarios for generation chaotic/stochastic dynamics on the level of representation theory only. As a generic example we consider the modeling of fusion dynamics in plasma physics. http://math.ipme.ru/zeitlin.html, http://mp.ipme.ru/zeitlin.html Close

Abstract: Complex networks have been conjectured to be embedded in hidden metric spaces, in which distances between nodes encode their similarity and, thus, their likelihood of being connected. This hypothesis, combined with a suitable underlying space, has offered a geometric interpretation of the complex topologies observed in real networks, including scale-free degree distributions, the small-world effect, strong clustering as a reflection of the triangle inequality, and self-similarity. It has also explained their efficient inter-node communication without a knowledge of the complete structure. Moreover, it has been shown that for networks whose degree distribution is scale-free, the natural geometry of their underlying metric space is hyperbolic. These results have led to geometric models for real growing networks that reproduce their evolution and in which preferential attachment emerges from local optimization principles. Using real networks from very different domains, we present empirical evidence that the magnitude of the connections, the weights, also have a geometric nature. To quantify the level of coupling between the topology, the weights, and the underlying metric space in real networks, we introduce the most general and versatile class of weighted networks embedded in hidden metric spaces. This framework allows us to independently regulate the coupling between the topology and the geometry and between the weights and the geometry. We show that such couplings can be significantly different in real networks, which supports the hypothesis that the formation of connections and the assignment of their magnitude is ruled by different processes. Our empirical findings, combined with our new class of models, open the path towards the uncovering of the natural geometry of real weighted complex networks. Close

Abstract: Dynamical processes on networks are currently being considered in different domains of cross-disciplinary interest. Reaction-diffusion systems hosted on directed graphs are in particular relevant for their widespread applications, from neuroscience, to computer networks and traffic systems. We shall here consider as a paradigmatic example the complex Ginzburg-Landau equation defined on a asymmetric lattice, with next-nearest-neighbors couplings. The peculiar spectrum of the discrete Laplacian operator yields an extended class of modulational instabilities which can be analytically predicted. Specifically, the synchronized regime can turn unstable to external perturbation because of the imposed degree of spatial asymmetry, and for a choice of the paramaters for which the instability cannot develop on undirected graphs. The excited modes can then stabilize in traveling wave solutions. Alternatively, the modulus of the complex quantity that obeys Ginzburg-Landau equation can display a complicated mosaic of patterned structures in the non linear regime of evolution. The bifurcation between the different regimes is predicted by the theory and ultimately relates to the long range nature of the spatial coupling imposed. The case of an heterogeneous generic directed network will be also discussed. Close

Abstract: The interplay between network evolution and the dynamics of a spreading process impacts the conditions for large-scale propagation, by altering the epidemic threshold, i.e., the critical transmissibility value above which the disease turns epidemic. In order to study these processes many works have resorted to discrete-time approximations of both network and spreading dynamics. While this is practical from both the numerical and the theoretical point of view, it is known to bias results in some circumstances. Here we analytically derive the epidemic threshold for a generic time varying network, in both continuous and discrete time. We focus on the susceptible-infected-susceptible spreading process, within the quenched mean field framework. In discrete time, the epidemic threshold of a generic network can be computed from the spectral radius of the infection propagator, a matrix encoding a multi-layer representation of both network and spreading dynamics [Valdano et al (2015) Phys Rev X, Valdano et al (2015) Eur Phys J B]. We build a new theoretical framework that allows us to perform the continuous time limit of the infection propagator, and we find it correctly describes the linearized form of the continuous-time Markov equations of the process. This yields a solution for the epidemic threshold in continuous time that admits an explicit form in specific cases. The mathematical formalism proposed here allows addressing the effect of discretization and temporal resolution on the epidemic threshold accounting for different network properties and parameter regimes. Close