Foundations  (F) Session 10

Schedule Top Page

Time and Date: 16:00 - 17:20 on 22nd Sep 2016

Room: N - Graanbeurszaal

Chair: Yamir Moreno

328 Irreducibility of multilayer network dynamics: the case of the voter model [abstract]
Abstract: We address the issue of the reducibility of the dynamics on a multilayer network to an equivalent process on an aggregated single-layer network. As a typical example of models for opinion formation in social networks, we implement the voter model on a two-layer multiplex network, and we study its dynamics as a function of two control parameters, namely the fraction of edges simultaneously existing in both layers of the network (edge overlap), and the fraction of nodes participating in both layers (interlayer connectivity or degree of multiplexity). We compute the asymptotic value of the number of active links (interface density) in the thermodynamic limit, and the time to reach an absorbing state for finite systems, and we compare the numerical results with the analytical predictions on equivalent single-layer networks obtained through various possible aggregation procedures. We find a large region of parameters where the interface density of large multiplexes gives systematic deviations from that of the aggregates. We show that neither of the standard unweighted aggregation procedures is able to capture the highly nonlinear increase in the lifetime of a finite size multiplex at small interlayer connectivity. These results indicate that multiplexity should be appropriately taken into account when studying voter model dynamics, and that, in general, single-layer approximations might be not accurate enough to properly understand processes occurring on multiplex networks, since they might flatten out relevant dynamical details.
Marina Diakonova, Vincenzo Nicosia, Vito Latora and Maxi San Miguel
552 New dimensions for network science [abstract]
Abstract: Network science makes a major contribution to understanding complexity but has focused on relations between two entities and hardly embraced the generality of n-ary relations for any value of n. A set of elements is n-ary related if, on removing one of them, the relation ceases to hold, e.g., the notes {C, E, G} forming the chord of C major (3-ary relation), four people playing bridge (4-ary relation), and the characters of the word {w,h,o,l,e} (5-ary relation). N-ary relations are ubiquitous in complex systems. Hypergraphs, with edges sets of vertices, provide a powerful first step. Generally vertices need to be ordered to avoid, e.g., {g, r, o, w, n} = {w, r, o, n, g}. An ordered set of vertices is a ‘simplex’, e.g. != . Simplices take network edges to new dimensions, is a 1-dimensional edge, is a 2-dimensional triangle, is 3-dimensional tetrahedron, and … with (p+1) vertices is a p-dimensional polyhedron. Polyhedra are q-connected through their q-dimensional faces, leading to higher dimensional q-connectivity. Generally the same set of vertices can support many relations, e.g. the right facing smiling face :-) and the left facing frowning face )-: are both assembled from the same three symbols. The ‘explicit relation’ notation of multiplex hypersimplices, != , allows different structures with same vertices to be discriminated. It will be shown that multilevel multiplex hypernetworks, formed from hypersimplices, are part of a natural family integrating graphs, networks and multiplex networks with their higher dimensional extensions to hypergraphs, simplicial complexes and multiplex hypernetworks. Illustrative analyses will be presented. Embracing higher dimensions can make network science even more powerful.
Jeffrey Johnson
100 The diffusion manifold of complex networks [abstract]
Abstract: Complex networks are special mathematical objects lacking an appropriate definition of distance between their units. In fact, the shortest path between two nodes is not metric because it does not satisfy the triangle inequality. One possible alternative is to introduce a metric distance based on dynamical process, more specifically random walks. This "diffusion distance" between two nodes, already used in recent machine learning and image processing applications, quantify how easily a walker can diffuse between them and it is a true metric. We show that the diffusion distance allows to identify a metric tensor g whose properties depends on the eigenvalue spectrum of the Laplacian matrix of the underlying network G. We introduce a Riemannian manifold M endowed with such a metric tensor and the Levi-Civita connection as the natural affine connection. By requiring that distances on G are preserved on M, this choice allows us to embed the network into a metric space that we call "diffusion manifold". The embedding of a complex network into a metric manifold provides several advantages for the analysis. For instance, it is possible to exploit the mathematical properties of the manifold to better understand the diffusion landscape of the network: we discuss the cases of several real-world networks, from physical ones (such as transportation networks, which are naturally embedded in an Euclidean space) to non-physical ones (such as online social networks). More intriguingly, we show that the diffusion manifold allows to naturally define a dynamical renormalization of the underlying complex network that can be exploited to better understand its structure and its critical properties.
Manlio De Domenico and Alex Arenas
208 Nonlinear resonances for discrete cycles and chains [abstract]
Abstract: The graph wave equation arises naturally from conservation laws on a network; there, the usual continuum Laplacian is replaced by the graph Laplacian. We consider such a wave equation with a cubic defocusing non-linearity on a general network. The model is well-posed. It is close to the φ4 model in condensed matter physics. Using the normal modes of the graph Laplacian as a basis, we derive the amplitude equations and define resonance conditions that relate the graph structure to the dynamics. For cycles and chains, the spectrum of the Laplacian is known; for these we analyze the amplitude equations in detail. The results are validated by comparison to the numerical solutions. This study could help understand other dynamical systems on networks from biology, physics or engineering.
Imene Khames, Jean Guy Caputo and Arnaud Knippel