BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Maria Deijfen

Maria Deijfen appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.PRmath.COphysics.soc-phQuantitative MethodsSocial and Information Networks

Catalog footprint

What is connected

27works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

27 published item(s)

preprint2022arXiv

Competition on $\mathbb{Z}^d$ driven by branching random walk

A competition process on $\mathbb{Z}^d$ is considered, where two species compete to color the sites. The entities are driven by branching random walks. Specifically red (blue) particles reproduce in discrete time and place offspring according to a given reproduction law, which may be different for the two types. When a red (blue) particle is placed at a site that has not been occupied by any particle before, the site is colored red (blue) and keeps this color forever. The types interact in that, when a particle is placed at a site of opposite color, the particle adopts the color of the site with probability $p\in[0,1]$. Can a given type color infinitely many sites? Can both types color infinitely many sites simultaneously? Partial answers are given to these questions and many open problems are formulated.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The winner takes it all but one

We study competing first passage percolation on graphs generated by the configuration model with infinite-mean degrees. Initially, two uniformly chosen vertices are infected with type 1 and type 2 infection, respectively, and the infection then spreads via nearest neighbors in the graph. The time it takes for the type 1 (resp. 2) infection to traverse an edge $e$ is given by a random variable $X_1(e)$ (resp. $X_2(e)$) and, if the vertex at the other end of the edge is still uninfected, it then becomes type 1 (resp. 2) infected and immune to the other type. Assuming that the degrees follow a power-law distribution with exponent $τ\in (1,2)$, we show that, with high probability as the number of vertices tends to infinity, one of the infection types occupies all vertices except for the starting point of the other type. Moreover, both infections have a positive probability of winning regardless of the passage times distribution. The result is also shown to hold for the erased configuration model, where self-loops are erased and multiple edges are merged, and when the degrees are conditioned to be smaller than $n^α$ for some $α> 0$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A preferential attachment model with random initial degrees

In this paper, a random graph process ${G(t)}_{t\geq 1}$ is studied and its degree sequence is analyzed. Let $(W_t)_{t\geq 1}$ be an i.i.d. sequence. The graph process is defined so that, at each integer time $t$, a new vertex, with $W_t$ edges attached to it, is added to the graph. The new edges added at time t are then preferentially connected to older vertices, i.e., conditionally on $G(t-1)$, the probability that a given edge is connected to vertex i is proportional to $d_i(t-1)+δ$, where $d_i(t-1)$ is the degree of vertex $i$ at time $t-1$, independently of the other edges. The main result is that the asymptotical degree sequence for this process is a power law with exponent $τ=\min\{τ_{W}, τ_{P}\}$, where $τ_{W}$ is the power-law exponent of the initial degrees $(W_t)_{t\geq 1}$ and $τ_{P}$ the exponent predicted by pure preferential attachment. This result extends previous work by Cooper and Frieze, which is surveyed.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Friendly frogs, stable marriage, and the magic of invariance

We introduce a two-player game involving two tokens located at points of a fixed set. The players take turns to move a token to an unoccupied point in such a way that the distance between the two tokens is decreased. Optimal strategies for this game and its variants are intimately tied to Gale-Shapley stable marriage. We focus particularly on the case of random infinite sets, where we use invariance, ergodicity, mass transport, and deletion-tolerance to determine game outcomes.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The winner takes it all

We study competing first passage percolation on graphs generated by the configuration model. At time 0, vertex 1 and vertex 2 are infected with the type 1 and the type 2 infection, respectively, and an uninfected vertex then becomes type 1 (2) infected at rate $λ_1$ ($λ_2$) times the number of edges connecting it to a type 1 (2) infected neighbor. Our main result is that, if the degree distribution is a power-law with exponent $τ\in(2,3)$, then, as the number of vertices tends to infinity and with high probability, one of the infection types will occupy all but a finite number of vertices. Furthermore, which one of the infections wins is random and both infections have a positive probability of winning regardless of the values of $λ_1$ and $λ_2$. The picture is similar with multiple starting points for the infections.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A stochastic model for competing growth on $\mathbb{R}^d$

