with the continual improvement of computing power , individual - based models of infectious disease spread have become more popular .
these models allow us to incorporate stochastic effects , and individual - scale detail in ways that can not be captured in more traditional models . in this paper
, we review a framework based on directed random networks that unifies a range of individual - based models in closed populations , simplifying their analysis .
we then show how this framework provides a new and potentially useful perspective on the design of vaccination strategies .
directed random networks that we call epidemic percolation networks ( epns ) can be used to understand the final outcomes of stochastic 
( sir ) and  susceptible - exposed - infectious - removed  ( seir ) epidemic models . in these models , susceptible persons are infected upon infectious contact with an infectious person .
once infected , they either become infectious immediately ( in sir models ) or become infectious after a latent period ( in seir models ) .
infectious persons eventually recover , after which they can neither infect others nor be infected .
the number of persons infected in an epidemic is called the size of the epidemic , and the proportion of the population infected is called the attack rate .
the average number of persons infected by a typical infectious person in the early stages of an epidemic is called the basic reproductive number and denoted by r0 . for simplicity , we assume the entire population is susceptible to infection at the beginning of an epidemic . when one or more persons are infected , there are two possible outcomes . in a minor epidemic or outbreak ,
the attack rate is negligible and transmission ceases because infected persons fail to make any infectious contacts .
a major epidemic has a higher attack rate and transmission ceases because infected persons make infectious contact with previously infected persons . when r0  1 , major epidemics have probability zero . when r0 >
1 , both major and minor epidemics can occur , and the probability and attack rate of a major epidemic both increase as r0 increases .
( mathematically , the distinction between major and minor epidemics is exact only in the limit of an infinite population size . in a finite population ,
this pattern was first recognized in the 1950s , and it has proven to hold for almost all stochastic s(e)ir epidemic models , including mass - action and network - based models .   the idea of using networks to represent the final outcomes of stochastic epidemic models developed separately for mass - action models and network - based models . in a mass - action model , an infectious person i can make infectious contact with any other person , but the probability of infectious contact from i to any given j  i is inversely proportional to the population size .
in a network - based model , infection is transmitted across the edges of a contact network .
an infectious person i can make infectious contact with j  i only if there is an edge connecting i and j in the contact network . the number of neighbors of i and the probabilities of infectious contact from i to his or her neighbors when i is infectious are independent of the population size . both mass - action and network - based models can be analyzed using epns .
related concepts have been used previously [ 27 ] , generally as a theoretical tool for proving rigorous results .
in fact , this approach deserves more attention as a general framework for exploring s(e)ir epidemics : it provides a powerful theoretical tool , efficient numerical methods , and a guide to vaccination strategy design . in this paper
, we review the fundamental concepts underlying the definition and use of epns and give examples of their use in designing efficient vaccination strategies for both mass - action and network - based epidemic models .
  informally , a single realization of the epn is generated by considering each individual i separately , imagining i is infected , and drawing an arrow from i to all persons with whom he or she makes infectious contact .
this gives us four possible edges in each unordered pair of nodes i and j :    no edge between i and j , a directed edge from i to j ( i  j ) ,   a directed edge from j to i ( i  j ) ,   an undirected edge between i and j ( ij ) .  
				
an outgoing or undirected edge from i to j indicates that i will make infectious contact with j if i is ever infected . if i is infected and j is at the end of one of the outgoing or undirected edges from i , then j is either infected by i or infected from another source prior to receiving infectious contact from i. in either case , j is infected before i recovers from infection .
if person j is infected , then all persons at the end of an outgoing or undirected edge starting from j will be infected before j recovers from infection , and so on .
eventually , all persons connected to i by a series of outgoing or undirected edges will be infected . in the rest of this section ,
we formally define a general stochastic seir model , define its epn , and describe the epidemic threshold in terms of the emergence of giant components in the epn .  
, n. each individual is in one of four possible states : susceptible ( s ) , exposed ( e ) , infectious ( i ) , or removed ( r ) .
person i moves from s to e at his or her infection time ti , with ti =  if i is never infected . after infection
, i has a latent period of length i , during which he or she is infected but not infectious . at time
ti + i , i moves from e to i , beginning an infectious period of length i . at time
ti + ri , where ri = i + i is the recovery period , i moves from i to r. once in r , i can no longer infect others or be infected .
the latent period is a nonnegative random variable with cumulative distribution function ( cdf ) fi( ) and the infectious period is a strictly positive random variable with cdf fi( ) .
an sir model is an seir model where i = 0 with probability one for all i. an epidemic begins with one or more persons infected from outside the population , which we call initial infections . after becoming infectious at time ti + i , person
i makes infectious contact with j  i at time tij = ti + i + ij * , where the infectious contact interval ij * is a strictly positive random variable with ij * =  if infectious contact never occurs . since infectious contact must occur while i is infectious or never , ij *  ( 0 , i ] or ij * = . we define infectious contact to be sufficient to cause infection in a susceptible person , so the infection time tj  tij .
| i ) may depend on properties of i and j ( such as age , immune status , contact intensity , etc . ) .
the general stochastic seir model can be turned into almost any standard epidemic model by choosing appropriate fi( ) , fi( ) , and fij*( | i ) . 

