Unveiling order from chaos by approximate 2-localization of random matrices.

Quantum many-body systems are typically endowed with a tensor product structure. A structure they inherited from probability theory, where the probability of two independent events is the product of the probabilities. The tensor product structure of a Hamiltonian thus gives a natural decomposition of the system into independent smaller subsystems. It is interesting to understand whether a given Hamiltonian is compatible with some particular tensor product structure. In particular, we ask, is there a basis in which an arbitrary Hamiltonian has a 2-local form, i.e., it contains only pairwise interactions? Here we show, using analytical and numerical calculations, that a generic Hamiltonian (e.g., a large random matrix) can be approximately written as a linear combination of two-body interaction terms with high precision; that is, the Hamiltonian is 2-local in a carefully chosen basis. Moreover, we show that these Hamiltonians are not fine-tuned, meaning that the spectrum is robust against perturbations of the coupling constants. Finally, by analyzing the adjacency structure of the couplings [Formula: see text], we suggest a possible mechanism for the emergence of geometric locality from quantum chaos.

Influencer identification in dynamical complex systems.

The integrity and functionality of many real-world complex systems hinge on a small set of pivotal nodes, or influencers. In different contexts, these influencers are defined as either structurally important nodes that maintain the connectivity of networks, or dynamically crucial units that can disproportionately impact certain dynamical processes. In practice, identification of the optimal set of influencers in a given system has profound implications in a variety of disciplines. In this review, we survey recent advances in the study of influencer identification developed from different perspectives, and present state-of-the-art solutions designed for different objectives. In particular, we first discuss the problem of finding the minimal number of nodes whose removal would breakdown the network (i.e. the optimal percolation or network dismantle problem), and then survey methods to locate the essential nodes that are capable of shaping global dynamics with either continuous (e.g. independent cascading models) or discontinuous phase transitions (e.g. threshold models). We conclude the review with a summary and an outlook.

Circuits with broken fibration symmetries perform core logic computations in biological networks.

We show that logic computational circuits in gene regulatory networks arise from a fibration symmetry breaking in the network structure. From this idea we implement a constructive procedure that reveals a hierarchy of genetic circuits, ubiquitous across species, that are surprising analogues to the emblematic circuits of solid-state electronics: starting from the transistor and progressing to ring oscillators, current-mirror circuits to toggle switches and flip-flops. These canonical variants serve fundamental operations of synchronization and clocks (in their symmetric states) and memory storage (in their broken symmetry states). These conclusions introduce a theoretically principled strategy to search for computational building blocks in biological networks, and present a systematic route to design synthetic biological circuits.

Diversity increases the stability of ecosystems.

In 1972, Robert May showed that diversity is detrimental to an ecosystem since, as the number of species increases, the ecosystem is less stable. This is the so-called diversity-stability paradox, which has been derived by considering a mathematical model with linear interactions between the species. Despite being in contradiction with empirical evidence, the diversity-stability paradox has survived the test of time for over 40+ years. In this paper we first show that this paradox is a conclusion driven solely by the linearity of the model employed in its derivation which allows for the neglection of the fixed point solution in the stability analysis. The linear model leads to an ill-posed solution and along with it, its paradoxical stability predictions. We then consider a model ecosystem with nonlinear interactions between species, which leads to a stable ecosystem when the number of species is increased. The saturating non linear term in the species interaction is analogous to a Hill function appearing in systems like gene regulation, neurons, diffusion of information and ecosystems The exact fixed point solution of this model is based on k-core percolation and shows that the paradox disappears. This theoretical result, which is exact and non-perturbative, shows that diversity is beneficial to the ecosystem in agreement with analyzed experimental evidence.

Fibration symmetries uncover the building blocks of biological networks.

A major ambition of systems science is to uncover the building blocks of any biological network to decipher how cellular function emerges from their interactions. Here, we introduce a graph representation of the information flow in these networks as a set of input trees, one for each node, which contains all pathways along which information can be transmitted in the network. In this representation, we find remarkable symmetries in the input trees that deconstruct the network into functional building blocks called fibers. Nodes in a fiber have isomorphic input trees and thus process equivalent dynamics and synchronize their activity. Each fiber can then be collapsed into a single representative base node through an information-preserving transformation called "symmetry fibration," introduced by Grothendieck in the context of algebraic geometry. We exemplify the symmetry fibrations in gene regulatory networks and then show that they universally apply across species and domains from biology to social and infrastructure networks. The building blocks are classified into topological classes of input trees characterized by integer branching ratios and fractal golden ratios of Fibonacci sequences representing cycles of information. Thus, symmetry fibrations describe how complex networks are built from the bottom up to process information through the synchronization of their constitutive building blocks.

