Decreasing the spectral radius of a graph by link removals

Network Robustness Prediction: Influence of Training Data Distributions

Network robustness refers to the ability of a network to continue its functioning against malicious attacks, which is critical for various natural and industrial networks. Network robustness can be quantitatively measured by a sequence of values that record the remaining functionality after a sequential node- or edge-removal attacks. Robustness evaluations are traditionally determined by attack simulations, which are computationally very time-consuming and sometimes practically infeasible. The convolutional neural network (CNN)-based prediction provides a cost-efficient approach to fast evaluating the network robustness. In this article, the prediction performances of the learning feature representation-based CNN (LFR-CNN) and PATCHY-SAN methods are compared through extensively empirical experiments. Specifically, three distributions of network size in the training data are investigated, including the uniform, Gaussian, and extra distributions. The relationship between the CNN input size and the dimension of the evaluated network is studied. Extensive experimental results reveal that compared to the training data of uniform distribution, the Gaussian and extra distributions can significantly improve both the prediction performance and the generalizability, for both LFR-CNN and PATCHY-SAN, and for various functionality robustness. The extension ability of LFR-CNN is significantly better than PATCHY-SAN, verified by extensive comparisons on predicting the robustness of unseen networks. In general, LFR-CNN outperforms PATCHY-SAN, and thus LFR-CNN is recommended over PATCHY-SAN. However, since both LFR-CNN and PATCHY-SAN have advantages for different scenarios, the optimal settings of the input size of CNN are recommended under different configurations.

A control measure for epidemic spread based on the susceptible-infectious-susceptible (SIS) model

When an epidemic occurs in a network, finding the important links and cutting them off is an effective measure for preventing the spread of the epidemic. Traditional methods that remove important links easily lead to a disconnected network, inevitably incurring high costs arising from quarantining individuals or communities in a real-world network. In this study, we combine the clustering coefficient and the eigenvector to identify the important links using the susceptible-infectious-susceptible (SIS) model. The results show that our approach can improve the epidemic threshold while maintaining the connectivity of the network to control the spread of the epidemic. Experiments on multiple real-world and synthetic networks of varying sizes, demonstrate the effectiveness and scalability of our approach.

On the sensitivity of centrality metrics

Despite the huge importance that the centrality metrics have in understanding the topology of a network, too little is known about the effects that small alterations in the topology of the input graph induce in the norm of the vector that stores the node centralities. If so, then it could be possible to avoid re-calculating the vector of centrality metrics if some minimal changes occur in the network topology, which would allow for significant computational savings. Hence, after formalising the notion of centrality, three of the most basic metrics were herein considered (i.e., Degree, Eigenvector, and Katz centrality). To perform the simulations, two probabilistic failure models were used to describe alterations in network topology: Uniform (i.e., all nodes can be independently deleted from the network with a fixed probability) and Best Connected (i.e., the probability a node is removed depends on its degree). Our analysis suggests that, in the case of degree, small variations in the topology of the input graph determine small variations in Degree centrality, independently of the topological features of the input graph; conversely, both Eigenvector and Katz centralities can be extremely sensitive to changes in the topology of the input graph. In other words, if the input graph has some specific features, even small changes in the topology of the input graph can have catastrophic effects on the Eigenvector or Katz centrality.

Structural network characteristics affect epidemic severity and prediction in social contact networks

Understanding and mitigating epidemic spread in complex networks requires the measurement of structural network properties associated with epidemic risk. Classic measures of epidemic thresholds like the basic reproduction number (R0) have been adapted to account for the structure of social contact networks but still may be unable to capture epidemic potential relative to more recent measures based on spectral graph properties. Here, we explore the ability of R0 and the spectral radius of the social contact network to estimate epidemic susceptibility. To do so, we simulate epidemics on a series of constructed (small world, scale-free, and random networks) and a collection of over 700 empirical biological social contact networks. Further, we explore how other network properties are related to these two epidemic estimators (R0 and spectral radius) and mean infection prevalence in simulated epidemics. Overall, we find that network properties strongly influence epidemic dynamics and the subsequent utility of R0 and spectral radius as indicators of epidemic risk.

Recovering Power Grids Using Strategies Based on Network Metrics and Greedy Algorithms

