Pour savoir comment effectuer et gérer un dépôt de document, consultez le « Guide abrégé – Dépôt de documents » sur le site Web de la Bibliothèque. Pour toute question, écrivez à corpus@ulaval.ca.
 

Personne :
Dubé, Louis J.

En cours de chargement...
Photo de profil

Adresse électronique

Date de naissance

Projets de recherche

Structures organisationnelles

Fonction

Nom de famille

Dubé

Prénom

Louis J.

Affiliation

Université Laval. Département de physique, de génie physique et d'optique

ISNI

ORCID

Identifiant Canadiana

ncf11850600

person.page.name

Résultats de recherche

Voici les éléments 1 - 10 sur 13
  • PublicationAccès libre
    Complex networks as an emerging property of hierarchical preferential attachment
    (American Physical Society, 2015-12-09) Young, Jean-Gabriel; Hébert-Dufresne, Laurent; Allard, Antoine; Laurence, Edward; Dubé, Louis J.
    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.
  • PublicationAccès libre
    Percolation on random networks with arbitrary k-core structure
    (American Physical Society through the American Institute of Physics, 2013-12-30) Young, Jean-Gabriel; Hébert-Dufresne, Laurent; Allard, Antoine; Dubé, Louis J.
    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.
  • PublicationAccès libre
    Finite-size analysis of the detectability limit of the stochastic block model
    (American Physical Society, 2017-06-19) Young, Jean-Gabriel; Hébert-Dufresne, Laurent; Laurence, Edward; Dubé, Louis J.; Desrosiers, Patrick
    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.
  • PublicationAccès libre
    Global efficiency of local immunization on complex networks
    (Nature Publishing Group, 2013-07-10) Young, Jean-Gabriel; Hébert-Dufresne, Laurent; Allard, Antoine; Dubé, Louis J.
    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.
  • PublicationAccès libre
    Phase transition of the susceptible-infected-susceptible dynamics on time-varying configuration model networks
    (American Physical Society, 2018-02-12) Young, Jean-Gabriel; St-Onge, Guillaume; Laurence, Edward; Dubé, Louis J.; Murphy, Charles
    We present a degree-based theoretical framework to study the susceptible-infected-susceptible (SIS) dynamics on time-varying (rewired) configuration model networks. Using this framework on a given degree distribution, we provide a detailed analysis of the stationary state using the rewiring rate to explore the whole range of the time variation of the structure relative to that of the SIS process. This analysis is suitable for the characterization of the phase transition and leads to three main contributions: (1) We obtain a self-consistent expression for the absorbing-state threshold, able to capture both collective and hub activation. (2) We recover the predictions of a number of existing approaches as limiting cases of our analysis, providing thereby a unifying point of view for the SIS dynamics on random networks. (3) We obtain bounds for the critical exponents of a number of quantities in the stationary state. This allows us to reinterpret the concept of hub-dominated phase transition. Within our framework, it appears as a heterogeneous critical phenomenon: observables for different degree classes have a different scaling with the infection rate. This phenomenon is followed by the successive activation of the degree classes beyond the epidemic threshold.
  • PublicationAccès libre
    Exact analytical solution of irreversible binary dynamics on networks
    (American Physical Society, 2018-03-02) Young, Jean-Gabriel; Laurence, Edward; Melnik, Sergey; Dubé, Louis J.
    In binary cascade dynamics, the nodes of a graph are in one of two possible states (inactive, active), andnodes in the inactive state make an irreversible transition to the active state, as soon as their precursors satisfya predetermined condition. We introduce a set of recursive equations to compute the probability of reachingany final state, given an initial state, and a specification of the transition probability function of each node.Because the naive recursive approach for solving these equations takes factorial time in the number of nodes, wealso introduce an accelerated algorithm, built around a breath-first search procedure. This algorithm solves theequations as efficiently as possible in exponential time.
  • PublicationAccès libre
    Coexistence of phases and the observability of random graphs
    (American Physical Society, 2014-02-06) Young, Jean-Gabriel; Hébert-Dufresne, Laurent; Allard, Antoine; Dubé, Louis J.
    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.
  • PublicationAccès libre
    Constrained growth of complex scale-independent systems
    (American Physical Society, 2016-03-03) Young, Jean-Gabriel; Hébert-Dufresne, Laurent; Allard, Antoine; Dubé, Louis J.
    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.
  • PublicationRestreint
    Efficient sampling of spreading processes on complex networks using a composition and rejection algorithm
    (Elsevier, 2019-02-19) Young, Jean-Gabriel; Hébert-Dufresne, Laurent; St-Onge, Guillaume; Dubé, Louis J.
    Efficient stochastic simulation algorithms are of paramount importance to the study of spreading phenomena on complex networks. Using insights and analytical results from network science, we discuss how the structure of contacts affects the efficiency of current algorithms. We show that algorithms believed to require O(log N) or even O(1) operations per update – where N is the number of nodes – display instead a polynomial scaling for networks that are either dense or sparse and heterogeneous. This significantly affects the required computation time for simulations on large networks. To circumvent the issue, we propose a node-based method combined with a composition and rejection algorithm, a sampling scheme that has an average-case complexity of O[log(log N)] per update for general networks. This systematic approach is first set-up for Markovian dynamics, but can also be adapted to a number of non-Markovian processes and can enhance considerably the study of a wide range of dynamics on networks.
  • PublicationAccès libre
    A shadowing problem in the detection of overlapping communities : lifting the resolution limit through a cascading procedure
    (Public Library of Science, 2015-10-13) Young, Jean-Gabriel; Hébert-Dufresne, Laurent; Allard, Antoine; Dubé, Louis J.
    Community detection is the process of assigning nodes and links in significant communities (e.g. 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.