### Core team:

# Laurent Hébert-Dufresne

### University of Vermont

### Computer Science, Assistant Professor

Laurent studies the interaction of structure and dynamics. His research involves network theory, statistical physics and nonlinear dynamics along with their applications in epidemiology, ecology, biology, and sociology. Recent projects include comparing complex networks of different nature, the coevolution of human behavior and infectious diseases, understanding the role of forest shape in determining stability of tropical forests, as well as the impact of echo chambers in political discussions.

#### Most recent papers:

Percolation and the effective structure of complex networks.

Antoine Allard, Laurent Hébert-Dufresne. Preprint, 2018.[pdf] [arXiv]

**Abstract:**

Analytical approaches to model the structure of complex networks can be distinguished into two groups according to whether they consider an intensive (e.g., fixed degree sequence and random otherwise) or an extensive (e.g., adjacency matrix) description of the network structure. While extensive approaches---such as the state-of-the-art Message Passing Approach---typically yield more accurate predictions, intensive approaches provide crucial insights on the role played by any given structural property in the outcome of dynamical processes. Here we introduce an intensive description that yields almost identical predictions to the ones obtained with MPA for bond percolation. Our approach distinguishes nodes according to two simple statistics: their degree and their position in the core-periphery organization of the network. Our near-exact predictions highlight how accurately capturing the long-range correlations in network structures allows to easily and effectively compress real complex network data.

Network archaeology: phase transition in the recoverability of network history.

Jean-Gabriel Young, Laurent Hébert-Dufresne, Edward Laurence, Charles Murphy, Guillaume St-Onge, Patrick Desrosiers. Preprint, 2018.[pdf] [arXiv]

**Abstract:**

Network growth processes can be understood as generative models of the structure and history of complex networks. This point of view naturally leads to the problem of network archaeology: Reconstructing all the past states of a network from its structure---a difficult permutation inference problem. In this paper, we introduce a Bayesian formulation of network archaeology, with a generalization of preferential attachment as our generative mechanism. We develop a sequential importance sampling algorithm to evaluate the posterior averages of this model, as well as an efficient heuristic that uncovers the history of a network in linear time. We use these methods to identify and characterize a phase transition in the quality of the reconstructed history, when they are applied to artificial networks generated by the model itself. Despite the existence of a no-recovery phase, we find that non-trivial inference is possible in a large portion of the parameter space as well as on empirical data.

Edge fires drive the shape and stability of tropical forests.

Laurent Hébert-Dufresne, Adam Pellegrini, Uttam Bhat, Stephen Pacala, Andrew Berdahl. Ecology Letters, , , 2018.[pdf] [journal page] [arXiv]

**Abstract:**

In tropical regions, fires propagate readily in grasslands but typically consume only edges of forest patches. Thus forest patches grow due to tree propagation and shrink by fires in surrounding grasslands. The interplay between these competing edge effects is unknown, but critical in determining the shape and stability of individual forest patches, as well the landscape-level spatial distribution and stability of forests. We analyze high-resolution remote-sensing data from protected areas of the Brazilian Cerrado and find that forest shapes obey a robust perimeter-area scaling relation across climatic zones. We explain this scaling by introducing a heterogeneous fire propagation model of tropical forest-grassland ecotones. Deviations from this perimeter-area relation determine the stability of individual forest patches. At a larger scale, our model predicts that the relative rates of tree growth due to propagative expansion and long-distance seed dispersal determine whether collapse of regional-scale tree cover is continuous or discontinuous as fire frequency changes.

The risk of sustained sexual transmission of Zika is underestimated.

Antoine Allard, Benjamin Althouse, Laurent Hébert-Dufresne, Samuel V. Scarpino. PLoS Pathogens, , 13, 2017.[pdf] [journal page]

**Abstract:**

Pathogens often follow more than one transmission route during outbreaks—from needle sharing plus sexual transmission of HIV to small droplet aerosol plus fomite transmission of influenza. Thus, controlling an infectious disease outbreak often requires characterizing the risk associated with multiple mechanisms of transmission. For example, during the Ebola virus outbreak in West Africa, weighing the relative importance of funeral versus health care worker transmission was essential to stopping disease spread. As a result, strategic policy decisions regarding interventions must rely on accurately characterizing risks associated with multiple transmission routes. The ongoing Zika virus (ZIKV) outbreak challenges our conventional methodologies for translating case-counts into route-specific transmission risk. Critically, most approaches will fail to accurately estimate the risk of sustained sexual transmission of a pathogen that is primarily vectored by a mosquito—such as the risk of sustained sexual transmission of ZIKV. By computationally investigating a novel mathematical approach for multi-route pathogens, our results suggest that previous epidemic threshold estimates could under-estimate the risk of sustained sexual transmission by at least an order of magnitude. This result, coupled with emerging clinical, epidemiological, and experimental evidence for an increased risk of sexual transmission, would strongly support recent calls to classify ZIKV as a sexually transmitted infection.

Asymmetric percolation drives a double transition in sexual contact networks.

Antoine Allard, Benjamin Althouse, Samuel V. Scarpino, Laurent Hébert-Dufresne. Proceedings of the National Academy of Sciences of the United States of America, , , 2017.[pdf] [journal page] [arXiv]

**Abstract:**