For this study, we investigated efficient strategies for the recovery of individual links in power grids governed by the direct current (DC) power flow model, under random link failures. Our primary objective was to explore the efficacy of recovering failed links based solely on topological network metrics. In total, we considered 13 recovery strategies, which encompassed 2 strategies based on link centrality values (link betweenness and link flow betweenness), 8 strategies based on the products of node centrality values at link endpoints (degree, eigenvector, weighted eigenvector, closeness, electrical closeness, weighted electrical closeness, zeta vector, and weighted zeta vector), and 2 heuristic strategies (greedy recovery and two-step greedy recovery), in addition to the random recovery strategy. To evaluate the performance of these proposed strategies, we conducted simulations on three distinct power systems: the IEEE 30, IEEE 39, and IEEE 118 systems. Our findings revealed several key insights: Firstly, there were notable variations in the performance of the recovery strategies based on topological network metrics across different power systems. Secondly, all such strategies exhibited inferior performance when compared to the heuristic recovery strategies. Thirdly, the two-step greedy recovery strategy consistently outperformed the others, with the greedy recovery strategy ranking second. Based on our results, we conclude that relying solely on a single metric for the development of a recovery strategy is insufficient when restoring power grids following link failures. By comparison, recovery strategies employing greedy algorithms prove to be more effective choices.

Abrupt transition of the efficient vaccination strategy in a population with heterogeneous fatality rates

An insufficient supply of an effective SARS-CoV-2 vaccine in most countries demands an effective vaccination strategy to minimize the damage caused by the disease. Currently, many countries vaccinate their population in descending order of age (i.e., descending order of fatality rate) to minimize the deaths caused by the disease; however, the effectiveness of this strategy needs to be quantitatively assessed. We employ the susceptible-infected-recovered-dead model to investigate various vaccination strategies. We constructed a metapopulation model with heterogeneous contact and fatality rates and investigated the effectiveness of vaccination strategies to reduce epidemic mortality. We found that the fatality-based strategy, which is currently employed in many countries, is more effective when the contagion rate is high and vaccine supply is low, but the contact-based method outperforms the fatality-based strategy when there is a sufficiently high supply of the vaccine. We identified a discontinuous transition of the optimal vaccination strategy and path-dependency analogous to hysteresis. This transition and path-dependency imply that combining the fatality-based and contact-based strategies is ineffective in reducing the number of deaths. Furthermore, we demonstrate that such phenomena occur in real-world epidemic diseases, such as tuberculosis and COVID-19. We also show that the conclusions of this research are valid even when the complex epidemic stages, efficacy of the vaccine, and reinfection are considered.

Network Models and Simulation Analytics for Multi-scale Dynamics of Biological Invasions

Globalization and climate change facilitate the spread and establishment of invasive species throughout the world via multiple pathways. These spread mechanisms can be effectively represented as diffusion processes on multi-scale, spatial networks. Such network-based modeling and simulation approaches are being increasingly applied in this domain. However, these works tend to be largely domain-specific, lacking any graph theoretic formalisms, and do not take advantage of more recent developments in network science. This work is aimed toward filling some of these gaps. We develop a generic multi-scale spatial network framework that is applicable to a wide range of models developed in the literature on biological invasions. A key question we address is the following: how do individual pathways and their combinations influence the rate and pattern of spread? The analytical complexity arises more from the multi-scale nature and complex functional components of the networks rather than from the sizes of the networks. We present theoretical bounds on the spectral radius and the diameter of multi-scale networks. These two structural graph parameters have established connections to diffusion processes. Specifically, we study how network properties, such as spectral radius and diameter are influenced by model parameters. Further, we analyze a multi-pathway diffusion model from the literature by conducting simulations on synthetic and real-world networks and then use regression tree analysis to identify the important network and diffusion model parameters that influence the dynamics.

Optimization of epilepsy surgery through virtual resections on individual structural brain networks

