True scale-free networks hidden by finite size effects.

We analyze about 200 naturally occurring networks with distinct dynamical origins to formally test whether the commonly assumed hypothesis of an underlying scale-free structure is generally viable. This has recently been questioned on the basis of statistical testing of the validity of power law distributions of network degrees. Specifically, we analyze by finite size scaling analysis the datasets of real networks to check whether the purported departures from power law behavior are due to the finiteness of sample size. We find that a large number of the networks follows a finite size scaling hypothesis without any self-tuning. This is the case of biological protein interaction networks, technological computer and hyperlink networks, and informational networks in general. Marked deviations appear in other cases, especially involving infrastructure and transportation but also in social networks. We conclude that underlying scale invariance properties of many naturally occurring networks are extant features often clouded by finite size effects due to the nature of the sample data.

Bacterial Protein Interaction Networks: Connectivity is Ruled by Gene Conservation, Essentiality and Function.

BACKGROUND: Protein-protein interaction (PPI) networks are the backbone of all processes in living cells. In this work, we relate conservation, essentiality and functional repertoire of a gene to the connectivity k (i.e. the number of interactions, links) of the corresponding protein in the PPI network. METHODS: On a set of 42 bacterial genomes of different sizes, and with reasonably separated evolutionary trajectories, we investigate three issues: i) whether the distribution of connectivities changes between PPI subnetworks of essential and nonessential genes; ii) how gene conservation, measured both by the evolutionary retention index (ERI) and by evolutionary pressures, is related to the connectivity of the corresponding protein; iii) how PPI connectivities are modulated by evolutionary and functional relationships, as represented by the Clusters of Orthologous Genes (COGs). RESULTS: We show that conservation, essentiality and functional specialisation of genes constrain the connectivity of the corresponding proteins in bacterial PPI networks. In particular, we isolated a core of highly connected proteins (connectivities k≥40), which is ubiquitous among the species considered here, though mostly visible in the degree distributions of bacteria with small genomes (less than 1000 genes). CONCLUSION: The genes that support this highly connected core are conserved, essential and, in most cases, belong to the COG cluster J, related to ribosomal functions and the processing of genetic information.

Influence of Technological Innovations on Industrial Production: A Motif Analysis on the Multilayer Network.

In this work we aim at identifying combinations of technological advancements that reveal the presence of local capabilities for a given industrial production. To this end, we generated a multilayer network using country-level patent and trade data, and performed motif-based analysis on this network using a statistical-validation approach derived from maximum-entropy arguments. We show that in many cases the signal far exceeds the noise, providing robust evidence of synergies between different technologies that can lead to a competitive advantage in specific markets. Our results can be highly useful for policymakers to inform industrial and innovation policies.

Network topology mapping of chemical compounds space.

We define bipartite and monopartite relational networks of chemical elements and compounds using two different datasets of inorganic chemical and material compounds, as well as study their topology. We discover that the connectivity between elements and compounds is distributed exponentially for materials, and with a fat tail for chemicals. Compounds networks show similar distribution of degrees, and feature a highly-connected club due to oxygen . Chemical compounds networks appear more modular than material ones, while the communities detected reveal different dominant elements specific to the topology. We successfully reproduce the connectivity of the empirical chemicals and materials networks by using a family of fitness models, where the fitness values are derived from the abundances of the elements in the aggregate compound data. Our results pave the way towards a relational network-based understanding of the inherent complexity of the vast chemical knowledge atlas, and our methodology can be applied to other systems with the ingredient-composite structure.

Capability accumulation patterns across economic, innovation, and knowledge-production activities.

The evolution of economic and innovation systems at the national scale is shaped by a complex dynamics related to the multi-layer network connecting countries to the activities in which they are proficient. Each layer represents a different domain, related to the production of knowledge and goods: scientific research, technology innovation, industrial production and trade. Nestedness, a footprint of a complex dynamics, emerges as a persistent feature across these multiple kinds of activities (i.e. network layers). We observe that, in the layers of innovation and trade, the competitiveness of countries correlates unambiguously with their diversification, while the science layer shows some peculiar features. The evolution of the scientific domain leads to an increasingly modular structure, in which the most developed countries become relatively less active in the less advanced scientific fields, where emerging countries acquire prominence. This observation is in line with a capability-based view of the evolution of economic systems, but with a slight twist. Indeed, while the accumulation of specific know-how and skills is a fundamental step towards development, resource constraints force countries to acquire competitiveness in the more complex research fields at the expense of more basic, albeit less visible (or more crowded) ones. This tendency towards a relatively specialized basket of capabilities leads to a trade-off between the need to diversify in order to evolve and the need to allocate resources efficiently. Collaborative patterns among developed countries reduce the necessity to be competitive in the less sophisticated research fields, freeing resources for the more complex ones.