Zika virus (ZIKV) continues to be a threat to countries with conditions suitable for transmission, namely adequate temperatures and the presence of competent mosquito vectors. Estimates of risk in other countries based on the sexual transmission of ZIKV may be underestimated because of inadequate surveillance. Here, we formulate random network models of sexual transmission of ZIKV with asymmetric transmission (men being infectious for longer than women) and show that, contrary to previous work, there exists two epidemic thresholds and that certain men who have sex with men communities could sustain transmission on their own. Our results also shed light on a class of processes on random networks by providing a complete analysis of dynamics with multiple critical points.

Strategic tradeoffs in competitor dynamics on adaptive networks.

Laurent Hébert-Dufresne, Antoine Allard, Pierre-André Noël, Jean-Gabriel Young, Eric Libby. Scientific Reports, , 7, 2017.[pdf] [journal page] [arXiv]

**Abstract:**

Recent empirical work highlights the heterogeneity of social competitions such as political campaigns: proponents of some ideologies seek debate and conversation, others create echo chambers. While symmetric and static network structure is typically used as a substrate to study such competitor dynamics, network structure can instead be interpreted as a signature of the competitor strategies, yielding competition dynamics on adaptive networks. Here we demonstrate that tradeoffs between aggressiveness and defensiveness (i.e., targeting adversaries vs. targeting like-minded individuals) creates paradoxical behaviour such as non-transitive dynamics. And while there is an optimal strategy in a two competitor system, three competitor systems have no such solution; the introduction of extreme strategies can easily affect the outcome of a competition, even if the extreme strategies have no chance of winning. Not only are these results reminiscent of classic paradoxical results from evolutionary game theory, but the structure of social networks created by our model can be mapped to particular forms of payoff matrices. Consequently, social structure can act as a measurable metric for social games which in turn allows us to provide a game theoretical perspective on online political debates.

Finite size analysis of the detectability limit of the stochastic block model.

Jean-Gabriel Young, Patrick Desrosiers, Laurent Hébert-Dufresne, Edward Laurence, Louis J. Dubé. Physical Review E, , 95, 2017.[pdf] [journal page] [arXiv]

**Abstract:**

It has been shown in recent years that the stochastic block model is sometimes undetectable in the sparse limit, i.e., that no algorithm can identify a partition correlated with the partition used to generate an instance, if the instance is sparse enough and infinitely large. In this contribution, we treat the finite case explicitly, using arguments drawn from information theory and statistics. We give a necessary condition for finite-size detectability in the general SBM. We then distinguish the concept of average detectability from the concept of instance-by-instance detectability and give explicit formulas for both definitions. Using these formulas, we prove that there exist large equivalence classes of parameters, where widely different network ensembles are equally detectable with respect to our definitions of detectability. In an extensive case study, we investigate the finite-size detectability of a simplified variant of the SBM, which encompasses a number of important models as special cases. These models include the symmetric SBM, the planted coloring model, and more exotic SBMs not previously studied. We conclude with three appendices, where we study the interplay of noise and detectability, establish a connection between our information-theoretic approach and random matrix theory, and provide proofs of some of the more technical results.

Dynamics of beneficial epidemics.

Andrew Berdahl, Christa Brelsford, Caterina De Bacco, Marion Dumas, Laurent Hébert-Dufresne, et al.. Preprint, 2017.[pdf] [arXiv]

**Abstract:**

Pathogens can spread epidemically through populations. Beneficial contagions, such as viruses that enhance host survival or technological innovations that improve quality of life, also have the potential to spread epidemically. How do the dynamics of beneficial biological and social epidemics differ from those of detrimental epidemics? We investigate this question using three theoretical approaches. First, in the context of population genetics, we show that a horizontally-transmissible element that increases fitness, such as viral DNA, spreads superexponentially through a population, more quickly than a beneficial mutation. Second, in the context of behavioral epidemiology, we show that infections that cause increased connectivity lead to superexponential fixation in the population. Third, in the context of dynamic social networks, we find that preferences for increased global infection accelerate spread and produce superexponential fixation, but preferences for local assortativity halt epidemics by disconnecting the infected from the susceptible. We conclude that the dynamics of beneficial biological and social epidemics are characterized by the rapid spread of beneficial elements, which is facilitated in biological systems by horizontal transmission and in social systems by active spreading behavior of infected individuals.

Exotic phase transitions of k-cores in clustered networks.

Uttam Bhat, Munik Shrestha, Laurent Hébert-Dufresne. Physical Review E, , 95, 2017.[pdf] [journal page] [arXiv]

**Abstract:**

The giant k -core—maximal connected subgraph of a network where each node has at least k neighbors—is important in the study of phase transitions and in applications of network theory. Unlike Erdős-Rényi graphs and other random networks where k -cores emerge discontinuously for k ≥ 3 , we show that transitive linking (or triadic closure) leads to 3-cores emerging through single or double phase transitions of both discontinuous and continuous nature. We also develop a k -core calculation that includes clustering and provides insights into how high-level connectivity emerges.

Growing networks of overlapping communities with internal structur.

Jean-Gabriel Young, Laurent Hébert-Dufresne, Antoine Allard, Louis J. Dubé. Physical Review E, , 94, 2016.[pdf] [journal page] [arXiv]

**Abstract:**

