Session L43: Complex Networks and their Applications II

Flexible embedding of networks

We introduce a model for embedding one network into another, focusing on the case where network A is much bigger than network B. Nodes from network A are assigned to the nodes in network B using an algorithm where we control the extent of localization of node placement in network B using a single parameter. Starting from an unassigned node in network A, called the source node, we first map this node to a randomly chosen node in network B, called the target node. We then assign the neighbors of the source node to the neighborhood of the target node using a random walk based approach. To assign each neighbor of the source node to one of the nodes in network B, we perform a random walk starting from the target node with stopping probability $\alpha$. We repeat this process until all nodes in network A have been mapped to the nodes of network B. The simplicity of the model allows us to calculate key quantities of interest in closed form. By varying the parameter $\alpha$, we are able to produce embeddings from very local ($\alpha = 1$) to very global ($\alpha \to 0$). We show how our calculations fit the simulated results, and we apply the model to study how social networks are embedded in geography and how the neurons of C. Elegans are embedded in the surrounding volume.   

Exploring many-body physics with deep networks

The introduction of neural networks with deep architecture has led to a revolution, giving rise to a new wave of technologies empowering our modern society. Although data science has been the main focus, the idea of generic algorithms which automatically extract features and representations from raw data is quite general and applicable in multiple scenarios. Motivated by the effectiveness of deep learning algorithms in revealing complex patterns and structures underlying data, we are interested in exploiting such tool in the context of many-body physics. In this talk we will focus on how to extract information about the physics of a many-body system from the generative training of a deep network, and ultimately consider discriminative tasks, such as phase diagrams estimation and critical points detection. We will discuss results for different classical spin systems, including models with quenched disorder.   

Random walks on networks

Random walks on lattices are a well used model for diffusion on continuum. They have been to model subdiffusive systems, systems with forcing and reactions as well as a combination of the three. We extend the traditional random walk framework to the network to obtain novel results. As an example due to the small graph diameter, the early time behaviour of subdiffusive dynamics dominates the observed system which has implications for models of the brain or airline networks.   

The Impact of Selectivity on Fitness Evolution in the Multi-Generational Matching Problem

The stochastic matching hypothesis has been found to produce self-similar pairing without explicitly requiring self-similarity in the rules for matching. Here, we introduce an added complexity of selectivity in which the relative probability of being matched are modified.\footnote{T. Jia, R.F. Spivey, B. Szymanski, G. Korniss, PLOS ONE 10(6): e0129804 (2015)} This allows for probing in areas between the currently established matching hypothesis, random matching, and the extreme case of super selectivity, where only the very best fitness matches for nodes are created. A higher selectivity parameter has been found to indirectly increase the number of matches in the system monotonically. A fairly simple model is then implemented to produce offspring who inherit fitness based on the inherited fitness distribution which is a function of the parents' fitness. While the results show that the specific distribution used may limit the inherited quality factors to a too narrow range to be broadly applicable, the model does expose some interesting patterns in fitness evolution across multiple generations in the context of selectivity and network degree distribution.   

A matrix product algorithm for stochastic dynamics on locally tree-like graphs

In this talk, I describe a novel algorithm for the efficient simulation of generic stochastic dynamics of classical degrees of freedom defined on the vertices of locally tree-like graphs. Such models correspond for example to spin-glass systems, Boolean networks, neural networks, or other technological, biological, and social networks. Building upon the cavity method and ideas from quantum many-body theory, the algorithm is based on a matrix product approximation of the so-called edge messages -- conditional probabilities of vertex variable trajectories. The matrix product edge messages (MPEM) are constructed recursively. Computation costs and accuracy can be tuned by controlling the matrix dimensions of the MPEM in truncations. In contrast to Monte Carlo simulations, the approach has a better error scaling and works for both, single instances as well as the thermodynamic limit. Due to the absence of cancellation effects, observables with small expectation values can be evaluated accurately, allowing for the study of decay processes and temporal correlations with unprecedented accuracy. The method is demonstrated for the prototypical non-equilibrium Glauber dynamics of an Ising spin system. Reference: arXiv:1508.03295.   

Percolation transition in dynamical traffic network with evolving critical bottlenecks

A critical phenomenon is an intrinsic feature of traffic dynamics, during which transition between isolated local flows and global flows occurs. However, very little attention has been given to the question of how the local flows in the roads are organized collectively into a global city flow. Here we characterize this organization process of traffic as ``traffic percolation,'' where the giant cluster of local flows disintegrates when the second largest cluster reaches its maximum. We find in real-time data of city road traffic that global traffic is dynamically composed of clusters of local flows, which are connected by bottleneck links. This organization evolves during a day with different bottleneck links appearing in different hours, but similar in the same hours in different days. A small improvement of critical bottleneck roads is found to benefit significantly the global traffic, providing a method to improve city traffic with low cost. Our results may provide insights on the relation between traffic dynamics and percolation, which can be useful for efficient transportation, epidemic control, and emergency evacuation.   

Properties of the networks of same-spin sites in each Ising Model macrostate