example 1 in the stochastic kermack - mckendrick sir model for a population of size n , infectious persons have a constant hazard  of recovery and there is a constant hazard (n1 ) of infectious contact in every infectious - susceptible pair
. this model can be obtained by taking 
									 ( 1)fii()=1e,fij(    i)={1e/(n1)if  (0,i],1ei/(n1)if  (i, ) . 
  in the stochastic kermack - mckendrick sir model for a population of size n , infectious persons have a constant hazard  of recovery and there is a constant hazard (n1 ) of infectious contact in every infectious - susceptible pair
. this model can be obtained by taking 
									 ( 1)fii()=1e,fij(    i)={1e/(n1)if  (0,i],1ei/(n1)if  (i, ) . 

example 2 in the network - based analogue of the kermack - mckendrick model , infection is transmitted across the edges of a contact network .
it has the same infectious period distribution   as the mass - action   model but a constant hazard  of infectious contact that does not depend on n. thus , 
									 ( 2)fij(    i)={1eif  (0,i],1eiif  (i, ) , 
								 whenever i and j are connected in the contact network .
when i and j are not connected , ij * =  with probability one . 
  in the network - based analogue of the kermack - mckendrick model ,
it has the same infectious period distribution   as the mass - action   model but a constant hazard  of infectious contact that does not depend on n. thus , 
									 ( 2)fij(    i)={1eif  (0,i],1eiif  (i, ) , 
								 whenever i and j are connected in the contact network . when i and j are not connected , ij * =  with probability one .   
the general stochastic epidemic model is time - homogeneous , which means that the latent period , infectious period , and infectious contact interval distributions are specified a priori .
first , we can sample  on the fly  for each new infection i by generating a latent period i and an infectious period i and then sampling ij * from its conditional distribution given i for each j  i. second , we can sample a priori by generating i and i for each i and then sampling ij * from the appropriate conditional distribution for each ordered pair ij before starting the epidemic .
we then look up these values as we need them to run the model .  
					
sampling on the fly is more efficient if the goal is to produce just a single epidemic realization , but sampling a priori provides information about many possible epidemics and leads to the definition of the epn .
for each individual i , 
 sample a latent period i from fi(),sample an infectious period i from fi(),for each j  i , sample an infectious contact interval ij * from fij*( | i ) . 
 
sample a latent period i from fi( ) , sample an infectious period i from fi( ) , for each j  i , sample an infectious contact interval ij * from fij*( | i ) .   for each pair of individuals i and j ,   
 if ij * <  and ji * <  , draw an undirected edge between i and j , if ij * <  and ji * =  , draw a directed edge from i to j , if ij * =  and ji * <  , draw a directed edge from j to i , if ij * =  and ji * =  , draw no edge between i and j. 
  if ij * <  and ji * <  , draw an undirected edge between i and j , if ij * <  and ji * =  , draw a directed edge from i to j , if ij * =  and ji * <  , draw a directed edge from j to i , if ij * =  and ji * =  , draw no edge between i and j.  
					 the time homogeneity assumption guarantees that i , i , and each ij * are chosen from the correct distributions regardless of when node i actually becomes infected . for a population of size n , there are up to 2 possible realizations of the epn , each with a different edge set . the probability of each possible edge set is determined by the underlying seir model .  
the most important properties of the epn are its degree distribution and its component size distributions .
the indegree , outdegree , and undirected degree of node i are the number of incoming , outgoing , and undirected edges incident to i. the degree distribution of the epn is the joint distribution of these degrees over the nodes in the network .
the in - component of node i is the set of nodes from which i can be reached by following a series of edges in the correct direction .
the out - component of node i is the set of nodes that can be reached from i by following a series of edges in the correct direction . in both definitions ,
undirected edges can be crossed in either direction and the in- and out - components of node i include i itself .
if any node in the in - component of i is infected , then i will be infected eventually .
if i is infected , then every node in the out - component of i will be infected eventually . since the epn is a random network , each node does not have fixed in- , out- , or undirected degrees or fixed in- and out - components ( though these are fixed in any single realization of the epn ) .
however , the distribution of the out - component sizes of node i is exactly the same as the distribution of epidemic sizes obtained in repeated runs of the corresponding s(e)ir model with i as the initial infection [ 8 , 9 ] .
the epidemic threshold of an s(e)ir model corresponds to the emergence of giant components in the epn .
a strongly connected component is a group of nodes in which each node can be reached from every other node by following a series of edges .
the nodes in a strongly connected component all have the same in - component and the same out - component .
the epn for a model below the epidemic threshold consists of many small strongly connected components .
the epn for a model above the epidemic threshold consists of a single giant strongly connected component ( gscc ) and many small strongly connected components .
the in- and out - components of nodes in the gscc are called the giant in - component ( gin ) and the giant out - component ( gout ) .
if all initial infections occur outside the gin , a minor epidemic occurs because the out - components of all initial infections are small .
if an initial infection occurs in the gin , infection spreads to the gscc and to the rest of the gout , so there is a major epidemic .
if a single initial infection is chosen randomly , the distribution of outbreak sizes is equal to the distribution of small out - component sizes and the probability of a major epidemic is equal to the proportion of the network contained in the gin .
no matter where a major epidemic starts , its attack rate is equal to the proportion of the network contained in the gout .
  in the limit of large n , almost all realizations of the epn have the same degree distribution and the same distribution of in- , out- , and strongly connected component sizes , so a great deal of information is contained in a single realization of the epn for an s(e)ir model with a large population . for many models , the asymptotic distribution of small component sizes and the proportion of the network contained in each of the giant components  and hence the outbreak size distribution and the asymptotic probability and attack rate of a major epidemic  can be calculated using probability generating functions [ 810 ] . in this section ,
we show how the analysis of mass - action and network - based seir models using epns and probability generating functions is a generalization of earler methods .
we also show that epns are a useful theoretical tool and a powerful numerical tool for simulating s(e)ir epidemics in closed populations .
to demonstrate the accuracy of the epn framework , we compare theoretical predictions of the probability and attack rate of a major epidemic based on epns with observations from a series of simulations of mass - action and network - based models .
these simulations were implemented in python ( http://www.python.org/ ) using the scipy ( http://www.scipy.org/ )   and networkx ( http://networkx.lanl.gov/ )   packages .
the code is available as online supplementary material ( see supplementary material available online at doi:10.1155/2011/543520 ) .     in mass - action seir models like example 1
, infectious contact is possible between any two individuals , but the probability of infectious contact is inversely proportional to the population size .
( mathematically , the cumulative hazard of infectious contact is inversely proportional to the population size , but the cumulative hazard and the probability are approximately equal for very small probabilities . )
there is a long tradition of approximating the initial spread of infection using a branching process [ 1 , 1315 ] . in a branching process
, one or more initial nodes have offspring , where the number of offspring is a random sample from a given discrete distribution .
the total size of the branching process is the total number of individuals produced . when the mean number of offspring is greater than one , there is a positive probability that the branching process 
explodes ,  continuing forever and producing an infinite population . the total size distribution and the explosion probability can be calculated using probability generating functions . for mass - action models with independent infectiousness and susceptibility ,
the outbreak size distribution and the probability and attack rate of a major epidemic can be predicted using branching process approximations that become exact in the limit of large n . in the  forward  branching process , the offspring of each infection are the people he or she infects . in the 
backward  branching process , the offspring of each infection are the people who would have infected the parent had they been infected .
asymptotically , the outbreak size distribution is equal to the distribution of finite total sizes in the forward branching process , and the probability of an epidemic is equal to the probability that the forward branching process explodes .
the attack rate of a major epidemic is asymptotically equal to the probability that the backward branching process explodes . for these models ,
the out - component size distribution in the epn is identical to the total size   distribution of the forward branching process and the in - component size distribution of the epn is identical to the total size distribution of the backward branching process .
thus , the epn predicts the same outbreak size distribution and probability and attack rate of a major epidemic as the branching process approximations .
when infectiousness and susceptibility are not independent , the branching process approximations break down but the epn predictions remain correct . in this case , the probability generating functions in the epn approach are similar to those of a branching process , but they allow the number of offspring in the first generation ( i.e. , the initial infections ) to have a different distribution than the number of offspring in all subsequent generations . 
 figure 2 shows the observed and predicted probabilities and attack rates of a major epidemic in a series of mass - action sir models . each model had a population of 50,000 .
the observed probability of a major epidemic was the number of epidemics with a final size 250 out of 1,000 runs .
the observed final size of an epidemic was based on a single major epidemic , which was defined as an epidemic with a final size 250 .
there are three series of models : one with a fixed infectious period , one with an exponentially distributed infectious period , and one where the infectious period has a weibull distribution with shape parameter 0.5 . at each r0
, these distributions produce different probabilities of a major epidemic but the same attack rate .
the predicted probability and attack rate of a major epidemic are equal only when the infectious period is fixed . in a network - based seir model ,
infection is transmitted across the edges of a contact network . for network - based models ,
analysis via epns can be seen as a generalization of analysis via bond percolation models , first used to calculate the attack rate of a major epidemic   and later extended to the size distribution of minor epidemics and the probability of a major epidemic . in this approach , each edge in the contact network is erased with probability 1  t , where t is the marginal probability of infectious contact from an infected node to a neighbor .
when infectiousness and susceptibility are constant , the distribution of minor epidemic sizes is equal to the distribution of small component sizes , the epidemic threshold corresponds to the emergence of a giant component in the posterasure contact network , and the probability and attack rate of a major epidemic are both equal to the proportion of the network contained in the giant component . to illustrate this approach and its limitations
, we generalize the network - based kermack - mckendrick model from example 2 by allowing it to have an arbitrary infectious period distribution . in the corresponding bond percolation model , each edge in the contact network would be retained independently with probability 
 ( 3)t=01edfi( ) , 
							 where 1  exp  (  ) is the conditional probability of infectious contact given an infectious period of  and df( ) represents integration or summation over the infectious period distribution . when the infectious period is fixed
, the bond percolation model and the epn predict exactly the same distribution of outbreak sizes and the same probability and attack rate of a major epidemic ( which are equal in this case ) .
however , the bond percolation model does not predict the correct outbreak size distribution or probability of an epidemic if the infectious period is variable . 

example 3consider a network - based kermack - mckendrick model that has an exponential infectious period with mean one .
the probability that a single initial infection with 2 neighbors fails to transmit infection is 
									 ( 4)0e(2+1)  d=12+1 , 
								 which is the probability that the corresponding node has an out - component of size one in the epn . in the bond percolation model ,
( 3 ) gives us t = (+1 ) , so the probability that both edges incident to the initial infection get erased is 
									 ( 5)(1t)2=12 + 2+1<12+1 . 
								
thus , the bond percolation model underestimates the probability of an outbreak of size one .
the bond percolation model treats infection of the two neighbors as independent events , but they are positively correlated because both are affected by the infectious period of the initial node .
this limitation of the bond percolation model also affects contact networks that include directed edges , as considered in . to see this ,
replace the undirected edges in this example with any combination of outgoing and undirected edges . 
 
consider a network - based kermack - mckendrick model that has an exponential infectious period with mean one .
the probability that a single initial infection with 2 neighbors fails to transmit infection is 
									 ( 4)0e(2+1)  d=12+1 , 
								 which is the probability that the corresponding node has an out - component of size one in the epn . in the bond percolation model ,
( 3 ) gives us t = (+1 ) , so the probability that both edges incident to the initial infection get erased is 
									 ( 5)(1t)2=12 + 2+1<12+1 . 
								
thus , the bond percolation model underestimates the probability of an outbreak of size one .
the bond percolation model treats infection of the two neighbors as independent events , but they are positively correlated because both are affected by the infectious period of the initial node .
this limitation of the bond percolation model also affects contact networks that include directed edges , as considered in . to see this ,
replace the undirected edges in this example with any combination of outgoing and undirected edges .     in this class of models ,
the bond percolation model overestimates the probability of a major epidemic whenever there is a variable infectious period [ 8 , 10 ] .
to demonstrate this , we conducted a series of simulations on erds - rnyi networks with mean degree 5 .
the observed probability of a major epidemic was the number of epidemics with a final size 250 out of 1,000 runs .
the observed final size of an epidemic was based on a single major epidemic , defined as an epidemic with a final size 250 .
one series of simulations had a fixed infectious period of one , the second series had an exponentially distributed infectious period with mean one , and the third series had infectious persons transmit to all or none of their contacts .
the first and last models define the upper and lower bounds , respectively , of the epidemic probability for models with independent infectiousness and susceptibility . for a given r0 ,
all three models have the same t , so they should have identical major epidemic probabilities and attack rates according to the bond percolation framework .
in addition , the bond percolation framework implies that the probability and attack rate are always equal .
however , figure 3 clearly shows that the three models produce different major epidemic probabilities but equal attack rates .
the probability and attack rate are equal only in models with a fixed infectious period . in models with variable infectiousness , the probabilities are lower than the attack rates .
the epn predictions of probability and attack rate are accurate for all of these models . in these examples and the models considered in ,
when models have variable infectiousness and susceptibility , the bond percolation approach can predict the wrong attack rate for a major epidemic in addition to the wrong outbreak size distribution and probability of a major epidemic .
the epn is very similar to the  locally dependent random graph    for sir epidemics on lattices , which was used to show that sir models on lattices reduce to bond percolation processes if and only if the infectious period is constant .
in these and all other time - homogeneous s(e)ir models on networks , an analysis based on epns predicts the correct minor epidemic size distribution and the correct probability and attack rate of a major epidemic .  
most stochastic simulations of epidemic spread provide dynamic information about the spread of an epidemic .
in contrast , a realization of an epn is a static object , so many more mathematical tools are available to analyze it .
to calculate the probability of a major epidemic , it suffices to calculate the proportion of nodes in the gin . to calculate the attack rate
, it suffices to calculate the proportion in the gout . in the infinite population limit , this is equivalent to calculating the probability that the epn has an infinite path directed into or out of a randomly chosen node .
this justifies the branching process approximation for mass - action models , and a similar approach is appropriate in networks without short cycles .
these lead to analyses based on probability generating functions for the bond percolation model   and for epns [ 810 ] .
more generally , however , we can not use probability generating functions when the branches of the initial spread of infection intersect with asymptotically nonzero probability .
thus , we need different approaches to calculate the size and probability of an epidemic on a network with short cycles .
this can be done numerically with epns as described below , but we can also use epns to make rigorous statements about the disease spread .
for example , if we want to analyze the impact a single individual has on an epidemic , a standard stochastic model would require many simulations . with an epn approach ,
we are able to generate a realization of the epn , including edges between all other nodes , and then consider the impact of each possible edge involving the targeted individual .
this approach was used in   to investigate the impact of heterogeneity in the population .
this paper compared two different random rules ( with identical average ) for assigning each node 's infectiousness and susceptibility ( independently of other nodes and each other ) , showing that the rule which provides a more homogeneous population results in larger and more probable epidemics .
the approach was to choose a node u and consider any epn realization created without edges involving u. then the infectiousness and susceptibility of u would be assigned and the edges involving u chosen .
it was then proven that regardless of how the remainder of the epn was assigned , the size of in- and out - components would be maximized by the more homogeneous assignment rule .  
traditionally , the probability and attack rate of a major epidemic in an s(e)ir model are estimated by running the model repeatedly . for each run , we record whether a major epidemic occurred and , if so , we record the attack rate . whether a major epidemic occurs
is a binomial process where each run of the model is like a single coin flip .
thus , repeated simulation produces an accurate estimate of the attack rate much faster than the probability . in a model with a sufficiently large population
, the probability and attack rate of a major epidemic can be calculated with equal precision from a single realization of the epn .
tarjan 's algorithm   can be used to identify the gscc , gin , and gout in a time that is linear in the population size n. the sizes of the giant components vary by an amount of order ln  n , so the proportional error is small for large n. in figure 4 , we compare the result from a single epn and the results from 50 simulations with the exact calculations in the infinite population limit .
we consider three different models for the spread of a disease : exponentially distributed infectious periods , all - or - nothing infectiousness , and all - or - nothing susceptibility . in all - or - nothing infectiousness
, a proportion of the population infects every susceptible neighbor , while the remainder infect none . in all - or - nothing susceptibility , a proportion become infected if any neighbor is ever infected , while the remainder are never infected . in the simulations ,
the calculations of a single epn took approximately 1/3 the time of simulating 50 epidemics .
however , the probability of an epidemic is poorly predicted by the simulations because the convergence of a binomial process is relatively slow . if the population had short cycles , the exact calculations used to predict the probability and attack rate would fail . in that case
, a single epn would provide an accurate numerical prediction   of the probability of a major epidemic much faster than repeated simulations .
although our attention has focused on static quantities such as the probability or size of major epidemics , epns can also be used to calculate the dynamic spread of an epidemic .
returning to the generation algorithm described in section 2.2 , we can assign a latent period i to each node i. for each ordered pair with ij * <  , we can assign a time of i + ij * to the edge from i to j in the epn ( similarly , if ji * <  , assign a time of j + ji * to the opposite direction ) . the time associated with each edge
if an epidemic begins with a single initial infection at time zero , the infection time of node i is simply the total length of the shortest path from the initial infection to node i. if no such path exists , i is never infected .
these paths and their lengths can be found in time proportional to nln  n using dijkstra 's algorithm . thus , epns provide an extremely efficient way to get complete runs of an epidemic model , including time dynamics as well as the final outcome . by choosing a different initial infection each time
, many nearly independent runs of the seir model can be obtained from a single epn .
   in this section , we show how epns provide a useful guide to the design of efficient vaccination strategies in mass - action and network - based seir models . for simplicity
, we assume that we have a perfect vaccine that makes its recipients immune to infection .
the effect of the vaccine can be represented by erasing all incoming , outgoing , and undirected edges incident to each vaccinated node in the epn . since
a major epidemic is possible if and only if there is a gscc , we hypothesized that vaccine should be targeted to nodes with a high probability of inclusion in the gscc and a high number of connections to nodes in gscc .    to test the effect of this targeting strategy in a mass - action model , we created a mass - action model with three subpopulations , a , b , and c , of equal size .
subpopulation a had high infectiousness but low susceptibility , subpopulation b had average infectiousness and susceptibility , and subpopulation c had low infectiousness but high susceptibility . within subpopulation a , each node had a relative susceptibility that was exponentially distributed with mean one .
within subpopulation c , each node had a relative infectiousness that was exponentially distributed with mean one .
subpopulation a had the highest probability of being in the gin , subpopulation b had the highest probability of being in the gscc , and subpopulation c had the highest probability of being in the gout . with no vaccination , r0 = 2.14 and
the probability and attack rate of a major epidemic are both equal to  .72 .
calculations of r0 and the probability and attack rate of a major epidemic at different vaccination fractions in each subpopulation were done using probability generating functions [ 9 , 10 ] . 

vaccinating subpopulation a was optimal for reducing the probability of an epidemic because its members were the most infectious and the most likely to be in the gin .
vaccinating subpopulation c was optimal for reducing the attack rate of an epidemic because its members were the most susceptible and the most likely to be in the gout .
vaccinating subpopulation b was nearly optimal for reducing both the probability and attack rate of a major epidemic because its members had the right combination of infectiousness and susceptibility to make them the most likely to be in the gscc .
vaccinating any of the three subpopulations produced exactly the same effect on r0 , but vaccinating subpopulation b was most effective in reducing the overall risk of infection given a single initial infection .
vaccinating subpopulation a was optimal for reducing the probability of an epidemic because its members were the most infectious and the most likely to be in the gin .
vaccinating subpopulation c was optimal for reducing the attack rate of an epidemic because its members were the most susceptible and the most likely to be in the gout .
vaccinating subpopulation b was nearly optimal for reducing both the probability and attack rate of a major epidemic because its members had the right combination of infectiousness and susceptibility to make them the most likely to be in the gscc .
vaccinating any of the three subpopulations produced exactly the same effect on r0 , but vaccinating subpopulation b was most effective in reducing the overall risk of infection given a single initial infection .
the standard approach to vaccination targeting in network - based models is to target nodes with high degree in the contact network [ 24 , 25 ] .
however , this approach ignores all information about the disease other than the contact network itself .
an approach based on the epn uses information about both the contact network and the epidemiological characteristics of the disease . in a series of epidemic models , we compared two vaccine - targeting strategies , each represented by a ranked list of nodes to vaccinate .
for the first strategy , we ranked the nodes by degree in the contact network .
for the second , we generated a single realization of the epn and ranked nodes in the gscc by the number of edges connecting them to other nodes in the gscc , ignoring direction .
nodes outside the gscc were placed in random order at the bottom of the list .
for a vaccination fraction of v , the first nv nodes on each list would be vaccinated , where n = 100,000 was the population size . to compare the two vaccination strategies
, we estimated the probability and attack rate of a major epidemic as a function of the vaccination fraction v. for each v , we generated ten independent realizations of the epn and estimated the probability and attack rate of an epidemic by calculating the mean proportion of the population in the gin and the gout , respectively .
we compared strategies on two different types of contact networks : an   erds - rnyi   network with mean degree five and a scale - free network with  = 2 and an exponential cutoff around 50 . if pk denotes the probability that node has degree k , then pk  5/k ! in the erds - rnyi network and pk  kexp  k/50 in the scale - free network .
when all nodes have the same infectiousness and susceptibility , we expect to see no difference between the two strategies because degree in the contact network is the only determinant of a node 's probability of being in the gscc . to represent the effects of variation in susceptibility and infectiousness , we allowed the transmission probability from node i to node j to be  
 ( 6)pij=1e100inf  isusj , 
							 where 0 < inf  i < 1 represents the infectiousness of i and 0 < susj < 1 represents the susceptibility of node j. we allowed infi and susi to have different beta distributions .
a beta(2 , 2 ) distribution has a single peak at 0.5 , so there is little variation in infectiousness and susceptibility .
a beta(.25 ,  .25 ) distribution has peaks near zero and one , so most nodes have either very high or very low infectiousness ( or susceptibility ) . in our primary models ,
to look at the effects of positive and negative correlations of infectiousness and susceptibility , we also compared the strategies in positively correlated models , where inf  i = susi , and negatively correlated models , where inf  i = 1  susi . 

resultsthe results of the comparison for a model with independent infectiousness and susceptibility are shown in figure 7 . as expected
, we see almost no difference in the effectiveness of the two strategies when inf   and sus have beta(2 , 2 ) distributions .
when inf  i and susi have beta(.25 ,  .25 ) distributions , targeting vaccination to the gscc is much more effective in reducing both the probability and attack rate of a major epidemic than targeting nodes with high degree in the contact network .  
figure 8 shows similar results for models with positive and negative correlations between infectiousness and susceptibility . targeting vaccination to the gscc of
the epn takes advantage of information about the epidemiology of the disease that targeting to nodes with high degree in the contact network does not , and this makes a substantial difference in the effectiveness of the vaccination strategy . 
 
the results of the comparison for a model with independent infectiousness and susceptibility are shown in figure 7 .
as expected , we see almost no difference in the effectiveness of the two strategies when inf   and sus have beta(2 , 2 ) distributions .
when inf  i and susi have beta(.25 ,  .25 ) distributions , targeting vaccination to the gscc is much more effective in reducing both the probability and attack rate of a major epidemic than targeting nodes with high degree in the contact network .  
figure 8 shows similar results for models with positive and negative correlations between infectiousness and susceptibility .
targeting vaccination to the gscc of the epn takes advantage of information about the epidemiology of the disease that targeting to nodes with high degree in the contact network does not , and this makes a substantial difference in the effectiveness of the vaccination strategy .
  epns provide a very useful intuitive point of view when thinking about the behavior of stochastic seir epidemic models .
bow - tie  diagram in figure 1 provides a simple visual explanation for the following basic facts .  
the probability and attack rate of an epidemic must be both zero or both positive , so there is a single epidemic threshold .   in general
, vaccinating the highly infectious ( i.e. , those likely to be in the gin ) will reduce the probability of a major epidemic , and vaccinating the highly susceptible ( i.e. , those likely to be in the gout ) will reduce its attack rate . vaccinating those likely to be in the gscc will reduce both .  
				
the ideal vaccination targets are not necessarily the most infectious or the most susceptible individuals .
instead , they are those individuals with the right combination of infectiousness and susceptibility to be effective receivers and transmitters of infection .
it is precisely these nodes that hold together the gscc of the epn . in section 4
, we showed that targeting vaccine to nodes likely to be in the gscc and highly connected within the gscc was an efficient intervention strategy for both mass - action and network - based models .
the correspondence between the epidemic threshold in an seir model and the emergence of the gscc in its epn makes elimination of the gscc a necessary and sufficient condition for the elimination of disease transmission in a population .
the primary limitation of epns is that they are defined only for time - homogeneous seir models .
they can not accurately represent the final outcomes of complex , time - dependent seir models and interventions .
for example , they can not accurately represent seasonality , the effects of changing behavior or demographics , or the effects of an intervention that is implemented only when a certain prevalence of infection is reached .
the vaccination strategies in section 4 were all prevaccination strategies , where the population was vaccinated prior to the beginning of disease spread .
if vaccination began after an epidemic had already started , as was the case in the recent influenza a(h1n1 ) pandemic , its effects could not be represented accurately using an epn .
nonetheless , epns generalize earlier approaches to the analysis of mass - action and network - based models , providing a simple unified framework for the analysis and implementation of time - homogeneous s(e)ir models .
they are powerful theoretical and practical tools , and they represent an important application of networks in infectious disease epidemiology .
 epidemic percolation networks ( epns ) are directed random networks 
 that can be used to analyze stochastic  susceptible - infectious - removed  
 
 ( sir ) and  susceptible - exposed - infectious - removed  ( seir ) epidemic 
 models , unifying and generalizing previous uses of networks and branching processes to analyze mass - action and network - based s(e)ir models . 
 
 this paper explains the fundamental concepts underlying the definition 
 and use of epns , using them to build intuition about the final outcomes 
 of epidemics . 
 we then show how epns provide a novel and useful perspective on the design of vaccination strategies . 
1. Introduction
2. Epidemic Percolation Networks
3. Analysis of Stochastic SEIR Models
4. Vaccination Strategies
5. Discussion