The success of epilepsy surgery in patients with refractory epilepsy depends upon correct identification of the epileptogenic zone (EZ) and an optimal choice of the resection area. In this study we developed individualized computational models based upon structural brain networks to explore the impact of different virtual resections on the propagation of seizures. The propagation of seizures was modelled as an epidemic process [susceptible-infected-recovered (SIR) model] on individual structural networks derived from presurgical diffusion tensor imaging in 19 patients. The candidate connections for the virtual resection were all connections from the clinically hypothesized EZ, from which the seizures were modelled to start, to other brain areas. As a computationally feasible surrogate for the SIR model, we also removed the connections that maximally reduced the eigenvector centrality (EC) (large values indicate network hubs) of the hypothesized EZ, with a large reduction meaning a large effect. The optimal combination of connections to be removed for a maximal effect were found using simulated annealing. For comparison, the same number of connections were removed randomly, or based on measures that quantify the importance of a node or connection within the network. We found that 90% of the effect (defined as reduction of EC of the hypothesized EZ) could already be obtained by removing substantially less than 90% of the connections. Thus, a smaller, optimized, virtual resection achieved almost the same effect as the actual surgery yet at a considerably smaller cost, sparing on average 27.49% (standard deviation: 4.65%) of the connections. Furthermore, the maximally effective connections linked the hypothesized EZ to hubs. Finally, the optimized resection was equally or more effective than removal based on structural network characteristics both regarding reducing the EC of the hypothesized EZ and seizure spreading. The approach of using reduced EC as a surrogate for simulating seizure propagation can suggest more restrictive resection strategies, whilst obtaining an almost optimal effect on reducing seizure propagation, by taking into account the unique topology of individual structural brain networks of patients.

Prioritizing allocation of COVID-19 vaccines based on social contacts increases vaccination effectiveness

We study allocation of COVID-19 vaccines to individuals based on the structural properties of their underlying social contact network. Even optimistic estimates suggest that most countries will likely take 6 to 24 months to vaccinate their citizens. These time estimates and the emergence of new viral strains urge us to find quick and effective ways to allocate the vaccines and contain the pandemic. While current approaches use combinations of age-based and occupation-based prioritizations, our strategy marks a departure from such largely aggregate vaccine allocation strategies. We propose a novel approach motivated by recent advances in (i) science of real-world networks that point to efficacy of certain vaccination strategies and (ii) digital technologies that improve our ability to estimate some of these structural properties. Using a realistic representation of a social contact network for the Commonwealth of Virginia, combined with accurate surveillance data on spatiotemporal cases and currently accepted models of within- and between-host disease dynamics, we study how a limited number of vaccine doses can be strategically distributed to individuals to reduce the overall burden of the pandemic. We show that allocation of vaccines based on individuals' degree (number of social contacts) and total social proximity time is significantly more effective than the currently used age-based allocation strategy in terms of number of infections, hospitalizations and deaths. Our results suggest that in just two months, by March 31, 2021, compared to age-based allocation, the proposed degree-based strategy can result in reducing an additional 56-110k infections, 3.2- 5.4k hospitalizations, and 700-900 deaths just in the Commonwealth of Virginia. Extrapolating these results for the entire US, this strategy can lead to 3-6 million fewer infections, 181-306k fewer hospitalizations, and 51-62k fewer deaths compared to age-based allocation. The overall strategy is robust even: (i) if the social contacts are not estimated correctly; (ii) if the vaccine efficacy is lower than expected or only a single dose is given; (iii) if there is a delay in vaccine production and deployment; and (iv) whether or not non-pharmaceutical interventions continue as vaccines are deployed. For reasons of implementability, we have used degree, which is a simple structural measure and can be easily estimated using several methods, including the digital technology available today. These results are significant, especially for resource-poor countries, where vaccines are less available, have lower efficacy, and are more slowly distributed.

Secure the IoT Networks as Epidemic Containment Game

The spread of a computer virus among the Internet of Things (IoT) devices can be modeled as an Epidemic Containment (EC) game, where each owner decides the strategy, e.g., installing anti-virus software, to maximize his utility against the susceptible-infected-susceptible (SIS) model of the epidemics on graphs. The EC game’s canonical solution concepts are the Minimum/Maximum Nash Equilibria (MinNE/MaxNE). However, computing the exact MinNE/MaxNE is NP-hard, and only several heuristic algorithms are proposed to approximate the MinNE/MaxNE. To calculate the exact MinNE/MaxNE, we provide a thorough analysis of some special graphs and propose scalable and exact algorithms for general graphs. Especially, our contributions are four-fold. First, we analytically give the MinNE/MaxNE for EC on special graphs based on spectral radius. Second, we provide an integer linear programming formulation (ILP) to determine MinNE/MaxNE for the general graphs with the small epidemic threshold. Third, we propose a branch-and-bound (BnB) framework to compute the exact MinNE/MaxNE in the general graphs with several heuristic methods to branch the variables. Fourth, we adopt NetShiled (NetS) method to approximate the MinNE to improve the scalability. Extensive experiments demonstrate that our BnB algorithm can outperform the naive enumeration method in scalability, and the NetS can improve the scalability significantly and outperform the previous heuristic method in solution quality.