We introduce an intuitive model that describes both the emergence of community structure and the evolution of the internal structure of communities in growing social networks. The model comprises two complementary mechanisms: One mechanism accounts for the evolution of the internal link structure of a single community, and the second mechanism coordinates the growth of multiple overlapping communities. The first mechanism is based on the assumption that each node establishes links with its neighbors and introduces new nodes to the community at different rates. We demonstrate that this simple mechanism gives rise to an effective maximal degree within communities. This observation is related to the anthropological theory known as Dunbar's number, i.e., the empirical observation of a maximal number of ties which an average individual can sustain within its social groups. The second mechanism is based on a recently proposed generalization of preferential attachment to community structure, appropriately called structural preferential attachment (SPA). The combination of these two mechanisms into a single model (SPA+) allows us to reproduce a number of the global statistics of real networks: The distribution of community sizes, of node memberships and of degrees. The SPA+ model also predicts (a) three qualitative regimes for the degree distribution within overlapping communities and (b) strong correlations between the number of communities to which a node belongs and its number of connections within each community. We present empirical evidence that support our findings in real complex networks.

The effect of a prudent adaptive behaviour on disease transmission.

Samuel V. Scarpino, Antoine Allard, Laurent Hébert-Dufresne. Nature Physics, 1042-1046, 12, 2016.[pdf] [journal page] [arXiv]

**Abstract:**

The spread of disease can be slowed by certain aspects of real-world social networks, such as clustering and community structure, and of human behaviour, including social distancing and increased hygiene, many of which have already been studied. Here, we consider a model in which individuals with essential societal roles—be they teachers, first responders or health-care workers—fall ill, and are replaced with healthy individuals. We refer to this process as relational exchange, and incorporate it into a dynamic network model to demonstrate that replacing individuals can accelerate disease transmission. We find that the effects of this process are trivial in the context of a standard mass-action model, but dramatic when considering network structure, featuring accelerating spread, discontinuous transitions and hysteresis loops. This result highlights the inability of mass-action models to account for many behavioural processes. Using empirical data, we find that this mechanism parsimoniously explains observed patterns across 17 influenza outbreaks in the USA at a national level, 25 years of influenza data at the state level, and 19 years of dengue virus data from Puerto Rico. We anticipate that our findings will advance the emerging field of disease forecasting and better inform public health decision making during outbreaks.

Multi-scale structure and topological anomaly detection via a new network statistic: The onion decomposition.

Laurent Hébert-Dufresne, Joshua Grochow, Antoine Allard. Scientific Reports, , 6, 2016.[pdf] [journal page] [arXiv]

**Abstract:**

We introduce a network statistic that measures structural properties at the micro-, meso-, and macroscopic scales, while still being easy to compute and interpretable at a glance. Our statistic, the onion spectrum, is based on the onion decomposition, which refines the k-core decomposition, a standard network fingerprinting method. The onion spectrum is exactly as easy to compute as the k-cores: It is based on the stages at which each vertex gets removed from a graph in the standard algorithm for computing the k-cores. Yet, the onion spectrum reveals much more information about a network, and at multiple scales; for example, it can be used to quantify node heterogeneity, degree correlations, centrality, and tree- or lattice-likeness. Furthermore, unlike the k-core decomposition, the combined degree-onion spectrum immediately gives a clear local picture of the network around each node which allows the detection of interesting subgraphs whose topological structure differs from the global network organization. This local description can also be leveraged to easily generate samples from the ensemble of networks with a given joint degree-onion distribution. We demonstrate the utility of the onion spectrum for understanding both static and dynamic properties on several standard graph models and on many real-world networks.

Constrained growth of complex scale-independent systems.

Laurent Hébert-Dufresne, Antoine Allard, Jean-Gabriel Young, Louis J. Dubé. Physical Review E, , 93, 2016.[pdf] [journal page] [arXiv]

**Abstract:**

Scale independence is a ubiquitous feature of complex systems that implies a highly skewed distribution of resources with no characteristic scale. Research has long focused on why systems as varied as protein networks, evolution, and stock actions all feature scale independence. Assuming that they simply do, we focus here on describing how this behavior emerges, in contrast to more idealized models usually considered. We arrive at the conjecture that a minimal model to explain the growth toward scale independence involves only two coupled dynamical features: the first is the well-known preferential attachment principle, and the second is a general form of delayed temporal scaling. While the first is sufficient, the second is present in all studied data and appears to maximize the speed of convergence to true scale independence. The delay in this temporal scaling acts as a coupling between population growth and individual activity. Together, these two dynamical properties appear to pave a precise evolution path, such that even an instantaneous snapshot of a distribution is enough to reconstruct the past of the system and predict its future. We validate our approach and confirm its usefulness in diverse spheres of human activities, ranging from scientific and artistic productivity to sexual relations and online traffic.

A preferential attachment approach to community structure Growing networks of overlapping communities with internal structureand the structure of communities..

Jean-Gabriel Young, Laurent Hébert-Dufresne, Antoine Allard, Louis J. Dubé. Physical Review E, , 94, 2016.[pdf] [journal page]

**Abstract:**