Cumulative merging percolation: A long-range percolation process in networks.

Percolation on networks is a common framework to model a wide range of processes, from cascading failures to epidemic spreading. Standard percolation assumes short-range interactions, implying that nodes can merge into clusters only if they are nearest neighbors. Cumulative merging percolation (CMP) is a percolation process that assumes long-range interactions such that nodes can merge into clusters even if they are topologically distant. Hence, in CMP clusters do not coincide with the topologically connected components of the network. Previous work has shown that a specific formulation of CMP features peculiar mechanisms for the formation of the giant cluster and allows one to model different network dynamics such as recurrent epidemic processes. Here we develop a more general formulation of CMP in terms of the functional form of the cluster interaction range, showing an even richer phase transition scenario with competition of different mechanisms resulting in crossover phenomena. Our analytic predictions are confirmed by numerical simulations.

Self-induced consensus of Reddit users to characterise the GameStop short squeeze.

The short squeeze of GameStop (GME) shares in mid-January 2021 has been primarily orchestrated by retail investors of the Reddit r/wallstreetbets community. As such, it represents a paramount example of collective coordination action on social media, resulting in large-scale consensus formation and significant market impact. In this work we characterise the structure and time evolution of Reddit conversation data, showing that the occurrence and sentiment of GME-related comments (representing how much users are engaged with GME) increased significantly much before the short squeeze actually took place. Taking inspiration from these early warnings as well as evidence from previous literature, we introduce a model of opinion dynamics where user engagement can trigger a self-reinforcing mechanism leading to the emergence of consensus, which in this particular case is associated to the success of the short squeeze operation. Analytical solutions and model simulations on interaction networks of Reddit users feature a phase transition from heterogeneous to homogeneous opinions as engagement grows, which we qualitatively compare to the sudden hike of GME stock price. Although the model cannot be validated with available data, it offers a possible and minimal interpretation for the increasingly important phenomenon of self-organized collective actions taking place on social networks.

Temporal effects in the growth of networks.

We show that to explain the growth of the citation network by preferential attachment (PA), one has to accept that individual nodes exhibit heterogeneous fitness values that decay with time. While previous PA-based models assumed either heterogeneity or decay in isolation, we propose a simple analytically treatable model that combines these two factors. Depending on the input assumptions, the resulting degree distribution shows an exponential, log-normal or power-law decay, which makes the model an apt candidate for modeling a wide range of real systems.

Co-evolution between codon usage and protein-protein interaction in bacteria.

We study the correlation between the codon usage bias of genetic sequences and the network features of protein-protein interaction (PPI) in bacterial species. We use PCA techniques in the space of codon bias indices to show that genes with similar patterns of codon usage have a significantly higher probability that their encoded proteins are functionally connected and interacting. Importantly, this signal emerges when multiple aspects of codon bias are taken into account at the same time. The present study extends our previous observations on E. coli over a wide set of 34 bacteria. These findings could allow for future investigations on the possible effects of codon bias on the topology of the PPI network, with the aim of improving existing bioinformatics methods for predicting protein interactions.

Fast and scalable likelihood maximization for Exponential Random Graph Models with local constraints.