A multilayer temporal network model for STD spreading accounting for permanent and casual partners

Sexually transmitted diseases (STD) modeling has used contact networks to study the spreading of pathogens. Recent findings have stressed the increasing role of casual partners, often enabled by online dating applications. We study the Susceptible-Infected-Susceptible (SIS) epidemic model –appropriate for STDs– over a two-layer network aimed to account for the effect of casual partners in the spreading of STDs. In this novel model, individuals have a set of steady partnerships (links in layer 1). At certain rates, every individual can switch between active and inactive states and, while active, it establishes casual partnerships with some probability with active neighbors in layer 2 (whose links can be thought as potential casual partnerships). Individuals that are not engaged in casual partnerships are classified as inactive, and the transitions between active and inactive states are independent of their infectious state. We use mean-field equations as well as stochastic simulations to derive the epidemic threshold, which decreases substantially with the addition of the second layer. Interestingly, for a given expected number of casual partnerships, which depends on the probabilities of being active, this threshold turns out to depend on the duration of casual partnerships: the longer they are, the lower the threshold.

Perturbation analysis and comparison of network synchronization methods

In many networked systems, synchronization is important and useful, and how to enhance synchronizability is an interesting problem. Based on the matrix perturbation theory, we analyze five methods of network synchronization enhancement, including the link removal, node removal, dividing hub node, pull control, and pinning control methods, and obtain explicit expressions for eigenvalue changes. By these comparisons, we find that, among all these methods, the pull control method is remarkable, as it can extend the synchronization (coupling strength) region from both the left and right sides, for any controlled node. Extensive simulation results are given to support the accuracy of the perturbation-based analysis.

Effective approach to epidemic containment using link equations in complex networks

Epidemic containment is a major concern when confronting large-scale infections in complex networks. Many studies have been devoted to analytically understand how to restructure the network to minimize the impact of major outbreaks of infections at large scale. In many cases, the strategies are based on isolating certain nodes, while less attention has been paid to interventions on the links. In epidemic spreading, links inform about the probability of carrying the contagion of the disease from infected to susceptible individuals. Note that these states depend on the full structure of the network, and its determination is not straightforward from the knowledge of nodes' states. Here, we confront this challenge and propose a set of discrete-time governing equations that can be closed and analyzed, assessing the contribution of links to spreading processes in complex networks. Our approach allows a scheme for the containment of epidemics based on deactivating the most important links in transmitting the disease. The model is validated in synthetic and real networks, yielding an accurate determination of epidemic incidence and critical thresholds. Epidemic containment based on link deactivation promises to be an effective tool to maintain functionality of networks while controlling the spread of diseases, such as disease spread through air transportation networks.

Convex skeletons of complex networks

A convex network can be defined as a network such that every connected induced subgraph includes all the shortest paths between its nodes. A fully convex network would therefore be a collection of cliques stitched together in a tree. In this paper, we study the largest high-convexity part of empirical networks obtained by removing the least number of edges, which we call a convex skeleton. A convex skeleton is a generalization of a network spanning tree in which each edge can be replaced by a clique of arbitrary size. We present different approaches for extracting convex skeletons and apply them to social collaboration and protein interactions networks, autonomous systems graphs and food webs. We show that the extracted convex skeletons retain the degree distribution, clustering, connectivity, distances, node position and also community structure, while making the shortest paths between the nodes largely unique. Moreover, in the Slovenian computer scientists coauthorship network, a convex skeleton retains the strongest ties between the authors, differently from a spanning tree or high-betweenness backbone and high-salience skeleton. A convex skeleton thus represents a simple definition of a network backbone with applications in coauthorship and other social collaboration networks.

Pseudoinverse of the Laplacian and best spreader node in a network

