Second Workshop "Critical and collective effects in graphs and networks"

Classic model organisms have vast collections of genome-wide gene expression experiments accumulated during a long history of well-funded research. For example, the current number of publicly available microarray expression samples in a model plant Arabidopsis thaliana exceeds 6000 (see Plant Journal 86, 472 (2016)). The biological information contained in these experiments is often described in terms of coexpression networks linking co-regulated genes. One of the popular is to construct a single “master” coexpression network by combining multiple expression datasets generated in different labs. In Sci. Rep. 6:38956 (2016) my collaborator and I advocate a complementary approach in which one instead constructs a large collection of coexpression networks based on expression datasets reported in individual publications. This allowed us to minimize “batch effects” artefacts and to discover rare but biologically important functions activated only in a small subset of conditions. To describe the resulting set of 134 coexpression networks in Arabidopsis thaliana we introduce the concepts of ‘pan-network’ and ‘core-network’ representing the union and the intersection between sizable fractions of individual networks, respectively. These two types of networks differ from each other both by their topology as well as by biological functions of interacting genes. We proceed by constructing a "network of networks" in which pairs of networks with significantly overlapping typologies are connected to each other.

The natural framework to understand the structure of social interaction patterns is in terms of temporal multiplex networks, that is, networks composed by a set of different layers, corresponding to different kinds of social interactions, in which edges have a dynamic nature, being created, interrupted and rewired at different time scales. Here we
present an empirical analysis of such networks, focusing on the measurement of inter-layer correlations, namely, whether activity in one layer enhances or suppresses the chances of engaging in social acts in another layer. We define suitable observables able to detect when genuine correlations are present in empirical data, and we conclude that
such correlations act as to depress the tendency to concentrate long stretches of activity on the same layer. These correlations have moreover a deep impact of dynamical processes on top of such multiplexes, which we address in the context of epidemic spreading and searching processes.

Effective Distances for Epidemics Spreading on Complex Networks

We show that the recently introduced logarithmic metrics used to predict disease arrival times on complex networks are approximations of more general network based measures derived from random walks theory.  Using the daily air-traffic transportation data we perform numerical experiments to compare the infection arrival time with this alternative metric that is obtained by accounting for multiple walks instead of only the most probable path. The comparison with direct simulations reveals a higher correlation compared to the shortest-path approach used previously.  In addition our method allows to connect fundamental observables in epidemic spreading with the cumulant generating function of the hitting time for a Markov chain. Our results provides a general and computationally efficient approach using only algebraic methods.

Dense subgraphs in random graphs

The problem of identifying large dense subgraphs received a lot of attention in the recent literature due to its various practical applications. Since the recognition version of this problem is NP-complete, good analytical bounds may play an important role for the design and development of effective heuristic algorithms as well as evaluating their performance. In this presentation, we develop asymptotic analytical bounds on the size of the largest subgraphs with certain edge density (referred to as quasi-cliques) in random graphs G(n,p). Specifically, we demonstrate that, similarly to the asymptotic behavior of large cliques, the size of the largest quasi-clique with high probability is also concentrated around one integer. Moreover, we present our recently developed MIP models and conduct computational experiments to investigate the accuracy of presented bounds in reasonably small graphs.
 

Resting state networks in the mouse brain: cellular mapping and network characterization

A resting state network is a correlated activity of many neural structures in absence of external stimulation or functional tasks, and it is a fundamental endogenous feature of the human and animal brain. However, the nature and function of such spontaneous activity remain poorly understood. One of the hypothesis suggest that they reflect hidden activation, replay and consolidation of individually acquired neural networks of prior experience, which prepares and predetermines an organism’s perception, awareness and reaction to the external events. However, classical non-invasive fMRI and EEG methods used for resting state network detection cannot tag specific cellular elements of the neural network at the time when individual experience is acquired so that their activity can be subsequently investigated in the resting state. To overcome this limitation, we started a project on cellular imaging neuronal resting state networks of the mouse brain and relating their activity to animal’s past experiences. As the first stage of the project we characterized resting-state activity of 104 mouse brain structures by means of large-scale c-Fos cellular mapping. We made an estimate of the expected level of activation for each of the analyzed brain areas based on amount of c-Fos positive cells in all the experimental animals. Based on the level of resting state activity the examined brain areas were divided into four groups: 59 brain areas were non-active, 14 – were low, 29 – medium, and 8 – were highly active. There was no direct relationship between anatomical attributes of examined areas and the level of their activity. We also analyzed individual variability of levels of activity for each group of brain areas and showed that resting state networks identified by c-Fos expression were stable and reproducible in all the animals. Next, we selected 38 areas (associative, sensory and motor neocortical areas, hippocampus, parahippocampal cortex, amygdala, basal nuclei, thalamus, olfactory areas and subcortical nuclei) to characterize the major components and analyze functional connectivity of the resting state network. Based on the activity of selected brain areas and using Pearson correlation we obtained seven networks with correlation coefficients varying from 0.6 to 0.9 (inclusive, step=0.05) and compared each experimentally identified networks with model networks (random, scale free and small world) of the same size using clustering and global efficiency coefficients and degree distribution. The experimental resting state network had substantially higher clustering than model networks. Global efficiency of the resting state network was relatively low and was at the same level as global efficiency of a random network. At correlation coefficients, higher than 0.7 the resting state network broke down into separate subnetworks. The comparison of experimental network to the model networks and the analysis of its degree distribution suggests that the resting state network of the mouse brain is highly clustered and has features of scale free networl with low global efficiency. In addition, we identified several major groups of functionally connected areas in the resting state network of an awake mouse brain: a cluster of medial prefrontal cortex and other medial associative neocortical areas, a cluster of visual areas, a tightly linked cluster of sensorimotor areas and basal nuclei, and an entirely isolated cluster of auditory brain areas. Importantly, activity of structures known for their relationship to fear and threat learning (such as amygdala, hippocampus, and prelimbic cortex) was not correlated and did not comprise any special functional group. This high variability in the activity of fear-related brain structures will be used at the next stage of the project to examine changes in the cellular activity of the resting state network in relation to a neuronal network of threat experience previously labeled in the same mouse brain. 
Supported by RSF 16-15-00300.

The analysis of the structure and emergent phenomena in multiplex networks has attracted a lot of attention in the last years. Here we explore multiplex networks in two different ways, but which admit similar mathematical approaches: their robustness using bond percolation, and information spreading with cascade models. First, we show that bond percolation behaves the same in multiplex networks and their aggregated counterparts, except when the layers are highly anticorrelated, for which multiple percolation transitions occur. Then, we analyze a cascade process in which the decision to spread or not the information depends on the trust on the neighbors. The trust and information spreading dynamics are supposed to take place in two different layers of a multiplex networks. The results show how the spreading of information is promoted by trust, but there is also an opposing effect of memory. 

Characteristics of the oriented weighted graph representing input-output relationships in multisector macroeconomic models are discussed. Macroeconomic dynamics on these networks is studied in the framework competitive and non-competititve evolutionary models. Key role of page-rank centrality of individual sectors is discussed.

Tensor models have been proposed as a discretized  random-geometric approach to quantum gravity. Recently a connection has emerged between these models and the AdS/CfT correspondence that we  shall discuss.

The end