We introduce an intuitive model that describes both the emergence of community structure and the evolution of the internal structure of communities in growing social networks. The model comprises two complementary mechanisms: One mechanism accounts for the evolution of the internal link structure of a single community, and the second mechanism coordinates the growth of multiple overlapping communities. The first mechanism is based on the assumption that each node establishes links with its neighbors and introduces new nodes to the community at different rates. We demonstrate that this simple mechanism gives rise to an effective maximal degree within communities. This observation is related to the anthropological theory known as Dunbar's number, i.e., the empirical observation of a maximal number of ties which an average individual can sustain within its social groups. The second mechanism is based on a recently proposed generalization of preferential attachment to community structure, appropriately called structural preferential attachment (SPA). The combination of these two mechanisms into a single model (SPA+) allows us to reproduce a number of the global statistics of real networks: The distribution of community sizes, of node memberships, and of degrees. The SPA+ model also predicts (a) three qualitative regimes for the degree distribution within overlapping communities and (b) strong correlations between the number of communities to which a node belongs and its number of connections within each community. We present empirical evidence that support our findings in real complex networks.

Complex networks as an emerging property of hierarchical preferential attachment.

Laurent Hébert-Dufresne, Edward Laurence, Antoine Allard, Jean-Gabriel Young, Louis J. Dubé. Physical Review E, , 92, 2015.[pdf] [journal page]

**Abstract:**

Real complex systems are not rigidly structured; no clear rules or blueprints exist for their construction. Yet, amidst their apparent randomness, complex structural properties universally emerge. We propose that an important class of complex systems can be modeled as an organization of many embedded levels (potentially infinite in number), all of them following the same universal growth principle known as preferential attachment. We give examples of such hierarchy in real systems, for instance, in the pyramid of production entities of the film industry. More importantly, we show how real complex networks can be interpreted as a projection of our model, from which their scale independence, their clustering, their hierarchy, their fractality, and their navigability naturally emerge. Our results suggest that complex networks, viewed as growing systems, can be quite simple, and that the apparent complexity of their structure is largely a reflection of their unobserved hierarchical nature.

General and exact approach to percolation on random graphs.

Antoine Allard, Laurent Hébert-Dufresne, Jean-Gabriel Young, Louis J. Dubé. Physical Review E, , 92, 2015.[pdf] [journal page]

**Abstract:**

We present a comprehensive and versatile theoretical framework to study site and bond percolation on clustered and correlated random graphs. Our contribution can be summarized in three main points. (i) We introduce a set of iterative equations that solve the exact distribution of the size and composition of components in finite-size quenched or random multitype graphs. (ii) We define a very general random graph ensemble that encompasses most of the models published to this day and also makes it possible to model structural properties not yet included in a theoretical framework. Site and bond percolation on this ensemble is solved exactly in the infinite-size limit using probability generating functions [i.e., the percolation threshold, the size, and the composition of the giant (extensive) and small components]. Several examples and applications are also provided. (iii) Our approach can be adapted to model interdependent graphs—whose most striking feature is the emergence of an extensive component via a discontinuous phase transition—in an equally general fashion. We show how a graph can successively undergo a continuous then a discontinuous phase transition, and preliminary results suggest that clustering increases the amplitude of the discontinuity at the transition.

Enhancing disease surveillance with novel data streams: challenges and opportunities.

Benjamin Althouse, Samuel V. Scarpino, Lauren Ancel Meyers, John Ayers, Laurent Hébert-Dufresne, et al.. EPJ Data Science, 17, 4, 2015.[pdf] [journal page]

**Abstract:**

Novel data streams (NDS), such as web search data or social media updates, hold promise for enhancing the capabilities of public health surveillance. In this paper, we outline a conceptual framework for integrating NDS into current public health surveillance. Our approach focuses on two key questions: What are the opportunities for using NDS and what are the minimal tests of validity and utility that must be applied when using NDS? Identifying these opportunities will necessitate the involvement of public health authorities and an appreciation of the diversity of objectives and scales across agencies at different levels (local, state, national, international). We present the case that clearly articulating surveillance objectives and systematically evaluating NDS and comparing the performance of NDS to existing surveillance data and alternative NDS data is critical and has not sufficiently been addressed in many applications of NDS currently in the literature.

A shadowing problem in the detection of overlapping communities: Lifting the resolution limit through a cascading procedure.

Jean-Gabriel Young, Antoine Allard, Laurent Hébert-Dufresne, Louis J. Dubé. PloS one, , 10, 2015.[pdf] [journal page]

**Abstract:**

Community detection is the process of assigning nodes and links in significant communities (eg clusters, function modules) and its development has led to a better understanding of complex networks. When applied to sizable networks, we argue that most detection algorithms correctly identify prominent communities, but fail to do so across multiple scales. As a result, a significant fraction of the network is left uncharted. We show that this problem stems from larger or denser communities overshadowing smaller or sparser ones, and that this effect accounts for most of the undetected communities and unassigned links. We propose a generic cascading approach to community detection that circumvents the problem. Using real and artificial network datasets with three widely used community detection algorithms, we show how a simple cascading procedure allows for the detection of the missing communities. This work highlights a new detection limit of community structure, and we hope that our approach can inspire better community detection algorithms.

Complex dynamics of synergistic coinfections on realistically clustered networks.

Laurent Hébert-Dufresne, Benjamin Althouse. Proceedings of the National Academy of Sciences, , 112, 2015.[pdf] [journal page]

**Abstract:**