Determining a set of "important" nodes in a network constitutes a basic endeavor in network science. Inspired by electrical flows in a resistor network, we propose the best conducting node j in a graph G as the minimizer of the diagonal element Q_{jj}^{†} of the pseudoinverse matrix Q^{†} of the weighted Laplacian matrix of the graph G. We propose a new graph metric that complements the effective graph resistance R_{G} and that specifies the heterogeneity of the nodal spreading capacity in a graph. Various formulas and bounds for the diagonal element Q_{jj}^{†} are presented. Finally, we compute the pseudoinverse matrix of the Laplacian of star, path, and cycle graphs and derive an expansion and lower bound of the effective graph resistance R_{G} based on the complement of the graph G.

Optimized evolution of networks for principal eigenvector localization

Network science is increasingly being developed to get new insights about behavior and properties of complex systems represented in terms of nodes and interactions. One useful approach is investigating the localization properties of eigenvectors having diverse applications including disease-spreading phenomena in underlying networks. In this work, we evolve an initial random network with an edge rewiring optimization technique considering the inverse participation ratio as a fitness function. The evolution process yields a network having a localized principal eigenvector. We analyze various properties of the optimized networks and those obtained at the intermediate stage. Our investigations reveal the existence of a few special structural features of such optimized networks, for instance, the presence of a set of edges which are necessary for localization, and rewiring only one of them leads to complete delocalization of the principal eigenvector. Furthermore, we report that principal eigenvector localization is not a consequence of changes in a single network property and, preferably, requires the collective influence of various distinct structural as well as spectral features.

Efficient method for comprehensive computation of agent-level epidemic dissemination in networks

Susceptible-infected (SI) and susceptible-infected-susceptible (SIS) are simple agent-based models often employed in epidemic studies. Both models describe the time evolution of infectious diseases in networks whose vertices are either susceptible (S) or infected (I) agents. Precise estimation for disease spreading is one of the major goals in epidemic studies but often restricted to heavy numerical simulations. Analytic methods using operatorial content are subject to the asymmetric eigenvalue problem, limiting the use of perturbative methods. Numerical methods are limited to small populations, since the vector space increases exponentially with population size N. Here, we propose the use of the squared norm of the probability vector to obtain an algebraic equation, which permits the evaluation of stationary states in Markov processes. The equation requires the eigenvalues of symmetrized time generators and takes full advantage of symmetries, reducing the time evolution to an O(N) sparse problem. The calculation of eigenvalues employs quantum many-body techniques, while the standard perturbation theory accounts for small modifications to the network topology.

Approximate formula and bounds for the time-varying susceptible-infected-susceptible prevalence in networks

Based on a recent exact differential equation, the time dependence of the SIS prevalence, the average fraction of infected nodes, in any graph is first studied and then upper and lower bounded by an explicit analytic function of time. That new approximate "tanh formula" obeys a Riccati differential equation and bears resemblance to the classical expression in epidemiology of Kermack and McKendrick [Proc. R. Soc. London A 115, 700 (1927)1364-502110.1098/rspa.1927.0118] but enhanced with graph specific properties, such as the algebraic connectivity, the second smallest eigenvalue of the Laplacian of the graph. We further revisit the challenge of finding tight upper bounds for the SIS (and SIR) epidemic threshold for all graphs. We propose two new upper bounds and show the importance of the variance of the number of infected nodes. Finally, a formula for the epidemic threshold in the cycle (or ring graph) is presented.

Reducing the Spectral Radius of a Torus Network by Link Removal

The optimal link removal (OLR) problem aims at removing a given number of links of a network so that the spectral radius of the residue network obtained by removing the links from the network attains the minimum. Torus networks are a class of regular networks that have witnessed widespread applications. This paper addresses three subproblems of the OLR problem for torus networks, where two or three or four edges are removed. For either of the three subproblems, a link-removing scheme is described. Exhaustive searches show that, for small-sized tori, each of the proposed schemes produces an optimal solution to the corresponding subproblem. Monte-Carlo simulations demonstrate that, for medium-sized tori, each of the three schemes produces a solution to the corresponding subproblem, which is optimal when compared to a large set of randomly produced link-removing schemes. Consequently, it is speculated that each of the three schemes produces an optimal solution to the corresponding subproblem for all torus networks. The set of links produced by each of our schemes is evenly distributed over a network, which may be a common feature of an optimal solution to the OLR problem for regular networks.

