Foundations  (F) Session 6

Abstract: The dynamics of random walks and thermal diffusion on network is interlinked with the spectral properties of the associated graph representing the network. For example, the eigenvalues of the normalized Laplacian L of the graph characterize the time scales for the convergence to the equilibrium probability distribution over the nodes of the graph. The normalized Laplacian also describes the thermal heat conduction on networks via the Fourier heat transport equation. The heat conduction on networks has been investigated experimentally using a 2 dimensional network cut from strongly thermal conducting pyrolytic graphite films and observing the diffusion of heat with a thermal camera. The effect of network topology, length and width of the connections in the network is analyzed using the general concepts of the spectral theory of graphs. Cospectral graphs have identical eigenspectrum for the matrices associated with the graph such as the adjacency matrix A, the Laplacian matrix L=D-A, with D is the degree matrix for the vertices, and the normalized Laplacian matrix. The dynamics of a random walk, -hence also the heat conduction -, on these graphs can be found by iterating the probability transfer matrix P= D^(-1) A and is strongly related to the spectra of the normalized Laplacian L = D^(-1/2) AD^(-1/2). In the past decades methods have been devised to systematically generate sets of graphs with cospectral properties. For example L cospectral graphs can be generated systematically for inflated star graphs by modifying the arm composition (swapping). The graphs have identical eigenvalues, but different topology. Furthermore, some of these graphs have multiple zero eigenvalues, making the final distribution dependent on the initial starting conditions. The effect of cospectral behavior and multiple zero eigenvalue degeneracy on the dynamics of thermal conduction is demonstrated using the experiments and by numerical and analytical modeling . Close

Abstract: Evolutionary game theory has been studied intensely as a mathematical framework for understudying Darwinian evolution. Despite the fact that evolutionary dynamics, whether in biological ecosystems or, say in human environments like the economy, takes place in the form of co-evolving webs of interactions; game theory is usually studied in the limit of very few strategies. Here, we study replicator dynamics with extinctions and mutations in a large game with many strategies. We perform numerical simulations of a game where each player can play one of a large number of strategies. The game is defined with a payoff matrix whose elements are random numbers which can be positive or negative, with majority being zero. At the beginning of the simulation we choose randomly a small number of strategies to be played. Reproduction of players is done according to the replicator equation in which a small amount of mutations is introduced. In this way new strategies can appear in the system. Additionally we introduce an extinction threshold; strategies with a frequency less than this threshold are removed from the system. The resulting behaviour shows complex intermittent time dependence similar to those of the Tangled Nature model. The dynamics has two types of phases: a quasi stable phase in which the number of active strategies is more or less constant and hectic phases during which creation and extinct of strategies happens at a high rate. We see that the complex behaviour of the Tangled Nature model, which is in good agreement with observations on ecosystems, also arises from the game theoretic basis of the replicator dynamics. Finally we investigate various lifetime distributions and find fat tail distributions similar to those often observed for real systems and show that these distributions can be explained using supestatistics. Close

Abstract: Many real-world complex systems exhibit a community structure, where groups of nodes share a high internal connection density or strength but have fewer or weaker connections with nodes belonging to different groups. Identifying these groups of nodes is a key challenge in network theory and much attention has been devoted to this specific task. Amongst the methods proposed so far, those based on the modularity function are the most popular and widely used. Modularity is a quality function that assigns a score to each partition of the network, with higher scores corresponding to better partitions. However, despite its wide use, modularity has also been shown to suffer from severe limitations, such as a resolution limit or finding communities on random graphs. We present the properties of a new objective function, modularity density, which was introduced in recent years by Szymanski and collaborators to address some of the limitations mentioned above. Modularity density presents interesting properties as a quality function, and we will derive the analytical dependence of modularity density on connection density in random graphs of any given size. We will also show that modularity density allows for a comparison of the community structure between networks with different number of nodes. Finally, we will present a detailed community detection algorithm based on modularity density, discussing its computational complexity. This presentation will allow me to further disseminate my work to an audience with broad interests. It will help me establish a personal network of connections in the complex systems scientific community. This may enable collaborations, which would be of great benefit in my career as a young researchers. This talk is aimed at researchers with an interest in network science and methods to analyse networked data. Close

Abstract: How much information does a complex networks integrate as a whole over the sum of its parts? Can the complexity of such networks be quantified in an information-theoretic way and be meaningfully coupled to its function? Recently, measures of dynamical complexity such as integrated information have been proposed. However, problems related to the normalization and Bell number of partitions associated to these measures make these approaches computationally infeasible for large-scale networks. Our goal in this work is to address this problem. Our formulation of network integrated information is based on the Kullback-Leibler divergence between the multivariate distribution on the set of network states versus the corresponding factorized distribution over its parts. We find that implementing the maximum information partition optimizes computations. These methods are well-suited for large networks with linear stochastic dynamics. As an application of our formalism, we compute the information complexity of the human brain’s connectome network. Compared to a randomly re-wired network, we find that the specific topology of the brain generates greater information complexity. Close

Abstract: One of the main objectives to study on complex systems and complex networks is to understand how to efficiently control them, or alternatively, to make them difficult to be controlled (and therefore become robust under certain circumstances). While extensive studies have been carried out on controllability of complex networks, which typically aim to finding the minimum set of driver nodes to be connected to external controllers for ensuring that the system can be driven to any state, little has been done for an arguably even more important problem: the optimal control of complex networks, which aims to driving a system to a certain state with the minimum energy cost. A complex system with perfect controllability may not be actually controllable in the real life, if the cost for driving it to the target state is too high. To start, we consider the “simplest” optimal control problem, trying to find the solution for driving a static complex network at the minimum energy cost with a given number of controllers. A projected gradient method has been proposed, which works efficiently in both synthetic and real-life networks. The study is then extended to the case when each controller can only be connected to a single network node for having the lowest connection complexity. Interesting insights reveal that such connections basically avoid high-degree nodes of the network, which is in resonance with recent observations on controllability of complex networks. Such results open the technical path to enabling minimum cost control of complex networks, and contribute new insights into locating the key nodes from a minimum cost control perspective. We shall also discuss on the possible approaches for enhancing the scalability of the proposed method and provide some preliminary testing results on some of these approaches Close