Explicit non-Markovian susceptible-infected-susceptible mean-field epidemic threshold for Weibull and Gamma infections but Poisson curings

Although non-Markovian processes are considerably more complicated to analyze, real-world epidemics are likely non-Markovian, because the infection time is not always exponentially distributed. Here, we present analytic expressions of the epidemic threshold in a Weibull and a Gamma SIS epidemic on any network, where the infection time is Weibull, respectively, Gamma, but the recovery time is exponential. The theory is compared with precise simulations. The mean-field non-Markovian epidemic thresholds, both for a Weibull and Gamma infection time, are physically similar and interpreted via the occurrence time of an infection during a healthy period of each node in the graph. Our theory couples the type of a viral item, specified by a shape parameter of the Weibull or Gamma distribution, to its corresponding network-wide endemic spreading power, which is specified by the mean-field non-Markovian epidemic threshold in any network.

Unified mean-field framework for susceptible-infected-susceptible epidemics on networks, based on graph partitioning and the isoperimetric inequality

We propose an approximation framework that unifies and generalizes a number of existing mean-field approximation methods for the susceptible-infected-susceptible (SIS) epidemic model on complex networks. We derive the framework, which we call the unified mean-field framework (UMFF), as a set of approximations of the exact Markovian SIS equations. Our main novelty is that we describe the mean-field approximations from the perspective of the isoperimetric problem, which results in bounds on the UMFF approximation error. These new bounds provide insight in the accuracy of existing mean-field methods, such as the N-intertwined mean-field approximation and heterogeneous mean-field method, which are contained by UMFF. Additionally, the isoperimetric inequality relates the UMFF approximation accuracy to the regularity notions of Szemerédi's regularity lemma.

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.

The epidemic spreading model and the direction of information flow in brain networks

The interplay between structural connections and emerging information flow in the human brain remains an open research problem. A recent study observed global patterns of directional information flow in empirical data using the measure of transfer entropy. For higher frequency bands, the overall direction of information flow was from posterior to anterior regions whereas an anterior-to-posterior pattern was observed in lower frequency bands. In this study, we applied a simple Susceptible-Infected-Susceptible (SIS) epidemic spreading model on the human connectome with the aim to reveal the topological properties of the structural network that give rise to these global patterns. We found that direct structural connections induced higher transfer entropy between two brain regions and that transfer entropy decreased with increasing distance between nodes (in terms of hops in the structural network). Applying the SIS model, we were able to confirm the empirically observed opposite information flow patterns and posterior hubs in the structural network seem to play a dominant role in the network dynamics. For small time scales, when these hubs acted as strong receivers of information, the global pattern of information flow was in the posterior-to-anterior direction and in the opposite direction when they were strong senders. Our analysis suggests that these global patterns of directional information flow are the result of an unequal spatial distribution of the structural degree between posterior and anterior regions and their directions seem to be linked to different time scales of the spreading process.

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.

Interconnectivity structure of a general interdependent network

A general two-layer network consists of two networks G_{1} and G_{2}, whose interconnection pattern is specified by the interconnectivity matrix B. We deduce desirable properties of B from a dynamic process point of view. Many dynamic processes are described by the Laplacian matrix Q. A regular topological structure of the interconnectivity matrix B (constant row and column sum) enables the computation of a nontrivial eigenmode (eigenvector and eigenvalue) of Q. The latter eigenmode is independent from G_{1} and G_{2}. Such a regularity in B, associated to equitable partitions, suggests design rules for the construction of interconnected networks and is deemed crucial for the interconnected network to show intriguing behavior, as discovered earlier for the special case where B=wI refers to an individual node to node interconnection with interconnection strength w. Extensions to a general m-layer network are also discussed.

Predicting haemodynamic networks using electrophysiology: The role of non-linear and cross-frequency interactions

Understanding the electrophysiological basis of resting state networks (RSNs) in the human brain is a critical step towards elucidating how inter-areal connectivity supports healthy brain function. In recent years, the relationship between RSNs (typically measured using haemodynamic signals) and electrophysiology has been explored using functional Magnetic Resonance Imaging (fMRI) and magnetoencephalography (MEG). Significant progress has been made, with similar spatial structure observable in both modalities. However, there is a pressing need to understand this relationship beyond simple visual similarity of RSN patterns. Here, we introduce a mathematical model to predict fMRI-based RSNs using MEG. Our unique model, based upon a multivariate Taylor series, incorporates both phase and amplitude based MEG connectivity metrics, as well as linear and non-linear interactions within and between neural oscillations measured in multiple frequency bands. We show that including non-linear interactions, multiple frequency bands and cross-frequency terms significantly improves fMRI network prediction. This shows that fMRI connectivity is not only the result of direct electrophysiological connections, but is also driven by the overlap of connectivity profiles between separate regions. Our results indicate that a complete understanding of the electrophysiological basis of RSNs goes beyond simple frequency-specific analysis, and further exploration of non-linear and cross-frequency interactions will shed new light on distributed network connectivity, and its perturbation in pathology.

