Epidemic threshold and network structure: The interplay of probability of transmission and of persistence in small-size directed networks

A growing number of studies are investigating the effect of contact structure on the dynamics of epidemics in large-scale complex networks. Whether findings thus obtained apply also to networks of small size, and thus to many real-world biological applications, is still an open question. We use numerical simulations of disease spread in directed networks of 100 individual nodes with a constant number of links. We show that, no matter the type of network structure (local, small-world, random and scale-free), there is a linear threshold determined by the probability of infection transmission between connected nodes and the probability of infection persistence in an infected node. The threshold is significantly lower for scale-free networks compared to local, random and small-world ones only if super-connected nodes have a higher number of links both to and from other nodes. The starting point, the node at which the epidemic starts, does not affect the threshold conditions, but has a marked influence on the final size of the epidemic in all kinds of network. There is evidence that contact structure has an influence on the average final size of an epidemic across all starting nodes, with significantly lower values in scale-free networks at equilibrium. Simulations in scale-free networks show a distinctive time-series pattern, which, if found in a real epidemic, can be used to infer the underlying network structure. The findings have relevance also for meta-population ecology and species conservation.     

Disease spread in small-size directed networks: Epidemic threshold, correlation between links to and from nodes, and clustering

Network epidemiology has mainly focused on large-scale complex networks. It is unclear whether findings of these investigations also apply to networks of small size. This knowledge gap is of relevance for many biological applications, including meta-communities, plant–pollinator interactions and the spread of the oomycete pathogen Phytophthora ramorum in networks of plant nurseries. Moreover, many small-size biological networks are inherently asymmetrical and thus cannot be realistically modelled with undirected networks. We modelled disease spread and establishment in directed networks of 100 and 500 nodes at four levels of connectance in six network structures (local, small-world, random, one-way, uncorrelated, and two-way scale-free networks). The model was based on the probability of infection persistence in a node and of infection transmission between connected nodes. Regardless of the size of the network, the epidemic threshold did not depend on the starting node of infection but was negatively related to the correlation coefficient between in- and out-degree for all structures, unless networks were sparsely connected. In this case clustering played a significant role. For small-size scale-free directed networks to have a lower epidemic threshold than other network structures, there needs to be a positive correlation between number of links to and from nodes. When this correlation is negative (one-way scale-free networks), the epidemic threshold for small-size networks can be higher than in non-scale-free networks. Clustering does not necessarily have an influence on the epidemic threshold if connectance is kept constant. Analyses of the influence of the clustering on the epidemic threshold in directed networks can also be spurious if they do not consider simultaneously the effect of the correlation coefficient between in- and out-degree.     

Modelling disease spread and control in networks: implications for plant sciences

Networks are ubiquitous in natural, technological and social systems. They are of increasing relevance for improved understanding and control of infectious diseases of plants, animals and humans, given the interconnectedness of today's world. Recent modelling work on disease development in complex networks shows: the relative rapidity of pathogen spread in scale-free compared with random networks, unless there is high local clustering; the theoretical absence of an epidemic threshold in scale-free networks of infinite size, which implies that diseases with low infection rates can spread in them, but the emergence of a threshold when realistic features are added to networks (e.g. finite size, household structure or deactivation of links); and the influence on epidemic dynamics of asymmetrical interactions. Models suggest that control of pathogens spreading in scale-free networks should focus on highly connected individuals rather than on mass random immunization. A growing number of empirical applications of network theory in human medicine and animal disease ecology confirm the potential of the approach, and suggest that network thinking could also benefit plant epidemiology and forest pathology, particularly in human-modified pathosystems linked by commercial transport of plant and disease propagules. Potential consequences for the study and management of plant and tree diseases are discussed.     

The large graph limit of a stochastic epidemic model on a dynamic multilayer network

We consider a Markovian SIR-type (Susceptible → Infected → Recovered) stochastic epidemic process with multiple modes of transmission on a contact network. The network is given by a random graph following a multilayer configuration model where edges in different layers correspond to potentially infectious contacts of different types. We assume that the graph structure evolves in response to the epidemic via activation or deactivation of edges of infectious nodes. We derive a large graph limit theorem that gives a system of ordinary differential equations (ODEs) describing the evolution of quantities of interest, such as the proportions of infected and susceptible vertices, as the number of nodes tends to infinity. Analysis of the limiting system elucidates how the coupling of edge activation and deactivation to infection status affects disease dynamics, as illustrated by a two-layer network example with edge types corresponding to community and healthcare contacts. Our theorem extends some earlier results describing the deterministic limit of stochastic SIR processes on static, single-layer configuration model graphs. We also describe precisely the conditions for equivalence between our limiting ODEs and the systems obtained via pair approximation, which are widely used in the epidemiological and ecological literature to approximate disease dynamics on networks. The flexible modeling framework and asymptotic results have potential application to many disease settings including Ebola dynamics in West Africa, which was the original motivation for this study.     