Approximating frustration scores in complex networks via perturbed Laplacian spectra

Systems of many interacting components, as found in physics, biology, infrastructure, and the social sciences, are often modeled by simple networks of nodes and edges. The real-world systems frequently confront outside intervention or internal damage whose impact must be predicted or minimized, and such perturbations are then mimicked in the models by altering nodes or edges. This leads to the broad issue of how to best quantify changes in a model network after some type of perturbation. In the case of node removal there are many centrality metrics which associate a scalar quantity with the removed node, but it can be difficult to associate the quantities with some intuitive aspect of physical behavior in the network. This presents a serious hurdle to the application of network theory: real-world utility networks are rarely altered according to theoretic principles unless the kinetic impact on the network's users are fully appreciated beforehand. In pursuit of a kinetically interpretable centrality score, we discuss the f-score, or frustration score. Each f-score quantifies whether a selected node accelerates or inhibits global mean first passage times to a second, independently selected target node. We show that this is a natural way of revealing the dynamical importance of a node in some networks. After discussing merits of the f-score metric, we combine spectral and Laplacian matrix theory in order to quickly approximate the exact f-score values, which can otherwise be expensive to compute. Following tests on both synthetic and real medium-sized networks, we report f-score runtime improvements over exact brute force approaches in the range of 0 to 400% with low error (<3%).

Nodal infection in Markovian susceptible-infected-susceptible and susceptible-infected-removed epidemics on networks are non-negatively correlated

By invoking the famous Fortuin, Kasteleyn, and Ginibre (FKG) inequality, we prove the conjecture that the correlation of infection at the same time between any pair of nodes in a network cannot be negative for (exact) Markovian susceptible-infected-susceptible (SIS) and susceptible-infected-removed (SIR) epidemics on networks. The truth of the conjecture establishes that the N-intertwined mean-field approximation (NIMFA) upper bounds the infection probability in any graph so that network design based on NIMFA always leads to safe protections against malware spread. However, when the infection or/and curing are not Poisson processes, the infection correlation between two nodes can be negative.

Epidemic threshold in directed networks

Epidemics have so far been mostly studied in undirected networks. However, many real-world networks, such as the online social network Twitter and the world wide web, on which information, emotion, or malware spreads, are directed networks, composed of both unidirectional links and bidirectional links. We define the directionality ξ as the percentage of unidirectional links. The epidemic threshold τ(c) for the susceptible-infected-susceptible (SIS) epidemic is lower bounded by 1/λ(1) in directed networks, where λ(1), also called the spectral radius, is the largest eigenvalue of the adjacency matrix. In this work, we propose two algorithms to generate directed networks with a given directionality ξ. The effect of ξ on the spectral radius λ(1), principal eigenvector x(1), spectral gap (λ(1)-|λ(2)|), and algebraic connectivity μ(N-1) is studied. Important findings are that the spectral radius λ(1) decreases with the directionality ξ, whereas the spectral gap and the algebraic connectivity increase with the directionality ξ. The extent of the decrease of the spectral radius depends on both the degree distribution and the degree-degree correlation ρ(D). Hence, in directed networks, the epidemic threshold is larger and a random walk converges to its steady state faster than that in undirected networks with the same degree distribution.

The robustness analysis of wireless sensor networks under uncertain interference

Based on the complex network theory, robustness analysis of condition monitoring wireless sensor network under uncertain interference is present. In the evolution of the topology of sensor networks, the density weighted algebraic connectivity is taken into account, and the phenomenon of removing and repairing the link and node in the network is discussed. Numerical simulation is conducted to explore algebraic connectivity characteristics and network robustness performance. It is found that nodes density has the effect on algebraic connectivity distribution in the random graph model; high density nodes carry more connections, use more throughputs, and may be more unreliable. Moreover, the results show that, when network should be more error tolerant or robust by repairing nodes or adding new nodes, the network should be better clustered in median and high scale wireless sensor networks and be meshing topology in small scale networks.

Towards designing robust coupled networks