•

We introduce a mathematical model to predict fMRI-based RSNs using MEG.

•

Our model is based on a multi-variate Taylor series expansion.

•

The electrophysiological basis of RSNs goes beyond frequency-band specific analysis.

•

RSNs result 1) from multiple frequency bands and cross-frequency coupling.

•

RSNs result 2) from direct and shared electrophysiological connectivity.

Accuracy criterion for the mean-field approximation in susceptible-infected-susceptible epidemics on networks

Mean-field approximations (MFAs) are frequently used in physics. When a process (such as an epidemic or a synchronization) on a network is approximated by MFA, a major hurdle is the determination of those graphs for which MFA is reasonably accurate. Here, we present an accuracy criterion for Markovian susceptible-infected-susceptible (SIS) epidemics on any network, based on the spectrum of the adjacency and SIS covariance matrix. We evaluate the MFA criterion for the complete and star graphs analytically, and numerically for connected Erdős-Rényi random graphs for small size N≤14. The accuracy of MFA increases with average degree and with N. Precise simulations (up to network sizes N=100) of the MFA accuracy criterion versus N for the complete graph, star, square lattice, and path graphs lead us to conjecture that the worst MFA accuracy decreases, for large N, proportionally to the inverse of the spectral radius of the adjacency matrix of the graph.

The relation between structural and functional connectivity patterns in complex brain networks

OBJECTIVE

An important problem in systems neuroscience is the relation between complex structural and functional brain networks. Here we use simulations of a simple dynamic process based upon the susceptible-infected-susceptible (SIS) model of infection dynamics on an empirical structural brain network to investigate the extent to which the functional interactions between any two brain areas depend upon (i) the presence of a direct structural connection; and (ii) the degree product of the two areas in the structural network.

METHODS

For the structural brain network, we used a 78×78 matrix representing known anatomical connections between brain regions at the level of the AAL atlas (Gong et al., 2009). On this structural network we simulated brain dynamics using a model derived from the study of epidemic processes on networks. Analogous to the SIS model, each vertex/brain region could be in one of two states (inactive/active) with two parameters β and δ determining the transition probabilities. First, the phase transition between the fully inactive and partially active state was investigated as a function of β and δ. Second, the statistical interdependencies between time series of node states were determined (close to and far away from the critical state) with two measures: (i) functional connectivity based upon the correlation coefficient of integrated activation time series; and (ii) effective connectivity based upon conditional co-activation at different time intervals.

RESULTS

We find a phase transition between an inactive and a partially active state for a critical ratio τ=β/δ of the transition rates in agreement with the theory of SIS models. Slightly above the critical threshold, node activity increases with degree, also in line with epidemic theory. The functional, but not the effective connectivity matrix closely resembled the underlying structural matrix. Both functional connectivity and, to a lesser extent, effective connectivity were higher for connected as compared to disconnected (i.e.: not directly connected) nodes. Effective connectivity scaled with the degree product. For functional connectivity, a weaker scaling relation was only observed for disconnected node pairs. For random networks with the same degree distribution as the original structural network, similar patterns were seen, but the scaling exponent was significantly decreased especially for effective connectivity.

CONCLUSIONS

Even with a very simple dynamical model it can be shown that functional relations between nodes of a realistic anatomical network display clear patterns if the system is studied near the critical transition. The detailed nature of these patterns depends on the properties of the functional or effective connectivity measure that is used. While the strength of functional interactions between any two nodes clearly depends upon the presence or absence of a direct connection, this study has shown that the degree product of the nodes also plays a large role in explaining interaction strength, especially for disconnected nodes and in combination with an effective connectivity measure. The influence of degree product on node interaction strength probably reflects the presence of large numbers of indirect connections.

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.

Susceptible-infected-susceptible epidemics on networks with general infection and cure times