We investigate the impact of contact structure clustering on the dynamics of multiple diseases interacting through coinfection of a single individual, two problems typically studied independently. We highlight how clustering, which is well known to hinder propagation of diseases, can actually speed up epidemic propagation in the context of synergistic coinfections if the strength of the coupling matches that of the clustering. We also show that such dynamics lead to a first-order transition in endemic states, where small changes in transmissibility of the diseases can lead to explosive outbreaks and regions where these explosive outbreaks can only happen on clustered networks. We develop a mean-field model of coinfection of two diseases following susceptible-infectious-susceptible dynamics, which is allowed to interact on a general class of modular networks. We also introduce a criterion based on tertiary infections that yields precise analytical estimates of when clustering will lead to faster propagation than nonclustered networks. Our results carry importance for epidemiology, mathematical modeling, and the propagation of interacting phenomena in general. We make a call for more detailed epidemiological data of interacting coinfections.

Spreading dynamics on complex networks: a general stochastic approach.

Pierre-André Noël, Antoine Allard, Laurent Hébert-Dufresne, Vincent Marceau, Louis J. Dubé. Preprint, 2014.[pdf] [journal page]

**Abstract:**

Dynamics on networks is considered from the perspective of Markov stochastic processes. We partially describe the state of the system through network motifs and infer any missing data using the available information. This versatile approach is especially well adapted for modelling spreading processes and/or population dynamics. In particular, the generality of our framework and the fact that its assumptions are explicitly stated suggests that it could be used as a common ground for comparing existing epidemics models too complex for direct comparison, such as agent-based computer simulations. We provide many examples for the special cases of susceptible-infectious-susceptible and susceptible-infectious-removed dynamics (eg, epidemics propagation) and we observe multiple situations where accurate results may be obtained at low computational cost. Our perspective reveals a subtle balance between the complex requirements of a realistic model and its basic assumptions.

The Social Zombie: Modelling undead outbreaks on social networks.

Laurent Hébert-Dufresne, Vincent Marceau, Pierre-André Noël, Antoine Allard, Louis J. Dubé. Mathematical Modelling of Zombies, 149-170, , 2014.[pdf] [journal page]

**Abstract:**

According to Mulder’s theory, the zombies will eventually fall on each other and make love. However, be it for love or evil, the cold, hard reality remains that the actions of the undead, just like those of the living, are structured by simple constraints of a social or spatiotemporal nature. In this chapter, we consider the underlying social network of the living and the horde behaviour of the undead. This model is then further improved by considering the adaptive nature of social interactions: people usually tend to avoid contact with zombies. Doing so captures the co-evolution of the human social network and of the zombie outbreak, which encourages humans to naturally barricade themselves in groups of survivors to better fight the undead menace. And then? Better stack goods, arm yourself and be patient, for the undead hordes are there to stay—hopefully dancing and making love.

Epidemic cycles driven by host behaviour.

Benjamin Althouse, Laurent Hébert-Dufresne. Journal of the Royal Society Interface, , 11, 2014.[pdf] [journal page]

**Abstract:**

Host immunity and demographics (the recruitment of susceptibles via birthrate) have been demonstrated to be a key determinant of the periodicity of measles, pertussis and dengue epidemics. However, not all epidemic cycles are from pathogens inducing sterilizing immunity or are driven by demographics. Many sexually transmitted infections are driven by sexual behaviour. We present a mathematical model of disease transmission where individuals can disconnect and reconnect depending on the infectious status of their contacts. We fit the model to historic syphilis (Treponema pallidum) and gonorrhea (Neisseria gonorrhoeae) incidence in the USA and explore potential intervention strategies against syphilis. We find that cycles in syphilis incidence can be driven solely by changing sexual behaviour in structured populations. Our model also explains the lack of similar cycles in gonorrhea incidence even if the two infections share the same propagation pathways. Our model similarly illustrates how sudden epidemic outbreaks can occur on time scales smaller than the characteristic demographic time scale of the population and that weaker infections can lead to more violent outbreaks. Behaviour also appears to be critical for control strategies as we found a bigger sensitivity to behavioural interventions than antibiotic treatment. Thus, behavioural interventions may play a larger role than previously thought, especially in the face of antibiotic resistance and low intervention efficacies.

Coexistence of phases and the observability of random graphs.

Antoine Allard, Laurent Hébert-Dufresne, Jean-Gabriel Young, Louis J. Dubé. Physical Review E, , 89, 2014.[pdf] [journal page]

**Abstract:**

In a recent Letter, Yang et al. [Phys. Rev. Lett. 109, 258701 (2012)] introduced the concept of observability transitions: the percolationlike emergence of a macroscopic observable component in graphs in which the state of a fraction of the nodes, and of their first neighbors, is monitored. We show how their concept of depth- L percolation—where the state of nodes up to a distance L of monitored nodes is known—can be mapped onto multitype random graphs, and use this mapping to exactly solve the observability problem for arbitrary L . We then demonstrate a nontrivial coexistence of an observable and of a nonobservable extensive component. This coexistence suggests that monitoring a macroscopic portion of a graph does not prevent a macroscopic event to occur unbeknown to the observer. We also show that real complex systems behave quite differently with regard to observability depending on whether they are geographically constrained or not.

On the growth and structure of social systems following preferential attachment.

Laurent Hébert-Dufresne. Université Laval, , , 2014.[pdf] [journal page]

**Abstract:**

