Understanding complex networked systems is key to solving some of the most vexing problems confronting humankind, from discovering how thoughts and behaviors arise from dynamic brain connections, to preventing the spread of disease. However, a critical gap remains in understanding how the structure of networks affects the dynamics of complex systems, which we have been addressing with methods to compute and remove redundancy from them. Whereas patterns of connectivity (structure) have been amply studied in complex networks & systems (CNS), and patterns of dynamics have been studied in dynamical systems theory, much remains to be done to characterize redundancy and its importance for understanding and controlling the dynamics of complex systems −which, ultimately, defines their function. In this talk we will present our recent studies of redundancy in both the structure and dynamics of complex systems.
The first concept we present is the invariant sub-graph that is revealed by the computation of all shortest paths (metric closure) of a weighted graph [1, 2]. We refer to this subgraph as the metric backbone of a complex network [4]. The size of the backbone subgraph, in relation to the size of the original graph, defines the amount of redundancy in the network: edges not on this backbone are superfluous in the computation of shortest paths. We demonstrate the utility of the metric backbone with an analysis of the SocioPatterns datasets [5], which yield duration of contact between pairs of individuals (via wearable sensors), and have been used in models of epidemic spread to evaluate containment policies [6, 7]. We show that the SocioPatterns contact networks are very redundant, with the proportion of semi-metric edges ranging from 50-91%---four of the six networks with larger than 80% redundancy. This means that all shortest paths can be computed with fewer than 50 to 9% of the edges (which comprise the metric backbone). The figure shows the primary school contact network [3] and its metric backbone, which contains only 9% of the edges in the original network. Importantly, the social structure of the contact network is preserved in the backbone subnetwork---the preservation of community structure in the metric backbone is observed in all the six SocioPatterns networks. Finally, we compare epidemic spread simulations, using the original and backbone networks, for different spreading rates to demonstrate the utility of the metric backbone in dynamical processes on networks.
The second concept stems from a dynamics perspective. Based on recent work [9, 10] we show that the control of complex networks crucially depends on redundancy that exists at the level of variable dynamics. To understand the effect of such redundancy, we study automata networks−both systems biology models and large random ensembles of Boolean networks (BN). In these discrete dynamical systems, redundancy is conceptualized as canalization: when a subset of inputs is sufficient to determine the output of an automaton. We discuss two types of canalization: effective connectivity and input symmetry [9]. First, we show that effective connectivity strongly influences the controllability of multivariate dynamics. Indeed, predictions made by structure-only methods can both undershoot and overshoot the number and which sets of variables actually control BN[10]. To understand how control and information effectively propagate in such complex systems, we uncover the effective graph that results after computation of effective connectivity [11]. To study the effect of input symmetry, we further develop our dynamics canalization map, a parsimonious dynamical system representation of the original BN obtained after removal of all redundancy [2]. Mapping canalization in BN via these representations allows us to understand how control pathways operate, aiding the discovery of dynamical modularity and robustness present in such systems. Finally, we demonstrate the utility of the approach with the analysis of a battery 50+ systems biology automata networks, including systems biology models of cancer.