A stochastic model, describing the growth of two competing infections on $\mathbb{R}^d$, is introduced. The growth is driven by outbursts in the infected region, an outburst in the type 1 (2) infected region transmitting the type 1 (2) infection to the previously uninfected parts of a ball with stochastic radius around the outburst point. The main result is that with the growth rate for one of the infection types fixed, mutual unbounded growth has probability zero for all but at most countably many values of the other infection rate. This is a continuum analog of a result of Häggström and Pemantle. We also extend a shape theorem of Deijfen for the corresponding model with just one type of infection.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Asymptotic shape in a continuum growth model

A continuum growth model is introduced. The state at time $t$, $S_t$, is a subset of $\mathbb{R}^d$ and consists of a connected union of randomly sized Euclidean balls, which emerge from outbursts at their center points. An outburst occurs somewhere in $S_t$ after an exponentially distributed time with expected value $|S_t|^{-1}$ and the location of the outburst is uniformly distributed over $S_t$. The main result is that if the distribution of the radii of the outburst balls has bounded support, then $S_t$ grows linearly and $S_t/t$ has a non-random shape as $t\rightarrow \infty$. Due to rotation invariance the asymptotic shape must be a Euclidean ball.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Coexistence in a two-type continuum growth model

We consider a stochastic model, describing the growth of two competing infections on $\mathbb{R}^d$. The growth takes place by way of spherical outbursts in the infected region, an outburst in the type 1 (2) infected region causing all previously uninfected points within a stochastic distance from the outburst location to be type 1 (2) infected. The main result is that, if the infection types have the same intensity, then there is a strictly positive probability that both infection types grow unboundedly.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Generating simple random graphs with prescribed degree distribution

Let $F$ be a probability distribution with support on the non-negative integers. Four methods for generating a simple undirected graph with (approximate) degree distribution $F$ are described and compared. Two methods are based on the so called configuration model with modifications ensuring a simple graph, one method is an extension of the classical Erdős-Rényi graph where the edge probabilities are random variables, and the last method starts with a directed random graph which is then modified to a simple undirected graph. All methods are shown to give the correct distribution in the limit of large graph size, but under different assumptions on the degree distribution $F$ and also using different order of operations.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Generating stationary random graphs on $\mathbb{Z}$ with prescribed i.i.d.\ degrees

Let $F$ be a probability distribution with support on the non-negative integers. Two algorithms are described for generating a stationary random graph, with vertex set $\mathbb{Z}$, so that the degrees of the vertices are i.i.d.\ random variables with distribution $F$. Focus is on an algorithm where, initially, a random number of "stubs" with distribution $F$ is attached to each vertex. Each stub is then randomly assigned a direction, left or right, and the edge configuration is obtained by pairing stubs pointing to each other, first exhausting all possible connections between nearest neighbors, then linking second nearest neighbors, and so on. Under the assumption that $F$ has finite mean, it is shown that this algorithm leads to a well-defined configuration, but that the expected length of the shortest edge of a vertex is infinite. It is also shown that any stationary algorithm for pairing stubs with random, independent directions gives infinite mean for the total length of the edges of a given vertex. Connections to the problem of constructing finitary isomorphisms between Bernoulli shifts are discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Growing networks with preferential addition and deletion of edges

A preferential attachment model for a growing network incorporating deletion of edges is studied and the expected asymptotic degree distribution is analyzed. At each time step $t=1,2,\ldots$, with probability $π_1>0$ a new vertex with one edge attached to it is added to the network and the edge is connected to an existing vertex chosen proportionally to its degree, with probability $π_2$ a vertex is chosen proportionally to its degree and an edge is added between this vertex and a randomly chosen other vertex, and with probability $π_3=1-π_1-π_2<1/2$ a vertex is chosen proportionally to its degree and a random edge of this vertex is deleted. The model is intended to capture a situation where high-degree vertices are more dynamic than low-degree vertices in the sense that their connections tend to be changing. A recursion formula is derived for the expected asymptotic fraction $p_k$ of vertices with degree $k$, and solving this recursion reveals that, for $π_3<1/3$, we have $p_k\sim k^{-(3-7π_3)/(1-3π_3)}$, while, for $π_3>1/3$, the fraction $p_k$ decays exponentially at rate $(π_1+π_2)/2π_3$. There is hence a non-trivial upper bound for how much deletion the network can incorporate without loosing the power-law behavior of the degree distribution. The analytical results are supported by simulations.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Nonmonotonic coexistence regions for the two-type Richardson model