K-core robustness in ecological and financial networks.

In many real-world networks, the ability to withstand targeted or global attacks; extinctions; or shocks is vital to the survival of the network itself, and of dependent structures such as economies (for financial networks) or even the planet (for ecosystems). Previous attempts to characterise robustness include nestedness of mutualistic networks or exploration of degree distribution. In this work we present a new approach for characterising the stability and robustness of networks with all-positive interactions by studying the distribution of the k-shell of the underlying network. We find that high occupancy of nodes in the inner and outer k-shells and low occupancy in the middle shells of financial and ecological networks (yielding a "U-shape" in a histogram of k-shell occupancy) provide resilience against both local targeted and global attacks. Investigation of this highly-populated core gives insights into the nature of a network (such as sharp transitions in the core composition of the stock market from a mix of industries to domination by one or two in the mid-1990s) and allow predictions of future network stability, e.g., by monitoring populations of "core" species in an ecosystem or noting when stocks in the core-dominant sector begin to move in lock-step, presaging a dramatic move in the market. Moreover, this "U-shape" recalls core-periphery structure, seen in a wide range of networks including opinion and internet networks, suggesting that the "U-shaped" occupancy histogram and its implications for network health may indeed be universal.

Symmetry group factorization reveals the structure-function relation in the neural connectome of Caenorhabditis elegans.

The neural connectome of the nematode Caenorhabditis elegans has been completely mapped, yet in spite of being one of the smallest connectomes (302 neurons), the design principles that explain how the connectome structure determines its function remain unknown. Here, we find symmetries in the locomotion neural circuit of C. elegans, each characterized by its own symmetry group which can be factorized into the direct product of normal subgroups. The action of these normal subgroups partitions the connectome into sectors of neurons that match broad functional categories. Furthermore, symmetry principles predict the existence of novel finer structures inside these normal subgroups forming feedforward and recurrent networks made of blocks of imprimitivity. These blocks constitute structures made of circulant matrices nested in a hierarchy of block-circulant matrices, whose functionality is understood in terms of neural processing filters responsible for fast processing of information.

The jamming transition is a k-core percolation transition.

We explain the structural origin of the jamming transition in jammed matter as the sudden appearance of k-cores at precise coordination numbers which are related not to the isostatic point, but to the emergence of the giant 3- and 4-cores as given by k-core percolation theory. At the transition, the k-core variables freeze and the k-core dominates the appearance of rigidity. Surprisingly, the 3-D simulation results can be explained with the result of mean-field k-core percolation in the Erdös-Rényi network. That is, the finite-dimensional transition seems to be explained by the infinite-dimensional k-core, implying that the structure of the jammed pack is compatible with a fully random network.

Inference and control of the nosocomial transmission of methicillin-resistant Staphylococcus aureus.

Methicillin-resistant Staphylococcus aureus (MRSA) is a continued threat to human health in both community and healthcare settings. In hospitals, control efforts would benefit from accurate estimation of asymptomatic colonization and infection importation rates from the community. However, developing such estimates remains challenging due to limited observation of colonization and complicated transmission dynamics within hospitals and the community. Here, we develop an inference framework that can estimate these key quantities by combining statistical filtering techniques, an agent-based model, and real-world patient-to-patient contact networks, and use this framework to infer nosocomial transmission and infection importation over an outbreak spanning 6 years in 66 Swedish hospitals. In particular, we identify a small number of patients with disproportionately high risk of colonization. In retrospective control experiments, interventions targeted to these individuals yield a substantial improvement over heuristic strategies informed by number of contacts, length of stay and contact tracing.

Publisher Correction: Finding influential nodes for integration in brain networks using optimal percolation theory.

The original version of this Article contained an error in the last sentence of the first paragraph of the Introduction, which incorrectly read 'Correlation of brain activity is typically measured using functional magnetic resonance imaging (fMRI), and the correlation structure is often referred to as "fu'. The correct version states 'referred to as "functional connectivity"2-6' in place of 'referred to as "fu'. This has been corrected in both the PDF and HTML versions of the Article.