Natural and technological interdependent systems have been shown to be highly vulnerable due to cascading failures and an abrupt collapse of global connectivity under initial failure. Mitigating the risk by partial disconnection endangers their functionality. Here we propose a systematic strategy of selecting a minimum number of autonomous nodes that guarantee a smooth transition in robustness. Our method which is based on betweenness is tested on various examples including the famous 2003 electrical blackout of Italy. We show that, with this strategy, the necessary number of autonomous nodes can be reduced by a factor of five compared to a random choice. We also find that the transition to abrupt collapse follows tricritical scaling characterized by a set of exponents which is independent on the protection strategy.

Random line graphs and a linear law for assortativity

For a fixed number N of nodes, the number of links L in the line graph H(N,L) can only appear in consecutive intervals, called a band of L. We prove that some consecutive integers can never represent the number of links L in H(N,L), and they are called a bandgap of L. We give the exact expressions of bands and bandgaps of L. We propose a model which can randomly generate simple graphs which are line graphs of other simple graphs. The essence of our model is to merge step by step a pair of nodes in cliques, which we use to construct line graphs. Obeying necessary rules to ensure that the resulting graphs are line graphs, two nodes to be merged are randomly chosen at each step. If the cliques are all of the same size, the assortativity of the line graphs in each step are close to 0, and the assortativity of the corresponding root graphs increases linearly from -1 to 0 with the steps of the nodal merging process. If we dope the constructing elements of the line graphs-the cliques of the same size-with a relatively smaller number of cliques of different size, the characteristics of the assortativity of the line graphs is completely altered. We also generate line graphs with the cliques whose sizes follow a binomial distribution. The corresponding root graphs, with binomial degree distributions, zero assortativity, and semicircle eigenvalue distributions, are equivalent to Erdős-Rényi random graphs.

Social climber attachment in forming networks produces a phase transition in a measure of connectivity

The formation and fragmentation of networks are typically studied using percolation theory, but most previous research has been restricted to studying a phase transition in cluster size, examining the emergence of a giant component. This approach does not study the effects of evolving network structure on dynamics that occur at the nodes, such as the synchronization of oscillators and the spread of information, epidemics, and neuronal excitations. We introduce and analyze an alternative link-formation rule, called social climber (SC) attachment, that may be combined with arbitrary percolation models to produce a phase transition using the largest eigenvalue of the network adjacency matrix as the order parameter. This eigenvalue is significant in the analyses of many network-coupled dynamical systems in which it measures the quality of global coupling and is hence a natural measure of connectivity. We highlight the important self-organized properties of SC attachment and discuss implications for controlling dynamics on networks.

Epidemics in networks with nodal self-infection and the epidemic threshold

Since the Susceptible-Infected-Susceptible (SIS) epidemic threshold is not precisely defined in spite of its practical importance, the classical SIS epidemic process has been generalized to the ε-SIS model, where a node possesses a self-infection rate ε, in addition to a link infection rate β and a curing rate δ. The exact Markov equations are derived, from which the steady state can be computed. The major advantage of the ε-SIS model is that its steady state is different from the absorbing (or overall-healthy state) and approximates, for a certain range of small ε > 0, the in reality observed phase transition, also called the "metastable" state, that is characterized by the epidemic threshold. The exact steady-state analysis for the complete graph illustrates the effect of small ε and the quality of the first-order mean-field approximation, the N-intertwined model, proposed earlier. Apart from duality principles, often used in the mathematical literature, we present an exact recursion relation for the Markov infinitesimal generator.

Second-order mean-field susceptible-infected-susceptible epidemic threshold

Given the adjacency matrix A of a network, we present a second-order mean-field expansion that improves on the first-order N-intertwined susceptible-infected-susceptible (SIS) epidemic model. Unexpectedly, we found that, in contrast to first-order, second-order mean-field theory is not always possible: the network size N should be large enough. Under the assumption of large N, we show that the crucial and characterizing quantity, the SIS epidemic threshold τ(c), obeys an eigenvalue equation, more complex than the one in the first-order N-intertwined model. However, the resulting epidemic threshold is more accurate: τ(c)((2)) = τ(c)((1)) + O(τ(c)((1))/N), where the first-order epidemic threshold is τ(c)((1)) = 1/λ(1)(A) and where λ(1)(A) is the spectral radius of the adjacency matrix A.