In the two-type Richardson model on a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, each vertex is at a given time in state $0$, $1$ or $2$. A $0$ flips to a $1$ (resp.\ $2$) at rate $λ_1$ ($λ_2$) times the number of neighboring $1$'s ($2$'s), while $1$'s and $2$'s never flip. When $\mathcal{G}$ is infinite, the main question is whether, starting from a single $1$ and a single $2$, with positive probability we will see both types of infection reach infinitely many sites. This has previously been studied on the $d$-dimensional cubic lattice $\mathbb{Z}^d$, $d\geq 2$, where the conjecture (on which a good deal of progress has been made) is that such coexistence has positive probability if and only if $λ_1=λ_2$. In the present paper examples are given of other graphs where the set of points in the parameter space which admit such coexistence has a more surprising form. In particular, there exist graphs exhibiting coexistence at some value of $\frac{λ_1}{λ_2} \neq 1$ and non-coexistence when this ratio is brought closer to $1$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Random intersection graphs with tunable degree distribution and clustering

A random intersection graph is constructed by assigning independently to each vertex a subset of a given set and drawing an edge between two vertices if and only if their respective subsets intersect. In this paper a model is developed in which each vertex is given a random weight, and vertices with larger weights are more likely to be assigned large subsets. The distribution of the degree of a given vertex is characterized and is shown to depend on the weight of the vertex. In particular, if the weight distribution is a power law, the degree distribution will be so as well. Furthermore, an asymptotic expression for the clustering in the graph is derived. By tuning the parameters of the model, it is possible to generate a graph with arbitrary clustering, expected degree and -- in the power law case -- tail exponent.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Random networks with preferential growth and vertex death

A dynamic model for a random network evolving in continuous time is defined where new vertices are born and existing vertices may die. The fitness of a vertex is defined as the accumulated in-degree of the vertex and a new vertex is connected to an existing vertex with probability proportional to a function $b$ of the fitness of the existing vertex. Furthermore, a vertex dies at a rate given by a function $d$ of its fitness. Using results from the theory of general branching processes, an expression for the asymptotic empirical fitness distribution $\{p_k\}$ is derived and analyzed for a number of specific choices of $b$ and $d$. When $b(i)=i+α$ and $d(i)=β$ -- that is, linear preferential attachment for the newborn and random deaths -- then $p_k\sim k^{-(2+α)}$. When $b(i)=i+1$ and $d(i)=β(i+1)$, with $β<1$, then $p_k\sim (1+β)^{-k}$, that is, if also the death rate is proportional to the fitness, then the power law distribution is lost. Furthermore, when $b(i)=i+1$ and $d(i)=β(i+1)^γ$, with $β,γ<1$, then $\log p_k\sim -k^γ$ -- a stretched exponential distribution. The momentaneous in-degrees are also studied and simulations suggest that their behaviour is qualitatively similar to that of the fitnesses.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Stationary random graphs on $\mathbb{Z}$ with prescribed iid degrees and finite mean connections

Let $F$ be a probability distribution with support on the non-negative integers. A model is proposed for generating stationary simple graphs on $\mathbb{Z}$ with degree distribution $F$ and it is shown for this model that the expected total length of all edges at a given vertex is finite if $F$ has finite second moment. It is not hard to see that any stationary model for generating simple graphs on $\mathbb{Z}$ will give infinite mean for the total edge length per vertex if $F$ does not have finite second moment. Hence, finite second moment of $F$ is a necessary and sufficient condition for the existence of a model with finite mean total edge length.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Stationary random graphs with prescribed iid degrees on a spatial Poisson process

Let $[\mathcal{P}]$ be the points of a Poisson process on $\mathbb{R}^d$ and $F$ a probability distribution with support on the non-negative integers. Models are formulated for generating translation invariant random graphs with vertex set $[\mathcal{P}]$ and iid vertex degrees with distribution $F$, and the length of the edges is analyzed. The main result is that finite mean for the total edge length per vertex is possible if and only if $F$ has finite moment of order $(d+1)/d$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The initial configuration is irrelevant for the possibility of mutual unbounded growth in the two-type Richardson model

The two-type Richardson model describes the growth of two competing infections on $\mathbb{Z}^d$. At time 0 two disjoint finite sets $ξ_1,ξ_2\subset \mathbb{Z}^d$ are infected with type 1 and type 2 infection respectively. An uninfected site then becomes type 1 (2) infected at a rate proportional to the number of type 1 (2) infected nearest neighbors and once infected it remains so forever. The main result in this paper is, loosely speaking, that the choice of the initial sets $ξ_1$ and $ξ_2$ is irrelevant in deciding whether the event of mutual unbounded growth for the two infection types has positive probability or not.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The pleasures and pains of studying the two-type Richardson model