An Ising Model macrostate contains all the microstates with the same energy. Each macrostate is labeled in an energy two-space by the two sums in the Hamiltonian, one for the magnetism and the other for the interaction energy. In a single macrostate, a network can be defined for all the up-spin sites and another network for all the down-spin sites. An exact formula has been derived that explicitly provides the total number of connection links (edges) in both of these macrostate networks. This derivation follows from a meticulous analysis of the calculation of the sum of the product of spins in the Hamiltonian. It is applicable to one, two, and three dimension Ising models with periodic boundary conditions. The formula permits calculation of the total number of nearest-neighbor connections for all of the sites, and thus the average number of connections per site. The number of connections can be used to calculate the probability that a nearest neighbor in a particular direction at a spin site has the same spin. This probability can be used to infer the closeness of any macrostate to the ferromagnetic ground states, the paramagnetic region, or the anti-ferromagnetic ground states. Note that these properties of each macrostate do not require knowledge of the number of microstates in the macrostate (the density of states).   

Upper Bound for the Ordering Transition on an Ising Model on a Graph

We present an upper bound for the ordering transition of a ferromagnetic Ising model on a graph. Namely, we show that at any given temperature, the magnetic susceptibility per spin cannot exceed that on an infinite tree, the universal cover of the original graph. Exact solution of the Ising model on the tree can be obtained using Bethe-Peierls expansion (also known as Belief Propagation). The corresponding transition point is given by a solution of an eigenvalue problem.   

Spectral renormalization group theory on nonspatial networks

We recently proposed a ``spectral renormalization group'' scheme, for non-spatial networks with no metric defined on them. We implemented the spectral renormalization group on two deterministic non-spatial networks without translational invariance, namely the Cayley tree and diamond lattice . The thermodynamic critical exponents for the Gaussian model are only functions of the spectral dimension, $\tilde d$. The Gaussian fixed point is stable with respect to a $\psi^4$ perturbation up to second order on these lattices with $\tilde d=2$, the lower critical dimension for the Ising universality class. This is expected for the Cayley tree, but for the diamond lattice it is an indication that the perturbation expansion up to second order breaks down at $\tilde d=2$, as it does for the Wilson scheme on the square lattice. On generalized diamond lattices, with $2<\tilde d<4$, we find non-Gaussian fixed points with non-trivial exponents. For $\tilde d>4$, the critical behavior is once again mean field.   

Real beards and real networks: a spin-glass model for interacting individuals

"I want to be different, just like all the other different people" sang the band King Missile. Whether they are the Beatniks of the 1950s, the punks of the 1970s, or the hipsters of today, non-conformists often tend to look the same, seemingly at odds with their goal of non-conformity. The spin-glass model, originally developed to describe the interaction of magnetic spins, and since applied to situations as diverse as the electrical activity of networks of neurons, to trades on a financial market, has recently been used in social science to study populations of interacting individuals comprised of a mix of both conformists and anti-conformists - or hipsters. Including delay effects for the interactions between individuals has been shown to give a system with non-trivial dynamics with a phase transition from stable behaviour to periodic switching between two states (let's call them bushy bearded and clean shaven). Analytic solutions to such a model are possible, but only for particular assumptions about the interaction and delay matrices. In this work we will show what happens when the interactions in the model are based on real-world networks with "small-world" effects and clustering.   

Condensation and transport in the totally asymmetric inclusion process (TASIP)

Transport phenomena are often modeled by the hopping of particles on regular lattices or networks. Such models describe, e.g., the exclusive movement of molecular motors along microtubules: no two motors may occupy the same site. In our work, we study inclusion processes that are the bosonic analogues of the fermionic exclusion processes. In inclusion processes, many particles may occupy a single site and hopping rates depend linearly on the occupation of departure and arrival sites. Particles thus attract other particles to their own site. Condensation occurs when particles collectively cluster in one or multiple sites, whereas other sites become depleted.\\ We showed that inclusion processes describe both the selection of strategies in evolutionary zero-sum games and the condensation of non-interacting bosons into multiple quantum states in driven-dissipative systems. The condensation is captured by the antisymmetric Lotka-Volterra equation (ALVE), which constitutes a nonlinearly coupled dynamical system. We derived an algebraic method to analyze the ALVE and to determine the condensates. Our approach allows for the design of networks that result in condensates with oscillating occupations, and yields insight into the interplay between network topology and transport properties.   

Multi-frequency and edge localized modes in mechanical and electrical lattices

We present experimental evidence for the existence of a type of dynamical, self-localized mode called a multi-frequency breather in both a mechanical lattice of pendula and an electrical lattice. These modes were excited and stabilized by subharmonic driving. We also experimentally characterize dynamical modes that are localized on the edges of the pendulum chain, as well as in 2D electrical lattices. In the latter system, we briefly discuss the role of lattice topology in the stability of such modes.   

Stokes Trap: Multiplexed particle trapping and manipulation using fluidics

We report the development of the Stokes Trap, which is a multiplexed microfluidic trap for control over an arbitrary number of small particles in a microfluidic device. Our work involves the design and implementation of ``smart'' flow-based devices by coupling feedback control with microfluidics, thereby enabling new routes for the fluidic-directed assembly of particles. Here, we discuss the development of a new method to achieve multiplexed microfluidic trapping of an arbitrary number of particles using the sole action of fluid flow. In particular, we use a Hele-Shaw microfluidic cell to generate hydrodynamic forces on particles in a viscous-dominated flow defined by the microdevice geometry and imposed peripheral flow rates. This platform allows for a high degree of flow control over individual particles and can be used for manufacturing novel particles for fundamental studies, using fluidic-directed assembly. From a broader perspective, our work provides a solid framework for guiding the design of next-generation, automated on-chip assays.