Foundations  (F) Session 8

Abstract: Real networks often form interacting parts of larger and more complex systems. Examples can be found in different domains, ranging from the Internet to structural and functional brain networks. Here, we show that these multiplex systems are not random combinations of single network layers. Instead, they are organized in specific ways dictated by hidden geometric correlations interweaving the layers. We find that these correlations are significant in different real multiplexes, and form a key framework for answering many important questions. Specifically, we show that these geometric correlations facilitate: (i) the definition and detection of multidimensional communities, which are sets of nodes that are simultaneously similar in multiple layers; (ii) accurate trans-layer link prediction, where connections in one layer can be predicted by observing the hidden geometric space of another layer; and (iii) efficient targeted navigation in the multilayer system using only local knowledge, which outperforms navigation in the single layers only if the geometric correlations are sufficiently strong. Importantly, if optimal correlations are present, the fraction of failed deliveries is mitigated superlinerarly with the number of layers, suggesting that more layers with the right correlations quickly make multiplex systems almost perfectly navigable. Our findings uncover fundamental organizing principles behind real multiplexes and can have important applications in diverse domains, ranging from improving information transport and navigation or search in multilayer communication systems and decentralized data architectures, to understanding functional and structural brain networks and deciphering their precise relationship(s), to predicting links among nodes (e.g., terrorists) in a specific network by knowing their connectivity in some other network. Close

Abstract: Living organisms capitalize on their ability to predict their environment to maximize their available free energy, and invest this energy in turn to create new complex structures. For example, a lion metabolizes the structure of an antelope (destroying it in the process), and uses the energy released to build more lion. Is there a preferred method by which this manipulation of structure should be done? Our intuition is “simpler is better,” but this is only a guiding principal. By formalizing the manipulation of patterns – structured sequences of data – this intuitive preference for simplicity can be substantiated through physical reasoning based on thermodynamics. Using techniques from complexity science and information theory, we consider devices that can manipulate (i.e. create, change or destroy) patterns. In order to operate continually, such devices must utilize an internal memory in order to keep track of their current position within the pattern. However, the exact structure of this internal memory is not uniquely defined, and all choices are not equivalent when it comes to their thermal properties. Here, we present the fundamental bounds of the cost of pattern manipulation. When it comes to generating a pattern, we see indeed that the machine with the simplest memory capable of the task is indeed the best choice thermodynamically. Using the simplest internal memory for generation grants the advantage that less antelope needs to be consumed in order to produce the same amount of lion. However, contrary to intuition, when it comes to extracting work from a pattern, any device capable of making statistically accurate predictions can recover all available energy from the structure. This apparent paradox can be explained by careful consideration of nature of the information-processing tasks at hand: namely, one of logical irreversibility. [See also arXiv:1510.00010.] Close

Abstract: Recently Gao et al.[1] showed that classes of complex networks could be described in a universal way. In particular it was stated that the dynamics of a complex network consisting of many nodes and links is governed by a one-dimensional effective dynamical equation, which was obtained by averaging over all network configurations. In this paper we address the question how well the averaged effective equation describes classes of networks by numerical calculation of variances in dynamics. It appears that huge variances in the dynamics can arise. To examine the consequences of our work to practical situations, we apply our findings to specific networks occurring in transport and supply chains. References [1] Jianxi Gao1, Baruch Barzel, Albert-László Barabási, Universal resilience patterns in complex networks, Nature 530, 307 (2016). Close

Abstract: Assortative mixing (or homophily) in networks is the tendency for nodes with the same attributes, or metadata to link to each other. For instance in social networks we may observe more interactions between people with the same age, race, or political belief. Quantifying the level of assortativity or disassortativity (the preference of linking to nodes with different attributes) can shed light on the factors involved in the formation of links in complex networks. It is common practice to measure the level of assortativity according to the assortativity coefficient, or modularity in the case of discrete-valued metadata. This global value is an average behaviour across the network and may not be a representative statistic when mixing patterns are heterogeneous. For example, a social network that spans the globe may exhibit local differences in mixing patterns as a consequence of differences in cultural norms. Here, we present a new approach to localise these global measures so that we can describe the assortativity at the node level. Consequently we are able to capture and qualitatively evaluate the distribution of mixing patterns in the network. We develop a statistical hypothesis test with null models that preserve the global mixing pattern and degree distribution so that we may quantitatively determine the representativeness of the global assortativity. Using synthetic examples we describe cases of heterogeneous assortativity and demonstrate that for many real-world networks the global assortativity is not representative of the mixing patterns throughout the network. Close

Abstract: We will sketch an algorithmic take, i.e. message-passing algorithms, on networks and its relevance to some questions and insight in complex systems. Recently, message-passing algorithms have been shown to be an efficient, scalable approach to solve hard computational problems ranging from detecting community structures in networks to simulating probabilisitic epidemic dynamics on networks. The objective of the talk is two fold. On on hand, we will discuss how the non-backtracking nature of message-passing avoids an “echo-chamber effects” of signal flow and thus makes a good tool to consider for problems in networks. On the other hand, we will also argue why insight gained from algorithms are equally important when exploring questions at the boundaries of scientific studies, such as networks and complex systems. Close