This paper provides a survey of known results and open problems for the two-type Richardson model, which is a stochastic model for competition on $\mathbb{Z}^d$. In its simplest formulation, the Richardson model describes the evolution of a single infectious entity on $\mathbb{Z}^d$, but more recently the dynamics have been extended to comprise two competing growing entities. For this version of the model, the main question is whether there is a positive probability for both entities to simultaneously grow to occupy infinite parts of the lattice, the conjecture being that the answer is yes if and only if the entities have the same intensity. In this paper attention focuses on the two-type model, but the most important results for the one-type version are also described.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

First passage percolation on $\mathbb{Z}^2$ -- a simulation study

First passage percolation on $\mathbb{Z}^2$ is a model for describing the spread of an infection on the sites of the square lattice. The infection is spread via nearest neighbor sites and the time dynamic is specified by random passage times attached to the edges. In this paper, the speed of the growth and the shape of the infected set is studied by aid of large-scale computer simulations, with focus on continuous passage time distributions. It is found that the most important quantity for determining the value of the time constant, which indicates the inverse asymptotic speed of the growth, is $\mathbf{E}[\min\{τ_1,\ldots,τ_4\}]$, where $τ_1,\ldots,τ_4$ are i.i.d. passage time variables. The relation is linear for a large class of passage time distributions. Furthermore, the directional time constants are seen to be increasing when moving from the axis towards the diagonal, so that the limiting shape is contained in a circle with radius defined by the speed along the axes. The shape comes closer to the circle for distributions with larger variability.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Routing on trees

We consider three different schemes for signal routing on a tree. The vertices of the tree represent transceivers that can transmit and receive signals, and are equipped with i.i.d. weights representing the strength of the transceivers. The edges of the tree are also equipped with i.i.d. weights, representing the costs for passing the edges. For each one of our schemes, we derive sharp conditions on the distributions of the vertex weights and the edge weights that determine when the root can transmit a signal over arbitrarily large distances.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Bipartite stable Poisson graphs on R

Let red and blue points be distributed on $\mathbb{R}$ according to two independent Poisson processes $\mathcal{R}$ and $\mathcal{B}$ and let each red (blue) point independently be equipped with a random number of half-edges according to a probability distribution $ν$ ($μ$). We consider translation-invariant bipartite random graphs with vertex classes defined by the point sets of $\mathcal{R}$ and $\mathcal{B}$, respectively, generated by a scheme based on the Gale-Shapley stable marriage for perfectly matching the half-edges. Our main result is that, when all vertices have degree 2 almost surely, then the resulting graph does not contain an infinite component. The two-color model is hence qualitatively different from the one-color model, where Deijfen, Holroyd and Peres have given strong evidence that there is an infinite component. We also present simulation results for other degree distributions.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A weighted configuration model and inhomogeneous epidemics

A random graph model with prescribed degree distribution and degree dependent edge weights is introduced. Each vertex is independently equipped with a random number of half-edges and each half-edge is assigned an integer valued weight according to a distribution that is allowed to depend on the degree of its vertex. Half-edges with the same weight are then paired randomly to create edges. An expression for the threshold for the appearance of a giant component in the resulting graph is derived using results on multi-type branching processes. The same technique also gives an expression for the basic reproduction number for an epidemic on the graph where the probability that a certain edge is used for transmission is a function of the edge weight. It is demonstrated that, if vertices with large degree tend to have large (small) weights on their edges and if the transmission probability increases with the edge weight, then it is easier (harder) for the epidemic to take off compared to a randomized epidemic with the same degree and weight distribution. A recipe for calculating the probability of a large outbreak in the epidemic and the size of such an outbreak is also given. Finally, the model is fitted to three empirical weighted networks of importance for the spread of contagious diseases and it is shown that $R_0$ can be substantially over- or underestimated if the correlation between degree and weight is not taken into account.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Epidemics and vaccination on weighted graphs