Finding influential nodes for integration in brain networks using optimal percolation theory.

Global integration of information in the brain results from complex interactions of segregated brain networks. Identifying the most influential neuronal populations that efficiently bind these networks is a fundamental problem of systems neuroscience. Here, we apply optimal percolation theory and pharmacogenetic interventions in vivo to predict and subsequently target nodes that are essential for global integration of a memory network in rodents. The theory predicts that integration in the memory network is mediated by a set of low-degree nodes located in the nucleus accumbens. This result is confirmed with pharmacogenetic inactivation of the nucleus accumbens, which eliminates the formation of the memory network, while inactivations of other brain areas leave the network intact. Thus, optimal percolation theory predicts essential nodes in brain networks. This could be used to identify targets of interventions to modulate brain function.

Validation of Twitter opinion trends with national polling aggregates: Hillary Clinton vs Donald Trump.

Measuring and forecasting opinion trends from real-time social media is a long-standing goal of big-data analytics. Despite the large amount of work addressing this question, there has been no clear validation of online social media opinion trend with traditional surveys. Here we develop a method to infer the opinion of Twitter users by using a combination of statistical physics of complex networks and machine learning based on hashtags co-occurrence to build an in-domain training set of the order of a million tweets. We validate our method in the context of 2016 US Presidential Election by comparing the Twitter opinion trend with the New York Times National Polling Average, representing an aggregate of hundreds of independent traditional polls. The Twitter opinion trend follows the aggregated NYT polls with remarkable accuracy. We investigate the dynamics of the social network formed by the interactions among millions of Twitter supporters and infer the support of each user to the presidential candidates. Our analytics unleash the power of Twitter to uncover social trends from elections, brands to political movements, and at a fraction of the cost of traditional surveys.

Emergence of robustness in networks of networks.

A model of interdependent networks of networks (NONs) was introduced recently [Proc. Natl. Acad. Sci. (USA) 114, 3849 (2017)PNASA60027-842410.1073/pnas.1620808114] in the context of brain activation to identify the neural collective influencers in the brain NON. Here we investigate the emergence of robustness in such a model, and we develop an approach to derive an exact expression for the random percolation transition in Erdös-Rényi NONs of this kind. Analytical calculations are in agreement with numerical simulations, and highlight the robustness of the NON against random node failures, which thus presents a new robust universality class of NONs. The key aspect of this robust NON model is that a node can be activated even if it does not belong to the giant mutually connected component, thus allowing the NON to be built from below the percolation threshold, which is not possible in previous models of interdependent networks. Interestingly, the phase diagram of the model unveils particular patterns of interconnectivity for which the NON is most vulnerable, thereby marking the boundary above which the robustness of the system improves with increasing dependency connections.

Inferring personal economic status from social network location.

It is commonly believed that patterns of social ties affect individuals' economic status. Here we translate this concept into an operational definition at the network level, which allows us to infer the economic well-being of individuals through a measure of their location and influence in the social network. We analyse two large-scale sources: telecommunications and financial data of a whole country's population. Our results show that an individual's location, measured as the optimal collective influence to the structural integrity of the social network, is highly correlated with personal economic status. The observed social network patterns of influence mimic the patterns of economic inequality. For pragmatic use and validation, we carry out a marketing campaign that shows a threefold increase in response rate by targeting individuals identified by our social network metrics as compared to random targeting. Our strategy can also be useful in maximizing the effects of large-scale economic stimulus policies.

Model of brain activation predicts the neural collective influence map of the brain.

Efficient complex systems have a modular structure, but modularity does not guarantee robustness, because efficiency also requires an ingenious interplay of the interacting modular components. The human brain is the elemental paradigm of an efficient robust modular system interconnected as a network of networks (NoN). Understanding the emergence of robustness in such modular architectures from the interconnections of its parts is a longstanding challenge that has concerned many scientists. Current models of dependencies in NoN inspired by the power grid express interactions among modules with fragile couplings that amplify even small shocks, thus preventing functionality. Therefore, we introduce a model of NoN to shape the pattern of brain activations to form a modular environment that is robust. The model predicts the map of neural collective influencers (NCIs) in the brain, through the optimization of the influence of the minimal set of essential nodes responsible for broadcasting information to the whole-brain NoN. Our results suggest intervention protocols to control brain activity by targeting influential neural nodes predicted by network theory.