Social systems are notoriously unfair. In this thesis, we focus on the distribution and structure of shared resources and activities. Through this lens, their extreme inequalities tend to roughly follow a universal pattern known as scale independence which manifests itself through the absence of a characteristic scale. In physical systems, scale-independent organizations are known to occur at critical points in phase transition theory. The position of this critical behaviour being very specific, it is reasonable to expect that the distribution of a social resource might also imply specific mechanisms. This analogy is the basis of this work, whose goal is to apply tools of statistical physics to varied social activities. As a first step, we show that a system whose resource distribution is growing towards scale independence is subject to two constraints. The first is the well-known preferential attachment principle, a mathematical principle roughly stating that the rich get richer. The second is a new general form of delayed temporal scaling between the population size and the amount of available resource. These constraints pave a precise evolution path, such that even an instantaneous snapshot of a distribution is enough to reconstruct its temporal evolution and predict its future states. We validate our approach on diverse spheres of human activities ranging from scientific and artistic productivity, to sexual relations and online traffic. We then broaden our framework to not only focus on resource distribution, but to also consider the resulting structure. We thus apply our framework to the theory of complex networks which describes the connectivity structure of social, technological or biological systems. In so doing, we propose that an important class of complex systems can be modelled as a construction of potentially infinitely many levels of organization all following the same universal growth principle known as preferential attachment. We show how real complex networks can be interpreted as a projection of our model, from which naturally emerge not only their scale independence, but also their clustering or modularity, their hierarchy, their fractality and their navigability. Our results suggest that social networks can be quite simple, and that the apparent complexity of their structure is largely a reflection of the complex hierarchical nature of our world.

Percolation on random networks with arbitrary k-core structure.

Laurent Hébert-Dufresne, Antoine Allard, Jean-Gabriel Young, Louis J. Dubé. Physical Review E, , 88, 2013.[pdf] [journal page] [arXiv]

**Abstract:**

The k-core decomposition of a network has thus far mainly served as a powerful tool for the empirical study of complex networks. We now propose its explicit integration in a theoretical model. We introduce a hard-core random network (HRN) model that generates maximally random networks with arbitrary degree distribution and arbitrary k-core structure. We then solve exactly the bond percolation problem on the HRN model and produce fast and precise analytical estimates for the corresponding real networks. Extensive comparison with real databases reveals that our approach performs better than existing models, while requiring less input information.

Escaping the poverty trap: modeling the interplay between economic growth and the ecology of infectious disease.

Georg Goerg, Oscar Patterson-Lomba, Laurent Hébert-Dufresne, Benjamin Althouse. Preprint, 2013.[pdf] [journal page] [arXiv]

**Abstract:**

The dynamics of economies and infectious disease are inexorably linked: economic well-being influences health (sanitation, nutrition, treatment capacity, etc.) and health influences economic well-being (labor productivity lost to sickness and disease). Often societies are locked into" poverty traps" of poor health and poor economy. Here, using a simplified coupled disease-economic model with endogenous capital growth we demonstrate the formation of poverty traps, as well as ways to escape them. We suggest two possible mechanisms of escape both motivated by empirical data: one, through an influx of capital (development aid), and another through changing the percentage of GDP spent on healthcare. We find that a large influx of capital is successful in escaping the poverty trap, but increasing health spending alone is not. Our results demonstrate that escape from a poverty trap may be possible, and carry important policy implications in the world-wide distribution of aid and within-country healthcare spending.

Global efficiency of local immunization on complex networks.

Laurent Hébert-Dufresne, Antoine Allard, Jean-Gabriel Young, Louis J. Dubé. Scientific Reports, , 3, 2013.[pdf] [journal page]

**Abstract:**

Epidemics occur in all shapes and forms: infections propagating in our sparse sexual networks, rumours and diseases spreading through our much denser social interactions, or viruses circulating on the Internet. With the advent of large databases and efficient analysis algorithms, these processes can be better predicted and controlled. In this study, we use different characteristics of network organization to identify the influential spreaders in 17 empirical networks of diverse nature using 2 epidemic models. We find that a judicious choice of local measures, based either on the network's connectivity at a microscopic scale or on its community structure at a mesoscopic scale, compares favorably to global measures, such as betweenness centrality, in terms of efficiency, practicality and robustness. We also develop an analytical framework that highlights a transition in the characteristic scale of different epidemic regimes. This allows to decide which local measure should govern immunization in a given scenario.

Optimizing treatment regimes to hinder antiviral resistance in influenza across time scales.

Oscar Patterson-Lomba, Benjamin Althouse, Georg Goerg, Laurent Hébert-Dufresne. PloS one, , 8, 2013.[pdf] [journal page]

**Abstract:**

The large-scale use of antivirals during influenza pandemics poses a significant selection pressure for drug-resistant pathogens to emerge and spread in a population. This requires treatment strategies to minimize total infections as well as the emergence of resistance. Here we propose a mathematical model in which individuals infected with wild-type influenza, if treated, can develop de novo resistance and further spread the resistant pathogen. Our main purpose is to explore the impact of two important factors influencing treatment effectiveness: i) the relative transmissibility of the drug-resistant strain to wild-type, and ii) the frequency of de novo resistance. For the endemic scenario, we find a condition between these two parameters that indicates whether treatment regimes will be most beneficial at intermediate or more extreme values (eg, the fraction of infected that are treated). Moreover, we present analytical expressions for effective treatment regimes and provide evidence of its applicability across a range of modeling scenarios: endemic behavior with deterministic homogeneous mixing, and single-epidemic behavior with deterministic homogeneous mixing and stochastic heterogeneous mixing. Therefore, our results provide insights for the control of drug-resistance in influenza across time scales.

Pathogen Mutation Modeled by Competition Between Site and Bond Percolation.