A Reed-Frost epidemic with inhomogeneous infection probabilities on a graph with prescribed degree distribution is studied. Each edge $(u,v)$ in the graph is equipped with two weights $W_{(u,v)}$ and $W_{(v,u)}$ that represent the (subjective) strength of the connection and determine the probability that $u$ infects $v$ in case $u$ is infected and vice versa. Expressions for the epidemic threshold are derived for i.i.d.\ weights and for weights that are functions of the degrees. For i.i.d.\ weights, a variation of the so called acquaintance vaccination strategy is analyzed where vertices are chosen randomly and neighbors of these vertices with large edge weights are vaccinated. This strategy is shown to outperform the strategy where the neighbors are chosen randomly in the sense that the basic reproduction number is smaller for a given vaccination coverage.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Scale-free percolation

We formulate and study a model for inhomogeneous long-range percolation on $\Zbold^d$. Each vertex $x\in\Zbold^d$ is assigned a non-negative weight $W_x$, where $(W_x)_{x\in\Zbold^d}$ are i.i.d.\ random variables. Conditionally on the weights, and given two parameters $α,λ>0$, the edges are independent and the probability that there is an edge between $x$ and $y$ is given by $p_{xy}=1-\exp\{-λW_xW_y/|x-y|^α\}$. The parameter $λ$ is the percolation parameter, while $α$ describes the long-range nature of the model. We focus on the degree distribution in the resulting graph, on whether there exists an infinite component and on graph distance between remote pairs of vertices. First, we show that the tail behavior of the degree distribution is related to the tail behavior of the weight distribution. When the tail of the distribution of $W_x$ is regularly varying with exponent $τ-1$, then the tail of the degree distribution is regularly varying with exponent $γ=α(τ-1)/d$. The parameter $γ$ turns out to be crucial for the behavior of the model. Conditions on the weight distribution and $γ$ are formulated for the existence of a critical value $λ_c\in(0,\infty)$ such that the graph contains an infinite component when $λ>λ_c$ and no infinite component when $λ<λ_c$. Furthermore, a phase transition is established for the graph distances between vertices in the infinite component at the point $γ=2$, that is, at the point where the degrees switch from having finite to infinite second moment. The model can be viewed as an interpolation between long-range percolation and models for inhomogeneous random graphs, and we show that the behavior shares the interesting features of both these models.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Stable Poisson Graphs in One Dimension

Let each point of a homogeneous Poisson process on $\RR$ independently be equipped with a random number of stubs (half-edges) according to a given probability distribution $μ$ on the positive integers. We consider schemes based on Gale-Shapley stable marriage for perfectly matching the stubs to obtain a simple graph with degree distribution $μ$. We prove results on the existence of an infinite component and on the length of the edges, with focus on the case $μ(\{2\})=1$. In this case, for the random direction stable matching scheme introduced by Deijfen and Meester we prove that there is no infinite component, while for the stable matching of Deijfen, Häggström and Holroyd we prove that existence of an infinite component follows from a certain statement involving a {\em finite} interval, which is overwhelmingly supported by simulation evidence.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On the speed of biased random walk in translation invariant percolation

For biased random walk on the infinite cluster in supercritical i.i.d.\ percolation on $\Z^2$, where the bias of the walk is quantified by a parameter $β>1$, it has been conjectured (and partly proved) that there exists a critical value $β_c>1$ such that the walk has positive speed when $β<β_c$ and speed zero when $β>β_c$. In this paper, biased random walk on the infinite cluster of a certain translation invariant percolation process on $\Z^2$ is considered. The example is shown to exhibit the opposite behavior to what is expected for i.i.d.\ percolation, in the sense that it has a critical value $β_c$ such that, for $β<β_c$, the random walk has speed zero, while, for $β>β_c$, the speed is positive. Hence the monotonicity in $β$ that is part of the conjecture for i.i.d.\ percolation cannot be extended to general translation invariant percolation processes.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Percolation in invariant Poisson graphs with i.i.d. degrees

Let each point of a homogeneous Poisson process in R^d independently be equipped with a random number of stubs (half-edges) according to a given probability distribution mu on the positive integers. We consider translation-invariant schemes for perfectly matching the stubs to obtain a simple graph with degree distribution mu. Leaving aside degenerate cases, we prove that for any mu there exist schemes that give only finite components as well as schemes that give infinite components. For a particular matching scheme that is a natural extension of Gale-Shapley stable marriage, we give sufficient conditions on mu for the absence and presence of infinite components.

0 citations0 reviewsNo code linkedOpen access