with Jason Schweinsberg
arXiv:2310.00707, 23pp, 2023 Download: Preprint

We consider branching Brownian motion in which initially there is one particle at $x$, particles produce a random number of offspring with mean $m+1$ at the time of branching events, and each particle branches at rate $\beta = 1/2m$. Particles independently move according to Brownian motion with drift $-1$ and are killed at the origin. It is well-known that this process eventually dies out with positive probability. We condition this process to survive for an unusually large time $t$ and study the behavior of the process at small times $s \ll t$ using a spine decomposition. We show, in particular, that the time when a particle gets furthest from the origin is of the order $t^{5/6}$.

with Manon Costa and Anthony Muraro
arXiv:2305.08498, 2023 Download: Preprint

We consider a discrete-time version of a Hawkes process defined as a Poisson auto-regressive process whose parameters depend on the past of the trajectory. We allow these parameters to take on negative values, modelling inhibition. More precisely, the model is the stochastic process $(X_n)_{n\ge 0}$ with parameters $a_1,…,a_p \in \mathbb {R}$, $p\in \mathbb {N}$ and $\lambda \ge 0$, such that for all $n\ge p$, conditioned on $X_0,…,X_{n-1}$, $X_n$ is Poisson distributed with parameter \[ \left (a_1 X_{n-1} + \cdots + a_p X_{n-p} + \lambda \right )_+ \] We consider specifically the case $p = 2$, for which we are able to classify the asymptotic behavior of the process for the whole range of parameters, except for boundary cases. In particular, we show that the process remains stochastically bounded whenever the linear recurrence equation $x_n = a_1x_{n-1} + a_2x_{n-1} + \lambda $ remains bounded, but the converse is not true. Relatedly, the criterion for stochastic boundedness is not symmetric in $a_1$ and $a_2$, in contrast to the case of non-negative parameters, illustrating the complex effects of inhibition.

with Sarah Penington
arXiv:2209.14653, 2022 Download: Preprint

We study the Bolker-Pacala-Diekmann-Law (BPDL) model of population dynamics in the regime of large population density. The BPDL model is a particle system in which particles reproduce, move randomly in space and compete with each other locally. We rigorously prove global survival as well as a shape theorem describing the asymptotic spread of the population, when the population density is sufficiently large. In contrast to most previous studies, we allow the competition kernel to have an arbitrary, even infinite range, whence the term non-local competition. This makes the particle system non-monotone and of infinite-range dependence, meaning that the usual comparison arguments break down and have to be replaced by a more hands-on approach. Some ideas in the proof are inspired by works on the non-local Fisher-KPP equation, but the stochasticity of the model creates new difficulties.

with Olivier Wintenberger
arXiv:2207.07069, 2022 Download: Preprint

We consider random coefficient autoregressive models of infinite order (AR(∞)) under the assumption of non-negativity of the coefficients. We develop novel methods yielding sufficient or necessary conditions for finiteness of moments, based on combinatorial expressions of first and second moments. The methods based on first moments recover previous sufficient conditions by Doukhan and Wintenberger in our setting. The second moment method provides in particular a necessary and sufficient condition for finiteness of second moments which is different, but shown to be equivalent to the classical criterion of Nicholls and Quinn in the case of finite order. We further illustrate our results through two examples.

with Fu-Hsuan Ho
Electronic Journal of Probability 27, 1–18, 2022 Download: Preprint

Disordered systems such as spin glasses have been used extensively as models for high-dimensional random landscapes and studied from the perspective of optimization algorithms. In a recent paper by L. Addario-Berry and the second author, the continuous random energy model (CREM) was proposed as a simple toy model to study the efficiency of such algorithms. The following question was raised in that paper: what is the threshold β G , at which sampling (approximately) from the Gibbs measure at inverse temperature β becomes algorithmically hard? This paper is a first step towards answering this question. We consider the branching random walk, a time-homogeneous version of the continuous random energy model. We show that a simple greedy search on a renormalized tree yields a linear-time algorithm which approximately samples from the Gibbs measure, for every β < β c , the (static) critical point. More precisely, we show that for every ε > 0, there exists such an algorithm such that the specific relative entropy between the law sampled by the algorithm and the Gibbs measure of inverse temperature β is less than ε with high probability. In the supercritical regime β > β c , we provide the following hardness result. Under a mild regularity condition, for every δ > 0, there exists z > 0 such that the running time of any given algorithm approximating the Gibbs measure stochastically dominates a geometric random variable with parameter e −z √ N on an event with probability at least 1 − δ.

