Publications and collaborators

Here is a detailed list of my papers (including abstracts), and a list of my co-authors and students.


Picture of the inhomogeneous random graph introduced in the joint work with A. Pachon and M. Kang.

Papers

    2015 - now

  1. A General Markov Chain Approach for Disease and Rumor Spreading in Complex Networks
    (with G. Arruda, E. Cozzo, Y. Moreno, and F. Rodrigues).
    Journal of Complex Networks, In press.
    Abstract
    ×

    A General Markov Chain Approach for Disease and Rumor Spreading in Complex Networks

    with Guilherme Arruda, Francisco A. Rodrigues (ICMC-USP), Emanuele Cozzo, Yamir Moreno (Universidad de Zaragoza)

    Spreading processes are ubiquitous in natural and artificial systems. They can be studied via a plethora of models, depending on the specific details of the phenomena under study. Disease contagion and rumor spreading are among the most important of these processes due to their practical relevance. However, despite the similarities between them, current models address both spreading dynamics separately. In this paper, we propose a general information spreading model that is based on discrete time Markov chains. The model includes all the transitions that are plausible for both a disease contagion process and rumor propagation. We show that our model not only covers the traditional spreading schemes, but that it also contains some features relevant in social dynamics, such as apathy, forgetting, and lost/recovering of interest. The model is evaluated analytically to obtain the spreading thresholds and the early time dynamical behavior for the contact and reactive processes in several scenarios. Comparison with Monte Carlo simulations shows that the Markov chain formalism is highly accurate while it excels in computational efficiency. We round off our work by showing how the proposed framework can be applied to the study of spreading processes occurring on social networks.

  2. On the existence of accessibility in a tree-indexed percolation model (with C. Coletti and R. Gava).
    Physica A: Statistical Mechanics and its Applications 492 (2018):382-388.
    Abstract
    ×

    On the existence of accessibility in a tree-indexed percolation model

    with Cristian Coletti (UFABC) and Renato Gava (UFSCar)

    We study the accessibility percolation model on infinite trees. The model is defined by associating an absolute continuous random variable Xv to each vertex v of the tree. The main question to be considered is the existence or not of an infinite path of nearest neighbors v1, v2, v3 ... such that

    Xv1 < Xv2 < Xv3 < …

    and which span the entire graph. The event defined by the existence of such path is called percolation. We consider the case of the accessibility percolation model on a spherically symmetric tree with growth function given by f(i) = ⌈ (i+1) ⌉α, where α>0 is a given constant. We show that there is a percolation threshold at αc=1 such that there is percolation if α>1 and there is absence of percolation if α ≤ 1. Moreover, we study the event of percolation starting at any vertex, as well as the continuity of the percolation probability function. Finally, we provide a comparison between this model with the well known Fα record model. We also discuss a number of open problems concerning the accessibility percolation model for further consideration in future research.

  3. Phase transition for the Maki-Thompson rumor model on a small-world network.
    (with E. Agliari, A. Pachon, F. Tavani).
    Journal of Statistical Physics 169 n.4 (2017): 846-875.
    Abstract
    ×

    Phase transition for the Maki-Thompson rumor model on a small-world network

    with Elena Agliari, Flavia Tavani (Sapienza Università di Roma) and Angelica Pachon (Università di Torino)

    We consider the Maki-Thompson model for the stochastic propagation of a rumour within a population. We extend the original hypothesis of homogenously mixed population by allowing for a small-world network embedding the model. This structure is realized starting from a k-regular ring and by inserting, in the average, c additional links in such a way that k and c are tuneable parameter for the population architecture. We prove that this system exhibits a transition between regimes of localization (where the final number of stiflers is at most logarithmic in the population size) and propagation (where the final number of stiflers grows algebraically with the population size) at a finite value of the network parameter c. A quantitative estimate for the critical value of c is obtained via extensive numerical simulations.

  4. A stochastic two-stage innovation diffusion model on a lattice (with C. Coletti and K. B. E. Oliveira).
    Journal of Applied Probability 53 n.4 (2016): 1019-1030.
    ×

    A stochastic two-stage innovation diffusion model on a lattice

    with Cristian Coletti (UFABC) and Karina E. B. de Oliveira (ICMC-USP)

    We propose and study a spatial stochastic model describing a process of awareness, evaluation and decision-making by agents on the d-dimensional integer lattice. Each agent may be in any of the three states belonging to the set {0, 1, 2}. In this model 0 stands for ignorants, 1 for aware and 2 for adopters. Aware and adopters inform its nearest ignorant neighbors about a new product innovation at rate lambda. At rate alpha an agent in aware state becomes an adopter due to the influence of (its nearest) adopters neighbors. Finally, aware and adopters forget the information about the new product at rate one. The purpose of this work is to analyze the influence of the parameters lambda and alpha on the qualitative behavior of the process. More precisely, we study sufficient conditions under which the innovation diffusion (and adoption) either becomes extinct or propagates through the population with positive probability.

  5. A process of rumour scotching on finite populations (with Arruda, Lebensztayn and Rodrigues).
    Royal Society Open Science 2 (2015): 150240.
    Abstract
    ×

    A process of rumour scotching on finite populations

    with Elcio Lebensztayn (UNICAMP), Guilherme Arruda and Francisco Rodrigues (ICMC-USP)

    Rumour spreading is a ubiquitous phenomenon in social and technological networks. Traditional models consider that the rumour is propagated by pairwise interactions between spreaders and ignorants. Only spreaders are active and may become stiflers after contacting spreaders or stiflers. Here we propose a competition-like model in which spreaders try to transmit an information, while stiflers are also active and try to scotch it. We study the influence of transmission/scotching rates and initial conditions on the qualitative behaviour of the process. An analytical treatment based on the theory of convergence of density-dependent Markov chains is developed to analyse how the final proportion of ignorants behaves asymptotically in a finite homogeneously mixing population. We perform Monte Carlo simulations in random graphs and scale-free networks and verify that the results obtained for homogeneously mixing populations can be approximated for random graphs, but are not suitable for scale-free networks. Furthermore, regarding the process on a heterogeneous mixing population, we obtain a set of differential equations that describes the time evolution of the probability that an individual is in each state. Our model can also be applied for studying systems in which informed agents try to stop the rumour propagation, or for describing related SIR-systems. In addition, our results can be considered to develop optimal information dissemination strategies and approaches to control rumour propagation.

  6. 2008 - 2014

  7. The role of centrality for the identification of influential spreaders in complex networks
    (with G. de Arruda, A. Barbieri, F. Rodrigues, Y. Moreno and L. Costa).
    Physical Review E 90 (2014): 032812.
    Abstract
    ×

    The role of centrality for the identification of influential spreaders in complex networks

    with G. de Arruda, A. Barbieri, F. Rodrigues (ICMC-USP), Y. Moreno (University of Zaragoza) and L. Costa (IFSC-USP)

    The identification of the most influential spreaders in networks is important to control and understand the spreading capabilities of the system as well as to ensure an efficient information diffusion such as in rumor-like dynamics. Recent works have suggested that the identification of influential spreaders is not independent of the dynamics being studied. For instance, the key disease spreaders might not necessarily be so when it comes to analyze social contagion or rumor propagation. Additionally, it has been shown that different metrics (degree, coreness, etc) might identify different influential nodes even for the same dynamical processes with diverse degree of accuracy. In this paper, we investigate how nine centrality measures correlate with the disease and rumor spreading capabilities of the nodes that made up different synthetic and real-world (both spatial and non-spatial) networks. We also propose a generalization of the random walk accessibility as a new centrality measure and derive analytical expressions for the latter measure for simple network configurations. Our results show that for non-spatial networks, the k-core and degree centralities are most correlated to epidemic spreading, whereas the average neighborhood degree, the closeness centrality and accessibility are most related to rumor dynamics. On the contrary, for spatial networks, the accessibility measure outperforms the rest of centrality metrics in almost all cases regardless of the kind of dynamics considered. Therefore, an important consequence of our analysis is that previous studies performed in synthetic random networks cannot be generalized to the case of spatial networks.

  8. Rumor processes on N and discrete renewal processes (with S. Gallo, N. Garcia and V. Vargas).
    Journal of Statistical Physics 155 n.3 (2014): 591-602.
    Abstract
    ×

    Rumor processes on Ν and discrete renewal processes

    with Sandro Gallo (UFRJ), Nancy Garcia (UNICAMP) and Valdivino Vargas (UFG)

    We study two rumor processes on Ν, the dynamics of which are related to an SI epidemic model with long range transmission. Both models start with one spreader at site 0 and ignorants at all the other sites of Ν, but differ by the transmission mechanism. In one model, the spreaders transmit the information within a random distance on their right, and in the other the ignorants take the information from a spreader within a random distance on their left. We obtain the probability of survival, information on the distribution of the range of the rumor and limit theorems for the proportion of spreaders. The key step of our proofs is to show that, in each model, the position of the spreaders on Ν can be related to a suitably chosen discrete renewal process.

  9. A connection between a system of random walks and rumor transmission (with E. Lebensztayn).
    Physica A: Statistical Mechanics and its Applications 392 n.23 (2013): 5793-5800.
    Abstract
    ×

    A connection between a system of random walks and rumor transmission

    with Elcio Lebensztayn (UNICAMP)

    We establish a relationship between the phenomenon of rumor transmission on a population and a probabilistic model of interacting particles on the complete graph. More precisely, we consider variations of the Maki?Thompson epidemic model and the “frog model” of random walks, which were introduced in the scientific literature independently and in different contexts. We analyze the Markov chains which describe these models, and show a coupling between them. Our connection shows how the propagation of a rumor in a closed homogeneously mixing population can be described by a system of random walks on the complete graph. Additionally, we discuss further applications of the random walk model which are relevant to the modeling of different biological dynamics.

  10. A spatial stochastic model for rumor transmission (with C. F. Coletti and R. B. Schinazi).
    Journal of Statistical Physics 147 n.2 (2012): 375-381.
    Abstract
    ×

    A spatial stochastic model for rumor transmission

    with Cristian Coletti (UFABC) and Rinaldo Schinazi (University of Colorado)

    We consider an interacting particle system representing the spread of a rumor by agents on the d-dimensional integer lattice. Each agent may be in any of the three states belonging to the set {0,1,2}. Here 0 stands for ignorants, 1 for spreaders and 2 for stiflers. A spreader tells the rumor to any of its (nearest) ignorant neighbors at rate λ. At rate α a spreader becomes a stifler due to the action of other (nearest neighbor) spreaders. Finally, spreaders and stiflers forget the rumor at rate one. We study sufficient conditions under which the rumor either becomes extinct or survives with positive probability.

  11. Limit theorems for a general stochastic rumour model (with E. Lebensztayn and F. P. Machado).
    SIAM Journal on Applied Mathematics 71 n.4 (2011): 1476-1486.
    Abstract
    ×

    Limit theorems for a general stochastic rumour model

    with Elcio Lebensztayn and Fabio Machado (IME-USP)

    We study a general stochastic rumour model in which an ignorant individual has a certain probability of becoming a stifler immediately upon hearing the rumour. We refer to this special kind of stifler as an uninterested individual. Our model also includes distinct rates for meetings between two spreaders in which both become stiflers or only one does, so that particular cases are the classical Daley-Kendall and Maki-Thompson models. We prove a Law of Large Numbers and a Central Limit Theorem for the proportions of those who ultimately remain ignorant and those who have heard the rumour but become uninterested in it.

  12. On the behaviour of a rumour process with random stifling (with E. Lebensztayn and F. P. Machado).
    Environmental Modelling and Software 26 n.4 (2011): 517-522.
    Abstract
    ×

    On the behaviour of a rumour process with random stifling

    with Elcio Lebensztayn and Fabio Machado (IME-USP)

    We propose a realistic generalization of the Maki-Thompson rumour model by assuming that each spreader ceases to propagate the rumour right after being involved in a random number of stifling experiences. We consider the process with a general initial configuration and establish the asymptotic behaviour (and its fluctuation) of the ultimate proportion of ignorants as the population size grows to infinity. Our approach leads to explicit formulas so that the limiting proportion of ignorants and its variance can be computed.

  13. The disk-percolation model on graphs (with E. Lebensztayn).
    Statistics and Probability Letters 78 n.14 (2008): 2130-2136.
    Abstract
    ×

    The disk-percolation model on graphs

    with Elcio Lebensztayn (IME-USP)

    We study a long-range percolation model whose dynamics describe the spreading of an infection on an infinite graph. We obtain a sufficient condition for phase transition and prove an upper bound for the critical parameter of spherically symmetric trees.