Network frailty and the geometry of herd immunity

The spread of infectious disease through communities depends fundamentally on the underlying patterns of contacts between individuals. Generally, the more contacts one individual has, the more vulnerable they are to infection during an epidemic. Thus, outbreaks disproportionately impact the most highly connected demographics. Epidemics can then lead, through immunization or removal of individuals, to sparser networks that are more resistant to future transmission of a given disease. Using several classes of contact networks-Poisson, scale-free and small-world-we characterize the structural evolution of a network due to an epidemic in terms of frailty (the degree to which highly connected individuals are more vulnerable to infection) and interference (the extent to which the epidemic cuts off connectivity among the susceptible population that remains following an epidemic). The evolution of the susceptible network over the course of an epidemic differs among the classes of networks; frailty, relative to interference, accounts for an increasing component of network evolution on networks with greater variance in contacts. The result is that immunization due to prior epidemics can provide greater community protection than random vaccination on networks with heterogeneous contact patterns, while the reverse is true for highly structured populations.     

The number of links to and from the starting node as a predictor of epidemic size in small-size directed networks

Much recent modelling is focusing on epidemics in large-scale complex networks. Whether or not findings of these investigations also apply to networks of small size is still an open question. This is an important gap for many biological applications, including the spread of the oomycete pathogen Phytophthora ramorum in networks of plant nurseries. We use numerical simulations of disease spread and establishment in directed networks of 100 individual nodes at four levels of connectivity. Factors governing epidemic spread are network structure (local, small-world, random, scale-free) and the probabilities of infection persistence in a node and of infection transmission between connected nodes. Epidemic final size at equilibrium varies widely depending on the starting node of infection, although the latter does not affect the threshold condition for spread. The number of links from (out-degree) but not the number of links to (in-degree) the starting node of the epidemic explains a substantial amount of variation in final epidemic size at equilibrium irrespective of the structure of the network. The proportion of variance in epidemic size explained by the out-degree of the starting node increases with the level of connectivity. Targeting highly connected nodes is thus likely to make disease control more effective also in case of small-size populations, a result of relevance not just for the horticultural trade, but for epidemiology in general.     

The emergent properties of a dolphin social network

Many complex networks, including human societies, the Internet, the World Wide Web and power grids, have surprising properties that allow vertices (individuals, nodes, Web pages, etc.) to be in close contact and information to be transferred quickly between them. Nothing is known of the emerging properties of animal societies, but it would be expected that similar trends would emerge from the topology of animal social networks. Despite its small size (64 individuals), the Doubtful Sound community of bottlenose dolphins has the same characteristics. The connectivity of individuals follows a complex distribution that has a scale-free power-law distribution for large k. In addition, the ability for two individuals to be in contact is unaffected by the random removal of individuals. The removal of individuals with many links to others does affect the length of the 'information' path between two individuals, but, unlike other scale-free networks, it does not fragment the cohesion of the social network. These self-organizing phenomena allow the network to remain united, even in the case of catastrophic death events.     

Traveling and Pinned Fronts in Bistable Reaction-Diffusion Systems on Networks

Traveling fronts and stationary localized patterns in bistable reaction-diffusion systems have been broadly studied for classical continuous media and regular lattices. Analogs of such non-equilibrium patterns are also possible in networks. Here, we consider traveling and stationary patterns in bistable one-component systems on random Erdös-Rényi, scale-free and hierarchical tree networks. As revealed through numerical simulations, traveling fronts exist in network-organized systems. They represent waves of transition from one stable state into another, spreading over the entire network. The fronts can furthermore be pinned, thus forming stationary structures. While pinning of fronts has previously been considered for chains of diffusively coupled bistable elements, the network architecture brings about significant differences. An important role is played by the degree (the number of connections) of a node. For regular trees with a fixed branching factor, the pinning conditions are analytically determined. For large Erdös-Rényi and scale-free networks, the mean-field theory for stationary patterns is constructed.     