with Bastien Mallein
Electronic Communications in Probability 26, 1–12, 2021 Download: Journal

with Gaël Raoul and Julie Tourniaire
arXiv:2105.06985, 2021 Download: Preprint

We consider a certain lattice branching random walk with on-site competition and in an environment which is heterogeneous at a macroscopic scale $1/\varepsilon $ in space and time. This can be seen as a model for the spatial dynamics of a biological population in a habitat which is heterogeneous at a large scale (mountains, temperature or precipitation gradient...). The model incorporates another parameter, $K$, which is a measure of the local population density. We study the model in the limit when first $\varepsilon \to 0$ and then $K\to \infty $. In this asymptotic regime, we show that the rescaled position of the front as a function of time converges to the solution of an explicit ODE. We further discuss the relation with another popular model of population dynamics, the Fisher-KPP equation, which arises in the limit $K\to \infty $. Combined with known results on the Fisher-KPP equation, our results show in particular that the limits $\varepsilon \to 0$ and $K\to \infty $ do not commute in general. We conjecture that an interpolating regime appears when $\log K$ and $1/\varepsilon $ are of the same order.

with Michel Pain
arXiv:2103.10412 Download: Preprint

Let $\mu _t$ denote the critical derivative Gibbs measure of branching Brownian motion at time$\sim $$t$. It has been proved by Madaule and Maillard and Zeitouni that $\mu _t$ converges weakly to the random measure $Z_\infty \sqrt {2/\pi } x^2 e^{-x^2/2} \boldsymbol 1_{x >0}\; dx$, where $Z_\infty $ is the limit of the derivative martingale. In this paper, we are interested in the fluctuations that occur in this convergence and prove for a large class of functions $F$ that \[ \sqrt {t} \left ( \int _{\mathbb R} F\;d\mu _t - Z_\infty \int _0^\infty F(x) \sqrt {\frac {2}{\pi }} x^2 e^{-x^2/2} \;dx - \frac {c(F) \log t}{\sqrt {t}} Z_\infty \right ) \xrightarrow [t\to \infty ]{} S^F_{Z_\infty },  \text {in law}, \] where $c(F)$ is a constant depending on $F$ and $(S^F_r)_{r\geq 0}$ is a 1-stable Lévy process independent of $Z_\infty $. Moreover, we extend this result to a functional convergence, and we identify precisely the particles responsible for the fluctuations. In particular, this proves the following result for the critical additive martingale $(W_t)_{t\geq 0}$: \[ \sqrt {t} \left ( \sqrt {t} W_t - \sqrt {\frac {2}{\pi }} Z_\infty \right ) \xrightarrow [t\to \infty ]{} S_{Z_\infty },  \text {in law}, \] where here $(S_r)_{r\geq 0}$ is a Cauchy process independent of $Z_\infty $, confirming a conjecture by Mueller and Munier in the physics literature.

with Jason Schweinsberg
Annales Henri Lebesgue 5, 921–985, 2022 Download: Journal · Preprint

We consider one-dimensional branching Brownian motion in which particles are absorbed at the origin. We assume that when a particle branches, the offspring distribution is supercritical, but the particles are given a critical drift towards the origin so that the process eventually goes extinct with probability one. We establish precise asymptotics for the probability that the process survives for a large time t, building on previous results by Kesten (1978) and Berestycki, Berestycki, and Schweinsberg (2014). We also prove a Yaglom-type limit theorem for the behavior of the process conditioned to survive for an unusually long time, providing an essentially complete answer to a question first addressed by Kesten (1978). An important tool in the proofs of these results is the convergence of a certain observable to a continuous state branching process. Our proofs incorporate new ideas which might be of use in other branching models.

with Elliot Paquette
Annals of Applied Probability 32, 3537–3571, 2022 Download: Preprint

We consider a Markovian evolution on point processes, the Ψ–process, on the unit interval in which points are added according to a rule that depends only on the spacings of the existing point configuration. Having chosen a spacing, a new point is added uniformly within it. Building on previous work of the authors and of Junge, we show that the empirical distribution of points in such a process is always equidistributed under mild assumptions on the rule, generalizing work of Junge. A major portion of this article is devoted to the study of a particular growth–fragmentation process, or cell process, which is a type of piecewise–deterministic Markov process (PDMP). This process represents a linearized version of a size–biased sampling from the Ψ–process. We show that this PDMP is ergodic and develop the semigroup theory of it, to show that it describes a linearized version of the Ψ–process. This PDMP has appeared in other contexts, and in some sense we develop its theory under minimal assumptions.