Please contact me if you can not get free access to any of these publications.

Other publications

    Preprints

  1. On the isomorphisms between evolution algebras of random walks and graphs.
    (with P. Cadavid and Mary Luz Rodiño Montoya). Submited.
    Abstract
    ×

    On the isomorphisms between evolution algebras of random walks and graphs

    with Paula Cadavid and Mary Luz Rodiño Montoya (Universidad de Antioquia)

    Evolution algebras are non-associative algebras inspired from biological phenomena, which have applications to or connections with different mathematical fields. There are two natural ways to define an evolution algebra associated to a given graph. While one takes into account only the adjacencies of the graph, the other includes probabilities related to the symmetric random walk on the same graph. In this work we state new properties related to the relation between these algebras, which is one of the open questions in the theory of evolution algebras. We show that for any graph both algebras are strongly isotopic, while for non-singular graphs any homomorphism between them is either the null map or an isomorphism. In the last case we establish the form of such isomorphism. In addition, we establish a connection between this question and the problem of looking for automorphisms of an evolution algebra provided the underlying graph is regular. We use this comparison to revisit a result existing in the literature about the identification of the automorphism group of an evolution algebra, and we give an improved version of it.

  2. A connection between evolution algebras, random walks, and graphs.
    (with P. Cadavid and Mary Luz Rodiño Montoya). Submited.
    Abstract
    ×

    A connection between evolution algebras, random walks, and graphs

    with Paula Cadavid and Mary Luz Rodiño Montoya (Universidad de Antioquia)

    Evolution algebras are a new type of non-associative algebras which are inspired from biological phenomena. A special class of such algebras, called Markov evolution algebras, is strongly related to the theory of discrete time Markov chains. The winning of this relation is that many results coming from Probability Theory may be stated in the context of Abstract Algebra. In this paper we explore the connection between evolution algebras, random walks and graphs. More precisely, we study the relationships between the evolution algebra induced by a random walk on a graph and the evolution algebra determined by the same graph. Given that any Markov chain may be seen as a random walk on a graph we believe that our results may add a new landscape in the study of Markov evolution algebras.

  3. Frog models on trees through renewal theory.
    (with S. Gallo). Submited.
    Abstract
    ×

    Frog models on trees through renewal theory

    with Sandro Gallo (UFSCar)

    This paper studies a class of growing systems of random walks on regular trees, known as frog models with geometric lifetime in the literature. With the help of results from renewal theory, we derive new bounds for their critical parameters. As a byproduct, we also improve the bounds of the literature for the critical parameter of a percolation model on trees called cone percolation.

  4. Galton-Watson processes in varying environment and accessibility percolation
    (with D. Bertacchi and F. Zucca). Submited.
    Abstract
    ×

    Galton-Watson processes in varying environment and accessibility percolation

    with Daniela Bertacchi (Università di Milano-Bicocca) and Fabio Zucca (Politecnico di Milano)

    This paper deals with branching processes in varying environment, namely, whose offspring distributions depend on the generations. We provide sufficient conditions for survival or extinction which rely only on the first and second moments of the offspring distributions. These results are then applied to branching processes in varying environment with selection where every particle has a real-valued label and labels can only increase along genealogical lineages; we obtain analogous conditions for survival or extinction. These last results can be interpreted in terms of accessibility percolation on Galton-Watson trees, which represents a relevant tool for modeling the evolution of biological populations.

  5. Evolution of a modified binomial random graph by agglomeration
    (with M. Kang and A. Pachon). Submited.
    Abstract
    ×

    Evolution of a modified binomial random graph by agglomeration

    with Mihyun Kang (Graz University of Technology) and Angelica Pachón (Universittà di Torino)

    In the classical Erdös-Rényi random graph G(n, p) there are n vertices and each of the possible edges is independently present with probability p. One of the most known results for this model is the threshold for connectedness, a phenomenon which is tightly related to the nonexistence of isolated vertices. Numerous random graphs inspired in real networks are inhomogeneous in the sense that not all vertices have the same characteristic, which may influence the connection probability between pairs of vertices. The random graph G(n, p) is homogeneous in this respect. Thus, with the aim to study real networks, new random graph models have been introduced and analyzed recently. The purpose of this paper is to contribute to this task by proposing a new inhomogeneous random graph model which is obtained in a constructive way from the classical Erdös-Rényi model. We consider an initial configuration of subsets of vertices and we call each subset a super-vertex, then the random graph model is defined by letting that two super-vertices be connected if there is at least one edge between them in G(n,p). Our main result concerns to the threshold for connectedness. We also analyze the phase transition for the emergence of the giant component and the degree distribution. We point out that even though our model begin from G(n, p), it assumes the existence of community structure and under certain conditions it exhibits a power law degree distribution, both important properties for real applications.

  6. Lecture Notes

  7. Modelos probabilisticos discretos y aplicaciones (in spanish).
    Lecture notes of a minicourse given at EMALCA Colombia, Medellín, 2017.