Modelling disease spread through random and regular contacts in clustered populations

An epidemic spreading through a network of regular, repeated, contacts behaves differently from one that is spread by random interactions: regular contacts serve to reduce the speed and eventual size of an epidemic. This paper uses a mathematical model to explore the difference between regular and random contacts, considering particularly the effect of clustering within the contact network. In a clustered population random contacts have a much greater impact, allowing infection to reach parts of the network that would otherwise be inaccessible. When all contacts are regular, clustering greatly reduces the spread of infection; this effect is negated by a small number of random contacts.     

Network structure, and vaccination strategy and effort interact to affect the dynamics of influenza epidemics

There is growing interest in understanding and controlling the spread of diseases through realistically structured host populations. We investigate how network structures, ranging from circulant, through small-world networks, to random networks, and vaccination strategy and effort interact to influence the proportion of the population infected, the size and timing of the epidemic peak, and the duration of the epidemic. We found these three factors, and their higher-order interactions, significantly influenced epidemic development and extent. Increasing vaccination effort (from 0% to 90%) decreased the number of hosts infected while increasing network randomness worked to increase disease spread. On average, vaccinating hosts based on degree (hubs) resulted in the smallest epidemics while vaccinating hosts with the highest clustering coefficient resulted in the largest epidemics. In a targeted test of five vaccination strategies on a small-world network (probability of rewiring edges=5%) with 10% vaccination effort we found that vaccinating hosts preferentially with high-clustering coefficients (similar to real-world strategies) resulted in twice the number of hosts infected as random vaccinations and nearly a 30-fold higher number of cases than our strategy targeting hubs (highest degree hosts). Our model suggests how vaccinations might be implemented to minimize the extent of an epidemic (e.g., duration and total number infected) as well as the timing and number of hosts infected at a given time over a wide range of structured host networks.     

A Model for Improving the Learning Curves of Artificial Neural Networks

In this article, the performance of a hybrid artificial neural network (i.e. scale-free and small-world) was analyzed and its learning curve compared to three other topologies: random, scale-free and small-world, as well as to the chemotaxis neural network of the nematode Caenorhabditis Elegans. One hundred equivalent networks (same number of vertices and average degree) for each topology were generated and each was trained for one thousand epochs. After comparing the mean learning curves of each network topology with the C. elegans neural network, we found that the networks that exhibited preferential attachment exhibited the best learning curves.     

A scale-free structure prior for graphical models with applications in functional genomics

The problem of reconstructing large-scale, gene regulatory networks from gene expression data has garnered considerable attention in bioinformatics over the past decade with the graphical modeling paradigm having emerged as a popular framework for inference. Analysis in a full Bayesian setting is contingent upon the assignment of a so-called structure prior-a probability distribution on networks, encoding a priori biological knowledge either in the form of supplemental data or high-level topological features. A key topological consideration is that a wide range of cellular networks are approximately scale-free, meaning that the fraction, , of nodes in a network with degree is roughly described by a power-law with exponent between and . The standard practice, however, is to utilize a random structure prior, which favors networks with binomially distributed degree distributions. In this paper, we introduce a scale-free structure prior for graphical models based on the formula for the probability of a network under a simple scale-free network model. Unlike the random structure prior, its scale-free counterpart requires a node labeling as a parameter. In order to use this prior for large-scale network inference, we design a novel Metropolis-Hastings sampler for graphical models that includes a node labeling as a state space variable. In a simulation study, we demonstrate that the scale-free structure prior outperforms the random structure prior at recovering scale-free networks while at the same time retains the ability to recover random networks. We then estimate a gene association network from gene expression data taken from a breast cancer tumor study, showing that scale-free structure prior recovers hubs, including the previously unknown hub SLC39A6, which is a zinc transporter that has been implicated with the spread of breast cancer to the lymph nodes. Our analysis of the breast cancer expression data underscores the value of the scale-free structure prior as an instrument to aid in the identification of candidate hub genes with the potential to direct the hypotheses of molecular biologists, and thus drive future experiments.     

Congruent epidemic models for unstructured and structured populations: analytical reconstruction of a 2003 SARS outbreak