Exponential Random Graph Models (ERGMs) have gained increasing popularity over the years. Rooted into statistical physics, the ERGMs framework has been successfully employed for reconstructing networks, detecting statistically significant patterns in graphs, counting networked configurations with given properties. From a technical point of view, the ERGMs workflow is defined by two subsequent optimization steps: the first one concerns the maximization of Shannon entropy and leads to identify the functional form of the ensemble probability distribution that is maximally non-committal with respect to the missing information; the second one concerns the maximization of the likelihood function induced by this probability distribution and leads to its numerical determination. This second step translates into the resolution of a system of O(N) non-linear, coupled equations (with N being the total number of nodes of the network under analysis), a problem that is affected by three main issues, i.e. accuracy, speed and scalability. The present paper aims at addressing these problems by comparing the performance of three algorithms (i.e. Newton's method, a quasi-Newton method and a recently-proposed fixed-point recipe) in solving several ERGMs, defined by binary and weighted constraints in both a directed and an undirected fashion. While Newton's method performs best for relatively little networks, the fixed-point recipe is to be preferred when large configurations are considered, as it ensures convergence to the solution within seconds for networks with hundreds of thousands of nodes (e.g. the Internet, Bitcoin). We attach to the paper a Python code implementing the three aforementioned algorithms on all the ERGMs considered in the present work.

Prioritizing the First Doses of SARS-CoV-2 Vaccine to Save the Elderly: The Case Study of Italy.

SARS-CoV-2 is currently causing hundreds of deaths every day in European countries, mostly in not yet vaccinated elderly. Vaccine shortage poses relevant challenges to health authorities, called to act promptly with a scarcity of data. We modeled the mortality reduction of the elderly according to a schedule of mRNA SARS-CoV-2 vaccine that prioritized first dose administration. For the case study of Italy, we show an increase in protected individuals up to 53.4% and a decrease in deaths up to 19.8% in the cohort of over 80's compared with the standard vaccine recalls after 3 or 4 weeks. This model supports the adoption of vaccination campaigns that prioritize the administration of the first doses in the elderly.

Generalized Markov stability of network communities.

We address the problem of community detection in networks by introducing a general definition of Markov stability, based on the difference between the probability fluxes of a Markov chain on the network at different timescales. The specific implementation of the quality function and the resulting optimal community structure thus become dependent both on the type of Markov process and on the specific Markov times considered. For instance, if we use a natural Markov chain dynamics and discount its stationary distribution (that is, we take as reference process the dynamics at infinite time) we obtain the standard formulation of the Markov stability. Notably, the possibility to use finite-time transition probabilities to define the reference process naturally allows detecting communities at different resolutions, without the need to consider a continuous-time Markov chain in the small time limit. The main advantage of our general formulation of Markov stability based on dynamical flows is that we work with lumped Markov chains on network partitions, having the same stationary distribution of the original process. In this way the form of the quality function becomes invariant under partitioning, leading to a self-consistent definition of community structures at different aggregation scales.

Fragility and anomalous susceptibility of weakly interacting networks.

Percolation is a fundamental concept that has brought new understanding of the robustness properties of complex systems. Here we consider percolation on weakly interacting networks, that is, network layers coupled together by much fewer interlinks than the connections within each layer. For these kinds of structures, both continuous and abrupt phase transitions are observed in the size of the giant component. The continuous (second-order) transition corresponds to the formation of a giant cluster inside one layer and has a well-defined percolation threshold. The abrupt transition instead corresponds to the merger of coexisting giant clusters among different layers and is characterized by a remarkable uncertainty in the percolation threshold, which in turns causes an anomalous behavior of the observed susceptibility. We develop a simple mathematical model able to describe this phenomenon, using a susceptibility measure that defines the range where the abrupt transition is more likely to occur. Finite-size scaling analysis in the abrupt region supports the hypothesis of a genuine first-order phase transition.

Grand canonical ensemble of weighted networks.

The cornerstone of statistical mechanics of complex networks is the idea that the links, and not the nodes, are the effective particles of the system. Here, we formulate a mapping between weighted networks and lattice gases, making the conceptual step forward of interpreting weighted links as particles with a generalized coordinate. This leads to the definition of the grand canonical ensemble of weighted complex networks. We derive exact expressions for the partition function and thermodynamic quantities, both in the cases of global and local (i.e., node-specific) constraints on the density and mean energy of particles. We further show that, when modeling real cases of networks, the binary and weighted statistics of the ensemble can be disentangled, leading to a simplified framework for a range of practical applications.

Unfolding the innovation system for the development of countries: coevolution of Science, Technology and Production.

We show that the space in which scientific, technological and economic activities interplay with each other can be mathematically shaped using techniques from statistical physics of networks. We build a holistic view of the innovation system as the tri-layered network of interactions among these many activities (scientific publication, patenting, and industrial production in different sectors), also taking into account the possible time delays. Within this construction we can identify which capabilities and prerequisites are needed to be competitive in a given activity, and even measure how much time is needed to transform, for instance, the technological know-how into economic wealth and scientific innovation, being able to make predictions with a very long time horizon. We find empirical evidence that, at the aggregate scale, technology is the best predictor for industrial and scientific production over the upcoming decades.

Essentiality, conservation, evolutionary pressure and codon bias in bacterial genomes.

Essential genes constitute the core of genes which cannot be mutated too much nor lost along the evolutionary history of a species. Natural selection is expected to be stricter on essential genes and on conserved (highly shared) genes, than on genes that are either nonessential or peculiar to a single or a few species. In order to further assess this expectation, we study here how essentiality of a gene is connected with its degree of conservation among several unrelated bacterial species, each one characterised by its own codon usage bias. Confirming previous results on E. coli, we show the existence of a universal exponential relation between gene essentiality and conservation in bacteria. Moreover, we show that, within each bacterial genome, there are at least two groups of functionally distinct genes, characterised by different levels of conservation and codon bias: i) a core of essential genes, mainly related to cellular information processing; ii) a set of less conserved nonessential genes with prevalent functions related to metabolism. In particular, the genes in the first group are more retained among species, are subject to a stronger purifying conservative selection and display a more limited repertoire of synonymous codons. The core of essential genes is close to the minimal bacterial genome, which is in the focus of recent studies in synthetic biology, though we confirm that orthologs of genes that are essential in one species are not necessarily essential in other species. We also list a set of highly shared genes which, reasonably, could constitute a reservoir of targets for new anti-microbial drugs.