with Pierre Boutaud
arXiv:2004.03393, 1–25, 2020 Download: Preprint

We consider branching random walks with a spine in the domain of attraction of an α-stable Lévy process. For this process, the classical derivative martingale in general degenerates in the limit. We first determine the quantity replacing the derivative martingale and show that it converges to a non-degenerate limit under a certain LlogL-type condition which we assume to be optimal. We go on to give the Seneta-Heyde norming for the critical additive martingale under the same assumptions. The proofs are based on the methods introduced in our previous paper which considered the finite variance case [Boutaud and Maillard (2019), EJP, vol. 24, paper no. 99].

with Pierre Boutaud
Electronic Journal of Probability 24, paper no. 99, 22 pp., 2019 Download: Journal · Preprint

We introduce a set of tools which simplify and streamline the proofs of limit theorems concerning near-critical particles in branching random walks under optimal assumptions. We exemplify our method by giving another proof of the Seneta-Heyde norming for the critical additive martingale, initially due to Aïdékon and Shi. The method involves in particular the replacement of (truncated) second moments by truncated first moments, and the replacement of ballot-type theorems for random walks by estimates coming from an explicit expression for the potential kernel of random walks killed below the origin. Of independent interest might be a short, self-contained proof of this expression, as well as a criterion for convergence in probability of non-negative random variables in terms of conditional Laplace transforms.

with Louigi Addario-Berry
Mathematical Statistics and Learning 2, 77–101, 2019 Download: Preprint

We prove an algorithmic hardness result for finding low-energy states in the so-called continuous random energy model (CREM), introduced by Bovier and Kurkova in 2004 as an extension of Derrida's generalized random energy model. The CREM is a model of a random energy landscape $(X_v)_{v \in \{0,1\}^N}$ on the discrete hypercube with built-in hierarchical structure, and can be regarded as a toy model for strongly correlated random energy landscapes such as the family of $p$-spin models including the Sherrington–Kirkpatrick model. The CREM is parameterized by an increasing function $A:[0,1]\to [0,1]$, which encodes the correlations between states. We exhibit an algorithmic hardness threshold $x_*$, which is explicit in terms of $A$. More precisely, we obtain two results: First, we show that a renormalization procedure combined with a greedy search yields for any $\varepsilon > 0$ a linear-time algorithm which finds states $v \in \{0,1\}^N$ with $X_v \ge (x_*-\varepsilon ) N$. Second, we show that the value $x_*$ is essentially best-possible: for any $\varepsilon > 0$, any algorithm which finds states $v$ with $X_v \ge (x_*+\varepsilon )N$ requires exponentially many queries in expectation and with high probability. We further discuss what insights this study yields for understanding algorithmic hardness thresholds for random instances of combinatorial optimization problems.

with Michel Pain
The Annals of Probability 47, 2953–3002, 2019 Download: Journal · Preprint

Let $(Z_t)_{t\geq 0}$ denote the derivative martingale of branching Brownian motion, i.e.\@ the derivative with respect to the inverse temperature of the normalized partition function at critical temperature. A well-known result by Lalley and Sellke [Ann. Probab., 15(3):1052–1061, 1987] says that this martingale converges almost surely to a limit $Z_\infty $, positive on the event of survival. In this paper, our concern is the fluctuations of the derivative martingale around its limit. A corollary of our results is the following convergence, confirming and strengthening a conjecture by Mueller and Munier [Phys. Rev. E, 90:042143, 2014]: \[ \sqrt {t} \left ( Z_\infty - Z_t + \frac {\log t}{\sqrt {2\pi t}} Z_\infty \right ) \xrightarrow [t\to \infty ]{} S_{Z_\infty },  \text {in law}, \] where $S$ is a spectrally positive 1-stable Lévy process independent of $Z_\infty $. In a first part of the paper, a relatively short proof of (a slightly stronger form of) this convergence is given based on the functional equation satisfied by the characteristic function of $Z_\infty $ together with tail asymptotics of this random variable. We then set up more elaborate arguments which yield a more thorough understanding of the trajectories of the particles contributing to the fluctuations. In this way, we can upgrade our convergence result to functional convergence. This approach also sets the ground for a follow-up paper, where we study the fluctuations of more general functionals including the renormalized critical additive martingale. All proofs in this paper are given under the hypothesis $\mathbb E[L(\log L)^3] < \infty $, where the random variable $L$ follows the offspring distribution of the branching Brownian motion. We believe this hypothesis to be optimal.