Both the threat of bioterrorism and the natural emergence of contagious diseases underscore the importance of quantitatively understanding disease transmission in structured human populations. Over the last few years, researchers have advanced the mathematical theory of scale-free networks and used such theoretical advancements in pilot epidemic models. Scale-free contact networks are particularly interesting in the realm of mathematical epidemiology, primarily because these networks may allow meaningfully structured populations to be incorporated in epidemic models at moderate or intermediate levels of complexity. Moreover, a scale-free contact network with node degree correlation is in accord with the well-known preferred mixing concept. The present author describes a semi-empirical and deterministic epidemic modeling approach that (a) focuses on time-varying rates of disease transmission in both unstructured and structured populations and (b) employs probability density functions to characterize disease progression and outbreak controls. Given an epidemic curve for a historical outbreak, this modeling approach calls for Monte Carlo calculations (that define the average new infection rate) and solutions to integro-differential equations (that describe outbreak dynamics in an aggregate population or across all network connectivity classes). Numerical results are obtained for the 2003 SARS outbreak in Taiwan and the dynamical implications of time-varying transmission rates and scale-free contact networks are discussed in some detail.     

Discriminating Different Classes of Biological Networks by Analyzing the Graphs Spectra Distribution

The brain''s structural and functional systems, protein-protein interaction, and gene networks are examples of biological systems that share some features of complex networks, such as highly connected nodes, modularity, and small-world topology. Recent studies indicate that some pathologies present topological network alterations relative to norms seen in the general population. Therefore, methods to discriminate the processes that generate the different classes of networks (e.g., normal and disease) might be crucial for the diagnosis, prognosis, and treatment of the disease. It is known that several topological properties of a network (graph) can be described by the distribution of the spectrum of its adjacency matrix. Moreover, large networks generated by the same random process have the same spectrum distribution, allowing us to use it as a “fingerprint”. Based on this relationship, we introduce and propose the entropy of a graph spectrum to measure the “uncertainty” of a random graph and the Kullback-Leibler and Jensen-Shannon divergences between graph spectra to compare networks. We also introduce general methods for model selection and network model parameter estimation, as well as a statistical procedure to test the nullity of divergence between two classes of complex networks. Finally, we demonstrate the usefulness of the proposed methods by applying them to (1) protein-protein interaction networks of different species and (2) on networks derived from children diagnosed with Attention Deficit Hyperactivity Disorder (ADHD) and typically developing children. We conclude that scale-free networks best describe all the protein-protein interactions. Also, we show that our proposed measures succeeded in the identification of topological changes in the network while other commonly used measures (number of edges, clustering coefficient, average path length) failed.     

Biological network comparison using graphlet degree distribution

MOTIVATION: Analogous to biological sequence comparison, comparing cellular networks is an important problem that could provide insight into biological understanding and therapeutics. For technical reasons, comparing large networks is computationally infeasible, and thus heuristics, such as the degree distribution, clustering coefficient, diameter, and relative graphlet frequency distribution have been sought. It is easy to demonstrate that two networks are different by simply showing a short list of properties in which they differ. It is much harder to show that two networks are similar, as it requires demonstrating their similarity in all of their exponentially many properties. Clearly, it is computationally prohibitive to analyze all network properties, but the larger the number of constraints we impose in determining network similarity, the more likely it is that the networks will truly be similar. RESULTS: We introduce a new systematic measure of a network's local structure that imposes a large number of similarity constraints on networks being compared. In particular, we generalize the degree distribution, which measures the number of nodes 'touching' k edges, into distributions measuring the number of nodes 'touching' k graphlets, where graphlets are small connected non-isomorphic subgraphs of a large network. Our new measure of network local structure consists of 73 graphlet degree distributions of graphlets with 2-5 nodes, but it is easily extendible to a greater number of constraints (i.e. graphlets), if necessary, and the extensions are limited only by the available CPU. Furthermore, we show a way to combine the 73 graphlet degree distributions into a network 'agreement' measure which is a number between 0 and 1, where 1 means that networks have identical distributions and 0 means that they are far apart. Based on this new network agreement measure, we show that almost all of the 14 eukaryotic PPI networks, including human, resulting from various high-throughput experimental techniques, as well as from curated databases, are better modeled by geometric random graphs than by Erd?s-Rény, random scale-free, or Barabási-Albert scale-free networks. AVAILABILITY: Software executables are available upon request.     