Laurent Hébert-Dufresne, Oscar Patterson-Lomba, Georg Goerg, Benjamin Althouse. Physical Review Letters, , 110, 2013.[pdf] [journal page]

**Abstract:**

While disease propagation is a main focus of network science, its coevolution with treatment has yet to be studied in this framework. We present a mean-field and stochastic analysis of an epidemic model with antiviral administration and resistance development. We show how this model maps to a coevolutive competition between site and bond percolation featuring hysteresis and both second-and first-order phase transitions. The latter, whose existence on networks is a long-standing question, imply that a microscopic change in infection rate can lead to macroscopic jumps in expected epidemic size.

The Timing and Targeting of Treatment in Influenza Pandemics Influences the Emergence of Resistance in Structured Populations.

Benjamin Althouse, Oscar Patterson-Lomba, Georg Goerg, Laurent Hébert-Dufresne. PLOS Computational Biology, , 9, 2013.[pdf] [journal page]

**Abstract:**

Antiviral resistance in influenza is rampant and has the possibility of causing major morbidity and mortality. Previous models have identified treatment regimes to minimize total infections and keep resistance low. However, the bulk of these studies have ignored stochasticity and heterogeneous contact structures. Here we develop a network model of influenza transmission with treatment and resistance, and present both standard mean-field approximations as well as simulated dynamics. We find differences in the final epidemic sizes for identical transmission parameters (bistability) leading to different optimal treatment timing depending on the number initially infected. We also find, contrary to previous results, that treatment targeted by number of contacts per individual (node degree) gives rise to more resistance at lower levels of treatment than non-targeted treatment. Finally we highlight important differences between the two methods of analysis (mean-field versus stochastic simulations), and show where traditional mean-field approximations fail. Our results have important implications not only for the timing and distribution of influenza chemotherapy, but also for mathematical epidemiological modeling in general. Antiviral resistance in influenza may carry large consequences for pandemic mitigation efforts, and models ignoring contact heterogeneity and stochasticity may provide misleading policy recommendations.

Unveiling hidden communities through cascading detection on network structures.

Jean-Gabriel Young, Antoine Allard, Laurent Hébert-Dufresne, Louis J. Dubé. Preprint, 2012.[pdf]

**Abstract:**

Community detection is the process of assigning nodes and links in significant communities (eg clusters, function modules) and its development has led to a better understanding of complex networks. When applied to sizable networks, we argue that most detection algorithms correctly identify prominent communities, but fail to do so across multiple scales. As a result, a significant fraction of the network is left uncharted. We show that this problem stems from larger or denser communities overshadowing smaller or sparser ones, and that this effect accounts for most of the undetected communities and unassigned links. We propose a generic cascading approach to community detection that circumvents the problem. Using real network datasets with two widely used community detection algorithms, we show how cascading detection allows for the detection of the missing communities and results in a significant drop of the fraction of unassigned links.

On the constrained growth of complex critical systems.

Laurent Hébert-Dufresne, Antoine Allard, Louis J. Dubé. Preprint, 2012.[pdf] [arXiv]

**Abstract:**

Critical, or scale independent, systems are so ubiquitous, that gaining theoretical insights on their nature and properties has many direct repercussions in social and natural sciences. In this report, we start from the simplest possible growth model for critical systems and deduce constraints in their growth: the well-known preferential attachment principle, and, mainly, a new law of temporal scaling. We then support our scaling law with a number of calculations and simulations of more complex theoretical models: critical percolation, self-organized criticality and fractal growth. Perhaps more importantly, the scaling law is also observed in a number of empirical systems of quite different nature: prose samples, artistic and scientific productivity, citation networks, and the topology of the Internet. We believe that these observations pave the way towards a general and analytical framework for predicting the growth of complex systems.

Bond percolation on a class of correlated and clustered random graphs.

Antoine Allard, Laurent Hébert-Dufresne, Pierre-André Noël, Vincent Marceau, Louis J. Dubé. Journal of Physics A: Mathematical and Theoretical, , , 2012.[pdf] [journal page] [arXiv]

**Abstract:**

We introduce a formalism for computing bond percolation properties of a class of correlated and clustered random graphs. This class of graphs is a generalization of the configuration model where nodes of different types are connected via different types of hyperedges, edges that can link more than two nodes. We argue that the multitype approach coupled with the use of clustered hyperedges can reproduce a wide spectrum of complex patterns, and thus enhances our capability to model real complex networks. As an illustration of this claim, we use our formalism to highlight unusual behaviours of the size and composition of the components (small and giant) in a synthetic, albeit realistic, social network.

Exact solution of bond percolation on small arbitrary graphs.

Antoine Allard, Laurent Hébert-Dufresne, Pierre-André Noël, Vincent Marceau, Louis J. Dubé. EPL (Europhysics Letters), , 98, 2012.[pdf] [journal page] [arXiv]

**Abstract:**

We introduce a set of iterative equations that exactly solves the size distribution of components on small arbitrary graphs after the random removal of edges. We also demonstrate how these equations can be used to predict the distribution of the node partitions (ie, the constrained distribution of the size of each component) in undirected graphs. Besides opening the way to the theoretical prediction of percolation on arbitrary graphs of large but finite size, we show how our results find application in graph theory, epidemiology, percolation and fragmentation theory.

Structural preferential attachment: Stochastic process for the growth of scale-free, modular and self-similar systems.