with Linxiao Chen and Nicolas Curien
Annales de l'Institut Henri Poincare (D) Combinatorics, Physics and their Interactions 7, 535–584, 2020 Download: Journal · Preprint

We study the branching tree of the perimeters of the nested loops in the nongeneric critical O.n/ model on random quadrangulations. We prove that after renormalization it converges towards an explicit continuous multiplicative cascade whose offspring distribution .xi /i≥1 is related to the jumps of a spectrally positive ˛-stable Lévy process with ˛ (formula presented) and for which we have the surprisingly simple and explicit transform (formula presented) An important ingredient in the proof is a new formula of independent interest on first moments of additive functionals of the jumps of a left-continuous random walk stopped at a hitting time. We also identify the scaling limit of the volume of the critical O.n/-decorated quadrangulation using the Malthusian martingale associated to the continuous multiplicative cascade.

Bernoulli 24, 297–315, 2018 Download: Journal · Preprint

A λ-invariant measure of a sub-Markov chain is a left eigenvector of its transition matrix of eigenvalue λ. In this article, we give an explicit integral representation of the λ-invariant measures of subcritical Bienaymé–Galton–Watson processes killed upon extinction, i.e. upon hitting the origin. In particular, this characterizes all quasi-stationary distributions of these processes. Our formula extends the Kesten–Spitzer formula for the (1-)invariant measures of such a process and can be interpreted as the identification of its minimal λ-Martin entrance boundary for all λ. In the particular case of quasi-stationary distributions, we also present an equivalent characterization in terms of semi-stable subordinators. Unlike Kesten and Spitzer's arguments, our proofs are elementary and do not rely on Martin boundary theory.

ALEA, Lat. Am. J. Probab. Math. Stat. 13, 545–561, 2016 Download: Journal · Preprint

We consider random walks indexed by arbitrary finite random or deterministic trees. We derive a simple sufficient criterion which ensures that the maximal displacement of the tree-indexed random walk is determined by a single large jump. This criterion is given in terms of four quantities: the tail and the expectation of the random walk steps, the height of the tree and the number of its vertices. The results are applied to critical Galton–Watson trees with offspring distributions in the domain of attraction of a stable law.

with Rémi Rhodes, Vincent Vargas and Ofer Zeitouni
Ann. Inst. H. Poincaré Probab. Statist. 52, 1281–1320, 2016 Download: Journal · Preprint

We initiate in this paper the study of analytic properties of the Liouville heat kernel. In particular, we establish regularity estimates on the heat kernel and derive non trivial lower and upper bounds.

with Olivier Hénard
Journal de l'Ecole Polytechnique 3, 365–400, 2016 Download: Journal · Preprint

We study random trees which are invariant in law under the operation of contracting each edge independently with probability $p\in (0,1)$. We show that all such trees can be constructed through Poissonian sampling from a certain class of random measured $\mathbb R$-trees satisfying a natural scale invariance property. This has connections to exchangeable partially ordered sets, real-valued self-similar increasing processes and quasi-stationary distributions of Galton–Watson processes.

with Elliot Paquette
Israel Journal of Mathematics 212, 337–384, 2016 Download: Journal · Preprint

We consider a random interval splitting process, in which the splitting rule depends on the empirical distribution of interval lengths. We show that this empirical distribution converges to a limit almost surely as the number of intervals goes to infinity. We give a characterization of this limit as a solution of an ODE and use this to derive precise tail estimates. The convergence is established by showing that the size-biased empirical distribution evolves in the limit according to a certain deterministic evolution equation. Although this equation involves a non-local, non-linear operator, it can be studied thanks to a carefully chosen norm with respect to which this operator is contractive. In finite-dimensional settings, convergence results like this usually go under the name of stochastic approximation and can be approached by a general method of Kushner and Clark. An important technical contribution of this article is the extension of this method to an infinite-dimensional setting.

with Itai Benjamini
in Geometric Aspects of Functional Analysis, Israel Seminar (GAFA) 2011-2013, Lecture Notes in Mathematics, Vol. 2116, 47–51, Bo'az Klartag, Emanuel Milman (eds.), Springer, 2014 Download: Journal · Preprint