Emergence of scale-free distribution in protein–protein interaction networks based on random selection of interacting domain pairs

Recent analyses of biological and artificial networks have revealed a common network architecture, called scale-free topology. The origin of the scale-free topology has been explained by using growth and preferential attachment mechanisms. In a cell, proteins are the most important carriers of function, and are composed of domains as elemental units responsible for the physical interaction between protein pairs. Here, we propose a model for protein–protein interaction networks that reveals the emergence of two possible topologies. We show that depending on the number of randomly selected interacting domain pairs, the connectivity distribution follows either a scale-free distribution, even in the absence of the preferential attachment, or a normal distribution. This new approach only requires an evolutionary model of proteins (nodes) but not for the interactions (edges). The edges are added by means of random interaction of domain pairs. As a result, this model offers a new mechanistic explanation for understanding complex networks with a direct biological interpretation because only protein structures and their functions evolved through genetic modifications of amino acid sequences. These findings are supported by numerical simulations as well as experimental data.     

Attack Robustness and Centrality of Complex Networks

Many complex systems can be described by networks, in which the constituent components are represented by vertices and the connections between the components are represented by edges between the corresponding vertices. A fundamental issue concerning complex networked systems is the robustness of the overall system to the failure of its constituent parts. Since the degree to which a networked system continues to function, as its component parts are degraded, typically depends on the integrity of the underlying network, the question of system robustness can be addressed by analyzing how the network structure changes as vertices are removed. Previous work has considered how the structure of complex networks change as vertices are removed uniformly at random, in decreasing order of their degree, or in decreasing order of their betweenness centrality. Here we extend these studies by investigating the effect on network structure of targeting vertices for removal based on a wider range of non-local measures of potential importance than simply degree or betweenness. We consider the effect of such targeted vertex removal on model networks with different degree distributions, clustering coefficients and assortativity coefficients, and for a variety of empirical networks.     

Identifying Cognitive States Using Regularity Partitions

Functional Magnetic Resonance (fMRI) data can be used to depict functional connectivity of the brain. Standard techniques have been developed to construct brain networks from this data; typically nodes are considered as voxels or sets of voxels with weighted edges between them representing measures of correlation. Identifying cognitive states based on fMRI data is connected with recording voxel activity over a certain time interval. Using this information, network and machine learning techniques can be applied to discriminate the cognitive states of the subjects by exploring different features of data. In this work we wish to describe and understand the organization of brain connectivity networks under cognitive tasks. In particular, we use a regularity partitioning algorithm that finds clusters of vertices such that they all behave with each other almost like random bipartite graphs. Based on the random approximation of the graph, we calculate a lower bound on the number of triangles as well as the expectation of the distribution of the edges in each subject and state. We investigate the results by comparing them to the state of the art algorithms for exploring connectivity and we argue that during epochs that the subject is exposed to stimulus, the inspected part of the brain is organized in an efficient way that enables enhanced functionality.     

Laplacian Estrada and Normalized Laplacian Estrada Indices of Evolving Graphs

Large-scale time-evolving networks have been generated by many natural and technological applications, posing challenges for computation and modeling. Thus, it is of theoretical and practical significance to probe mathematical tools tailored for evolving networks. In this paper, on top of the dynamic Estrada index, we study the dynamic Laplacian Estrada index and the dynamic normalized Laplacian Estrada index of evolving graphs. Using linear algebra techniques, we established general upper and lower bounds for these graph-spectrum-based invariants through a couple of intuitive graph-theoretic measures, including the number of vertices or edges. Synthetic random evolving small-world networks are employed to show the relevance of the proposed dynamic Estrada indices. It is found that neither the static snapshot graphs nor the aggregated graph can approximate the evolving graph itself, indicating the fundamental difference between the static and dynamic Estrada indices.     

On analytical approaches to epidemics on networks

One way to describe the spread of an infection on a network is by approximating the network by a random graph. However, the usual way of constructing a random graph does not give any control over the number of triangles in the graph, while these triangles will naturally arise in many networks (e.g. in social networks). In this paper, random graphs with a given degree distribution and a given expected number of triangles are constructed. By using these random graphs we analyze the spread of two types of infection on a network: infections with a fixed infectious period and infections for which an infective individual will infect all of its susceptible neighbors or none. These two types of infection can be used to give upper and lower bounds for R(0), the probability of extinction and other measures of dynamics of infections with more general infectious periods.