Efficient collective influence maximization in cascading processes with first-order transitions.

In many social and biological networks, the collective dynamics of the entire system can be shaped by a small set of influential units through a global cascading process, manifested by an abrupt first-order transition in dynamical behaviors. Despite its importance in applications, efficient identification of multiple influential spreaders in cascading processes still remains a challenging task for large-scale networks. Here we address this issue by exploring the collective influence in general threshold models of cascading process. Our analysis reveals that the importance of spreaders is fixed by the subcritical paths along which cascades propagate: the number of subcritical paths attached to each spreader determines its contribution to global cascades. The concept of subcritical path allows us to introduce a scalable algorithm for massively large-scale networks. Results in both synthetic random graphs and real networks show that the proposed method can achieve larger collective influence given the same number of seeds compared with other scalable heuristic approaches.

Collective Behaviour in Video Viewing: A Thermodynamic Analysis of Gaze Position.

Videos and commercials produced for large audiences can elicit mixed opinions. We wondered whether this diversity is also reflected in the way individuals watch the videos. To answer this question, we presented 65 commercials with high production value to 25 individuals while recording their eye movements, and asked them to provide preference ratings for each video. We find that gaze positions for the most popular videos are highly correlated. To explain the correlations of eye movements, we model them as "interactions" between individuals. A thermodynamic analysis of these interactions shows that they approach a "critical" point such that any stronger interaction would put all viewers into lock-step and any weaker interaction would fully randomise patterns. At this critical point, groups with similar collective behaviour in viewing patterns emerge while maintaining diversity between groups. Our results suggest that popularity of videos is already evident in the way we look at them, and that we maintain diversity in viewing behaviour even as distinct patterns of groups emerge. Our results can be used to predict popularity of videos and commercials at the population level from the collective behaviour of the eye movements of a few viewers.

Collective Influence of Multiple Spreaders Evaluated by Tracing Real Information Flow in Large-Scale Social Networks.

Identifying the most influential spreaders that maximize information flow is a central question in network theory. Recently, a scalable method called "Collective Influence (CI)" has been put forward through collective influence maximization. In contrast to heuristic methods evaluating nodes' significance separately, CI method inspects the collective influence of multiple spreaders. Despite that CI applies to the influence maximization problem in percolation model, it is still important to examine its efficacy in realistic information spreading. Here, we examine real-world information flow in various social and scientific platforms including American Physical Society, Facebook, Twitter and LiveJournal. Since empirical data cannot be directly mapped to ideal multi-source spreading, we leverage the behavioral patterns of users extracted from data to construct "virtual" information spreading processes. Our results demonstrate that the set of spreaders selected by CI can induce larger scale of information propagation. Moreover, local measures as the number of connections or citations are not necessarily the deterministic factors of nodes' importance in realistic information spreading. This result has significance for rankings scientists in scientific networks like the APS, where the commonly used number of citations can be a poor indicator of the collective influence of authors in the community.

Collective Influence Algorithm to find influencers via optimal percolation in massively large social media.

We elaborate on a linear-time implementation of Collective-Influence (CI) algorithm introduced by Morone, Makse, Nature 524, 65 (2015) to find the minimal set of influencers in networks via optimal percolation. The computational complexity of CI is O(N log N) when removing nodes one-by-one, made possible through an appropriate data structure to process CI. We introduce two Belief-Propagation (BP) variants of CI that consider global optimization via message-passing: CI propagation (CIP) and Collective-Immunization-Belief-Propagation algorithm (CIBP) based on optimal immunization. Both identify a slightly smaller fraction of influencers than CI and, remarkably, reproduce the exact analytical optimal percolation threshold obtained in Random Struct. Alg. 21, 397 (2002) for cubic random regular graphs, leaving little room for improvement for random graphs. However, the small augmented performance comes at the expense of increasing running time to O(N(2)), rendering BP prohibitive for modern-day big-data. For instance, for big-data social networks of 200 million users (e.g., Twitter users sending 500 million tweets/day), CI finds influencers in 2.5 hours on a single CPU, while all BP algorithms (CIP, CIBP and BDP) would take more than 3,000 years to accomplish the same task.