We consider first passage percolation (FPP) on $\mathbb {T}_{d}\times G$, where $\mathbb {T}_d$ is the $d$-regular tree ($d\ge 3$) and $G$ is a graph containing an infinite ray $0,1,2,…$. It is shown that for a fixed vertex $v$ in the tree, the fluctuation of the distance in the FPP metric between the points $(v,0)$ and $(v,n)$ is of the order of at most $\log n$. We conjecture that the real fluctuations are of order $1$ and explain why.

with Ofer Zeitouni
Annales de l'Institut Henri Poincaré, Probabilités et Statistiques 52, 1144–1160, 2016 Download: Journal · Preprint

We consider the distribution of the maximum $M_T$ of branching Brownian motion with time-inhomogeneous variance of the form $\sigma ^2(t/T)$, where $\sigma (\cdot )$ is a strictly decreasing function. This corresponds to the study of the time-inhomogeneous Fisher–Kolmogorov-Petrovskii-Piskunov (F-KPP) equation $ F_t(x,t)=\sigma ^2(1-t/T)F_{xx} (x,t)/2+ g(F(x,t))$, for appropriate nonlinearities $g(\cdot )$. Fang and Zeitouni (2012) showed that $M_T-v_\sigma T$ is negative of order $T^{1/3}$, where $v_\sigma =\int _0^1 \sigma (s)ds$. In this paper, we show the existence of a function $m'_T$, such that $M_T-m'_T$ converges in law, as $T\rightarrow \infty $. Furthermore, $m'_T=v_\sigma T - w_\sigma T^{1/3} - \sigma (1)\log T + O(1)$ with $w_\sigma = 2^{-1/3}\alpha _1 \int _0^1 \sigma (s)^{1/3} |\sigma '(s)|^{2/3}\,ds$. Here, $-\alpha _1=-2.33811...$ is the largest zero of the Airy function $\operatorname {Ai}$. The proof uses a mixture of probabilistic and analytic arguments.

Probability Theory and Related Fields 166, 1061–1173, 2016 Download: Journal · Preprint

We consider branching Brownian motion on the real line with the following selection mechanism: Every time the number of particles exceeds a (large) given number $N$, only the $N$ right-most particles are kept and the others killed. After rescaling time by $\log ^3N$, we show that the properly recentred position of the $\lfloor \alpha N\rfloor $-th particle from the left, $\alpha \in (0,1)$, converges in law to an explicitly given spectrally positive Lévy process. This behaviour has been predicted to hold for a large class of models falling into the universality class of the FKPP equation with weak multiplicative noise [Brunet et al., Phys. Rev. E 73(5), 056126 (2006)] and is proven here for the first time for such a model.

with Ofer Zeitouni
Ann. Appl. Probab. 24, 2070–2090, 2014 Download: Journal · Preprint

Consider a $d$-ary rooted tree ($d\geq 3$) where each edge $e$ is assigned an i.i.d. (bounded) random variable $X(e)$ of negative mean. Assign to each vertex $v$ the sum $S(v)$ of $X(e)$ over all edges connecting $v$ to the root, and assume that the maximum $S_n^*$ of $S(v)$ over all vertices $v$ at distance $n$ from the root tends to infinity (necessarily, linearly) as $n$ tends to infinity. We analyze the Metropolis algorithm on the tree and show that under these assumptions there always exists a temperature $1/\beta $ of the algorithm so that it achieves a linear (positive) growth rate in linear time. This confirms a conjecture of Aldous (Algorithmica, 22(4):388-412, 1998). The proof is obtained by establishing an Einstein relation for the Metropolis algorithm on the tree.

with Jean Bérard
Electronic Journal of Probability 19, no. 22, 1–17, 2014 Download: Journal · Preprint

We consider a system of $N$ particles on the real line that evolves through iteration of the following steps: 1) every particle splits into two, 2) each particle jumps according to a prescribed displacement distribution supported on the positive reals and 3) only the $N$ right-most particles are retained, the others being removed from the system. This system has been introduced in the physics literature as an example of a microscopic stochastic model describing the propagation of a front. Its behavior for large $N$ is now well understood – both from a physical and mathematical viewpoint – in the case where the displacement distribution admits exponential moments. Here, we consider the case of displacements with regularly varying tails, where the relevant space and time scales are markedly different. We characterize the behavior of the system for two distinct asymptotic regimes. First, we prove convergence in law of the rescaled positions of the particles on a time scale of order $\log N$ and give a construction of the limit based on the records of a space-time Poisson point process. Second, we determine the appropriate scaling when we let first the time horizon, then $N$ go to infinity.