The classical, continuous-time susceptible-infected-susceptible (SIS) Markov epidemic model on an arbitrary network is extended to incorporate infection and curing or recovery times each characterized by a general distribution (rather than an exponential distribution as in Markov processes). This extension, called the generalized SIS (GSIS) model, is believed to have a much larger applicability to real-world epidemics (such as information spread in online social networks, real diseases, malware spread in computer networks, etc.) that likely do not feature exponential times. While the exact governing equations for the GSIS model are difficult to deduce due to their non-Markovian nature, accurate mean-field equations are derived that resemble our previous N-intertwined mean-field approximation (NIMFA) and so allow us to transfer the whole analytic machinery of the NIMFA to the GSIS model. In particular, we establish the criterion to compute the epidemic threshold in the GSIS model. Moreover, we show that the average number of infection attempts during a recovery time is the more natural key parameter, instead of the effective infection rate in the classical, continuous-time SIS Markov model. The relative simplicity of our mean-field results enables us to treat more general types of SIS epidemics, while offering an easier key parameter to measure the average activity of those general viral agents.

Non-Markovian infection spread dramatically alters the susceptible-infected-susceptible epidemic threshold in networks

Most studies on susceptible-infected-susceptible epidemics in networks implicitly assume Markovian behavior: the time to infect a direct neighbor is exponentially distributed. Much effort so far has been devoted to characterize and precisely compute the epidemic threshold in susceptible-infected-susceptible Markovian epidemics on networks. Here, we report the rather dramatic effect of a nonexponential infection time (while still assuming an exponential curing time) on the epidemic threshold by considering Weibullean infection times with the same mean, but different power exponent α. For three basic classes of graphs, the Erdős-Rényi random graph, scale-free graphs and lattices, the average steady-state fraction of infected nodes is simulated from which the epidemic threshold is deduced. For all graph classes, the epidemic threshold significantly increases with the power exponents α. Hence, real epidemics that violate the exponential or Markovian assumption can behave seriously differently than anticipated based on Markov theory.

Susceptible-infected-susceptible epidemics on the complete graph and the star graph: exact analysis

Since mean-field approximations for susceptible-infected-susceptible (SIS) epidemics do not always predict the correct scaling of the epidemic threshold of the SIS metastable regime, we propose two novel approaches: (a) an ε-SIS generalized model and (b) a modified SIS model that prevents the epidemic from dying out (i.e., without the complicating absorbing SIS state). Both adaptations of the SIS model feature a precisely defined steady state (that corresponds to the SIS metastable state) and allow an exact analysis in the complete and star graph consisting of a central node and N leaves. The N-intertwined mean-field approximation (NIMFA) is shown to be nearly exact for the complete graph but less accurate to predict the correct scaling of the epidemic threshold τ(c) in the star graph, which is found as τ(c)=ατ(c)((1)), where α=√[1/2 logN + 3/2 log logN] and where τ(c)((1))=1/√[N]<τ(c) is the first-order epidemic threshold for the star in NIMFA and equal to the inverse of the spectral radius of the star's adjacency matrix.

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.

Spectral graph analysis of modularity and assortativity

Expressions and bounds for Newman's modularity are presented. These results reveal conditions for or properties of the maximum modularity of a network. The influence of the spectrum of the modularity matrix on the maximum modularity is discussed. The second part of the paper investigates how the maximum modularity, the number of clusters, and the hop count of the shortest paths vary when the assortativity of the graph is changed via degree-preserving rewiring. Via simulations, we show that the maximum modularity increases, the number of clusters decreases, and the average hop count and the effective graph resistance increase with increasing assortativity.

Effect of tumor resection on the characteristics of functional brain networks

Brain functioning such as cognitive performance depends on the functional interactions between brain areas, namely, the functional brain networks. The functional brain networks of a group of patients with brain tumors are measured before and after tumor resection. In this work, we perform a weighted network analysis to understand the effect of neurosurgery on the characteristics of functional brain networks. Statistically significant changes in network features have been discovered in the beta (13-30 Hz) band after neurosurgery: the link weight correlation around nodes and within triangles increases which implies improvement in local efficiency of information transfer and robustness; the clustering of high link weights in a subgraph becomes stronger, which enhances the global transport capability; and the decrease in the synchronization or virus spreading threshold, revealed by the increase in the largest eigenvalue of the adjacency matrix, which suggests again the improvement of information dissemination.

Spectral perturbation and reconstructability of complex networks

In recent years, many network perturbation techniques, such as topological perturbations and service perturbations, were employed to study and improve the robustness of complex networks. However, there is no general way to evaluate the network robustness. In this paper, we propose a global measure for a network, the reconstructability coefficient theta , defined as the maximum number of eigenvalues that can be removed, subject to the condition that the adjacency matrix can be reconstructed exactly. Our main finding is that a linear scaling law, E[theta]=aN, seems universal in that it holds for all networks that we have studied.