Laurent Hébert-Dufresne, Antoine Allard, Vincent Marceau, Pierre-André Noël, Louis J. Dubé. Physical Review E, , 85, 2012.[pdf] [journal page] [arXiv]

**Abstract:**

Many complex systems have been shown to share universal properties of organization, such as scale independence, modularity, and self-similarity. We borrow tools from statistical physics in order to study structural preferential attachment (SPA), a recently proposed growth principle for the emergence of the aforementioned properties. We study the corresponding stochastic process in terms of its time evolution, its asymptotic behavior, and the scaling properties of its statistical steady state. Moreover, approximations are introduced to facilitate the modeling of real systems, mainly complex networks, using SPA. Finally, we investigate a particular behavior observed in the stochastic process, the peloton dynamics, and show how it predicts some features of real growing systems using prose samples as an example.

Propagation on networks: an exact alternative perspective.

Pierre-André Noël, Antoine Allard, Laurent Hébert-Dufresne, Vincent Marceau, Louis J. Dubé. Physical Review E, , 85, 2012.[pdf] [journal page] [arXiv]

**Abstract:**

By generating the specifics of a network structure only when needed (on-the-fly), we derive a simple stochastic process that exactly models the time evolution of susceptible-infectious dynamics on finite-size networks. The small number of dynamical variables of this birth-death Markov process greatly simplifies analytical calculations. We show how a dual analytical description, treating large scale epidemics with a Gaussian approximation and small outbreaks with a branching process, provides an accurate approximation of the distribution even for rather small networks. The approach also offers important computational advantages and generalizes to a vast class of systems.

Structural preferential attachment: Network organization beyond the link.

Laurent Hébert-Dufresne, Antoine Allard, Vincent Marceau, Pierre-André Noël, Louis J. Dubé. Physical Review Letters, , 107, 2011.[pdf] [journal page] [arXiv]

**Abstract:**

We introduce a mechanism which models the emergence of the universal properties of complex networks, such as scale independence, modularity and self-similarity, and unifies them under a scale-free organization beyond the link. This brings a new perspective on network organization where communities, instead of links, are the fundamental building blocks of complex systems. We show how our simple model can reproduce social and information networks by predicting their community structure and more importantly, how their nodes or communities are interconnected, often in a self-similar manner.

Modeling the dynamical interaction between epidemics on overlay networks.

Vincent Marceau, Pierre-André Noël, Laurent Hébert-Dufresne, Antoine Allard, Louis J. Dubé. Physical Review E, , 84, 2011.[pdf] [journal page] [arXiv]

**Abstract:**

Epidemics seldom occur as isolated phenomena. Typically, two or more viral agents spread within the same host population and may interact dynamically with each other. We present a general model where two viral agents interact via an immunity mechanism as they propagate simultaneously on two networks connecting the same set of nodes. By exploiting a correspondence between the propagation dynamics and a dynamical process performing progressive network generation, we develop an analytical approach that accurately captures the dynamical interaction between epidemics on overlay networks. The formalism allows for overlay networks with arbitrary joint degree distribution and overlap. To illustrate the versatility of our approach, we consider a hypothetical delayed intervention scenario in which an immunizing agent is disseminated in a host population to hinder the propagation of an undesirable agent (e.g., the spread of preventive information in the context of an emerging infectious disease).

Propagation dynamics on networks featuring complex topologies.

Laurent Hébert-Dufresne, Pierre-André Noël, Vincent Marceau, Antoine Allard, Louis J. Dubé. Physical Review E, , 82, 2010.[pdf] [journal page] [arXiv]

**Abstract:**

Analytical description of propagation phenomena on random networks has flourished in recent years, yet more complex systems have mainly been studied through numerical means. In this paper, a mean-field description is used to coherently couple the dynamics of the network elements (such as nodes, vertices, individuals, etc.) on the one hand and their recurrent topological patterns (such as subgraphs, groups, etc.) on the other hand. In a susceptible-infectious-susceptible (SIS) model of epidemic spread on social networks with community structure, this approach yields a set of ordinary differential equations for the time evolution of the system, as well as analytical solutions for the epidemic threshold and equilibria. The results obtained are in good agreement with numerical simulations and reproduce the behavior of random networks in the appropriate limits which highlights the influence of topology on the processes. Finally, it is demonstrated that our model predicts higher epidemic thresholds for clustered structures than for equivalent random topologies in the case of networks with zero degree correlation.br>

Adaptive networks: Coevolution of disease and topology.

Vincent Marceau, Pierre-André Noël, Laurent Hébert-Dufresne, Antoine Allard, Louis J. Dubé. Physical Review E, , 82, 2010.[pdf] [journal page] [arXiv]

**Abstract:**

Adaptive networks have been recently introduced in the context of disease propagation on complex networks. They account for the mutual interaction between the network topology and the states of the nodes. Until now, existing models have been analyzed using low complexity analytical formalisms, revealing nevertheless some novel dynamical features. However, current methods have failed to reproduce with accuracy the simultaneous time evolution of the disease and the underlying network topology. In the framework of the adaptive susceptible-infectious-susceptible (SIS) model of Gross et al.[Phys. Rev. Lett. 96, 208701 (2006)], we introduce an improved compartmental formalism able to handle this coevolutionary task successfully. With this approach, we analyze the interplay and outcomes of both dynamical elements, process and structure, on adaptive networks featuring different degree distributions at the initial stage.

(show all)