Electronic Communications in Probability 18, no. 5, 1–9, 2013 Download: Journal · Preprint

We call a point process $Z$ on $\mathbb R$ exp-1-stable if for every $\alpha ,\beta \in \mathbb R$ with $e^\alpha +e^\beta =1$, $Z$ is equal in law to $T_\alpha Z+T_\beta Z'$, where $Z'$ is an independent copy of $Z$ and $T_x$ is the translation by $x$. Such processes appear in the study of the extremal particles of branching Brownian motion and branching random walk and several authors have proven in that setting the existence of a point process $D$ on $\mathbb R$ such that $Z$ is equal in law to $\sum _{i=1}^\infty T_{\xi _i} D_i$, where $(\xi _i)_{i\ge 1}$ are the atoms of a Poisson process of intensity $e^{-x}\,dx$ on $\mathbb R$ and $(D_i)_{i\ge 1}$ are independent copies of $D$ and independent of $(\xi _i)_{i\ge 1}$. In this note, we show how this decomposition follows from the classic LePage decomposition of a (union)-stable point process. Moreover, we give a short proof of it in the general case of random measures on $\mathbb R$.

Annales de l'institut Henri Poincare (B) Probability and Statistics 49, 428–455, 2013 Download: Journal · Preprint

We study supercritical branching Brownian motion on the real line starting at the origin and with constant drift $c$. At the point $x > 0$, we add an absorbing barrier, i.e. individuals touching the barrier are instantly killed without producing offspring. It is known that there is a critical drift $c_0$, such that this process becomes extinct almost surely if and only if $c \ge c_0$. In this case, if $Z_x$ denotes the number of individuals absorbed at the barrier, we give an asymptotic for $P(Z_x=n)$ as $n$ goes to infinity. If $c=c_0$ and the reproduction is deterministic, this improves upon results of L. Addario-Berry and N. Broutin [1] and E. A\"ıdékon [2] on a conjecture by David Aldous about the total progeny of a branching random walk. The main technique used in the proofs is analysis of the generating function of $Z_x$ near its singular point $1$, based on classical results on some complex differential equations.

with Robert Görke, Andrea Schumm, Christian Staudt and Dorothea Wagner
J. Exp. Algorithmics 18, 1.5:1.1–1.5:1.29, 2013 Download: Journal · Preprint

Maximizing the quality index modularity has become one of the primary methods for identifying the clustering structure within a graph. Since many contemporary networks are not static but evolve over time, traditional static approaches can be inappropriate for specific tasks. In this work, we pioneer the NP-hard problem of online dynamic modularity maximization. We develop scalable dynamizations of the currently fastest and the most widespread static heuristics and engineer a heuristic dynamization of an optimal static algorithm. Our algorithms efficiently maintain a modularity-based clustering of a graph for which dynamic changes arrive as a stream. For our quickest heuristic we prove a tight bound on its number of operations. In an experimental evaluation on both a real-world dynamic network and on dynamic clustered random graphs, we show that the dynamic maintenance of a clustering of a changing graph yields higher modularity than recomputation, guarantees much smoother clustering dynamics, and requires much lower runtimes. We conclude with giving sound recommendations for the choice of an algorithm.

with Robert Görke, Christian Staudt and Dorothea Wagner
in Experimental Algorithms, Lecture Notes in Computer Science 6049, 436–448, Paola Festa (ed.), Springer Berlin / Heidelberg, 2010 Download: Journal · Preprint

Maximizing the quality index modularity has become one of the primary methods for identifying the clustering structure within a graph. As contemporary networks are not static but evolve over time, traditional static approaches can be inappropriate for specific tasks. In this work we pioneer the NP-hard problem of online dynamic modularity maximization. We develop scalable dynamizations of the currently fastest and the most widespread static heuristics and engineer a heuristic dynamization of an optimal static algorithm. Our algorithms efficiently maintain a modularity-based clustering of a graph for which dynamic changes arrive as a stream. For our quickest heuristic we prove a tight bound on its number of operations. In an experimental evaluation on both a real-world dynamic network and on dynamic clustered random graphs, we show that the dynamic maintenance of a clustering of a changing graph yields higher modularity than recomputation, guarantees much smoother clustering dynamics and requires much lower runtimes. We conclude with giving recommendations for the choice of an algorithm.