Multiple structural transitions in interacting networks.

Many real-world systems can be modeled as interconnected multilayer networks, namely, a set of networks interacting with each other. Here, we present a perturbative approach to study the properties of a general class of interconnected networks as internetwork interactions are established. We reveal multiple structural transitions for the algebraic connectivity of such systems, between regimes in which each network layer keeps its independent identity or drives diffusive processes over the whole system, thus generalizing previous results reporting a single transition point. Furthermore, we show that, at first order in perturbation theory, the growth of the algebraic connectivity of each layer depends only on the degree configuration of the interaction network (projected on the respective Fiedler vector), and not on the actual interaction topology. Our findings can have important implications in the design of robust interconnected networked systems, particularly in the presence of network layers whose integrity is more crucial for the functioning of the entire system. We finally show results of perturbation theory applied to the adjacency matrix of the interconnected network, which can be useful to characterize percolation processes on such systems.

Erratum: Estimating topological properties of weighted networks from limited information [Phys. Rev. E 92, 040802(R) (2015)].

This corrects the article DOI: 10.1103/PhysRevE.92.040802.

Network reconstruction via density sampling.

Reconstructing weighted networks from partial information is necessary in many important circumstances, e.g. for a correct estimation of systemic risk. It has been shown that, in order to achieve an accurate reconstruction, it is crucial to reliably replicate the empirical degree sequence, which is however unknown in many realistic situations. More recently, it has been found that the knowledge of the degree sequence can be replaced by the knowledge of the strength sequence, which is typically accessible, complemented by that of the total number of links, thus considerably relaxing the observational requirements. Here we further relax these requirements and devise a procedure valid when even the the total number of links is unavailable. We assume that, apart from the heterogeneity induced by the degree sequence itself, the network is homogeneous, so that its (global) link density can be estimated by sampling subsets of nodes with representative density. We show that the best way of sampling nodes is the random selection scheme, any other procedure being biased towards unrealistically large, or small, link densities. We then introduce our core technique for reconstructing both the topology and the link weights of the unknown network in detail. When tested on real economic and financial data sets, our method achieves a remarkable accuracy and is very robust with respect to the sampled subsets, thus representing a reliable practical tool whenever the available topological information is restricted to small portions of nodes.

Enhanced capital-asset pricing model for the reconstruction of bipartite financial networks.

Reconstructing patterns of interconnections from partial information is one of the most important issues in the statistical physics of complex networks. A paramount example is provided by financial networks. In fact, the spreading and amplification of financial distress in capital markets are strongly affected by the interconnections among financial institutions. Yet, while the aggregate balance sheets of institutions are publicly disclosed, information on single positions is mostly confidential and, as such, unavailable. Standard approaches to reconstruct the network of financial interconnection produce unrealistically dense topologies, leading to a biased estimation of systemic risk. Moreover, reconstruction techniques are generally designed for monopartite networks of bilateral exposures between financial institutions, thus failing in reproducing bipartite networks of security holdings (e.g., investment portfolios). Here we propose a reconstruction method based on constrained entropy maximization, tailored for bipartite financial networks. Such a procedure enhances the traditional capital-asset pricing model (CAPM) and allows us to reproduce the correct topology of the network. We test this enhanced CAPM (ECAPM) method on a dataset, collected by the European Central Bank, of detailed security holdings of European institutional sectors over a period of six years (2009-2015). Our approach outperforms the traditional CAPM and the recently proposed maximum-entropy CAPM both in reproducing the network topology and in estimating systemic risk due to fire sales spillovers. In general, ECAPM can be applied to the whole class of weighted bipartite networks described by the fitness model.